Ejemplo más simple de continuaciones hacia atrás en Scheme sin mutación explícita

Question

Escribí un pequeño intérprete de Scheme en C#, y me di cuenta de que, de la manera en que lo había implementado, era muy fácil agregar soporte para las continuaciones adecuadas.

Así que los agregué ... pero quiero "probar" que la forma en que los agregué es correcta.

Sin embargo, el intérprete de My Scheme no tiene soporte para el estado de "mutación": todo es inmutable.

así que era bastante fácil de escribir una prueba unitaria para exponer "hacia arriba" continuaciones:

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

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

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

Pero, por supuesto, lo anterior sería simplemente probar que "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 usando "set!" para demostrar la continuación escapada.

¿Cuál es el ejemplo de esquema más simple que demuestra un soporte adecuado para las continuidades hacia atrás sin depender de la mutación?

¿Las continuación hacia atrás se usan sin mutación? Estoy comenzando a sospechar que no lo son, porque solo podrías usarlo para ejecutar exactamente el mismo cálculo de nuevo ... lo cual no tiene sentido si no hay efectos secundarios. ¿Es por eso 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 debería 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 Usted 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)) 

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

Answer 2

Creo que tienes razón, sin mutaciones, las continuidades hacia atrás no hacen nada que las continuaciones directas no puedan hacer.

Answer 3

Esto es lo mejor que he llegado con:

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

No es sorprendente, pero es una continuación hacia atrás que luego "llamar" con la función real que 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 le todavía debe estar interesado en un contraejemplo.

Answer 4

Hilos funcionales:

se puede utilizar un bucle recursivo para actualizar el estado sin mutación. incluyendo el estado de la próxima continuación que se llamará. Ahora, esto es más complicado que los otros ejemplos dados, pero todo lo que realmente necesita es el thread-1 y main. El otro subproceso y la función de "actualización" están ahí para mostrar que las continuaciones pueden usarse para más que un ejemplo trivial. Además, para que funcione este ejemplo, necesita una implementación con el nombre let. Esto se puede traducir a una forma equivalente hecha con declaraciones definidas.

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))))) 

que da salida a

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