lisp - continuaciones del esquema para los maniquíes

scheme continuations

Question

Por mi vida, no puedo entender las continuaciones. Creo que el problema se deriva del hecho de que no entiendo para qué sirven . Todos los ejemplos que he encontrado en libros o en línea son muy triviales. Me hacen preguntarme, ¿por qué alguien querría continuar?

Este es un ejemplo típico poco práctico, de TSPL , que creo que es un libro bastante reconocido sobre el tema. En inglés, describen la continuación como "qué hacer" con el resultado de un cálculo. OK, eso es algo comprensible.

Luego, el segundo ejemplo dado:

(call/cc
  (lambda (k)
    (* 5 (k 4)))) => 4 

¿¿Como tiene sentido eso?? k ni siquiera está definido! ¿Cómo se puede evaluar este código, cuando (k 4) ni siquiera se puede calcular? Sin mencionar, ¿cómo call/cc sabe cómo extraer el argumento 4 a la expresión más interna y devolverlo? ¿Qué le sucede a (* 5 .. ? Si esta expresión más externa se descarta, ¿por qué incluso escribirla?

Luego, un ejemplo "menos" trivial es cómo usar call/cc para proporcionar una salida no local desde una recursión. Eso suena como una directiva de control de flujo, es decir, como break/return en un lenguaje imperativo, y no un cálculo.

¿Y cuál es el propósito de pasar por estos movimientos? Si alguien necesita el resultado del cálculo, ¿por qué no simplemente almacenarlo y recuperarlo más tarde, según sea necesario?

Answer 1

Aquí está el texto de mis notas de clase: http://tmp.barzilay.org/cont.txt . Se basa en varias fuentes y está muy extendido. Tiene motivaciones, explicaciones básicas, explicaciones más avanzadas sobre cómo se hace, y un buen número de ejemplos que van de lo simple a lo avanzado, e incluso una discusión rápida de las continuaciones delimitadas.

(Traté de jugar poniendo todo el texto aquí, pero como esperaba, 120k de texto no es algo que haga TAN feliz.

Answer 2

No intentaré explicar todos los lugares donde las continuaciones pueden ser útiles, pero espero poder dar ejemplos breves del lugar principal donde he encontrado que las continuaciones son útiles en mi propia experiencia. En lugar de hablar sobre la call/cc Scheme, me gustaría centrar la atención en el estilo de paso de continuación . En algunos lenguajes de programación, las variables pueden tener un alcance dinámico, y en lenguajes sin un alcance dinámico, se pueden usar repeticiones con variables globales (suponiendo que no haya problemas de código de subprocesos múltiples, etc.). Por ejemplo, supongamos que hay una lista de secuencias de registro activas actualmente, *logging-streams* , y que queremos llamar a la function en un entorno dinámico donde *logging-streams* se aumenta con logging-stream-x . En Common Lisp podemos hacer

(let ((*logging-streams* (cons logging-stream-x *logging-streams*)))
  (function))

Si no tenemos variables de alcance dinámico, como en Esquema, todavía podemos hacer

(let ((old-streams *logging-streams*))
  (set! *logging-streams* (cons logging-stream-x *logging-streams*)
  (let ((result (function)))
    (set! *logging-streams* old-streams)
    result))

Ahora supongamos que realmente nos dan un árbol de contras cuyas hojas no nil son secuencias de registro, todas las cuales deberían estar en *logging-streams* cuando se llama a la function . Tenemos dos opciones:

1. Podemos aplanar el árbol, recopilar todas las secuencias de registro, extender *logging-streams* y luego llamar a la function .
2. Podemos, usando el estilo de paso de continuación, atravesar el árbol, extendiendo gradualmente *logging-streams* , y finalmente llamar a la function cuando no haya más tree para atravesar.

Opción 2 se ve algo así como

(defparameter *logging-streams* ''())

(defun extend-streams (stream-tree continuation)
  (cond
    ;; a null leaf
    ((null stream-tree)
     (funcall continuation))
    ;; a non-null leaf
    ((atom stream-tree)
     (let ((*logging-streams* (cons stream-tree *logging-streams*)))
       (funcall continuation)))
    ;; a cons cell
    (t
     (extend-streams (car stream-tree)
                     #''(lambda ()
                         (extend-streams (cdr stream-tree)
                                         continuation))))))

Con esta definición, tenemos

CL-USER> (extend-streams
          ''((a b) (c (d e)))
          #''(lambda ()
              (print *logging-streams*)))
=> (E D C B A) 

Ahora, ¿hubo algo útil acerca de esto? En este caso, probablemente no. Algunos beneficios menores podrían ser que extend-streams son recurrentes a la cola, por lo que no tenemos mucho uso de pila, aunque los cierres intermedios lo compensan en el espacio de almacenamiento dinámico. Tenemos el hecho de que la continuación eventual se ejecuta en el ámbito dinámico de cualquier material intermedio que se configuren en los extend-streams . En este caso, eso no es tan importante, pero en otros casos puede serlo.

Ser capaz de abstraer parte del flujo de control y tener salidas no locales, o poder realizar un cálculo en algún lugar de hace un tiempo, puede ser muy útil. Esto puede ser útil en la búsqueda de seguimiento, por ejemplo. A continuación se incluye un programa de resolución de cálculo proposicional de estilo de paso de continuación para fórmulas en las que una fórmula es un símbolo (un literal proposicional), o una lista de la forma (not formula) , (and left right) , o (or left right) .

(defun fail ()
  ''(() () fail))

(defun satisfy (formula 
                &optional 
                (positives ''())
                (negatives ''())
                (succeed #''(lambda (ps ns retry) `(,ps ,ns ,retry)))
                (retry ''fail))
  ;; succeed is a function of three arguments: a list of positive literals,
  ;; a list of negative literals.  retry is a function of zero
  ;; arguments, and is used to `try again` from the last place that a
  ;; choice was made.
  (if (symbolp formula)
      (if (member formula negatives) 
          (funcall retry)
          (funcall succeed (adjoin formula positives) negatives retry))
      (destructuring-bind (op left &optional right) formula
        (case op
          ((not)
           (satisfy left negatives positives 
                    #''(lambda (negatives positives retry)
                        (funcall succeed positives negatives retry))
                    retry))
          ((and) 
           (satisfy left positives negatives
                    #''(lambda (positives negatives retry)
                        (satisfy right positives negatives succeed retry))
                    retry))
          ((or)
           (satisfy left positives negatives
                    succeed
                    #''(lambda ()
                        (satisfy right positives negatives
                                 succeed retry))))))))

Si se encuentra una asignación satisfactoria, entonces se llama a success con tres argumentos: la lista de literales positivos, la lista de literales negativos y la función que puede reintentar la búsqueda (es decir, intentar encontrar otra solución). Por ejemplo:

CL-USER> (satisfy ''(and p (not p)))
(NIL NIL FAIL)
CL-USER> (satisfy ''(or p q))
((P) NIL #<CLOSURE (LAMBDA #) {1002B99469}>)
CL-USER> (satisfy ''(and (or p q) (and (not p) r)))
((R Q) (P) FAIL)

El segundo caso es interesante, ya que el tercer resultado no es FAIL , sino una función que se puede llamar que intentará encontrar otra solución. En este caso, podemos ver que (or pq) es satisfactorio al hacer p o q verdad:

CL-USER> (destructuring-bind (ps ns retry) (satisfy ''(or p q))
           (declare (ignore ps ns))
           (funcall retry))
((Q) NIL FAIL)

Eso hubiera sido muy difícil de hacer si no estuviéramos usando un estilo de paso de continuación en el que podamos guardar el flujo alternativo y volver a él más tarde. Usando esto, podemos hacer algunas cosas inteligentes, como recoger todas las tareas satisfactorias:

(defun satisfy-all (formula &aux (assignments ''()) retry)
  (setf retry #''(lambda () 
                  (satisfy formula ''() ''()
                           #''(lambda (ps ns new-retry)
                               (push (list ps ns) assignments)
                               (setf retry new-retry))
                           ''fail)))
  (loop while (not (eq retry ''fail))
     do (funcall retry)
     finally (return assignments)))

CL-USER> (satisfy-all ''(or p (or (and q (not r)) (or r s))))
(((S) NIL)   ; make S true
 ((R) NIL)   ; make R true
 ((Q) (R))   ; make Q true and R false
 ((P) NIL))  ; make P true

Podríamos cambiar el loop un poco y obtener solo n asignaciones, hasta algunas n , o variaciones en ese tema. Muchas veces, el estilo de paso de continuación no es necesario, o puede hacer que el código sea difícil de mantener y entender, pero en los casos en que es útil, puede hacer que algunas cosas muy difíciles sean bastante fáciles.

Answer 3

Olvídate de call/cc por un momento. Cada expresión / declaración, en cualquier lenguaje de programación, tiene una continuación, que es lo que haces con el resultado. En C, por ejemplo,

x = (1 + (2 * 3)); 
printf ("Done");

tiene la continuación de la tarea de matemáticas siendo printf(...) ; la continuación de (2 * 3) es ''agregar 1; asignar a x; printf (...) ''. Conceptualmente, la continuación está allí tanto si tiene acceso como si no. Piense por un momento qué información necesita para la continuación: la información es 1) el estado de la memoria del montón (en general), 2) la pila, 3) cualquier registro y 4) el contador del programa.

Por lo tanto, existen continuaciones, pero generalmente solo son implícitas y no se puede acceder a ellas.

En Esquema, y ​​en algunos otros idiomas, tiene acceso a la continuación. Esencialmente, detrás de su espalda, el compilador + el tiempo de ejecución reúne toda la información necesaria para una continuación, la almacena (generalmente en el montón) y le da un control de la misma. El identificador que obtiene es la función ''k'': si llama a esa función, continuará exactamente después del punto de call/cc . Es importante destacar que puede llamar a esa función varias veces y siempre continuará después del punto de call/cc .

Veamos algunos ejemplos:

> (+ 2 (call/cc (lambda (cont) 3)))
5

En lo anterior, el resultado de call/cc es el resultado de la lambda que es 3. No se invocó la continuación.

Ahora invocemos la continuación:

> (+ 2 (call/cc (lambda (cont) (cont 10) 3)))
12

Al invocar la continuación, omitimos cualquier cosa después de la invocación y continuamos directamente en el punto de call/cc . Con (cont 10) la continuación devuelve 10 que se agrega a 2 para 12.

Ahora salvemos la continuación.

> (define add-2 #f)
> (+ 2 (call/cc (lambda (cont) (set! add-2 cont) 3)))
5
> (add-2 10)
12
> (add-2 100)
102

Al guardar la continuación, podemos usarla como nos plazca para "saltar a" cualquier cálculo seguido del punto de call/cc .

A menudo se utilizan continuaciones para una salida no local. Piense en una función que devolverá una lista a menos que haya algún problema en el punto en el que se devolverá ''() .

(define (hairy-list-function list)
  (call/cc
    (lambda (cont)
       ;; process the list ...

       (when (a-problem-arises? ...)
         (cont ''()))

       ;; continue processing the list ...

       value-to-return)))

Answer 4

TL; DR : las continuaciones son solo GOTO capturados, con valores, más o menos.

El ejemplo sobre el que preguntas,

(call/cc
  (lambda (k)
    ;;;;;;;;;;;;;;;;
    (* 5 (k 4))                     ;; body of code
    ;;;;;;;;;;;;;;;;
    )) => 4 

se puede traducir aproximadamente a, por ejemplo, Common Lisp, como

(prog (k retval)
    (setq k (lambda (x)             ;; capture the current continuation:
                    (setq retval x) ;;   set! the return value
                    (go EXIT)))     ;;   and jump to exit point

    (setq retval                    ;; get the value of the last expression,
      (progn                        ;;   as usual, in the
         ;;;;;;;;;;;;;;;;
         (* 5 (funcall k 4))        ;; body of code
         ;;;;;;;;;;;;;;;;
         ))
  EXIT                              ;; the goto label
    (return retval))

Esto es sólo una ilustración; en Common Lisp no podemos saltar de nuevo en el tag tag PROG después de haberlo salido la primera vez. Pero en el esquema, con continuaciones reales, podemos. Si establecemos alguna variable global dentro del cuerpo de la función llamada por call/cc , digamos (setq qq k) , en Scheme podemos llamarla en cualquier momento posterior, desde cualquier lugar, volviendo a ingresar al mismo contexto (ej. (qq 42) ).

El punto es que el cuerpo del formulario de call/cc puede contener un if o una expresión cond . Puede llamar a la continuación solo en algunos casos, y en otros retorna normalmente, evaluando todas las expresiones en el cuerpo del código y devolviendo el último valor, como de costumbre. Allí puede haber una profunda recursión. Al llamar a la continuación capturada se logra una salida inmediata.

Así que aquí vemos que k está definido. Está definido por la call/cc llamada call/cc . Cuando se (call/cc g) , llama a su argumento con la continuación actual: (g the-current-continuation) . the current-continuation es un "procedimiento de escape" que apunta al punto de retorno del formulario de call/cc . Llamar significa proporcionar un valor como si fuera devuelto por el propio formulario call/cc .

Así que lo anterior resulta en

((lambda(k) (* 5 (k 4))) the-current-continuation) ==>

(* 5 (the-current-continuation 4)) ==>

; to call the-current-continuation means to return the value from
; the call/cc form, so, jump to the return point, and return the value:

4