En informática , una continuación es una representación abstracta del estado de control de un programa informático . Una continuación implementa ( reifica ) el estado de control del programa, es decir, la continuación es una estructura de datos que representa el proceso computacional en un punto dado de la ejecución del proceso; el lenguaje de programación puede acceder a la estructura de datos creada, en lugar de estar oculta en el entorno de ejecución . Las continuaciones son útiles para codificar otros mecanismos de control en lenguajes de programación, como excepciones , generadores , corrutinas , etc.
La " continuación actual " o "continuación del paso de cálculo" es la continuación que, desde la perspectiva del código en ejecución, se derivaría del punto actual en la ejecución de un programa. El término continuaciones también se puede utilizar para referirse a las continuaciones de primera clase , que son construcciones que le dan a un lenguaje de programación la capacidad de guardar el estado de ejecución en cualquier punto y volver a ese punto en un punto posterior en el programa, posiblemente varias veces.
La primera descripción de las continuaciones fue realizada por Adriaan van Wijngaarden en septiembre de 1964. Wijngaarden habló en la Conferencia de trabajo de la IFIP sobre lenguajes de descripción de lenguajes formales celebrada en Baden bei Wien, Austria. Como parte de una formulación para un preprocesador Algol 60 , pidió una transformación de los procedimientos adecuados en un estilo de paso de continuación , [1] aunque no utilizó este nombre, y su intención era simplificar un programa y, por lo tanto, hacer que su resultado fuera más claro.
Christopher Strachey , Christopher P. Wadsworth y John C. Reynolds dieron relevancia al término continuación en su trabajo en el campo de la semántica denotacional que hace un uso extensivo de las continuaciones para permitir que los programas secuenciales se analicen en términos de semántica de programación funcional . [1]
Steve Russell [2] inventó la continuación en su segunda implementación de Lisp para el IBM 704 , aunque no le puso nombre. [3]
Reynolds (1993) ofrece una historia completa del descubrimiento de las continuaciones.
Las continuaciones de primera clase son la capacidad de un lenguaje de controlar completamente el orden de ejecución de las instrucciones. Se pueden usar para saltar a una función que produjo la llamada a la función actual o a una función que ya salió. Se puede pensar en una continuación de primera clase como si guardara el estado de ejecución del programa. Las continuaciones de primera clase verdaderas no guardan datos del programa (a diferencia de una imagen de proceso ), solo el contexto de ejecución. Esto se ilustra con la descripción del "sándwich de continuación":
Digamos que estás en la cocina frente al refrigerador, pensando en un sándwich. Coges una continuación y te la guardas en el bolsillo. Luego sacas un poco de pavo y pan del refrigerador y te preparas un sándwich, que ahora está sobre la encimera. Invocas la continuación en tu bolsillo y te encuentras de nuevo de pie frente al refrigerador, pensando en un sándwich. Pero afortunadamente hay un sándwich sobre la encimera y todos los materiales utilizados para hacerlo han desaparecido. Así que te lo comes. :-) [4]
En esta descripción, el sándwich es parte de los datos del programa (por ejemplo, un objeto en el montón) y, en lugar de llamar a una rutina "hacer sándwich" y luego regresar, la persona llamó a una rutina "hacer sándwich con continuación actual", que crea el sándwich y luego continúa donde se detuvo la ejecución.
Scheme fue el primer sistema de producción completo que ofrecía primero "catch" [1] y luego call/cc . Bruce Duba introdujo call/cc en SML .
Las continuaciones también se utilizan en modelos de computación, incluida la semántica denotacional , el modelo de actor , los cálculos de procesos y el cálculo lambda . Estos modelos dependen de que los programadores o los ingenieros semánticos escriban funciones matemáticas en el llamado estilo de paso de continuación . Esto significa que cada función consume una función que representa el resto del cálculo relativo a esta llamada de función. Para devolver un valor, la función llama a esta "función de continuación" con un valor de retorno; para abortar el cálculo, devuelve un valor.
Los programadores funcionales que escriben sus programas en estilo de paso de continuación obtienen el poder expresivo de manipular el flujo de control de manera arbitraria. El costo es que deben mantener las invariantes de control y continuaciones a mano, lo que puede ser una tarea altamente compleja (pero vea "estilo de paso de continuación" a continuación).
Las continuaciones simplifican y clarifican la implementación de varios patrones de diseño comunes , incluidas las corrutinas / hilos verdes y el manejo de excepciones , al proporcionar el primitivo básico de bajo nivel que unifica estos patrones aparentemente inconexos. Las continuaciones pueden proporcionar soluciones elegantes a algunos problemas difíciles de alto nivel, como programar un servidor web que admita varias páginas, a las que se acceda mediante el uso de los botones de avance y retroceso y siguiendo enlaces. El marco web Smalltalk Seaside utiliza continuaciones con gran efecto, lo que permite programar el servidor web en estilo procedimental, al cambiar de continuaciones al cambiar de página.
También existen construcciones más complejas para las que "las continuaciones proporcionan una descripción elegante" [1] . Por ejemplo, en C , longjmp se puede utilizar para saltar desde el medio de una función a otra, siempre que la segunda función se encuentre más profundamente en la pila (si está esperando a que la primera función regrese, posiblemente entre otras). Otros ejemplos más complejos incluyen corrutinas en Simula 67 , Lua y Perl ; tasklets en Stackless Python ; generadores en Icon y Python ; continuaciones en Scala (a partir de 2.8); fibras en Ruby (a partir de 1.9.1); el mecanismo de retroceso en Prolog ; mónadas en programación funcional ; y subprocesos .
El lenguaje de programación Scheme incluye el operador de control call-with-current-continuation (abreviado como: call/cc) con el que un programa Scheme puede manipular el flujo de control:
( define la continuación #f ) ( define ( test ) ( let (( i 0 )) ; call/cc llama a su primer argumento de función, pasando ; una variable de continuación que representa este punto en ; el programa como argumento a esa función. ; ; En este caso, el argumento de la función asigna esa ; continuación a la variable the-continuation. ; ( call/cc ( lambda ( k ) ( set! the-continuation k ))) ; ; La próxima vez que se llame a the-continuation, comenzaremos aquí. ( set! i ( + i 1 )) i )) Utilizando lo anterior, el siguiente bloque de código define una función testque establece the-continuationel futuro estado de ejecución de sí misma:
> ( prueba ) 1 > ( la-continuación ) 2 > ( la-continuación ) 3 > ; almacena la continuación actual (que se imprimirá 4 a continuación) > ( define otra-continuación la-continuación ) > ( prueba ) ; restablece la-continuación 1 > ( la-continuación ) 2 > ( otra-continuación ) ; usa la continuación 4 almacenada previamente Para una introducción más sencilla a este mecanismo, consulte call-with-current-continuation .
Este ejemplo muestra un posible uso de continuaciones para implementar corrutinas como subprocesos separados. [5]
;;; Una cola ingenua para la programación de subprocesos. ;;; Contiene una lista de continuaciones "en espera de ejecutarse". ( define *cola* ' ()) ( define ( ¿cola vacía? ) ( ¿nulo? *cola* )) ( define ( pone en cola x ) ( establece! * cola * ( agrega * cola * ( lista x )))) ( define ( saca de la cola ) ( deja (( x ( carro *cola* ))) ( establece! *cola* ( cdr *cola* )) x )) ;;; Esto inicia un nuevo hilo en ejecución (proc). ( definir ( bifurcar proc ) ( llamar/cc ( lambda ( k ) ( poner en cola k ) ( proc )))) ;;; Esto cede el procesador a otro hilo, si hay uno. ( definir ( rendimiento ) ( llamar/cc ( lambda ( k ) ( poner en cola k ) (( sacar de la cola ))))) ;;; Esto finaliza el hilo actual, o el programa entero ;;; si no quedan otros hilos. ( define ( salida-hilo ) ( si ( cola-vacía? ) ( salir ) (( sacar- de-cola )))) Las funciones definidas anteriormente permiten definir y ejecutar hilos a través de multitarea cooperativa , es decir, hilos que ceden el control al siguiente en una cola:
;;; El cuerpo de un hilo típico de Scheme que hace cosas: ( define ( hacer-cosas-n-imprimir str ) ( lambda () ( deja bucle (( n 0 )) ( formato #t "~A ~A \n " str n ) ( rendimiento ) ( bucle ( + n 1 ))))) ;;; Crea dos hilos y comienza a ejecutarlos. ( fork ( do-stuff-n-print "Esto es AAA" )) ( fork ( do-stuff-n-print "Hola desde BBB" )) ( thread-exit ) El código anterior producirá este resultado:
Esto es AAA 0 Hola desde BBB 0 Esto es AAA 1 Hola desde BBB 1 Esto es AAA 2 Hola desde BBB 2 ...
Un programa debe asignar espacio en la memoria para las variables que utilizan sus funciones. La mayoría de los lenguajes de programación utilizan una pila de llamadas para almacenar las variables necesarias porque permite una asignación y liberación automática de memoria rápida y sencilla. Otros lenguajes de programación utilizan un montón para esto, lo que permite flexibilidad a un mayor costo para la asignación y liberación de memoria. Ambas implementaciones tienen ventajas y desventajas en el contexto de las continuaciones. [6]
Muchos lenguajes de programación exhiben continuaciones de primera clase bajo varios nombres; específicamente:
asyncy await: "registra el resto del método como continuación y luego regresa a su llamador inmediatamente; la tarea invocará la continuación cuando se complete". Programación asincrónica para C#callcc0ycallcc1Control.Monad.Contcreate, suspend, @operador: coexpresionesContinuationContinuationContinuationPMC; utiliza el estilo de paso de continuación para todo el flujo de controlcall(exp())ycontinue(aContinuation, anyValue)_continuation.continuletscall-with-current-continuation(comúnmente abreviado como call/cc)callccscala.util.continuationsproporciona shift/resetcall-with-current-continuation(comúnmente abreviado como call/cc)Continuation currentDo:en la mayoría de los entornos Smalltalk modernos se pueden implementar continuaciones sin soporte de VM adicional.SMLofNJ.Cont.callccc, la operación de control de flujo para la llamada con continuación actualEn cualquier lenguaje que admita cierres y llamadas de cola adecuadas , es posible escribir programas en estilo de paso de continuación e implementar manualmente call/cc. (En el estilo de paso de continuación, call/cc se convierte en una función simple que se puede escribir con lambda ). Esta es una estrategia particularmente común en Haskell , donde es fácil construir una " mónada de paso de continuación " (por ejemplo, la Contmónada y ContTel transformador de mónada en la mtlbiblioteca). El soporte para llamadas de cola adecuadas es necesario porque en el estilo de paso de continuación ninguna función nunca retorna; todas las llamadas son llamadas de cola.
Un área en la que se han utilizado de forma práctica las continuaciones es en la programación web . [7] [8] El uso de continuaciones protege al programador de la naturaleza sin estado del protocolo HTTP . En el modelo tradicional de programación web, la falta de estado se refleja en la estructura del programa, lo que lleva a un código construido en torno a un modelo que se presta muy mal a la expresión de problemas computacionales. Por tanto, las continuaciones permiten un código que tiene las propiedades útiles asociadas con la inversión de control , al tiempo que evita sus problemas. "Invertir de nuevo la inversión de control o Continuaciones versus programación centrada en páginas" [9] es un artículo que proporciona una buena introducción a las continuaciones aplicadas a la programación web.
El soporte para las continuaciones varía ampliamente. Un lenguaje de programación admite continuaciones re-invocables si una continuación puede ser invocada repetidamente (incluso después de que ya haya regresado). Las continuaciones re-invocables fueron introducidas por Peter J. Landin usando su operador J (por Jump) que podía transferir el flujo de control de vuelta a la mitad de una invocación de procedimiento. Las continuaciones re-invocables también han sido llamadas "re-entrantes" en el lenguaje Racket . Sin embargo, este uso del término "re-entrante" puede confundirse fácilmente con su uso en discusiones sobre multithreading .
Un tipo más limitado es la continuación de escape que se puede utilizar para escapar del contexto actual a uno circundante. Muchos lenguajes que no admiten explícitamente las continuaciones admiten el manejo de excepciones , que es equivalente a las continuaciones de escape y se puede utilizar para los mismos fines. Los lenguajes de C setjmp/longjmptambién son equivalentes: solo se pueden utilizar para desenrollar la pila . Las continuaciones de escape también se pueden utilizar para implementar la eliminación de llamadas finales .
Una generalización de las continuaciones son las continuaciones delimitadas . Los operadores de continuación como call/cccapturan todo el cálculo restante en un punto dado del programa y no proporcionan ninguna forma de delimitar esta captura. Los operadores de continuación delimitados abordan esto proporcionando dos mecanismos de control separados: un indicador que delimita una operación de continuación y un operador de cosificación como shifto control. Las continuaciones capturadas mediante operadores delimitados solo representan una parte del contexto del programa.
Las continuaciones son la expresión funcional de la declaración GOTO y se aplican las mismas advertencias. [10] Si bien son una opción sensata en algunos casos especiales, como la programación web, el uso de continuaciones puede generar código difícil de seguir. De hecho, el lenguaje de programación esotérico Unlambda incluye la llamada con la continuación actual como una de sus características únicamente porque las expresiones que la involucran "tienden a ser irremediablemente difíciles de rastrear". [11] Los enlaces externos a continuación ilustran el concepto con más detalle.
En "Continuaciones y la naturaleza de la cuantificación", Chris Barker introdujo la "hipótesis de continuación", según la cual
Algunas expresiones lingüísticas (en particular, las frases nominales cuantificacionales) tienen denotaciones que manipulan sus propias continuaciones. [12]
Barker argumentó que esta hipótesis podría usarse para explicar fenómenos como la dualidad del significado de los SN (por ejemplo, el hecho de que el QNP "everyone" se comporte de manera muy diferente del sintagma nominal no cuantificacional "Bob" al contribuir al significado de una oración como "Alice ve [Bob/everyone]"), el desplazamiento de alcance (por ejemplo, que "a raindrop fell on every car" se interpreta típicamente como en lugar de como ), y la ambigüedad de alcance (que una oración como "someone saw everybody" puede ser ambigua entre y ). También observó que esta idea es en cierto modo una extensión natural del enfoque de Richard Montague en "The Proper Treatment of Quantification in Ordinary English" (PTQ), escribiendo que "con el beneficio de la retrospectiva, una forma limitada de paso de continuación es claramente discernible en el núcleo del tratamiento PTQ de Montague (1973) de los SN como cuantificadores generalizados".
El grado en que las continuaciones pueden utilizarse para explicar otros fenómenos generales en el lenguaje natural es un tema de investigación actual. [13]
