evaluation order

evaluation order

[Christophe Raffalli]

Hello,

In OCaml-3.11.1 (I did not try other version),
the following code print 0 when compiled in bytecode and 1 in nativecode
for obvious reason of different evaluation order in the pair ...


let ptr = ref 0
let fn b =
  if b then incr ptr else decr ptr
let c = fn true, !ptr
let _ = print_int (snd c); print_newline ()

Is any difference between ocamlc and ocamlopt a bug ?

Cheers,
Christophe

Re: evaluation order

[Rémi Vanicat]

Christophe Raffalli <raffalli@univ-savoie.fr> writes:

> Hello,
>
> In OCaml-3.11.1 (I did not try other version),
> the following code print 0 when compiled in bytecode and 1 in nativecode
> for obvious reason of different evaluation order in the pair ...
>
>
> let ptr = ref 0
> let fn b =
>  if b then incr ptr else decr ptr
> let c = fn true, !ptr
> let _ = print_int (snd c); print_newline ()
>
> Is any difference between ocamlc and ocamlopt a bug ?

Both must follow the specification, but order of evaluation is left
unspecified in ocaml, so this difference is not a bug. The bug is in
your code that depend of an unspecified feature of one of the compiler.
-- 
Rémi Vanicat

Re: [Caml-list] evaluation order

[Jon Harrop]

On Sunday 14 June 2009 17:36:39 Christophe Raffalli wrote:
> Hello,
>
> In OCaml-3.11.1 (I did not try other version),
> the following code print 0 when compiled in bytecode and 1 in nativecode
> for obvious reason of different evaluation order in the pair ...
>
>
> let ptr = ref 0
> let fn b =
>   if b then incr ptr else decr ptr
> let c = fn true, !ptr
> let _ = print_int (snd c); print_newline ()
>
> Is any difference between ocamlc and ocamlopt a bug ?

Not at all, no. They are expected to have different behaviour with respect to 
floating point arithmetic. In this case, they have chosen to evaluate 
subexpressions in a different order, which is fine because the order of 
evaluation is officially undefined.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

Re: [Caml-list] evaluation order

[Christophe Raffalli]

Jon Harrop a écrit :
> On Sunday 14 June 2009 17:36:39 Christophe Raffalli wrote:
>   
>> Hello,
>>
>> In OCaml-3.11.1 (I did not try other version),
>> the following code print 0 when compiled in bytecode and 1 in nativecode
>> for obvious reason of different evaluation order in the pair ...
>>
>>
>> let ptr = ref 0
>> let fn b =
>>   if b then incr ptr else decr ptr
>> let c = fn true, !ptr
>> let _ = print_int (snd c); print_newline ()
>>
>> Is any difference between ocamlc and ocamlopt a bug ?
>>     
>
> Not at all, no. They are expected to have different behaviour with respect to 
> floating point arithmetic. In this case, they have chosen to evaluate 
> subexpressions in a different order, which is fine because the order of 
> evaluation is officially undefined.
>
>   
Despite the fact that it should not be written in OCaml because the 
result rely on the unspecified evaluation order, my example still seems 
to contradict chapter 11 of OCaml's documentation:

"Compatibility with the bytecode compiler is extremely high: the same 
source code should run identically when compiled with ocamlc and ocamlopt."

This kind of bug could also be a nightmare to debug ... because the 
debugger is only available for bytecode ...

Cheers,
Christophe

RE: [Caml-list] Evaluation Order

[Manuel Fahndrich]

I feel your pain, having run into this problem before. What we need is a
way for the compiler to alert the programmer in contexts where
evaluation order is unspecified, but where the programmer relies on some
order.

The only way I can imagine doing this is if the language contains a
notion of side effecting evaluation. If such a concept is present, then
in any context where evaluation order is undefined, all involved
expressions must be side effect free, which guarantees that the code
will evaluate in the same way no matter what order the actual
implementation chooses.

Of course, the side effect annotations can become burdensome. Also, one
pretty quickly wants to distinguish certain side effects from others.
Evaluation order independence can be guaranteed if the side effects of
two expressions don't interfere. 

In a language with regions (such as Tofte and Talpin) we can obtain some
of this directly:

If we have e1 + e2, and the effects of e1 are E1 and effects of e2 are
E2, then we merely have to check that the intersection of E1 and E2 is
empty. That sounds simple, but it is not, because of possible region
aliasing.

Yet another way to look at it is in terms of heap splitting. If in order
to evaluate e1 + e2, we can split the heap M into disjoint parts M1 + M2
and evaluate e1 under M1 and e2 under M2, then we know they can't
interfere. This is the notion studied in Reynold's syntactic control of
interference, and also in the logic of bunched implications, and in the
capability calculus.

(shameless plug)
In VAULT (http://research.microsoft.com/vault) we have a notion of
non-aliasing for regions, thus there are situations where we can decide
the above non-interference.

-Maf


-----Original Message-----
From: David McClain [mailto:dmcclain1@mindspring.com] 
Sent: Saturday, June 09, 2001 9:00 AM
To: caml-list@inria.fr
Subject: [Caml-list] Evaluation Order

I thought I would share an experience with all of you to solicit your
*constructive* comments.

I just rewrote my block convolution routine in pure OCaml native
compiled
along with the inner loop in C/C++. This is necessarily a side effecting
program since it must alter the outside world of data. I had a statement
in
OCaml that went something like this:

    let ans = fnx () + fny ()

where both fnx and fny are side effecting closures.

I consider myself a very experienced OCaml programmer, and I am so
accustomed to getting pristine results from OCaml, that I spent many
hours
going through my C/C++ code looking for the error. I was getting
anomalous
output values at the front of my convolution records, but everything
else
worked just fine. I was convinced something was awry with my C code ---
whenever a problem occurs that's almost always where it is -- never in
the
OCaml code.

I had forgotten about the evaluation ordering in OCaml being from right
to
left. I am aware of the reasons for this, having studied the Zinc paper
some
time ago. But the tendency to read implicit temporal ordering of
operations
as left to right is a very strong psychological factor here. The
problem,
once tracked down, was easily fixed by restating the routine as

    let ans = fnx() in
        ans + fny()

to force evaluation of fnx before fny.

I suppose if Hebrew or Arabic were my native tongue then the opposite
expectation would be true and I would have naturally written

    let ans = fny() + fnx()

and I would be no wiser about evaluation order here, since everything
would
have worked properly.

I don't have a good answer to this problem, but I did want to point out
the
one and only place where OCaml forced me to spend hours debugging a
problem
caused solely by a clash of psychology and OCaml semantics. All of my
other
debugging activities have, and will probably continue, to focus on C/C++
as
the likely culprit.

This problem will be permanently etched into my mind from now on, and I
will
be sure to remember to avoid order dependent syntax.

The same problem occurs regularly in C, and I have become quite
accustomed
and adept at avoiding these ordering problems. Good examples are to be
found
among C preprocessor macrology. I just now have to remember that the
same is
true of OCaml.

I had been lulled into a belief that OCaml was nearly perfect, while
C/C++
is definitely not. The problem is not one of OCaml, but rather a clash
between normal psychological expectations and the programming language
at
hand.

Since embedded realtime systems are chock full of temporally ordered
operations this must be one of the severe weak points in software
control
systems. There must be a better way to guide human thinking here. Just
as
OCaml has provided a system to look over our shoulders and force us to
write
the correct things, there must be a way of doing something similar for
temporally dependent clauses.

Any thoughts? (other than that I was boneheaded here!)

- DM


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

Frederick Smith wrote:
 
> I do not believe a simple effect annotation on function types, as suggested, would
> suffice.  Although we may like to think of OCaml programs as effect free, they are
> replete with effects: 1) I/O, 2) exceptions, and 3) non-termination.  

	Arghh. You're quite right. Even if we forget about
non-termination, the dynamic nature of exception handling
makes it very hard to make static typing rules which account
for them.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Frederick Smith]

Someone asked earlier on this thread if anyone had ever suggested adding effects to
types.  I believe this idea was introduced by Lucassen and Gifford in POPL '88.
Since then there have been numerous papers, including some extending ML's type
inference to support effects (for example Andrew Wright's paper of 1992). Check out
http://citeseer.nj.nec.com/contextsummary/83989/0 for a list of over 50 papers
citing that first POPL paper.

I do not believe a simple effect annotation on function types, as suggested, would
suffice.  Although we may like to think of OCaml programs as effect free, they are
replete with effects: 1) I/O, 2) exceptions, and 3) non-termination.  It is
theoretically and practically infeasible to check that programs terminate.  Since
non-termination is usually not the source of programmer error, except perhaps when
writing multi-threaded applications, we may choose not to consider non-termination
a side-effect.  This pragmatic choice means that there will be programs whose
behavior depends on the order of evaluation.  If that is unacceptable, than it
would be best to fix the order of evaluation and let the compiler use the effect
analysis of its choice without burdening the user with additional annotations.
Have there been any studies showing the practical effect of fixing evaluation
order?  How bad is the performance penalty? How much can compiler analyses do to
minimize the impact?

If we choose to ignore non-termination but keep exceptions as effects then we face
the same problem as Java's throw clauses.  These throw annotations indicate which
exceptions a function may throw.  For large applications, it soon becomes the case
that nearly every function throws some kind of exception directly or indirectly.
Often the programmers know that those exceptions (NullPointer for example) will
never occur, but the type system cannot verify this fact.  Consequently, every
function contains a throws annotation making the annotations useless.  Similarly,
many OCaml functions especially in a deeply nested large application are likely to
raise exceptions.  Note that almost every one of the 2-list functions in the list
library raise exceptions.  Are you willing to wrap every call to List.for_all2 with
a handler?  How will you deal with the error?  Most likely by raising an
"impossible" exception and aborting the program :-).  Therefore it seems to me that
exceptions cannot be counted as side-effects either, increasing yet again the set
of programs whose behavior depends on order of evaluation.

If the real goal of the effect annotation is to prevent I/O from happening in an
unexpected order than a simple solution would be to implement the I/O libraries as
a monad. No extension of the type system or compiler would be necessary, although
we might want some syntactic sugar for convenience.  The connection between monads
and effects has been explored by Wadler.  Maybe someone with Haskell experience
could comment on how well monads work in practice?

In our project, order of evaluation surprised us in the pretty printer and later in
the assembler and disassembler.  It is dismaying to see these kinds of problems
arise in as friendly a language as OCaml.  I wish a solution were obvious.

-Fred


John Max Skaller wrote:

> Dave Mason wrote:
>
> > I think the answer is that the ``effect''ness isn't simply captured in
> > the type.  So the current type-inference engine would not be able to
> > do it.  It would require a bit of ad-hocery in the compiler.  That
> > doesn't mean that it's unsound, just that the existing compiler
> > mechanisms couldn't do it.
>
>         I think you probably _have_ to capture it in the type.
> Consider a new type
>
>         'a => 'b
>
> where '=>' means 'function with side effects'. Now consider
> the following two term constructors:
>
>         Apply(fn1,arg1)
>         Init(name,fn2,arg2)
>
> The type-checking rules are then clear:
>
>         fn1: 'a->'b, arg1:'a, Apply(fn1,arg1):'b
>         fn2: 'a=>'b, arg2:'a, name: 'b
>
> and
>
>         'a->'b is a subtype of 'a=>'b'
>
> In Felix it would be easy to verify correct usage,
> but I'm not sure it is possible to verify correct
> specification. In Ocaml, it may be harder, since
> one can use a function before declaration in a 'let rec',
> and it may be too late when spotting the type annotation
> to report a wrong usage.
>
> [OTOH, if the Ocaml compiler scanned 'let recs' for type
> annotations before examining bodies, it might improve
> error reporting in other circumstances??]
>
> --
> John (Max) Skaller, mailto:skaller@maxtal.com.au
> 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
> checkout Vyper http://Vyper.sourceforge.net
> download Interscript http://Interscript.sourceforge.net
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

Dave Mason wrote:

> I think the answer is that the ``effect''ness isn't simply captured in
> the type.  So the current type-inference engine would not be able to
> do it.  It would require a bit of ad-hocery in the compiler.  That
> doesn't mean that it's unsound, just that the existing compiler
> mechanisms couldn't do it.

	I think you probably _have_ to capture it in the type.
Consider a new type

	'a => 'b

where '=>' means 'function with side effects'. Now consider
the following two term constructors:

	Apply(fn1,arg1)
	Init(name,fn2,arg2)

The type-checking rules are then clear:

	fn1: 'a->'b, arg1:'a, Apply(fn1,arg1):'b
	fn2: 'a=>'b, arg2:'a, name: 'b

and

	'a->'b is a subtype of 'a=>'b'

In Felix it would be easy to verify correct usage,
but I'm not sure it is possible to verify correct
specification. In Ocaml, it may be harder, since
one can use a function before declaration in a 'let rec',
and it may be too late when spotting the type annotation
to report a wrong usage.

[OTOH, if the Ocaml compiler scanned 'let recs' for type
annotations before examining bodies, it might improve
error reporting in other circumstances??]



-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

Dave Mason wrote:

> > In principle, the Felix type checker would prevent this:
> > side-effects are not permitted in functions.
> 
> >       The reason for relaxing the rules is that it is very ugly and
> > insecure to write things like:
> 
> >       val x : int; // uninitialised variable!
> >       fetch(&x,&state_object);
> 
> > instead of
> 
> >       val x : int = fetch(&state_object);
> 
> > I can't think of good way around this though.
 
> Functions *should* be able to do side-effects (unless you have a pure
> functional language), 

	My desire is to have a purely functional subsystem.
So I would 'say' that functions cannot have side effects.
However, Felix has procedures too, which cannot return
values. There is a reason for this.

	Functions execute 'on the stack'. They may not
read input or have any side effects.

	Procedures work by continuation passing.
When you call a procedure, it _returns_ control,
passing a continuation, which is immediately
resumed by the driver. When a request to read input
is encountered, control is also returned.
The driver then stores a message and resumes
the continuation. In other words, the system
is event driven transparently.

	Now see below:

> I think my proposal from the weekend is better: functions can have
> side effects, but you can't use the results in a way that will bite
> you (due to order of evaluation).

	That is what I am looking for. Basically,
I want some sugar, so that users can write:

	val x = f();

but the implementation is actually equivalent to:

	val x;
	f(&x); 

Note that this is implemented like this:

	switch(pc) {
	...
	...
	pc = 2;
	return new f(&x);
	case 2:
	...

So in Felix, it is not a matter of style that procedures
returning values cannot be used 'inside' expressions:
it would greatly complicate the compiler, because it
would have to linearise expression trees 'down to'
any procedure call. Currently, expressions are 
simply replaced by their C++ equivalents, and the C++
compiler can then have a go at optimising them.

BTW: I'm currently putting Felix up on sourceforge:

	http://felix.sf.net

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

Brian Rogoff wrote:

> > Perhaps binding record fields left to right makes sense,
> 
> And tuples, and (::), and ...
> 
> Why not make the default correspond to everyone's intuition?

	It may clobber performance, and, it isn't
all that obvious anyhow.

	Here is the 'classic' example from C:

	x[i++] = y[i++]

[If you think you know the answer .. just consider that
i might alias x :-]

If the order of evaluation is strictly specified,
a lot of results must be written to memory
prematurely. It is one reason why C is slower than Fortran.
I suspect it is processor dependent.

	C specifies sequence points: places where
write operations must be completed before continuing.
If you do a read before that, the result is indeterminate.
The rules try to make efficient 'in register' operations
possible and allow enough flexibility to reorder
instructions to suit a processors caching and pipelining
model --  while still making common idioms work.

	I'm no expert. I simply advise caution here.
_Functional_ expressions can be optimised in useful
ways at very low processor dependent levels.
Lets not stop the Ocaml team trying to beat both
C _and_ Fortran!

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Pierre Weis]

> Tore Lund wrote:
> 
> >   # let _ =
> >       print_string "before";
> >       print_string "MIDDLE";
> >       print_string "after";;
> >   beforeMIDDLEafter- : unit = ()
> > 
> > but not in this one:
> > 
> >   # let _ =
> >       print_string "before";
> >       Format.print_string "MIDDLE";
> >       print_string "after";;
> >   beforeafterMIDDLE- : unit = ()
> > 
> > What's going on here?  
> 
> 	Buffering I guess. print_string buffers using stdio buffers.
> Format.* has its own buffer, which is flushed into the
> stdout buffer too late.
> 
> 
> -- 
> John (Max) Skaller, mailto:skaller@maxtal.com.au
> 10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
> checkout Vyper http://Vyper.sourceforge.net
> download Interscript http://Interscript.sourceforge.net
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Thank you for pointing out this delicate point.

I added your example and some basic explanation to the FAQ: 

----------------------------------------------------------------------
<H2 ALIGN=LEFT><A NAME="impression_format"> Why some printing material
is mixed up and does not appear in the right order ?</A></H2>

<P>If you use printing functions of the <CODE>format</CODE> module,
you might not mix printing commands from <CODE>format</CODE> with
printing commands from the basic I/O system. In effect, the material
printed by functions from the <CODE>format</CODE> module is delayed
(stored into the pretty-printing queue) in order to find out the
proper line breaking to perform with the material at hand. By contrast
low level output is performed with no more buffering than usual I/O
buffering. So that you can observe the following output differences between
pure low level output:

<PRE>
# print_string "before";
  print_string "MIDDLE";
  print_string "after";;
beforeMIDDLEafter- : unit = ()
</PRE> 

and mixed calls to low and high level printing:

<PRE>
# print_string "before";
  Format.print_string "MIDDLE";
  print_string "after";;
beforeafterMIDDLE- : unit = ()
</PRE>

<P>To avoid this kind of problems you should not mix printing orders
from <CODE>format</CODE> and basic printing commands; that's the reason why
when using functions from the <CODE>format</CODE> module, it is
considered good programming habit to open <CODE>format</CODE> globally
in order to completely mask low level printing functions by the high
level printing functions provided by <CODE>format</CODE>.

<P>N.B: <CODE>format</CODE> printings are automatically flushed after
each evaluation in the interective system. Explicit flushes are
also performed by calling the <CODE>print_newline</CODE> function that
emits a line break and empties the pretty printer queue.
----------------------------------------------------------------------

All constructive criticisms are warmly welcome.

Best regards,

Pierre Weis

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


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Dave Mason]

>>>>> On Sat, 9 Jun 2001 19:25:01 -0700, "David McClain" <dmcclain1@mindspring.com> said:

> I had just thought of a similar solution myself, but I wouldn't be
> so strict as to disallow any use in an expression. Rather, as long
> as only one such function call exists in any one expression it would
> be okay. That would allow things like

> let ans = prev_ans + process_tail() in ....

Yes.

> It does sound like an easy solution, so knowing myself as I do, I am
> wondering what I don't understand about the details... If it were so
> easy, then why hasn't it been done yet?

I think the answer is that the ``effect''ness isn't simply captured in
the type.  So the current type-inference engine would not be able to
do it.  It would require a bit of ad-hocery in the compiler.  That
doesn't mean that it's unsound, just that the existing compiler
mechanisms couldn't do it.

../Dave
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Dave Mason]

>>>>> On Mon, 11 Jun 2001 00:06:29 +1000, John Max Skaller <skaller@ozemail.com.au> said:

> In principle, the Felix type checker would prevent this:
> side-effects are not permitted in functions.

> 	The reason for relaxing the rules is that it is very ugly and
> insecure to write things like:

> 	val x : int; // uninitialised variable!
>	fetch(&x,&state_object);

> instead of

> 	val x : int = fetch(&state_object);

> I can't think of good way around this though.

Functions *should* be able to do side-effects (unless you have a pure
functional language), or at least, there need to be chunks of code
that can have side-effects and also return values.  Otherwise you
can't write atomic code in a multi-threaded environment - i.e. pull
the next thing off a queue (unless you pass in refs as you suggest,
which I really dislike).

I think my proposal from the weekend is better: functions can have
side effects, but you can't use the results in a way that will bite
you (due to order of evaluation).

> You can also cheat, by wrapping C functions as Felix functions:
> there's no way to check if the C function has side effects or not.

You can always cheat by stepping outside the semantics.  Write in
assembler, edit the executable with Emacs, etc.  The last system I am
aware of where you couldn't cheat was the Burroughs operating system
from the 1970's, where only the system linker could produce executable
programs.  But even there, I'm sure there was a cheat available to the
system architects.

../Dave
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Dave Mason]

>>>>> On Sun, 10 Jun 2001 19:59:11 +0200 (MET DST), Damien Doligez <Damien.Doligez@inria.fr> said:

> The original argument about optimizations is still as valid as it
> ever was.  The real problem is that there is a conflict between
> left-to-right evaluation order and currying.  Consider the
> expression:

>    f e1 e2 e3

> It only looks like the application of f to 3 arguments.  In reality,
> it is a nested expression with three function applications.  If you
> want to evaluate it in left-to-right order, you have to do the
> following:
>[...]

> If you want to optimize this to get something as efficient as O'Caml
> currently is, you have to know that f doesn't do any side-effect
> before receiving all its arguments, which is generally impossible.
> With right-to-left, the compiler doesn't have to know anything about
> f.

This is also addressable with my suggestion (which I posted last
night, but hasn't made it to the mailing list yet) of annotating
results of functions that cause a side-effect.  So, in your example,
instead of the existing:
	# let x = ref 0;;
	val x : int ref = {contents=0}
	# let f w y = incr x;let x' = !x in function z -> w+x'+y+z;;
	val f : int -> int -> int -> int = <fun>
you would get instead:
	val f : int -> int -> (int -> int effect) effect = <fun>
now when you apply it:
	f e1 e2 e3
you get an error if e3 is also an effect value, because the order of
evaluation between the evaluation of (f e1 e2) and (e3) might cause a
problem.  So you would be forced to rewrite it as:
	let f' = f e1 e2 in f' e3
or
	let e3' = e3 in f e1 e2 e3'
whichever reflected the order of evaluation that you want.  Note that
you would not get an error if e2 was an effect value because it must
be evaluated (because of ml's strict semantics) before f is applied to
it, and it doesn't matter whether e2 is evaluated before or after (f
e1) is.  Similarly, it does not matter if e1 is an effect value
because it has to be evaluated before f can be applied to it.  (Note
that if f was an expression that itself was an effect, this wouldn't
be true.)  If e1 and e2 were *both* effect values, then there would be
a conflict between them and you would get a compilation error.

(Note that in my other posting I suggested a refinement of this that
would get finer granularity on the conflicts, but the principle is the
same.)  This is somewhat related to monads, but with ocaml's strict
semantics it need not be as intrusive as monads.

../Dave
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Damien Doligez]

>From: Brian Rogoff <bpr@best.com>

>No, this is a language problem. Lots of people who teach OCaml have mentioned 
>that this is an issue. If the clash with expectation is so great then that
>You should always be careful about sequencing in imperative style programming, 
>but IMO this is one of those few things that SML does right that OCaml does 
>not. As you say, there is a very strong expectation that events occur in
>the order that we read them. The original arguments about optimizations
>and parallelism don't seem to have borne fruit, so it would be good to fix
>this.

The original argument about optimizations is still as valid as it ever
was.  The real problem is that there is a conflict between
left-to-right evaluation order and currying.  Consider the expression:

   f e1 e2 e3

It only looks like the application of f to 3 arguments.  In reality,
it is a nested expression with three function applications.  If you
want to evaluate it in left-to-right order, you have to do the
following:

1. evaluate f
2. evaluate e1
3. evaluate f (e1)   (call the result f1)
4. evaluate e2
5. evaluate f1 (e2)  (call the result f2)
6. evaluate e3
7. evaluate f2 (e3)

If you want to optimize this to get something as efficient as O'Caml
currently is, you have to know that f doesn't do any side-effect
before receiving all its arguments, which is generally impossible.
With right-to-left, the compiler doesn't have to know anything about f.

For years I thought that the only solution to this problem would be to
move away from currying by changing the preferred programming style to
passing tuples or records (as SML does).  But people at INRIA are
overly fond of currying for some reason.

Now I think there's another solution.  Let's just have different
semantics for  (f e1 e2 e3)  and  ((f e1) e2 e3) :

f e1 e2 e3 should evaluate f, then e1, then e2, then e3, then do a
ternary application.

(f e1) e2 e3 should evaluate f, then e1, then do a unary application,
then evaluate e2, then e3, then do a binary application.


I think this solution should work, and retain all the efficiency of
O'Caml.  The question is, how much does it interfere with labels and
optional arguments ?

-- Damien
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Dave Mason]

>>>>> On Sun, 10 Jun 2001 09:47:25 -0700 (PDT), Brian Rogoff <bpr@best.com> said:

> Well, OCaml isn't referentially transparent, and it is strict to
> begin with. I agree that it would be awful if my argument was only
> about the order of evaluation of (+).

No it isn't.  But it would be nice if code which wasn't was detectable
as such and otherwise you could reason as if it were.  I have a
longish email on its way to the list that proposes marking the results
of any functions that cause side-effects as such, and not allowing
them to be used in compound expressions where they would be
order-dependent.

> Why not make the default correspond to everyone's intuition?

Because that isn't everyone's intuition!  Better to not specify the
order, but prevent expressions where order dependency could create a
problem.  That also leaves the compiler maximum flexibility in
ordering evaluation (while this may not be exploited by the current
compilers, it is likely to become increasingly important as the
processor/memory differential increases).

> I agree completely. I even shove in prints to debug purely
> functional code (shame on me!) by adding "let _ = prerr_endline
> ... in" in such constructs.

I sometimes do that.  Perhaps for my proposal it would be useful to
have a ``debugf'' that prints (and flushes) to stderr, but isn't
flagged as side-effecting, with the assumption that these are not part
of the semantics of the program and will be removed before production.

(BTW, my postings to this list usually take 2 days to appear... I just
checked and this machine's mail queue is empty, so I don't know which
machine is holding on to my posting.... but I wish it would stop!)

../Dave
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Brian Rogoff]

On Sun, 10 Jun 2001, John Max Skaller wrote:
> Brian Rogoff wrote:
> 
> [Evaluation order]
> 
> > The original arguments about optimizations
> > and parallelism don't seem to have borne fruit, so it would be good to fix
> > this.
> 
> The question is whether we really want to encourage such
> an obvious flouting of referential transparency as being
> able to depend on the order of evaluation of the arguments
> of the infix integer addition operator.

Well, OCaml isn't referentially transparent, and it is strict to begin
with. I agree that it would be awful if my argument was only about the
order of evaluation of (+).

> Perhaps binding record fields left to right makes sense,

And tuples, and (::), and ... 

Why not make the default correspond to everyone's intuition?

> but making evaluation order explicit by
> 
> 	let a = f() in
> 	let b = g() in
> 	a + b
> 
> seems to be good style to me (you only need to know that
> Ocaml is an eager language).

I agree completely. I even shove in prints to debug purely functional code 
(shame on me!) by adding "let _ = prerr_endline ... in" in such constructs.  
I also rarely use "and" when there are no dependencies (I see that kind of 
code) and only use it when there is a recursive definition.

> You could also run into problems if you used some syntactic sugar such
> as by using ocamlp4: the visible ordering mightn't be the final one
> unless the p4 macros took special care to ensure this.

Hmmm, I wonder if this is a problem for MetaML, which is a macro-like
system based on SML? Any users on the list care to comment? As a
digression, macros and generic functions seem to be one of the few places 
left where Lisp has some advantage over ML (IMO of course). It would be 
nice to surpass Lisp completely one day...

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

Tore Lund wrote:

>   # let _ =
>       print_string "before";
>       print_string "MIDDLE";
>       print_string "after";;
>   beforeMIDDLEafter- : unit = ()
> 
> but not in this one:
> 
>   # let _ =
>       print_string "before";
>       Format.print_string "MIDDLE";
>       print_string "after";;
>   beforeafterMIDDLE- : unit = ()
> 
> What's going on here?  

	Buffering I guess. print_string buffers using stdio buffers.
Format.* has its own buffer, which is flushed into the
stdout buffer too late.


-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

David McClain wrote:

> The results of these two operations, integers, are arithmetically commutable
> under addition. But what isn't commutable is the order in which these
> operations occur. No current type checking in OCaml (or any other language
> with which I am familiar) could help catch this mistake.

	In principle, the Felix type checker would prevent this:
side-effects are not permitted in functions. In practice,
I had to relax the syntax permitted in functions, and the current
translator doesn't check for side effects yet. You can also
cheat, by wrapping C functions as Felix functions: there's no
way to check if the C function has side effects or not.

	The reason for relaxing the rules is that it is very ugly
and insecure to write things like:

	val x : int; // uninitialised variable!
	fetch(&x, &state_object);

instead of

	val x : int = fetch(&state_object);

I can't think of good way around this though.

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

Brian Rogoff wrote:

[Evaluation order]

> The original arguments about optimizations
> and parallelism don't seem to have borne fruit, so it would be good to fix
> this.

The question is whether we really want to encourage such
an obvious flouting of referential transparency as being
able to depend on the order of evaluation of the arguments
of the infix integer addition operator.

Perhaps binding record fields left to right makes sense,
but making evaluation order explicit by

	let a = f() in
	let b = g() in
	a + b

seems to be good style to me (you only need to know that
Ocaml is an eager language). You could also run into problems
if you used some syntactic sugar such as by using ocamlp4:
the visible ordering mightn't be the final one unless the p4
macros took special care to ensure this.


-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Tore Lund]

Tore Lund wrote:
> 
>   # let _ =
>       print_string "before";
>       print_string "MIDDLE";
>       print_string "after";;
>   beforeMIDDLEafter- : unit = ()
> 
>   # let _ =
>       print_string "before";
>       Format.print_string "MIDDLE";
>       print_string "after";;
>   beforeafterMIDDLE- : unit = ()
> 
> What's going on here?  All I did was to add "Format".  Is not printing
> an "effet du bord"?

For that matter:

  # let a =  print_string "before" in
    let b =  print_string "MIDDLE" in
    let c =  print_string "after" in
    a; b; c;;
  beforeMIDDLEafter- : unit = ()

versus:

  # let a = print_string "before" in
    let b = Format.print_string "MIDDLE" in
    let c = print_string "after" in
    a; b; c;;
  beforeafterMIDDLE- : unit = ()

Okay.  So there is buffering at work that has little to do with OCaml. 
Which probably means that the only side-effects guaranteed to happen in
a certain order are those carried out by the runtime system itself. 
Hmmm, at the very least this makes it necessary to distinguish between
two species of side-effect.
-- 
    Tore

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Tore Lund]

Charles Martin wrote:
> 
> The specification that indicates temporal preference is
> 
>         let <first> in let <second> in ...

Does not a sequence accomplish the same thing?  According to the
"Développement" (book-ora028.html):

  La première de des structures typiquement impérative est la séquence. 
  Elle permet l'évaluation ordonnée de gauche à droite d'une suite 
  d'expressions séparées par un point-virgule. 

and:

  Une séquence est une expression dont la valeur est celle de sa 
  dernière expression (ici, exprn). Néanmoins toutes les expressions 
  sont évaluées, et en particulier leurs effets de bord sont pris en 
  compte. 

If I read this right, it says that a sequence is evaluated from left to
right and side-effects are taking into account.  And it seems to work in
this example:

  # let _ =
      print_string "before";
      print_string "MIDDLE";
      print_string "after";;
  beforeMIDDLEafter- : unit = ()

but not in this one:

  # let _ =
      print_string "before";
      Format.print_string "MIDDLE";
      print_string "after";;
  beforeafterMIDDLE- : unit = ()

What's going on here?  All I did was to add "Format".  Is not printing
an "effet du bord"?
-- 
    Tore

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Joerg Czeranski]

David McClain wrote:
> My mistake was writing
>
> let ans = process_stream() + process_tail()
>
> [...]
>
> The results of these two operations, integers, are arithmetically commutable
> under addition. But what isn't commutable is the order in which these
> operations occur. No current type checking in OCaml (or any other language
> with which I am familiar) could help catch this mistake.

A minor nit: commutativity isn't involved.
The problem would be the same for

  let y = f() / g()

and even

  let y = h (f()) (g())

Operators (and functions) just don't care in which order their operands
(parameters) are evaluated.

I really like Haskell's solution, but I've never used Haskell much.
The main reasons for this is OCaml's superior Unix binding
and it being much easier to build and install.

jörg
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[David McClain]

> It sounds like a lot of what you're describing comes with Haskell's
> monadic IO system.  If you have an expression
>
>   e1 +  e2
>
> where e1 and e2 could be side effecting expressions, the type system
> forces you to write:
>
> do v1 <- e1
>    v2 <- e2
>    return v1 + v2
>

Hmm... Monads have been mentioned several times now. I need to go back and
refresh my understanding of these. I seem to recall that Marcus Motl did
something in OCaml related to monadic programming idioms. I am aware, now
that you mention it, that Haskell does have these temporal ordering
constraints available. It would be very nice to have these in a language
like OCaml with its easy integration of foreign functions.

- DM


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Patrick M Doane]

It sounds like a lot of what you're describing comes with Haskell's
monadic IO system.  If you have an expression

  e1 +  e2

where e1 and e2 could be side effecting expressions, the type system
forces you to write:

do v1 <- e1
   v2 <- e2
   return v1 + v2

If you're already familiar with Haskell, were there additional properties
you were looking for?

Patrick

On Sat, 9 Jun 2001, David McClain wrote:

> Earlier, I stated that there were no reference vars in the program. That's
> strictly true only of the OCaml portion of the code. However, the C/C++ core
> does maintain a mutable state and that is the reason for evaluation order
> dependencies.
> 
> It would seem that the compiler could automatically spot side effecting
> functions and propagate that attribute by noticing when reference vars are
> modified, when arrays and structures are mutated, etc. Hence explicit
> declaration should be unnecessary -- except! for those declared "external"
> routines that have side effects. Those need to be flagged explicitly to the
> compiler.
> 
> - DM
> 
> 
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr
> 

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Evaluation Order

[David McClain]

Earlier, I stated that there were no reference vars in the program. That's
strictly true only of the OCaml portion of the code. However, the C/C++ core
does maintain a mutable state and that is the reason for evaluation order
dependencies.

It would seem that the compiler could automatically spot side effecting
functions and propagate that attribute by noticing when reference vars are
modified, when arrays and structures are mutated, etc. Hence explicit
declaration should be unnecessary -- except! for those declared "external"
routines that have side effects. Those need to be flagged explicitly to the
compiler.

- DM


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[David McClain]

> The specification that indicates temporal preference is
>
>         let <first> in let <second> in ...
>
> Argument evaluation order and temporal preference are two orthogonal
concepts and should not be conflated.  I support unspecified argument
evaluation order.

I agree with you, but you have proposed effectively doing nothing. There is
no safeguard to prevent someone bypassing this syntax by accident.

- DM


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[David McClain]

> The idea is to annotate the type of any functional result with the
> fact that it has escaping side-effects.  Then to not let any
> so-annotated value be used directly in an expression.  Let's look at
> David's problem:

I had just thought of a similar solution myself, but I wouldn't be so strict
as to disallow any use in an expression. Rather, as long as only one such
function call exists in any one expression it would be okay. That would
allow things like

let ans = prev_ans + process_tail() in ....

It does sound like an easy solution, so knowing myself as I do, I am
wondering what I don't understand about the details... If it were so easy,
then why hasn't it been done yet?

- DM

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Charles Martin]

>The results of these two operations, integers, are arithmetically commutable
>under addition. But what isn't commutable is the order in which these
>operations occur....
>
>What is needed is some specification that indicates temporal preference, and
>then the type checking mechanism must be enhanced to keep temporal order.
>Most programs in OCaml probably have no preference, and in fact, a sense of
>order is strongly discouraged in most FPL's -- e.g., Haskell.

The specification that indicates temporal preference is

        let <first> in let <second> in ...

Argument evaluation order and temporal preference are two orthogonal concepts and should not be conflated.  I support unspecified argument evaluation order.

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Dave Mason]

There is a solution to this problem.  I don't know if anyone has
proposed this before, but it would be hard to believe that it's novel.

The idea is to annotate the type of any functional result with the
fact that it has escaping side-effects.  Then to not let any
so-annotated value be used directly in an expression.  Let's look at
David's problem:

>>>>> On Sat, 9 Jun 2001 16:28:56 -0700, "David McClain" <dmcclain1@mindspring.com> said:

> My mistake was writing

> let ans = process_stream() + process_tail()

In what I'm proposing, the result type of both process_stream and
process_tail would be so annotated:
	process_stream : unit -> int effect
	process_tail   : unit -> int effect
and the compiler would give you a side-effect error with that
expression.  But using such a value which was a simple variable would
remove the annotation and apply it to the whole expression, so:

	let ans =
	 let ans1 = process_stream() in
	 let ans2 = process_tail() in
		ans1 + ans2

would work.  Note that the function containing this computation must
also be tagged as side-effecting when its results are used elsewhere.

This would be fairly easy to add to the compiler and would *not*
require us to have a specified execution order in expression
evaluation (a Good Thing(TM)) but would prevent you from making the
kind of error seen here.  The biggest problem is that this is not a
proper type, as I have described it, although it could go in the
module interfaces as such, and can be automatically propagated by the
compiler.

So then David could go back to trusting the ocaml type system to
protect him.  :-)

This would not be completely backward-compatible with existing ocaml
programs (a Bad Thing(TM)), but any programs that it would break would
be ones that currently depend on the existing evaluation order (a Very
Bad Thing(TM)), so forcing them to fix their programs would be a Good
Thing, and for a change, two wrongs would make a right!

> What is needed is some specification that indicates temporal
> preference, and then the type checking mechanism must be enhanced to
> keep temporal order.  Most programs in OCaml probably have no
> preference, and in fact, a sense of order is strongly discouraged in
> most FPL's -- e.g., Haskell.

I have a feeling that what I propose is somehow related to monads, but
in a way that ocaml programmers would not find intrusive and would
make our programs more robust.

(This could actually be made a little more more useful at the cost of
being a little more complex.  Instead of 'a effect, have at least
three annotations: 'a ref_effect, 'a io_effect, 'a assign_effect.  So
the types of some common operators would be:
	(:=) : 'a ref -> 'a -> unit assign_effect
	(!)  : 'a ref -> 'a ref_effect
	incr : int ref -> unit assign_effect
	printf : ('a, out_channel, unit) format -> 'a io_effect
Then you could have any number of ref_effects combined with at most
one io_effect, but assign_effects could not be combined with another
assign_effect, more than one io_effect, or any ref_effects.  This
would break a minumum number of existing programs, but still be safe.)

../Dave
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[David McClain]

> > Use lots of lets to sequence operations. Avoid side effects like output
in
> > value returning operations, otherwise you'll want to use lets to
sequence
> > the outputs while getting the value. Write Haskellish code, by which I
> > mean try to push all of your refs and mutable values to the top level
and
> > have all of your library calls pure. Agitate to get this annoying
feature
> > fixed. Etc...
>
> Actually the side effects I was referring to have nothing to do with
> reference vars. In fact there are none in the code. Rather, the side
effects
> have to do with the order in which data are processed and sent along to
the
> next job upstream.

In fact let me be a bit more specific, by way of example...

The block convolution operation could be viewed as adding reverberation to a
data stream. The first function processes the entire stream. The second
operation writes out the remainder, the reverb tail, after the input stream
has been exhausted.

My mistake was writing

let ans = process_stream() + process_tail()

where both operations return a count of how many data samples had been
written to the output stream. I accidentally got the tail processing first,
which caused the anomalous output. The front of the output stream had too
much null data, and the final tail of the stream was chopped off.

The results of these two operations, integers, are arithmetically commutable
under addition. But what isn't commutable is the order in which these
operations occur. No current type checking in OCaml (or any other language
with which I am familiar) could help catch this mistake.

What is needed is some specification that indicates temporal preference, and
then the type checking mechanism must be enhanced to keep temporal order.
Most programs in OCaml probably have no preference, and in fact, a sense of
order is strongly discouraged in most FPL's -- e.g., Haskell.

I am saying that real-world applications for control systems do have strong
needs for these additional constraints. I am not being critical of OCaml or
any other language here. But my experience pointed out the need for even
more from programming languages than what we have today.

The major flubs of the past decades, Arianne, Therac, and many others, are
examples of systems in which not only the data types have to be ensured, but
also temporal orderings of function evaluation. We are rapidly adopting a
system with a foundation of dust when we come to rely so heavily on human
programmed computers to manage and treat our lives.

- DM


----- Original Message -----
From: "David McClain" <dmcclain1@mindspring.com>
To: "Brian Rogoff" <bpr@best.com>
Cc: <caml-list@inria.fr>
Sent: Saturday, June 09, 2001 4:12 PM
Subject: Re: [Caml-list] Evaluation Order


> > No, if Hebrew or Arabic were your native tongue you'd have exactly the
> > same expectation as you have now, which is that the events occur in the
> > order that you scan them while reading. What happens in OCaml now is
like
> > some weird boustrophedon.
>
> Huh? Hebrew and Arabic read from right to left, which is why I said what I
> did... A boustrophedon infers that the order changes to and fro in a
raster
> pattern. I won't argue the point about unspecified order of evaluation. I
> would argue for notation that indicates temporal preferences and helps to
> enforce them in the code.
>
>
> > Use lots of lets to sequence operations. Avoid side effects like output
in
> > value returning operations, otherwise you'll want to use lets to
sequence
> > the outputs while getting the value. Write Haskellish code, by which I
> > mean try to push all of your refs and mutable values to the top level
and
> > have all of your library calls pure. Agitate to get this annoying
feature
> > fixed. Etc...
>
> Actually the side effects I was referring to have nothing to do with
> reference vars. In fact there are none in the code. Rather, the side
effects
> have to do with the order in which data are processed and sent along to
the
> next job upstream.
>
> I would argue for something stronger here. The mistake was made as a
result
> of performing a commutative arithmetic operation between two results that
> should never commute in time. I think a sequencing operation and a type
that
> distinguishes objects that have specified temporal orderings is in order
> here.
>
> Otherwise we are left to astute programmers who have to be on their very
> guard continuously against unintentional misuse of evaluation order.
Humans
> are not trustworthy in the sense that machines are, which never tire of
> mundane tasks.
>
> - DM
>
> -------------------
> Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ:
http://caml.inria.fr/FAQ/
> To unsubscribe, mail caml-list-request@inria.fr  Archives:
http://caml.inria.fr

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[John Max Skaller]

David McClain wrote:
[order of evaluation problem]

> Any thoughts? (other than that I was boneheaded here!)

	Actually, I think that the problem is that the
Ocaml syntax is basically designed for a referentially
transparent functional programming language, which
Ocaml is not. 

	If you have a function with side-effects,
return 'unit'. At worst:

	f ( g () ) 

which is equivalent to

	g(); f()

[Ugh: Felix has a type 'void' to prevent this]

-- 
John (Max) Skaller, mailto:skaller@maxtal.com.au
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[David McClain]

> No, if Hebrew or Arabic were your native tongue you'd have exactly the
> same expectation as you have now, which is that the events occur in the
> order that you scan them while reading. What happens in OCaml now is like
> some weird boustrophedon.

Huh? Hebrew and Arabic read from right to left, which is why I said what I
did... A boustrophedon infers that the order changes to and fro in a raster
pattern. I won't argue the point about unspecified order of evaluation. I
would argue for notation that indicates temporal preferences and helps to
enforce them in the code.


> Use lots of lets to sequence operations. Avoid side effects like output in
> value returning operations, otherwise you'll want to use lets to sequence
> the outputs while getting the value. Write Haskellish code, by which I
> mean try to push all of your refs and mutable values to the top level and
> have all of your library calls pure. Agitate to get this annoying feature
> fixed. Etc...

Actually the side effects I was referring to have nothing to do with
reference vars. In fact there are none in the code. Rather, the side effects
have to do with the order in which data are processed and sent along to the
next job upstream.

I would argue for something stronger here. The mistake was made as a result
of performing a commutative arithmetic operation between two results that
should never commute in time. I think a sequencing operation and a type that
distinguishes objects that have specified temporal orderings is in order
here.

Otherwise we are left to astute programmers who have to be on their very
guard continuously against unintentional misuse of evaluation order. Humans
are not trustworthy in the sense that machines are, which never tire of
mundane tasks.

- DM

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Evaluation Order

[Brian Rogoff]

On Sat, 9 Jun 2001, David McClain wrote:
> I thought I would share an experience with all of you to solicit your
> *constructive* comments.

Hmmm, last time we were through this I recall that you were emphatically
in favor of leaving the evaluation order undefined. It is good that you
have finally seen the light ;-) (sorry, that wasn't terribly constructive). 

> I had forgotten about the evaluation ordering in OCaml being from right to
> left. 

Actually, if you are an anal reader of reference manuals (sorry, once an
Ada programmer...) you'll not that evaluation order in OCaml is currently 
unspecified. Of course, the one implementation behaves as you describe.

> I suppose if Hebrew or Arabic were my native tongue then the opposite
> expectation would be true and I would have naturally written
> 
>     let ans = fny() + fnx()
> 
> and I would be no wiser about evaluation order here, since everything would
> have worked properly.

No, if Hebrew or Arabic were your native tongue you'd have exactly the
same expectation as you have now, which is that the events occur in the
order that you scan them while reading. What happens in OCaml now is like
some weird boustrophedon.

> I had been lulled into a belief that OCaml was nearly perfect, while C/C++
> is definitely not. 

But that's true! Damn, I keep baiting Chris, gotta sit on my hands :-)

> The problem is not one of OCaml, but rather a clash between normal
> psychological expectations and the programming language at hand.

No, this is a language problem. Lots of people who teach OCaml have mentioned 
that this is an issue. If the clash with expectation is so great then that
You should always be careful about sequencing in imperative style programming, 
but IMO this is one of those few things that SML does right that OCaml does 
not. As you say, there is a very strong expectation that events occur in
the order that we read them. The original arguments about optimizations
and parallelism don't seem to have borne fruit, so it would be good to fix
this.

> Any thoughts? (other than that I was boneheaded here!)

Use lots of lets to sequence operations. Avoid side effects like output in
value returning operations, otherwise you'll want to use lets to sequence
the outputs while getting the value. Write Haskellish code, by which I
mean try to push all of your refs and mutable values to the top level and
have all of your library calls pure. Agitate to get this annoying feature
fixed. Etc...

-- Brian


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Evaluation Order

[David McClain]

I thought I would share an experience with all of you to solicit your
*constructive* comments.

I just rewrote my block convolution routine in pure OCaml native compiled
along with the inner loop in C/C++. This is necessarily a side effecting
program since it must alter the outside world of data. I had a statement in
OCaml that went something like this:

    let ans = fnx () + fny ()

where both fnx and fny are side effecting closures.

I consider myself a very experienced OCaml programmer, and I am so
accustomed to getting pristine results from OCaml, that I spent many hours
going through my C/C++ code looking for the error. I was getting anomalous
output values at the front of my convolution records, but everything else
worked just fine. I was convinced something was awry with my C code ---
whenever a problem occurs that's almost always where it is -- never in the
OCaml code.

I had forgotten about the evaluation ordering in OCaml being from right to
left. I am aware of the reasons for this, having studied the Zinc paper some
time ago. But the tendency to read implicit temporal ordering of operations
as left to right is a very strong psychological factor here. The problem,
once tracked down, was easily fixed by restating the routine as

    let ans = fnx() in
        ans + fny()

to force evaluation of fnx before fny.

I suppose if Hebrew or Arabic were my native tongue then the opposite
expectation would be true and I would have naturally written

    let ans = fny() + fnx()

and I would be no wiser about evaluation order here, since everything would
have worked properly.

I don't have a good answer to this problem, but I did want to point out the
one and only place where OCaml forced me to spend hours debugging a problem
caused solely by a clash of psychology and OCaml semantics. All of my other
debugging activities have, and will probably continue, to focus on C/C++ as
the likely culprit.

This problem will be permanently etched into my mind from now on, and I will
be sure to remember to avoid order dependent syntax.

The same problem occurs regularly in C, and I have become quite accustomed
and adept at avoiding these ordering problems. Good examples are to be found
among C preprocessor macrology. I just now have to remember that the same is
true of OCaml.

I had been lulled into a belief that OCaml was nearly perfect, while C/C++
is definitely not. The problem is not one of OCaml, but rather a clash
between normal psychological expectations and the programming language at
hand.

Since embedded realtime systems are chock full of temporally ordered
operations this must be one of the severe weak points in software control
systems. There must be a better way to guide human thinking here. Just as
OCaml has provided a system to look over our shoulders and force us to write
the correct things, there must be a way of doing something similar for
temporally dependent clauses.

Any thoughts? (other than that I was boneheaded here!)

- DM


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr