Fortsetzung - Continuation

Für andere Verwendungen siehe Fortsetzung (Begriffsklärung) .

In der Informatik ist eine Fortsetzung eine abstrakte Darstellung des Steuerungszustands eines Computerprogramms . Eine Fortsetzung implementiert ( verifiziert ) den Programmsteuerungszustand, dh die Fortsetzung ist eine Datenstruktur, die den Rechenprozess an einem gegebenen Punkt in der Ausführung des Prozesses repräsentiert; auf die erstellte Datenstruktur kann von der Programmiersprache zugegriffen werden, anstatt in der Laufzeitumgebung versteckt zu sein . Fortsetzungen sind nützlich, um andere Kontrollmechanismen in Programmiersprachen wie Exceptions , Generatoren , Coroutinen usw. zu codieren .

Die " aktuelle Fortsetzung " oder "Fortsetzung des Berechnungsschritts" ist die Fortsetzung, die aus Sicht des laufenden Codes vom aktuellen Punkt in der Ausführung eines Programms abgeleitet würde. Der Begriff Fortsetzungen kann auch verwendet werden, um sich auf erstklassige Fortsetzungen zu beziehen , das sind Konstrukte, die einer Programmiersprache die Möglichkeit geben, den Ausführungszustand an jedem Punkt zu speichern und zu einem späteren Zeitpunkt im Programm möglicherweise mehrmals zu diesem Punkt zurückzukehren.

Geschichte

Die früheste Beschreibung der Fortsetzungen stammt von Adriaan van Wijngaarden im September 1964. Wijngaarden sprach auf der IFIP-Arbeitskonferenz zu formalen Sprachbeschreibungssprachen in Baden bei Wien, Österreich. Als Teil einer Formulierung für einen Algol-60- Präprozessor forderte er eine Transformation der richtigen Prozeduren in den Continuation-Passing-Stil , obwohl er diesen Namen nicht verwendete, und seine Absicht war, ein Programm zu vereinfachen und damit sein Ergebnis klarer zu machen.

Christopher Strachey , Christopher P. Wadsworth und John C. Reynolds haben den Begriff der Fortsetzung in ihrer Arbeit auf dem Gebiet der denotationalen Semantik in den Vordergrund gerückt , die ausgiebig von Fortsetzungen Gebrauch macht, um sequentielle Programme hinsichtlich der Semantik der funktionalen Programmierung zu analysieren .

Steve Russell erfand die Fortsetzung in seiner zweiten Lisp- Implementierung für die IBM 704 , nannte sie jedoch nicht.

Reynolds (1993) gibt eine vollständige Geschichte der Entdeckung von Fortsetzungen.

Erstklassige Fortsetzungen

Erstklassige Fortsetzungen sind die Fähigkeit einer Sprache, die Ausführungsreihenfolge von Anweisungen vollständig zu kontrollieren. Sie können verwendet werden, um zu einer Funktion zu springen, die den Aufruf der aktuellen Funktion erzeugt hat, oder zu einer Funktion, die zuvor beendet wurde. Eine erstklassige Fortsetzung kann man sich als Speichern des Ausführungszustands des Programms vorstellen. Dabei ist zu beachten, dass echte erstklassige Fortsetzungen nicht – anders als ein Prozessabbild – Programmdaten speichern, sondern nur den Ausführungskontext. Dies wird durch die Beschreibung des "Fortsetzungssandwichs" veranschaulicht:

Angenommen, Sie stehen in der Küche vor dem Kühlschrank und denken an ein Sandwich. Du nimmst gleich dort eine Fortsetzung und steckst sie in die Tasche. Dann holt man Truthahn und Brot aus dem Kühlschrank und macht sich ein Sandwich, das nun auf der Theke steht. Du rufst die Fortsetzung in deiner Tasche auf und findest dich wieder vor dem Kühlschrank wieder und denkst an ein Sandwich. Aber zum Glück liegt ein Sandwich auf der Theke, und alle Materialien, aus denen es gemacht wurde, sind weg. Also isst du es. :-)

In dieser Beschreibung ist der Sandwich - Teil der Programmdaten (zB ein Objekt auf dem Heap), und anstatt eine „make Sandwich“ Routine aufrufen und dann zurückkehrte, rief die Person ein „make - Sandwich mit aktuellen Fortsetzung“ Routine, die erstellt das Sandwich und fährt dann dort fort, wo die Ausführung aufgehört hat.

Scheme war das erste vollständige Produktionssystem (1969-1970), das zuerst "catch" und dann call/cc bereitstellte . Bruce Duba führte call/cc in SML ein .

Fortsetzungen sind auch in Modellen der Berechnung einschließlich der verwendeten Denotationelle Semantik , der Schauspieler Modell , Prozess calculi und Lambda - Kalkül . Diese Modelle verlassen sich auf Programmierer oder Semantik-Ingenieure, um mathematische Funktionen im sogenannten Continuation-Passing-Stil zu schreiben . Das bedeutet, dass jede Funktion eine Funktion verbraucht, die den Rest der Berechnung relativ zu diesem Funktionsaufruf darstellt. Um einen Wert zurückzugeben, ruft die Funktion diese "Fortsetzungsfunktion" mit einem Rückgabewert auf; Um die Berechnung abzubrechen, wird ein Wert zurückgegeben.

Funktionale Programmierer, die ihre Programme im Continuation-Passing-Stil schreiben, gewinnen die Ausdruckskraft, den Kontrollfluss auf beliebige Weise zu manipulieren. Der Preis besteht darin, dass sie die Invarianten der Kontrolle und der Fortsetzungen von Hand aufrechterhalten müssen, was ein sehr komplexes Unterfangen sein kann (siehe jedoch unten 'Fortsetzungs-Übergabe-Stil').

Verwendet

Fortsetzungen vereinfachen und verdeutlichen die Implementierung mehrerer allgemeiner Entwurfsmuster , einschließlich Coroutinen / Grüne Threads und Ausnahmebehandlung , indem sie das grundlegende Low-Level-Primitive bereitstellen, das diese scheinbar unverbundenen Muster vereint. Fortsetzungen können elegante Lösungen für einige schwierige Probleme auf hoher Ebene bieten, z. B. die Programmierung eines Webservers, der mehrere Seiten unterstützt, auf die über die Vorwärts- und Zurück-Schaltflächen und über das Folgen von Links zugegriffen wird. Das Smalltalk Seaside- Webframework verwendet Fortsetzungen mit großer Wirkung und ermöglicht es, den Webserver im prozeduralen Stil zu programmieren, indem beim Seitenwechsel die Fortsetzungen gewechselt werden.

Es gibt auch komplexere Konstrukte, für die "Fortsetzungen eine elegante Beschreibung liefern" . Zum Beispiel in C , longjmp aus der Mitte einer zu springen verwendet werden Funktion zum anderen, sofern die zweite Funktion liegt tiefer im Stapel (wenn es für die erste Funktion auf Rückkehr warten, möglicherweise unter anderem). Andere komplexere Beispiele sind Coroutinen in Simula 67 , Lua und Perl ; Tasklets in Stackless Python ; Generatoren in Icon und Python ; Fortsetzungen in Scala (ab 2.8); Fasern in Rubin (ab 1.9.1); der Backtracking- Mechanismus in Prolog ; Monaden in der funktionalen Programmierung ; und Fäden .

Beispiele

Die Programmiersprache Scheme enthält den Control Operator call-with-current-continuation (abgekürzt als: call/cc), mit dem ein Scheme-Programm den Steuerungsfluss manipulieren kann: 

 (define the-continuation #f)

 (define (test)
   (let ((i 0))
     ; call/cc calls its first function argument, passing
     ; a continuation variable representing this point in
     ; the program as the argument to that function.
     ;
     ; In this case, the function argument assigns that
     ; continuation to the variable the-continuation.
     ;
     (call/cc (lambda (k) (set! the-continuation k)))
     ;
     ; The next time the-continuation is called, we start here.
     (set! i (+ i 1))
     i))

Unter Verwendung des Obigen definiert der folgende Codeblock eine Funktion test, die the-continuationauf den zukünftigen Ausführungsstatus von sich selbst setzt: 

 > (test)
 1
 > (the-continuation)
 2
 > (the-continuation)
 3
 > ; stores the current continuation (which will print 4 next) away
 > (define another-continuation the-continuation)
 > (test) ; resets the-continuation
 1
 > (the-continuation)
 2
 > (another-continuation) ; uses the previously stored continuation
 4

Eine sanftere Einführung in diesen Mechanismus finden Sie unter call-with-current-continuation .

Koroutinen

Dieses Beispiel zeigt eine mögliche Verwendung von Fortsetzungen, um Coroutinen als separate Threads zu implementieren . 

 ;;; A naive queue for thread scheduling.
 ;;; It holds a list of continuations "waiting to run".

   (define *queue* '())

   (define (empty-queue?)
     (null? *queue*))

   (define (enqueue x)
     (set! *queue* (append *queue* (list x))))

   (define (dequeue)
     (let ((x (car *queue*)))
       (set! *queue* (cdr *queue*))
       x))

   ;;; This starts a new thread running (proc).

   (define (fork proc)
     (call/cc
      (lambda (k)
        (enqueue k)
        (proc))))

   ;;; This yields the processor to another thread, if there is one.

   (define (yield)
     (call/cc
      (lambda (k)
        (enqueue k)
        ((dequeue)))))

   ;;; This terminates the current thread, or the entire program
   ;;; if there are no other threads left.

   (define (thread-exit)
     (if (empty-queue?)
         (exit)
         ((dequeue))))

Die oben definierten Funktionen ermöglichen das Definieren und Ausführen von Threads durch kooperatives Multitasking , dh Threads, die die Kontrolle an den nächsten in einer Warteschlange abgeben: 

   ;;; The body of some typical Scheme thread that does stuff:

   (define (do-stuff-n-print str)
     (lambda ()
       (let loop ((n 0))
         (format #t "~A ~A\n" str n)
         (yield)
         (loop (+ n 1)))))

   ;;; Create two threads, and start them running.
   (fork (do-stuff-n-print "This is AAA"))
   (fork (do-stuff-n-print "Hello from BBB"))
   (thread-exit)

Der vorherige Code erzeugt diese Ausgabe: 

 This is AAA 0
 Hello from BBB 0
 This is AAA 1
 Hello from BBB 1
 This is AAA 2
 Hello from BBB 2
 ...

Implementierung

Ein Programm muss Platz im Speicher für die Variablen reservieren, die seine Funktionen verwenden. Die meisten Programmiersprachen verwenden eine Aufrufliste zum Speichern der benötigten Variablen, da sie eine schnelle und einfache Zuweisung und automatische Freigabe von Speicher ermöglicht. Andere Programmiersprachen verwenden dafür einen Heap , der Flexibilität bei höheren Kosten für die Zuweisung und Freigabe von Speicher ermöglicht. Beide Implementierungen haben Vor- und Nachteile im Zusammenhang mit Fortsetzungen.

Unterstützung von Programmiersprachen

Viele Programmiersprachen weisen unter verschiedenen Namen erstklassige Fortsetzungen auf; speziell:

In jeder Sprache, die Closures und richtige Tailcalls unterstützt , ist es möglich, Programme im Continuation-Passing-Stil zu schreiben und call/cc manuell zu implementieren. (Im Continuation-Passing-Stil wird call/cc zu einer einfachen Funktion, die mit lambda geschrieben werden kann .) Dies ist eine besonders häufige Strategie in Haskell , wo es einfach ist, eine "Continuation-Passing- Monade " zu konstruieren (zum Beispiel die ContMonade und ContTMonadentransformator in der mtlBibliothek). Die Unterstützung für richtige Tail-Calls wird benötigt, da im Continuation-Passing-Stil keine Funktion jemals zurückkehrt; alle Anrufe sind Schwanzanrufe.

In der Webentwicklung

Ein Bereich, in dem Fortsetzungen praktisch eingesetzt wurden, ist die Webprogrammierung . Die Verwendung von Fortsetzungen schützt den Programmierer vor der zustandslosen Natur des HTTP- Protokolls. Im traditionellen Modell der Webprogrammierung spiegelt sich der fehlende Zustand in der Programmstruktur wider, was dazu führt, dass Code um ein Modell herum konstruiert wird, das sich nur sehr schlecht zum Ausdrücken von Rechenproblemen eignet. Somit ermöglichen Fortsetzungen Code, der die nützlichen Eigenschaften hat, die mit der Inversion von control verbunden sind , während deren Probleme vermieden werden. Die Umkehrung der Inversion der Kontrolle oder Fortsetzungen versus seitenzentrierte Programmierung ist ein Artikel, der eine gute Einführung in Fortsetzungen bietet, die auf die Webprogrammierung angewendet werden.

Einige der beliebtesten Fortsetzungs-fähigen Webserver sind der Racket Web Server , das UnCommon Web Framework und das Weblocks Web Framework für Common Lisp , das Seaside Framework für Smalltalk , Ocsigen/Eliom für OCaml , Continuity für Perl , Wee für Ruby , Tales Framework für Fantom und das Nagare-Framework für Python , Wt für C++ , MFlow für Haskell . Das Apache Cocoon Web Application Framework bietet auch Fortsetzungen (siehe Cocoon-Handbuch ).

Arten

Die Unterstützung für Fortsetzungen ist sehr unterschiedlich. Eine Programmiersprache unterstützt wiederaufrufbare Fortsetzungen, wenn eine Fortsetzung wiederholt aufgerufen werden kann (auch nachdem sie bereits zurückgekehrt ist). Wiederaufrufbare Fortsetzungen wurden von Peter J. Landin mit seinem J- Operator (für Jump) eingeführt, der den Kontrollfluss zurück in die Mitte eines Prozeduraufrufs verlagern konnte. Wiederaufrufbare Fortsetzungen wurden in der Racket- Sprache auch als "Wiedereinsteiger" bezeichnet . Diese Verwendung des Begriffs "Wiedereinsteiger" kann jedoch leicht mit seiner Verwendung in Diskussionen über Multithreading verwechselt werden .

Eine eingeschränktere Art ist die Escape-Fortsetzung , die verwendet werden kann, um den aktuellen Kontext in einen umgebenden Kontext zu entkommen. Viele Sprachen, die Fortsetzungen nicht explizit unterstützen, unterstützen die Ausnahmebehandlung , die Escape-Fortsetzungen entspricht und für dieselben Zwecke verwendet werden kann. C's setjmp/longjmpsind auch äquivalent: Sie können nur verwendet werden, um den Stapel abzuwickeln. Escape-Fortsetzungen können auch verwendet werden, um die Beseitigung von Rückrufen zu implementieren .

Eine Verallgemeinerung von Fortsetzungen sind abgegrenzte Fortsetzungen . Fortsetzungsoperatoren wie das call/ccErfassen der gesamten verbleibenden Berechnung an einem bestimmten Punkt im Programm und bieten keine Möglichkeit, diese Erfassung abzugrenzen. Begrenzte Fortsetzungsoperatoren beheben dies, indem sie zwei separate Kontrollmechanismen bereitstellen: eine Eingabeaufforderung , die eine Fortsetzungsoperation abgrenzt, und einen Verifikationsoperator wie shiftoder control. Fortsetzungen, die mit begrenzten Operatoren erfasst werden, repräsentieren somit nur einen Ausschnitt des Programmkontexts.

Nachteile

Fortsetzungen sind der funktionale Ausdruck der GOTO- Anweisung, und es gelten die gleichen Vorbehalte. Während sie in einigen Spezialfällen wie der Webprogrammierung eine sinnvolle Option sind, kann die Verwendung von Fortsetzungen zu schwer nachvollziehbarem Code führen. In der Tat, die esoterischen Programmiersprache unlambda beinhaltet Call-mit-Strom-Fortsetzung als eines ihrer Merkmale , nur weil Ausdrücke , die sie „sind in der Regel hoffnungslos schwierig, nach unten zu verfolgen.“ Die folgenden externen Links veranschaulichen das Konzept genauer.

Linguistik

In "Fortsetzungen und die Natur der Quantifizierung" stellte Chris Barker die "Fortsetzungshypothese" vor, die

einige linguistische Ausdrücke (insbesondere QNPs [quantificational noun phrases]) haben Bezeichnungen, die ihre eigenen Fortsetzungen manipulieren.

Barker argumentierte, dass diese Hypothese verwendet werden könnte, um Phänomene wie die Dualität der NP-Bedeutung zu erklären (z "Alice sieht [Bob/jeder]"), Umfangsverschiebung (z. B. dass "ein Regentropfen auf jedes Auto fiel" wird typischerweise eher als als als interpretiert ) und Umfangsmehrdeutigkeit (dass ein Satz wie "jemand hat alle gesehen" mehrdeutig sein kann zwischen und ). Er bemerkte auch, dass diese Idee in gewisser Weise nur eine natürliche Erweiterung von Richard Montagues Ansatz in "The Proper Treatment of Quantification in Ordinary English" (PTQ) ist und schreibt, dass "im Nachhinein eine begrenzte Form des Continuation-Passing istpass klar erkennbar im Kern von Montagues (1973) PTQ-Behandlung von NPs als generalisierte Quantoren".

Inwieweit Fortsetzungen verwendet werden können, um andere allgemeine Phänomene in natürlicher Sprache zu erklären, ist ein Thema der aktuellen Forschung.

Siehe auch

Verweise

Weiterlesen

  • Peter Landin . Ein Bericht zur Verallgemeinerung von Sprüngen und Labels . UNIVAC Systemprogrammierungsforschung. August 1965. Nachgedruckt in Higher Order and Symbolic Computation, 11(2):125-143, 1998, mit einem Vorwort von Hayo Thielecke.
  • Drew McDermott und Gerry Sussman . Das Conniver-Referenzhandbuch MIT AI Memo 259. Mai 1972.
  • Daniel Bobrow : Ein Modell für Kontrollstrukturen für Programmiersprachen für künstliche Intelligenz IJCAI 1973.
  • Carl Hewitt , Peter Bishop und Richard Steiger . Ein universeller modularer Akteursformalismus für künstliche Intelligenz IJCAI 1973.
  • Christopher Strachey und Christopher P. Wadsworth . Fortsetzungen: a Mathematische Semantik für den Umgang mit vollen Sprüngen Technische Monographie PRG-11. Computerlabor der Universität Oxford. Januar 1974. Nachgedruckt in Higher Order and Symbolic Computation, 13(1/2): 135–152, 2000, mit einem Vorwort von Christopher P. Wadsworth.
  • John C. Reynolds . Definitional Interpreters for Higher-Order Programming Languages Proceedings of 25th ACM National Conference, S. 717–740, 1972. Nachgedruckt in Higher-Order and Symbolic Computation 11(4):363-397, 1998, mit einem Vorwort.
  • John C. Reynolds. Zum Verhältnis von Direkt- und Fortsetzungssemantik Proceedings of Second Colloquium on Automaten, Languages ​​and Programming. LNCS-Vol. 14, S. 141–156, 1974.
  • Reynolds, John C. (1993). "Die Entdeckungen der Fortsetzungen" (PDF) . Lisp und symbolische Berechnung . 6 (3/4): 233–248.
  • Gerald Sussman und Guy Steele . SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, Dezember 1975. Nachgedruckt in Higher-Order and Symbolic Computation 11(4):405-439, 1998, mit einem Vorwort.
  • Robert Hieb , R. Kent Dybvig , Carl Bruggeman . Representing Control in Presence of First-Class Continuations Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, S. 66–77.
  • Will Clinger , Anne Hartheimer , Eric Ost . Implementation Strategies for Continuations Proceedings of the 1988 ACM Conference on LISP and Functional Programming, S. 124-131, 1988. Zeitschriftenversion: Higher-Order and Symbolic Computation, 12(1):7-45, 1999.
  • Christian Queinnec . Inverting back the Inversion of Control oder, Fortsetzungen versus seitenzentrierte Programmierung SIGPLAN Notices 38(2), S. 57–64, 2003.

Externe Links