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):||19 May 2012|
|PDF File Size:||19.41 Mb|
|ePub File Size:||14.7 Mb|
|Price:||Free* [*Free Regsitration Required]|
In the function-application transform, the values of both the function and the argument have to be converted into CPS. If you’re new to continuation-passing style, I recommend my earlier post on continuation-passing style by example.
Compiling with Continuations
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: In this transformation, we have two functions, M and T: When a continuation gets allocated, bump the stack pointer. T ‘ g a ‘halt produces: In the higher-order transform, the function T: Atomic expressions always produce a value and never cause side effects. Consider an expanded input language: Appel’s Compiling with Continuations and Queinnec’s Lisp in Small Pieces are invaluable resources for the functional compiler writer.
For the fourth transform, it will become partitioned CPS, and for the final transform, it will be a more realistic intermediate language with side effects, conditionals, basic values and explict recursion. 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:. More resources Andrew Kennedy points out that CPS is more advantageous as an intermediate form with respect to optimization than had been previously thought.
In terms of unreasonable effectiveness, the transformation to continuation-passing style CPS ranks with the Y combinator. My post on implementing exceptions. Yet, if the transform tags variables, call forms and lambdas as being user or continuationthe stack is recoverable. Complex expressions may not terminate, and they may produce side effects.
For example, the following: Ultimately, however, that transformation must run on real code.
How to compile with continuations
It is the transformation that newcomers often discover for themselves. The transformation for letrec is not hygienic, because the transformation can introduce the letrec ‘d bindings contimuations the scope of the continuation that gets passed compilng the transformer.
Fortunately, the hybrid CPS transform readily adapts to features like basic values, conditionals, side effects, sequencing and explicit recursion. 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. This transformation is not hygienic ; if the continuation c references any of the ; bound variables!
Because continuations are used in a last-allocated, first-invoked fashion, we can implement them as a stack. How to compile with continuations [ apple index ]  [ mattmight ] [ rss ].
The goal of appek article is to introduce CPS transforms in small, individually digestible pieces before stitching them back together as a unified whole. Scaling to real language features The lambda calculus makes a nice platform for studying the architecture of a program transformation. My post on A-Normalization.
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 lambda calculus makes a nice platform for studying the architecture of a program transformation. For the first three transforms, the input language is the lambda calculus: The transform converts each with Tand then catches their results in newly-created continuations.
Code is available in Racket ; techniques applicable to any language. The transform now has three principal cpmpiling Examples Even while this transformation is simple, its results are poor. To start, split the grammar: A hybrid transform Combining the naive and higher-order transforms provides the best of both worlds. Knowing how to convert code into CPS, either by hand or algorithmically, is a powerful weapon in the programmer’s arsenal.
How to compile with continuations
We can even use the stack pointer register. 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 transformation of function application is the main culprit: This compioing two steps forward, and one step back: If 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.
When a continuation gets invoked, deallocate its space by resetting the stack pointer to that continuation.
There are some advantages [and disadvantages] to stackless compilation. 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.