Continuation

Die Continuation ist ein abstraktes Konzept höherer, insbesondere funktionaler Programmiersprachen. Er bezeichnet den Kontrollzustand eines Programms zu einem bestimmten Zeitpunkt zu dessen Laufzeit. Der Begriff Continuation entspricht daher näherungsweise dem Konzept des Prozesskontexts, allerdings schließt der Prozesskontext den aktuellen Zustand der Programmdaten, also z. B. die Werte lokaler und globaler Variablen mit ein.

Zugriff auf Continuations ermöglicht es, den Kontrollfluss eines Programmes beliebig zu beeinflussen. So wird es möglich, ein Programm zu einem beliebigen Zeitpunkt anzuhalten und später fortzusetzen, oder das Programm an einer bestimmten Stelle in einen früheren Zustand zurückzuversetzen. Diese Eigenschaft kommt auch im Namen Continuation, zu deutsch Fortsetzung zum Ausdruck. Unter Verwendung von Continuations ist jede Art von Schleife simulierbar. Der uneingeschränkte Zugriff auf die Continuation sowie eine Form einer bedingten Anweisung reichen bereits aus, um beliebige berechenbare Probleme zu lösen. Diese Fähigkeit ermöglicht einen eigenen Programmierstil, den sog. continuation-passing style.

Verschiedene Programmiersprachen unterstützen den Umgang mit Continuations, die bekanntesten Vertreter dabei sind verschiedene Lispdialekte wie Scheme. Moderne objektorientierte Sprachen bieten mit Konzepten wie Ausnahmebehandlung eingeschränkte Möglichkeiten, auf die Continuation eines Programms zuzugreifen.

Beispiele

Endliche Automaten

In der Automatentheorie, einem Teilbereich der theoretischen Informatik, ist ein wesentliches theoretisches Konstrukt der endliche Automat. Dieser befindet sich zu jedem Zeitpunkt in einem aus einer endlichen Menge möglicher Zustände. Dieser Zustand kann als die Continuation zum jeweiligen Zeitpunkt interpretiert werden.

Moderne Mikroprozessoren

Moderne Mikroprozessoren sind meist Registermaschinen. Auf einer solchen Registermaschine stellt der Inhalt bestimmter Register zu einem gegebenen Zeitpunkt die Continuation des ausgeführten Prozesses zum jeweiligen Zeitpunkt dar. Moderne Prozessoren machen sich dies zunutze, um zwischen mehreren Prozessen hin- und herzuschalten und so den Eindruck zu erwecken, dass diese gleichzeitig ausgeführt werden. Steht ein solcher Kontextwechsel an, so sichert der Prozessor den Inhalt aller Register. Anschließend füllt er die Register mit Inhalten, die zu einem früheren Zeitpunkt aus den Registern gesichert wurden. Damit wird der Prozess, der zum Zeitpunkt des Sicherns aktiv war, an genau der Stelle fortgesetzt, an welcher er sich zum Zeitpunkt der Sicherung befand. Die Continuation wird hierbei durch den Befehlszähler, zusammen mit dem Inhalt des Aufrufstapels bzw. den Inhalt des Stapelzeigers, repräsentiert.

Continuations in Scheme

Scheme behandelt Continuations als First-Class-Objekte, d. h. Scheme macht es nicht nur möglich, auf die aktuelle Continuation zuzugreifen, sondern auch, diese Continuation in beliebigen Variablen abzulegen und Funktionen als Parameter zu übergeben. Scheme bietet dazu die Funktion call/cc. Der folgende Code implementiert die Fakultät mittels Continuations:

(define fac (lambda (x)
  (let ((a 1)
        (cont #f))
    (call/cc (lambda (k) (set! cont k) #t))
    (cond
      ((< x 2) a)
      (else
        (set! a (* a x))
        (set! x (- x 1))
        (cont))))))

Hierbei wird der Funktion call/cc eine anonyme Funktion übergeben. call/cc ruft diese Funktion mit der aktuellen Continuation auf, die anonyme Funktion speichert diese Continuation in der Variablen cont. In der letzten Zeile wird mittels (cont) die Continuation aufgerufen, der Programmfluss springt daher zu der Anweisung hinter dem Aufruf von call/cc.

Siehe auch

Continuation-Passing Style

Literatur

Christian Queinnec: Lisp in Small Pieces. Cambridge University Press, 1994, ISBN 0-521-54566-8.