31 votos

¿Puede un 'ST'-como Mónada ejecutarse exclusivamente (sin la biblioteca de 'ST')?

Este post es analfabeta Haskell. Sólo hay que poner en un archivo, como "pad.lhs" y ghci será capaz de ejecutarlo.

> {-# LANGUAGE GADTs, Rank2Types #-}
> import Control.Monad
> import Control.Monad.ST
> import Data.STRef

Bueno, a lo que yo era capaz de entender cómo se representa el ST mónada en código puro. Primero empezamos con nuestro tipo de referencia. Su valor específico no es realmente importante. La cosa más importante es que PT s a no debe ser isomorfo a cualquier otro tipo forall s. (En particular, debe ser isomorfo a ni () ni Void.)

> newtype PTRef s a = Ref {unref :: s a} -- This is defined liked this to make `toST'` work. It may be given a different definition.

El tipo de s es *->*, pero que realmente no es importante ahora. Podría ser polykind, para que todos nos importa.

> data PT s a where
>     MkRef   :: a -> PT s (PTRef s a)
>     GetRef  :: PTRef s a -> PT s a
>     PutRef  :: a -> PTRef s a -> PT s ()
>     AndThen :: PT s a -> (a -> PT s b) -> PT s b

Bastante recta hacia adelante. AndThen nos permite utilizar esto como un Monad. Usted puede estar preguntándose cómo return es implementado. Aquí está su mónada de instancia (solo respeta la mónada de las leyes con respecto a runPF, a ser definido más adelante):

> instance Monad (PT s) where
>     (>>=)    = AndThen
>     return a = AndThen (MkRef a) GetRef --Sorry. I like minimalism.
> instance Functor (PT s) where
>     fmap = liftM
> instance Applicative (PT s) where
>     pure  = return
>     (<*>) = ap

Ahora podemos definir fib como un caso de prueba.

> fib :: Int -> PT s Integer
> fib n = do
>     rold <- MkRef 0
>     rnew <- MkRef 1
>     replicateM_ n $ do
>         old <- GetRef rold
>         new <- GetRef rnew
>         PutRef      new  rold
>         PutRef (old+new) rnew
>     GetRef rold

Y que tipo de controles. Hurra!! Ahora, yo era capaz de convertir este a ST (ahora vemos por qué s tuvo que ser * -> *)

> toST :: PT (STRef s) a -> ST s a
> toST (MkRef  a        ) = fmap Ref $ newSTRef a
> toST (GetRef   (Ref r)) = readSTRef r
> toST (PutRef a (Ref r)) = writeSTRef r a
> toST (pa `AndThen` apb) = (toST pa) >>= (toST . apb)

Ahora podemos definir una función para que se ejecute PT sin hacer referencia a ST a todos los:

> runPF :: (forall s. PT s a) -> a
> runPF p = runST $ toST p

runPF $ fib 7 da 13, lo cual es correcto.


Mi pregunta es ¿podemos definir runPF sin referencia usando ST ?

Es allí una manera pura para definir runPF? PTRef's definición es completamente irrelevante; es sólo un marcador de posición de tipo de todos modos. Puede ser redefinido a lo que hace el trabajo.

Si usted no puede definir runPF pura, dar una prueba de que se puede.

El rendimiento no es una preocupación (si fue así, yo no habría hecho todo return tener su propio ref).

Estoy pensando que existencial tipos pueden ser útiles.

Nota: Es trivial si suponemos es a es dynamicable o algo. Estoy en busca de una respuesta que funciona con todos los a.

Nota: De hecho, una respuesta no necesariamente tiene que ver mucho con PT. Sólo se necesita ser tan poderoso como ST sin el uso de la magia. (Conversión de (forall s. PT s) es una especie de prueba de si una respuesta es válida o no.)

14voto

Benjamin Hodgson Puntos 3510

tl;dr: no Es posible sin los ajustes a la definición de PT. Aquí está el núcleo del problema: se le ejecuta su estado de cálculo en el contexto de algún tipo de medio de almacenamiento, pero dijo que el medio de almacenamiento tiene que saber cómo almacenar arbitraria tipos. Esto no es posible sin el embalaje algún tipo de evidencia en la MkRef constructor - un existencialmente envuelto Typeable diccionario como otros han sugerido, o una prueba de que el valor pertenece a uno de un conjunto finito de tipos.

Para un primer intento, vamos a tratar de usar una lista como el medio de almacenamiento y enteros para referirse a los elementos de la lista.

newtype Ix a = MkIx Int  -- the index of an element in a list

interp :: PT Ix a -> State [b] a
interp (MkRef x) = modify (++ [x]) >> gets (Ref . MkIx . length)
-- ...

Cuando se almacena un nuevo elemento en el medio ambiente, nos aseguramos de que se agregue al final de la lista, de modo que Refs hemos dado con anterioridad a cabo permanecer apuntando al elemento correcto.

Esto no es correcto. Puedo hacer una referencia a cualquier tipo a, pero el tipo de interp dice que el medio de almacenamiento es homogénea lista de bs. GHC nos ha bang a los derechos cuando rechaza este tipo de firma, quejándose de que no pueden igualar b con el tipo de la cosa dentro de MkRef.


Sin inmutarse, vamos a tener un ir en el uso de una heterogénea lista como el medio ambiente para el State mónada en el que vamos a interpretar PT.

infixr 4 :>
data Tuple as where
    E :: Tuple '[]
    (:>) :: a -> Tuple as -> Tuple (a ': as)

Este es uno de mis favoritos personales de Haskell tipos de datos. Es un extensible tupla indexados por una lista de los tipos de las cosas dentro de él. Las tuplas son heterogéneos listas vinculadas con el tipo de nivel de información acerca de los tipos de las cosas dentro de él. (Es a menudo llamado HList siguiente Kiselyov del papel , pero yo prefiero Tuple.) Cuando se agrega algo a la parte delantera de una tupla, el tipo al frente de la lista de tipos. En una poética del estado de ánimo, yo una vez lo puso de esta manera: "La tupla y su tipo de crecer juntos, como una vid crezca una planta de bambú."

Ejemplos de Tuples:

ghci> :t 'x' :> E
'x' :> E :: Tuple '[Char]
ghci> :t "hello" :> True :> E
"hello" :> True :> E :: Tuple '[[Char], Bool]

¿Qué hacer referencias a valores dentro de tuplas? Tenemos que demostrar a GHC que el tipo de la cosa vamos a salir de la tupla es de hecho el tipo que esperar.

data Elem as a where  -- order of indices arranged for convenient partial application
    Here :: Elem (a ': as) a
    There :: Elem as a -> Elem (b ': as) a

La definición de Elem es estructuralmente de los números naturales (Elem valores There (There Here) aspecto similar al de los números naturales como S (S Z)) pero con tipos adicionales - en este caso, lo que demuestra que el tipo a está en el tipo de nivel lista as. Menciono esto porque es sugerente: Nats hacer una buena lista de índices, y de la misma manera Elem es útil para la indización en una tupla. En este sentido, será útil como un reemplazo para el Int dentro de nuestro tipo de referencia.

(!) :: Tuple as -> Elem as a -> a
(x :> xs) ! Here = x
(x :> xs) ! (There ix) = xs ! ix

Necesitamos un par de funciones para trabajar con las tuplas y los índices.

type family as :++: bs where
    '[] :++: bs = bs
    (a ': as) :++: bs = a ': (as :++: bs)

appendT :: a -> Tuple as -> (Tuple (as :++: '[a]), Elem (as :++: '[a]) a)
appendT x E = (x :> E, Here)
appendT x (y :> ys) = let (t, ix) = appendT x ys
                      in (y :> t, There ix)

Vamos a intentar escribir un intérprete para una PT en Tuple medio ambiente.

interp :: PT (Elem as) a -> State (Tuple as) a
interp (MkRef x) = do
    t <- get
    let (newT, el) = appendT x t
    put newT
    return el
-- ...

No se puede hacer, buster. El problema es que el tipo de la Tuple en el entorno cambia cuando se obtiene una nueva referencia. Como he mencionado antes, añadir algo a una tupla agrega su tipo para la tupla del tipo, hecho desmentido por el tipo State (Tuple as) a. GHC no se deje engañar por este intento de subterfugio: Could not deduce (as ~ (as :++: '[a1])).


Esto es donde las ruedas, por lo que puedo contar. Lo que realmente quiero hacer es mantener el tamaño de la tupla constante a lo largo de un PT computación. Esto podría requerir que usted índice PT sí por la lista de tipos a los que se pueden obtener referencias, demostrando cada vez que lo que está permitido (por dar un Elem de valor). El medio ambiente a continuación, sería como una tupla de listas, y una referencia consistirá en un Elem (para seleccionar la lista de la derecha) y un Int (para encontrar el elemento en la lista).

Este plan rompe las reglas, por supuesto (es necesario cambiar la definición de la PT), pero también tiene problemas de ingeniería. Cuando llamo MkRef, la responsabilidad recae en mí para dar un Elem por el valor que estoy haciendo referencia, lo cual es bastante tedioso. (Dicho esto, usted puede realizar Elem valores implícitos con un hacky tipo de clase).

Otra cosa: componer PTs se convierte en difícil. Todas las partes de su cálculo tiene que ser indexados por la misma lista de tipos. Usted podría intentar introducir combinadores o clases que le permiten crecer en el ambiente de PT, pero también tendría que actualizar todas las referencias cuando hacen eso. El uso de la mónada sería muy difícil.

Posiblemente el limpiador de aplicación permitiría a la lista de tipos en un PT a variar a medida que usted camina alrededor de la tipo de datos: cada vez que encuentro un MkRef el tipo se pone uno más. Debido a que el tipo de la computación cambios a medida que avanza, no se puede utilizar un regular de la mónada - usted tiene que recurrir a IxMonad . Si usted quiere saber lo que el programa parece, ver a mi otra respuesta.

En última instancia, el punto de fricción es que el tipo de la tupla es determinado por el valor de la PT solicitud. El medio ambiente es lo que una petición determinada decide almacenar en ella. interp no se llega a elegir lo que es en la tupla, debe provenir de un índice en PT. Cualquier intento de engañar a ese requisito es que va a estrellarse y arder. Ahora, en una verdadera dependencia-escribió sistema que podría examinar la PT valor nos dieron y averiguar lo as debe ser. Por desgracia, Haskell no es un dependiente para cada tipo de sistema.

11voto

András Kovács Puntos 5385

Una solución simple es envolver un State mónada y el presente de la misma API ST. En este caso no hay necesidad de almacenar información de tipo en tiempo de ejecución, ya que puede estar determinado por el tipo de STRef-s, y el habitual ST s de cuantificación truco nos permite evitar que los usuarios se pelee hasta el contenedor de almacenamiento de las referencias.

Seguimos ref-s en un IntMap e incrementará el contador cada vez que se asigne un nuevo ref. La lectura y la escritura simplemente modifica el IntMap con algunos unsafeCoerce espolvoreado encima.

{-# LANGUAGE DeriveFunctor, GeneralizedNewtypeDeriving, RankNTypes, RoleAnnotations #-}

module PureST (ST, STRef, newSTRef, readSTRef, modifySTRef, runST) where

import Data.IntMap (IntMap, (!))
import qualified Data.IntMap as M

import Control.Monad
import Control.Applicative
import Control.Monad.Trans.State
import GHC.Prim (Any)
import Unsafe.Coerce (unsafeCoerce)

type role ST nominal representational
type role STRef nominal representational
newtype ST s a = ST (State (IntMap Any, Int) a) deriving (Functor, Applicative, Monad)
newtype STRef s a = STRef Int deriving Show

newSTRef :: a -> ST s (STRef s a)
newSTRef a = ST $ do
  (m, i) <- get
  put (M.insert i (unsafeCoerce a) m, i + 1)
  pure (STRef i)

readSTRef :: STRef s a -> ST s a
readSTRef (STRef i) = ST $ do
  (m, _) <- get
  pure (unsafeCoerce (m ! i))

writeSTRef :: STRef s a -> a -> ST s ()
writeSTRef (STRef i) a = ST $ 
  modify $ \(m, i') -> (M.insert i (unsafeCoerce a) m, i')

modifySTRef :: STRef s a -> (a -> a) -> ST s ()
modifySTRef (STRef i) f = ST $
  modify $ \(m, i') -> (M.adjust (unsafeCoerce f) i m, i')                      

runST :: (forall s. ST s a) -> a
runST (ST s) = evalState s (M.empty, 0)

foo :: Num a => ST s (a, Bool)
foo = do
  a <- newSTRef 0 
  modifySTRef a (+100)
  b <- newSTRef False
  modifySTRef b not
  (,) <$> readSTRef a <*> readSTRef b

Ahora, podemos hacer:

> runST foo
(100, True)

Pero la siguiente falla con la habitual ST tipo de error:

> runST (newSTRef True)

Por supuesto, el esquema anterior nunca de basura recoge referencias, sino que te libera de todo en cada runST llamada. Creo que un sistema más complejo podría implementar múltiples regiones distintas, cada una marcada por un parámetro de tipo, y asignar/recursos gratuitos en un grano más fino manera.

También, el uso de unsafeCoerce significa aquí que el uso de elementos internos directamente es tan peligroso como el uso de GHC.ST internos y State# directamente, por lo que debe asegurarse de presentar un seguro de API, y también a prueba nuestras interioridades de fondo (o por el contrario podemos obtener segfaults en Haskell, un gran pecado).

9voto

Benjamin Hodgson Puntos 3510

Ya he publicado mi anterior respuesta, ha indicado que no le importa hacer cambios en su definición de PT. Estoy feliz de informar: relaja la restricción a los cambios de la respuesta a su pregunta de no a yes! Ya he argumentado que usted necesita para un índice de su mónada por el conjunto de tipos en el medio de almacenamiento, así que aquí tiene algunas código de trabajo que muestra cómo hacerlo. (Yo tenía originalmente esto como una edición a mi respuesta anterior pero lo tengo muy largo, así que aquí estamos.)

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE GADTs #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE RebindableSyntax #-}
{-# LANGUAGE TypeOperators #-}

import Prelude

Vamos a necesitar de una forma más inteligente Monad de la clase que en el Preludio: la de indexado mónada cosas como describir rutas de acceso a través de un grafo dirigido. Por razones que debe ser evidente, voy a definir indexado functors así.

class FunctorIx f where
    imap :: (a -> b) -> f i j a -> f i j b

class FunctorIx m => MonadIx m where
    ireturn :: a -> m i i a
    (>>>=) :: m i j a -> (a -> m j k b) -> m i k b

(>>>) :: MonadIx m => m i j a -> m j k b -> m i k b
ma >>> mb = ma >>>= \_ -> mb

replicateM_ :: MonadIx m => Int -> m i i a -> m i i ()
replicateM_ 0 _ = ireturn ()
replicateM_ n m = m >>> replicateM_ (n - 1) m

Indizada a la mónada utiliza el tipo de sistema para rastrear el progreso de un estado de la computación. m i j a es un monádico de cálculo que requiere un estado de entrada de i, cambia el estado a j, y produce un valor de tipo a. La secuenciación indexado mónadas con >>>= es como jugar al dominó. Usted puede alimentar a un cálculo que toma el estado de i a j en un cálculo que va desde j a k, y obtener un mayor cálculo de i a k. (Hay una versión más ricos de esta indexado mónada se describe en Kleisli Flechas de la mala Fortuna (y otros lugares), pero esto es más que suficiente para nuestros propósitos).

Una posibilidad con MonadIx es File mónada que realiza el seguimiento del estado de un identificador de archivo, asegurando no te olvides de recursos gratuitos. fOpen :: File Closed Open () comienza con un cerrado archivo y lo abre, fRead :: File Open Open String devuelve el contenido de un archivo abierto, y fClose :: File Open Closed () toma un archivo de abierto a cerrado. El run operación se lleva a un cálculo de tipo File Closed Closed a, lo que garantiza que los identificadores de archivo siempre asearse.

Pero me desvío del tema: aquí nos interesa no con un identificador de archivo, pero con un conjunto de escribir "lugares de la memoria"; los tipos de las cosas en la memoria de la máquina virtual de banco se lo vamos a utilizar para la mónada de índices. Me gusta tener mi "programa/intérprete de" mónadas gratis porque expresa el hecho de que los resultados en vivo en las hojas de cálculo, y promueve composability y la reutilización de código, así que aquí está el functor que producirá PT cuando conectamos en FreeIx a continuación:

data PTF ref as bs r where
    MkRef_ :: a -> (ref (a ': as) a -> r) -> PTF ref as (a ': as) r
    GetRef_ :: ref as a -> (a -> r) -> PTF ref as as r
    PutRef_ :: a -> ref as a -> r -> PTF ref as as r

instance FunctorIx (PTF ref) where
    imap f (MkRef_ x next) = MkRef_ x (f . next)
    imap f (GetRef_ ref next) = GetRef_ ref (f . next)
    imap f (PutRef_ x ref next) = PutRef_ x ref (f next)

PTF es programable por el tipo de referencia ref :: [*] -> * -> * - referencias permitido saber que los tipos están en el sistema - y catalogados por la lista de tipos que se almacena en el intérprete de "la memoria"". El caso interesante es MkRef_: hacer una nueva referencia agrega un valor de tipo a a la memoria, teniendo en as a a ': as; la continuación espera un ref en el entorno ampliado. El resto de operaciones no cambiar la lista de tipos en el sistema.

Cuando creo referencias de forma secuencial (x <- mkRef 1; y <- mkRef 2), que vas a tener diferentes tipos: el primero será un ref (a ': as) a y el segundo será un ref (b ': a ': as) b. Para hacer que los tipos de línea, necesito una manera de utilizar una referencia en un entorno de mayor tamaño que el que se creó. En general, esta operación depende del tipo de referencia, así que voy a poner en una clase.

class Expand ref where
    expand :: ref as a -> ref (b ': as) a

Una posible generalización de esta clase sería envolver el patrón de repetidas aplicaciones de expand, con un tipo como inflate :: ref as a -> ref (bs :++: as) a.

He aquí otro reutilizables poco de la infraestructura, la indexado libre mónada que he mencionado anteriormente. FreeIx se convierte en un índice functor en indizada a la mónada proporcionando un tipo de alineado a unirse a la operación Free, que los lazos de la recursivo nudo en el functor del parámetro, y no hacer nada operación Pure.

data FreeIx f i j a where
    Pure :: a -> FreeIx f i i a
    Free :: f i j (FreeIx f j k a) -> FreeIx f i k a

lift :: FunctorIx f => f i j a -> FreeIx f i j a
lift f = Free (imap Pure f)

instance FunctorIx f => MonadIx (FreeIx f) where
    ireturn = Pure
    Pure x >>>= f = f x
    Free love {- , man -} >>>= f = Free $ imap (>>>= f) love

instance FunctorIx f => FunctorIx (FreeIx f) where
    imap f x = x >>>= (ireturn . f)

Una desventaja de libre mónadas es repetitivo usted tiene que escribir para hacer Free y Pure más fácil trabajar con. Aquí hay algunas de una sola acción PTs que forman la base de la mónada de la API, y algunos patrón de sinónimos para ocultar la Free constructores cuando nos desempaquetar PT valores.

type PT ref = FreeIx (PTF ref)

mkRef :: a -> PT ref as (a ': as) (ref (a ': as) a)
mkRef x = lift $ MkRef_ x id

getRef :: ref as a -> PT ref as as a
getRef ref = lift $ GetRef_ ref id

putRef :: a -> ref as a -> PT ref as as ()
putRef x ref = lift $ PutRef_ x ref ()

pattern MkRef x next = Free (MkRef_ x next)
pattern GetRef ref next = Free (GetRef_ ref next)
pattern PutRef x ref next = Free (PutRef_ x ref next)

Eso es todo lo que necesita para ser capaz de escribir PT cálculos. Aquí está tu fib ejemplo. Estoy usando RebindableSyntax local y la redefinición de la mónada operadores (a indizado equivalentes) para que yo pueda usar do de notación en mi indexado mónada.

-- fib adds two Ints to an arbitrary environment
fib :: Expand ref => Int -> PT ref as (Int ': Int ': as) Int
fib n = do
    rold' <- mkRef 0
    rnew <- mkRef 1
    let rold = expand rold'
    replicateM_ n $ do
        old <- getRef rold
        new <- getRef rnew
        putRef new rold
        putRef (old+new) rnew
    getRef rold
        where (>>=) = (>>>=)
              (>>) = (>>>)
              return :: MonadIx m => a -> m i i a
              return = ireturn
              fail :: MonadIx m => String -> m i j a
              fail = error

Esta versión de fib se ve como la que quería escribir en la pregunta original. La única diferencia (aparte de la local de enlaces de >>= y así sucesivamente) es la llamada a expand. Cada vez que cree una nueva referencia, usted tiene que expand todos los viejos, lo cual es un poco tedioso.

Finalmente podemos terminar el trabajo que nos propusimos hacer y construir una PT-máquina que utiliza una Tuple como el medio de almacenamiento y Elem como el tipo de referencia.

infixr 5 :>
data Tuple as where
    E :: Tuple '[]
    (:>) :: a -> Tuple as -> Tuple (a ': as)

data Elem as a where
    Here :: Elem (a ': as) a
    There :: Elem as a -> Elem (b ': as) a

(!) :: Tuple as -> Elem as a -> a
(x :> xs) ! Here = x
(x :> xs) ! There ix = xs ! ix

updateT :: Elem as a -> a -> Tuple as -> Tuple as
updateT Here x (y :> ys) = x :> ys
updateT (There ix) x (y :> ys) = y :> updateT ix x ys

El uso de un Elem en un mayor tupla que la que se construyó para, sólo se necesita para hacer que se vea más abajo en la lista.

instance Expand Elem where
    expand = There

Tenga en cuenta que este despliegue de Elem se parece bastante a una de Bruijn índice: más recientemente variables vinculadas tienen menores índices.

interp :: PT Elem as bs a -> Tuple as -> a
interp (MkRef x next) tup = let newTup = x :> tup
                            in interp (next $ Here) newTup
interp (GetRef ix next) tup = let x = tup ! ix
                              in interp (next x) tup
interp (PutRef x ix next) tup = let newTup = updateT ix x tup
                                in interp next newTup
interp (Pure x) tup = x

Cuando el intérprete se encuentra con un MkRef solicitud, se aumenta el tamaño de su memoria mediante la adición de x a la parte delantera. El comprobador de tipos le recordamos que cualquier refs desde antes de la MkRef debe ser correctamente expanded, de modo referencias existentes no se desequilibran cuando la tupla cambia de tamaño. Hemos pagado por un intérprete sin inseguro moldes, pero llegamos a la integridad referencial para el arranque.

Se ejecuta desde un principio permanente requiere que el PT cálculo espera comenzar con el vacío de un banco de memoria, pero que nos permitirá final, en cualquier estado.

run :: (forall ref. Expand ref => PT ref '[] bs a) -> a
run x = interp x E

Es typechecks, pero ¿funciona?

ghci> run (fib 5)
5
ghci> run (fib 3)
2

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X