for review: add lazy evaluation to library

[Lee Naish]

Fergus Henderson <fjh at cs.mu.OZ.AU> writes:

>I propose adding support for optional lazy evaluation to the
>standard library.  Comments?
>I'd appreciate any feedback.


>% a lazily-evaluted value of type T
> :- type lazy(T).

>% convert a value from type T to lazy(T)
> :- func val(T) = lazy(T).
> :- mode val(in) = out(lazy) is det.

>% construct a lazily-evaluated lazy(T) from a closure.
> :- func delay((func) = T) = lazy(T).
> :- mode delay((func) = out is det) = out(lazy) is det.

>% force the evaluation of a lazy(T), and return the result as type T.
> :- func force(lazy(T)) = T.
> :- mode force(in(lazy)) = out is det.


I suspect a few people might be mislead by this interface with its
scanty comments.  Laziness is mostly useful for recursive type, eg list.
Reading the above its tempting to think lazy(list(int)) is a lazy list
of ints.  In fact, only the outermost level is lazy.  For recursive
types you need to do more work yourself and create a type like the
following: lazyish_list ---> [] ; [int | lazy(lazyish_list)] then use
lazy(lazyish_list) everywhere.

The "force" primitive is also less powerful than some might suspect.
Typically you need to distinguish between two kinds of forcing of
evaluation: just the top level of the DS (for a switch) or the whole DS
(eg, if the top level prints the result).  The implementation of both
these tends to be iterative.  Even to evaluate the top level in a
typical lazy language you need iteration to handle

f(X) = g(X).
g(X) = h(X).
...

Each of these is implicitly lazy, like

f(X) = delay(g(X)).
g(X) = delay(h(X)).

With Fergus' scheme you run into problems with the types: lazy(lazy(T))
is different from T.  The programming style is less flexible - I'm not
sure of the consequences of this.  Se also * below.

Evaluating the whole term is also generally required when comparison is
done.  I suspect Fergus' implementation of equality is wrong for
recursively defined lazy types: somehow force must be called multiple
times to check if two things of type lazy(lazyish_list) are equal.  I
guess the user must supply the right equality code for the type
lazyish_list instead of relying on the default.

* In my implementation of laziness on top of Prolog, the additional
wrapper for closures was essentially *merged* with the existing types
rather than wrapping up types with the two possibilities (closure or
concrete value).  eg, for lists we get

lazy_list ---> [] ; [int | lazy_list] ; closure(...).

I am still convinced that this is the "right" design and that Fergus'
method (while easier to graft on to existing code) is not as good.
Perhaps it gives an ok but somewhat less flexible way to do laziness.
Or it may even be worse than that.

	lee