Continuation-passing style

In continuation- passing style ( CPS for short ) refers to a style of programming in which the control flow is controlled exclusively by continuations. Continuations are functions that represent the remaining calculations. In place of the function return occurs, the call of the passed continuation, of programs in continuation- passing style.

In most programming languages, their results and the control flow is returned to the caller after the end of a function. This is referred to as a direct style, direct style, the delineation of CPS. It is also possible the function to pass a successor function to get the result instead of the caller. Instead of returning to the caller, the function returns its result this successor function. The functions in a sense form a chain. Instead of a follow-up function can also speak of a " continuation ", the German word for continuation. The CPS is a programming style that follows this procedure.

CPS makes the necessary in many languages ​​stack to store the return address when calling a method obsolete. This makes it possible to implement a programming language without a stack ( stackless ). As on many systems, the stack size is limited, without CPS also the maximum recursion depth limited, which can be a problem under certain circumstances. CPS, it is possible to circumvent this limitation. An example is Stackless Python.

Many compilers logical and functional programming languages ​​use CPS as an internal representation of a program, since it makes it easier to draw conclusions about the program, simplifying optimizations.

To transform a direct- style language such as JavaScript in CPS, causes (if the compiler no Tail Call Optimization support ) that sooner or later overflows the stack, as an abandoned by calling a continuation does not shut down on their "official" way is, and thus the stack entry is not cleared. If exceptions are available, but it is possible to achieve a certain recursion depth to grab the current continuation in an exception and throw it. The winds from the stack, and at the upper end of the chain of function calls waiting an exception handler that calls the packaged continuation. In this way, for example, implemented flapjax a CPS transformation of JavaScript code.

Example

The following JavaScript function computes the factorial of its argument. The result of the Rekursionsaufrufs is further used:

Function factorial ( n ) {      if ( n === 0) return 1;      return n * factorial ( n - 1); } This continuation can also be assumed by a function that is passed to the factorial function:

Fakultaet_cps function (n, k ) {      if ( n === 0 ) return k (1);      return fakultaet_cps (          n - 1,          function ( interim result ) {              return k (n * between result);          }); } To evaluate the factorial function you give it as a continuation the identity function:

Identity function (x ) {return x; } fakultaet_cps (5, identity); / / Results in 120 The factorial function could also have been called in an environment in which their result is to be doubled:

2 * factorial ( 5) In the CPS assumes the continuation:

Fakultaet_cps (5, function ( x ) {return 2 * x; }) literature

  • Daniel P. Friedman, Mitchell Wall: Essentials of Programming Languages ​​. The MIT Press, 2008, ISBN 0,262,062,798th
201177
de