order of evaluation ?

[Bernard James POPE]

konst writes:

> my question is, if i have an expression such as ((Const False) :&:
> <subexp>), will <subexp> be reduced first (according to the definition
> 'simplify (x :&: y) = simplify' ((simplify x) :&: (simplify y))') or
> will laziness do the right thing, and emit (Const False) without looking
> into <exp>?
> i think the latter, but would appreciate a word from an expert.

Hi Konst,

There is an easy way to check, try making <subexp> an erroneous 
computation.  There is such a value in the Prelude, it is called
undefined:

   simplify ((Const False) :&: undefined)

If this bombs then you know that simplify wasn't as lazy as you thought, since
it must have tried to evaluated 'undefined'. On my version of hugs I get:

   Program error: {undefined}
 
The important bits of code are: 
 
   simplify (x :&: y) = simplify' ((simplify x) :&: (simplify y))
 
   simplify' (x :&: (Not y)) | x==y = Const False

   simplify' ((Const False) :&: _)  = Const False

The order of the equations for simplify' is important. Effectively pattern
matching causes evaluation in Haskell. To determine whether the first
equation for simplify' should be used, the second argument of :&: must
be evaluated to what is called "weak head normal form" (whnf). This means
that the outermost constructor of that argument must be computed. 
Hence the computation with undefined fails in this case.

However, what happens if you swap the order of the equations for simplify'?
Doing so will give you the lazyness that you originally expected (for this
particular example).

Swapping the order of equations is not a silver bullet however, and you must
be very careful with how you order them.

One of the best places to learn about the operational semantics of languages
like Haskell is "The Implementation of Functional Programming Languages"
by Simon Peyton Jones. I think it is out of print, but you may find copies
in your local uni library if you are lucky. 

For this particular example, pay close attention to the Pattern Matching
Compiler section, which I think was done by Wadler.

Cheers,
Bernie.