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: 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

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>