RE: Undefined evaluation order: define it for constructors ?

RE: Undefined evaluation order: define it for constructors ?

[Dave Berry]

Map is a function that really can be evaluated in parallel.  There is a
project at Heriot-Watt university that translates pure SML programs to run
on a parallel processor.  Array.map can potentially be run in parallel on
SIMD machines too.  So there is an argument for not specifying the order of
traversal of these functions (although this need not affect the language
definition).

Dave.

-----Original Message-----
From: Hugo Herbelin [mailto:Hugo.Herbelin@inria.fr]
Sent: Thursday, October 12, 2000 2:27 PM
To: garrigue@kurims.kyoto-u.ac.jp
Cc: caml-list@inria.fr
Subject: Re: Undefined evaluation order: define it for constructors ?

[Excerpt]
  It is sometimes useful to do side-effects with "List.map" (or
"Array.map"): it leads to code more readable than if using
"fold_left". I'd be happy if the evaluation order of "map" in the
interface were specified, as it is the case (for a good reason) for
the "iter" functional. 

RE: Undefined evaluation order

[Greg Morrisett]

> 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

RE: Undefined evaluation order: define it for constructors ?

[Jacques Garrigue]

Interesting that so many people would favour left-to-right order.

First a tiny addition: there seems to be a belief that evaluation in
ocaml is always right-to-left. This is true for ocaml2, but not always
for ocaml3, since (even in classic mode) optional arguments can be
passed in a different order. In such cases the compiler is free to
choose any evaluation order, in practice this is right-to-left, but
according to the type.

# let f ?(x=0) ?(y=0) () = x + y;;
val f : ?x:int -> ?y:int -> unit -> int = <fun>
# f ~y:(print_int 2; 2) ~x:(print_int 3; 3) ();;
23- : int = 5

As Xavier wrote, this would be pretty easy to automatically convert
the program as to provide strict left-to-right evaluation (according
to the text), but this is another example of potential tiny
innefficiency.
Moreover, strict left-to-right order also means that the function must
be evaluated first. For instance
    (f (f1 a1)) (f2 a2)
would lead to (flattening all computations in sub-expressions)
    let x1 = f1 a1 in let f0 = f x1 in let x2 = f2 a2 in f0 x2
rather than the expected
    let x1 = f1 a1 in let x2 = f2 a2 in f x1 x2
In bytecode the second form is more efficient, since it often avoids the
creation of a closure f0 (the binary application is detected at
runtime).


Another remark is that all the problems I see are due to
unspecified evaluation order in value construction, not in function
application. That is, tuples (Greg's example), records (Brian),
and lists (Pierre, old List.map), where the syntax really suggests
some sequencing.

On the other hand, function application is more symmetrical, and one
is less tempted by making assumptions about it.
The only caml program I've seen depending on evaluation order in
function application was by a friend of mine in Caml V3, about 10
years ago, and this was because he didn't know about ";" as a
sequencer :-)

Value construction and function application are distinguished
syntactically in Caml, so they might be considered independently.
I have a feeling that left-to-right order in value construction would
not be that expensive, even in the bytecode interpreter. How is it?

Regards,

Jacques
---------------------------------------------------------------------------
Jacques Garrigue      Kyoto University     garrigue at kurims.kyoto-u.ac.jp
		<A HREF=http://wwwfun.kurims.kyoto-u.ac.jp/~garrigue/>JG</A>

Re: Undefined evaluation order: define it for constructors ?

[Hugo Herbelin]

  As Jacques Garrigue underlines it, discussions are less about the
evaluation order of arguments of functions that those of tuples and
the latter looks like strictly arbitrary (I guess it was initially
chosen right-to-left by consistency with the evaluation order of
arguments which is not arbitrary). To make evaluation of tuple LR or
RL is then just a matter of principle... and to guarantee it for the
user also!

  It is sometimes useful to do side-effects with "List.map" (or
"Array.map"): it leads to code more readable than if using
"fold_left". I'd be happy if the evaluation order of "map" in the
interface were specified, as it is the case (for a good reason) for
the "iter" functional. 

  Furthermore, in O'Caml (in contrast with Caml-Light -- a teaching
language!), List.map and Array.map are written in such a way they
evaluate as we write lists, i.e. from left to right! Is it not
the right time to say it?

  Regarding the evaluation order of arguments for functions, is it
only to adapt polymorphism with the stack-model on which the bytecode
interpreter relies? If so, what would be the overhead if the frame
were first allocated then arguments evaluated LR but put in the frame
in the _reverse_ way in order (possibly incremental) capture of
arguments by the function continues to work.

                                                  Hugo