Cuándo usar CPS vs codensidad vs reflexión sin remordimientos en Haskell

reflection monads

Question

¿Hay alguna regla general para cuándo usar el estilo de paso de continuación frente a la codensidad frente a la reflexión sin remordimientos al crear mónadas en Haskell?

Como ejemplo, voy a utilizar una simple mónada coroutina. Si nunca ha visto esto antes, puede consultar el artículo "Coroutine Pipelines" en Monad.Reader Issue 19 o la biblioteca de pipes . El código completo para los siguientes ejemplos se puede encontrar en este repositorio .

1. Normal

   Esto es solo una mónada normal definida como un tipo de datos:

   data FooM i o a
     = Await (i -> FooM i o a)
     | Yield o (FooM i o a)
     | Done a

   Este estilo es usado extensivamente a través del ecosistema de Haskell. Un ejemplo de este estilo es el tipo de datos Proxy de las pipes .

2. Estilo de paso de la continuación (CPS)

   Esto es similar al estilo normal , pero cada constructor de datos se ha convertido en un argumento para una continuación:

   newtype FooCPS i o a = FooCPS
     { runFooCPS
         :: forall r.
            ((i -> FooCPS i o a) -> r)
         -> (o -> FooCPS i o a -> r)
         -> (a -> r)
         -> r
     }

   Este estilo se usa tanto en attoparsec como en parsec .

3. Codensidad

   Este estilo utiliza un transformador de mónada de codensidad envuelto alrededor de una mónada definida en el estilo normal . Esto da O (1) enlace asociativo a la izquierda.

   El transformador de mónada codensity se parece a lo siguiente:

   newtype Codensity m a = Codensity
     { runCodensity :: forall b. (a -> m b) -> m b
     }

   Nuestra mónada real podría definirse como un nuevo tipo con el transformador Codensity . Observe cómo FooCodensity está utilizando FooM internamente.

   newtype FooCodensity i o a = FooCodensity
     { runFooCodensity :: Codensity (FooM i o) a
     }

   Este estilo es utilizado por conduit en el tipo ConduitM .

4. Reflexión sin remordimientos

   Este es el estilo discutido en el artículo Reflexión sin remordimiento .

   Esto es similar al estilo normal , pero las llamadas recursivas se han convertido en una estructura de datos con O (1) adjunto y amortizado O (1). Esto da O (1) enlace asociativo a la izquierda y reflexión monádica a la mónada FooRWR :

   data FooRWR i o a
     = AwaitRWR (forall x. i -> FooExplicit i o x a)
     | YieldRWR  o (forall x. FooExplicit i o x a)
     | DoneRWR a

   El tipo FooExplicit se define como lo siguiente:

   type FooExplicit i o = FTCQueue (FooRWR i o)

   FTCQueue es una estructura de datos con O (1) anexado y amortizado O (1).

   Este estilo es usado por los paquetes de freer-effects y extensible . Está disponible como una biblioteca independiente en monad-skeleton .

¿Cuándo se debe usar normal vs CPS vs codensity vs reflexión sin remordimiento ? Me imagino que una respuesta rápida y difícil requeriría una evaluación comparativa de una mónada y una aplicación determinadas, pero ¿hay alguna regla práctica ?

De mi propia investigación, he encontrado las siguientes ideas / comentarios:

• El CPS puede ser más rápido que el estilo normal porque es posible que no tenga que hacer un análisis de casos. Aunque la aceleración real puede variar según la forma en que GHC compila el código. La codensidad y la reflexión sin remordimientos tienen algo de sobrecarga.

  Gabriel Gonzalez (el autor de pipes ) escribe acerca de cómo se mantiene con el estilo normal de las pipes tanto en este hilo reddit como en este issue en Github.

  Bryan O''Sullivan (el autor de attoparsec ) escribe sobre cómo el cambio de attoparsec del estilo normal al CPS dio un factor de 8 de aceleración . Algunos de los comentarios en esa publicación también hablan sobre el estilo normal vs CPS .

• Si necesita vínculos asociativos profundos a la izquierda, el estilo normal y el CPS terminan con un tiempo de ejecución cuadrático.

  Aquí hay un ejemplo del artículo "Reflexión sin remordimientos" que mostrará un tiempo de ejecución cuadrático.

  data It i a = Get (i -> It i a) | Done a
  
  sumInput :: Int -> It Int Int
  sumInput n = Get (foldl (>=>) return (replicate (n - 1) f))
    where
      f x = get >>= return . (+ x)

  Si sumInput se reescribe con codensidad o reflexión sin remordimientos , funcionará perfectamente rápido.

  Si su aplicación tiene profundos vínculos asociativos hacia la izquierda, probablemente debería usar codensidad o reflexión sin remordimientos .

  Michael Snoyman (autor de conduit ) habla sobre esto en una publicación del blog sobre cómo acelerar el conduit .

  La biblioteca de pipes utilizada para proporcionar un transformador de codensidad.

• El CPS y la codensidad no admiten la reflexión O (1).

  Aquí hay una función que requiere reflexión monádica. Este ejemplo está adaptado del documento "Reflexión sin remordimientos":

  data It i a = Get (i -> It i a) | Done a
  
  par :: It i a -> It i b -> It i (It i a, It i b)
  par l r
    | Done <- l = Done (l, r)
    | Done <- r = Done (l, r)
    | Get f <- l, Get g <- r = Get Done >>= /x -> par (f x) (g x)

  Este método no se puede escribir en el estilo CPS o codensity sin volver a convertir primero al estilo normal . El estilo de reflexión sin remordimientos no tiene este problema.

  Si necesita una reflexión monádica, probablemente debería usar un estilo normal o una reflexión sin remordimientos .

• La reflexión sin remordimientos agrega cierta sobrecarga, pero es el único estilo que proporciona a O (1) enlace y reflexión asociativos por la izquierda.

pregunta adicional : se podría hacer una pregunta similar sobre Free (estilo normal ) vs F ( CPS ) del paquete free . ¿Cuándo debería usarse Free ? ¿Cuándo debe usarse F ?

Answer 1

Este problema se puede dividir en dos partes: cómo representa el tipo de datos y cómo los compone juntos.

Tipos de datos

Los estilos enumerados utilizan solo 2 estilos de tipos de datos, el estilo "normal" y el estilo de paso de continuación. Difieren en qué objetos se eligen como primitivos del lenguaje.

En el estilo normal, los tipos de datos y sus constructores se eligen como primitivos. Los tipos de datos son sumas (que tienen múltiples constructores) de productos (que contienen valores múltiples)

data Sum a b = Left a | Right b
data Product a b = Product a b

Los principales objetos del lenguaje son estos tipos de datos y funciones; Las funciones deconstruyen los datos para mirar dentro y ver lo que hace.

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l _ (Left a)  = l a
either _ r (Right b) = r b

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry f (Product a b) = f a b

Puede crear un lenguaje equivalente en el que los tipos cuantificados universalmente se traten como primitivos en lugar de tipos de datos. En este caso, puede definir los tipos de datos en términos de cuantificación universal. Las sumas se representan mediante su función, cuantificada universalmente sobre el tipo de retorno. Los productos están representados por su función no uncurry , cuantificada universalmente sobre el tipo de retorno. La necesidad de una extensión de idioma ( RankNTypes ) para representar los tipos de datos de esta manera sugiere por qué llamaríamos al primer estilo "normal".

{-# LANGUAGE RankNTypes #-}

newtype Product a b = Product (forall r. (a -> b -> r) -> r)

product :: a -> b -> Product a b
product a b = Product (/f -> f a b)

uncurry :: (a -> b -> c) -> Product a b -> c
uncurry both (Product f) = f both

newtype Sum a b = Sum (forall r. (a -> r) -> (b -> r) -> r)

left :: a -> Sum a b
left a = Sum (/l r -> l a)

right :: b -> Sum a b
right b = Sum (/l r -> r b)

either :: (a -> c) -> (b -> c) -> Sum a b -> c
either l r (Sum f) = f l r

Esto da lugar a una de las principales diferencias entre los dos estilos. En el estilo universalmente cuantificado no hay constructores. Toda la estructura de los datos debe almacenarse en cierres de funciones, que es exactamente donde están los reemplazos para los constructores a la left , a la right y al product . En el estilo universalmente cuantificado no puedes construir ningún objeto intermedio innecesario; no existe ningún objeto para que usted construya. Todavía se pueden construir cierres intermedios innecesarios. Como mínimo, engañará al generador de perfiles para que le diga que no tiene un montón de objetos dando vueltas.

Su tipo de datos FooM , que se repite aquí, también se puede representar en estilo de paso de continuación.

data FooM i o a
  = Await (i -> FooM i o a)
  | Yield o (FooM i o a)
  | Done a

Estará representado por su función matchFoo , que he definido.

matchFoo :: ((i -> FooM i o a) -> r) -> (o -> FooM i o a -> r) -> (a -> r) -> r
matchFoo a _ _ (Await f) = a f
matchFoo _ y _ (Yield o next) = y o next
matchFoo _ _ d (Done a) = d a

El FooM cuantificado universalmente identifica un FooM con su función matchFoo , calificado universalmente sobre su tipo de retorno.

newtype FooCPS i o a = FooCPS
  { runFooCPS
      :: forall r.
         ((i -> FooCPS i o a) -> r)
      -> (o -> FooCPS i o a -> r)
      -> (a -> r)
      -> r
  }

await :: (i -> FooCPS i o a) -> FooCPS i o a
await f = FooCPS (/a _ _ -> a f)

yield :: o -> FooCPS i o a -> FooCPS i o a
yield o next = FooCPS (/_ y _ -> y o next)

done :: a -> FooCPS i o a
done a = FooCPS (/_ _ d -> d a)

Romper el problema en 2

Para usar el mismo tipo de datos para todas las formas de componerlos juntos, vamos a reemplazar FooM con su funtor base. El functor base es el tipo de datos normal con recursiones reemplazadas por una variable de tipo.

data FooF i o a next
  = Await (i -> next)
  | Yield o next
  | Done a
    deriving (Functor)

Puede definir de manera equivalente un funtor base en el estilo de paso de continuación.

newtype FooFCPS i o a next = FooFCPS
  { runFooCPS
      :: forall r.
         ((i -> next) -> r)
      -> (o -> next -> r)
      -> (a -> r)
      -> r
  }
  deriving (Functor)

Componiéndolos de nuevo juntos

1. Normal

Podemos recuperar inmediatamente FooM definiendo

newtype FooM i o a = FooM (FooF i o a (FooM i o a))

Si ya has definido el punto fijo de un functor :

newtype Fix f = Fix (f (Fix f))

Entonces FooM puede ser recuperado por

newtype FooM i o a = FooM (Fix (FooF i o a))

2. Estilo de paso continuo

El estilo de paso de continuación se puede recuperar inmediatamente del FooFCPS cuantificado universalmente

newtype FooCPS i o a = FooCPS (Fix (FooFCPS i o a))

3. Codensidad

El transformador de codensidad funciona con FooM o FooCPS .

4. Reflexión sin remordimientos

Podemos definir la reflexión sin remordimientos en términos de funtores de base sin reproducir el tipo de datos FooM en FooRWR .

newtype RWR f a = RWR { runRWR :: f (RWRExplicit f a) }

newtype RWRExplicit f a = RWRExplicit (forall x. FTCQueue (RWR f) x a)

Y luego recuperar FooRWR con

newtype FooRWR i o a = FooRWR {runFooRWR :: RWR (FooF i o a) a}

Observaciones extra

Gratis

Tanto Free como F trabajarán con cualquiera de los funtores base FooF o FooFCPS .

Transformadores de mónada

El funtor base también se puede utilizar para construir un transformador de mónada. Hay una discusión detallada de FooM construir el transformador MachineT (que está estrechamente relacionado con FooM ) en esta pregunta y respuesta .

La afirmación de que par no se puede escribir en CPS sin volver a convertir primero al estilo normal necesita alguna calificación, ya que todos los tipos de datos pueden reemplazarse con tipos de estilo de paso de continuación cuantificados universalmente.