othar@ernie.Berkeley.EDU (Othar Hansson) (10/26/89)
Hoping not to invoke the wrath of the anti-featurists, I'd like to pose the following problem, whose solution calls for a new language feature. Imagine that I had a really nice matrix class definition, and wrote the following code: #include "reallynicematrixclass.h" matrix A,B,C,D,E; ... // give the matrices bounds, and fill them with values matrix ANSWER = A * B * C * D * E; // use matrix::operator*(matrix&, matrix&) Now, if I remember, C++ and C will parenthesize this expression from left to right, evaluating A*B first, etc. However, one of the first things we learn in a class on algorithms is the dynamic programming example of optimizing the order of matrix multiplications. Depending on the matrix bounds, this might be the parenthesization which runs the fastest: ANSWER = (A * B) * ((C * D) * E) For those who aren't familiar with this problem, consider the case where C has 1 row, and E has 1 column -- then C*D*E ends up being a 1x1 matrix, which is pretty cheap to multiply by A*B (note that B must have 1 column also). You can construct examples where the cost ratio (optimal evaluation order/left-to-right) is arbitrarily high. The example is also generalizable beyond matrices, to the evaluation of arbitrary expressions of arbitrary types. In this case, where the bounds are run-time defined, the programmer can't parenthesize the expression in advance. In C++ version 8.0, how are we going to allow the code to decide order of evaluation at run-time? It would be nice if, for every operatorX(), there were a costX(), which estimates the cost of the operation X for particular arguments, and when the order of operation is not specified and costX() is defined, code is generated which checks the costs and then produces a cheapest order of evaluation. Anyone have any other examples, or other ideas on how to solve this puzzle? I'm not seriously suggesting adding this to the menagerie of C++ language features, but things like it are certainly already appearing in theorem-provers, etc. Othar Hansson CS Division UC Berkeley othar@ernie.berkeley.edu
jack@odi.com (Jack Orenstein) (10/26/89)
In article <32164@ucbvax.BERKELEY.EDU> othar@ernie.Berkeley.EDU (Othar Hansson) writes: >Imagine that I had a really nice matrix class definition, and wrote >the following code: > >#include "reallynicematrixclass.h" >matrix A,B,C,D,E; > >... // give the matrices bounds, and fill them with values > >matrix ANSWER = A * B * C * D * E; // use matrix::operator*(matrix&, matrix&) > >Now, if I remember, C++ and C will parenthesize this expression from >left to right, evaluating A*B first, etc. However, one of the first >things we learn in a class on algorithms is the dynamic programming >example of optimizing the order of matrix multiplications. Depending >on the matrix bounds, this might be the parenthesization which runs >the fastest: > >ANSWER = (A * B) * ((C * D) * E) >... >In this case, where the bounds are run-time defined, the programmer >can't parenthesize the expression in advance. In C++ version 8.0, how >are we going to allow the code to decide order of evaluation at >run-time? Probably the same as in 1.2 or 2.0. Define matrix::operator+, operator*, etc. to construct a tree representing the expression. Then, when the value of the expression is needed, e.g. in assignment to ANSWER above, or in a comparison, optimize and evaluate. Jack Orenstein Object Design, Inc.
peter@mit-amt.MEDIA.MIT.EDU (Peter Schroeder) (10/26/89)
>operator*, etc. to construct a tree representing the expression. Then, >when the value of the expression is needed, e.g. in assignment to >ANSWER above, or in a comparison, optimize and evaluate. > >Jack Orenstein >Object Design, Inc. Does anybody have PD code that does this? I'd love to see some of it as a learning aid. (Plus, it seems to hairy to reinvent if somebody already did it...) Peter peter@media-lab.media.mit.edu
jack@odi.com (Jack Orenstein) (10/27/89)
In article <893@mit-amt.MEDIA.MIT.EDU> peter@media-lab.media.mit.edu (Peter Schroeder) writes: >>operator*, etc. to construct a tree representing the expression. Then, >>when the value of the expression is needed, e.g. in assignment to >>ANSWER above, or in a comparison, optimize and evaluate. >Does anybody have PD code that does this? I'd love to see some of it as a >learning aid. (Plus, it seems to hairy to reinvent if somebody already did >it...) I'll bet that someone working with CSG (constructive solid geometry) representations in C++ has done this. Instead of addition and multiplication, there is union and intersection of 3d primitives, (there are other operations as well). Since you're at MIT, try someone involved with mechanical CAD or solid modelling. Jack Orenstein Object Design, Inc.