RE: Undefined evaluation order

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

[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: define it for constructors ?

[Jacques Garrigue]

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

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

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

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


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

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

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

Regards,

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

Re: Undefined evaluation order: define it for constructors ?

[Hugo Herbelin]

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

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

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

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

                                                  Hugo

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

[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

[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

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

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

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