Re: Undefined evaluation order

Re: Undefined evaluation order

[Gerard Huet]

At 22:35 11/10/00 +0200, Pierre Weis wrote:
>I would like to report the most difficult example I know to confuse students 
> [...]
>map add [1; 2; 3];;
>argument 3
>argument 2
>argument 1
>- : int list = [2; 3; 4]
Your students are not happy.
> [...]
>Pierre Weis

So, maybe it is time to write a course on programming in ML that will put
things up front so that people don't get bitten unexpectedly later on. 

I'll be glad to contribute to the first course. The intended style is like
FAQ,
code interspersed with comments. It is intended to teachers of ML beginners.
______________________________________________________________________________

Programming in ML - Course 1

1. Hello to the class.

You start the class by greeting everyone, telling them that it is a
programming
language class, that there is no prerequisite except knowing how to access a
computer account and using an editor, and you give them 3 informations :
a - how to login on their course account
b - what is the calling sequence to the ML top-level
c - what is the calling sequence to emacs configured with tuareg and stuff

and then you tell them a little bit of history, in fairy tale style (once upon
a time, there was LISP, there was LCF, there was (Edinburgh LCF) ML, blabla...
In this course we shall use as backend a modern implementation of ML called
Objective Caml V3.0, abbreviated Ocaml, and as front end a better syntax
defined with the Camlp4 preprocessor. 

2. Hello to the world.

This is the first programming example in any programming language : how to
print stuff on your terminal. If you do not know how to do that, you are
condemned to stay within a shallow shell, some read-eval loop interpreter, but
you do not have access to the wonderful world of your file system, operating
system, and the world wide web on Internet. So here it is :

value hello_world_in_Ocaml =
let the_inverting_demon _ = () in 
     the_inverting_demon(print_string "World!",
                         print_string "Hello ");

At this point students should react with various questions:

Question 1. Why are the two string "World!" and "Hello " written in the wrong
order ?

Answer. Look at the answer computed by ML for the value of
hello_world_in_Ocaml
and you will see that "Hello World!" gets printed, and thus the strings are
written in the right order, it is just that calling the function
the_inverting_demon executes the two print statements in reverse. 

Question 2. I do not understand how the_inverting_demon works. What is this
crazy notation ? If I type in "();" it tells me "- : unit = ()", and if I type
in "_" it tells me "Parse error", I am confused.

Answer. "()" is the unique value of data type unit, like "True" and "False"
are
the two values of data type bool. We use the dummy value "()" as the value of
statements, that is expressions which are used only for their effect, but this
way statements may be accommodated within the syntax as expressions. Thus if
you type in "print_string;" you see that print_string is a function of type
"string -> unit", and thus "print_string (print_string "Hello");" does not
print anything, since the type checker verifies that the inner expression has
type unit instead of the expected type string, and so you get a typing error
and the compilation aborts. Whereas "_" is not the representation of a value,
but of a pattern, it is the pattern that matches any value. Patterns can
appear
only in the contexts where formal parameters are expected, so you get a
parsing
error. 

Question 3. If _ matches any value, what is its type ?

Answer. If you bring the inside let expression as a top value declaration:
value the_inverting_demon _ = ();
then you see its type :
the_inverting_demon : 'a -> unit = <fun>
indicating that it takes a value of any type, since 'a is a type variable
(read
as alpha) which may be instanciated by any concrete type, and thus you may
call
the_inverting_demon ();
the_inverting_demon True;
the_inverting_demon "Hello"
and it always just returns the dummy value ().

Question 4. If it does nothing, why do you put it in the code of hello_world ?

Answer. If I remove it, I get a bug:
value buggy_hello_world_in_Ocaml = 
  (print_string "World!" print_string "Hello ");
I get "World!Hello " printed, this does not obey the spec of hello_world.

Question 5 (smart student). Why don't you write:
value hello_world = 
  (print_string "Hello " print_string "World!");

Answer. You may indeed. This is correct, and it will work not just in
Ocaml, but
in other dialects of ML, modulo adjustement of syntax. A program specification
admits many different solutions, we should not expect to have
non-redundancy in
programming; indeed there are many ways to program a task, some are more
efficient, some are more elegant, some have code that is better to understand
and maintain. 

Question 6 (dumb student). Why did you not give us hello_world in the first
place ?

Answer. Because I wanted to teach you the inverting effect of calling this
function on its two arguments, so that you understand the difference between
the_inverting_demon (print_string "World!", print_string "Hello ");
which prints "Hello World!" and 
the_inverting_demon (print_string "World!" print_string "Hello ");
which prints "World!Hello ".

[you may expect some students to leave the room at this point and look for
alternative programming courses in Java or C++]. A few brave and/or curious
students will keep asking questions as to why "," means right to left while ""
means left to right, until either a very smart student asks the following
question, or you yourself declare that the proper question to ask first is:

Question 7. Why does 
the_inverting_demon (print_string "Foo Bar");
print anything in the first place, since the_inverting_demon does not even
look
at its argument ?

Answer. Ah Ah ! This is because ML uses a strict evaluation regime: when you
call a function foo with an argument expression bar, which may be written
in ML
"foo bar" or "foo(bar)" or "(foo)bar" or "(foo bar)" or "(foo)(bar)" etc, what
happens is that first "foo" is evaluated to its (functional) value, that is a
so-called closure which encapsulates a piece of code with a representation of
the environment in which its global variables are bound to their values, then
bar is evaluated to a value, and finally we execute the code in the extended
environment. This is in contrast with other dialects of ML, such as Haskell,
which use a lazy evaluation regime, where 
the_inverting_demon (print_string "Foo Bar");
would return imediately value () without evaluating the argument to
the_inverting_demon since it is not needed, and thus without any printing
effect. Another terminology tells that Ocaml uses "call by value" whereas
Haskell uses "call by need". 

Question 8 (bright student). I still do not see why the arguments to
the_inverting_demon get evaluated from the right to the left.

Answer. Ah Ah! This is because Ocaml happens to evaluate multiple arguments
to a
function in a right to left manner. This has nothing to do with
the_inverting_demon, I just fooled you all along with a crazy name, but names
don't matter in a program, calling you functions "bug_free" or
"spec_certified"
does not help, only the program text matters. There are other dialects of ML,
such as SML, which use strict evaluation, but with left to right evaluation of
their arguments. Actually, you may test the evaluation regime of ML dialects
with the help of the following ML_tester, where we see another control
structure for programming exceptional effects:

value ML_tester () = 
let null _ = ()
in try (null(raise Left, raise Right); print_string "Haskell!")
    with [ Left -> print_string "SML!"
         | Right -> print_string "Ocaml!"
         ];

Question 9. Why did the implementers of Ocaml make this choice ?

Answer. Actually, they did not commit themselves to any particular order.
It is
more convenient to evaluate arguments from right to left in the bytecode
interpreter, as we shall see in a more advanced lesson, but the Ocaml manual
says that the order of evaluation of arguments is not specified, so that your
programs should not depend on it. And so maybe one day, after enough debate
proves conclusively that right to left has more inconvenients than advantages,
the Ocaml implementers will change their minds, and we shall change slightly
this introductory lesson.

Many questions from excited students speaking all together:
* How do you program Hello World in Haskell ?
* I typed in "(0,1);" to Ocaml and it returned the pair "(0,1)" and not the
pair "(1,0)", is this a bug ?

OK, now the course is over, see you to-morrow.

Re: Undefined evaluation order

[Ralf Treinen]

Christophe Raffalli wrote:

>
> I guess that it is does not need to much work to come up with a correct
> type system infering such types (I may be wrong ... ).
> And knowing if an expression has side effects could be usefull for the
> compiler in other cases ?

You will have to consider exceptions too: if both evaluation of e1
and e2 raise a different exception then the exception raised by
(f e1 e2) depends on the evaluation order.

-Ralf.
-- 
-------------------------------------------------------------
Ralf Treinen,      L.R.I. Bât. 490,     Université Paris-Sud,
F91405 Orsay cedex, France.        http://www.lri.fr/~treinen  

Re: Undefined evaluation order

[Christophe Raffalli]

Brian Rogoff a écrit :
> 
> On Mon, 16 Oct 2000, Christophe Raffalli wrote:
> > It seems to me that a program making use of evaluation order in function
> > or constructor application is wrong !
> 
> Why? It seems right to me, when you're reading in a file of records or
> building an AST from a file, or whatever, to depend on the evaluation
> order when building the data structure. I didn't get surprised, because I
> know OCaml is right-to-left, but I still find all of that let binding code
> redundant, especially when the records get long. There is nothing "wrong"
> about it that I can see, except that some people don't like it in concept.
> Interestingly, some people really did like it in concept and some of them
> were teachers who've witnessed beginners stumble over this very issue.
> 

Ok, I agree for record construction (because of its syntax). But then it
should be left to right avaluation order.

> > It seems easy to me to add some marking in the type system to detect
> > expression with side effects ...
> 
> I thought about this too. Something like Clean's uniqueness types? Maybe
> in OCaml 4 :)
> 
> > then one could have a warning (or even
> > an error :-) when some code depends on evaluation order and then, in
> > this case only, force left to right evaluation order.
> 
> What does this mean? That you would have the programmer manually insert
> lets to force the order, or that the compiler does so automatically?
> 

I meant that if the type system detects that the execution depends on
the evaluation order then it compiles the code to achieve left to right 
evaluation order and it also warn the user about it. 

\x13> > I am sure I would find some bugs in my programs with such a warning
-)
> 
> I think the random evaluation order that someone proposed as a test/debugging
> tool might be easier than a modification of the type system.
>

For tricky bug, the probability might be too low to have it appears
randomly. However a warning will be always there and gives you a precise
line number.

I think the extension require just a mark on each arrow which
 may be 
 ->'       (does side effect) 
 ->        (does not do side effect )
 ->_x|y|z  a disjunction of polymorphic variable

eg: 

let compose f g x = f (g x) would have type

compose : ('b ->_x 'c) -> ('a ->_y 'b) -> 'a ->_x|y 'c 

meaning that compose f g x does a side effect when receiving its third
argument if f or g does a side effect when receiving their first
argument.

I guess that it is does not need to much work to come up with a correct
type system infering such types (I may be wrong ... ).
And knowing if an expression has side effects could be usefull for the
compiler in other cases ?



-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Re: Undefined evaluation order

[Brian Rogoff]

On Mon, 16 Oct 2000, Christophe Raffalli wrote:
> It seems to me that a program making use of evaluation order in function
> or constructor application is wrong !

Why? It seems right to me, when you're reading in a file of records or
building an AST from a file, or whatever, to depend on the evaluation
order when building the data structure. I didn't get surprised, because I 
know OCaml is right-to-left, but I still find all of that let binding code 
redundant, especially when the records get long. There is nothing "wrong" 
about it that I can see, except that some people don't like it in concept.
Interestingly, some people really did like it in concept and some of them 
were teachers who've witnessed beginners stumble over this very issue.

> It seems easy to me to add some marking in the type system to detect 
> expression with side effects ... 

I thought about this too. Something like Clean's uniqueness types? Maybe
in OCaml 4 :)

> then one could have a warning (or even
> an error :-) when some code depends on evaluation order and then, in
> this case only, force left to right evaluation order.

What does this mean? That you would have the programmer manually insert 
lets to force the order, or that the compiler does so automatically? 

> I am sure I would find some bugs in my programs with such a warning :-)

I think the random evaluation order that someone proposed as a test/debugging 
tool might be easier than a modification of the type system.

-- Brian

Re: Undefined evaluation order

[Christophe Raffalli]

It seems to me that a program making use of evaluation order in function
or constructor application is wrong !

It seems easy to me to add some marking in the type system to detect 
expression with side effects ... then one could have a warning (or even
an error :-) when some code depends on evaluation order and then, in
this case only, force left to right evaluation order.

I am sure I would find some bugs in my programs with such a warning :-)

What do think the OCaml's developpers about this ?

Note: the problem of List.map is different and the library should
specify an evaluation order (there could be even two versions of
List.map and List.iter)


-- 
Christophe Raffalli
Université de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tél: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI

Re: Undefined evaluation order

[David McClain]

Dave Berry writes:

> Are you saying that if (a * b) would result in a NaN
>then you always want (a * b * 0.0) to return a NaN, so that you are aware
> of the potential problem?

Yes! That is indeed the case. This is what the IEEE floating point spec
calls for. There are two kinds of Nan's -- signaling and non-signaling. The
signaling ones can potentially raise an exception, while the non-signaling
ones simply represent "Not-A-Number" values. One might use signaling Nan's
to initialize arrays, in some languages (i.e., Fortran) so that one could
catch the use of uninitialized variables...

I don't really distinguish the two in most of my work... Indeed, on the
Alpha architecture, you have to explicitly check for such errors by
inserting trap barrier instructions into the instruction stream. Hence, all
you can know is whether or not an exception has occured since the last time
you checked. The IEEE floating point spec allows for this kind of behavior
in the readily available FPU architectures as well (i.e., Pentium)

Most of my work involves signal and image processing on vast collections of
numbers, frequently in real-time environments. While the numerical analysts
might like to know about Nan signaling to help them write more sophisticated
(mathematical) function evaluators, nearly all of my math routines have to
be quick and not so exacting. In physics and measurement environments we
rarely have more than 3 significant digits in our data. Of course the work
of Prof. William Kahan, UC Berkeley, shows the need to carry many more
significant digits during intermediate calculations, but mathematical
refinement is not generally our concern. As I mentioned previously, if an
anomalous computation occurs in one or a few cases out of the billions that
we stream then we just drop it (them) on the floor and keep running...

- DM

Re: Undefined evaluation order

[Markus Mottl]

On Fri, 13 Oct 2000, Judicael Courant wrote:
> BTW, my 2 cents worth opinion about the evaluation order :
> when I program in a high-level language such as Caml, performance is not
> my primary concern. My primary concerns are correctness and development
> costs. Only the OCaml developpers should be concerned with performance.
> Therefore, I would clearly vote for a more natural, somewhat less
> efficient semantics (deterministic evaluation order) against a somewhat
> more efficient, less natural semantics.

I also agree on this. Of course, it all depends on the real tradeoff
associated with fixing evaluation order to left-to-right. If it were,
say, 10%, would anybody really care? If it were 100% - hm, possibly
already relevant for some cases. Are there any estimates so that we know
how much efficiency loss we are talking about?

My suggestion would be to make the "sane" left-to-right evaluation order
the default and to provide a flag "-unsafe-eval-order" or so to let the
compiler choose "at will": this (unsafe) warns the user about unintended
effects. Is this reasonable and sufficiently easy to implement?

Of course, writing functional programs that depend on evaluation order
diminishes their "functional flavour" and should always be avoided:
but working against intuition is always a bad idea, too.

Best regards,
Markus Mottl

-- 
Markus Mottl, mottl@miss.wu-wien.ac.at, http://miss.wu-wien.ac.at/~mottl

RE: Undefined evaluation order

[Dave Berry]

David,

Thanks for your reply.  Are you saying that if (a * b) would result in a NaN
then you always want (a * b * 0.0) to return a NaN, so that you are aware of
the potential problem? 

Dave.

> -----Original Message-----
> From: David McClain [mailto:dmcclain@azstarnet.com]
> Sent: Thursday, October 12, 2000 6:06 PM
> To: caml-list@inria.fr
> Subject: Re: Undefined evaluation order
> 
> 
> ... but the same would be true the other way too... (0.0 * a * b).  I am a
> numeric programmer and these things are unavoidable no matter how you
choose
> to order the evaluations.
> 
> If (a * b) raises a NaN then what would be the value of 0.0 times that?
The
> IEEE spec would say the result would have to continue to be a NaN.
> 
> I normally perform all arithmetic with exception processing supressed or
> deferred. The only time an exception is useful to me is if there is some
> remedial action that could be taken. I want my NaN's and INF's to appear
in
> my answers. In particular, if something should go awry at one point out of
> millions I don't want that one point to hose my entire calculation. (Note
> that I do not look kindly at the Fortran way of aborting an entire program
> for one bad point...) In signal and image processing, especially in a
> real-time environment, you just drop the bad points on the floor and
> continue running.
> 
> - DM

Re: Undefined evaluation order

[Judicael Courant]

Pierre Weis a écrit :
> I totally agree with all your comments, and would like to report the
> most difficult example I know to confuse students (and sometimes
> teachers!).
> 
> 

Let me tell you another one. Just ask your students to build a list of
characters from a file :

(*
  [char_list_of_channel : in_channel -> char list]
   build the list of characters contained in [c]
*)
let rec char_list_of_channel c =
  try input_char c :: char_list_of_channel c with
  | End_of_file -> []
;;

Then try to explain them they are wrong...

BTW, my 2 cents worth opinion about the evaluation order :
when I program in a high-level language such as Caml, performance is not
my primary concern. My primary concerns are correctness and development
costs. Only the OCaml developpers should be concerned with performance.
Therefore, I would clearly vote for a more natural, somewhat less
efficient semantics (deterministic evaluation order) against a somewhat
more efficient, less natural semantics.

In the development of Coq, I remember we were bitten at least once by
the problem of evaluation order. As far as I can remember, the problem
was in a function application (not a constructor) and the bug was not
easy to find. Although we perfectly knew that the evaluation order was
not specified and that it was right to left in practice, it is soooo
natural to assume it to be left to right when you read a program...

\begin{flamewar}
If you want performance, buy a better machine or code your whole program
in assembly.
\end{flamewar}

Judicaël.
-- 
Judicael.Courant@lri.fr, http://www.lri.fr/~jcourant/
(+33) (0)1 69 15 64 85
"Show me parts of your world, and I'll share you mine".
Tim, number #929, death row offender.
http://rozenn.picard.free.fr/timeng.html

Re: Undefined evaluation order

[David McClain]

... but the same would be true the other way too... (0.0 * a * b).  I am a
numeric programmer and these things are unavoidable no matter how you choose
to order the evaluations.

If (a * b) raises a NaN then what would be the value of 0.0 times that? The
IEEE spec would say the result would have to continue to be a NaN.

I normally perform all arithmetic with exception processing supressed or
deferred. The only time an exception is useful to me is if there is some
remedial action that could be taken. I want my NaN's and INF's to appear in
my answers. In particular, if something should go awry at one point out of
millions I don't want that one point to hose my entire calculation. (Note
that I do not look kindly at the Fortran way of aborting an entire program
for one bad point...) In signal and image processing, especially in a
real-time environment, you just drop the bad points on the floor and
continue running.

- DM

-----Original Message-----
From: Dave Berry <dave@kal.com>
To: Greg Morrisett <jgm@cs.cornell.edu>; caml-list@inria.fr
<caml-list@inria.fr>
Date: Thursday, October 12, 2000 4:53 AM
Subject: RE: Undefined evaluation order


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

RE: Undefined evaluation order

[Greg Morrisett]

> May I toss in a possible complication?   I'm thinking of 
> numeric code, and
> the possibilities of optimisation.  

I'm not saying that you can't get better performance
if you leave things unspecified.  Rather, a programmer
might like to know whether they'll get 0 or NaN (or
an exception) rather than "I'll get one of those things
real fast" :-)

Perhaps a practical solution would be to have a flag
controlling whether or not evaluation order is fixed.
Speed demons can turn the flag off, teachers can leave
the flag on.  

It wouldn't be that hard to implement, either -- leave
the compiler largely alone, but do an A-normalization
pass introducing explicit let-expressions to force
the evaluation order.  

-Greg

RE: Undefined evaluation order

[Dave Berry]

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

Re: Undefined evaluation order

[Pierre Weis]

[...]
> 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!
[...]
> -Greg

I totally agree with all your comments, and would like to report the
most difficult example I know to confuse students (and sometimes
teachers!).

Consider to explain the naive definition of map: 

let rec map f = function
  | [] -> []
  | x :: l -> f x :: map f l;;

Now, you map a trivial function as an example:

let add i = i + 1;;

map add [1; 2; 3];;
- : int list = [2; 3; 4]

Seems perfectly good and ok. Your students are happy.

Then, suppose you explain the use of printf to debug functions, by
a simple modification of their code:

let add i = Printf.printf "argument %d\n" i; i + 1;;

add 1;;
argument 1
- : int = 2

Easy. Your students are happy.

Now, unfortunately one of them is a brave soul and types in something
you don't ask:

map add [1; 2; 3];;
argument 3
argument 2
argument 1
- : int list = [2; 3; 4]

After 10 seconds, the brave soul is claiming ``urbi et orbi'': I've
found a bug in Caml!

Now, try to explain to your students (that are now at leat 12 standing
up and gazing at the brave soul's screen!) that the compiler is indeed
right!

Not easy. Your students are not happy.

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://cristal.inria.fr/~weis/

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

[Brian Rogoff]

On Tue, 10 Oct 2000, Thorsten Ohl wrote:
> Maybe I have ben brainwashed by too much Fortran, but depending on
> side effects in the evaluation of function arguments that change the
> result according to the evaluation order is not good style, IMHO.

I suppose I could claim to be brainwashed by too much Ada and C as well,
but somehow I am no longer enthralled by the lack of specified evaluation
order in those languages, even though I like both of them (not as much as 
OCaml of course :-).

BTW, in the particular case I mentioned, it wasn't function arguments but 
record/tuple expressions, as I was building an structure from a file read. 
It doesn't seem like bad style at all, in fact it seemed quite natural, 
only it doesn't work in OCaml, but would be fine SML.

> Explicit `let' bindings are clear and improve the likelihood that the
> author will still be able to understand his/her code a few year later
> significantly.

I don't believe that it improves understandability. Fix the evaluation
order to be left-to-right and the code is more understandable IMO. 
Explicitness doesn't necessarily imply greater readability/understandability.

Obviously, clarity is in the eye of the beholder, and probably depends on
your experiences as a programmer. I find the explicit let for sequencing 
redundant and distracting. Of course, if evaluation order were defined to 
be right-to-left I would use let bindings to force left-to-right because 
r-t-l is SO unnatural. 

> I agree that leaving this important chunk of the semantics unspecified
> is not nice, but closing the door on parallelism forever would be much
> worse, IMHO.

Arguments about optimizations in the bytecode compiler and parallelization 
are good arguments. The question is whether these outweigh the obvious
drawbacks. I don't think specifying evaluation order closes out
parallelism forever, since you can extend the language with explicit
parallel sequencing constructs if this were to ever become important. 

> (Only half-joking) There should be an option in the compiler
> randomizing evaluation order for debugging ...

That would be a good even if we had a specified order, so that you don't
inadvertently write code with such dependencies. 

-- Brian

Re: Undefined evaluation order

[Stefan Monnier]

>>>>> "Brian" == Brian Rogoff <bpr@best.com> writes:
> optimizations, but it is mentioned that this usually leads to clearer
> programs.  I'm sure the bytecode compiler argument is valid, but not the code
> clarity one, since it sounds similar to an argument that having uninitialized
> variables is clearer since it forces you to make values explicit, and I don't
> believe that.

I don't think it can be compared that way.  Using let does not introduce
grey-areas like uninitialized variables.  All it does is give a name to
an intermediate value.  This will usually improve the readability of the
code, unless the name is poorly chosen.


        Stefan

Re: Undefined evaluation order

[David McClain]

I second this opinion overall... I cut my teeth with respect to this when
writing C back about 20 years ago. Each individual statement in a program
carries with it the (implicit) assumption of simultaneous evaluation, unless
care is taken to indicate otherwise (e.g., Lisp (LET ...) vs (LET* ...) ).
Hence depending on a particular order of evaluation is seemingly dangerous,
not to mention confusing when switching between many different languages as
I must do... (Lately, with a mix of OCaml, SmallTalk, Dylan, and Lisp I have
even been getting confused about operator precedence!).

I think it is probably wrong for too many assumptions to be made in the
design and use of a language. Lisp is stellar in this regard, simply because
only one assumption is made - first operand is a function all the rest are
args. When one must switch between languages, it is horribly confusing to
have to get back into the mindset of the crowd that fancies their particular
language as the one and only...

Just my 2c...

- DM

-----Original Message-----
From: Thorsten Ohl <ohl@hep.tu-darmstadt.de>
To: caml-list@inria.fr <caml-list@inria.fr>
Date: Tuesday, October 10, 2000 10:08 AM
Subject: Re: Undefined evaluation order


>Brian Rogoff <bpr@best.com> writes:
>
>> For OCaml it appears that the perspective adopted is that the
>> programmer must make the temporal dependencies explicit. [...] it is
>> mentioned that this usually leads to clearer programs.  I'm sure the
>> bytecode compiler argument is valid, but not the code clarity one
>
>Maybe I have ben brainwashed by too much Fortran, but depending on
>side effects in the evaluation of function arguments that change the
>result according to the evaluation order is not good style, IMHO.
>Explicit `let' bindings are clear and improve the likelihood that the
>author will still be able to understand his/her code a few year later
>significantly.
>
>I agree that leaving this important chunk of the semantics unspecified
>is not nice, but closing the door on parallelism forever would be much
>worse, IMHO.
>
>(Only half-joking) There should be an option in the compiler
>randomizing evaluation order for debugging ...
>--
>Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
>http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]
>

Re: Undefined evaluation order

[John R Harrison]

In the old ML compiler used in Cambridge LCF and HOL88 (which I guess was
a kind of ur-CAML), the order of evaluation was genuinely changeable, e.g:

   #let f x y = (x,y);;
   f = - : (* -> ** -> (* # **))

   #f (print_int 1;100) (print_int 2;200);;
   21(100, 200) : (int # int)

   #(I f) (print_int 1;100) (print_int 2;200);;
   12(100, 200) : (int # int)

We just ended up saying in HOL's DESCRIPTION manual:

   "Due to optimizations in the ML compiler, the order of evaluation
    may vary."

Gerard Huet might have been responsible for the optimizations that led to
this behaviour, so perhaps he knows more...

Cheers,

John.

Re: Undefined evaluation order

[Thorsten Ohl]

Brian Rogoff <bpr@best.com> writes:

> For OCaml it appears that the perspective adopted is that the
> programmer must make the temporal dependencies explicit. [...] it is
> mentioned that this usually leads to clearer programs.  I'm sure the
> bytecode compiler argument is valid, but not the code clarity one

Maybe I have ben brainwashed by too much Fortran, but depending on
side effects in the evaluation of function arguments that change the
result according to the evaluation order is not good style, IMHO.
Explicit `let' bindings are clear and improve the likelihood that the
author will still be able to understand his/her code a few year later
significantly.

I agree that leaving this important chunk of the semantics unspecified
is not nice, but closing the door on parallelism forever would be much
worse, IMHO.

(Only half-joking) There should be an option in the compiler
randomizing evaluation order for debugging ...
-- 
Thorsten Ohl, Physics Department, TU Darmstadt -- ohl@hep.tu-darmstadt.de
http://heplix.ikp.physik.tu-darmstadt.de/~ohl/ [<=== PGP public key here]

RE: Undefined evaluation order

[Greg Morrisett]

> In retrospect, perhaps we should have considered introducing "let"
> bindings automatically to preserve left-to-right semantics within the
> push-enter model (like Moscow ML does, I think), although this entails
> a performance hit for the bytecode interpreter.

Let me put in a vote for left-to-right ordering.  I've also
been bitten by the evaluation order (with almost exactly the
same kind of code -- reading a record's values from some file).
But more importantly, the primary reasons I chose SML over 
O'Caml for my class this semester is that the evaluation 
model of SML is more uniform.  Left-to-right in O'Caml might
well change my mind.  

On this note, I find the discussion of syntax very interesting.
Teaching either variant of ML to a group of students raised
on Visual Basic, Java, and Javascript is not easy, and today's
ML implementations are not very student-friendly when it comes
to either parse- or type-error messages...

-Greg

Re: Undefined evaluation order

[Xavier Leroy]

>     It is well known that OCaml has undefined evaluation orders and that
> it uses right-to-left ordering. What is the rationale for that decision? 

The main reason was to accommodate the "push-enter" model used by the
Caml Light and Objective Caml virtual machines.  In this model,
arguments to curried functions are pushed on a stack, first argument
last, and then the code of the closure is entered.  (As opposed to the
"eval-apply" model, where the first argument is evaluated, followed by
one function application, then the second argument is evaluated,
followed by a second application, etc.)

The "push-enter" model allows a lot of nice optimizations for curried
functions, but entails right-to-left evaluation of function arguments.

Rather than "standardize" a right-to-left evaluation order, we decided
to leave the evaluation order officially unspecified.  At that time,
it was also believed that this could leave more flexibility for other
optimizations, e.g. the reordering of sub-expressions for minimizing
register use described in the Dragon book, and perhaps also for
parallel evaluation.

In retrospect, we overestimated the potential gains of such
optimizations, and actually never implemented any of them (nor
parallel evaluation), sticking to the same evaluation order in the
native-code compiler than in the bytecode interpreter.

>     Besides being surprising for lots of people, it is actually a little
> ugly to have to write explicit let bindings to force the order and when
> reading files which consist of long records;

Yes, I agree.  Even with good programming discipline, I get bitten
about once a year by the unexpected evaluation order.

In retrospect, perhaps we should have considered introducing "let"
bindings automatically to preserve left-to-right semantics within the
push-enter model (like Moscow ML does, I think), although this entails
a performance hit for the bytecode interpreter.

- Xavier Leroy

Re: Undefined evaluation order

[Brian Rogoff]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: TEXT/PLAIN; charset=X-UNKNOWN, Size: 1573 bytes --]

On 8 Oct 2000, David [iso-8859-1] Mentré wrote:
> Brian Rogoff <bpr@best.com> writes:
> 
> >     It is well known that OCaml has undefined evaluation orders and that
> > it uses right-to-left ordering. What is the rationale for that decision? 
> 
> It is linked to the way the bytecode is designed to optimize functions
> evaluation. You'll find a detailed (and more accurate) explanation in
> the following paper :
> 
> RT-0117 The ZINC experiment : an economical implementation of the ML
> language - Xavier Leroy
>  http://www.inria.fr/RRRT/RT-0117.html

Thanks David, that's exactly the kind of explanation I was looking for. 

Interestingly, I had a discussion with my manager about this and we had
slightly different views. I argued that evaluation order should be
specified and that it should be left-to-right, which I hope everyone
agrees is the most natural order. He argued that evaluation order should 
be defined so that you can analyze programs, but that the order was
irrelevant; he'd be happy with right-to-left if it were specified. For
OCaml it appears that the perspective adopted is that the programmer must
make the temporal dependencies explicit. The reason is for (bytecode) compiler 
optimizations, but it is mentioned that this usually leads to clearer programs. 
I'm sure the bytecode compiler argument is valid, but not the code clarity one, 
since it sounds similar to an argument that having uninitialized variables is 
clearer since it forces you to make values explicit, and I don't believe that.

-- Brian

Re: Undefined evaluation order

[David Mentré]

Brian Rogoff <bpr@best.com> writes:

>     It is well known that OCaml has undefined evaluation orders and that
> it uses right-to-left ordering. What is the rationale for that decision? 

It is linked to the way the bytecode is designed to optimize functions
evaluation. You'll find a detailed (and more accurate) explanation in
the following paper :

RT-0117 The ZINC experiment : an economical implementation of the ML
language - Xavier Leroy
 http://www.inria.fr/RRRT/RT-0117.html


d.
-- 
 David.Mentre@irisa.fr -- http://www.irisa.fr/prive/dmentre/
 Opinions expressed here are only mine.

Re: Undefined evaluation order

[Ken Wakita]

Thanks for your correction.  I looked up in versions of "n'th revised
reports on algorithmic language Scheme" and found the following at a
section "Procedure calls":

  Note: Although the order of evaluation is otherwise unspecified, the
        effect of any concurrent evaluation of the operator and
        operand expressions is constrained to be consistent with some
        sequential order of evaluation. The order of evaluation may be
        chosen differently for each procedure call.

        (http://swissnet.ai.mit.edu/~jaffer/r5rs_6.html#SEC28)

This note first appeared in R4RS.  However, in R3RS it is rather
unclear in that "the same evaluation rules" may allow nondeterministic
evaluations:

  Note: In contrast to other dialects of Lisp, the order of evaluation
        is unspecified, and the operator expression and the operand
        expressions are always evaluated with the same evaluation
        rules.

        (http://swissnet.ai.mit.edu/~jaffer/r3rs_6.html#SEC25)

Ken Wakita

Re: Undefined evaluation order

[Pierpaolo BERNARDI]

On Fri, 6 Oct 2000, Ken Wakita wrote:

> Scheme also has its evaluation orders of function parameters
> undefined.  I remember one of the reasons for this decision is to
> leave possibility for parallel evaluation of the arguments.

This is not correct.  In scheme, parallel evaluation of the arguments is
explicitly disallowed (unless the compiler can prove that evaluating them 
in parallel does not have any observable effect, of course).

The real reason of the unspecified order in Scheme, is that when the first 
reports on scheme were being drafted, there already were implementations
which evaluated arguments in different order.  And this has never been
fixed afterwards.

(People interested in the history of Scheme can check the archives of the
scheme authors mailing list at MIT).

Gxis,
  Pierpaolo Bernardi

Re: Undefined evaluation order

[Ken Wakita]

Scheme also has its evaluation orders of function parameters
undefined.  I remember one of the reasons for this decision is to
leave possibility for parallel evaluation of the arguments.

Ken Wakita
Tokyo Institute of Technology

Undefined evaluation order

[Brian Rogoff]

Hi,
    It is well known that OCaml has undefined evaluation orders and that
it uses right-to-left ordering. What is the rationale for that decision? 
I remember some discussion of this but I couldn't find it in the Caml list
archives. 

    Besides being surprising for lots of people, it is actually a little
ugly to have to write explicit let bindings to force the order and when
reading files which consist of long records; for instance I much prefer 

type date =
  { year : int
  ; month : int
  ; day : int
  ; hour : int
  ; minute : int
  ; second : int 
  }

let input_date igds =
  { year = input_word igds
  ; month = input_word igds
  ; day = input_word igds
  ; hour = input_word igds
  ; minute = input_word igds
  ; second = input_word igds
  }

to 

let input_date igds =
  let year = input_word igds in
  let month = input_word igds in
  let day = input_word igds in
  let hour = input_word igds in
  let minute = input_word igds in
  let second = input_word igds in
  {  year = year
   ; month = month
   ; day = day
   ; hour = hour
   ; minute = minute
   ; second = second
   }

or even with right-to-left where the order is exactly the opposite of the 
record definition (and of what most readers expect). 

-- Brian