Más simple ejemplo de continuaciones hacia atrás en el Esquema sin mutación explícita

Question

He escrito un pequeño intérprete de Scheme en C #, y se dio cuenta de que la forma en que había puesto en práctica, era muy fácil de añadir soporte para continuaciones adecuados.

Así que les añadí ... pero quiero "probar" que se forma en que me han añadido ellas es correcta.

Mi intérprete de Scheme sin embargo no tiene soporte para "mutando" estado -. Todo es inmutable

Por lo tanto, era bastante fácil de escribir una prueba unitaria para exponer continuaciones "hacia arriba":

AssertEqual(Eval("(call/cc (lambda (k) (+ 56 (k 3))))"), 3);

Sin embargo, también quiero escribir una unidad de prueba que demuestra que si la continuación "escapa" a continuación, que todavía funciona también:

AssertEqual(Eval("(call/cc (lambda (k) k))", <some continuation>);

Pero, por supuesto, lo anterior simplemente habría que probar "Tengo una continuación" ... no es que en realidad es una continuación válida.

Todos los ejemplos que puedo encontrar, sin embargo, siempre terminan con "Ajustar!" para demostrar la continuación escapado.

¿Qué es el ejemplo más sencillo esquema que demuestra el apoyo adecuado para continuaciones hacia atrás sin depender de la mutación?

¿Son revés continuaciones cualquier uso sin mutación? Estoy empezando a sospechar que no lo son, ya que sólo se podría utilizar para ejecutar exactamente el mismo cálculo de nuevo ... lo que no tiene sentido si no hay efectos secundarios. Es por esto que Haskell no tiene continuaciones?

Answer 1

No sé si este es el más simple, pero aquí es un ejemplo del uso revés continuaciones sin ninguna llamada a set! o similar:

(apply
  (lambda (k i) (if (> i 5) i (k (list k (* 2 i)))))
  (call/cc (lambda (k) (list k 1))))

Esto debe evaluar a 8.

Un poco más interesante es:

(apply
  (lambda (k i n) (if (= i 0) n (k (list k (- i 1) (* i n)))))
  (call/cc (lambda (k) (list k 6 1))))

que calcula 6! (es decir, se debe evaluar a 720).

Incluso se puede hacer lo mismo con let*:

(let* ((ka (call/cc (lambda (k) `(,k 1)))) (k (car ka)) (a (cadr ka)))
      (if (< a 5) (k `(,k ,(* 2 a))) a))

(Hombre, resaltado de sintaxis de stackoverflow falla masiva en el esquema.)

Answer 2

Creo que tienes razón - sin mutación, hacia atrás continuaciones no hacen nada que transmita continuaciones no puede

.

Answer 3

Esto es lo mejor que he llegado con:

AssertEqual(Eval("((call/cc (lambda (k) k)) (lambda (x) 5))", 5);

No es espectacular, pero es una continuación hacia atrás que luego "llamada" con la función real deseo invocar, una función que devuelve el número 5.

Ah y yo también he llegado con esto como un buen caso de prueba de unidad:

AssertEqual(Eval("((call/cc call/cc) (lambda (x) 5))", 5);

Estoy de acuerdo con Jacob B - No creo que sea tan útil sin estado mutable ... pero estaría todavía estaría interesado en un contraejemplo

.

Answer 4

Temas funcionales:

Puede utilizar un bucle recursivo para actualizar el estado sin mutación. incluyendo el estado de la siguiente continuación para ser llamado. Ahora bien, esto es más complicado que los otros ejemplos dados, pero lo único que necesitas es el bucle thread-1 y main. El otro hilo y la función de "actualización" están ahí para mostrar que continuaciones pueden ser utilizados para más de un ejemplo trivial. Además, para que este ejemplo funcione es necesario una aplicación con la let llamado. Esto puede traducirse en una forma equivalente hecha con definir declaraciones.

Ejemplo:

(let* ((update (lambda (data) data))                ;is identity to keep simple for example
       (thread-1                                    
         (lambda (cc)                               ;cc is the calling continuation
           (let loop ((cc cc)(state 0))
             (printf "--doing stuff       state:~A~N" state)
             (loop (call/cc cc)(+ state 1)))))      ;this is where the exit hapens
       (thread-2
         (lambda (data)                             ;returns the procedure to be used as 
           (lambda (cc)                             ;thread with data bound
             (let loop ((cc cc)(data data)(state 0))
               (printf "--doing other stuff state:~A~N" state)
               (loop (call/cc cc)(update data)(+ state 1)))))))
  (let main ((cur thread-1)(idle (thread-2 '()))(state 0))
    (printf "doing main stuff    state:~A~N" state)
    (if (< state 6)
        (main (call/cc idle) cur (+ state 1)))))

¿Qué salidas

doing main stuff    state:0
--doing other stuff state:0
doing main stuff    state:1
--doing stuff       state:0
doing main stuff    state:2
--doing other stuff state:1
doing main stuff    state:3
--doing stuff       state:1
doing main stuff    state:4
--doing other stuff state:2
doing main stuff    state:5
--doing stuff       state:2
doing main stuff    state:6