Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!ucsd!pacbell.com!pacbell!osc!jgk
From: jgk@osc.COM (Joe Keane)
Newsgroups: comp.lang.functional
Subject: Re: Can laziness sometimes be too lazy?
Summary: Errors are not bottom.
Message-ID: <3188@osc.COM>
Date: 23 Jul 90 22:48:39 GMT
References: <2706@bruce.cs.monash.OZ.AU>
Reply-To: jgk@osc.COM (Joe Keane)
Organization: Object Sciences Corp., Menlo Park, CA
Lines: 41

In article <2706@bruce.cs.monash.OZ.AU> mmcg@bruce.cs.monash.OZ.AU (Mike
McGaughey) writes:
>Are there situations where lazy evaluation is *too* lazy?
>
>The following example (due to Lloyd Alison) shows what I mean:
>
>let rec first n l =
>		if n = 0 then []
>		else (hd l).(first (n-1) (tl l))
>and rec length l =
>		if l = [] then 0
>		else 1 + length (tl l)
>in
>    length (first 2 [])
>
>In a strict language, the result is an error, due to the (tl []) in "first".
>
>In a lazy language (LML here), you get the result 2.

The whole idea of being lazy is that you do as little work as possible.  The
constraint is that that you can't change the return values or side effects of
an expression.  One thing that you are allowed to do is change bottom into
some valid value, as long as you're consistent.  I won't explain this, except
to point out that a program which gets stuck can't contradict one that does
something useful.

Many functional languages are weak in exception handling.  For example, one
whose name i won't mention says that if you get any error, you lose, the
result is the same as bottom.  In a language like this, it is valid for the
example expression to return 2, for the reason given above.

Now suppose we're in a language with real exception handling.  It's only a
matter of terminology whether you count an exception as a kind of return
value, a side effect, or something different.  Given the constraint above, the
implementation must examine the expression far enough to determine whether it
will raise an exception.  This is exactly what you'd expect.  If it doesn't,
it's broken.

In summary, i think exception handling is an important part of any language.
In particular, defining errors to be the same as bottom is an unwise thing to
do, and this example points out some of the consequences.