Continuation-Passing Style

from Wikipedia, the free encyclopedia

Under continuation-passing style (short CPS ) is defined as a programming style in which the control flow exclusively by continuations is controlled. Continuations are functions that represent the remaining calculations. In the case of programs in continuation-passing style, the function return is replaced by the call of the passed continuation.

In most programming languages, after a function has ended, its result and the control flow are returned to the caller. To delimit CPS this is as a direct style, direct style , called. However, it is also possible to pass a successor function to the function that is to receive the result instead of the caller. Instead of returning to the caller, the function passes its result to this successor function. The functions form a chain, so to speak. Instead of a successor function, one can also speak of a “continuation”, the German word for continuation . The CPS is a style of programming that follows this approach.

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

Many compilers of logical and functional programming languages ​​use CPS as the internal representation of a program, as it makes it easier to draw conclusions about the program and thus simplifies optimization.

Transforming a direct-style language such as JavaScript into CPS (if the compiler does not support Tail Call Optimization) leads to the stack overflowing sooner or later, since a function left by calling a continuation does not end via its "official" route and thus the stack entry is not cleared. If exceptions are available, however, it is possible to pack the current continuation into an exception and throw it when a certain recursion depth is reached. This handles the stack, and at the top of the chain of function calls there is an exception handler that calls the packaged continuation. In this way, for example, flapjax implements a CPS transformation of JavaScript code.

example

The following JavaScript function calculates the factorial of its argument. The result of the recursion call is used further: 

function factorial(number) {
    if (number === 0)
        return 1;
    
    return number * factorial(number - 1);
}

This continuation can also be taken over by a function that is transferred to the faculty function: 

function factorial_cps(number, callback) {
    if (number === 0)
        return callback(1);
    
    return factorial_cps(number - 1, function(value) {
        return callback(number * value);
    });
}

To evaluate the faculty function, the identity function is passed to it as a continuation : 

function identity(number) {
    return number;
}

factorial_cps(5, identity); // ergibt 120

The factorial function could also have been called in an environment in which its result should be doubled: 

2 * factorial(5);

In the CPS this is done by the continuation: 

factorial_cps(5, function(number) {
    return 2 * number;
});

literature

  • Daniel P. Friedmann, Mitchell Wand: Essentials of Programming Languages . The MIT Press, 2008, ISBN 0-262-06279-8 .

Web links