[Haskell] Importance of precise lazy-evaluation semantics (was: line-based interactive program)

[Jan-Willem Maessen]

On Jul 8, 2005, at 10:20 AM, Jean-Philippe Bernardy wrote (in an  
exchange with Colin Runciman):
>>>> My interaction depends on the (subtle order of) evaluation of a  
>>>> pure and
>>>> total function?
>>>>
>> Pure, yes; total, no.
>>
>> Many important things depend on order of evaluation in lazy programs:
>> for example, whether they compute a well-defined value at all!   ...
> It seems to me that this sort of thing is why haskell is difficult to
> compile to efficient code. I have the impression that relaxed
> semantics wouldn't hurt 99% of programs while make the compiler-writer
> job easier. The only disadvantage is that tricks like the above one
> wouldn't work any more.
>
> Another point is, imho, most haskell programmers don't grasp the exact
> lazyness semantics; they think of lazyness as "evaluation order is up
> to the compiler", not the precise graph-reduction thing.
>
> Hence, haskell would perhaps be better off with more "fuzzy"
> semantics, since it would match the intuition of people, and allow
> more optimized code. Those ideas have been explored before, if I'm
> correct in the "optimistic evaluation" project, and Eager haskell.
> Yet, I'm wondering what's the current opinion of the haskell "gurus"
> on the subject.

Be careful.  Both Eager Haskell and optimistic evaluation went to some  
pains to preserve the exact same non-strict semantics as lazy  
implementations of Haskell.  Eager Haskell had particular trouble with  
lazy computations (especially infinite streams): it computed quite a  
bit of extraneous gunk before noticing that it was wasting time and  
returning to useful computation.  This came up more often than I  
initially assumed, though most idiomatic uses were easy to eliminate  
(by substituting "numberListFrom n" for "zip [n..]" for example).

By contrast, pH has the "fuzzy" semantics you seem to imagine---it just  
runs eagerly and non-strictly.  A number of Haskell idioms (anything  
involving where clauses springs to mind) don't work quite the way you'd  
expect in this setting, and you have to be relatively careful about  
code motion during program optimization.

-Jan-Willem Maessen

>> [I am conscious that we are using bandwidth on the main Haskell  
>> mailing
>> list for this little discussion -- perhaps we are about done, but if  
>> not
>> perhaps we should mail each other direct.]
>
> The subject is very interesting to me, and I suspect many others, so  
> feel free.
>
>
> Cheers,
> JP.
>
> [1] Eager haskell
> http://csg.csail.mit.edu/projects/? 
> action=viewProject&projectID=5&projectGroup=Programming%20Languages
>
> [2] Optimistic evaluation
> http://www.cambridge.intel-research.net/~rennals/icfp2003.pdf
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell