Parameter evaluation order

Parameter evaluation order

["Márk S. Zoltán"]

I was recently thinking about parameter evaluation order and how come it 
is unspecified in OCaml. Maybe this was already discussed here, but I do 
not recall it and cannot find it, either. Do not get me wrong, I do not 
have an unsurmontable problem with unspecified parameter evaluation 
ordering, and in a world full of languages with similar disclaimers I 
could not even have a problem. Also, side effects in parameters is just 
ugly. So the current shape of the language is fine with me.

But I do think that currying + strictness + side-effects => 
left-to-right evaluation order.  That is because a multi-parameter 
function application should be functionally equivalent to a closure 
taking the first (== leftmost) parameter and returning a closure which 
takes the second parameter etc. while parameters should be evaluated 
before passing, as per strictness. 

Consider the following code:

==== 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 ()
==============

The three let ()'s should be functionally equivalent, and yet they are not:

---------------------
$ ocaml ordertest.ml
1234
2143
4321
---------------------

ocamlopt creates a different outcome, but that is well known: the last 
line reads 1234.

Of course, if this kind of logic was applied, labels and FFI's would be 
difficult to handle. Probably even enrichment of the type system with 
'has side effect' and forbidding the use of expressions with such types 
in parameters would be simpler than that, not that I advocate either 
solution. I do not say we should have left-to-right evaluation order, 
only that it would be more logical.  Am I wrong?

    M-

Re: [Caml-list] Parameter evaluation order

[Alain Frisch]

Márk S. Zoltán wrote:
> But I do think that currying + strictness + side-effects =>
> left-to-right evaluation order.  That is because a multi-parameter
> function application should be functionally equivalent to a closure
> taking the first (== leftmost) parameter and returning a closure which
> takes the second parameter 

It is, but your conclusion about left-to-right evaluation order is
wrong. It's just that the binary application operator evaluates first
its second argument (the function's argument), then its first argument
(the functional value), and finally applies the function to the
argument. An application (e1 e2) is semantically equivalent to:  (let y
= e2 in let x = e1 in x y). Hence you get right-to-left evaluation order
(but this is not specified).

-- Alain

Re: [Caml-list] Parameter evaluation order

["Márk S. Zoltán"]

First of all, thank you for your answers. I thought a bit about this 
stuff - took a while. For reasons I am too embarrassed to explain, I 
prefer to answer a number of posts in one reply.

Alain Frisch wrote:

>
>It is, but your conclusion about left-to-right evaluation order is
>wrong. It's just that the binary application operator evaluates first
>its second argument (the function's argument), then its first argument
>(the functional value), and finally applies the function to the
>argument. An application (e1 e2) is semantically equivalent to:  (let y
>= e2 in let x = e1 in x y). Hence you get right-to-left evaluation order
>(but this is not specified).
>
>-- Alain
>  
>
I think I have to retract my equation completely: right now I do not see 
how *any* evaluation order would be implied by currying + strictness + 
side effects at all. Alain, in your model right-to-left evaluation is a 
consequence of defining (e1 e2) as you do; if it was defined to be (let 
x = e1 in let y = e2 in x y), we would have left-to-right evaluation. So 
the evaluation order is introduced by the definition of the functional 
application, not by strictness, currying etc.

I still wonder why did I implicitly assume this latter definition for 
function application. It seemed so straightforward, and it is also the 
order in which application of curried functions is usually explained 
(the explanation proceeds this way, it does not ever say that the actual 
ordering is also left-to-right). Sorry, guys.


Damien Doligez wrote:

> The problem (and historical reason for OCaml's unspecified order) is  
> that
>
> currying + side-effects + left-to-right evaluation order => inefficiency

That line of reasoning is fine with me, as I would not make use of a 
declared parameter evaluation order anyway, while I constantly rely on 
the performance of OCaml. Whoever relies on parameter evaluation order 
is probably capable of committing other hideous crimes, too.


brogoff wrote:

>It's a fun topic to chat about, but if you were allowed one change in the
>language, surely this wouldn't be it?  :-) 
>
Absolutely so. Tail recursion modulo cons is more important.

Regards

    M-

Re: [Caml-list] Parameter evaluation order

[Damien Doligez]

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

Re: [Caml-list] Parameter evaluation order

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1251 bytes --]

On Mon, 2005-08-22 at 18:50 +0200, Damien Doligez wrote:

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

what data, and possibly annotations, would be required to solve this
problem?

For example if all functions are total and pure 
then the above problem vanishes.

Felix doesn't permit functions to have side-effects,
however this isn't enough for full optimisation in 
the presence of exceptions, for example. Additionally,
lazy evaluation can save the setting of a variable,
a sufficient condition being purity (non-dependence on variables
as well as having no side-effects) *and* totality.

Seems like these properties:

* writes variables (side-effect)
* reads variables (side-dependence)
* raises exception
* fails to terminate

impact evaluation strategy. It would be good to know which
properties of things would allow which evaluation strategies.


-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: [Caml-list] Parameter evaluation order

[Damien Doligez]

On Aug 23, 2005, at 09:12, skaller wrote:



> On Mon, 2005-08-22 at 18:50 +0200, Damien Doligez wrote:
>
>
>
>
>> 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.
>>
>>
>>
>
> what data, and possibly annotations, would be required to solve this
> problem?
>
>

The most direct solution is to introduce the notion of function arity
in the type system.  As far as I know, there is no theoretical  
difficulty,
the biggest problem is to find a syntax that satisfies everyone...

-- Damien

Re: [Caml-list] Parameter evaluation order

[Igor Pechtchanski]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1498 bytes --]

On Tue, 23 Aug 2005, Damien Doligez wrote:

> On Aug 23, 2005, at 09:12, skaller wrote:
>
> > On Mon, 2005-08-22 at 18:50 +0200, Damien Doligez wrote:
> >
> > > 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.
> >
> > what data, and possibly annotations, would be required to solve this
> > problem?
>
> The most direct solution is to introduce the notion of function arity in
> the type system.  As far as I know, there is no theoretical difficulty,
> the biggest problem is to find a syntax that satisfies everyone...

Hi,

Been lurking on this thread, decided to chime in.

This may be a naïve question, but what's wrong with tuples?  It doesn't
seem like the order in which the tuple components are evaluated matters
(in terms of efficiency, that is).  Am I missing something?
	Igor
-- 
				http://cs.nyu.edu/~pechtcha/
      |\      _,,,---,,_		pechtcha@cs.nyu.edu
ZZZzz /,`.-'`'    -.  ;-;;,_		igor@watson.ibm.com
     |,4-  ) )-,_. ,\ (  `'-'		Igor Pechtchanski, Ph.D.
    '---''(_/--'  `-'\_) fL	a.k.a JaguaR-R-R-r-r-r-.-.-.  Meow!

If there's any real truth it's that the entire multidimensional infinity
of the Universe is almost certainly being run by a bunch of maniacs. /DA

Re: [Caml-list] Parameter evaluation order

[Damien Doligez]

On Aug 23, 2005, at 15:34, Igor Pechtchanski wrote:

> This may be a naïve question, but what's wrong with tuples?  It  
> doesn't
> seem like the order in which the tuple components are evaluated  
> matters
> (in terms of efficiency, that is).  Am I missing something?

Tuples, like currying, is only an encoding.  If you cannot distinguish
between a 4-argument function and a function that takes a 4-tuple as
argument, you have to allocate the tuple in the heap instead of passing
the 4 arguments directly in registers.  Inefficient.

Or you have to make your compiler guess which is which, compile some
functions as taking 4 arguments and some as taking a tuple, and  
translate
between the two representations as needed, in a way that is very similar
to what happens with curried functions, except that this time guessing
"n-ary" every time is not quite as good a heuristic.

Higher-order functions are particularly good at exposing this problem,
because you only know the type of their functional arguments, and you
have to deduce the calling convention from no more information than the
type itself.  But the problem also appears with separate compilation.

-- Damien

Re: Parameter evaluation order

[Hao-yang Wang]

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

It seems to me that as long as evaluate f the last, we are ok. We can 
specify the evaluation order of the _parameters_ left-to-right (i.e., e1 
then e2, e3, e4, and finally f), without running into the efficiency 
problem.

Cheers,
Hao-yang Wang 

Re: [Caml-list] Re: Parameter evaluation order

[Damien Doligez]

On Aug 24, 2005, at 03:24, Hao-yang Wang wrote:


>> 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.
>>
>>
>
> It seems to me that as long as evaluate f the last, we are ok.
>

Yes.


> We can specify the evaluation order of the _parameters_ left-to-right
> (i.e., e1 then e2, e3, e4, and finally f), without running into the
> efficiency problem.
>

No, that is a contradiction.  f is an arbitrary expression of the  
language,
for example (g e0), so the code above might well be in fact:

   g e0 e1 e2 e3 e4

Now, if you evaluate f last, you are obviously not evaluating the  
arguments
in left-to-right order, since you evaluate e0 after the others.  In  
order to
stay consistent, you have to evaluate them in right-to-left order.

In fact, when all your functions are curried there are only two possible
choices: evaluate the function first, or the argument first.  There is
no such thing as a multi-argument function application.  Evaluating f
last forces you to evaluate the arguments in right-to-left order in
expressions like the above.

-- Damien

Re: [Caml-list] Re: Parameter evaluation order

[Christophe Raffalli]

If you really want left-to-right evaluation order in ocaml, use camlp4 
to change the syntax with a postfix function application (with the 
argument to the left).

That will be homogenous with type application !

:-)

or with a right-associtive operator if you do not like camlp4:

# let (@) x f = f x
val ( @ ) : 'a -> ('a -> 'b) -> 'b = <fun>
# 1 @ 2 @ (+)
- : int = 3

Berkeley DB

[Joel Reymont]

Folks,

How do I find out if my version of OCaml was built with Berkeley DB  
(SleepyCat) support?

Alternatively, how do I build OCaml from the source to support BDB?  
This is based on my understanding that BDB support is built-in since  
I'm not able to find any BDB packages for OCaml more recent than 2002.

     Thanks, Joel

--
http://wagerlabs.com/uptick

Re: [Caml-list] Re: Parameter evaluation order

[brogoff]

On Wed, 24 Aug 2005, Christophe Raffalli wrote:
> If you really want left-to-right evaluation order in ocaml, use camlp4
> to change the syntax with a postfix function application (with the
> argument to the left).
>
> That will be homogenous with type application !
>
> :-)

Alas, it doesn't help with the evaluation of order of constructors,
which is where I'd find left-to-right most helpful. One of those places
where I think SML is better, even though I usually favor efficiency
over elegance.

-- Brian

Re: [Caml-list] Re: Parameter evaluation order

[Christophe Raffalli]

brogoff a écrit :
> On Wed, 24 Aug 2005, Christophe Raffalli wrote:
> 
>>If you really want left-to-right evaluation order in ocaml, use camlp4
>>to change the syntax with a postfix function application (with the
>>argument to the left).
>>
>>That will be homogenous with type application !
>>
>>:-)
> 
> 
> Alas, it doesn't help with the evaluation of order of constructors,
> which is where I'd find left-to-right most helpful. One of those places
> where I think SML is better, even though I usually favor efficiency
> over elegance.
> 
Anyway, I always found that the application of constructor has a syntax 
to near the syntax of function application:

f (x,y) and A (x,y) are both meaningfull ...

I would prefer square bracket for constructor application, mandatory 
even for unary constructor (and maybe also constant constructor then you 
can lift the restriction about capital letter)

> -- Brian
> 

Re: [Caml-list] Re: Parameter evaluation order

[brogoff]

On Wed, 24 Aug 2005, Christophe Raffalli wrote:
> Anyway, I always found that the application of constructor has a syntax
> to near the syntax of function application:
>
> f (x,y) and A (x,y) are both meaningfull ...
>
> I would prefer square bracket for constructor application, mandatory
> even for unary constructor (and maybe also constant constructor then you
> can lift the restriction about capital letter)

The examples that bother me most are record constructors, where I want to
read structured data from a file into a record. And of course :: (which is
just sugar) too.

If it were just functions, it would be less annoying, but left to right is
less surprising.

It's a fun topic to chat about, but if you were allowed one change in the
language, surely this wouldn't be it? :-)

-- Brian

Re: [Caml-list] Re: Parameter evaluation order

[Jon Harrop]

On Wednesday 24 August 2005 21:25, brogoff wrote:
> > I would prefer square bracket for constructor application, mandatory
> > even for unary constructor (and maybe also constant constructor then you
> > can lift the restriction about capital letter)

It would be nice if variant constructors were functions (as they are in SML, 
IIRC). So you could do this:

# type num = Int of int | Float of float;;
type num = Int of int | Float of float
# List.map Int [1; 2; 3];;
- : num list = [Int 1; Int 2; Int 3]

Rather than having to do "List.map (fun i -> Int i) ...". That wouldn't work 
with polymophic variants though, at least not trivially.

If variant constructors always accepted a single, tuple argument could it not 
be optimised away in most cases? Also, could constructors be curried instead 
of using tuples (or syntax that looks like tuples)?

> The examples that bother me most are record constructors, where I want to
> read structured data from a file into a record. And of course :: (which is
> just sugar) too.

Yes. It would be nice if (fun h t -> h::t) could be written infix as ( :: ), 
as operators are. In fact, couldn't that be added without breaking backward 
compatibility?

> It's a fun topic to chat about, but if you were allowed one change in the
> language, surely this wouldn't be it? :-)

Good question. :-)

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Re: Parameter evaluation order

[Christophe Raffalli]

 >
 > The examples that bother me most are record constructors, where I want to
 > read structured data from a file into a record. And of course :: 
(which is
 > just sugar) too.
 >

I did not know and completely agree with you:

# type test = { a : int; b : int }
type test = { a : int; b : int; }
# { a = (print_string "a"; 1); b = (print_string "b"; 2)};;
ba- : test = {a = 1; b = 2}

This looks strange, because the semicolumn is used both to specify order 
evaluation left-to-right in sequence and right-to-left in record.

And the pb of function application is not there, you could evaluate with 
the same efficiency record in any order, you know the number of 
arguments and what you should do with them at compile time.

Moreover, if you want to unify record and modules ... then you have no 
choice, no body wants right-to-left (I should say bottom-to-top :-)
evaluation order in modules :-)

Re: [Caml-list] Re: Parameter evaluation order

[Jon Harrop]

On Friday 26 August 2005 10:53, Christophe Raffalli wrote:
> This looks strange, because the semicolumn is used both to specify order
> evaluation left-to-right in sequence and right-to-left in record.

I haven't checked but it is probably undefined, rather than right-to-left in 
records.

Semicolons are used in many places in OCaml's grammar. Would you expect the 
members of a list literal to be evaluated left-to-right, for example?

# [print_endline "1"; print_endline "2"];;
2
1
- : unit list = [(); ()]

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

Re: [Caml-list] Re: Parameter evaluation order

[Christophe Raffalli]

Jon Harrop a écrit :
> On Friday 26 August 2005 10:53, Christophe Raffalli wrote:
> 
>>This looks strange, because the semicolumn is used both to specify order
>>evaluation left-to-right in sequence and right-to-left in record.
> 
> 
> I haven't checked but it is probably undefined, rather than right-to-left in 
> records.
> 
> Semicolons are used in many places in OCaml's grammar. Would you expect the 
> members of a list literal to be evaluated left-to-right, for example?
> 
> # [print_endline "1"; print_endline "2"];;
> 2
> 1
> - : unit list = [(); ()]
> 

yes I would ...

In fact, after though, the only place where evalauation order should be 
unspecified or better, specified right-to-left is function application 
and all other case (tuple, variants (and therefore list), should be 
left-to-right.

Let me explain:

- why function should be right-to-left:

because the syntax is somehow wrong, the argument should come first !
A good way to think about it is when you write the operationnal 
semantics of call-by-value

if v is a value then (fun x -> t) v evaluates t[x:=v]

in this sentence we are looking at v first.

Another point: if you use a stack (either to define the semantics or to 
implement), the left most argument should be on the top of the stack and 
therefore pushed last.

Why are most language left-to-right: because nobody wanted to reverse 
the notation of function aplpication :-) (and if you think, the standard 
notation for numbers should also be reversed ... and whe should read 
from right to left, which is what we do when we do an addition with 
paper and pencil)

- why other contructor (tuple, records, variants) should be 
left-to-right: because this is the most natural thing to do, and in fact 
there is no semantical reason to choose one evaluation order or another 
(except for variant constructor if you consider that they are function 
like others). (except that they are people around the world that writes 
right-to-left or top-to-bottom ... what are the camlp4 guys doing for 
this poor people ;-)

- why should the evaluation order be specified: this is needed if you 
want to formally reason about programs ... as far as I know. I had like 
to find a system where I can prove programs in call-by-value whatever 
evaluation order they use ... but I do not know how to do that, without 
proving programs for all the possible evaluation order as soon as the 
argument have side effect which is too much.

- Yes, this is a pity since you may want the compiler to interleave the 
code of the various arguments to fill the pileline. But I think doing 
this when the code has no side effect is enough (like with arithmetic 
expression in a + b + c, d + e + f).

Re: [Caml-list] Re: Parameter evaluation order

[Diego Olivier Fernandez Pons]

    Bonjour,

> why should the evaluation order be specified: this is needed if you
> want to formally reason about programs ... as far as I know.

Could you elaborate more on this ?

I see the evaluation order in Caml more as a compiler optimization
problem that a semantic one. If I need a specific evaluation order, I
just sequencialize my program explicitelly.

        Diego Olivier

Re: [Caml-list] Re: Parameter evaluation order

[Christophe Raffalli]

Diego Olivier Fernandez Pons a écrit :
>     Bonjour,
> 
> 
>>why should the evaluation order be specified: this is needed if you
>>want to formally reason about programs ... as far as I know.
> 
> 
> Could you elaborate more on this ?
> 
> I see the evaluation order in Caml more as a compiler optimization
> problem that a semantic one. If I need a specific evaluation order, I
> just sequencialize my program explicitelly.
> 

Let us say you want to prove a program using references ...
one possible way is to translate is automatically in a purely functional 
program using a state monad ... then you need to specify the evaluation 
order to define the translation of

let x = f a_1 ... a_n in

which could approximately be (x' denotes the translation of x) ans s 
denotes the states holding the map table assigning values to addresses

let s,a_n  = a'_n s in
let s,a_(n-1) = a'_(n-1) s in
..
let s,a_1 = a'_1 s in
let s,x = f' s a_1 ... a_n in

to define this translation, you need to know the evaluation order and it 
is not reasonnable to
assume that the program you want to prove if fully sequentialized (and 
if you want to force sequentialized program then you should only allow 
variables as function arguments in the language definition ;-).

Remark: clearly, a good proof system should not show the monadic 
translation and hide it behind the scene ... but  such a system for full 
ML does not exist yes (as far as I know).

Re: [Caml-list] Re: Parameter evaluation order

[Christophe TROESTLER]

On Fri, 26 Aug 2005, Christophe Raffalli <christophe.raffalli@univ-savoie.fr> wrote:
> 
> Remark: clearly, a good proof system should not show the monadic 
> translation and hide it behind the scene ...

Shouldn't a good proof system show the code to be correct regardless
of the evaluation order of function args, records,...?  After all,
different evaluation orders may be interesting on different platforms
and I think programs that rely on the evaluation order (say) of
functions arguments to be correct are fragile -- they have a great
potential to be broken at the first maintenance.

On Fri, 26 Aug 2005, Fernando Alegre <fernando@cc.gatech.edu> wrote:
> 
> Ignoring efficiency concerns, may I suggest that the correct way to
> build lists is by appending elements, not prepending them:
> 
> # append('d', append('c', append('b', append('a', []))));;
> - : char list = ['a'; 'b'; 'c'; 'd']

It is not.  You have to respect their recursive definition, from which
it is clear that "append" is not a primitive operation.  The data
structure that you contruct with "append" and deconstruct with "head"
is a FIFO queue.

I've been skimming through the discussion and basically I do not
understand you guys who want a given evaluation order for function
application, constructors,...  First there is a way of imposing
evaluation order of expressions if you need it and moreover, you are
using a functional language which emphasizes immutability for which
evaluation order does not matter...

My 2¢,
ChriS

Re: [Caml-list] Re: Parameter evaluation order

[Ville-Pertti Keinonen]

Christophe Raffalli wrote:

> Jon Harrop a écrit :

>> Semicolons are used in many places in OCaml's grammar. Would you 
>> expect the members of a list literal to be evaluated left-to-right, 
>> for example?

> yes I would ...

An OCaml list is built starting with the tail.  Left-to-right evaluation 
could end up using huge amounts of temporaries.

Consider an explicit implementation of lists:

type 'a list = Cons of 'a * 'a list | Nil

Now, you'd write the list [ a; b; c; d ] (where a, b, c and d could be 
complex expressions) as

Cons (a, Cons (b, Cons (c, (Cons (d, Nil)))))

You need to have Cons (d, Nil) before you can construct Cons (c, ...) 
etc.  It's the innermost expression, so evaluating it first makes sense 
in any sensible evaluation order.

Re: [Caml-list] Re: Parameter evaluation order

[Fernando Alegre]

On Fri, Aug 26, 2005 at 03:36:31PM +0300, Ville-Pertti Keinonen wrote:

> Consider an explicit implementation of lists:
> 
> type 'a list = Cons of 'a * 'a list | Nil
> 
> Now, you'd write the list [ a; b; c; d ] (where a, b, c and d could be 
> complex expressions) as
> 
> Cons (a, Cons (b, Cons (c, (Cons (d, Nil)))))
> 
> You need to have Cons (d, Nil) before you can construct Cons (c, ...) 
> etc.  It's the innermost expression, so evaluating it first makes sense 
> in any sensible evaluation order.


Ignoring efficiency concerns, may I suggest that the correct way to
build lists is by appending elements, not prepending them:

# let append (element,list) = list @ [element];;
val append : 'a * 'a list -> 'a list = <fun>
# append('d', append('c', append('b', append('a', []))));;
- : char list = ['a'; 'b'; 'c'; 'd']

This will evaluate in the right order.

Fernando

Re: [Caml-list] Re: Parameter evaluation order

[Christophe Raffalli]

Ville-Pertti Keinonen a écrit :

 > Christophe Raffalli wrote:
 >
 >> Jon Harrop a écrit :
 >
 >
 >
 >>> Semicolons are used in many places in OCaml's grammar. Would you 
expect the members of a list literal to be evaluated left-to-right, for 
example?
 >
 >
 >
 >> yes I would ...
 >
 >
 >
 > An OCaml list is built starting with the tail.  Left-to-right 
evaluation could end up using huge amounts of temporaries.
 >

This is the same problem as the problem of a tail recursive map 
function, which is important and has reasonable solution.
the only risk is to charge the grey vals list of the GC if the 
evaluation of the list elements allocates enough memory to move 
partially constructed cons cell to the major heap.

But yet I quite agree this is a good point ... but you just need to 
redefine list as

type 'a rlist = Cons of 'a rlist * 'a | Nil

;-)

anyway one of the data type list or rlist as an efficiency problem 
whatever evaluation order you choose.

May be the good evaluation order for variants is recursive arguments 
last ? Or one should let the user choose ?

It is strange to note that records are less problematic since you can 
permutte the field to choose yourself the evaluation order ...

may be variant should have only one argument and list should be

type 'a record_list = Cons of { car : 'a; cdr : 'a list } | Nil



 > Consider an explicit implementation of lists:
 >
 > type 'a list = Cons of 'a * 'a list | Nil
 >
 > Now, you'd write the list [ a; b; c; d ] (where a, b, c and d could 
be complex expressions) as
 >
 > Cons (a, Cons (b, Cons (c, (Cons (d, Nil)))))
 >
 > You need to have Cons (d, Nil) before you can construct Cons (c, ...) 
etc.  It's the innermost expression, so evaluating it first makes sense 
in any sensible evaluation order.

Re: [Caml-list] Re: Parameter evaluation order

[skaller]

[-- Attachment #1: Type: text/plain, Size: 1242 bytes --]

On Fri, 2005-08-26 at 14:09 +0200, Christophe Raffalli wrote:

> - why should the evaluation order be specified: this is needed if you 
> want to formally reason about programs ... 

Indeterminate order is just fine for reasoning: there is no need
for a system to be fully deterministic to reason about it,
you just end up with sets of possible results instead of 
a unique one.

You can assume determinism and proceed, noting where such
assumptions matter and reporting this as a coding 'bug'
to the programmer. Or, you can make deductions based
on the assumption the programmer knew what they were
doing.

Considering this case:

[print_endline "1"; print_endline "2"];;

it is NOT clear immediately the non-determinism matters:
certainly there are two possible results, but who said
that one is not doing:

ocaml < funny_code | sort

This issue arose on the Alioth Shootout with floating point
tests where various codes generated nice ray traced images
from Jon Harrops test .. but the actual numbers were slightly
different .. what matters is how the human eye sees the
output image, determinism was only required for an artificial
reason.

-- 
John Skaller <skaller at users dot sourceforge dot net>


[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]