Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!ucbvax!ernie.Berkeley.EDU!othar
From: othar@ernie.Berkeley.EDU (Othar Hansson)
Newsgroups: comp.lang.c++
Subject: puzzle/problem/yet another new feature
Message-ID: <32164@ucbvax.BERKELEY.EDU>
Date: 25 Oct 89 21:57:57 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: othar@ernie.Berkeley.EDU (Othar Hansson)
Organization: University of California, Berkeley
Lines: 49

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