Recycling Continuations

Recycling Continuations, Jonathan Sobel and Daniel P. Friedman. ICFP 1998

If the continuations in functional data-structure-generating programs are made explicit and represented as records, they can be "recycled." Once they have served their purpose as temporary, intermediate structures for managing program control, the space they occupy can be reused for the structures that the programs produce as their output. To effect this immediate memory reclamation, we use a sequence of correctness-preserving program transformations, demonstrated through a series of simple examples. We then apply the transformations to general anamorphism operators, with the important consequence that all finite-output anamorphisms can now be run without any stack- or continuation-space overhead.

This is a fun paper, and exactly the kind of thing I find addictive: it uses some elegant theory to formalize and systematize a clever hackerly trick.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I've been looking for this paper.

I read this a long time ago but I could never think up the name again or a good set of keywords to stick in Google.