RE: [Caml-list] laziness

[Jason Smith <jns28@student.canterbury.ac.nz>]

>> > However if the call is *inlined* to get
>> >
>> > 	if c' then a' else b'
>> >
>> > then perhaps a' or b' will never be evaluated.
>I understand that argument -- but that doesn't mean the
>compiler conforms to the specification, nor that the
>specification is best.

I'm not sure about OCaml but in GHC we could garuentee that the arguments a' 
and b' would be reduced using the 'case' syntax in GHC's intermediate language 
"Core". This the code would become something like this:

case c' of 
{ c'' ->
   case a' of
   { a'' ->
      case b' of
      { b'' -> if c'' then a'' else b'';
      }
   }
}

case forces evaluation to WHNF form, thereby garuenteeing correct eager order 
evalation. I presume O'Caml would do the same to keep side-effects evaluting 
correctly.

>> E.g. the order of evaluation of arguments is
>> unspecified, so it might be different depending on inlining; but
>> OCaml does specify that each argument are evaluated exactly once
>> and inlining doesn't change that.
>
>Must they be evaluated before the function is called?

If O'Caml follows the usual eager order semantics then evaluation is AOR or 
Applicative order redection. (Which is what I use in Mondrian).

There are several locations where we may attempt to reduce this overhead.

Strictness analysis: Determines usuing some form of abstract reduction 
semantics weather the argument is "strict" in the function, i.e. that it will 
be used at all. If it isn't then there is no need to reduce it. The problem 
with this is that in O'Caml u once again have side-effect's raise there ugly 
head. This means that even if the argument is not used in the function, the 
results of evaluating the argument which uses side-effects is. So you may have 
to analyse the argument itself and see if it uses any reference semantics.

Usage analysis: Determines "how many times" an argument is used. Not so much 
applicable to eager order evaluation but very handy in lazy languages. We can 
save the cost of a THUNK update by determining if we actually need to update 
the thunk with the new value once the argument has been reduced.

There are a range of other analysis techniques that "increase the degree of 
laziness" aka full-laziness transformation, reduce the cost of creating 
intermediate data structures aka deforestation, let-floating etc.. refer to a 
great body of literature for comments on these area's.

HTH
Jason.

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