Was ist Call / cc?

Question

Ich habe mehrmals versucht, das Konzept der Fortsetzungen zu erfassen und Anruf / cc . Jeder einzelne Versuch war ein Fehlschlag. Kann jemand mir bitte, diese Konzepte erklären, idealerweise mit realistischen Beispielen als diese auf Wikipedia oder in anderen SO Beiträgen.

Ich habe Hintergrund in Web-Programmierung und OOP. Ich verstehe auch, 6502 Montag und hatte ein kleines randez-vous mit Erlang. Aber noch kann ich nicht meinen Kopf wickeln um Anruf / cc.

Answer 1

Sehen Sie, ich habe diese Weitergeben Stil beste Beschreibung zu diesem Thema rel="nofollow.

Hier ist die Details entkleidet Kopie dieses Artikels:

  

Autor: Marijn Haverbeke   Datum: 24. Juli 2007

     

Schemas des anruf mit Stromfortsetzungs Funktion macht es möglich, eine Berechnung, die einen Zustand des Call-Stack zu erfassen, wie es war, und wieder den gleichen Zustand zu einem späteren Zeitpunkt. Hinzu kommt eine solche primitive, verschiedene Form der Ausnahmebehandlung und C-ähnliche longjmp Tricks umgesetzt werden können.

function traverseDocument(node, func) {
  func(node);
  var children = node.childNodes;
  for (var i = 0; i < children.length; i++)
    traverseDocument(children[i], func);
}   

function capitaliseText(node) {
  if (node.nodeType == 3) // A text node
    node.nodeValue = node.nodeValue.toUpperCase();
}

traverseDocument(document.body, capitaliseText);

     

Dies kann wie folgt transformiert werden: Wir fügen ein zusätzliches Argument für jede Funktion, die verwendet wird, die Funktion der Fortsetzung zu übergeben. Diese Fortsetzung ist ein Funktionswert die Aktionen darstellt, die passieren müssen, nachdem die Funktion ‚zurück‘. Der (Call) Stapel wird in Fortsetzungsübertragungsstil obsolet - wenn eine Funktion eine andere Funktion aufruft, das ist das letzte, was sie tut. Statt für die gerufene Funktion wartet zurückzukehren, bringt es keine Arbeit es will danach in eine Fortsetzung tun, die es an die Funktion übergeben wird.

function traverseDocument(node, func, c) {
  var children = node.childNodes;
  function handleChildren(i, c) {
    if (i < children.length)
      traverseDocument(children[i], func,
                       function(){handleChildren(i + 1, c);});
    else
      c();
  }
  return func(node, function(){handleChildren(0, c);});
}

function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();
  c();
}

traverseDocument(document.body, capitaliseText, function(){});

     

Stellen Sie sich vor uns ein huuuuge Dokument zu nutzen haben. Nur es in einem Rutsch durchqueren dauert fünf Sekunden und fünf Sekunden lang den Browser Einfrieren ist eher schlechter Stil. Betrachten Sie diese einfache Modifikation capitaliseText (nicht die Aufmerksamkeit auf die hässliche globalen bezahlen):

var nodeCounter = 0;
function capitaliseText(node, c) {
  if (node.nodeType == 3)
    node.nodeValue = node.nodeValue.toUpperCase();

  nodeCounter++;
  if (nodeCounter % 20 == 0)
    setTimeout(c, 100);
  else
    c();
}

     

Nun, alle zwanzig Knoten wird die Berechnung für hundert Millisekunden unterbrochen, um dem Browser-Schnittstelle einen Moment auf Benutzereingaben zu reagieren zu geben. Eine sehr primitive Form von Threading -. Sie können sogar mehrere Berechnungen gleichzeitig wie folgt ausführen

     

Eine häufige nützliche Anwendung dieses auf XMLHttpRequests verwendet, oder die verschiedenen IFRAME und SCRIPT-Tag Hacks verwendet, um sie zu simulieren. Diese erfordern immer eine mit irgendeiner Art von Call-Back-Mechanismus zu arbeiten, um die Daten zu verarbeiten, die der Server zurückschickt. In einfachen Fällen wird eine triviale Funktion tun, oder ein paar Globals verwendet werden kann, um den Zustand der Berechnung zu speichern, die wieder aufgenommen werden müssen, nachdem die Daten zurückkommt. Bei komplexen Fällen, zum Beispiel wenn die Daten durch eine Funktion verwendet wird, der muss einen Wert an seinen Aufrufer zurückgeben, Fortsetzungen erheblich vereinfachen Dinge. Sie registrieren nur die Fortsetzung als Rückruf und Ihre Berechnung wieder aufgenommen wird, wenn die Anforderung abgeschlossen ist.

Answer 2

Um es zu C zu vergleichen, ist die aktuelle Fortsetzung wie der aktuelle Zustand des Stapels. Es verfügt über alle Funktionen für das Ergebnis der aktuellen Funktion warten zu beenden, so dass sie die Ausführung wieder aufnehmen. Die Variable als aktuelle Fortsetzungs erfasst wird wie eine Funktion verwendet, mit der Ausnahme, dass es nimmt den Wert bereitgestellt und gibt sie an den Wartestapel. Dieses Verhalten ist ähnlich der C-Funktion longjmp wo können Sie auf unteren Abschnitten des Stapels sofort zurück .

(define x 0) ; dummy value - will be used to store continuation later

(+ 2 (call/cc (lambda (cc)
                (set! x cc)  ; set x to the continuation cc; namely, (+ 2 _)
                3)))         ; returns 5

(x 4) ; returns 6

Ein wesentlicher Unterschied zwischen dem C-Stack und eine Fortsetzung ist, dass eine Fortsetzung an einer beliebigen Stelle im Programm verwendet werden kann, auch wenn der Zustand des Stapels verändert hat. Dies bedeutet, dass Sie im Wesentlichen frühere Versionen des Stapels wiederherstellen und nutzen sie, wieder und wieder, bis zu einem gewissen einzigartigen Programmablauf führt.

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7

  reason: it is because (x 5) replaces the existing continuation,
          (* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
          5 to x, creating (+ 2 5), or 7.

Die Fähigkeit, den Zustand eines Programms zu speichern und wiederherzustellen hat viel gemeinsam mit Multithreading. In der Tat können Sie Ihre eigenen Thread-Scheduler mit Fortsetzungen implementieren, wie ich versucht habe zu zeigen,

Ein triviales Beispiel für die Fortsetzung mit würde einen Thread implementieren (Faser, wenn Sie möchten) Manager auf einer Single-Prozessor-Maschine. Der Scheduler würde unterbricht die Ausführung periodisch fließen (oder, im Fall von Faser, an verschiedenen strategischen Punkten in dem Code aufgerufen werden), speichern Sie den Fortsetzungszustand (entsprechend den aktuellen Thread ), dann Wechsel zu einer unterschiedlichen Fortsetzungszustand (entsprechend einem anderen Thread, dessen Zustand wurde zuvor gespeichert.)

auf Ihre Montag Hintergrund Mit Bezug auf die Fortsetzung Zustand Details wie Befehlszeiger erfassen würde, Register und Stapelkontext (Zeiger) , gespeichert und nach Belieben wieder hergestellt werden.

Eine weitere Möglichkeit, die Fortsetzung der Verwendung wäre denken Verfahren zum Ersetzen Anrufe mit mehreren gewindeartigen Einheiten , dass koexistieren parallel (entweder läuft oder suspendiert), die Steuerung zu jedem anderen Fortsetzung Verwendung Kontexten statt des ‚klassischen‘ call Paradigma. Sie würden arbeiten auf globaler (gemeinsam) Daten, anstatt sich auf Parameter. Dies ist zu einem gewissen Grad flexibler als call in dem Sinne, dass Stapel dann nicht nach unten aufzuwickeln haben (calls sind verschachtelt ), aber Steuerung kann um beliebig weitergeben.

dieses Konzept zu visualisieren Der Versuch, in einer Sprache wie C, sich vorstellen, mit einer einzigen switch(continuation_point) { case point1: ... } Aussage eine große Schleife hat, wobei jede case auf eine Continuation-Sicherungspunkt entspricht, und in dem der Code innerhalb jedes case kann den Wert von continuation_point verändern und zu diesem continuation_point Kontrolle verzichten, indem aus dem break switching und die nächsten Iteration in der Schleife eingreifen.

Was ist der Kontext Ihrer Frage? Irgendwelche speziellen Szenarien Sie sind interessiert? Eine bestimmte Programmiersprache? Ist der Faden / Faser Beispiel über ausreichend?

Die Sache, die mir geholfen haben, ist die Idee, dass mit der Funktion in einer traditionellen Sprache Anrufe, die Sie implizit eine Fortsetzung jederzeit passieren Sie einen Funktionsaufruf zu machen.

zu einer Funktion Code Vor dem Sprung Sie einige Zustand auf dem Stapel speichern (das heißt Sie Ihre Absenderadresse drücken und der Stapel enthält bereits Ihre Einheimischen). Dies ist im Wesentlichen eine Fortsetzung. Wenn die Funktion beendet hat, hat es zu bestimmen, wo die Strömung der Ausführung zu senden. Es nutzt die Fortsetzung auf dem Stapel gespeichert, die Absenderadresse knallend und Springen zu.

Weitere Sprachen diese Idee von Fortsetzungen verallgemeinern so dass Sie explizit angeben, wo die Codeausführung fortzusetzen, anstatt implizit weiter an, von wo aus dem Funktionsaufruf durchgeführt wurde.

EDIT basierend auf Kommentar:

Die Fortsetzung ist der komplette Ausführungszustand. An jedem Punkt der Ausführung können Sie das Programm in zwei Teile aufzuteilen (in der Zeit, nicht Raum) - das, was bis zu diesem Punkt laufen hat, und alles, was von hier laufen los. Die „aktuelle Fortsetzung“ ist das „alles, was von hier läuft los“ (Sie daran denken können wie eine Art von Funktion, die alles tun, um der Rest des Programms getan haben würde). So ist die Funktion, die Sie call/cc liefern wird die Fortsetzung übergeben, die aktuell waren, als call/cc aufgerufen wurde. Die Funktion die Fortsetzung verwenden kann Ausführung an die call/cc Anweisung zurückzukehren (wahrscheinlicher, obwohl es die Fortsetzung um auf etwas anderem passieren würde, denn wenn sie es direkt verwendet könnte es stattdessen eine einfache Rückkehr zu tun).

Als ich versuchte Anruf / cc zu verstehen, fand ich diese Call-mit-Strom-Continuation-für-C-Programmierer Seite wurde hilfreich.

Die beste Erklärung, die ich gesehen habe, ist in Paul Grahams Buch, On Lisp .

Stellen Sie sich Ihr Skript ein Videospielstufe ist. Call / cc ist wie eine Bonus-Stage.

Sobald Sie es berühren Sie die Bonusstufe übertragen werden (das heißt, die Definition der Funktion als Argument übergeben nennen / cc [f in diesem Fall]).

Bonus Stufen unterscheiden sich von gewöhnlichen Stufen , da in der Regel haben sie ein Element (dh das Argument der Funktion aufzurufen, übergeben / cc), dass, wenn Sie es berühren Sie verlieren und werden wieder in der Normalstufe transportiert.

So ist es egal, tut, wenn es viele args sind, wenn Sie einer von ihnen erreichen die über. Also unsere Ausführung erreicht (arg 42) und gibt sie an die Summe (+ 42 10).

Auch gibt es einige Bemerkungen beachtenswert:

• Nicht alle Funktionen können mit Call / cc verwendet werden. Da es erwartet ein Fortsetzung (dh eine Funktion), können Sie keine f wie dieses: (define f (lambda (k) (+ k 42)), denn man kann nicht ein sum Funktion.
• Sie können auch nicht haben (define f (lambda (k) (f 42 10))) weil die Fortsetzung erwartet nur ein Argument.
• Sie können beenden ohne touching jede Ausfahrt, in diesem Fall die Funktion schreitet wie jede gewöhnliche Funktion (z.B. (define f (lambda (k) 42) Oberflächen und liefert 42).

Es gibt mehrere Ebenen zu verstehen Anruf / cc. Zuerst müssen Sie die Bedingungen verstehen und die, wie der Mechanismus funktioniert. Dann wird ein Verständnis davon, wie und wann Anruf / cc ist im „echten Leben“ verwendet Programmierung erforderlich ist.

Die erste Ebene kann durch das Studium CPS erreicht werden, aber es gibt Alternativen.

Für die zweite Ebene empfehle ich die folgenden Klassiker von Friedman.

Daniel P. Friedman. "Anwendungen von Fortsetzungen: Invited Tutorial". 1988 Principles of Programmiersprachen (POPL88). Januar 1988.

Werfen Sie einen Blick auf die Beschreibung und Umsetzung von Call / cc für FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with -continuations.aspx

Das Modell, das ich für verwendete Fortsetzungen von einem imperativ Standpunkt zu verstehen ist, dass es sich um eine Kopie des Call-Stack ist mit dem Zeiger auf den nächsten Befehl kombiniert.

Call / cc ruft eine Funktion (als Argument übergibt) mit der Fortsetzung als Argument.

Answer 3

Answer 4

Answer 5

Ein triviales Beispiel für die Fortsetzung mit würde einen Thread implementieren (Faser, wenn Sie möchten) Manager auf einer Single-Prozessor-Maschine. Der Scheduler würde unterbricht die Ausführung periodisch fließen (oder, im Fall von Faser, an verschiedenen strategischen Punkten in dem Code aufgerufen werden), speichern Sie den Fortsetzungszustand (entsprechend den aktuellen Thread ), dann Wechsel zu einer unterschiedlichen Fortsetzungszustand (entsprechend einem anderen Thread, dessen Zustand wurde zuvor gespeichert.)

auf Ihre Montag Hintergrund Mit Bezug auf die Fortsetzung Zustand Details wie Befehlszeiger erfassen würde, Register und Stapelkontext (Zeiger) , gespeichert und nach Belieben wieder hergestellt werden.

Eine weitere Möglichkeit, die Fortsetzung der Verwendung wäre denken Verfahren zum Ersetzen Anrufe mit mehreren gewindeartigen Einheiten , dass koexistieren parallel (entweder läuft oder suspendiert), die Steuerung zu jedem anderen Fortsetzung Verwendung Kontexten statt des ‚klassischen‘ call Paradigma. Sie würden arbeiten auf globaler (gemeinsam) Daten, anstatt sich auf Parameter. Dies ist zu einem gewissen Grad flexibler als call in dem Sinne, dass Stapel dann nicht nach unten aufzuwickeln haben (calls sind verschachtelt ), aber Steuerung kann um beliebig weitergeben.

dieses Konzept zu visualisieren Der Versuch, in einer Sprache wie C, sich vorstellen, mit einer einzigen switch(continuation_point) { case point1: ... } Aussage eine große Schleife hat, wobei jede case auf eine Continuation-Sicherungspunkt entspricht, und in dem der Code innerhalb jedes case kann den Wert von continuation_point verändern und zu diesem continuation_point Kontrolle verzichten, indem aus dem break switching und die nächsten Iteration in der Schleife eingreifen.

Was ist der Kontext Ihrer Frage? Irgendwelche speziellen Szenarien Sie sind interessiert? Eine bestimmte Programmiersprache? Ist der Faden / Faser Beispiel über ausreichend?

Answer 6

Die Sache, die mir geholfen haben, ist die Idee, dass mit der Funktion in einer traditionellen Sprache Anrufe, die Sie implizit eine Fortsetzung jederzeit passieren Sie einen Funktionsaufruf zu machen.

zu einer Funktion Code Vor dem Sprung Sie einige Zustand auf dem Stapel speichern (das heißt Sie Ihre Absenderadresse drücken und der Stapel enthält bereits Ihre Einheimischen). Dies ist im Wesentlichen eine Fortsetzung. Wenn die Funktion beendet hat, hat es zu bestimmen, wo die Strömung der Ausführung zu senden. Es nutzt die Fortsetzung auf dem Stapel gespeichert, die Absenderadresse knallend und Springen zu.

Weitere Sprachen diese Idee von Fortsetzungen verallgemeinern so dass Sie explizit angeben, wo die Codeausführung fortzusetzen, anstatt implizit weiter an, von wo aus dem Funktionsaufruf durchgeführt wurde.

EDIT basierend auf Kommentar:

Die Fortsetzung ist der komplette Ausführungszustand. An jedem Punkt der Ausführung können Sie das Programm in zwei Teile aufzuteilen (in der Zeit, nicht Raum) - das, was bis zu diesem Punkt laufen hat, und alles, was von hier laufen los. Die „aktuelle Fortsetzung“ ist das „alles, was von hier läuft los“ (Sie daran denken können wie eine Art von Funktion, die alles tun, um der Rest des Programms getan haben würde). So ist die Funktion, die Sie call/cc liefern wird die Fortsetzung übergeben, die aktuell waren, als call/cc aufgerufen wurde. Die Funktion die Fortsetzung verwenden kann Ausführung an die call/cc Anweisung zurückzukehren (wahrscheinlicher, obwohl es die Fortsetzung um auf etwas anderem passieren würde, denn wenn sie es direkt verwendet könnte es stattdessen eine einfache Rückkehr zu tun).

Answer 7

Die Sache, die mir geholfen haben, ist die Idee, dass mit der Funktion in einer traditionellen Sprache Anrufe, die Sie implizit eine Fortsetzung jederzeit passieren Sie einen Funktionsaufruf zu machen.

zu einer Funktion Code Vor dem Sprung Sie einige Zustand auf dem Stapel speichern (das heißt Sie Ihre Absenderadresse drücken und der Stapel enthält bereits Ihre Einheimischen). Dies ist im Wesentlichen eine Fortsetzung. Wenn die Funktion beendet hat, hat es zu bestimmen, wo die Strömung der Ausführung zu senden. Es nutzt die Fortsetzung auf dem Stapel gespeichert, die Absenderadresse knallend und Springen zu.

Weitere Sprachen diese Idee von Fortsetzungen verallgemeinern so dass Sie explizit angeben, wo die Codeausführung fortzusetzen, anstatt implizit weiter an, von wo aus dem Funktionsaufruf durchgeführt wurde.

EDIT basierend auf Kommentar:

Die Fortsetzung ist der komplette Ausführungszustand. An jedem Punkt der Ausführung können Sie das Programm in zwei Teile aufzuteilen (in der Zeit, nicht Raum) - das, was bis zu diesem Punkt laufen hat, und alles, was von hier laufen los. Die „aktuelle Fortsetzung“ ist das „alles, was von hier läuft los“ (Sie daran denken können wie eine Art von Funktion, die alles tun, um der Rest des Programms getan haben würde). So ist die Funktion, die Sie call/cc liefern wird die Fortsetzung übergeben, die aktuell waren, als call/cc aufgerufen wurde. Die Funktion die Fortsetzung verwenden kann Ausführung an die call/cc Anweisung zurückzukehren (wahrscheinlicher, obwohl es die Fortsetzung um auf etwas anderem passieren würde, denn wenn sie es direkt verwendet könnte es stattdessen eine einfache Rückkehr zu tun).

Answer 8

Als ich versuchte Anruf / cc zu verstehen, fand ich diese Call-mit-Strom-Continuation-für-C-Programmierer Seite wurde hilfreich.

Answer 9

Answer 10

Answer 11

Als ich versuchte Anruf / cc zu verstehen, fand ich diese

Answer 12

Die beste Erklärung, die ich gesehen habe, ist in Paul Grahams Buch, On Lisp .

Answer 13

Stellen Sie sich Ihr Skript ein Videospielstufe ist. Call / cc ist wie eine Bonus-Stage.

Sobald Sie es berühren Sie die Bonusstufe übertragen werden (das heißt, die Definition der Funktion als Argument übergeben nennen / cc [f in diesem Fall]).

Bonus Stufen unterscheiden sich von gewöhnlichen Stufen , da in der Regel haben sie ein Element (dh das Argument der Funktion aufzurufen, übergeben / cc), dass, wenn Sie es berühren Sie verlieren und werden wieder in der Normalstufe transportiert.

So ist es egal, tut, wenn es viele args sind, wenn Sie einer von ihnen erreichen die über. Also unsere Ausführung erreicht (arg 42) und gibt sie an die Summe (+ 42 10).

Auch gibt es einige Bemerkungen beachtenswert:

• Nicht alle Funktionen können mit Call / cc verwendet werden. Da es erwartet ein Fortsetzung (dh eine Funktion), können Sie keine f wie dieses: (define f (lambda (k) (+ k 42)), denn man kann nicht ein sum Funktion.
• Sie können auch nicht haben (define f (lambda (k) (f 42 10))) weil die Fortsetzung erwartet nur ein Argument.
• Sie können beenden ohne touching jede Ausfahrt, in diesem Fall die Funktion schreitet wie jede gewöhnliche Funktion (z.B. (define f (lambda (k) 42) Oberflächen und liefert 42).

Answer 14

Es gibt mehrere Ebenen zu verstehen Anruf / cc. Zuerst müssen Sie die Bedingungen verstehen und die, wie der Mechanismus funktioniert. Dann wird ein Verständnis davon, wie und wann Anruf / cc ist im „echten Leben“ verwendet Programmierung erforderlich ist.

Die erste Ebene kann durch das Studium CPS erreicht werden, aber es gibt Alternativen.

Für die zweite Ebene empfehle ich die folgenden Klassiker von Friedman.

Daniel P. Friedman. "Anwendungen von Fortsetzungen: Invited Tutorial". 1988 Principles of Programmiersprachen (POPL88). Januar 1988.

Answer 15

Werfen Sie einen Blick auf die Beschreibung und Umsetzung von Call / cc für FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with -continuations.aspx

Answer 16

Das Modell, das ich für verwendete Fortsetzungen von einem imperativ Standpunkt zu verstehen ist, dass es sich um eine Kopie des Call-Stack ist mit dem Zeiger auf den nächsten Befehl kombiniert.

Call / cc ruft eine Funktion (als Argument übergibt) mit der Fortsetzung als Argument.