[m-dev.] Laziness modules
pbone at csse.unimelb.edu.au
Mon Jun 1 16:16:43 AEST 2009
On Tue, May 05, 2009 at 05:04:53PM +1000, Ralph Becket wrote:
> I put a couple of modules providing support for lazy computation
> together at the weekend. Is there any interest in adding these to the
> library? Laziness gives us what in the C# and Java worlds they call
> "enumerables" and are using to good effect.
In the Mercury IRC channel (yes there is one, #mercury on irc.freenode.net) the following discussion occured.
* ski wonders why the lazy lists shown on the developers mailing-list are in the odd style
< ski> Laziness modules
< Boney> ski: how do you mean "in the old style".
< Boney> BTW, it looks like the lazy evaluation module in the extras package will move into the standard
< Boney> and perhaps I'll come along and make it thread safe.
< ski> Boney : "odd style", not "old style" :)
< ski> "odd" in the sense of "How to add laziness to a strict language,
without even being odd" by Philip Wadler,Walid Taha,David MacQueen at
< ski> also a potentially useful/relevant source is "SRFI 45: Primitives for
expressing iterative lazy algorithms" at
<http://srfi.schemers.org/srfi-45/srfi-45.html>, giving alternative
primitives for lazy suspensions, that allows the expression of
iterative lazy recursive processes (it might be this only matters for
the "even" style, i'm not sure)
< ski> in "odd style", each recursive substructure (tail, child tree, et.c.)
is wrapped in a suspension
< ski> in "even style", every constructor is wrapped in a suspension
(including the top-level one)
< Boney> ah,
< ski> e.g. if one considers a lazy list in "even style", with elements that
are expensive to compute, even the first element is delayed until and
unless it is asked for
< Boney> ic. so lazy list should be..
< Boney> lazy_list(T) ---> lazy(list(T))
< Boney> but then I have to evaluate two thunks if I want to find cons.
< Boney> err, car.
< ski> no
< ski> :- type lazy_list(T) == lazy(lazy_list_cell(T)).
< Boney> I can see I'm going to have to read the references..
< ski> :- type lazy_list_cell(T) ---> empty_lazy_list
< ski> ; cons_lazy_list(T,lazy_list(T)).
< ski> just as before, each tail is wrapped in a suspension
< Boney> ah,
< ski> only now, each "top-level" lazy list cell is also wrapped in a suspension
< Boney> that makes sense.
< ski> but istr Wadler et al. explains the ideas quite well, so you should
read the paper too :)
< Boney> certainly for the motivation of why this is good.
< Boney> your second link talks about space leaks. (I just skimmed it).
< ski> yes
ski goes on to explain the space leak..
< ski> the primitives in the module on the mailing list are
< ski> :- func susp((func) = T) = lazy(T).
< ski> :- func value(lazy(T)) = T.
< ski> with
< ski> :- func lazy(T) = lazy(T).
< ski> as an optimization
< ski> (in SRFI 45, these are called `delay' (more or less) and `force')
< ski> the space leak occurs because in certain cases (e.g. `filter') a nested
alternating sequence of `value' and `susp' (`value(susp((func) =
value(susp((func) = ...))))') may be built up, in what ought to be
< ski> the fix is to replace `susp' with a variant of it
< ski> :- func susp_value((func) = lazy(T)) = lazy(T).
< ski> (this is called `lazy' in that reference)
< ski> and to also include the `lazy' from above as primitive
< ski> (i'm not married to these names. just tried to use whatever Ralph
already used, for exposition)
< Boney> yep.
ski is not currently subscribed to the mailing lists and therefore didn't post this there.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 197 bytes
Desc: Digital signature
More information about the developers