Continuation-passing style

Unter Continuation-Passing Style (kurz CPS) versteht man einen Programmierstil, 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 wird 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 dazu (sofern der Compiler keine Tail Call Optimization unterstützt), 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:

function fakultaet(n) {
    if (n === 0) return 1;
    return n * fakultaet(n - 1);
}

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

function fakultaet_cps(n, k) {
    if (n === 0) return k(1);
    return fakultaet_cps(
        n - 1, 
        function(zwischenergebnis) { 
            return k(n * zwischenergebnis); 
        });
}

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

function identity(x) { return x; }
fakultaet_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 * fakultaet(5)

Im CPS übernimmt das die Continuation:

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

Literatur

• Daniel P. Friedmann, Mitchell Wand: Essentials of Programming Languages. The MIT Press, 2008, ISBN 0262062798.

Weblinks

• flapjax, ein Compiler der JavaScript-Code in CPS transformiert
• Compiling with Continuations, Continued, Andrew Kennedy. ICFP 2007. (PDF-Datei; 240 kB)
• Guy Lewis Steele, Jr.. “Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO”. MIT AI Lab. AI Lab Memo AIM-443. October 1977 (PDF-Datei; 1,88 MB)