[m-dev.] Re: for review: lazy evaluation [round 2]

[Fergus Henderson]

On 15-Mar-1999, Peter Schachte <schachte at cs.mu.OZ.AU> wrote:
> On Mon, Mar 15, 1999 at 01:16:51AM +0000, Lee Naish wrote:
> > Fergus Henderson <fjh at cs.mu.OZ.AU> writes:
> 
> > >+:- func append(lazy_list(T), lazy(lazy_list(T))) = lazy_list(T).
> > 
> > >+append([], Ys) = force_list(Ys).
> > 
> > This is an example where the naive "append([], Ys) = Ys" doesn't work
> > because the lazy wrapper is not integrated into the list type.
> 
> Couldn't this be made prettier by instead declaring
> 
> 	:- func append(lazy_list(T), lazy_list(T)) = lazy_list(T).
> 
> and then writing
> 
> append([], Ys) = Ys
> 
> ?

Doing that would make append/2 strict in its second argument,
which you don't want.

Consider

	foo = append(InfiniteList, Bottom) :-
		InfiniteList = iterate(double, 1),
		Bottom = delay((func) = loop).

	loop = loop.

The expression `take(5, foo)' should return `[1, 2, 4, 8, 16]',
whereas if append/2 were defined as you suggest, foo would have to
be defined as `foo = append(InfiniteList, force_list(Bottom)) :- ...',
and so evaluation of `take(5, foo)' would not terminate.

> > >+map(F, [H|T]) = [F(H) | delay((func) = R :- R = map(F, force_list(T)))].
> >                                 ^^^^^^^^^^^^^^^^^^
> > I wonder if this can be made less ugly.  Its tempting to encapsulate it
> > in some way but it probably needs a call by name construct which might
> > be even worse than messy syntax.  Or could you get away with
> > "func map(F, force_list(T))" denoting the closure?
> 
> Or "(func) = map(F, force_list(T))"
> 
> Better still, why can't "delay(map(F,force_list(T)))" work?

That can't work without special syntactic sugar,
because the compiler will rewrite `... delay(map(F,force_list(T))) ...'
as

	V0 = force_list(T).
	V1 = map(F, V0),
	... delay(V1) ...

and this implies that you get eager evaluation rather than lazy evaluation.

(For example, the above definition of map/2 would become

	map(H1, H2) = H3 :-
		H1 = V,
		H2 = [H | T],
		V0 = force_list(T).
		V1 = map(F, V0),
		V2 = delay(V1)
		H3 = [F(H) | V2],
	
after the compiler has converted the source to HLDS.)

You could do it with special syntactic sugar... but I suggest
that we not add syntactic sugar unless/until the lazy module is
part of the standard library.  Currently the concensus seems to be
that for the moment we should put the lazy module in extras rather
than in the standard library, but if people think it should go in
the standard library now I'd be happy with that.

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