Pregunta

He intentado varias veces comprender el concepto de continuations y call / cc . Cada intento fue un fracaso. Alguien puede 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 montaje 6502 y tuve un pequeño randez-vous con Erlang. Sin embargo, aún así, no puedo envolver mi cabeza alrededor de call / cc.

¿Fue útil?

Solución

Mire, he encontrado esta Estilo de aprobación de aprobación La mejor descripción de este tema.

Aquí está despojada de la copia de detalles de ese artículo:

  

Autor: Marijn Haverbeke   Fecha: 24 de julio de 2007

     

La función de llamada con la corriente actual de Scheme hace posible capturar un cálculo, un estado de la pila de llamadas, y reanudar ese mismo estado en un momento posterior. Además de esta forma primitiva, se pueden implementar varias formas de manejo de excepciones y trucos longjmp similares a 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 (de llamada) se vuelve obsoleta en el estilo de paso de continuación & # 8213; cuando una función llama a otra función, eso es lo último que hace. En lugar de esperar a que la función llamada regrese, coloca 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 de huuuuge para capitalizar. Solo 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álculo se interrumpe durante cien milisegundos para dar un momento a la interfaz del navegador para responder a la entrada del usuario. Una forma muy primitiva de enhebrar & # 8213; Incluso puede ejecutar varios cálculos al mismo tiempo como este.

     

Una aplicación más comúnmente útil de esto está relacionada con XMLHttpRequests, o los diversos 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. En casos simples, una función trivial funcionará, o se pueden usar algunas variables globales para almacenar el estado del cálculo que se debe reanudar después de que los datos regresen. Con 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 continuaciones simplifican las cosas considerablemente. Simplemente registre la continuación como devolución de llamada y su cálculo se reanudará cuando finalice la solicitud.

Otros consejos

Para compararlo con C, la continuación actual es como el estado actual de la pila. Tiene todas las funciones a la espera de que finalice 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 en espera. Este comportamiento es similar a la función C longjmp donde puede volver a las partes 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 se puede usar una continuación en cualquier punto del programa, incluso si el estado de la pila ha cambiado. Esto significa que esencialmente puedes restaurar versiones anteriores de la pila y usarlas una y otra vez, lo que lleva a 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 usando continuaciones, como he intentado ilustrar aquí .

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

Con referencia al fondo de su ensamblaje, el estado de continuación capturará detalles como el puntero de instrucción, los registros y el contexto de la pila (puntero) para guardarlos y restaurarlos a voluntad.

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

Al intentar visualizar este concepto en un lenguaje como el de C, imagina tener un gran bucle con un solo interruptor (punto_continuación) {caso punto1: ...} , donde cada caso corresponde a un punto de salvación de continuación, y donde el código dentro de cada caso puede alterar el valor de punto_continuación y ceder el control a ese punto_continuación por break a partir del interruptor y activando la siguiente iteración en el bucle.

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

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

Antes de saltar al código de una función, guardas algo de estado en la pila (es decir, presionas tu dirección de retorno y la pila ya contiene tus locales). Esto es esencialmente una continuación. Cuando la función ha finalizado, tiene que determinar dónde enviar el flujo de ejecución. Utiliza la continuación almacenada en la pila, haciendo estallar la dirección de retorno y saltando a ella.

Otros idiomas generalizan esta idea de continuación, 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 el 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 en espacio): lo que se ha ejecutado hasta este punto y todo lo que se ejecutará desde aquí. La " continuación actual " es el " todo lo que se va a ejecutar desde aquí " (Puedes pensar que es como una función que hará todo lo que el resto de tu programa hubiera hecho). Por lo tanto, la función que suministras a call / cc pasa a la continuación que era actual cuando se invocó call / cc . La función puede usar la continuación para devolver la ejecución a la declaración call / cc (aunque es más probable que pase la continuación a otra cosa, porque si la usara directamente podría hacer una simple devolución) ).

Cuando estaba tratando de entender call / cc, encontré esto call-with-current-continuation-for-C-programmers fue útil.

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

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

parellel entre la etapa de bonificación y call / cc

Tan pronto como lo tocas, eres transferido 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 pasada a call / cc) que si lo tocas, pierdes y son transportados de vuelta a la etapa normal.

paralelo entre la etapa de bonificación de salida y la función call / cc args

Por lo tanto, no importa si hay muchos args , cuando llegas a uno de ellos, se acabó. Así que nuestra ejecución llega a (arg 42) y la devuelve a la suma (+ 42 10) .

También hay algunos comentarios que vale la pena notar:

  • No todas las funciones se pueden usar con call / cc. Como se espera una continuación (que es una función), no puedes tener una f como esta: (define f (lambda (k) (+ k 42)) , porque no puedes suma a función.
  • También no puede tener (defina f (lambda (k) (f 42 10))) Porque la continuación solo espera un argumento.
  • puedes terminar sin tocar ninguna salida, en este caso la función continúa como cualquier función ordinaria (por ejemplo, (defina f (lambda (k) 42) termina y devuelve 42).

Hay varios niveles para comprender call / cc. Primero debe comprender los términos y cómo funciona el mecanismo. Luego, una comprensión de cómo y cuándo se utiliza call / cc en " vida real " la programación es necesaria.

Se puede llegar al primer nivel estudiando CPS, pero hay alternativas.

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

Daniel P. Friedman. " Aplicaciones de Continuaciones: Tutorial Invitado " ;. 1988 Principios de los lenguajes de programación (POPL88). Enero de 1988.

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

El modelo que utilicé para comprender las continuaciones desde un punto de vista imperativo es que es 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 un argumento) con la continuación como un argumento.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top