[m-dev.] Re: for review: add lazy evaluation to library

Fergus Henderson fjh at cs.mu.OZ.AU
Wed Mar 10 22:06:09 AEDT 1999


On 10-Mar-1999, Lee Naish <lee at cs.mu.OZ.AU> wrote:
> 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.

Yes, that is a good point.  I'll add something like that to the comments.

> 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.

Or recursive! ;-)

Yes, for lazyish_list you would need to write

	:- func force_lazy_list(lazy(lazyish_list(T))) = list(T).
	force_lazy_list(L0) = L :-
		L1 = force(L0),
		( L1 = [], L = []
		; L1 = [X|Xs], L = [X|force_lazy_list(Xs)]
		).

> 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,

Yes.

> like
> 
> f(X) = delay(g(X)).		[should be delay((func) = ...). -fjh]
> g(X) = delay(h(X)).		                 ^^^^^^^^

Well, perhaps more like

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

or

	lazy_f(X) = delay((func) = eval_f(X)).
	eval_f(X) = force(lazy_g(X)).

	lazy_g(X) = delay((func) = eval_g(X)).
	eval_g(X) = force(lazy_h(X)).

You can simply this by replacing force(lazy_foo(...)) with eval_foo(...):

	lazy_f(X) = delay((func) = eval_f(X)).
	eval_f(X) = eval_g(X).

	lazy_g(X) = delay((func) = eval_g(X)).
	eval_g(X) = eval_h(X).

In fact doing it this way is pretty much essential, because the former
approach risks space leaks.

> 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.

Well, you should never use the type lazy(lazy(T)), instead you should
insert a call to force/1 so that it becomes just lazy(T), as above.

It's true that the difference between lazy(T) and T makes things
less convenient than in a lazy language.

> 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.

No, my implementation of equality works fine for recursively defined
lazy types; the user doesn't need to supply their own equality code.

The compiler will generate code that looks like

	unify_lazyish_list([], []).
	unify_lazyish_list([X|Xs], [Y|Ys]) :-
		unify(X, Y),
		unify_lazy(Xs, Ys).

	unify_lazy(Xs, Ys) :-
		equal_values(Xs, Ys).

where equal_values/2 is my user-defined equality predicate for lazy(T):

	equal_values(Xs, Ys) :-
		force(Xs) = force(Ys).

The unification force(Xs) = force(Ys) will in this case
recursively call unify_lazyish_list to unify the tail.
(That will in turn call unify_lazy, which will call equal_values,
which will unify, which will call force and then unify_lazyish_list
again, etc.)

> * 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.

I implemented a lazy_list module for Mercury in the above manner,
before I came up with the current proposal.  And the above is indeed
potentially more efficient.

However, simply adding a lazy_list module is not nearly as general
as my current proposal.

We could add support for lazy data types and laziness to the language and
the compiler, rather than providing it as a library module.  However,
that would be a much more significant step.  The advantage of my proposal
is that it can be implemented as a library module, without needing
any compiler or language support.

> Perhaps it gives an ok but somewhat less flexible way to do laziness.

Inserting the calls to force and delay manually is more tedious, certainly,
but I don't think it is less flexible. 

There is really no significant difference, except perhaps efficiency,
between the indirectly recursive type lazy(lazyish_list(T)) and the
flattened directly recursive version lazy_list(T).  Anything that
you can do with the latter, you can also do with the former.

The significant difference is just that the user is the one inserting
the calls to force and delay, rather than the compiler.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.



More information about the developers mailing list