haskell scheme continuations callcc

haskell - ¿Implementación call/cc?



scheme continuations (5)

Estoy tratando de encontrar cómo se implementa call / cc. Lo mejor que he encontrado es este fragmento de Haskell:

callCC f = Cont $ /k -> runCont (f (/a -> Cont $ /_ -> k a)) k

Aunque esto no es tan simple como quiero debido a Cont y a runCont . También encontré descripciones de lo que hace, aunque nunca tan claro como el código real.

Entonces, ¿cómo se implementa en su forma más simple? Estoy etiquetando esto con Scheme y Haskell ya que esos son dos idiomas que prefiero.

Has escuchado el lado Haskell de la ecuación; Te daré el de Racket / Scheme, y el que sea más útil para ti, puedes correr con él.

Mi respuesta será mucho más corta, porque creo que la mejor fuente que puedo darte para la implementación de call / cc en un evaluador de raquetas simple proviene de PLAI de Shriram Krishnamurthi, específicamente la sección 20. Pensé en incluir la parte relevante del intérprete - está en la página 205 - pero después de tratar de reformatearlo varias veces, decidí que tendría más sentido en el lugar correcto en la página.

Una vez más, no estoy tratando de explicar la idea detrás de call / cc aquí, solo te señalo a una implementación en funcionamiento. Avísame si tienes otras preguntas.

call/cc es trivial de implementar. La parte difícil es configurar el entorno donde es posible implementarlo.

Primero debemos definir un entorno de ejecución de estilo de continuación de continuación (CPS). En este entorno, sus funciones (o cosas parecidas a funciones) no devuelven valores directamente; en su lugar, se les pasa una función que representa el "siguiente paso" en el cálculo, la "continuación", y pasan su resultado allí. En Haskell, esto se ve así:

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

Como puede ver, una acción de mónada Cont es realmente una función que toma una continuación (a -> r) , pasa un resultado a a la continuación y obtiene un resultado final de r , que simplemente pasa a su interlocutor ( es decir, una acción continua de mónada debe hacer cola en la continuación). runCont simplemente lo saca del envoltorio newtype; también podría pensar que invoca una acción con alguna continuación particular, como en runCont someAction someContinuation .

Entonces podemos convertir esto en una mónada:

instance Monad (Cont r) where return x = Cont $ /cc -> cc x (Cont f) (>>=) g = Cont $ /cc -> f (/r -> runCont (g r) cc)

Como puede ver, return solo obtiene un cc continuación y pasa su valor a la continuación. (>>=) es un poco más complicado, tiene que invocar f con una continuación que luego invoca g , recupera la acción y luego pasa la continuación externa a esta nueva acción.

Entonces, dado este marco, llegar a la continuación es simple. Solo queremos invocar una función con su continuación dos veces . La parte difícil es que debemos volver a envolver esta continuación en una nueva acción monádica que arroje la continuación existente. Así que analicémoslo un poco:

-- Invoke a raw continuation with a given argument, throwing away our normal -- continuation gotoContinuation :: (a -> r) -> a -> Cont r x gotoContinuation continuation argument = Cont $ /_ -> continuation argument -- Duplicate the current continuation; wrap one up in an easy-to-use action, and -- the other stays the normal continuation for f callCC f = Cont $ /cc -> runCont (f (gotoContinuation cc)) cc

Simple, ¿no?

En otros lenguajes como Scheme, el principio es el mismo, aunque puede implementarse como una primitiva del compilador; la razón por la que podemos hacerlo en Haskell es porque el paso de continuación fue algo que definimos en Haskell, no en un nivel inferior del tiempo de ejecución. Pero el principio es el mismo: primero necesita tener CPS, y luego call/cc es una aplicación trivial de este modelo de ejecución.

Al arriesgarme a estar fuera del lenguaje , creo que en Smalltalk las continuaciones se pueden implementar y comprender de la manera más fácil. La razón es que en Smalltalk la pila de ejecución se forma a partir de objetos normales a los que se puede acceder y manipular como cualquier otro objeto.

Para implementar un objeto de continuación simple, los siguientes dos métodos son necesarios. En el primer método, inicializamos la continuación iterando sobre los cuadros padre (remitente) (contextos) y copiando su estado (contador de programa, temporales, argumentos):

Continuation>>initializeFromContext: aContext context := aContext. stream := WriteStream on: (Array new: 200). [ context notNil ] whileTrue: [ stream nextPut: context. 1 to: context class instSize do: [ :index | stream nextPut: (context instVarAt: index) ]. 1 to: context size do: [ :index | stream nextPut: (context at: index) ]. context := context sender ]. values := stream contents

El segundo método es reanudar la ejecución: primero desenrollamos la pila actual (nuevamente es un simple bucle sobre la pila de ejecución), luego restauramos los marcos de pila capturados, los volvemos a unir al marco de pila actual thisContext y thisContext la ejecución con el argumento anObject :

Continuation>>value: anObject self terminate: thisContext. stream := values readStream. [ stream atEnd ] whileFalse: [ context := stream next. 1 to: context class instSize do: [ :index | context instVarAt: index put: stream next ]. 1 to: context size do: [ :index | context at: index put: stream next ] ] thisContext swapSender: values first. ^ anObject

Con estos dos métodos podemos construir callCC fácilmente:

Continuation class>>callCC: aBlock ^ aBlock value: (self new initializeFromContext: thisContext sender)

La belleza de este enfoque es que el código impreso muestra todo lo que se necesita para implementar una continuación completa (y de manera similar, otros tipos de continuación). No hay ningún comportamiento oculto en el sistema (VM). Uno puede usar un depurador para recorrer cada parte y observar cómo se manipula la pila de ejecución.

El código anterior es del marco web de Seaside . Para jugar con el código, es posible que desee utilizar una distribución ya hecha y navegar a las clases WAContinuation y WAContinuationTest .

"Implementing call/cc " realmente no tiene sentido en la capa en la que estás trabajando; si puede implementar call/cc en un idioma, eso significa que tiene una construcción incorporada al menos tan poderosa como call/cc . En el nivel del lenguaje en sí, call/cc es básicamente un operador de flujo de control primitivo, al igual que debe ser alguna forma de bifurcación.

Por supuesto, puede implementar un lenguaje con call/cc en un idioma sin él; esto es porque está en un nivel más bajo. Está traduciendo las construcciones del lenguaje de una manera específica, y organiza esta traducción para que pueda implementar call/cc ; es decir, en general, estilo de continuación de paso (aunque para la implementación no portátil en C, también puede simplemente copiar la pila directamente; trataré más adelante el estilo de continuación de paso). En realidad, esto no ofrece una gran idea de la call/cc sí misma : la idea está en el modelo con el que lo hace posible. Además de eso, call/cc es solo un contenedor.

Ahora, Haskell no expone una noción de continuación; rompería la transparencia referencial y limitaría las posibles estrategias de implementación. Cont se implementa en Haskell, al igual que cualquier otra mónada, y se puede considerar como un modelo de lenguaje con continuaciones que utilizan el estilo de continuación y paso, al igual que la lista de modelos de mónada no deterministas.

Técnicamente, esa definición de callCC sí escribe si solo eliminas las aplicaciones de Cont y runCont . Pero eso no te ayudará a entender cómo funciona en el contexto de la mónada Cont , así que veamos su definición en su lugar. (Esta definición no es la que se usa en la actual Biblioteca de transformadores Monad, ya que todas las mónadas se basan en sus versiones de transformadores, pero coincide con el uso de fragmentos de Cont (que solo funciona con la versión anterior), y simplifica las cosas dramáticamente)

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

OK, entonces Cont ra es simplemente (a -> r) -> r , y runCont nos permite obtener esta función fuera de un valor Cont ra . Suficientemente simple. Pero, ¿qué significa?

Cont ra es un cálculo de continuación-aprobación con resultado final r , y resultado a . ¿Qué significa el resultado final? Bueno, escribamos el tipo de runCont de runCont más explícita:

runCont :: Cont r a -> (a -> r) -> r

Entonces, como podemos ver, el "resultado final" es el valor que obtenemos de runCont al final. Ahora, ¿cómo podemos construir cálculos con Cont ? La instancia de la mónada es esclarecedora:

instance Monad (Cont r) where return a = Cont (/k -> k a) m >>= f = Cont (/k -> runCont m (/result -> runCont (f result) k))

Bueno, está bien, es esclarecedor si ya sabes lo que significa. La clave es que cuando escriba Cont (/k -> ...) , k es el resto de la computación , espera que le dé un valor a , y luego le dará el resultado final del cálculo (de teclee r , recuerde) atrás, que luego puede usar como su propio valor de retorno porque su tipo de devolución también es r . ¡Uf! Y cuando ejecutamos un cálculo de Cont con runCont , simplemente estamos especificando el k final - el "nivel superior" del cálculo que produce el resultado final.

¿Cómo se llama este "resto de la computación"? ¡Una continuación, porque es la continuación del cálculo!

(>>=) es bastante simple: ejecutamos el cálculo a la izquierda, dándole nuestro propio descanso de computación. Este rest-of-computation simplemente alimenta el valor en f , que produce su propio cálculo. Ejecutamos ese cálculo, alimentándolo con el resto del cálculo que se ha dado a nuestra acción combinada. De esta forma, podemos unir cálculos en Cont :

computeFirst >>= /a -> computeSecond >>= /b -> return (a + b)

o, en la notación do más familiar:

do a <- computeFirst b <- computeSecond return (a + b)

Entonces podemos ejecutar estos cálculos con runCont - la mayoría de las veces, algo así como runCont foo id funcionará bien, convirtiendo un foo con el mismo resultado y tipo de resultado final en su resultado.

Hasta aquí todo bien. Ahora hagamos las cosas confusas.

wtf :: Cont String Int wtf = Cont (/k -> "eek!") aargh :: Cont String Int aargh = do a <- return 1 b <- wtf c <- return 2 return (a + b + c)

¡¿Que está pasando aqui?! wtf es un cálculo de Cont con el resultado final String y resultado Int , pero no hay Int a la vista.

¿Qué sucede cuando ejecutamos aargh , digamos con runCont aargh show , es decir, ejecutamos el cálculo y show su resultado Int como una String para producir el resultado final?

¡Obtenemos "eek!" espalda.

¿Recuerdas que k es el "resto de la computación"? Lo que hemos hecho en wtf es astutamente no llamarlo, y en cambio proporcionar nuestro propio resultado final, que luego se convierte, ¡bueno, en definitivo!

Esto es solo lo primero que las continuaciones pueden hacer. Algo como Cont (/k -> k 1 + k 2) ejecuta el resto del cálculo como si devolviera 1, y nuevamente como si devolviera 2, ¡y suma los dos resultados finales! Las mejoras básicamente permiten expresar el flujo de control no local arbitrariamente complejo, haciéndolos tan poderosos como confusos. De hecho, las continuaciones son tan generales que, en cierto sentido, cada mónada es un caso especial de Cont . De hecho, puedes pensar en (>>=) en general como si usaras un tipo de estilo de continuación de paso:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

El segundo argumento es una continuación que toma el resultado del primer cálculo y devuelve el resto del cálculo que se ejecutará.

Pero todavía no he respondido a la pregunta: ¿qué está pasando con ese callCC ? Bueno, llama a la función que le das con la continuación actual. Pero espera un momento, ¿no es eso lo que estábamos haciendo con Cont ? Sí, pero compare los tipos:

Cont :: ((a -> r) -> r) -> Cont r a callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a

Huh. Verá, el problema con Cont es que no podemos secuenciar acciones desde el interior de la función que aprobamos, solo estamos produciendo un resultado r manera pura. callCC permite acceder a la continuación, callCC alto y, en general, ser manipulada desde cálculos de Cont . Cuando nosotros tenemos

do a <- callCC (/cc -> ...) foo ...

Puede imaginarse que cc es una función a la que podemos llamar con cualquier valor dentro de la función para hacer que el valor de retorno de callCC (/cc -> ...) mismo cómputo. O, por supuesto, podríamos devolver un valor normalmente, pero llamar a callCC en primer lugar sería un poco inútil :)

En cuanto a la misteriosa b , es solo porque puedes usar cc foo para representar cualquier tipo de cómputo que desees, ya que escapa al flujo de control normal y, como dije, lo usa inmediatamente como resultado de todo el callCC (/cc -> ...) . Por lo tanto, dado que nunca tiene que producir realmente un valor, puede salirse con la devolución de un valor de cualquier tipo que desee. ¡Furtivo!

Lo que nos lleva a la implementación real:

callCC f = Cont (/k -> runCont (f (/a -> Cont (/_ -> k a))) k)

Primero, obtenemos el resto del cálculo y lo llamamos k . Pero, ¿de qué se trata esta parte de f (/a -> Cont (/_ -> ka)) ? Bien, sabemos que f toma un valor de tipo (a -> Cont rb) , y eso es lo que es lambda - una función que toma un valor para usar como resultado de la callCC f , y devuelve un cálculo Cont que ignora su valor continuación y simplemente devuelve ese valor a través de k - el "resto de la computación" desde la perspectiva de callCC f . OK, entonces el resultado de esa llamada f es otro cálculo de Cont , del cual necesitaremos proporcionar una continuación para ejecutarlo. Acabamos de pasar la misma continuación otra vez ya que, si todo va bien, queremos que el cálculo que devuelve sea nuestro valor de retorno y continúe normalmente. (De hecho, pasar otro valor no tendría sentido , es "llamar con la continuación actual ", no "llamar con una continuación que no sea la que realmente me está ejecutando").

En general, espero que encuentres esto tan esclarecedor como largo. Las continuas son muy poderosas, pero puede llevar mucho tiempo obtener una intuición sobre cómo funcionan. Sugiero jugar con Cont (que tendrás que llamar cont para que las cosas funcionen con el mtl actual) y averiguar cómo obtienes los resultados que haces para tener una idea del flujo de control.

Se recomienda una lectura adicional sobre las continuaciones:

Bueno, proporcionaré una respuesta mucho más corta, basada en el Esquema, ya que también está etiquetada como "esquema".

Para comprender por qué su intento de implementar call/cc debe fallar, debe comprender qué es el estilo de continuación de paso . Una vez que entiendes eso, es bastante simple:

  • call/cc no se puede implementar en estilo directo.
  • Sin embargo, es trivial para implementar en el estilo de continuación de paso.

Pero para dar un poco más de información, el estilo de continuación de paso es una disciplina de control de flujo donde renuncia al uso de una pila de llamadas a favor de una convención de llamadas donde cada llamada de procedimiento pasa un argumento "extra": un cierre que se supone que el procedimiento llamado llamar cuando está "hecho" (pasando el "valor de retorno" como argumento). Estos cierres de argumentos adicionales se llaman continuaciones .

Cualquier programa puede traducirse mecánicamente en un estilo de continuación de aprobación, por medio de algo llamado, de manera apropiada, la transformación de CPS . De hecho, muchos sistemas Scheme funcionan así: el programa se analiza, se le aplica la transformación CPS y luego el árbol sintáctico abstracto CPS se interpreta o traduce al código objeto.

Así es como implementaría call/cc en el estilo de continuación de paso (usando la continuation como el nombre del argumento adicional para la continuación):

(define (call/cc-cps proc continuation) (proc continuation continuation))

Como debería poder ver, (a) no puede implementar esto en estilo directo (lo contrario de CPS), y (b) es trivial en CPS. call/cc es simplemente un procedimiento que toma otro procedimiento como su argumento y la continuación (obligatoria), y llama a ese procedimiento con la continuación tanto como su argumento como su continuación.