En la programación funcional , el estilo de continuación-paso ( 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 habitual de programación. 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 da una descripción detallada de los numerosos descubrimientos de continuaciones. [3]
Una función escrita en estilo de paso de continuación toma un argumento adicional: una "continuación" explícita, es decir, una función de un 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. Eso significa que cuando se invoca una función CPS, se requiere que la función de llamada proporcione un procedimiento que se invocará con el valor de "retorno" de la subrutina. Expresar código de esta forma hace que una serie de cosas sean explícitas que están implícitas en el estilo directo. Estos incluyen: devoluciones de procedimientos, que se hacen evidentes como llamadas a una continuación; valores intermedios, que son todos nombres de pila; orden de evaluación del argumento, 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ó al llamador.
Los programas se pueden transformar automáticamente de estilo directo a CPS. Los compiladores funcionales y lógicos a menudo usan CPS como una representación intermedia donde un compilador para un lenguaje de programación imperativo o procedimental usaría una 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 CPS se utiliza como representación intermedia). [5] Los compiladores funcionales también pueden usar la forma A-normal (ANF) (pero solo para lenguajes que requieren una evaluación entusiasta), en lugar de con ' thunks ' (descritos en los ejemplos a continuación) en CPS. Los compiladores utilizan CPS con más frecuencia que los programadores como estilo local o global.
Ejemplos de
En CPS, cada procedimiento toma un argumento adicional que representa lo que se debe hacer con el resultado que calcula la función. Esto, junto con un estilo restrictivo que prohíbe una variedad de construcciones usualmente disponibles, se usa para exponer la semántica de los programas, haciéndolos más fáciles de analizar. Este estilo también facilita la expresión de estructuras de control inusuales, como atrapar / lanzar u otras transferencias de control no locales.
La clave de CPS es 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 convertir las expresiones "de adentro hacia afuera" porque las partes más internas de la expresión deben evaluarse primero, por lo que CPS hace explícito 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 el CPS correspondiente. 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
":
( definir ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( definir ( pyth & x y k ) ( * & x x ( lambda ( x2 ) ( * & y y ( lambda ( y2 ) ( + & x2 y2 ( lambda ( x2py2 ) ( sqrt & x2py2 k )))))))) |
( define ( factorial n ) ( if ( = n 0 ) 1 ; NOT tail-recursive ( * n ( factorial ( - n 1 ))))) | ( define ( factorial & n k ) ( = & n 0 ( lambda ( b ) ( si b ; continuación creciente ( k 1 ) ; en la llamada recursiva ( - & n 1 ( lambda ( nm1 ) ( factorial & nm1 ( lambda ( f )) ( * & n f k ))))))))) |
( define ( factorial n ) ( f-aux n 1 )) ( define ( f-aux n a ) ( if ( = n 0 ) a ; tail-recursive ( f-aux ( - n 1 ) ( * n a )) )) | ( define ( factorial & n k ) ( f-aux & n 1 k )) ( define ( f-aux & n a k ) ( = & n 0 ( lambda ( b ) ( si b ; continuación sin modificar ( k a ) ; en el recursivo llamar ( - & n 1 ( lambda ( nm1 ) ( * & n a ( lambda ( nta ) ( f-aux & nm1 nta k ))))))))) |
Tenga en cuenta que en las versiones de CPS, las primitivas utilizadas, como +&
y *&
son en sí mismas CPS, no estilo directo, por lo que para que los ejemplos anteriores funcionen en un sistema Scheme necesitaríamos escribir estas versiones de primitivas de CPS, 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 ) ( aplica f ( reverse ( cdr r ))))))) ( define * & ( cps-prim * )) ( definir + & ( cps-prim + ))
Para llamar a un procedimiento escrito en CPS a partir de 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 (asumiendo que se han proporcionado primitivas de estilo CPS), podríamos llamar (factorial& 10 (lambda (x) (display x) (newline)))
.
Existe cierta variedad entre los compiladores en la forma en que se proporcionan las funciones primitivas en CPS. Anteriormente, hemos utilizado la convención más simple, sin embargo, a veces se proporcionan primitivas booleanas que requieren dos procesadores para ser llamadas en los dos casos posibles, por lo que la (=& n 0 (lambda (b) (if b ...)))
llamada dentro de la f-aux&
definición anterior se escribiría en su lugar como (=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...)))
. De manera similar, a veces la if
propia primitiva 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 del condicional.
Las traducciones que se muestran arriba muestran que CPS es una transformación global. El factorial de estilo directo toma, como era de esperar, un solo argumento; el factorial CPS & toma dos: el argumento y una continuación. Cualquier función que llame a una función CPS-ed debe proporcionar una nueva continuación o pasar la suya propia; cualquier llamada desde una función CPS-ed a una función que no sea CPS utilizará continuaciones implícitas. Por lo tanto, para garantizar la ausencia total de una pila de funciones, todo el programa debe estar en CPS.
CPS en Haskell
En esta sección escribiremos una función pyth
que calcula la hipotenusa usando el teorema de Pitágoras . Una implementación tradicional de la pyth
función se ve así:
pow2 :: Flotar -> Flotar pow2 a = a ** 2agregar :: Flotar -> Flotar -> Flotar agregar a b = a + bpyth :: Float -> Float -> Float pyth a b = sqrt ( agregar ( pow2 a ) ( pow2 b ))
Para transformar la función tradicional en CPS, necesitamos cambiar su firma. La función obtendrá otro argumento del tipo de función, y su tipo de retorno depende de esa función:
pow2 ' :: Float -> ( Float -> a ) -> a pow2' a cont = cont ( a ** 2 )add ' :: Float -> Float -> ( Float -> a ) -> a add' a b cont = cont ( a + b )- Los tipos a -> (b -> c) y a -> b -> c son equivalentes, por lo que la función CPS - puede verse como una función de orden superior sqrt ' :: Float -> (( Float -> a ) -> a ) raíz cuadrada ' a = \ cont -> cont ( raíz cuadrada a )pyth ' :: Float -> Float -> ( Float -> a ) -> a pyth' a b cont = pow2 ' a ( \ a2 -> pow2' b ( \ b2 -> agregar ' a2 b2 ( \ anb -> sqrt ' anb cont )))
Primero calculamos el cuadrado de unapyth'
función in y pasamos una función lambda como continuación que aceptará un cuadrado de a como primer argumento. Y así sucesivamente hasta llegar al resultado de nuestros cálculos. Para obtener el resultado de esta función podemos pasar id
función como argumento final que devuelve el valor que se ha pasado sin cambios: pyth' 3 4 id == 5.0
.
La biblioteca mtl, que se envía con GHC , tiene el módulo Control.Monad.Cont . Este módulo proporciona el tipo Cont, que implementa Monad y algunas otras funciones útiles. El siguiente fragmento muestra la pyth'
función usando 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 ( agregar ' a2 b2 ) r <- cont ( sqrt' anb ) return r
No solo la sintaxis se ha vuelto más limpia, sino que este tipo nos permite usar una función callCC
con tipo MonadCont m => ((a -> m b) -> m a) -> m a
. Esta función tiene un argumento de un tipo de función; ese argumento de función también acepta la función, lo que descarta todos los cálculos posteriores a su llamada. Por ejemplo, rompamos la ejecución de la pyth
función si al menos uno de sus argumentos es negativo y devuelve cero:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do - $ sign ayuda a evitar los paréntesis: a $ b + c == a (b + c) cuando ( b < 0 || a < 0 ) ( exitF 0.0 ) - cuando :: Aplicativo f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( agregue ' a2 b2 ) r <- cont ( sqrt ' anb ) return r
Continuaciones como objetos
La programación con continuaciones también puede ser útil cuando una persona que llama no quiere esperar hasta que termine la llamada. Por ejemplo, en la programación de la interfaz de usuario (UI), una rutina puede configurar campos de cuadro de diálogo y pasarlos, junto con una función de continuación, al marco de la interfaz de usuario. Esta llamada regresa de inmediato, lo que permite que el código de la aplicación continúe mientras el usuario interactúa con el cuadro de diálogo. Una vez que el usuario presiona el botón "Aceptar", el marco llama a la función de continuación con los campos actualizados. Aunque este estilo de codificación utiliza continuaciones, no es CPS completo. [ aclaración necesaria ]
función confirmName () { campos . nombre = nombre ; marco . Show_dialog_box ( campos , confirmNameContinuation ); }función confirmNameContinuation ( campos ) { nombre = campos . nombrar ; }
Se puede usar una idea similar cuando la función debe ejecutarse en un subproceso diferente o en un procesador diferente. El marco puede ejecutar la función llamada en un hilo de trabajo, luego llamar a la función de continuación en el hilo original con los resultados del trabajador. Esto está en Java usando el marco de interfaz de usuario de Swing :
void buttonHandler () { // Esto se está ejecutando en el hilo de la IU de Swing. // Podemos acceder a los widgets de la interfaz de usuario aquí para obtener parámetros de consulta. parámetro int final = getField (); new Thread ( new Runnable () { public void run () { // Este código se ejecuta en un hilo separado. // Podemos hacer cosas como acceder a una base de datos o un // recurso de bloqueo como la red para obtener datos. final int resultado = búsqueda ( parámetro ); javax . swing . SwingUtilities . invokeLater ( new Runnable () { public void run () { // Este código se ejecuta en el hilo de la interfaz de usuario y puede usar // los datos obtenidos para completar los widgets de la interfaz de usuario. setField ( resultado ); } }); } }). inicio (); }
El uso de la notación lambda de Java 8 anterior se acorta a (la final
palabra clave podría omitirse):
void buttonHandler () { int parámetro = getField (); new Thread (() -> { int resultado = lookup ( parámetro ); javax . swing . SwingUtilities . invokeLater (() -> setField ( resultado )); }). inicio (); }
Llamadas de cola
Cada llamada en CPS es una llamada de cola y la continuación se pasa explícitamente. El uso de CPS sin optimización de llamadas de cola (TCO) hará que no solo la continuación construida crezca potencialmente durante la recursividad, sino también la pila de llamadas . Por lo general, esto no es deseable, pero se ha utilizado de formas interesantes; consulte el compilador Chicken Scheme . Dado que CPS y TCO eliminan el concepto de retorno de función implícito, su uso combinado puede eliminar la necesidad de una pila en tiempo de ejecución. Varios compiladores e intérpretes de lenguajes de programación funcional utilizan esta capacidad de formas novedosas. [6]
Uso e implementación
El estilo de paso de continuación se puede utilizar para implementar continuaciones y controlar los operadores de flujo en un lenguaje funcional que no presenta continuaciones de primera clase, pero sí tiene funciones de primera clase y optimización de llamadas de cola . Sin la optimización de la llamada de cola , se pueden utilizar técnicas como el trampolín , es decir, el uso de un bucle que invoca iterativamente funciones de retorno de thunk; sin funciones de primera clase, incluso es posible convertir llamadas de cola en solo gotos en un ciclo de este tipo.
Escribir código en CPS, aunque no es imposible, suele ser propenso a errores. Hay varias traducciones, generalmente definidas como conversiones de una o dos pasadas de cálculo lambda puro , que convierten expresiones de estilo directo en expresiones CPS. Sin embargo, escribir en trampolín es extremadamente difícil; cuando se utiliza, suele ser el objetivo de algún tipo de transformación, como la compilación .
Las funciones que utilizan más de una continuación se pueden definir para capturar varios 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 ))))))
Es de destacar que la 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]
Usar en otros campos
Fuera de la informática , CPS es de interés más general como una 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 oraciones usando CPS podría explicar ciertos fenómenos en el lenguaje natural . [10]
En matemáticas , el isomorfismo de Curry-Howard entre los programas de computadora y las pruebas matemáticas relaciona la traducción del estilo de continuación-paso 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 regular de doble negación , que mapea proposiciones atómicas p a (( p → ⊥) → ⊥), el estilo de paso de continuación reemplaza ⊥ por el tipo de la expresión final. Por consiguiente, el resultado se obtiene pasando la función de identidad como una continuación de la expresión de estilo CPS, como en el ejemplo anterior.
La lógica clásica en sí se relaciona con la manipulación de la continuación de los programas directamente, como en el operador de control de llamada con continuación de corriente de Scheme , una observación debida a Tim Griffin (utilizando el operador de control C estrechamente relacionado). [11]
Ver también
- Recursión de la cola a través del trampolín
Notas
- ^ Sussman, Gerald Jay ; Steele, Guy L., Jr. (diciembre de 1975).
Es decir, en este estilo de programación de paso de continuación , una función siempre "devuelve" su resultado "enviándolo" a otra función . Ésta es la idea clave.
. AI Memo . 349 : 19. - ^ Sussman, Gerald Jay ; Steele, Guy L., Jr. (diciembre de 1998). "Esquema: un intérprete para el cálculo Lambda extendido" (reimpresión) . Computación simbólica y de orden superior . 11 (4): 405–439. doi : 10.1023 / A: 1010035624696 .
Creemos que esta fue la primera aparición del término " estilo de continuación-pase " en la literatura. Ha resultado ser un concepto importante en el análisis y transformación de código fuente para compiladores y otras herramientas de metaprogramación. También ha inspirado un conjunto de otros "estilos" de expresión de programas.
- ^ Reynolds, John C. (1993). "Los descubrimientos de continuaciones". Lisp y computación simbólica . 6 (3–4): 233–248. CiteSeerX 10.1.1.135.4705 . doi : 10.1007 / bf01019459 .
- ^ * Appel, Andrew W. (abril de 1998). "SSA es programación funcional". Avisos ACM SIGPLAN . 33 (4): 17-20. CiteSeerX 10.1.1.34.3282 . doi : 10.1145 / 278283.278285 .
- ^ * Kelsey, Richard A. (marzo de 1995). "Una correspondencia entre el estilo de paso de continuación y el formulario de asignación única estática". Avisos ACM SIGPLAN . 30 (3): 13-22. CiteSeerX 10.1.1.489.930 . doi : 10.1145 / 202530.202532 .
- ^ Appel, Andrew W. (1992). Compilación con continuaciones. Prensa de la Universidad de Cambridge. ISBN 0-521-41695-7 .
- ^ Mike Stay, "La transformación de paso de continuación y la incrustación de Yoneda"
- ^ Mike Stay, "El cálculo de Pi II"
- ^ Boudol, Gérard (1997). "El π-cálculo en estilo directo". CiteSeerX 10.1.1.52.6034 . Cite journal requiere
|journal=
( ayuda ) - ^ Barker, Chris (1 de septiembre de 2002). "Continuaciones y la naturaleza de la cuantificación" (PDF) . Semántica del lenguaje natural . 10 (3): 211–242. doi : 10.1023 / A: 1022183511876 . ISSN 1572-865X .
- ^ Griffin, Timothy (enero de 1990). Una noción de control basada en fórmulas . Actas de la Conferencia sobre los principios de los lenguajes de programación . 17 . págs. 47–58. doi : 10.1145 / 96709.96714 . ISBN 978-0897913430.
Referencias
- 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). Compilación con continuaciones . Prensa de la Universidad de Cambridge. ISBN 978-0-521-41695-5.
- Danvy, Olivier ; Filinski, Andrzej (1992). "Representando el control, un estudio de la transformación de CPS". Estructuras matemáticas en informática . 2 (4): 361–391. CiteSeerX 10.1.1.46.84 . doi : 10.1017 / S0960129500001535 .
- Chicken Scheme compiler , un compilador de Scheme to C que usa el estilo de paso de continuación para traducir los procedimientos de Scheme en funciones C mientras usa la pila C como guardería para el recolector de basura generacional
- Kelsey, Richard A. (marzo de 1995). "Una correspondencia entre el estilo de paso de continuación y el formulario de asignación única estática". Avisos ACM SIGPLAN . 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" . Avisos ACM SIGPLAN . 33 (4): 17-20. CiteSeerX 10.1.1.34.3282 . doi : 10.1145 / 278283.278285 .
- Danvy, Olivier; Millikin, Kevin; Nielsen, Lasse R. (2007). "Sobre transformaciones CPS de una pasada" . BRICS, Departamento de Ciencias de la Computación, Universidad de Aarhus. pag. 24. ISSN 0909-0878 . RS-07-6 . Consultado el 26 de octubre de 2007 .
- Dybvig, R. Kent (2003). El lenguaje de programación del esquema . Prentice Hall. pag. 64.Enlace directo: "Apartado 3.4. Estilo de pase de continuación" .