Thoughts on laziness (long)

[Jeffrey Straszhiem]

On Wed, Oct 18, 2000 at 01:11:44PM +0200, Robert Virding wrote:

> I personally think that laziness can be interesting but have yet
> come across any applications in Erlang where it would have been
> useful.

> Many of the uses of laziness in other functional languages are handled
> in Erlang with processes and message communication.  Implementing lazy 
> streams for communication does not give you very much and in many cases 
> is much more limiting than Erlang's message passing with selective 
> receives.

True, Erlang's rich process and message features do provide
alternatives to lazy streams for many tasks.  However, I think
Okasaki's amortized data structures might alone provide a good reason
for some call-by-need laziness features.

<snip>

> Another problem with call-by-need, which I tried to point out in an
> earlier mail, is that it creates problems when used in conjunction
> with processes and distribution.  For many applicattions it IS
> important WHEN and WHERE things are done.
 
> You also have the proble that in Erlang programs there are many
> functiona calls which are done for effect, send a message, so
> waiting to evaluate them until you need the result won't give you
> much. :-)
 
True, but these are areas where one would surely *not* choose a lazy
structure.

Regarding whether messages should be forced, if you are only using
laziness on side-effect-free values (as you should), it doesn't matter
when the suspension is forced.  And as suspensions are just memoized
Funs, and you can pass Funs as messages, there certainly is an option
to send the suspension unforced.

That being said, you give good reasons to force them.  I don't know
which would be best, and this should be left an issue of further
research (by smarter people than me).  For the purposes of amortized
structures, there are arguments that could be made for both options,
and an even stronger argument for putting suspensions in shared heap
-- but that is an entirely different topic I won't address :)

> My solution was, as mentioned, force full evalutaion for all messages 
> and for all calls which ignore the result.  This should make the most 
> things work, but you will still end up with sequencing problems:

>     R1 = foo(...),
>     R2 = bar(...),

> If R1 and R2 are used then both foo nad bar will be called but I may 
> lose control of the order, which may be important.

This is true, and without some Byzantine structure like monads, I
don't see an easy solution.  Perhaps laziness should be assigned to
the "only use this if you know what you're doing" category (which is
fortunately a small category in Erlang space, but needn't be an empty
category).

For instance, Okasaki's amortized queues wouldn't suffer because all
values place into the queue will have been evaluated before insertion
(as Erlang is still elsewhere strict).  Only the internal queue
structures (the cons's and such) themselves will be modified lazily.
This would be safe and useful, and could be provided in a nice module.

<snip>

> However, I wonder if it possible to update Erlang with such a feature 
> and still keep it sufficiently backwards compatible to call be able to 
> call it the same language.  You might end up with a new language, Lazy 
> Erlang, with new semantics.

Sure it would be backward compatible, as laziness would only be a
small addition to the language -- and only used just where
specifically desired.  I don't think anyone is advocating replacing
Erlang's present computational model with a lazy one, nor replacing
strict lists with lazy streams.  Lazy-by-default languages are complex
beasts, often hard to learn, and with a vague feeling of
"specifications on an amorphous sea of computation".  Erlang's simple
and direct model is easy to understand, and easy to learn.  This must
never change.

(As usual, just my 2 monetary units.)

-- Jeffrey Straszheim              |  A sufficiently advanced
-- Systems Engineer, Programmer    |  regular expression is
-- http://www.shadow.net/~stimuli  |  indistinguishable from
-- stimuli AT shadow DOT net       |  magic