[Caml-list] laziness

[skaller <skaller@users.sourceforge.net>]

Since I've been fiddling with various optimisations in
my own compiler, I've become quite curious about
laziness and its relation to both performance and semantic
guarrantees.

As motivation consider:

	let f c a b = if c then a else b

As I understand it Ocaml will handle a call

	f c' a' b'

by evaluating f,c',a',b' in some order then
applying f to c' a' b' -- eager evaluation.
However if the call is *inlined* to get

	if c' then a' else b'

then perhaps a' or b' will never be evaluated.

[As I understand it, inlining is substitution aka
normal order evaluation for lambda terms; 
that is, a lazy evaluation strategy.]

In particular my 'impression' that ocaml evaluates
function arguments eagerly would be wrong.

It seems that procedural code (which includes 
functional expressions) is actually a way to
specify evaluation order and timing and typically
control flow is used to delay evaluation -- so that
procedural programming is actually quite lazy.

OTOH procedural languages (including Ocaml) also
allow early evaluation.

>From a performance viewpoint, both eager and lazy
evaluation have advantages -- lazy evaluation avoids
gratuitously evaluating a term which the result does
not depend on, whereas eager evaluation can be used to
prevent an evaluation being done twice. Hence procedural
languages like Ocaml can be very fast because you can
hand tune the tradeoffs (also making it harder to 
reason about the outcome .. )

There seems to be some kind of sliding scale like this
for functional code:

C/C++ --> sequence points (functions have side effects)
Ocaml --> looser assurances
Felix --> no side effects but not fully parametric
Haskell --> everything is lazy, immutable, and parametric

So I have two questions:

(1) exactly what does Ocaml guarrantee?

(2) what kind of performance and semantic
tradeoffs are involved with perturbations
on these assurances?

What I'm actually finding at the moment with Felix is that
my optimisation efforts, mainly inlining, are actually
'lazifying' code, and thus involve a change in semantics --
although Felix functions can't have side effects, there
are also procedures which can, and functions may depend
on variables which procedures modify, so that in general
the result of a function does depend on when it is
executed. This effect is also available in Ocaml via
references.

I used to think the difference between lazy and eager
evaluation were minor quirks -- I'm tending to think now
the difference is quite fundamental, eg a purely functional
language is necessarily lazy, because lazy evaluation
is mandatory -- an eager evaluation strategy *requires* 
procedural constructions to provide the laziness, and so
can't work with a purely functional language.

Any comments would be appreciated.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net



-------------------
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/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners