Continuation-Passing Style

Unter Continuation-Passing Style (kurz CPS) versteht man einen Programmierkonzept, bei dem der Kontrollfluss ausschließlich durch Continuations gesteuert wird. Continuations sind Funktionen, die die verbleibenden Berechnungen repräsentieren. An die Stelle der Funktionsrückkehr tritt bei Programmen im Continuation-Passing Style der Aufruf der übergebenen Continuation.

In den meisten Programmiersprachen werden nach Beendigung einer Funktion ihr Ergebnis und der Kontrollfluss an den Aufrufer zurückgegeben. Zur Abgrenzung von CPS wird dies als direkter Stil, direct style, bezeichnet. Es ist aber auch möglich, der Funktion eine Nachfolgefunktion zu übergeben, die an Stelle des Aufrufers das Ergebnis erhalten soll. Anstatt zum Aufrufer zurückzukehren, übergibt die Funktion ihr Ergebnis dieser Nachfolgefunktion. Die Funktionen bilden gewissermaßen eine Kette. Statt von einer Nachfolgefunktion kann man auch von einer „Fortführung“ sprechen, dem deutschen Wort für Continuation. Der CPS ist ein Programmierstil, der dieser Vorgehensweise folgt.

CPS macht den in vielen Sprachen notwendigen Stack zur Speicherung der Rücksprungadresse beim Aufruf einer Methode überflüssig. Damit ist es möglich, eine Programmiersprache ohne Stack (stackless) zu implementieren. Da auf vielen Systemen die Größe des Stacks begrenzt ist, ist ohne CPS auch die maximale Rekursionstiefe begrenzt, was unter Umständen zum Problem werden kann. Mit CPS ist es möglich, diese Begrenzung zu umgehen. Ein Beispiel hierfür ist Stackless Python.

Viele Compiler logischer und funktionaler Programmiersprachen verwenden CPS als interne Repräsentation eines Programmes, da er es erleichtert, Schlüsse über das Programm zu ziehen, und damit Optimierungen vereinfacht.

Eine direct-style-Sprache wie JavaScript in CPS zu transformieren, führt (sofern der Compiler keine Tail Call Optimization unterstützt) dazu, dass früher oder später der Stack überläuft, da eine durch Aufruf einer Continuation verlassene Funktion nicht über ihren „offiziellen“ Weg beendet wird und somit der Stackeintrag nicht abgeräumt wird. Wenn Exceptions verfügbar sind, ist es aber möglich, beim Erreichen einer bestimmten Rekursionstiefe die aktuelle Continuation in eine Exception zu packen und diese zu werfen. Das wickelt den Stack ab, und am oberen Ende der Kette von Funktionsaufrufen wartet ein Exceptionhandler, der die verpackte Continuation aufruft. Auf diese Weise implementiert beispielsweise flapjax eine CPS-Transformation von JavaScript-Code.

Beispiel

Die folgende JavaScript-Funktion berechnet die Fakultät ihres Arguments. Das Ergebnis des Rekursionsaufrufs wird dabei weiterverwendet. Nachfolgend steht ein Aufrufbeispiel:

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

    return number * factorial(number - 1);
}

factorial(5); // ergibt 120

Diese Fortführung kann auch durch eine Funktion übernommen werden, die der Fakultätsfunktion übergeben wird:

function factorial_cps(number, callback) {
    if (number === 0)
        return callback(1);

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

Zur Auswertung der Fakultätsfunktion übergibt man ihr als Continuation die Identitätsfunktion:

function identity(number) {
    return number;
}

factorial_cps(5, identity); // ergibt 120

Die Fakultätsfunktion könnte aber auch in einer Umgebung aufgerufen worden sein, in der ihr Ergebnis noch verdoppelt werden soll:

2 * factorial(5);

Im CPS übernimmt das die Continuation:

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

Literatur

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

Weblinks

• flapjax – ein Compiler der JavaScript-Code in CPS transformiert
• Andrew Kennedy Compiling with Continuations, Continued. (PDF; 240 kB) ICFP 2007.
• Guy Lewis Steele, Jr.: Debunking the ‘Expensive Procedure Call’ Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO. (PDF; 951,34 KB) MIT AI Lab. AI Lab Memo AIM-443. Oktober 1977