der Suche nach Beispielen für „echte“ verwendet von Fortsetzungen

Question

Ich versuche, das Konzept der Fortsetzungen zu erfassen und ich mehrere kleine Lehre Beispiele wie diese aus der Wikipedia article gefunden:

(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)) 

Ich verstehe, was diese kleine Funktion tut, aber ich kann keine offensichtliche Anwendung davon sehen. Obwohl ich nicht erwarte, in meinem Code bald irgendwelche Fortsetzungen zu verwenden, würde ich gerne ein paar Fälle kennen, in denen sie angemessen sein könnten.

Also ich bin auf der Suche nach mehr nützliche Code-Beispiele, was Fortsetzungen kann mir als Programmierer bieten.

Prost!

Answer 1

In Algo & Daten II haben wir diese alle Zeiten „exit“ oder „Rückkehr“ von einer (langen) Funktion

zum Beispiel des BFS algorthm Bäume zu durchqueren mit wie dies umgesetzt wurde:

(define (BFS graph root-discovered node-discovered edge-discovered edge-bumped . nodes) 
    (define visited (make-vector (graph.order graph) #f)) 
    (define q (queue.new)) 
    (define exit()) 
    (define (BFS-tree node) 
    (if (node-discovered node) 
     (exit node)) 
    (graph.map-edges 
    graph 
    node 
    (lambda (node2) 
     (cond ((not (vector-ref visited node2)) 
       (when (edge-discovered node node2) 
       (vector-set! visited node2 #t) 
       (queue.enqueue! q node2))) 
      (else 
       (edge-bumped node node2))))) 
    (if (not (queue.empty? q)) 
     (BFS-tree (queue.serve! q)))) 

    (call-with-current-continuation 
    (lambda (my-future) 
    (set! exit my-future) 
    (cond ((null? nodes) 
      (graph.map-nodes 
      graph 
      (lambda (node) 
       (when (not (vector-ref visited node)) 
       (vector-set! visited node #t) 
       (root-discovered node) 
       (BFS-tree node))))) 
      (else 
      (let loop-nodes 
       ((node-list (car nodes))) 
       (vector-set! visited (car node-list) #t) 
       (root-discovered (car node-list)) 
       (BFS-tree (car node-list)) 
       (if (not (null? (cdr node-list))) 
       (loop-nodes (cdr node-list))))))))) 

Wie Sie den Algorithmus sehen beendet, wenn der Knoten entdeckt Funktion true zurückgibt:

(if (node-discovered node) 
     (exit node)) 

die Funktion wird auch eine „Rückkehr geben Wert ":‚Knoten‘

warum die Funktion beendet wird, ist diese Aussage wegen:

(call-with-current-continuation 
     (lambda (my-future) 
     (set! exit my-future) 

wenn wir Exit verwenden, wird es vor der Ausführung in den Zustand zurück, den Anruf-Stapel Entleerung und gib den Wert zurück, den du ihm gegeben hast.

Also im Grunde, Call-cc verwendet wird (hier) aus einer rekursiven Funktion zu springen, anstatt für die gesamte Rekursion des Wartens von selbst zu beenden (was sehr teuer sein kann, wenn eine Menge Rechenarbeit tun)

ein weiteres kleineres Beispiel das gleiche mit Call-cc tun:

(define (connected? g node1 node2) 
    (define visited (make-vector (graph.order g) #f)) 
    (define return()) 
    (define (connected-rec x y) 
    (if (eq? x y) 
     (return #t)) 
    (vector-set! visited x #t) 
    (graph.map-edges g 
        x 
        (lambda (t) 
         (if (not (vector-ref visited t)) 
         (connected-rec t y))))) 
    (call-with-current-continuation 
    (lambda (future) 
    (set! return future) 
    (connected-rec node1 node2) 
    (return #f)))) 

Answer 2

Fortsetzungen können in "real-life" -Beispielen verwendet werden, wenn der Programmablauf nicht linear oder nicht vorher festgelegt ist. Eine vertraute Situation ist web applications.

Answer 3

Fortsetzungen werden von einigen Webservern und Webframeworks zum Speichern von Sitzungsinformationen verwendet. Ein Fortsetzungsobjekt wird für jede Sitzung erstellt und dann von jeder Anforderung innerhalb der Sitzung verwendet.

There's an article about this approach here.

Answer 4

am Wasser:

• homepage
• wikipedia page

Answer 5

@ Pat

Meer

Ja, Seaside ist ein großartiges Beispiel. Ich habe den Code schnell durchsucht und diese Nachricht gefunden, die die Weitergabe der Kontrolle zwischen den Komponenten scheinbar statisch über das Web veranschaulicht.

WAComponent >> call: aComponent 
    "Pass control from the receiver to aComponent. The receiver will be 
    temporarily replaced with aComponent. Code can return from here later 
    on by sending #answer: to aComponent." 

    ^AnswerContinuation currentDo: [ :cc | 
     self show: aComponent onAnswer: cc. 
     WARenderNotification raiseSignal ] 

So schön!

Answer 6

ich kam accross einer Implementierung des amb Betreibers in this post von http://www.randomhacks.net, Fortsetzungen verwenden.

Hier ist, was die amb opeerator tut:

# amb will (appear to) choose values 
# for x and y that prevent future 
# trouble. 
x = amb 1, 2, 3 
y = amb 4, 5, 6 

# Ooops! If x*y isn't 8, amb would 
# get angry. You wouldn't like 
# amb when it's angry. 
amb if x*y != 8 

# Sure enough, x is 2 and y is 4. 
puts x, y 

Und hier ist die Umsetzung der Post:

# A list of places we can "rewind" to 
# if we encounter amb with no 
# arguments. 
$backtrack_points = [] 

# Rewind to our most recent backtrack 
# point. 
def backtrack 
    if $backtrack_points.empty? 
    raise "Can't backtrack" 
    else 
    $backtrack_points.pop.call 
    end 
end 

# Recursive implementation of the 
# amb operator. 
def amb *choices 
    # Fail if we have no arguments. 
    backtrack if choices.empty? 
    callcc {|cc| 
    # cc contains the "current 
    # continuation". When called, 
    # it will make the program 
    # rewind to the end of this block. 
    $backtrack_points.push cc 

    # Return our first argument. 
    return choices[0] 
    } 

    # We only get here if we backtrack 
    # using the stored value of cc, 
    # above. We call amb recursively 
    # with the arguments we didn't use. 
    amb *choices[1...choices.length] 
end 

# Backtracking beyond a call to cut 
# is strictly forbidden. 
def cut 
    $backtrack_points = [] 
end 

Ich mag amb!

Answer 7

Ich baute meine eigene Unit-Test-Software. Bevor ich den Test ausführe, speichere ich die Fortsetzung, bevor ich den Test ausführe, und bei einem Fehler sage ich (optional) dem Schema-Interpreter, in den Debug-Modus zu wechseln und die Fortsetzung erneut aufzurufen. Auf diese Weise kann ich den problematischen Code wirklich leicht durchgehen.

Wenn Ihr Fortsetzungen serializable sind, können Sie auch speichern Sie dann auf Anwendungsfehler, und dann erneut aufrufen, sie detaillierte Informationen über Variablenwerte zu erhalten, stapeln Spuren usw.

Answer 8

Fortsetzungen sind eine gute Alternative zu thread- Pro-Anfrage in Server-Programmierung (einschließlich Web-Anwendung Frontends.

In diesem Modell, anstatt einen neuen (schweren) Thread jedes Mal starten, wenn eine Anfrage hereinkommt, starten Sie einfach etwas Arbeit in einer Funktion. Dann, wenn Sie sind bereit zum Blockieren von I/O (dh Lesen von der Datenbank), übergeben Sie eine Fortsetzung in den Netzwerk-Antwort-Handler.Wenn die Antwort zurückkommt, führen Sie die Fortsetzung. Mit diesem s Mit wenigen Threads können Sie viele Anfragen bearbeiten.

Dies macht den Kontrollfluss komplexer als die Verwendung von blockierenden Threads, aber unter hoher Last ist es effizienter (zumindest auf der heutigen Hardware).

Answer 9

Wie wäre es mit der Google Mapplets API? Es gibt eine Reihe von Funktionen (alle enden in Async), an die Sie einen Rückruf übergeben. Die API-Funktion führt eine asynchrone Anfrage durch, erhält das Ergebnis und übergibt dieses Ergebnis an Ihren Rückruf (als "nächste Aufgabe"). Klingt sehr nach continuation passing style für mich.

Diese example zeigt einen sehr einfachen Fall.

map.getZoomAsync(function(zoom) { 
    alert("Current zoom level is " + zoom); // this is the continuation 
}); 
alert("This might happen before or after you see the zoom level message"); 

Da dies Javascript gibt es keine tail call optimization, so dass der Stapel wird bei jedem Aufruf in eine Fortsetzung wachsen, und Sie werden schließlich den Faden der Kontrolle an den Browser zurück. Egal, ich denke, es ist eine schöne Abstraktion.

Answer 10

Fortsetzungen können verwendet werden, um Ausnahmen, ein Debugger zu implementieren.

Answer 11

Wenn Sie eine asynchrone Aktion aufrufen und die Ausführung aussetzen müssen, bis Sie das Ergebnis erhalten, suchen Sie entweder nach dem Ergebnis oder fügen den Rest Ihres Codes in einen Callback ein, der nach Abschluss der asynchronen Aktion ausgeführt wird.Bei Fortsetzungen müssen Sie die ineffiziente Abfrage nicht durchführen, und Sie müssen nicht den gesamten Code einpacken, der nach dem asynch-Ereignis in einem Rückruf ausgeführt werden soll - Sie übergeben lediglich den aktuellen Status des Codes als Rückruf - und der Code wird effektiv "aufgeweckt", sobald die asynch Aktion abgeschlossen ist.

Answer 12

Der amb-Operator ist ein gutes Beispiel, das Prolog-ähnliche deklarative Programmierung ermöglicht.

Während wir sprechen, programmiere ich ein Stück Musikkompositionssoftware in Scheme (Ich bin ein Musiker mit fast keiner Kenntnis der Theorie hinter Musik und ich analysiere nur meine eigenen Stücke, um zu sehen, wie die Mathematik dahinter ist es funktioniert.)

Mit dem amb-Operator kann ich einfach die Nebenbedingungen eingeben, die eine Melodie erfüllen muss und lässt Schema das Ergebnis herausfinden.

Fortsetzungen werden wahrscheinlich in Schema eingefügt Aufgrund der Sprachphilosophie ist Scheme ein Framework, das es Ihnen ermöglicht, beliebige Programmierparadigmen in anderen Sprachen zu erkennen, indem Sie Bibliotheken in Scheme selbst definieren. Es geht darum, eigene abstrakte Kontrollstrukturen wie "return" oder "break" zu konstruieren oder deklarative Programmierung zu ermöglichen. Schema ist "verallgemeinernd" und bittet, dass solche Konstrukte auch vom Programmierer spezifiziert werden können.