Suchen Sie nach Beispielen für „echte“ Verwendungen von Fortsetzungen
https://stackoverflow.com/questions/34155
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich versuche, das Konzept der Fortsetzungen zu verstehen und habe mehrere kleine Lehrbeispiele wie dieses aus dem gefunden Wikipedia-Artikel:
(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 bewirkt, kann aber keine offensichtliche Anwendung davon erkennen.Obwohl ich nicht erwarte, dass ich in absehbarer Zeit überall in meinem Code Fortsetzungen verwenden werde, wünschte ich, ich wüsste ein paar Fälle, in denen sie angemessen sein können.
Deshalb suche ich nach explizit nützlichen Codebeispielen dafür, was Fortsetzungen mir als Programmierer bieten können.
Prost!
Lösung
In Algo & Data II haben wir diese immer verwendet, um eine (lange) Funktion zu „verlassen“ oder „zurückzukehren“.
Beispielsweise wurde der BFS-Algorithmus zum Durchqueren von Bäumen folgendermaßen implementiert:
(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 sehen können, wird der Algorithmus beendet, wenn die vom Knoten erkannte Funktion „true“ zurückgibt:
(if (node-discovered node)
(exit node))
Die Funktion gibt auch einen „Rückgabewert“ aus:'Knoten'
Warum die Funktion beendet wird, liegt an dieser Anweisung:
(call-with-current-continuation
(lambda (my-future)
(set! exit my-future)
Wenn wir Exit verwenden, kehrt es in den Zustand vor der Ausführung zurück, leert den Aufrufstapel und gibt den Wert zurück, den Sie ihm gegeben haben.
Im Grunde genommen wird call-cc (hier) verwendet, um aus einer rekursiven Funktion herauszuspringen, anstatt darauf zu warten, dass die gesamte Rekursion von selbst endet (was bei viel Rechenarbeit ziemlich teuer sein kann).
ein weiteres kleineres Beispiel, das dasselbe mit call-cc macht:
(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))))
Andere Tipps
Strand:
@Klopfen
Strand
Ja, Strand ist ein tolles Beispiel.Ich habe den Code schnell durchgesehen und diese Meldung gefunden, die die scheinbar zustandsbehaftete Übergabe der Kontrolle zwischen Komponenten im 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 nett!
Ich habe meine eigene Unit-Test-Software erstellt.Bevor ich den Test ausführe, speichere ich die Fortsetzung, bevor ich den Test ausführe, und weise dann bei einem Fehler (optional) den Schema-Interpreter an, in den Debug-Modus zu wechseln und die Fortsetzung erneut aufzurufen.Auf diese Weise kann ich den problematischen Code ganz einfach durchgehen.
Wenn Ihre Fortsetzungen serialisierbar sind, können Sie sie auch bei einem Anwendungsfehler speichern und sie dann erneut aufrufen, um detaillierte Informationen zu Variablenwerten, Stack-Traces usw. zu erhalten.
Fortsetzungen werden von einigen Webservern und Web-Frameworks zum Speichern von Sitzungsinformationen verwendet.Für jede Sitzung wird ein Fortsetzungsobjekt erstellt und dann von jeder Anforderung innerhalb der Sitzung verwendet.
Ich bin auf eine Implementierung von gestoßen amb Betreiber in dieser Beitrag aus http://www.randomhacks.net, mit Fortsetzungen.
Hier ist, was die amb Betreiber 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 des Beitrags:
# 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!
Fortsetzungen können in „realen“ Beispielen immer dann verwendet werden, wenn der Programmablauf nicht linear oder nicht einmal vorbestimmt ist.Eine bekannte Situation ist Web Applikationen.
Fortsetzungen sind eine gute Alternative zu Thread-per-Request in der Serverprogrammierung (einschließlich Webanwendungs-Frontends).
Anstatt bei diesem Modell jedes Mal, wenn eine Anfrage eingeht, einen neuen (schweren) Thread zu starten, beginnen Sie einfach mit der Arbeit in einer Funktion.Wenn Sie dann bereit sind, E/A zu blockieren (d. h.Beim Lesen aus der Datenbank übergeben Sie eine Fortsetzung an den Netzwerk-Antworthandler.Wenn die Antwort zurückkommt, führen Sie die Fortsetzung aus.Mit diesem Schema können Sie viele Anfragen mit nur wenigen Threads bearbeiten.
Dies macht den Kontrollfluss komplexer als die Verwendung blockierender Threads, ist aber unter hoher Last effizienter (zumindest auf heutiger Hardware).
Der amb-Operator ist ein gutes Beispiel, das prologartige deklarative Programmierung ermöglicht.
Während wir hier sprechen, programmiere ich eine Musikkompositionssoftware in Scheme (ich bin ein Musiker, der so gut wie keine Ahnung von der Theorie hinter der Musik hat und ich analysiere nur meine eigenen Stücke, um zu sehen, wie die Mathematik dahinter funktioniert.)
Mit dem Amb-Operator kann ich einfach Einschränkungen eingeben, die eine Melodie erfüllen muss, und Scheme das Ergebnis ermitteln lassen.
Fortsetzungen werden wahrscheinlich aufgrund der Sprachphilosophie in Scheme eingefügt. Scheme ist ein Framework, das es Ihnen ermöglicht, jedes in anderen Sprachen vorkommende Programmierparadigma kennenzulernen, indem Sie Bibliotheken in Scheme selbst definieren.Fortsetzungen dienen dazu, eigene abstrakte Kontrollstrukturen wie „return“, „break“ zu erstellen oder deklarative Programmierung zu ermöglichen.Scheme ist eher „verallgemeinernd“ und verlangt, dass solche Konstrukte auch vom Programmierer spezifiziert werden können.
Was ist mit Google Mapplets-API?Es gibt eine Reihe von Funktionen (alle enden auf Async), an den Sie einen Rückruf übergeben.Die API-Funktion führt eine asynchrone Anfrage aus, ruft das Ergebnis ab und übergibt dieses Ergebnis dann an Ihren Rückruf (als „nächstes zu tun“).Klingt sehr danach Fortsetzungspassstil mir.
Das Beispiel 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 es sich um Javascript handelt, gibt es kein Tail-Call-Optimierung, sodass der Stapel mit jedem Aufruf zu einer Fortsetzung wächst und Sie schließlich den Steuerungsthread an den Browser zurückgeben.Trotzdem finde ich, dass es eine schöne Abstraktion ist.
Wenn Sie eine asynchrone Aktion aufrufen und die Ausführung anhalten müssen, bis Sie das Ergebnis erhalten, würden Sie normalerweise entweder das Ergebnis abfragen oder den Rest Ihres Codes in einen Rückruf einfügen, der nach Abschluss von der asynchronen Aktion ausgeführt wird.Bei Fortsetzungen müssen Sie nicht die ineffiziente Option der Abfrage durchführen und Sie müssen nicht Ihren gesamten Code, der nach dem Asynch-Ereignis ausgeführt werden soll, in einem Rückruf zusammenfassen – Sie übergeben einfach den aktuellen Status des Codes als Rückruf – und der Code wird effektiv „aufgeweckt“, sobald die asynchrone Aktion abgeschlossen ist.
Fortsetzungen können verwendet werden, um Ausnahmen und einen Debugger zu implementieren.
