Buscando ejemplos de "real" utiliza de continuaciones

Question

que estoy tratando de comprender el concepto de continuaciones y he encontrado varios ejemplos de enseñanza pequeños como éste de la Wikipedia article:

(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 esta pequeña función lo hace, pero no puedo ver ninguna aplicación obvia de eso. Si bien no espero usar continuaciones en todo mi código en el corto plazo, me gustaría saber algunos casos en los que pueden ser apropiados.

Así que estoy buscando ejemplos de código explícitamente útiles de lo que las continuaciones me pueden ofrecer como programador.

¡Salud!

Answer 1

En Algo & de Datos II, utiliza estos todos los tiempos de la "salida" o "retorno" de una función (largo)

por ejemplo, el algorthm BFS para atravesar árboles con se implementó como esto:

(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 se puede ver el algoritmo va a salir cuando la función del nodo-descubierto devuelve verdadero:

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

la función también se dará un "retorno valor ": 'nodo'

por qué se cierra la función, se debe a que de esta declaración:

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

cuando usamos la salida, pasará de nuevo al estado antes de la ejecución, el vaciado de la pila de llamadas y devuelve el valor que le diste.

Así que, básicamente, call-cc se utiliza (en este caso) para saltar de una función recursiva, en lugar de esperar a que toda la recursividad para poner fin por sí mismo (que puede ser bastante caro cuando se hace un montón de trabajo computacional)

hacer lo mismo con la llamada cc otro ejemplo más pequeña:

(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

Las mejoras se pueden utilizar en ejemplos de "la vida real" siempre que el flujo del programa no sea lineal, o incluso no esté predeterminado. Una situación familiar es web applications.

Answer 3

Algunos servidores web y marcos web utilizan las actualizaciones para almacenar la información de la sesión. Se crea un objeto de continuación para cada sesión y luego lo usa cada solicitud dentro de la sesión.

There's an article about this approach here.

Answer 4

Mar:

• homepage
• wikipedia page

Answer 5

@Pat

Mar

Sí, Seaside es un gran ejemplo. Navegué su código rápidamente y encontré este mensaje que ilustra el control de paso entre los componentes de una manera aparentemente completa a través de 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 ] 

So nice!

Answer 6

me encontré con una implementación del operador amb en this post de http://www.randomhacks.net, usando continuaciones.

Esto es lo que hace el amb opeerator:

# 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 del mensaje:

# 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!

Answer 7

Creé mi propio software de pruebas unitarias. Antes de ejecutar la prueba, almaceno la continuación antes de ejecutar la prueba, y luego, cuando falla, I (opcionalmente) le digo al intérprete de esquema que pase al modo de depuración y vuelva a invocar la continuación. De esta manera, puedo pasar por el código problemático con mucha facilidad.

Si sus continuaciones son serializable, también se puede almacenar a continuación, en caso de fallo de aplicación, y luego volver a invocar a ellos para obtener información detallada sobre los valores de variables, trazas de la pila, etc.

Answer 8

continuaciones son una buena alternativa a thread- por solicitud en la programación del servidor (incluidas las interfaces de aplicaciones web

En este modelo, en vez de iniciar un nuevo subproceso (pesado) cada vez que recibe una solicitud, simplemente comienza a trabajar en una función. listo para bloquear en E/S (es decir, lectura desde la base de datos), pasa una continuación al manejador de respuestas de red. Cuando la respuesta vuelve, ejecuta la continuación. cheme, puede procesar muchas solicitudes con solo unos pocos hilos.

Esto hace que el flujo de control sea más complejo que usar hilos de bloqueo, pero con cargas pesadas, es más eficiente (al menos en el hardware actual).

Answer 9

¿Qué tal el Google Mapplets API? Hay un montón de funciones (todas que terminan en Async) a las que pasa una devolución de llamada. La función API realiza una solicitud asincrónica, obtiene su resultado y luego pasa ese resultado a su devolución de llamada (como "lo siguiente a hacer"). Suena mucho como continuation passing style para mí.

Este example 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 se trata de Javascript no hay tail call optimization, por lo que la pila crecerá con cada llamada en una continuación, y que finalmente va a volver el hilo de control para el navegador. De todos modos, creo que es una buena abstracción.

Answer 10

Las mejoras se pueden utilizar para implementar excepciones, un depurador.

Answer 11

Si tiene que invocar una acción asincrónica y suspender la ejecución hasta que obtenga el resultado, normalmente buscará el resultado o colocará el resto del código en una devolución de llamada para que se ejecute mediante la acción asíncrona al finalizar.Con las continuaciones, no necesita hacer la ineficiente opción de sondeo, y no necesita envolver todo su código para que se ejecute después del evento de sincronización en una devolución de llamada; simplemente pasa el estado actual del código como devolución de llamada. - y el código se "despierta" efectivamente tan pronto como se completa la acción de asincronización.

Answer 12

El operador amb es un buen ejemplo que permite una programación declarativa parecida a un prólogo.

Mientras hablamos estoy codificando una pieza de software de composición musical en Scheme (soy un músico con 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 las matemáticas detrás funciona.)

Utilizando el operador amb solo puedo rellenar las restricciones que una melodía debe cumplir y dejar que Scheme averigüe el resultado.

Es probable que las continuas se incluyan en el Esquema debido a la filosofía del lenguaje. Scheme es un marco que le permite conocer cualquier paradigma de programación encontrado en otro idioma mediante la definición de bibliotecas en Scheme. Las mejoras son para crear sus propias estructuras de control abstracto como 'retorno', 'pausa' o para habilitar la programación declarativa. Scheme es más "generalizador" y suplica que dichos constructos también puedan ser especificados por el programador.