Re: [Caml-list] Parameter evaluation order

[Damien Doligez <damien.doligez@inria.fr>]

On Aug 20, 2005, at 00:21, Márk S. Zoltán wrote:

> But I do think that currying + strictness + side-effects => left-to- 
> right evaluation order.

The problem (and historical reason for OCaml's unspecified order) is  
that

currying + side-effects + left-to-right evaluation order => inefficiency

Suppose you want to evaluate a curried function call in left-to-right  
order:
f e1 e2 e3 e4

You must evaluate f first, then e1.  Then you must apply f to e1, giving
a new function g1.  Then you must evalue e2, then apply f1 to e2, giving
f2, etc.

That's because f might do some side effects between its arguments.   
Since
all functions are unary and you must encode n-ary functions with  
currying,
there is no way to specify (within the type system) a function that is
safe for efficient application.  You would like to evaluate f, then e1,
then e2, then e3, then e4, then the whole application at once, but you
cannot.

So the programmer wants to write a function call with 4 arguments, but
he cannot, and his code ends up doing 4 separate function calls, which
is a lot of overhead.

Hence there needs to be a notion of n-ary function at some point.  If  
not
in the type system, then within the compiler, which has to guess which
functions the programmer wants to use as n-ary, and which ones as  
curried,
and translate between the two versions as needed.  Fortunately, it's not
hard to guess, since true curried functions are almost nonexistent,  
so you
can't go wrong (efficiency-wise) if you always guess "n-ary".  The only
drawback is that you have to work harder to implement higher-order
functions, and you lose some efficiency there.

> ==== ordertest.ml =====
> let f a b c d = ()
>
> let () =
>  let ff1 = f (print_string "1") in
>  let ff2 = ff1 (print_string "2") in
>  let ff3 = ff2 (print_string "3") in
>  ff3 (print_string "4");
>  print_newline ()
>
> let () =
>  let f2 = f (print_string "1") (print_string "2")
>  in f2 (print_string "3") (print_string "4") ;
>  print_newline ()
>
> let () =
>  f
>    (print_string "1")
>    (print_string "2")
>    (print_string "3")
>    (print_string "4");
>  print_newline ()
> ==============

You'll see the problem if you try replacing your definition of f with
the following:

let f a =
   print_string "a";
   fun b ->
   print_string "b";
   fun c ->
   print_string "c";
   fun d ->
   print_string "d";
   ()
;;

Note the really strange results when compiled with ocamlopt.

All these problems disappear when you evaluate in right-to-left order,
which corresponds to a nice optimization in the original ZAM: evaluate
and push each argument on the stack, then jump to the function code.

-- Damien