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

[Fergus Henderson]

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

Yes, all the evaluations which would be implicit in a lazy language
must be made explicit.

> >+map(F, [H|T]) = [F(H) | delay((func) = R :- R = map(F, force_list(T)))].
>                                 ^^^^^^^^^^^^^^^^^^
> I wonder if this can be made less ugly.

My recent change to the rules about quantification for lambda
expressions mean that this can now be written using just `='
rather than `= R :- R =':

	map(F, [H|T]) = [F(H) | delay((func) = map(F, force_list(T)))].

I left it as is for the moment for compatibility with Mercury 0.8.
I will add a comment explaining this.

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

I considered something very similar to this while making my change.
You could in fact get away with just passing the closure
`(func) = map(force_list(T))', rather than wrapping delay/1
around the closure and thus passing `delay((func) = map(force_list(T)))'.
In order to make this work you would need to define the type `lazy(T)'
as equivalent to a closure

	:- type lazy(T) == ((func) = T).

and make lazy(T) just a concrete equivalence type rather than an abstract
type.

This implementation of lazy(T) would even be a bit more efficient than the
current implementation, because it avoids an extra level of indirection.
However, although lazy(T) would become more efficient, ((func) = T)
would become a little less efficient, because doing this would require
the implementation to ensure that all closures of this type are not stored
in ROM, and that all closures of this type occupy enough storage to hold
at least one curried argument.

So in general, I think that putting this equivalence in the interface would
overconstrain the implementation, both of lazy(T) and of `((func) = T)'.
I prefer the current design with lazy(T) as an abstract type, because it
gives the implementation more flexibility.  The syntactic cost of calling
`delay' rather than using a closure directly is pretty small and so I think
this is a worthwhile price to pay for the additional implementation
flexibility.

Another disadvantage is that making lazy(T) an equivalence type rather than
a concrete type would probably make it harder to give good error messages
for the case when you forget to insert a call to `force' or `delay'.

If we wanted to provide nicer syntax, a better idea IMHO would be to provide
`lazy <expression>' as syntactic sugar for `delay((func) = <expression>)'.

This is of course very similar to your suggestion of using `func <expression>',
although I think you probably meant just passing the closure directly,
rather than having `func <expression>' be special syntactic sugar.
Still, if lazy(T) remains a different type than ((func) = T), as I argue
it should, then if we are to add special syntax for values of this type,
I'd say we should use `lazy' rather than `func' for the keyword.

However, I think it is not worth adding that syntactic sugar yet.
Currently we're not even going to put the lazy module in the standard
library, and it would make little sense to add special syntax for something
that is not even part of the standard library.

Cheers,
	Fergus.

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