Cambridge University Press, Appel, Andrew W., Compiling with continuations / Andrew W. Appel. p. 25 cm. Includes bibliographical references. Then, during CPS transformation, continuations desugar into functions. methods, including the well-known treatments in Appel’s Compiling with Continuations. This book shows how continuation-passing style is used as an intermediate representation to perform optimizations and program transformations. Continuations.

Author: Virn Malarisar
Country: Central African Republic
Language: English (Spanish)
Genre: Marketing
Published (Last): 27 March 2013
Pages: 66
PDF File Size: 10.25 Mb
ePub File Size: 9.74 Mb
ISBN: 735-2-55344-145-9
Downloads: 60512
Price: Free* [*Free Regsitration Required]
Uploader: Dalmaran

In the function-application transform, the values of both the function and the argument have to be converted into CPS. In terms of unreasonable effectiveness, the transformation to continuation-passing style CPS ranks with compjling Y combinator.

How to compile with continuations

The transformation for letrec is not hygienic, because the transformation can introduce the letrec ‘d bindings into the scope of the continuation that gets passed to the transformer. A hybrid transform Combining the naive and higher-order transforms provides the best of both worlds.

We can even use the stack pointer register. Continuatios the transform receives a real function expecting the atomic version of a the supplied expression, then the transform can check whether it is necessary to bind it to a variable. Yet, if the transform tags variables, call forms and lambdas as being user or continuationthe stack is recoverable.

To start, split the grammar: My post on A-Normalization.

Fortunately, the hybrid CPS transform readily adapts to features like basic values, conditionals, side effects, sequencing and explicit recursion. Atomic expressions always produce a value and never cause side effects. Both of those lambda terms are continuations.


Examples Even while this transformation is simple, its results are poor.

The transformation of function application is the main culprit: There are appell advantages [and disadvantages] to stackless compilation. Code is available in Racket ; techniques applicable to any language.

Danvy, Millikin and Nielsen have been able to connect some of these methods, including the well-known treatments in Appel’s Compiling compilijg Continuations and Queinnec’s Lisp in Small Pieces. T ‘ g a ‘halt produces: How to compile with continuations [ article index ] [] [ mattmight ] [ rss ].

Because continuations are used in a last-allocated, first-invoked fashion, we can implement them as a stack. During compilation, high-level control constructs ranging from coroutines and exceptions to while loops and break statements steadily desugar into a mixture of two constructs: Ultimately, however, that transformation must run on real code.

If you’re using this in practice, alphatize the program first, or modify letrec to bind the continuation to a variable outside the scope of the letrec. Knowing how to convert code into CPS, either by hand or algorithmically, is a powerful weapon in the programmer’s arsenal.

When a continuation gets allocated, bump the stack pointer.

To generate a fresh variable bound to a user value, the transform will use genusymand for a fresh variables bound to a continuation, the transform will use genksym: The M function only has to watch for lambda terms. The goal of this article is to introduce CPS transforms in small, individually digestible pieces before stitching them back together as a unified whole.

Complex expressions may not terminate, and they may produce side effects.


Contonuations is two steps forward, and one step back: When a continuation gets invoked, deallocate its space by resetting the stack pointer to that continuation. The naive transformation The naive transformation likely dates to Plotkin’s earliest work. The transform now has three principal functions: The transform converts each with Tand then catches their results in newly-created continuations. Consider an expanded input language: The transform T expr cont will transform expr into a CPS value, and then construct a call site that applies the term cont to that value:.

For example, the following: Continuation-passing style If you’re new to continuation-passing style, I recommend my earlier post on continuation-passing style by example. For the first three transforms, the input language is the lambda calculus: This transformation is not hygienic ; if the continuation c references any of the ; bound variables!

How to compile with continuations

The expression T expr cont might conrinuations read “the transformation of expr into continuation-passing style, such that cont will be invoked on its result. My post on implementing exceptions.

This simple shift in perspective is economical: If you’re new to continuation-passing style, I recommend my earlier post on continuation-passing style by example.