Re: [Caml-list] laziness

[Jon Harrop <jon@jdh30.plus.com>]

On Saturday 04 September 2004 07:30, skaller wrote:
> ...
> 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.

That is true for manual inlining but false for automatic inlining by the 
compiler (which must retain obide by the specifications).

Actually, for any single evaluation a' or b' will never be evaluated. ;-)

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

OCaml evaluates eagerly by default. There are some lazy special cases. 
Specifically the usual binary infix boolean operators, the "if" expression 
and pattern matches.

There was a discussion fairly recently, by Pierre Weis among others, that it 
might be cool to be able to declare your own functions as non-strict. The 
functionality can be obtained regardless, by wrapping expressions in closures 
and only evaluating them when you need to, but it's a pfaff.

> It seems that procedural code (which includes
> functional expressions) is actually a way to
> specify evaluation order

I would say that imperative style allows you to determine evaluation order, 
not specify it.

> and timing and typically 
> control flow is used to delay evaluation -- so that
> procedural programming is actually quite lazy.

I think inability to build a closure makes imperative languages even more 
strict. You may be referring to a way of "faking it" using imperative style 
but I wouldn't say that writing Haskell in C makes C lazy.

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

Lazy evaluation is often (typically?) used to refer to memoizing as well as 
evaluating on demand. In which case lazy evaluation also prevents 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 .. )

Reasoning about lazy programs is difficult, AFAIK. I imagine this is because 
lazy programs end up building stacks of closures which act as data structures 
(require memory etc.) and which are a function of the input (i.e. they have 
non-trivial complexities).

Such problems can appear in OCaml. For example, I'd assume that converting 
(I'm using Array to avoid discussions of tail recursion ;-):

Array.map f (Array.map f l)

to:

Array.map (fun e -> f (f e)) l

would be a deforesting optimisation. However, for short arrays and longer 
stacks of composited functions, there will probably come a time when an 
equivalent "optimisation" slows things down by "foresting" stacks of 
functions.

> (1) exactly what does Ocaml guarrantee?

I think you're looking for: "strict evaluation of function and constructor 
arguments in an unspecified order by default".

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

Are you asking if it would be productive to change the specs to something like 
in-order evaluation? I'm no expert but I think the non-specific order of 
evaluation is a good opportunity for optimising and the strictness vs 
laziness choices set OCaml in a nice position with regard to imperative 
programming.

> a purely functional
> language is necessarily lazy, because lazy evaluation
> is mandatory

I'd have thought that you cannot determine evaluation order in a purely 
functional language and, therefore, you couldn't distinguish between eager 
and lazy evaluation in this case.

> -- an eager evaluation strategy *requires* 
> procedural constructions to provide the laziness, and so
> can't work with a purely functional language.

I think that the way OCaml provides (memoized) laziness is inherently 
imperative but you could write a functional equivalent by providing an API 
which lets you recreate the lazy construct each time you use it.

Cheers,
Jon.

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