[m-dev.] Laziness modules

[Paul Bone]

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
<http://www.cs.mu.oz.au/research/mercury/mailing-lists/mercury-developers/mercury-developers.200905/0000.html>
< 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 
         library.
< 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
         e.g.
<http://homepages.inf.ed.ac.uk/wadler/topics/language-design.html#lazyinstrict>
< 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
       "tail-calls"
< 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...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://lists.mercurylang.org/archives/developers/attachments/20090601/099b889e/attachment.sig>