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@googlemail.com> wrote:
On 8 November 2010 13:28, Simon Marlow <
marlowsd@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).
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