Why is there a space leak here?

Mark Tullsen tullsen@cs.yale.edu
Tue, 05 Jun 2001 18:18:01 -0400

"Steinitz, Dominic J" wrote:
> I'd love it if someone could write a tutorial paper on space
> leaks. 

I agree that would be very useful.

> Even with the explanations that have been provided, I find it
> difficult to understand why expressions get evaluated in a
> particular order and why garbage collections happen at a given
> point.

In my "traces" I did the garbage collections as soon as possible, basically
removing unused let bindings.  

The ordering of evaluations is a bit more tricky ...  I would
recommend becoming familiar with the various call-by-need calculi.
For me, it was more intuitive than trying to understand what's going
on at some lower level (such as the STG Machine) and then relate that
lower level to my program.  With call-by-need calculi you can
understand what's going on at the source level.  Here's a starting

  The Call-by-Need Lambda Calculus,
  POPL 95, Ariola, Felleisen, Maraist, Odersky, & Wadler

  author = "John Maraist and Martin Odersky and Philip Wadler", 
  title = "The Call-by-Need Lambda Calculus", 
  journal = "Journal of Functional Programming", 
  volume = 8, 
  number = 3, 
  month = may, 
  year = 1998, 
  publisher = "Cambridge University Press", 

- Mark