RE: Undefined evaluation order

[Dave Berry <dave@kal.com>]

May I toss in a possible complication?   I'm thinking of numeric code, and
the possibilities of optimisation.  To take a simple example, (a * b * 0.0)
should always be zero.  Except that (a * b) could raise an exception or
return a NaN.  I imagine there exist more complex numeric optimisations that
a compiler may wish to perform.

So my question is whether numeric operations might be hampered by requiring
a defined evaluation order, even in the case that changing the order has a
visible (and desired!) effect.  I'm not a numeric programmer, and I know
there are some numeric programmers on the list, so perhaps they would care
to comment.

Perhaps an alternative would be to specify the evaluation order, but allow
the compiler to modify the evaluation order to reduce the possibilities of
NaN results or numeric exceptions.  It wouldn't be as elegant as a universal
rule, but might be more practical.

Dave.


-----Original Message-----
From: Greg Morrisett [mailto:jgm@cs.cornell.edu]
Sent: Wednesday, October 11, 2000 1:23 PM
To: 'Hendrik Tews'
Cc: caml-list@inria.fr
Subject: RE: Undefined evaluation order


> I would like to vote for leaving the evaluation order
> unspecified (implicitly repeating all suitable arguments from
> previous postings). The specification should only regulate the
> necessary things not more.

I don't see why.  As far as I can tell, the only reason
to not specify the order is for performance.  I've never
seen a systematic study that significant performance
gains are achievable across a range of applications.
Most compilers only do very local re-orderings, and
these can typically be achieved with local effects 
analysis (at least for languages like ML that are 
relatively effect free.)  

We've heard promises of expression-level parallelism 
since the dawn of Fortran and Lisp.  But for 40 years,
they speedups have yet to be realized because the granularity 
is always too small to do the necessary synchronization
for multi-processors, and the granularity is too large
for instruction-level parallelism (i.e., other hazards
manifest.)  If you truly believe that magic compilers
will someday come along and parallelize things, then
why are you worried that these compilers will be stopped
by a specified evaluation order?  

IMHO, there are compelling reasons to at least specify
an evaluation order, if not to standardize on left-to-
right.  In spite of the fact that programmer's *should*
realize that expressions could be evaluated in any order,
they tend to assume the order that the current compiler
uses.  Then when someone else ports the code, or the
compiler changes, things break.  

As I mentioned earlier, when teaching, it's nice for 
a language to be simple and uniform.  Explaining to
a student why:

	let x = input() in
	let y = input() in
	(x,y)

is not equivalent to:

	(input(), input())

is one more thing that confuses them -- especially when
we emphasize that the whole point of anonymous functions
is to avoid naming things that need not be named!

A standard trick for Scheme coders is, as someone suggested,
to randomize the order of evaluation in the hopes of
tripping across such bugs.  Ugh.  Maybe the type-checker
should just randomly type-check a few expressions too :-)

If you're going to have an unspecified order of evaluation,
then I think you realistically need an effects analysis
in order to warn the programmer that what they are writing
is dependent upon the order.  Unfortunately, either the
analysis would need to be global (to get rid of all the
false positives) or else you'd have to augment function 
types with effects information, add in polymorphic effects,
etc.  In other words, you're buying into a whole ball of wax.  
Neither option seems all that wonderful.  

-Greg