¿Qué es call/cc?

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 programación orientada a objetos. 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

Mira, esto he encontrado Continuation Passing Style mejor descripción sobre este tema.

Aquí está despojado de copia detalles de dicho artículo:

Autor: Marijn Haverbeke Fecha: July 24th de 2007

del Esquema de llamadas con corriente de continuación de la función hace posible capturar un cálculo, un estado de la pila de llamadas por así decirlo, y reanudar el 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: Añadimos un argumento adicional para cada función, que se utiliza 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(){}); 

Imagine que tenemos un documento original para capitalizar. Simplemente atravesarlo de una vez lleva cinco segundos, y congelar el navegador durante cinco segundos es un estilo bastante malo. Considera esta simple modificación de capitaliseText (no prestar atención a la fea 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álculo se interrumpe por cien milisegundos para dar la interfaz del navegador un momento para responder a los usuarios entrada. 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 con 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 2

Un ejemplo trivial del uso de la 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 programador interrumpiría periódicamente el flujo de ejecución (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 actual thread), luego cambiará a un diferente continuación del estado (correspondiente a un subproceso diferente cuyo estado se guardó anteriormente.)

Refiriéndose a su ensamblaje fondo, el estado de continuación podría capturar detalles como puntero de instrucción, registros, y el contexto de pila (puntero), siendo guardado y restaurado a voluntad.

Otra forma de utilizar continuación sería pensar en sustituir método llama con varias entidades de tipo filiforme que coexistir en paralelo (ya sea corriendo o suspendido) pasar el control a la otra usando contextos de continuación en lugar de la 'clásico 'call paradigma. Operarían en datos globales (compartidos) en lugar de depender de los parámetros. Esto es hasta cierto punto más flexible que call en el sentido de que la pila no tiene que cerrarse y luego bajar (calls son anidados), pero el control puede circular de forma arbitraria.

El intento de visualizar este concepto en un lenguaje tal C, imaginar tener un gran bucle con una sola switch(continuation_point) { case point1: ... } declaración, donde cada case corresponde a una continuación punto de almacenamiento, y donde el código dentro de cada case puede alterar el valor de continuation_point y ceder el control a ese continuation_point por break ing desde el switch y activando la siguiente iteración en el ciclo.

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

Answer 3

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

Answer 4

Lo que me ha ayudado 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, empuja su dirección de retorno y la pila ya contiene sus 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 continuación, lo que le permite 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 en base a un comentario:

La continuación es el estado de ejecución completa. 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). Por lo tanto, la función que proporcione 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 declaració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 5

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 puede volver 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 utilizar en cualquier punto en el 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, puede implementar su propio programador de hilos utilizando continuaciones, ya que he intentado ilustrar here.

Answer 6

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

El primer nivel se puede alcanzar mediante el estudio de CPS, pero hay alternativas.

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

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

Answer 7

Cuando estaba tratando de entender call/cc, encontré que esta página call-with-current-continuation-for-C-programmers fue útil.

Answer 8

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

Answer 9

El modelo que utilicé para la comprensión de las continuaciones de un punto de vista fundamental es que es una copia de la pila de llamadas combinado con el de una puntero a la siguiente instrucción.

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

Answer 10

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

Tan pronto como usted lo toca que se transfieren a la etapa de la prima (es decir, la definición de la función pasada como argumento para llamar/cc [f en este caso]).

fases de bonificación son diferentes de las etapas ordinarias porque por lo general tienen un elemento (es decir, el argumento de la función pasó a llamar/cc) que si lo tocas se pierde y es transportado de vuelta a la etapa normal.

Así que no importa si hay muchos args, cuando llegue a uno de ellos a su vez. Entonces, nuestra ejecución llega al (arg 42) y la devuelve a la suma (+ 42 10).

También hay algunas observaciones vale la pena escuchar:

• No todas las funciones se pueden utilizar con llamada/cc. Dado que espera una continuación de (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 .
• También no puede tener (define f (lambda (k) (f 42 10))) porque la continuación solo espera un argumento.
• Usted puede terminar sin touching cualquier salida, en este caso la función procede como cualquier función ordinaria (por ejemplo (define f (lambda (k) 42) acabados y retornos 42).