scheme callcc

scheme - ¿Cómo funciona el rompecabezas yin-yang?



callcc (6)

Comprender el esquema

Creo que al menos la mitad del problema para comprender este rompecabezas es la sintaxis Scheme, con la cual la mayoría no está familiarizada.

En primer lugar, personalmente encuentro que la call/cc x es más difícil de comprender que la alternativa equivalente, x get/cc . Todavía llama a x, pasando la continuación actual , pero de alguna manera es más susceptible de ser representado en mi circuito cerebral.

Con esto en mente, el constructo (call-with-current-continuation (lambda (c) c)) convierte simplemente en get-cc . Ahora estamos a esto:

(let* ((yin ((lambda (cc) (display #/@) cc) get-cc)) (yang ((lambda (cc) (display #/*) cc) get-cc)) ) (yin yang))

El siguiente paso es el cuerpo de la lambda interna. (display #/@) cc , en la sintaxis más familiar (para mí, de todos modos) significa print @; return cc; print @; return cc; . Mientras estamos en eso, también reescribamos lambda (cc) body como function (arg) { body } , eliminamos un montón de paréntesis y cambiamos las llamadas a la sintaxis tipo C para obtener esto:

(let* yin = (function(arg) { print @; return arg; })(get-cc) yang = (function(arg) { print *; return arg; })(get-cc) yin(yang))

Está empezando a tener más sentido ahora. Ahora es un pequeño paso para reescribir esto completamente en sintaxis tipo C (o similar a JavaScript, si lo prefiere), para obtener esto:

var yin, yang; yin = (function(arg) { print @; return arg; })(get-cc); yang = (function(arg) { print *; return arg; })(get-cc); yin(yang);

¡La parte más difícil ha terminado, hemos decodificado esto de Scheme! Es una broma; solo fue difícil porque no tenía experiencia previa con Scheme. Entonces, vamos a averiguar cómo funciona esto en realidad.

Una guía sobre las continuaciones

Observe el núcleo extrañamente formulado de yin y yang: define una función y luego la llama inmediatamente . Se parece a (function(a,b) { return a+b; })(2, 3) , que se puede simplificar a 5 . Pero simplificar las llamadas dentro de yin / yang sería un error, porque no le estamos pasando un valor ordinario. Estamos pasando la función una continuación .

Una continuación es una bestia extraña a primera vista. Considere el programa mucho más simple:

var x = get-cc; print x; x(5);

Inicialmente, x se establece en el objeto de continuación actual (tráiganme), y se ejecuta print x , imprimiendo algo así como <ContinuationObject> . Hasta aquí todo bien.

Pero una continuación es como una función; se puede invocar con un argumento. Lo que hace es: tomar el argumento, y luego saltar a donde sea que se creó esa continuación, restaurar todo el contexto y hacerlo de modo que get-cc devuelva este argumento.

En nuestro ejemplo, el argumento es 5 , así que básicamente volvemos al medio de esa declaración var x = get-cc , solo que esta vez get-cc devuelve 5 . Entonces x convierte en 5 , y la siguiente instrucción continúa imprimiéndose 5. Después de eso tratamos de llamar al 5(5) , que es un tipo de error, y el programa falla.

Observe que llamar a la continuación es un salto , no una llamada. Nunca regresa a donde se llamó a la continuación. Eso es importante.

Cómo funciona el programa

Si siguió eso, entonces no se ilusione: esta parte es realmente la más difícil. Aquí está nuestro programa de nuevo, descartando las declaraciones de variables porque de todos modos es un pseudocódigo:

yin = (function(arg) { print @; return arg; })(get-cc); yang = (function(arg) { print *; return arg; })(get-cc); yin(yang);

La primera vez que se golpean las líneas 1 y 2, ahora son simples: obtener la continuación, llamar a la función (arg), imprimir @ , regresar, almacenar esa continuación en yin . Lo mismo con yang . Ahora imprimimos @* .

Luego, llamamos a la continuación en yin , pasándola yang . Esto nos hace saltar a la línea 1, justo dentro de ese get-cc, y hacer que regrese yang lugar. El valor de yang ahora se pasa a la función, que imprime @ , y luego devuelve el valor de yang . Ahora a yin se le asigna la continuación que tiene yang . A continuación, procedemos a la línea 2: obtener c / c, imprimir * , almacenar la c / c en yang . Ahora tenemos @*@* . Y, por último, vamos a la línea 3.

Recuerde que yin ahora tiene la continuación de cuando se ejecutó por primera vez la línea 2. Así que saltamos a la línea 2, imprimimos un segundo * y actualizamos yang . Ahora tenemos @*@** . Por último, llame de nuevo a la continuación de yin , que saltará a la línea 1, imprimiendo un @ . Y así. Francamente, en este momento mi cerebro arroja una excepción OutOfMemory y pierdo la pista de todo. ¡Pero al menos llegamos a @*@** !

Esto es difícil de seguir y aún más difícil de explicar, obviamente. La forma perfecta de hacer esto sería pasar a través de él en un depurador que puede representar continuaciones, pero desafortunadamente, no conozco ninguna. Espero que hayas disfrutado esto; Ciertamente tengo.

Estoy tratando de captar la semántica de call / cc en Scheme, y la página de Wikipedia en continuaciones muestra el rompecabezas de yin-yang como un ejemplo:

(let* ((yin ((lambda (cc) (display #/@) cc) (call-with-current-continuation (lambda (c) c)))) (yang ((lambda (cc) (display #/*) cc) (call-with-current-continuation (lambda (c) c)))) ) (yin yang))

Debería salir @*@**@***@****@... pero no entiendo por qué; Esperaría que salga @*@********* ...

¿Alguien puede explicar en detalle por qué el rompecabezas yin-yang funciona de la manera en que funciona?

Como dijo otra respuesta, primero simplificamos (call-with-current-continuation (lambda (c) c)) con get-cc .

(let* ((yin ((lambda (cc) (display #/@) cc) get-cc)) (yang ((lambda (cc) (display #/*) cc) get-cc)) ) (yin yang))

Ahora, los dos lambda son solo una función idéntica asociada a los efectos secundarios. Llamemos a esas funciones f (para display #/@ ) g (para display #/* ).

(let* ((yin (f get-cc)) (yang (g get-cc))) (yin yang))

A continuación, tenemos que calcular la orden de evaluación. Para ser claros, presentaré una "expresión de paso" que hace que cada paso de evaluación sea explícito. Primero preguntemos: ¿qué es lo que la función anterior requiere?

Requiere definiciones de f y g . En la expresión de paso, escribimos

s0 f g =>

El primer paso es calcular yin , pero eso requiere una evaluación de (f get-cc) , y la posterior requiere get-cc .

En términos generales, get-cc le da un valor que representa la "continuación actual". Digamos que esto es s1 ya que este es el siguiente paso. Entonces escribimos

s0 f g => s1 f g ? s1 f g cc =>

Tenga en cuenta que los parámetros no tienen alcance, lo que significa que f y g en s0 y s1 no son necesariamente iguales y solo deben usarse dentro del paso actual. Esto hace que la información de contexto sea explícita. Ahora, ¿cuál es el valor de cc ? Como es una "continuación actual", tiene el mismo tipo de s1 con f y g vinculados al mismo valor.

s0 f g => s1 f g (s1 f g) s1 f g cc =>

Una vez que tenemos cc , podemos evaluar f get-cc . Además, dado que f no se usa en el siguiente código, no es necesario que transmita este valor.

s0 f g => s1 f g (s1 f g) s1 f g cc => s2 g (f cc) s2 g yin =>

El siguiente es el similar para yang . Pero ahora tenemos un valor más para transmitir: yin .

s0 f g => s1 f g (s1 f g) s1 f g cc => s2 g (f cc) s2 g yin => s3 g yin (s3 g yin) s3 g yin cc => s4 yin (g cc) s4 yin yang =>

Finalmente, el último paso es aplicar yang a yin .

s0 f g => s1 f g (s1 f g) s1 f g cc => s2 g (f cc) s2 g yin => s3 g yin (s3 g yin) s3 g yin cc => s4 yin (g cc) s4 yin yang => yin yang

Esto terminó la construcción de la expresión de paso. Traducirlo a Scheme es simple:

(let* ([s4 (lambda (yin yang) (yin yang))] [s3 (lambda (yin cc) (s4 yin (g cc))] [s2 (lambda (yin) (s3 yin ((lambda (cc) (s3 yin cc))))] [s1 (lambda (cc) (s2 (f cc)))]) (s1 s1))

El orden de evaluación detallado (aquí el lambda dentro del cuerpo de s2 simplemente se expresó como una evaluación parcial s3 yin lugar de (lambda (cc) (s3 yin cc)) ):

(s1 s1) => (s2 (f s1)) => @|(s2 s1) => @|(s3 s1 (s3 s1)) => @|(s4 s1 (g (s3 s1))) => @*|(s4 s1 (s3 s1)) => @*|(s1 (s3 s1)) => @*|(s2 (f (s3 s1))) => @*@|(s2 (s3 s1)) => @*@|(s2 (s3 s1)) => @*@|(s3 (s3 s1) (s3 (s3 s1))) => @*@|(s4 (s3 s1) (g (s3 (s3 s1)))) => @*@*|(s4 (s3 s1) (s3 (s3 s1))) => @*@*|(s3 s1 (s3 (s3 s1))) => @*@*|(s4 s1 (g (s3 (s3 s1)))) => @*@**|(s4 s1 (s3 (s3 s1))) => @*@**|(s1 (s3 (s3 s1))) => ...

(Recuerde, al evaluar s2 o s4 , el parámetro se evaluará primero

El rompecabezas YinYang está escrito en Scheme. Supongo que sabes la sintaxis básica de Scheme.

Pero supongo que no sabes let* o call-with-current-continuation , explicaré estas dos palabras clave.

Explique let*

Si ya lo sabe, puede omitir Explain call-with-current-continuation

let* , que se parece a let , actúa como let , pero evaluará sus variables definidas (the (yin ...) y (yang ...) ) uno por uno y con entusiasmo. Eso significa que primero evaluará yin y que yang .

Puedes leer más aquí: Usando Let in Scheme

Explicar call-with-current-continuation

Si ya lo sabes, puedes saltarte al Yin-Yang puzzle .

Es un poco difícil explicar call-with-current-continuation . Entonces usaré una metáfora para explicarlo.

Imagen de un asistente que conocía un hechizo, que era call-with-current-continuation . Una vez que lanzara el hechizo, crearía un nuevo universo y se enviaría a él. Pero no podía hacer nada en el nuevo universo, sino esperar que alguien lo llamara. Una vez que se lo llamara , el mago volvería al universo original, teniendo al pobre tipo, ''alguien'', en la mano, y continuaría con su vida de mago. Si no lo llamaron, cuando el nuevo universo terminó, el asistente también regresó al universo original.

Ok, seamos más técnicos.

call-with-current-continuation es una función que acepta una función como parámetro. Una vez que llame a call-with-current-continuation con una función F , empacará el entorno de ejecución actual, que se llama current-continuation , como un parámetro C , y lo enviará a la función F , y ejecutará F Entonces todo el programa se convierte en (FC) . O siendo más JavaScript: F(C); . C actúa como una función. Si no se llama a F en F , entonces es un programa ordinario, cuando F vuelve, call-with-current-continuation tiene un valor como el valor de retorno de F Pero si se llama a C con un parámetro V , cambiará todo el programa nuevamente. El programa cambia de nuevo a un estado cuando se call-with-current-continuation . Pero ahora call-with-current-continuation produce un valor, que es V Y el programa continúa.

Tomemos un ejemplo.

(define (f return) (return 2) 3) (display (f whatever)) ;; 3 (display (call-with-current-continuation f)) ;; 2 (display (call-with-current-continuation (lambda (x) 4))) ;; 4

La primera display salida 3 , de la causa.

Pero la segunda display salida 2 . ¿Por qué?

Vamos a sumergirnos en eso.

Al evaluar (display (call-with-current-continuation f)) , primero evaluará (call-with-current-continuation f) . Sabemos que cambiará todo el programa a

(f C)

Considerando la definición de f , tiene a (return 2) . Debemos evaluar (C 2) . Ahí es cuando se llama a la continuation . Entonces cambia todo el programa a

(display (call-with-current-continuation f))

Pero ahora, call-with-current-continuation tiene el valor 2 . Entonces el programa se convierte en:

(display 2)

Rompecabezas de Yin-Yang

Veamos el acertijo.

(let* ((yin ((lambda (cc) (display #/@) cc) (call-with-current-continuation (lambda (c) c)))) (yang ((lambda (cc) (display #/*) cc) (call-with-current-continuation (lambda (c) c))))) (yin yang))

Hagámoslo más legible.

(define (id c) c) (define (f cc) (display #/@) cc) (define (g cc) (display #/*) cc) (let* ((yin (f (call-with-current-continuation id))) (yang (g (call-with-current-continuation id)))) (yin yang))

Vamos a ejecutar el programa en nuestro cerebro.

Ronda 0

let* hacernos evaluar primero yin . yin es

(f (call-with-current-continuation id))

Entonces evaluamos primero (call-with-current-continuation id) . Encapsula el entorno actual, que llamamos C_0 para distinguir con otra continuación en la línea de tiempo, y entra en un universo completamente nuevo: id . Pero id simplemente devuelve C_0 .

Debemos recordar lo que es C_0 . C_0 es un programa como este:

(let* ((yin (f ###)) (yang (g (call-with-current-continuation id)))) (yin yang))

### es un marcador de posición, que en el futuro se rellenará con el valor que C_0 recupera.

Pero id simplemente devuelve C_0 . No llama a C_0 . Si llama, ingresaremos al universo de C_0 . Pero no fue así, entonces continuamos evaluando yin .

(f C_0) ;; yields C_0

f es una función como id , pero tiene un efecto secundario, dando como resultado @ .

Entonces, el programa dio como resultado @ y dejó que yin fuera C_0 . Ahora el programa se convierte

(let* ((yin C_0) (yang (g (call-with-current-continuation id)))) (yin yang))

Después de evaluar yin , comenzamos a evaluar yang . yang es

(g (call-with-current-continuation id))

call-with-current-continuation aquí crea otra continuación, llamada C_1 . C_1 es:

(let* ((yin C_0) (yang (g ###))) (yin yang))

### es marcador de posición. Tenga en cuenta que en esta continuación, se determina el valor de yin (eso es lo que let* hacer). Estamos seguros de que el valor de yin es C_0 aquí.

Dado que (id C_1) es C_1 , entonces el valor de yang es

(g C_1)

g tiene un efecto secundario: produce * . Entonces el programa sí.

El valor de yang ahora es C_1 .

Por ahora, hemos mostrado @*

Entonces ahora se convierte en:

(let* ((yin C_0) (yang C_1)) (yin yang))

Como se resuelven tanto yin como yang , debemos evaluar (yin yang) . Sus

(C_0 C_1)

¡Santo SH * T!

Pero finalmente, se llama C_0 . Entonces volamos al universo C_0 y olvidamos todo acerca de estas sh * ts. Nunca volveremos a este universo otra vez.

La ronda 1

C_0 toma con C_1 vuelta. El programa ahora se convierte en (Si olvida lo que significa C_0 , regrese para verlo):

(let* ((yin (f C_1)) (yang (g (call-with-current-continuation id)))) (yin yang))

Ah, descubrimos que el valor de yin aún no está determinado. Entonces lo evaluamos. En el proceso de evaluación de yin , generamos un efecto secundario de @ as f . Y sabemos que yin es C_1 ahora.

Comenzamos a evaluar yang , nos encontramos con call-with-current-continuation nuevamente. Somos practicados Creamos una continuación C_2 que significa:

(let* ((yin C_1) (yang (g ###))) (yin yang))

Y mostramos un * como g ejecutándose. Y venimos aquí

(let* ((yin C_1) (yang C_2)) (yin yang))

Así que tenemos:

(C_1 C_2)

Ya sabes a dónde vamos. Vamos al universo de C_1 . Lo recordamos de la memoria (o copiar y pegar desde la página web). Esto es ahora:

(let* ((yin C_0) (yang (g C_2))) (yin yang))

Sabemos que en el universo de C_1 , el valor de yin ha sido determinado. Entonces comenzamos a evaluar yang . A medida que se practique, le diré directamente que muestra * y se convierte en:

(C_0 C_2)

Ahora imprimimos @*@** , y vamos a tomar el universo de C_2 con C_2 .

La ronda 2

A medida que nos practicamos, les diré que mostramos ''@'', yin es C_2 y creamos una nueva continuación C_3 , que significa:

(let* ((yin C_2) (yang (g ###))) (yin yang))

Y mostramos * , yang es C_3 , y se convierte

(C_2 C_3)

Y podemos continuar Pero me detendré aquí, les mostré cuáles son los primeros resultados del rompecabezas de Yin-Yang.

¿Por qué el número de * aumenta?

Ahora tu cabeza está llena de detalles. Haré un resumen para ti.

Usaré una sintaxis similar a Haskell para simplificar. Y cc es la abreviatura de call-with-current-continuation .

Cuando #C_i# está entre corchetes con # , significa que la continuación es crear aquí. ; significa salida

yin = f cc id yang = g cc id yin yang --- yin = f #C_0# ; @ yang = g cc id yin yang --- yin = C_0 yang = g #C_1# ; * yin yang --- C_0 C_1 --- yin = f C_1 ; @ yang = g #C_2# ; * yin yang --- C_1 C_2 --- yin = C_0 yang = g C_2 ; * yin yang --- C_0 C_2 --- yin = f C_2 ; @ yang = g #C_3#; * yin yang --- C_2 C_3 --- yin = C_1 yang = g C_3 ; * yin yang --- C_1 C_3 --- yin = C_0 yang = g C_3 ; * yin yang --- C_0 C_3

Si observa cuidadosamente, será obvio para usted que

  1. Hay muchos universos (de hecho, infinitos), pero C_0 es el único universo que comenzó con f . Otros es iniciado por g .
  2. C_0 C_n siempre hace una nueva continuación C_max . Es porque C_0 es el primer universo que g cc id no se ha ejecutado.
  3. C_0 C_n también muestra @ . C_n C_m que n no es 0 mostrará * .
  4. Tiempo a tiempo el programa se deduce a C_0 C_n , y demostraré que C_0 C_n está separado por más y más expresiones, lo que lleva a @*@**@***...

Un poco de matemáticas

Asumir (n! = 0) es el número más grande en todas las continuaciones, y luego se llama C_0 C_n .

Suposición: cuando se llama C_n , C_n es la continuación numerada máxima actual.

Ahora es creado por C_0 C_n esta manera:

yin = f C_n ; @ yang = g #C_{n+1}# yin yang

Entonces concluimos que:

Teorema I. Si se llama C_0 C_n , producirá una continuación , en donde yin es C_n .

Luego, el siguiente paso es C_n C_{n+1} .

yin = C_{n-1} yang = g C_{n+1} ; * yin yang

La razón por la cual yin es C_{n-1} es que cuando C_n siendo creado obedecía el teorema I.

Y luego se llama C_{n-1} C_{n+1} , y sabemos cuándo se creó C_{n-1} , también obedeció el Teorema I. Entonces tenemos C_{n-2} C_{n+1} .

C_{n+1} es la variación. Entonces tenemos el segundo teorema:

Teorema II. Si se C_n C_m que n < m C_n C_m n > 0 , se convertirá en C_{n-1} C_m .

Y hemos verificado manualmente C_0 C_1 C_2 C_3 . Ellos obedecen la Asunción y todos los Teoremas. Y sabemos cómo se crean los primeros @ y * .

Entonces podemos escribir patrones a continuación.

C_0 C_1 ; @ * C_[1-0] C_2 ; @ * * C_[2-0] C_3 ; @ * * * ...

No es tan estricto, pero me gustaría escribir:

QED

No creo entender esto completamente, pero solo puedo pensar en una explicación ( extremadamente ondulada) para esto:

  • Los primeros @ y * se imprimen cuando yin y yang se unen por primera vez en let* . (yin yang) se aplica, y vuelve a la parte superior, justo después de que finaliza la primera llamada / cc.
  • Los siguientes @ y * se imprimen, luego otro * se imprime porque esta vez, yin se vuelve a vincular al valor de la segunda llamada / cc.
  • (yin yang) se aplica de nuevo, pero esta vez se está ejecutando en el entorno del yang original , donde yin está vinculado a la primera llamada / cc, por lo que el control vuelve a imprimir otro @. El argumento yang contiene la continuación que fue re-capturada en el segundo pase, que como ya hemos visto, dará como resultado la impresión ** . Entonces, en este tercer pase, se imprimirá @* , luego se invoca esta continuación de doble estrella, por lo que termina con 3 estrellas, y luego se vuelve a capturar esta continuación de triple estrella, ...

Reflexiones primero, posible respuesta al final.

Creo que el código se puede volver a escribir así:

; call (yin yang) (define (yy yin yang) (yin yang)) ; run (call-yy) to set it off (define (call-yy) (yy ( (lambda (cc) (display #/@) cc) (call/cc (lambda (c) c)) ) ( (lambda (cc) (display #/*) cc) (call/cc (lambda (c) c)) ) ) )

O con algunas declaraciones de visualización adicionales para ayudar a ver lo que está sucediendo:

; create current continuation and tell us when you do (define (ccc) (display "call/cc=") (call-with-current-continuation (lambda (c) (display c) (newline) c)) ) ; call (yin yang) (define (yy yin yang) (yin yang)) ; run (call-yy) to set it off (define (call-yy) (yy ( (lambda (cc) (display "yin : ") (display #/@) (display cc) (newline) cc) (ccc) ) ( (lambda (cc) (display "yang : ") (display #/*) (display cc) (newline) cc) (ccc) ) ) )

O así:

(define (ccc2) (call/cc (lambda (c) c)) ) (define (call-yy2) ( ( (lambda (cc) (display #/@) cc) (ccc2) ) ( (lambda (cc) (display #/*) cc) (ccc2) ) ) )

Posible respuesta

Esto puede no ser correcto, pero voy a intentarlo.

Creo que el punto clave es que una continuación ''llamada'' devuelve la pila a un estado anterior, como si nada más hubiera sucedido. Por supuesto, no sabe que lo estamos monitoreando mostrando los caracteres @ y * .

Inicialmente definimos yin como una continuación A que hará esto:

1. restore the stack to some previous point 2. display @ 3. assign a continuation to yin 4. compute a continuation X, display * and assign X to yang 5. evaluate yin with the continuation value of yang - (yin yang)

Pero si llamamos continuación de yang , sucede esto:

1. restore the stack to some point where yin was defined 2. display * 3. assign a continuation to yang 4. evaluate yin with the continuation value of yang - (yin yang)

Comenzamos aquí.

La primera vez que obtienes yin=A y yang=B como yin y yang se están inicializando.

The output is @*

(Ambas continuaciones A y B se calculan).

Ahora (yin yang) se evalúa como (AB) por primera vez.

Sabemos lo que hace A Hace esto:

1. restores the stack - back to the point where yin and yang were being initialised. 2. display @ 3. assign a continuation to yin - this time, it is B, we don''t compute it. 4. compute another continuation B'', display * and assign B'' to yang The output is now @*@* 5. evaluate yin (B) with the continuation value of yang (B'')

Ahora (yin yang) se evalúa como (B B'') .

Sabemos lo que B hace. Hace esto:

1. restore the stack - back to the point where yin was already initialised. 2. display * 3. assign a continuation to yang - this time, it is B'' The output is now @*@** 4. evaluate yin with the continuation value of yang (B'')

Dado que la pila se restauró al punto donde yin=A , (yin yang) se evalúa como (A B'') .

Sabemos lo que hace A Hace esto:

1. restores the stack - back to the point where yin and yang were being initialised. 2. display @ 3. assign a continuation to yin - this time, it is B'', we don''t compute it. 4. compute another continuation B", display * and assign B" to yang The output is now @*@**@* 5. evaluate yin (B'') with the continuation value of yang (B")

Sabemos lo que B'' hace. Hace esto:

1. restore the stack - back to the point where yin=B. 2. display * 3. assign a continuation to yang - this time, it is B" The output is now @*@**@** 4. evaluate yin (B) with the continuation value of yang (B")

Ahora (yin yang) se evalúa como (BB") .

Sabemos lo que B hace. Hace esto:

1. restore the stack - back to the point where yin=A and yang were being initialised. 2. display * 3. assign a continuation to yang - this time, it is B''" The output is now @*@**@*** 4. evaluate yin with the continuation value of yang (B''")

Dado que la pila se restauró al punto donde yin=A , (yin yang) se evalúa como (A B''") .

.......

Creo que tenemos un patrón ahora.

Cada vez que llamamos (yin yang) recorremos una pila de continuaciones B hasta que volvemos a yin=A y mostramos @ . Pasamos por la pila de continuaciones B escribimos un * cada vez.

(Estaría muy feliz si esto es más o menos correcto!)

Gracias por la pregunta.