Wadler space leak

[Josef Svenningsson]

Let me clarify a bit exactly how Gustavsson and Sands (I'll refer to them as
GS) handled the issue of the Wadler space leak. It's true that they adopted
an approach similar to Sparud in that they extended their core calculus with
a new language construct which could solve the problem. This is contrast to
Wadler who changed the garbage collector instead, something that GS said
would lead to bad behavior in their calculus.
BUT, GS did not adopt exactly the construct that Sparud suggested. Sparud's
suggestion was to add an updatePat primitive to the language. This was
inspired by how the G-machine work, it had update instructions which where
typically executed after a value was computed. It's a rather bad fit for the
STG-machine which pushes update markers on the stack whenever it starts to
evaluate a thunk. Updates are performed whenever there is an update marker
on the stack when it has computed something to WHNF.
The language construct that GS chose was to have pattern bindings as
primitive in the language. So the code snippet below (taken from Jörgen's
thesis) would be a valid core program. It would not be desugared into case
expressions.
~~~
let (ps,qs) = split ys
in (y:ps,qs)
~~~
The semantics of pattern bindings involves a new kind of update marker
which, in the example above, will update both ps and qs, whenever the 'split
ys' is computed to WHNF. This neatly solves the space leak problem. And it
is a much closer fit to the STG-machine in that uses update markers on the
stack to coordinate the graph reduction.

I think the solution GS chose should work much better for GHC than Sparud's
suggestion. But it would no doubt be an invasive change to GHC as Core would
have to be changed to support pattern bindings.

Cheers,

Josef

On Tue, Nov 9, 2010 at 8:58 AM, Duncan Coutts
<duncan.coutts at googlemail.com>wrote:

> On 8 November 2010 13:28, Simon Marlow <marlowsd at gmail.com> wrote:
> >
> > There's another approach in Jan Sparud's paper here:
> >
> > http://portal.acm.org/citation.cfm?id=165196
> >
> > although it's not clear that this interacts very well with inlining
> either,
> > and it has a suspicious-looking side-effecting operation.  It also looks
> > like it creates a circular reference between the thunk and the selectors,
> > which might hinder optimisations, and would probably also make things
> slower
> > (by adding extra free variables to the thunk).
>
> This proposal is mentioned favourably by Jörgen Gustavsson David Sands
> in [1] (see section 6, case study 6). They mention that there is a
> formalisation in Gustavsson's thesis [2]. That may say something about
> inlining, since that's just the kind of transformation they'd want to
> show is a space improvement.
>
> [1]: Possibilities and Limitations of Call-by-Need Space Improvement (2001)
>      http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.8.4097
>
> [2]: Space-Safe Transformations and Usage Analysis for Call-by-Need
> Languages (2001)
>      (which I cannot immediately find online)
>
> Duncan
> _______________________________________________
> Glasgow-haskell-users mailing list
> Glasgow-haskell-users at haskell.org
> http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20101109/7a79af58/attachment.html