Estilo de pase de continuación

En programación funcional , el estilo de paso de continuaciones ( CPS ) es un estilo de programación en el que el control se pasa explícitamente en forma de continuación . Esto contrasta con el estilo directo , que es el estilo de programación habitual. Gerald Jay Sussman y Guy L. Steele, Jr. acuñaron la frase en AI Memo 349 (1975), que establece la primera versión del lenguaje de programación Scheme . ^{[ 1 ] [ 2 ]} John C. Reynolds ofrece una descripción detallada de los numerosos descubrimientos de continuaciones. ^{[ 3 ]}

Una función escrita en estilo de paso de continuaciones toma un argumento adicional: una continuación explícita ; es decir, una función de un solo argumento. Cuando la función CPS ha calculado su valor de resultado, lo "devuelve" llamando a la función de continuación con este valor como argumento. Esto significa que al invocar una función CPS, la función que la llama debe proporcionar un procedimiento que se invocará con el valor de "retorno" de la subrutina. Expresar el código de esta forma hace explícitas varias cosas que son implícitas en el estilo directo. Estas incluyen: retornos de procedimientos, que se hacen evidentes como llamadas a una continuación; valores intermedios, que tienen nombres; orden de evaluación de argumentos, que se hace explícito; y llamadas de cola , que simplemente llaman a un procedimiento con la misma continuación, sin modificar, que se pasó a la función que la llamó.

Los programas pueden transformarse automáticamente del estilo directo al CPS. Los compiladores para lenguajes de programación funcional y lógica suelen usar CPS como representación intermedia , mientras que un compilador para un lenguaje de programación imperativo o procedimental usaría la forma de asignación única estática (SSA). ^{[ 4 ]} SSA es formalmente equivalente a un subconjunto de CPS (excluyendo el flujo de control no local , que no ocurre cuando se usa CPS como representación intermedia). ^{[ 5 ]} Los compiladores funcionales también pueden usar la forma A-normal (ANF) (pero solo para lenguajes que requieren evaluación estricta ), en lugar de con thunks (descritos en los ejemplos a continuación) en CPS. CPS es usado con más frecuencia por los compiladores que por los programadores como estilo local o global.

En CPS, cada procedimiento recibe un argumento adicional que indica qué se debe hacer con el resultado que calcula la función. Esto, junto con un estilo restrictivo que prohíbe diversas construcciones habitualmente disponibles, se utiliza para exponer la semántica de los programas, facilitando su análisis. Este estilo también permite expresar fácilmente estructuras de control inusuales, como catch/throwtransferencias de control no locales.

La clave de CPS reside en recordar que (a) cada función toma un argumento adicional conocido como su continuación, y (b) cada argumento en una llamada a función debe ser una variable o una expresión lambda (no una expresión más compleja). Esto tiene el efecto de invertir las expresiones, ya que las partes más internas de la expresión deben evaluarse primero; por lo tanto, CPS explicita el orden de evaluación, así como el flujo de control. A continuación se muestran algunos ejemplos de código en estilo directo y su correspondiente CPS. Estos ejemplos están escritos en el lenguaje de programación Scheme ; por convención, la función de continuación se representa como un parámetro llamado " k":

En las versiones CPS, las primitivas utilizadas, como +&y , *&son en sí mismas CPS, no de estilo directo, por lo que para que los ejemplos anteriores funcionen en un sistema Scheme se requiere escribir estas versiones CPS de las primitivas, con por ejemplo *&definidas por:

( definir ( *& x y k ) ( k ( * x y )))

Para hacer esto en general, podríamos escribir una rutina de conversión:

( define ( cps-prim f ) ( lambda args ( let (( r ( reverse args ))) (( car r ) ( apply f ( reverse ( cdr r ))))))) ( define *& ( cps-prim * )) ( define +& ( cps-prim + ))

Para llamar a un procedimiento escrito en CPS desde un procedimiento escrito en estilo directo, es necesario proporcionar una continuación que recibirá el resultado calculado por el procedimiento CPS. En el ejemplo anterior (suponiendo que se han proporcionado primitivas CPS), podríamos llamar a (factorial& 10 (lambda (x) (display x) (newline))).

Existe cierta variabilidad entre los compiladores en la forma en que se proporcionan las funciones primitivas en CPS. Arriba se utiliza la convención más simple; sin embargo, a veces se proporcionan primitivas booleanas que toman dos thunks para ser llamadas en los dos casos posibles, por lo que la (=& n 0 (lambda (b) (if b ...)))llamada dentro de f-aux&la definición anterior se escribiría en su lugar como (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...))). De manera similar, a veces la ifprimitiva no se incluye en CPS, y en su lugar if&se proporciona una función que toma tres argumentos: una condición booleana y los dos thunks correspondientes a los dos brazos de la condición.

Las traducciones mostradas anteriormente demuestran que CPS es una transformación global. El factorial de estilo directo toma, como cabría esperar, un solo argumento; el factorial& de CPS toma dos: el argumento y una continuación. Cualquier función que llame a una función en CPS debe proporcionar una nueva continuación o pasar la suya propia; cualquier llamada desde una función en CPS a una función que no lo esté utilizará continuaciones implícitas. Por lo tanto, para garantizar la ausencia total de una pila de funciones, todo el programa debe estar en CPS.

pow2 :: Float -> Float pow2 x = x ** 2agregar :: Flotador -> Flotador -> Flotador agregar x y = x + ypyth :: Flotador -> Flotador -> Flotador pyth x y = sqrt ( agregar ( pow2 x ) ( pow2 y ))

pow2' :: Float -> ( Float -> a ) -> a pow2' x cont = cont ( x ** 2 )agregar' :: Flotador -> Flotador -> ( Flotador -> a ) -> a agregar' x y cont = cont ( x + y )-- Los tipos a -> (b -> c) y a -> b -> c son equivalentes, por lo que la función CPS -- puede considerarse una función de orden superior sqrt' :: Float -> (( Float -> a ) -> a ) sqrt' x = \ cont -> cont ( sqrt x )pyth' :: Float -> Float -> ( Float -> a ) -> a pyth' x y cont = pow2' x ( \ x2 -> pow2' y ( \ y2 -> add' x2 y2 ( \ anb -> sqrt' anb cont )))

pow2_m :: Float -> Cont a Float pow2_m a = return ( a ** 2 )pyth_m :: Float -> Float -> Cont a Float pyth_m a b = do a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r

pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do -- El signo $ ayuda a evitar paréntesis: a $ b + c == a (b + c) when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Applicative f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return r

function confirmName () : none { fields . name = name ; framework . Show_dialog_box ( fields , confirmNameContinuation ); }función confirmNameContinuation ( campos : Campos ) : ninguno { nombre = campos . nombre ; }

import javax.swing.SwingUtilities ;void buttonHandler () { // Esto se ejecuta en el hilo de la interfaz de usuario de Swing. // Podemos acceder a los widgets de la interfaz de usuario aquí para obtener los parámetros de consulta. int parameter = getField ();Thread t = new Thread (() -> { // Este código se ejecuta en un hilo separado. // Podemos hacer cosas como acceder a una base de datos o a un // recurso bloqueante como la red para obtener datos. int result = lookup ( parameter );SwingUtilities.invokeLater (() - > { // Este código se ejecuta en el hilo de la interfaz de usuario y puede usar // los datos obtenidos para rellenar los widgets de la interfaz de usuario. setField ( result ); }); }); t.start ( ) ; }

En CPS, cada llamada es una llamada recursiva , y la continuación se pasa explícitamente. Usar CPS sin optimización de llamadas recursivas (TCO) provocará que tanto la continuación construida como la pila de llamadas crezcan potencialmente durante la recursión . Esto suele ser indeseable, pero se ha utilizado de formas interesantes; véase el compilador Chicken Scheme . Dado que CPS y TCO eliminan el concepto de retorno implícito de función, su uso combinado puede eliminar la necesidad de una pila de ejecución. Varios compiladores e intérpretes de lenguajes de programación funcional utilizan esta capacidad de formas novedosas. ^{[ 6 ]}

El estilo de paso de continuaciones se puede utilizar para implementar continuaciones y operadores de control de flujo en un lenguaje funcional que no cuenta con continuaciones de primera clase , pero sí con funciones de primera clase y optimización de llamadas recursivas . Sin optimización de llamadas recursivas, se pueden utilizar técnicas como el trampolín , es decir, usar un bucle que invoca iterativamente funciones que devuelven thunks ; sin funciones de primera clase, incluso es posible convertir llamadas recursivas en simples gotos en dicho bucle.

Si bien escribir código en CPS no es imposible, suele ser propenso a errores. Existen diversas traducciones, generalmente definidas como conversiones de una o dos pasadas del cálculo lambda puro , que transforman expresiones de estilo directo en expresiones CPS. Sin embargo, escribir en estilo trampolín es extremadamente difícil; cuando se utiliza, suele ser objeto de algún tipo de transformación, como la compilación .

Se pueden definir funciones que utilizan más de una continuación para capturar diversos paradigmas de flujo de control, por ejemplo (en Scheme ):

( define ( /& x y ok err ) ( =& y 0.0 ( lambda ( b ) ( if b ( err ( list "div by zero!" x y )) ( ok ( / x y ))))))

Una transformación CPS es conceptualmente una incrustación de Yoneda . ^{[ 7 ]} También es similar a la incrustación del cálculo lambda en el cálculo π . ^{[ 8 ] [ 9 ]}

Fuera del ámbito de la informática , la CPS tiene un interés más general como alternativa al método convencional de componer expresiones simples en expresiones complejas. Por ejemplo, dentro de la semántica lingüística , Chris Barker y sus colaboradores han sugerido que especificar las denotaciones de las oraciones mediante CPS podría explicar ciertos fenómenos del lenguaje natural . ^{[ 10 ]}

En matemáticas , el isomorfismo de Curry-Howard entre programas informáticos y demostraciones matemáticas relaciona la traducción de estilo de paso de continuación con una variación de las incrustaciones de doble negación de la lógica clásica en la lógica intuicionista (constructiva) . A diferencia de la traducción de doble negación regular , que asigna proposiciones atómicas p a (( p → ⊥) → ⊥), el estilo de paso de continuación reemplaza ⊥ por el tipo de la expresión final. En consecuencia, el resultado se obtiene pasando la función identidad como una continuación de la expresión CPS, como en el ejemplo anterior.

La lógica clásica en sí misma se relaciona con la manipulación directa de la continuación de programas, como en el operador de control de llamada con continuación actual de Scheme , una observación debida a Tim Griffin (utilizando el operador de control de C estrechamente relacionado). ^{[ 11 ]}

• Recursión de cola a través del trampolín
• Async/await
• Llamar/cc

• Continuation Passing C (CPC) - lenguaje de programación para escribir sistemas concurrentes , diseñado y desarrollado por Juliusz Chroboczek y Gabriel Kerneis. Repositorio de GitHub.
• La construcción de un compilador basado en CPS para ML se describe en: Appel, Andrew W. (1992). Compiling with Continuations . Cambridge University Press. ISBN 978-0-521-41695-5.
• Danvy, Olivier ; Filinski, Andrzej (1992). "Representando el control, un estudio de la transformación CPS". Estructuras matemáticas en informática . 2 (4): 361– 391. CiteSeerX 10.1.1.46.84 . doi : 10.1017/S0960129500001535 . S2CID 8790522 .  
• Compilador Chicken Scheme , un compilador de Scheme a C que utiliza el estilo de paso de continuaciones para traducir procedimientos Scheme a funciones C, utilizando la pila C como entorno para el recolector de basura generacional.
• Kelsey, Richard A. (marzo de 1995). "Una correspondencia entre el estilo de paso de continuación y la forma de asignación única estática". ACM SIGPLAN Notices . 30 (3): 13– 22. CiteSeerX 10.1.1.3.6773 . doi : 10.1145/202530.202532 . 
• Appel, Andrew W. (abril de 1998). "SSA es programación funcional" . ACM SIGPLAN Notices . 33 (4): 17– 20. CiteSeerX 10.1.1.34.3282 . doi : 10.1145/278283.278285 . S2CID 207227209 .  
• Danvy, Olivier; Millikin, Kevin; Nielsen, Lasse R. (2007). "Sobre las transformaciones CPS de una sola pasada" . Serie de informes BRICS : 24. ISSN 0909-0878 . RS-07-6 . Recuperado el 26 de octubre de 2007 . 
• Dybvig, R. Kent (2003). El lenguaje de programación Scheme . Prentice Hall. pág.  64.Enlace directo: "Sección 3.4. Estilo de paso de continuación" .