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.
|Published (Last):||20 October 2008|
|PDF File Size:||7.66 Mb|
|ePub File Size:||6.18 Mb|
|Price:||Free* [*Free Regsitration Required]|
If you’re new to continuation-passing style, I recommend my earlier post on continuation-passing style by example.
Cpmpiling calls become tail calls, so in effect, there is no stack. When a continuation gets invoked, deallocate its space by resetting the stack pointer to that continuation. 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: The transform now has three principal functions: The goal of this article is to introduce CPS transforms in small, individually digestible pieces before stitching them back together as a unified whole.
The wrinkle in the previous transform was that it forced function application to bind its function and its arguments to variables, even if they were already atomic. Appel’s Compiling with Continuations and Queinnec’s Lisp in Small Pieces are invaluable resources for the functional compiler writer. It is the transformation that newcomers often discover for themselves.
My post on implementing exceptions. Complex expressions may not terminate, and they may produce side effects.
Atomic expressions always produce a value and never cause side effects. In compiping of unreasonable effectiveness, the transformation to continuation-passing style CPS ranks with the Y combinator.
How to compile with continuations
My post on A-Normalization. T ‘ g a ‘halt produces: In this transformation, we have two functions, M and T: In the function-application transform, the values of both the function and the argument have to be converted into CPS.
Yet, if the transform tags variables, call forms and lambdas as being user or continuationthe stack is recoverable. This transformation is not hygienic ; if the continuation c references any of the ; bound variables! Knowing how to convert code into CPS, either by hand or algorithmically, is a powerful weapon in the programmer’s arsenal. Fortunately, the hybrid CPS transform readily adapts to features like basic values, conditionals, side effects, sequencing and explicit recursion.
The transformation of function application is the main culprit: Code is available in Racket ; techniques applicable to any language. For example, the following: When a continuation gets allocated, bump the stack pointer. 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.
How to compile with continuations
A hybrid transform Combining the naive and higher-order transforms provides the best of both worlds. The transform converts each with Tand then catches continyations results in newly-created continuations.
Scaling to real language features The lambda calculus makes a nice platform for studying the architecture of a program transformation. This simple compilling in perspective is economical: The lambda calculus makes a nice platform for studying the architecture of a program transformation.
The naive transformation The naive transformation likely dates to Plotkin’s earliest work. The expression T expr cont might be read “the transformation of expr into continuation-passing style, such that cont will be invoked on its result. Because continuations are used in a last-allocated, first-invoked fashion, we can implement them as a stack. 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.
In the higher-order transform, the function T: To generate a fresh variable bound to a user value, the transform continuatiosn use genusymand for a fresh ckntinuations bound to a continuation, the transform will use genksym: For the first three continuafions, the input language is the lambda calculus: Danvy, Millikin and Nielsen have been able to connect some of these methods, including the well-known treatments in Appel’s Compiling with Continuations and Queinnec’s Lisp in Small Pieces.
Compiling with Continuations
Consider an expanded input language: Examples Even while this transformation is simple, its results are poor. This is two steps forward, and one step back: For the fourth transform, it will become partitioned CPS, and for the final transform, it will be appek more realistic intermediate language with side effects, conditionals, basic values and explict recursion.
We can even use the stack pointer register. Ultimately, however, that transformation must run on real code.
Both of those lambda terms are continuations. How to compile with continuations [ article index ]  [ mattmight ] [ rss ]. If the transform receives a real function expecting the atomic version of a the supplied expression, then the transform can check whether continuatoins is necessary to bind it to a variable.
To start, split the grammar: