En programación funcional , el estilo de paso de continuación ( 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 ofrece una descripción detallada de los numerosos descubrimientos de las 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. Esto significa que cuando se invoca una función CPS, se requiere que la función que llama proporcione un procedimiento que se invocará con el valor de "retorno" de la subrutina. Expresar código en esta forma hace explícitas varias cosas que son implícitas en el estilo directo. Estas incluyen: retornos de procedimiento, que se vuelven evidentes como llamadas a una continuación; valores intermedios, que son todos nombres dados; 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 modificaciones, que se pasó al llamador.
Los programas se pueden transformar automáticamente del estilo directo al 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 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 CPS se usa 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 ansiosa), en lugar de con ' thunks ' (descritos en los ejemplos a continuación) en CPS. CPS es usado con más frecuencia por compiladores que por programadores como un estilo local o global.
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 que suelen estar disponibles, se utiliza para exponer la semántica de los programas, lo que facilita su análisis. Este estilo también facilita la expresión de estructuras de control inusuales, como captura/lanzamiento u otras transferencias de control no locales.
La clave del CPS es recordar que (a) cada función toma un argumento adicional conocido como su continuación, y (b) cada argumento en una llamada de función debe ser una variable o una expresión lambda (no una expresión más compleja). Esto tiene el efecto de poner las expresiones "al revés" porque las partes más internas de la expresión deben evaluarse primero, por lo que el CPS hace explícito el orden de evaluación, así como el flujo de control. A continuación aparecen 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":
Tenga en cuenta que en las versiones CPS, los primitivos utilizados, como +&y *&son en sí mismos CPS, no estilo directo, por lo que para que los ejemplos anteriores funcionen en un sistema Scheme, necesitaríamos escribir estas versiones CPS de los primitivos, por ejemplo, *&definidos 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 variedad entre los compiladores en cuanto a la forma en que se proporcionan las funciones primitivas en CPS. Más arriba 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 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 en sí no se incluye en CPS y, en su lugar, if&se proporciona una función que requiere tres argumentos: una condición booleana y los dos procesadores correspondientes a los dos brazos de la condicional.
Las traducciones que se muestran arriba muestran que CPS es una transformación global. El factorial de estilo directo toma, como podría esperarse, un único argumento; el factorial& de 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 no 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.
En esta sección, escribiremos una función pythque calcula la hipotenusa utilizando el teorema de Pitágoras . Una implementación tradicional de la pythfunción se ve así:
pow2 :: Flotante -> Flotante pow2 x = x ** 2 añadir :: Flotante -> Flotante -> Flotante añadir x y = x + y pyth :: Flotador -> Flotador -> Flotador pyth x y = sqrt ( agregar ( pow2 x ) ( pow2 y )) Para transformar la función tradicional en CPS, necesitamos cambiar su firma. La función recibirá otro argumento del tipo de función y su tipo de retorno depende de esa función:
pow2' :: Flotante -> ( Flotante -> a ) -> a pow2' x cont = cont ( x ** 2 ) añadir' :: Flotante -> Flotante -> ( Flotante -> a ) -> a añadir' 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 verse como una función de orden superior sqrt' :: Float -> (( Float -> a ) -> a ) sqrt' x = \ cont -> cont ( sqrt x ) pyth' :: Flotante -> Flotante -> ( Flotante -> a ) -> a pyth' x y cont = pow2' x ( \ x2 -> pow2' y ( \ y2 -> add' x2 y2 ( \ anb -> sqrt' anb cont ))) Primero calculamos el cuadrado de a en pyth'la función y pasamos una función lambda como continuación que aceptará el 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 idla función como argumento final que devuelve el valor que se le pasó sin cambios: pyth' 3 4 id == 5.0.
La biblioteca mtl, que se incluye con GHC , tiene el módulo Control.Monad.Cont. Este módulo proporciona el tipo Cont, que implementa Monad y otras funciones útiles. El siguiente fragmento muestra la pyth'función que utiliza Cont:
pow2_m :: Flotante -> Cont a Flotante pow2_m a = return ( a ** 2 ) pyth_m :: Flotante -> Flotante -> Cont a Flotante pyth_m a b = hacer a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) devolver r No solo la sintaxis se ha vuelto más clara, sino que este tipo nos permite usar una función callCCcon el 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, interrumpamos la ejecución de la pythfunción si al menos uno de sus argumentos es negativo y devolvemos cero:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do -- $ El signo 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 ( add' a2 b2 ) r <- cont ( sqrt' anb ) devuelve r La programación con continuaciones también puede ser útil cuando un llamador no quiere esperar hasta que el llamado termine. Por ejemplo, en la programación de 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 UI. 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 ; framework.Show_dialog_box ( campos , confirmNameContinuation ) ; } función confirmNameContinuation ( campos ) { nombre = campos.nombre ; } Se puede utilizar 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 subproceso de trabajo y luego llamar a la función de continuación en el subproceso original con los resultados del trabajo. Esto se hace en Java 8 utilizando el marco de interfaz de usuario Swing :
void buttonHandler () { // Esto se está ejecutando en el hilo de UI de Swing. // Podemos acceder a los widgets de UI aquí para obtener parámetros de consulta. int parameter = getField (); 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 de bloqueo como la red para obtener datos. int result = lookup ( parámetro ); javax . swing . SwingUtilities . activateLater (() -> { // 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 ( result ); }); }). start (); } 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 recursión, sino también la pila de llamadas . Esto suele ser indeseable, pero se ha utilizado de formas interesantes: consulte el compilador Chicken Scheme . Como CPS y TCO eliminan el concepto de un 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 para lenguajes de programación funcional utilizan esta capacidad de formas novedosas. [6]
El estilo de paso de continuación se puede utilizar para implementar continuaciones y operadores de flujo de control en un lenguaje funcional que no presenta continuaciones de primera clase pero sí tiene funciones de primera clase y optimización de llamadas finales . Sin la optimización de llamadas finales, se pueden utilizar técnicas como trampolining , es decir, usar un bucle que invoca iterativamente funciones que devuelven thunk ; sin funciones de primera clase, incluso es posible convertir llamadas finales en solo gotos en un bucle de este tipo.
Escribir código en CPS, si bien no es imposible, suele ser propenso a errores. Existen varias traducciones, generalmente definidas como conversiones de uno o dos pasos de cálculo lambda puro , que convierten expresiones de estilo directo en expresiones CPS. Sin embargo, escribir en estilo trampolín es extremadamente difícil; cuando se utiliza, suele ser el objetivo de algún tipo de transformación, como la compilación .
Se pueden definir funciones que utilicen más de una continuación 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 por cero!" x y )) ( ok ( / x y )))))) Cabe 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]
Fuera de la informática , el CPS tiene un interés más general como alternativa al método convencional de componer expresiones simples en expresiones complejas. Por ejemplo, en el ámbito de la semántica lingüística , Chris Barker y sus colaboradores han sugerido que especificar las denotaciones de oraciones mediante el 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 al pasar 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í se relaciona con la manipulación directa de la continuación de los programas, como en el operador de control de llamada con continuación actual de Scheme , una observación debida a Tim Griffin (que utiliza el operador de control C estrechamente relacionado). [11]
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 . Esta es la idea clave.
Creemos que esta fue la primera aparición del término "
estilo de paso de continuación
" 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.