Operational semantics for monads

While randomly browsing around on Planet Haskell I’ve found a post on Heinrich Apfelmus‘ blog about something called “operational semantics” for monads. Found it very iluminating. Basically it’s a form to implement monads focusing not on defining the bind and return operators, but on what the monad is really supposed to do. It’s a view where a monad define a Domain Specific Language, that must be interpreted in order to cause it’s effects. It seems to me it’s exactly what is implemented in the monadprompt (Control.Monad.Prompt) package, although I’m not sure.

> {-# LANGUAGE GADTs #-}
> import Control.Monad
> import Data.Map (Map, fromList, unionWith)

The definition of a monad on this approach starts with a common interface given by the following data type and a singleton function:

> data Program m a where
>     Then   :: m a -> (a -> Program m b) -> Program m b
>     Return :: a -> Program m a
>
> singleton :: m a -> Program m a
> singleton i = i `Then` Return

Note that the types of the data constructors Then and Return are very similar (but not equal…) to the types of the monadic operations (>>=) and return. This identification of class functions with data constructors is recurring throughout this post. This data type is instanciated as a traditional monad as follows:

>instance Monad (Program m) where
>    return = Return
>    (Return a)    >>= f  = f a
>    (i `Then` is) >>= f  = i `Then` (\ x -> is x >>= f)

This is all we need! As an example let’s describe the implementation of the State Monad within this approach. This is exactly the first example given by Apfelmus on his post, disguised as a stack machine.

The operational approach to monads begins with recognizing what operations you want your monad to perform. A State Monad have a state, a return value and two function: one that allows us to retrieve the state as the return value, and one that allows us to insert a new state. Let’s represent this in the following GADT:

> data StateOp st retVal where
>     Get :: StateOp st st  -- retrieve current state as a returned value
>     Put :: st -> StateOp st ()  -- insert a new state

This are the operations needed on the State Monad, but the monad itself is a sequence of compositions of such operations:

> type State st retVal = Program (StateOp st) retVal

Note that the type synonim State st is a monad already and satisfy all the monad laws by construction. We don’t need to worry about implementing return and (>>=) correctly: they are already defined.

So far, so good but… how do we use this monad in practice? This types define a kind of Domain Specific Language: we have operations represented by Get and Put and we can compose them in little programs by using Then and Return. Now we need to write an interpreter for this language. I find this is greatly simplified if you notice that the construct

do x <- singleton foo
   bar x

can be translated as foo `Then` bar in this context. Thus, to define how you’ll interpret the later, just think what’s the effect you want to have when you write the former.

Our interpreter will take a State st retVal and a state st as input and return a pair: the next state and the returned value (st, retVal):

> interpret :: State st retVal -> st -> (st, retVal)

First of all, how should we interpret the program Return val ? This program just takes any state input and return it unaltered, with val as it’s returned value:

> interpret (Return val) st = (st, val)

The next step is to interpret the program foo `Then` bar. Looking at the type of things always helps: Then, in this context, have type StateOp st a -> (a -> State st b) -> State st b. So, in the expression foo `Then` bar, foo is of type StateOp st a, that is, it’s a stateful computation with state of type st and returned value of type a. The rest of the expression, bar, is of type a -> State st b, that is, it expects to receive something of the type of the returned value of foo and return the next computation to be executed. We have two options for foo: Get and Put x.

When executing Get `Then` bar, we want this program to return the current state as the returned value. But we also want it to call the execution of bar val, the rest of the code. And if val is the value returned by the last computation, Get, it must be the current state:

> interpret (Get `Then` bar) st = interpret (bar st) st

The program Put x `Then` bar is suposed to just insert x as the new state and call bar val. But if you look at the type of Put x, it’s returned value is empty: (). So we must call bar (). The current state is then discarded and substituted by x.

> interpret (Put x `Then` bar) _  = interpret (bar ()) x

We have our interpreter (which, you guessed right, is just the function runState from Control.Monad.State) and now it’s time to write programs in this language. Let’s then define some helper functions:

> get :: State st st
> get = singleton Get

> put :: st -> State st ()
> put = singleton . Put

and write some code to be interpreted:

> example :: Num a => State a a
> example = do x <- get
>              put (x + 1)
>              return x
>
> test1 = interpret example 0
> test2 = interpret (replicateM 10 example) 0

This can be runned in ghci to give exactly what you would expect from the state monad:

*Main> test1
(1,0)

*Main> test2
(10,[0,1,2,3,4,5,6,7,8,9])

The approach seems very convenient from the point of view of developing applications, as it’s focused on what are actions the code must implement and how the code should be executed. But it seems to me that the focus on the operations the monad will implement is also very convenient to think about mathematical structures. To give an example, I’d like to implement a monad for Vector Spaces, in the spirit of Dan Piponi (Sigfpe)’s ideas here, here and here.

A vector space is a set of elements that can be summed ( if ) and multiplied elements of a field ( if and ). If we want this to be implemented as a monad then, we should, in analogy with what we did for the State Monad, write a GADT with data constructors that implement the sum and product by a scalar:

> data VectorOp field label where

>     Sum :: Vector field label
>         -> Vector field label
>         -> VectorOp field label

>     Mul :: field
>         -> Vector field label
>         -> VectorOp field label

> type Vector field label = Program (VectorOp field) label

and then we must implement a interpreter:

> runVector :: (Num field, Ord label) => Vector field label 
>                                     -> Map label field
> runVector (Return a) = fromList [(a, 1)]
> runVector (Sum u v `Then` foo) = let uVec = (runVector (u >>= foo))
>                                      vVec = (runVector (v >>= foo))
>                                  in unionWith (+) uVec vVec
> runVector (Mul x u `Then` foo) = fmap (x*) (runVector (u >>= foo))

The interpreter runVector takes a vector and returns it’s representation as a Map. As an example, we could do the following:

> infixr 3 <*>
> infixr 2 <+> 

> u <+> v = singleton $ Sum u v
> x <*> u = singleton $ Mul x u 

> data Base = X | Y | Z deriving(Ord, Eq, Show)

> x, y, z :: Vector Double Base
> x = return X
> y = return Y
> z = return Z

> reflectXY :: Vector Double Base -> Vector Double Base
> reflectXY vecU = do cp <- vecU
>                     return (transf cp)
>                         where transf X = Y
>                               transf Y = X
>                               transf Z = Z

and test this on ghci:

*Main> runVector $ x <+> y
fromList [(X,1.0),(Y,1.0)]

*Main> runVector $ reflectXY $ x <+> z
fromList [(Y,1.0),(Z,1.0)]

As Dan Piponi points out in his talk, any function acting on the base f :: Base -> Base is lifted to a linear map on the vector space Space field Base by doing:

> linearTrans f u = do vec <- u
>                      return (f vec)

More on this later.

HTML generated by org-mode 6.34c in emacs 23

Stochastic processes as monad transformers

I have a difficulty to understand functional programming concepts that I can’t put to some very simple and natural use (natural for me, of course). I need to find the perfect simple example to implement to finally understand something. And I’m not a computer scientist, so things like parsers and compilers have very little appeal to me (probably because I don’t understand them…). I’m a physicist, so this drives me to look for physical problems that can be implemented in Haskell so I can understand some concepts.

Monad transformers still eludes me. But I think I finally got the perfect subject were I can understand them: stochastic processes! First some book keeping:

> import Control.Monad.State
> import Control.Monad
> import Contro.Monad.Rand

Now, stochastic processes have characteristics related to two different monads. In one hand, they are dynamical processes, and the way to implement dynamics in Haskell is with state monads. For example, if I want to iterate the logistic map:

I could do the following:

> f :: Double -> Double
> f x = 4*x*(1-x) 

> logistic :: State Double Double
> logistic = do x0 <- get
>		let x1 = f x
>		put x1
>		return x1
> runLogistic :: State Double [Double]
> runLogistic n x0= evalState (replicateM n logistic) x0

Running this on ghci would give you, for example:

*Main> runLogistic 5 0.2
[0.6400000000000001,0.9215999999999999,0.28901376000000045,
0.8219392261226504,0.5854205387341]

So we can make the loose correspondence: dynamical system  ↔  state monad.

On the other hand, stochastic processes are compositions of random variables, and this is done with the Rand monad (found inControl.Monad.Random). As an example, the Box-Muller formula tells us that, if I have two inpendent random variables x and y, distributed uniformly between in the [0, 1] interval, then, the expression:

will be normally distributed. We can write then (there’s a catch here: x and y are not independent, but sampled from the same pseudo-random number generator, with the same seed… this can be solved, but it would only complicate the example):

> boxmuller :: Double -> Double -> Double
> boxmuller x y = sqrt(-2*log x)*cos(2*pi*y) 

> normal :: Rand StdGen Double
>  normal = do  x <- getRandom
>		y <- getRandom
>		return $ boxmuller x y
> normals n = replicateM n normal
> gen = mkStdGen 0

Running this function we get what we need:

*Main> (evalRand $ normals 5) gen =
[0.1600255836730147,0.1575360140445035,-1.595627933129274,
-0.18196791439834512,-1.082222285056746]

So what is a stochastic process? In very rough terms: is a dynamical system with random variables. So we need a way to make the Rand monad to talk nicely with the State monad. The way to do this is to use a monad transformer, in this case, the StateT transformer. Monad transformers allows you to combine the functionalities of two different monads. In the case of the StateT monads, they allow you to add a state to any other monad you want. In our case, we want to wrap the Rand monad inside a StateT transformer and work with things of type:

foo ::  StateT s (Rand StdGen) r

This type represent a monad that can store a state with type s, like the state monad, and can generate random variables of type r, like the rand monad. In general we would have a type

foo2 ::(MonadTrans t, Monad m) => t m a

In this case, t = StateT s and m = Rand StdGen. The class MonadTrans is defined in Control.Monad.Trans, and provides the function:

lift :: (MonadTrans t, Monad m) => m a -> t m a

In this case, t is itself a monad, and can be treated like one through the code. It works like this: inside a do expression you can use the lift function to access the inner monad. Things called with lift will operate in the inner monad. Things called without lift will operate in the outer monad.

So, suppose we want to simulate this very simple process:

where ηt is drawn from a normal distribution. We would do:

> randomWalk :: StateT Double (Rand StdGen) Double
> randomWalk = do eta <- lift normal
>                 x <- get
>                 let x' = x + eta
>                 put x'
>                 return x'
> runWalk :: Int -> Double -> StdGen -> [Double]
> runWalk n x0 gen = evalRand (replicateM n $ evalStateT randomWalk x0) gen

The evalStateT function is just evalState adapted to run a StateT monad. Running this on ghci we get:

 *Main> runWalk 5 0.0 gen
[0.1600255836730147,0.1575360140445035,-1.595627933129274,
-0.18196791439834512,-1.082222285056746]

This is what we can accomplish: we can easily operate simultaneously with functions that expect a state monad, like put and get, we can unwrap things with <- from the inner Rand monad by using lift , and we can return things to the state monad. We could have any monad inside theStateT transformer. For example, we could have another State monad. Here is a fancy implementation of the Fibonacci sequence using a State monad (that stores the last but one value in the sequence as its internal state) inside a StateT transfomer (that stores the last value of the sequence):

> fancyFib :: StateT Int (State Int) Int
> fancyFib = do old <- lift get
>               new <- get
>               let new' = new + old
>                   old' = new
>               lift $ put old'
>               put new'
>               return new             

> fancyFibs :: Int -> StateT Int (State Int) [Int]
> fancyFibs n = replicateM n fancyFibs

And we can run this to get:

*Main> evalState (evalStateT (fancyFibs 10) 1) 0
[1,1,2,3,5,8,13,21,34,55]

Final note: I expect this post to be usable as a literate haskell script. If you can’t run it, please let me know.

Hello world

I missed a place where I could write things in English about my recent adventures in physics, economics, biology, functional programming and all the random things I like to study. I write in another blogs (this one and this one)  in Portuguese, but this kinds of limits my audience, specially when I wanna talk about stuff I made in Haskell.

So, this is it… this is another one of my narcissistic blogs.