Programación monádica



Descargar 11,78 Kb.
Fecha de conversión17.09.2017
Tamaño11,78 Kb.

Programación monádica

  • Las variaciones del evaluador tienen una estructura similar. Abstrayendo en esta estructura podemos introducir la noción de mónada:
  • En cada variación introdujimos un tipo de computación, M digamos, donde M representa respectivamente computaciones que podrían levantar excepciones, actuar sobre un estado y generar salida.
  • El evaluador original tiene tipo Term  Int, mientras que cada una de sus variaciones tiene tipo Term  M Int.
  • En general, una función de tipo a  b es reemplazada por una función de tipo a  M b. Este tipo puede ser entendido como el de aquellas funciones que aceptan un argumento de tipo a y retornan un valor de tipo b, con un posible efecto lateral que es el que captura M.

Operaciones de M

  • Qué clase de operaciones sobre M son requeridas?
  • Necesitamos una forma de transformar un valor en una computación que retorna ese valor y no efectúa ninguna otra acción:
  • return :: a  M a
  • Necesitamos aplicar una función de tipo a  M b a una computación de tipo M a :
  • () :: M a(a  M b) M b
  • Una mónada es una tripleta (M,return, que consistede un constructor de tipos M y dos operaciones con los tipos polimórficos arriba presentados.

Operaciones de M (2)

  • Composición de computaciones:
  • m \a n
  • Lectura:
  • Efectúe la computación m, ligue a al valor resultante y luego efectúe la computación n.
  • Secuencia de computaciones:
  • (aM b M b
  • Lectura de m n:
  • Efectúe la computación m y luego la computación n.
  • Cómo definir usando 

Mónadas en Haskell

  • Las clases Monad, MonadZero y MonadPlus:
  • class Monad m where
  • return :: a  M a
  • () :: M a(a  M b) M b
  • (MaM b M b
  • m n = m \n
  • class (Monad M) MonadZero M where
  • zero :: M a
  • class (MonadZero m) MonadPlus m where
  • (++) :: M a M a M a

La mónada Excepción

  • En esta mónada una computación puede levantar una excepción o retornar un valor.
  • data Exc a= Raise Exception | Return a
  • type Exception = String
  • instance Monad Exc where
  • return x = Return x
  • (Raise e) q = Raise e
  • (Return x)  q = q x
  • return x simplemente retorna el valor x
  • p q examina el resultado de la computación p, si es una excepción entonces es re-levantada, sino la función q es aplicada al valor retornado.

Operaciones de Excepción

  • (no abstractas)
  • raise :: Exception Exc a
  • raise = Raise
  • (escape) :: Exc aExc aExc a
  • (Raise _ ) escape n = n
  • (Return x) escape n = Return x
  • elim :: Exc a(a b) (Exceptionbb
  • elim (Raise e) f g = g e
  • elim (Return x) f g = f x
  • (abstracta)
  • updateError :: Exc a Exception Exc a
  • updateError m str = elim m return (raise . (++ str))

Expresiones do

  • La expresión do permite usar una sintaxis más legible para expresar programación monádica.
  • Sintaxis Semántica (traducción al kernel)
  • exp -> do { stmts [;]}
  • stmts -> exp [; stmts] do {e} = e
  • | pat exp ; stmts do {e;stmts} = e do {stmts}
  • | let decllist ; stmts do {p e ; stmts} = e \p -> do{stmst}
  • do {let decllist; stmts} = let decllist in do{stmts}

Un Evaluador Monádico

  • El evaluador es ahora escrito usando una mónada m:
  • eval :: Monad m Term m Int
  • eval (Con x) = return x
  • eval (Div t u) =
  • do x eval t
  • y  eval u
  • return (x div y)
  • El tipo de eval indica que esta función dado un Term efectúa una computación m y retorna un valor de tipo Int.
  • La estructura de este evaluador es un poco más compleja que la del original, pero es más flexible: cada una de las variaciones discutidas puede ser obtenida fácilmente.

El evaluador original

  • En este evaluador la computación es simplemente el valor retornado.
  • Introducimos entonces la monad identidad:
  • newtype Id = MkId 
  • instance Monad Id where
  • return x = MkId x
  • (MkId x)  q = q x
  • Id es isomorfo a la función identidad de tipos
  • return es isomorfo a la función identidad
  •  es isomorfo a la aplicación de funciones
  • instance Show Show (Id ) where
  • show (MkId x) = “value: “ ++ show x
  • evalId :: Term Id Int
  • evalId = eval

Manejo de errores

  • Para agregar manejo de errores tomamos el evaluador monádico y reemplazamos el término return (x div y) por una expresión condicional.
  • evalEx :: Term Exc Int
  • evalEx (Con x) = return x
  • evalEx (Div t u) =
  • do x evalEx t
  • y evalEx u
  • if y == 0
  • then raise “division by zero”
  • else return (x div y)

Estado

  • En la mónada estado, una computación acepta un estado inicial y retorna una pareja consistente de un valor y el estado final.
  • instance Monad St where
  • return x = MkSt f
  • where f = \s (x,s)
  • p  q = MkSt f
  • where f = \s apply (q x) s’
  • where (x,s’) = apply p s
  • return x retorna el transf. de estado que devuelve el valor x y deja incambiado el estado.
  • una llamada a p  q aplica el transf. p al estado inicial s, lo que retorna un valor x y el estado intermedio s’. Luego, el transf. q x es aplicado a s’.

Contando ejecuciones

  • Una operación específica de la monad St es:
  • tick :: St ()
  • tick = MkSt f
  • where f = \s ((), s + 1)
  • Para agregar conteo de ejecuciones tomamos el evaluador monádico y sólo agregamos una llamada a tick en el lugar adecuado.
  • evalSt :: Term St Int
  • evalSt (Con x) = return x
  • evalSt (Div t u) =
  • do x evalSt t
  • y evalSt u
  • tick
  • return (x div y)

Salida

  • En la monad de salida una computación consiste en el par formado por la salida generada y el valor final.
  • instance Monad Out where
  • return x = MkOut (“”, x)
  • p  q = MkOut (ox ++ oy, y)
  • where
  • MkOut (ox,x) = p
  • MkOut (oy, y) = q x
  • return x retorna el par que consiste en la salida vacía y el valor x
  • p  q extrae una salida ox y el valor x a partir de la computación p, luego extrae una salida oy y el valor y del resultado de la computación q, y finalmente devuelve la salida formada por la concatenación de ox y oy y el valor final y.

Desplegando trazas de ejecución

  • Una operación específica de la mónada Out es:
  • out :: Output Out ()
  • out ox = MkOut (ox, ())
  • Para agregar trazas de ejecución, decoramos al evaluador monádico original con las correpondientes llamadas para generar salida:
  • evalOut :: Term  Out Int
  • evalOut (Con x) = do {out (line (Con x) x) ; return x}
  • evalOut (Div t u) =
  • do x evalOut t
  • y evalOut u
  • let z = (x div y)
  • out (line (Div t u)) z
  • return z

Combinando estado con excepciones

  • module MonadStExc where
  • import Exception
  • data StE st a = MkStE (st Exc (a , st))
  • applyStE :: Ste st a stExc (a , st))
  • applyStE (MkStE f) st = f st
  • instance Monad (StE st) where
  • return a = MkStE (\s  return (a,s))
  • (MkStE f) g = MkStE h
  • where h = \s  do (a , s’) f s
  • applyStE (g a) s’

Operaciones de StE

  • (no abstractas)
  • raiseStE :: Exception StE st a
  • raiseStE e = MkStE (\s  raise e)
  • getStE :: StE st st
  • getStE = MkStE (\s  return (s , s))
  • putStE :: st StE st ()
  • putStE st = MkStE (\_  return (() , st))
  • (abstractas)
  • updateStE :: (st stStE st ()
  • updateStE f = getStE (putStE . f)
  • stripStE :: StE st a stExc a
  • stripStE f st = applyStE f s (return . fst)


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal