La continuación ( continuación en inglés ) es una representación abstracta del estado del programa en un momento determinado, que se puede guardar y usar para hacer la transición a este estado. Las continuaciones contienen toda la información para continuar la ejecución del programa desde un punto determinado; el estado de las variables globales generalmente no se conserva, pero esto no es esencial para los lenguajes funcionales (por ejemplo, el guardado selectivo y la restauración de los valores de los objetos globales en Scheme se logra mediante un mecanismo de viento dinámico separado). Las continuaciones son similares a BASIC o macros en C , ya que también te permiten saltar a cualquier lugar del programa. Pero las continuaciones, a diferencia de , le permiten ir solo a una sección del programa con un estado determinado que debe guardarse con anticipación, mientras que le permite ir a una sección del programa con variables no inicializadas . goto setjmplongjmpgotogoto
El primer lenguaje en implementar el concepto de continuaciones fue Scheme , y más tarde apareció soporte integrado para continuaciones en varios otros lenguajes.
Formalmente, callcc esta es una función de orden superior que le permite abstraer el contexto dinámico de una función existente en la forma de otra función, que se llama "continuación".
Más sucintamente, una continuación es "el resto del programa desde un punto dado" o "una función que nunca regresa al punto al que fue llamada" [1] . En los cursos de programación funcional, la explicación del concepto de continuación a menudo se reduce a "expandir (complicar) el concepto de rutina ", pero en un sentido didáctico, tal explicación se considera inútil [1] . La razón de la dificultad de explicar el concepto radica en que las continuaciones son en realidad una justificación alternativa del concepto de “comportamiento” (“llamada” en el sentido más amplio), es decir, llevan un modelo semántico diferente, y en este sentido sentido, la transición inicial de la programación funcional "ordinaria" a la programación con un uso intensivo de continuaciones se puede comparar con la transición inicial de la programación imperativa a la funcional .
Las continuaciones proporcionan la base matemática para todo el orden de ejecución del programa , desde los buclesgoto hasta la recursividad , las excepciones , los generadores , las corrutinas y el mecanismo de retorno [1] . Como consecuencia, permiten la implementación de todos estos elementos en el lenguaje a través de un único constructo.
La programación de estilo de paso de continuación (CPS ) es un estilo de programación en el que el control se transfiere a través del mecanismo de continuación . El estilo CPS fue introducido por primera vez por Gerald Jay Sussman y Guy Steele, Jr. , al mismo tiempo que el lenguaje Scheme .
Un programa de "estilo clásico" a menudo se puede reescribir en estilo de paso de continuación. Por ejemplo, para el problema de calcular la hipotenusa de un triángulo rectángulo con código Haskell "clásico" :
pow2 :: Flotante -> Flotante pow2 a = a ** 2 añadir :: Flotante -> Flotante -> Flotante añadir a b = a + b pyth :: Flotante -> Flotante -> Flotante pyth a b = sqrt ( agregar ( pow2 a ) ( pow2 b ))puede agregar un argumento de tipo F, donde Fsignifica una función del valor de retorno de la función original a un tipo arbitrario x, y convertir este tipo arbitrario en el valor de retorno x:
pow2' :: Flotante -> ( Flotante -> a ) -> a pow2' a cont = cont ( a ** 2 ) agregar' :: Flotante -> Flotante -> ( Flotante -> a ) -> a agregar' 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 -- considerarse como una función de orden superior de un único argumento sqrt' :: Float -> ( ( Flotante -> a ) -> a ) sqrt' a = \ cont -> cont ( sqrt a ) pyth' :: Flotante -> Flotante -> ( Flotante -> a ) -> a pyth' a b cont = pow2' a ( \ a2 -> pow2' b ( \ b2 -> add' a2 b2 ( \ anb -> sqrt' y cont ) ))El pyth'cuadrado de se calcula en la función, y la función ( expresión lambdaa ) se pasa como continuación , tomando el cuadrado como único argumento. Además, todos los valores intermedios posteriores se calculan de la misma manera. Para realizar cálculos como una continuación, es necesario pasar una función de un argumento, por ejemplo, una función que devuelve cualquier valor que se le pase. Por lo tanto, la expresión es equivalente a . aidpyth' 3 4 id5.0
La biblioteca haskell estándar en el módulo Control.Monad.Cont contiene un tipo Contque le permite usar funciones CPS en una mónada. La función pyth'se verá así:
pow2_m :: Flotante -> Cont a Flotante pow2_m a = retorno ( a ** 2 ) -- la función cont eleva las funciones CPS normales a pyth_m monad :: 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 ( raíz cuadrada' anb ) devuelve rEste módulo también contiene una función callCCde tipo MonadCont m => ((a -> m b) -> m a) -> m a. Se puede ver en el tipo que toma una función como su único argumento, que a su vez también tiene una función como su único argumento, interrumpiendo los cálculos posteriores. Por ejemplo, podemos abortar más cálculos si al menos uno de los argumentos es negativo:
pyth_m :: Float -> Float -> Cont a Float pyth_m a b = callCC $ \ exitF -> do when ( b < 0 || a < 0 ) ( exitF 0.0 ) -- when :: Aplicativo f => Bool -> f () -> f () a2 <- pow2_m a b2 <- pow2_m b anb <- cont ( add' a2 b2 ) r <- cont ( sqrt' anb ) return rEjemplos de CPS en Scheme:
| estilo directo | Estilo de pase de continuación |
|---|---|
| ( definir ( pyth x y ) ( sqrt ( + ( * x x ) ( * y y )))) | ( define ( 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 ; NO cola recursiva ( * n ( factorial ( - n 1 ))))) | ( define ( factorial& n k ) ( =& n 0 ( lambda ( b ) ( si b ; sigue creciendo ( k 1 ) ; en 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 ; cola recursiva ( 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 preservada ( k a ) ) en llamada recursiva ( -& n 1 ( lambda ( nm1 ) ( *& n a ( lambda ( nta ) ( f-aux& nm1 nta k ))))))))) |
En un CPS "puro", en realidad no hay continuaciones: cada llamada resulta ser una llamada final . Si el idioma no garantiza la optimización de llamadas finales ( TCO ), entonces con cada llamada anidada , tanto la continuación como la pila de llamadas crecen . Por lo general, esto no es deseable, pero a veces se usa de una manera interesante (por ejemplo, en el compilador Chicken Scheme ). El uso combinado de estrategias de optimización de TCO y CPS le permite eliminar completamente la pila dinámica del programa ejecutable. Varios compiladores de lenguaje funcional funcionan de esta manera, como el compilador SML/NJ para Standard ML . callcc
Hay varios tipos de extensiones. Los más comunes son las continuaciones ilimitadas , implementadas usando una función o sus análogos. Tales continuaciones realmente representan el estado de todo el programa (o uno de sus subprocesos) en un momento determinado. Llamar a tal continuación no es como llamar a una función, ya que corresponde a "saltar" al estado guardado del programa y no devuelve ningún valor; dicha continuación generalmente no se puede llamar varias veces. Las continuaciones delimitadas abstraen la dependencia del resultado de algún bloque de programa del resultado de alguna subexpresión de este bloque. En cierto sentido, corresponden a algún segmento de la pila de llamadas y no a la pila completa. Tales continuaciones se pueden usar como funciones, llamadas varias veces, etc. Se abstraen usando el mecanismo : envuelve el bloque exterior, actúa como , pero recibe como argumento no una continuación global, sino limitada: la dependencia del valor del bloque de reinicio en el valor en lugar del bloque de cambio. Hay otras variedades, por ejemplo . call/ccshift/resetresetshiftcall/ccprompt/control
Muchos lenguajes de programación brindan esta capacidad con varios nombres, como:
En cualquier idioma que admita cierres , puede escribir programas de estilo de paso de continuación e implementar manualmente el call/cc. En particular, esta es una práctica aceptada en Haskell , donde las "mónadas que pasan continuaciones" se construyen fácilmente (por ejemplo, la mónada de la biblioteca Conty el transformador de mónadas ). ContTmtl