Buscando ejemplos de usos “reales” de continuaciones
https://stackoverflow.com/questions/34155
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy tratando de captar el concepto de continuaciones y encontré varios pequeños ejemplos de enseñanza como este del Artículo de 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))
Entiendo lo que hace esta pequeña función, pero no veo ninguna aplicación obvia.Si bien no espero usar continuaciones en todo mi código en el corto plazo, desearía conocer algunos casos en los que pueden ser apropiadas.
Así que estoy buscando ejemplos de código más explícitamente útiles de lo que las continuaciones pueden ofrecerme como programador.
¡Salud!
Solución
En Algo & Data II los usamos todo el tiempo para "salir" o "regresar" de una función (larga)
por ejemplo, el algoritmo BFS para atravesar árboles se implementó así:
(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)))))))))
Como puede ver, el algoritmo saldrá cuando la función descubierta por el nodo devuelva verdadero:
(if (node-discovered node)
(exit node))
la función también dará un "valor de retorno":'nodo'
La razón por la que la función sale es por esta declaración:
(call-with-current-continuation
(lambda (my-future)
(set! exit my-future)
cuando usamos exit, volverá al estado anterior a la ejecución, vaciará la pila de llamadas y devolverá el valor que le diste.
Básicamente, call-cc se usa (aquí) para saltar de una función recursiva, en lugar de esperar a que toda la recursividad termine por sí sola (lo que puede resultar bastante costoso cuando se realiza mucho trabajo computacional).
Otro ejemplo más pequeño que hace lo mismo 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))))
Otros consejos
@Palmadita
Playa
Sí, Playa es un gran ejemplo.Examiné su código rápidamente y encontré este mensaje que ilustra el paso del control entre componentes de una manera aparentemente completa en la 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 ]
¡Tan agradable!
Construí mi propio software de prueba unitaria.Antes de ejecutar la prueba, almaceno la continuación antes de ejecutar la prueba y luego, en caso de falla, (opcionalmente) le digo al intérprete del esquema que entre en modo de depuración y vuelva a invocar la continuación.De esta manera puedo recorrer el código problemático con mucha facilidad.
Si sus continuaciones son serializables, también puede almacenarlas en caso de falla de la aplicación y luego volver a invocarlas para obtener información detallada sobre valores de variables, seguimientos de pila, etc.
Algunos servidores web y marcos web utilizan continuaciones para almacenar información de la sesión.Se crea un objeto de continuación para cada sesión y luego lo utiliza cada solicitud dentro de la sesión.
Me encontré con una implementación del amb operador en esta publicación de http://www.randomhacks.net, usando continuaciones.
Esto es lo que amb El operador hace:
# 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
Y aquí está la implementación de la publicación:
# 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
Me gusta amb!
Las continuaciones se pueden utilizar en ejemplos de la "vida real" siempre que el flujo del programa no sea lineal o ni siquiera esté predeterminado.Una situación familiar es aplicaciones web.
Las continuaciones son una buena alternativa al subproceso por solicitud en la programación de servidores (incluidas las interfaces de aplicaciones web).
En este modelo, en lugar de lanzar un hilo nuevo (pesado) cada vez que llega una solicitud, simplemente comienza a trabajar en una función.Luego, cuando esté listo para bloquear las E/S (es decir,leyendo de la base de datos), pasa una continuación al controlador de respuesta de red.Cuando llega la respuesta, ejecuta la continuación.Con este esquema, puedes procesar muchas solicitudes con solo unos pocos subprocesos.
Esto hace que el flujo de control sea más complejo que usar subprocesos de bloqueo, pero bajo cargas pesadas, es más eficiente (al menos en el hardware actual).
El operador amb es un buen ejemplo que permite una programación declarativa similar a un prólogo.
Mientras hablamos, estoy codificando un software de composición musical en Scheme (soy un músico sin casi ningún conocimiento de la teoría detrás de la música y solo estoy analizando mis propias piezas para ver cómo funcionan las matemáticas detrás de esto).
Usando el operador amb puedo simplemente completar las restricciones que debe satisfacer una melodía y dejar que Scheme determine el resultado.
Probablemente se incluyan continuaciones en Scheme debido a la filosofía del lenguaje. Scheme es un marco que le permite comprender cualquier paradigma de programación que se encuentre en otro lenguaje definiendo bibliotecas en el propio Scheme.Las continuaciones sirven para crear sus propias estructuras de control abstractas como "retorno", "interrupción" o para habilitar la programación declarativa.Scheme es más "generalizador" y exige que el programador también pueda especificar dichas construcciones.
Qué hay de la API de maplets de Google?Hay un montón de funciones (todas terminan en Async) al que le pasas una devolución de llamada.La función API realiza una solicitud asíncrona, obtiene su resultado y luego pasa ese resultado a su devolución de llamada (como "lo siguiente que debe hacer").Suena muy parecido estilo de paso de continuación a mi.
Este ejemplo muestra un caso muy simple.
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");
Como esto es Javascript, no hay optimización de llamadas de cola, por lo que la pila crecerá con cada llamada hasta convertirse en una continuación y, eventualmente, devolverá el hilo de control al navegador.De todos modos, creo que es una bonita abstracción.
Si tiene que invocar una acción asincrónica y suspender la ejecución hasta obtener el resultado, normalmente sondeará el resultado o colocará el resto de su código en una devolución de llamada para que la acción asincrónica lo ejecute al finalizar.Con las continuaciones, no necesita realizar la opción ineficiente de sondeo, y no necesita resumir todo el código para ejecutarlo después del evento asíncrono en una devolución de llamada: simplemente pasa el estado actual del código como devolución de llamada. - y el código se "activa" efectivamente tan pronto como se completa la acción asíncrona.
Las continuaciones se pueden utilizar para implementar excepciones, un depurador.
