Continuación

En informática , una continuación es una representación abstracta del estado de control de un programa . Una continuación implementa ( reifica ) el estado de control del programa; es decir, es una estructura de datos que representa el proceso computacional en un punto determinado de su ejecución. El lenguaje de programación puede acceder a esta estructura de datos, en lugar de que permanezca 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 aquella que, desde la perspectiva de la ejecución del código, se derivaría del punto actual de la ejecución del programa. El término " continuaciones" también puede referirse a las continuaciones de primera clase , que son construcciones que permiten a un lenguaje de programación guardar el estado de ejecución en cualquier punto y volver a ese punto posteriormente en el programa, posiblemente varias veces.

La primera descripción de continuaciones la hizo Adriaan van Wijngaarden en septiembre de 1964. Wijngaarden habló en la Conferencia de Trabajo de la IFIP sobre Lenguajes de Descripción Formal celebrada en Baden bei Wien, Austria. Como parte de una formulación para un preprocesador de Algol 60 , propuso una transformación de los procedimientos propios al estilo de paso de continuaciones , ^{[ 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 popularizaron el término continuación en su trabajo en el campo de la semántica denotacional , que utiliza ampliamente las continuaciones para permitir el análisis de programas secuenciales en términos de la semántica de la 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 dio nombre. ^{[ 3 ]}

Reynolds (1993) ofrece una historia completa del descubrimiento de las continuaciones.

Las continuaciones de primera clase son la capacidad de un lenguaje para controlar completamente el orden de ejecución de las instrucciones. Se pueden usar para saltar a la función que generó la llamada a la función actual, o a una función que ya ha finalizado. Se puede pensar en una continuación de primera clase como un sistema que guarda el estado de ejecución del programa. Las verdaderas continuaciones de primera clase 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 continuaciones":

Imagina que estás en la cocina, frente al refrigerador, pensando en un sándwich. Tomas una continuación y la guardas en tu bolsillo. Luego sacas pavo y pan del refrigerador y te preparas un sándwich, que ahora está sobre la encimera. Invocas la continuación que guardaste en tu bolsillo y te encuentras de nuevo frente al refrigerador, pensando en un sándwich. Pero, por suerte, hay un sándwich en la encimera y todos los ingredientes para prepararlo han desaparecido. Así que te lo comes.  :-) ^{[ 4 ]}

En esta descripción, el sándwich forma parte de los datos del programa (por ejemplo, un objeto en el montón), y en lugar de llamar a una rutina "crear sándwich" y luego regresar, la persona llamó a una rutina "crear sándwich con continuación actual", que crea el sándwich y luego continúa donde se interrumpió la ejecución.

Scheme fue el primer sistema de producción completo que proporcionaba primero "captura" ^{[ 1 ]} y luego llamada/cc . Bruce Duba introdujo llamada/cc en SML .

Las continuaciones también se utilizan en modelos de computación, como la semántica denotacional , el modelo de actor , los cálculos de procesos y el cálculo lambda . Estos modelos requieren que los programadores o ingenieros semánticos escriban funciones matemáticas en el estilo denominado de paso de continuaciones . Esto significa que cada función consume otra función que representa el resto de la computación en relación con esta llamada a la función. Para devolver un valor, la función llama a esta "función de continuación" con un valor de retorno; para abortar la computación, devuelve un valor.

Los programadores funcionales que escriben sus programas con el estilo de paso de continuaciones obtienen la capacidad expresiva de manipular el flujo de control de forma arbitraria. El inconveniente es que deben mantener manualmente las invariantes de control y las continuaciones, lo cual puede ser una tarea muy compleja (véase más adelante el apartado «estilo de paso de continuaciones»).

( 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 de 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, comenzamos aquí. ( set! i ( + i 1 )) i ))

> ( prueba ) 1 > ( la-continuación ) 2 > ( la-continuación ) 3 > ; guarda la continuación actual (que imprimirá 4 a continuación) > ( define otra-continuación la-continuación ) > ( prueba ) ; reinicia la-continuación 1 > ( la-continuación ) 2 > ( otra-continuación ) ; usa la continuación almacenada previamente 4

;;; Una cola ingenua para la planificación de hilos. ;;; Contiene una lista de continuaciones "esperando para ejecutarse".( define *cola* ' ())( define ( empty-queue? ) ( null? *queue* ))( define ( enqueue x ) ( set! *queue* ( append *queue* ( list x ))))( define ( dequeue ) ( let (( x ( car *queue* ))) ( set! *queue* ( cdr *queue* )) x ));;; Esto inicia un nuevo hilo en ejecución (proc).( define ( fork proc ) ( call/cc ( lambda ( k ) ( enqueue k ) ( proc ))));;; Esto cede el procesador a otro hilo, si lo hay.( define ( yield ) ( call/cc ( lambda ( k ) ( enqueue k ) (( dequeue )))));;; Esto finaliza el hilo actual, o todo el programa ;;; si no quedan otros hilos.( define ( thread-exit ) ( if ( empty-queue? ) ( exit ) (( dequeue ))))

;;; El cuerpo de un hilo típico de Scheme que realiza alguna función:( define ( do-stuff-n-print str ) ( lambda () ( let loop (( n 0 )) ( format #t "~A ~A \n " str n ) ( yield ) ( loop ( + n 1 )))));;; Crea dos hilos y ejecútalos. ( fork ( hacer-cosas-e-imprimir "Esto es AAA" )) ( fork ( hacer-cosas-e-imprimir "Hola desde BBB" )) ( thread-exit )

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 área donde se ha visto el uso práctico de 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 para expresar problemas computacionales. Por lo tanto, las continuaciones permiten un código que tiene las propiedades útiles asociadas con la inversión de control , al tiempo que evitan sus problemas. "Inverting back the inversion of control or, Continuations versus page-centric programming" ^{[ 9 ]} es un artículo que proporciona una buena introducción a las continuaciones aplicadas a la programación web.

La compatibilidad con las continuaciones varía considerablemente. Un lenguaje de programación admite continuaciones reinvocables si una continuación puede invocarse repetidamente (incluso después de haber finalizado su ejecución). Peter J. Landin introdujo las continuaciones reinvocables mediante su operador J (de salto), que permitía transferir el flujo de control de vuelta al centro de la ejecución de un procedimiento. En el lenguaje Racket , las continuaciones reinvocables también se denominan "reentrantes" . Sin embargo, este uso del término "reentrante" puede confundirse fácilmente con su uso en el ámbito de la programación multihilo .

Un tipo más limitado es la continuación de escape, que puede usarse para escapar del contexto actual a uno circundante. Muchos lenguajes que no admiten explícitamente continuaciones admiten manejo de excepciones , que es equivalente a las continuaciones de escape y puede usarse para los mismos propósitos. Las de C setjmp/longjmptambién son equivalentes: solo pueden usarse para desenrollar la pila . Las continuaciones de escape también pueden usarse para implementar la eliminación de llamadas recursivas .

Una generalización de las continuaciones son las continuaciones delimitadas . Los operadores de continuación call/cccapturan todo el cálculo restante en un punto dado del programa y no ofrecen ninguna forma de delimitar esta captura. Los operadores de continuación delimitados solucionan esto proporcionando dos mecanismos de control separados: una indicación que delimita una operación de continuación y un operador de reificación como shifto control. Por lo tanto, las continuaciones capturadas mediante operadores delimitados solo representan una porción del contexto del programa.

Las continuaciones son la expresión funcional de la instrucció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 dar como resultado un código difícil de seguir. De hecho, el lenguaje de programación esotérico Unlambda incluye la llamada con 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", que

Algunas expresiones lingüísticas (en particular, los sintagmas nominales cuantificacionales [QNP]) 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 SN cuantificador "everyone" se comporta de manera muy diferente del sintagma nominal no cuantificador "Bob" al contribuir al significado de una oración como "Alice ve [Bob/everyone]"), desplazamiento del alcance (por ejemplo, que "una gota de lluvia cayó sobre cada coche" se interpreta típicamente como${\displaystyle \forall c\exists r,{\mbox{fell}}(r,c)}$en lugar de como${\displaystyle \exists r\forall c,{\mbox{fell}}(r,c)}$), y ambigüedad de alcance (que una oración como "alguien vio a todos" puede ser ambigua entre${\displaystyle \exists x\forall y,{\mbox{saw}}(x,y)}$y${\displaystyle \forall y\exists x,{\mbox{saw}}(x,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 la perspectiva que da el tiempo, una forma limitada de paso de continuación es claramente discernible en el núcleo del tratamiento de Montague (1973) de los sintagmas nominales como cuantificadores generalizados".

El grado en que las continuaciones pueden usarse para explicar otros fenómenos generales en lenguaje natural es un tema de investigación actual. ^{[ 13 ]}

• Llamada con continuación actual
• Cierre
• VEN DE
• Estilo de pase de continuación
• Flujo de control
• Corutina
• Continuación delimitada
• semántica denotacional
• IR A
• pila de espaguetis
• Quajects , un tipo de objeto que permite establecer continuaciones seleccionables (llamadas 'callouts') para métodos de forma individual para cada objeto, a través de la inyección de dependencias .

• Peter Landin . Informe sobre una generalización de saltos y etiquetas . UNIVAC Systems Programming Research. Agosto de 1965. Reimpreso en Higher Order and Symbolic Computation, 11(2):125-143, 1998, con un prólogo de Hayo Thielecke.
• Drew McDermott y Gerry Sussman . El manual de referencia de Conniver. Memorando de IA del MIT n.º 259. Mayo de 1972.
• Daniel Bobrow : Un modelo para estructuras de control para lenguajes de programación de inteligencia artificial IJCAI 1973.
• Carl Hewitt , Peter Bishop y Richard Steiger . Un formalismo de actor modular universal para la inteligencia artificial. IJCAI 1973.
• Christopher Strachey y Christopher P. Wadsworth . Continuaciones: una semántica matemática para el manejo de saltos completos. Monografía técnica PRG-11. Laboratorio de Computación de la Universidad de Oxford. Enero de 1974. Reimpreso en Higher Order and Symbolic Computation, 13(1/2):135—152, 2000, con un prólogo de Christopher P. Wadsworth.
• John C. Reynolds . Intérpretes definicionales para lenguajes de programación de orden superior. Actas de la 25.ª Conferencia Nacional de la ACM, págs.  717-740, 1972. Reimpreso en Higher-Order and Symbolic Computation 11(4):363-397, 1998, con un prólogo.
• John C. Reynolds. Sobre la relación entre la semántica directa y la de continuación. Actas del Segundo Coloquio sobre Autómatas, Lenguajes y Programación. LNCS, vol. 14, págs.  141-156, 1974.
• Reynolds, John C. (1993). "Los descubrimientos de las continuaciones" (PDF) . LISP y computación simbólica . 6 (3/4): 233–248 .
• Gerald Sussman y Guy Steele . SCHEME: Un intérprete para el cálculo lambda extendido. AI Memo 349, Laboratorio de Inteligencia Artificial del MIT, Cambridge, Massachusetts, diciembre de 1975. Reimpreso en Higher-Order and Symbolic Computation 11(4):405-439, 1998, con un prólogo.
• Robert Hieb , R. Kent Dybvig , Carl Bruggeman . Representación del control en presencia de continuaciones de primera clase. Actas de la conferencia ACM SIGPLAN '90 sobre diseño e implementación de lenguajes de programación, págs.  66-77.
• Will Clinger , Anne Hartheimer , Eric Ost . Estrategias de implementación para continuaciones. Actas de la conferencia ACM de 1988 sobre LISP y programación funcional, págs.  124-131, 1988. Versión en revista: Higher-Order and Symbolic Computation, 12(1):7-45, 1999.
• Christian Queinnec . Invertir la inversión de control o, Continuaciones versus programación centrada en la página SIGPLAN Notices 38(2), pp.  57–64, 2003.

• Taller ACM SIGPLAN sobre Continuaciones 2011 en el ICFP .
• Continuaciones para cascarrabias por Sam Ruby
• El libro "Teach Yourself Scheme in Fixnum Days" de Dorai Sitaram incluye un buen capítulo sobre continuaciones.
• Continuaciones y Python sin pila por Christian Tismer
• Actas en línea del Cuarto Taller ACM SIGPLAN sobre Continuaciones, archivadas el 2 de diciembre de 2010 en Wayback Machine.
• Actas en línea del Segundo Taller ACM SIGPLAN sobre Continuaciones
• Continuación, funciones y saltos. Archivado el 2 de diciembre de 2010 en Wayback Machine.
• http://okmij.org/ftp/continuations/ por Oleg Kiselyov
• https://wiki.haskell.org/Continuations
• Rinoceronte con continuaciones
• Continuaciones en Java puro del framework de aplicaciones web RIFE
• Continuaciones de depuración en Java puro. Archivado el 16 de mayo de 2021 en Wayback Machine desde el framework de aplicaciones web RIFE.
• Comparación de generadores, corrutinas y continuaciones, fuente del ejemplo anterior.