Ir a Haskell: ¿Alguien puede explicar este efecto aparentemente loco del uso de la mónada de continuación?

continuations monad-transformers

Question

A partir de this hilo (Control.Monad.Cont fun, 2005), Tomasz Zielonka presentó una función (comentada de forma clara y agradable por Thomas Jäger). Tomasz toma el argumento (una función) de un cuerpo de callCC y lo devuelve para su uso posterior con las dos definiciones siguientes:

import Control.Monad.Cont
...
getCC :: MonadCont m => m (m a)
getCC = callCC (/c -> let x = c x in return x)
getCC'' :: MonadCont m => a -> m (a, a -> m b)
getCC'' x0 = callCC (/c -> let f x = c (x, f) in return (x0, f))

Esos también se mencionan en Haskellwiki . Utilizándolos, puedes asemejarte a la semántica de Goto en haskell que se ve realmente genial:

import Control.Monad.Cont
getCC'' :: MonadCont m => a -> m (a, a -> m b)
getCC'' x0 = callCC (/c -> let f x = c (x, f) in return (x0, f))
main :: IO ()
main = (`runContT` return) $ do
(x, loopBack) <- getCC'' 0
lift (print x)
when (x < 10) (loopBack (x + 1))
lift (putStrLn "finish")

Esto imprime los números del 0 al 10.

Aquí viene el punto interesante. Usé esto junto con Writer Monad para resolver un cierto problema. Mi código se parece a lo siguiente:

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, UndecidableInstances #-}
import Control.Monad.Cont
import Control.Monad.Writer
getCC :: MonadCont m => m (m a)
getCC = callCC (/c -> let x = c x in return x)
getCC'' :: MonadCont m => a -> m (a, a -> m b)
getCC'' x0 = callCC (/c -> let f x = c (x, f) in return (x0, f))
-- a simple monad transformer stack involving MonadCont and MonadWriter
type APP= WriterT [String] (ContT () IO)
runAPP :: APP a -> IO ()
runAPP a= runContT (runWriterT a) process
where process (_,w)= do
putStrLn $ unlines w
return ()
driver :: Int -> APP ()
driver k = do
tell [ "The quick brown fox ..." ]
(x,loop) <- getCC'' 0
collect x
when (x<k) $ loop (x+1)
collect :: Int -> APP ()
collect n= tell [ (show n) ]
main :: IO ()
main = do
runAPP $ driver 4

Cuando compila y ejecuta este código, el resultado es:

The quick brown fox ...
4

Los números cero a tres son tragados en algún lugar en la profunda oscuridad de este ejemplo.

Ahora, en los estados "Real World Haskell" O''Sullivan, Goerzen y Stewart

"Apilar transformadores de mónada es análogo a las funciones de composición. Si cambiamos el orden en que aplicamos funciones y luego obtenemos resultados diferentes, no nos sorprenderá. Lo mismo ocurre con los transformadores de mónada". (Real World Haskell, 2008, P. 442)

Se me ocurrió la idea de cambiar los transformadores de arriba:

--replace in the above example
type APP= ContT () (WriterT [String] IO)
...
runAPP a = do
(_,w) <- runWriterT $ runContT a (return . const ())
putStrLn $ unlines w

Sin embargo, esto no se compilará porque no hay definición de instancia para MonadWriter en Control.Monad.Cont (razón por la cual hace poco hice esta pregunta ).

Agregamos una instancia dejando escuchar y pasar indefinido:

instance (MonadWriter w m) => MonadWriter w (ContT r m) where
tell = lift . tell
listen = undefined
pass = undefined

Agrega esas líneas, compila y ejecuta. Todos los números están impresos.

¿Qué ha sucedido en el ejemplo anterior?

Answer 1

Aquí hay una respuesta algo informal, pero afortunadamente útil. getCC'' devuelve una continuación al punto de ejecución actual; puedes pensar que es como guardar un marco de pila. La continuación devuelta por getCC'' tiene no solo el estado de ContT en el punto de la llamada, sino también el estado de cualquier mónada por encima de ContT en la pila. Cuando restaura ese estado llamando a la continuación, todas las mónadas construidas sobre ContT vuelven a su estado en el punto de la llamada getCC'' .

En el primer ejemplo, utiliza el type APP= WriterT [String] (ContT () IO) , con IO como la mónada base, luego ContT y finalmente WriterT . Así que cuando llamas a loop , el estado del escritor se desenrolla a lo que era en la llamada a getCC'' porque el escritor está por encima de ContT en la pila de mónadas. Cuando cambia ContT y WriterT , ahora la continuación solo desenrolla la mónada ContT porque es más alta que el escritor.

ContT no es el único transformador de mónada que puede causar problemas como este. Aquí hay un ejemplo de una situación similar con ErrorT

func :: Int -> WriterT [String] (ErrorT String IO) Int
func x = do
liftIO $ print "start loop"
tell [show x]
if x < 4 then func (x+1)
else throwError "aborted..."
*Main> runErrorT $ runWriterT $ func 0
"start loop"
"start loop"
"start loop"
"start loop"
"start loop"
Left "aborted..."

Aunque a la mónada del escritor se le indicaron los valores, todos se descartan cuando se ErrorT mónada ErrorT interna. Pero si cambiamos el orden de los transformadores:

switch :: Int -> ErrorT String (WriterT [String] IO) ()
switch x = do
liftIO $ print "start loop"
tell [show x]
if x < 4 then switch (x+1)
else throwError "aborted..."
*Main> runWriterT $ runErrorT $ switch 0
"start loop"
"start loop"
"start loop"
"start loop"
"start loop"
(Left "aborted...",["0","1","2","3","4"])

Aquí se conserva el estado interno de la mónada de escritor porque es inferior a ErrorT en la pila de mónada. La gran diferencia entre ErrorT y ContT es que el tipo de ErrorT deja en claro que cualquier cálculo parcial se descartará si se produce un error.

Definitivamente es más sencillo razonar sobre ContT cuando está en la parte superior de la pila, pero en ocasiones es útil para poder desenrollar una mónada en un punto conocido. Un tipo de transacción podría implementarse de esta manera, por ejemplo.

Answer 2

Pasé algún tiempo rastreando esto en el cálculo de λ. Se generaron páginas y páginas de derivaciones que no trataré de reproducir aquí, pero obtuve un poco de información sobre cómo funciona la pila de mónadas. Tu tipo se expande de la siguiente manera:

type APP a = WriterT [String] (ContT () IO) a
= ContT () IO (a,[String])
= ((a,[String]) -> IO()) -> IO()

También puede expandir el return del escritor, >>= , y tell , junto con el return de Cont, >>= y callCC . Sin embargo, rastrearlo es extremadamente tedioso.

El efecto del loop de llamada en el controlador es abandonar la continuación normal y, en su lugar, volver, de la llamada a getCC'' . Esa continuación abandonada contenía el código que habría agregado la x actual a la lista. Entonces, en cambio, repetimos el ciclo, pero ahora x es el siguiente número, y solo cuando alcanzamos el último número (y por lo tanto no abandonamos la continuación) armamos la lista de ["The quick brown fox"] y ["4"] .

Así como "Real World Haskell" enfatiza que la mónada IO necesita permanecer en la parte inferior de la pila, también parece importante que la mónada de continuación se mantenga en la parte superior.