Alla ricerca di esempi di usi “reali” delle continuazioni
https://stackoverflow.com/questions/34155
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando di afferrare il concetto di continuazione e ho trovato diversi piccoli esempi didattici come questo dal Articolo di Wikipedia:
(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))
Capisco cosa fa questa piccola funzione, ma non riesco a vederne alcuna applicazione ovvia.Anche se non prevedo di utilizzare presto le continuazioni in tutto il mio codice, vorrei conoscere alcuni casi in cui possono essere appropriate.
Quindi sto cercando esempi di codice più esplicitamente utili di ciò che le continuazioni possono offrirmi come programmatore.
Saluti!
Soluzione
In Algo & Data II li usavamo tutte le volte per "uscire" o "tornare" da una (lunga) funzione
ad esempio l'algoritmo BFS per attraversare gli alberi è stato implementato in questo modo:
(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)))))))))
Come puoi vedere, l'algoritmo terminerà quando la funzione del nodo scoperto restituisce true:
(if (node-discovered node)
(exit node))
la funzione fornirà anche un "valore restituito":'nodo'
il motivo per cui la funzione termina è a causa di questa affermazione:
(call-with-current-continuation
(lambda (my-future)
(set! exit my-future)
quando usiamo exit, tornerà allo stato prima dell'esecuzione, svuotando lo stack di chiamate e restituirà il valore che gli hai assegnato.
Quindi, in pratica, call-cc viene utilizzato (qui) per uscire da una funzione ricorsiva, invece di attendere che l'intera ricorsione finisca da sola (il che può essere piuttosto costoso quando si esegue molto lavoro computazionale)
un altro esempio più piccolo che fa lo stesso con call-cc:
(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))))
Altri suggerimenti
Mare:
@Colpetto
Mare
SÌ, Mare è un ottimo esempio.Ho sfogliato rapidamente il suo codice e ho trovato questo messaggio che illustra il passaggio del controllo tra i componenti in modo apparentemente completo sul Web.
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 ]
Così carino!
Ho creato il mio software di test unitario.Prima di eseguire il test, memorizzo la continuazione prima di eseguire il test e, in caso di fallimento, dico (facoltativamente) all'interprete dello schema di passare alla modalità debug e richiamare nuovamente la continuazione.In questo modo posso esaminare il codice problematico molto facilmente.
Se le continuazioni sono serializzabili, è possibile anche memorizzarle in caso di errore dell'applicazione e quindi richiamarle nuovamente per ottenere informazioni dettagliate sui valori delle variabili, sulle analisi dello stack e così via.
Le continuazioni vengono utilizzate da alcuni server Web e framework Web per archiviare informazioni sulla sessione.Un oggetto di continuazione viene creato per ogni sessione e quindi utilizzato da ogni richiesta all'interno della sessione.
Mi sono imbattuto in un'implementazione di amb operatore dentro questo post da http://www.randomhacks.net, utilizzando le continuazioni.
Ecco cosa amb l'operatore fa:
# 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
Ed ecco l'implementazione del 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
mi piace amb!
Le continuazioni possono essere utilizzate negli esempi "reali" ogni volta che il flusso del programma non è lineare o nemmeno predeterminato.Una situazione familiare è applicazioni web.
Le continuazioni sono una buona alternativa al thread-per-request nella programmazione del server (inclusi i frontend delle applicazioni web.
In questo modello, invece di lanciare un nuovo (pesante) thread ogni volta che arriva una richiesta, si inizia semplicemente a lavorare in una funzione.Quindi, quando sei pronto per bloccare l'I/O (ad es.leggendo dal database), si passa una continuazione al gestore della risposta di rete.Quando arriva la risposta, esegui la continuazione.Con questo schema puoi elaborare molte richieste con pochi thread.
Ciò rende il flusso di controllo più complesso rispetto all'utilizzo dei thread di blocco, ma sotto carico pesante è più efficiente (almeno sull'hardware odierno).
L'operatore amb è un buon esempio che consente una programmazione dichiarativa simile al prologo.
Mentre parliamo, sto codificando un pezzo di software di composizione musicale in Scheme (sono un musicista con una conoscenza quasi nulla della teoria dietro la musica e sto solo analizzando i miei pezzi per vedere come funziona la matematica dietro).
Usando l'operatore amb posso semplicemente inserire i vincoli che una melodia deve soddisfare e lasciare che Scheme calcoli il risultato.
Le continuazioni sono probabilmente inserite in Scheme a causa della filosofia del linguaggio, Scheme è un framework che ti consente di realizzare qualsiasi paradigma di programmazione trovato in altri linguaggi definendo le librerie in Scheme stesso.Le continuazioni servono per creare le proprie strutture di controllo astratte come "ritorno", "interruzione" o per abilitare la programmazione dichiarativa.Scheme è più "generalizzante" e richiede che tali costrutti possano essere specificati anche dal programmatore.
Che ne dici di API di Google Maplet?Ci sono un sacco di funzioni (tutte terminano con Async) a cui passi una richiamata.La funzione API esegue una richiesta asincrona, ottiene il risultato, quindi passa tale risultato al callback (come "prossima cosa da fare").Sembra molto simile stile di passaggio continuo per me.
Questo esempio mostra un caso molto semplice.
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");
Dato che questo è Javascript, non c'è ottimizzazione delle chiamate in coda, quindi lo stack crescerà con ogni chiamata in una continuazione e alla fine restituirai il thread di controllo al browser.Comunque penso che sia una bella astrazione.
Se devi invocare un'azione asincrona e sospendere l'esecuzione finché non ottieni il risultato, normalmente eseguirai il polling del risultato o inserirai il resto del codice in un callback per essere eseguito dall'azione asincrona al completamento.Con le continuazioni non è necessario eseguire l'opzione inefficiente del polling e non è necessario racchiudere tutto il codice per essere eseguito dopo l'evento asincrono in una richiamata: è sufficiente passare lo stato corrente del codice come richiamata - e il codice viene effettivamente "svegliato" non appena l'azione asincrona viene completata.
Le continuazioni possono essere utilizzate per implementare eccezioni, un debugger.
