lambda - programing - ¿Qué es call/cc?

que es un scheme

Question

He intentado varias veces entender el concepto de continuations y call/cc . Cada intento fue un fracaso. ¿Puede alguien explicarme estos conceptos, idealmente con ejemplos más realistas que estos en Wikipedia o en otras publicaciones de SO?

Tengo experiencia en programación web y OOP. También entiendo el ensamble 6502 y tuve una escalada menor con Erlang. Sin embargo, aún así, no puedo entender mi llamada / cc.

Answer 1

Cuando intentaba entender call / cc, encontré que esta página call-with-current-continuation-for-C-programmers era útil.

Answer 2

Eche un vistazo a la descripción e implementación de call / cc para FScheme: http://blogs.msdn.com/b/ashleyf/archive/2010/02/11/turning-your-brain-inside-out-with-continuations.aspx

Answer 3

El modelo que utilicé para comprender las continuaciones desde un punto de vista imperativo es que se trata de una copia de la pila de llamadas combinada con un puntero a la siguiente instrucción.

Call / cc llama a una función (pasada como argumento) con la continuación como argumento.

Answer 4

Hay varios niveles para entender call / cc. Primero necesita comprender los términos y cómo funciona el mecanismo. Entonces se necesita una comprensión de cómo y cuándo se usa call / cc en la programación de la "vida real".

El primer nivel se puede alcanzar estudiando CPS, pero hay alternativas.

Para el segundo nivel, recomiendo el siguiente clásico de Friedman.

Daniel P. Friedman. "Aplicaciones de Continuations: tutorial invitado". Principios de 1988 de lenguajes de programación (POPL88). Enero de 1988.

Answer 5

Imagina que tu guión es una etapa de videojuego. Call / cc es como una etapa extra.

En cuanto lo toca, se lo transfiere a la etapa de bonificación (es decir, la definición de la función pasada como argumento para llamar / cc [f en este caso]).

Las etapas de bonificación son diferentes de las etapas ordinarias porque generalmente tienen un elemento (es decir, el argumento de la función que se pasa a call / cc) que si lo tocas pierdes y vuelves a la etapa normal.

Entonces no importa si hay muchos args , cuando alcanzas uno de ellos termina. Entonces nuestra ejecución alcanza (arg 42) y la devuelve a la suma (+ 42 10) .

También hay algunas observaciones que vale la pena notar:

• No todas las funciones se pueden usar con call / cc. Como espera una continuación (que es una función), no puede tener una f como esta: (define f (lambda (k) (+ k 42)) , porque no puede sum una función.
• Tampoco puedes tener (define f (lambda (k) (f 42 10))) porque la continuación solo espera un argumento.
• Puede finalizar sin touching ninguna salida, en este caso la función procede como cualquier función ordinaria (por ejemplo, (define f (lambda (k) 42) termina y devuelve 42).

Answer 6

La mejor explicación que he visto es en el libro de Paul Graham, On Lisp .

Answer 7

Lo que me ayudó es la idea de que en un lenguaje tradicional con llamadas a funciones implícitamente se pasa una continuación cada vez que se realiza una llamada de función.

Antes de saltar al código de una función, guarda un estado en la pila (es decir, presionas la dirección de retorno y la pila ya contiene tus locales). Esto es esencialmente una continuación. Cuando la función ha terminado, tiene que determinar dónde enviar el flujo de ejecución. Utiliza la continuación almacenada en la pila, mostrando la dirección de retorno y saltando hacia ella.

Otros lenguajes generalizan esta idea de continuaciones permitiéndole especificar explícitamente dónde continuar la ejecución del código, en lugar de continuar implícitamente desde donde se realizó la llamada a la función.

EDITAR basado en un comentario:

La continuación es el estado de ejecución completo. En cualquier punto de ejecución, puede dividir el programa en dos partes (en tiempo, no espacio): la que se ha ejecutado hasta este punto y todo lo que se ejecutará desde aquí. La "continuación actual" es "todo lo que se va a ejecutar desde aquí" (se puede pensar que es como una función que hará todo lo que el resto de su programa hubiera hecho). De modo que la función que proporciona a call/cc pasa la continuación que era actual cuando se invoca call/cc . La función puede usar la continuación para devolver la ejecución a la instrucción call/cc (más probable es que pase la continuación a otra cosa, porque si la usara directamente podría hacer una simple devolución en su lugar).

Answer 8

Mira, encontré esta mejor descripción sobre este tema.

Aquí está despojado de los detalles copia de ese artículo:

Autor: Marijn Haverbeke Fecha: 24 de julio de 2007

La función call-with-current-continuation de Scheme permite capturar un cómputo, un estado de la pila de llamadas por así decirlo, y reanudar ese mismo estado en un momento posterior. Además de tal primitiva, se pueden implementar varias formas de manejo de excepciones y trucos de Longjmp tipo C.

function traverseDocument(node, func) {
func(node);
var children = node.childNodes;
for (var i = 0; i < children.length; i++)
traverseDocument(children[i], func);
}
function capitaliseText(node) {
if (node.nodeType == 3) // A text node
node.nodeValue = node.nodeValue.toUpperCase();
}
traverseDocument(document.body, capitaliseText);

Esto se puede transformar de la siguiente manera: agregamos un argumento adicional a cada función, que se usará para pasar la continuación de la función. Esta continuación es un valor de función que representa las acciones que deben ocurrir después de que la función ''devuelve''. La pila (llamada) se vuelve obsoleta en el estilo de continuación de paso: cuando una función llama a otra función, eso es lo último que hace. En lugar de esperar que la función llamada regrese, pone cualquier trabajo que quiera hacer después en una continuación, que pasa a la función.

function traverseDocument(node, func, c) {
var children = node.childNodes;
function handleChildren(i, c) {
if (i < children.length)
traverseDocument(children[i], func,
function(){handleChildren(i + 1, c);});
else
c();
}
return func(node, function(){handleChildren(0, c);});
}
function capitaliseText(node, c) {
if (node.nodeType == 3)
node.nodeValue = node.nodeValue.toUpperCase();
c();
}
traverseDocument(document.body, capitaliseText, function(){});

Imagina que tenemos un documento enorme para capitalizar. Simplemente atravesarlo de una vez lleva cinco segundos, y congelar el navegador durante cinco segundos es un estilo bastante malo. Considere esta simple modificación de capitaliseText (no preste atención a lo feo global):

var nodeCounter = 0;
function capitaliseText(node, c) {
if (node.nodeType == 3)
node.nodeValue = node.nodeValue.toUpperCase();
nodeCounter++;
if (nodeCounter % 20 == 0)
setTimeout(c, 100);
else
c();
}

Ahora, cada veinte nodos, el cómputo se interrumpe durante cien milisegundos para darle a la interfaz del navegador un momento para responder a la entrada del usuario. Una forma muy primitiva de enhebrar: incluso puedes ejecutar múltiples cálculos al mismo tiempo de esta manera.

Una aplicación más comúnmente útil de esto está relacionada con XMLHttpRequests, o los varios hacks de etiquetas IFRAME y SCRIPT utilizados para simularlos. Estos siempre requieren que uno trabaje con algún tipo de mecanismo de devolución de llamada para manejar los datos que el servidor envía de vuelta. En casos simples, funcionará una función trivial, o se pueden usar algunos valores globales para almacenar el estado del cálculo que debe reanudarse después de que los datos vuelvan. En casos complejos, por ejemplo, cuando los datos están siendo utilizados por una función que debe devolver algún valor a su interlocutor, las continuidades simplifican considerablemente las cosas. Simplemente registra la continuación como devolución de llamada, y su cálculo se reanuda cuando la solicitud finaliza.

Answer 9

Para compararlo con C, la continuación actual es como el estado actual de la pila. Tiene todas las funciones esperando que termine el resultado de la función actual para que puedan reanudar la ejecución. La variable capturada como la continuación actual se usa como una función, excepto que toma el valor proporcionado y lo devuelve a la pila de espera. Este comportamiento es similar a la función C longjmp donde puedes regresar a las porciones inferiores de la pila inmediatamente.

(define x 0) ; dummy value - will be used to store continuation later
(+ 2 (call/cc (lambda (cc)
(set! x cc) ; set x to the continuation cc; namely, (+ 2 _)
3))) ; returns 5
(x 4) ; returns 6

Una diferencia clave entre la pila C y una continuación es que una continuación se puede usar en cualquier punto del programa, incluso si el estado de la pila ha cambiado. Esto significa que básicamente puede restaurar versiones anteriores de la pila y usarlas una y otra vez, lo que genera un flujo de programa único.

(* 123 (+ 345 (* 789 (x 5)))) ; returns 7
reason: it is because (x 5) replaces the existing continuation,
(* 123 (+ 345 (* 789 _))), with x, (+ 2 _), and returns
5 to x, creating (+ 2 5), or 7.

La capacidad de guardar y restaurar el estado de un programa tiene mucho en común con el multihilo. De hecho, puedes implementar tu propio programador de hilos usando continuaciones, como he intentado ilustrar here .

Answer 10

Un ejemplo trivial de uso de continuación sería la implementación de un administrador de subprocesos (si se desea, fibra) en una máquina con un solo procesador. El planificador interrumpiría el flujo de ejecución periódicamente (o, en el caso de las fibras, se invocará en varios puntos estratégicos del código), guardará el estado de continuación (correspondiente al hilo actual ), luego cambiará a un estado de continuación diferente (correspondiente a un hilo diferente cuyo estado se guardó previamente).

Con respecto al fondo de su conjunto, el estado de continuación capturaría detalles como el puntero de instrucción, los registros y el contexto de la pila (puntero) , para ser guardados y restaurados a voluntad.

Otra forma de utilizar la continuación sería pensar en reemplazar las llamadas a métodos con varias entidades parecidas a subprocesos que coexisten en paralelo (ya sea en ejecución o suspendidas) pasando el control entre sí utilizando contextos de continuación en lugar del paradigma de call ''clásico''. Operarían en datos globales (compartidos) en lugar de depender de los parámetros. Esto es, hasta cierto punto, más flexible que la call en el sentido de que la pila no tiene que terminar hacia abajo (las calls están anidadas ), pero el control puede circular de forma arbitraria.

Intentando visualizar este concepto en un lenguaje como C, imagina tener un gran bucle con una sola instrucción switch(continuation_point) { case point1: ... } , donde cada case corresponde a un punto de recuperación de continuación, y donde el código dentro de cada uno case puede alterar el valor del punto de continuation_point y ceder el control a ese punto de continuation_point break el switch y activando la siguiente iteración en el ciclo.

¿Cuál es el contexto de tu pregunta? Cualquier escenario en particular que le interese? ¿Algún lenguaje de programación en particular? ¿El ejemplo de hilo / fibra es suficiente?