CMSC-16100

Honors Introduction to Programming, I

Autumn Quarter, 2015

Home Policies Lectures Notes Labs

---

Piazza

Lecture 16: The State Monad, I

The State type enables us to build computations that manipulate (hidden) state. I think of this as “elephant in the room” programming, wherein we have a central, ubiquitous data structure that is so important that we can actually clarify our code by hiding it. The State type is defined as:

newtype State s a = State { runState :: s -> (a,s) }

The intuition here is that s is the type of the “state” of the computation, a value of which may be used and altered over the course of a sub-computation that produces a value of type a. This is realized through a function that takes a state value as an argument, and which returns a pair consisting of a value of the advertised return type a, together with the updated state. I find it helpful to think of this diagrammatically:

This type is very different from the monadic types we've seen before, in that the monomorphic algebraic constructor wraps a function rather than a simpler value.

Our first order of business is to make State s an instance of Functor:

instance Functor (State s) where fmap f ma = State $ \s -> let (a,t) = runState ma s in (f a,t)

Here, the effect of the fmap f is to wrap up the old state transforming function in a new state transforming function that calls the old state transforming function, capturing and adjusting its return value. This is a harbinger of things to come.

Next up in the type class hierarchy, we make State s an instance of Applicative:

instance Applicative (State s) where pure a = State $ \s -> (a,s) af <*> aa = State $ \s -> let (f,t) = runState af s (a,u) = runState aa t in (f a, u)

This is worth understanding. The pure instance produces a State function that doesn't use or change the state s, it just returns a through the first coordinate of the pair. The (<*>) action takes the input state, and obtains the function f and an updated state t, then passes the updated state t to aa, obtaining the argument a and an updated state u, and finally we package up the application f a and the final state u into a pair. It is important to understand that (<*>) specifies an order in which the state is used: left-hand (function) argument first, then the right-hand argument.

We can envision this process diagrammatically as follows:

Finally (at least, finally in the first-pass sense), we make State s an instance of Monad:

instance Monad (State s) where return = pure ma >>= f = State $ \s -> let (a,t) = runState ma s mb = f a (b,u) = runState mb t in (b,u)

The definition of (>>=) is quite similar to (<*>). As with (<*>), the state will flow through the expression in left-to-right order. In the case of (>>=), the argument ma is performed first, obtaining a result a and an updated state t, then the function f is applied to a, obtaining another monadic action mb, which is performed passing it the state t, obtaining a result b and a final state u, which are packaged into the result pair (b,u) as before.

As usual, return is just a legacy name for pure.

To use State effectively, we provide monadic functions that extract, inject, and modify the state, hence,

get :: State s s get = State $ \s -> (s,s) put :: s -> State s () put t = State $ \s -> ((),t) modify :: (s -> s) -> State s () modify f = State $ \s -> ((),f s)

But now that we have this toy, what do we do with it? In a typical application, we'll consider State s for some application-specific type s, and we'll use get and put to write application-specific state accessors and mutators.

Turning Haskell into a 1980s era calculator

The Hewlett-Packard corporation made a name for itself by producing high-quality electronic scientific (and later, financial) calculators which thoroughly disrupted the pre-existing economy of scientific calculation built on slide rules. A novel feature of the HP calculators was their use of reverse polish notation (RPN), which involved the use of an operand stack, together with operations that acted on that stack. This had the considerable virtue of simplifying input handling, thereby allowing silicon to be devoted to other tasks, and HP calculators were rightly famous for their numerical precision and speed. With an RPN calculator, to add 1 to 2, you'd hit, 1, Enter, 2, and then, finally, +. The more advanced models that started to appear in the 1980's were programmable, in the sense that certain keys could be programmed to execute a sequence of key strokes (possibly involving other programmable keys). With these calculators, the operand stack was arguably the most important abstraction, but paradoxically, it was hidden from view. Our goal is to write code that provides much of the feel of working with these early calculators, and doing so requires that we hide the operand stack.

You can find a javascript simulator of an HP-35 calculator—the very calculator I purchased used for $100.00 in 1976 here.

This particular example will give us the opportunity to focus on the notion of abstraction barriers. These are a software engineering technique whereby we decompose the problem into subproblems, with each sub-solution specifying a well-defined interface that completely determines the ways that other subproblems can interact with it. Haskell's module system provides excellent support for abstraction barriers, as we'll see. Let's start by taking the work that we've just done building the State monad, and encapsulate it in a module called State (in State.hs).

Our next module will be the Calc module (in Calc.hs), in which we'll define (and export) the basic functionality of our calculator. A particular convention of our calculator will be that all of the calculator operations we export will have the form kOperation for some operation.

We'll start by defining the type associated with a simple calculation:

type CalcState = State [Double]

CalcState is intended for internal use, whereas the more restricted

type Calculation = CalcState ()

is intended for exported values.

Next, we define a couple of monadic functions that enable us to push and pop values off of the stack. We can think of these as primitives, built on top of the still more primitive get and put functions:

pop :: CalcState Double pop = do stk <- get case stk of [] -> return 0.0 x:xs -> do put xs return x push :: Double -> CalcState () push d = do stk <- get put (d:stk)

Note how we return 0.0 when we have an empty stack. Intuitively, this is equivalent to viewing the stack as being infinitely deep, and filled to the bottom with 0.0's. Standard code transformations can result in surprising concision:

push = modify . (:)

If we think in a somewhat more concrete way about how the State monad works, we can come up with the following much more succinct definition:

pop = state $ \s -> case s of [] -> (0.0,[]) x:xs -> (x,xs)

At first, this feels a bit like both a typographical error and an abstraction barrier violation, but it's neither, because state is a standard part of the State interface:

state :: (s -> (a,s)) -> State s a state = State

The push operation, which we think of as a stack primitive, is actually something we want to export, albeit under a different name:

kEnter :: Double -> Calculation kEnter = push

Next, we provide the basic arithmetic functions:

binOp :: (Double -> Double -> Double) -> CalcState () binOp op = do y <- pop x <- pop push $ op x y kAdd, kSub, kMul, kDiv :: Calculation kAdd = binOp (+) kSub = binOp (-) kMul = binOp (*) kDiv = binOp (/)

Notice how in binOp that if we've pushed the first operand first, that must mean that we'll pop the second operand first. Notice also the preference within a module for using the private push over the exported kEnter. This is not required, but it does reflect differences in how with think about the problem: outside of the abstraction barrier, we use the exported functionality, inside the abstraction barrier, we have unrestricted access to the functions defined at that level (or exported from a lower level still).

Next, we need a little bit of code to allow us to actually run a Calculation.

perform :: Calculation -> Double perform ma = fst $ runState (ma >> pop) []

This is just a bit obscure. It might seem simpler conceptually to do this:

perform ma = head . snd $ runState ms []

The problem we solve with a final pop is that running ma might result in an empty stack, in which case the call to head would raise an exception. A final pop action takes advantage of the error handling we've built into pop, albeit while delivering the intended result as the value returned by performing the action, rather than as the top of the resulting state. We can simplify this a bit further through use of a couple of convenience functions that are a standard part of the State interface:

evalState :: State s a -> s -> a evalState ma s = fst (runState ma s) execState :: State s a -> s -> s execState ma s = snd (runState ma s)

where evalState throws away the final state, evaluating to the final returned value, whereas execState throws away the final return value (often ()), evaluating to the final stack. With this, we write:

perform :: Calculation -> Double perform ma = evalState (ma >> pop) []

With these, we can begin to write little programs that resemble old-school RPN calculations, e.g., here's how we'd compute (1+2)*3:

test :: Double test = perform $ do kEnter 1 kEnter 2 kAdd kEnter 3 kMul

Now, part of the game in trying to simulate an RPN calculator is to avoid the use of explicit bindings except in the definition of primitives in the Calc module. This is an issue if we want, e.g., to define a hypotenuse macro. The idea here is that hypotenuse should expect two arguments on the stack, and it should pop them off, leaving the hypotenuse of the corresponding right triangle pushed on the stack. To handle this, we introduce a couple of new primitives to Calc:

kSwap :: Calculation kSwap = do y <- pop x <- pop push y push x kDup :: Calculation kDup = do x <- pop push x push x

together with the corresponding updates to Calc's export list. At this point, purists might note that while the HP-35 had a swap key, it didn't have a dup key. That's because the Enter key did the work of both kEnter and kDup, depending on the input state, i.e., it had the effect of kEnter if we'd just typed a number in, and kDup if the last key-stroke was an operation or an Enter.

We're also going to need a square root function. To facilitate this, we'll add a private unOp function:

unOp :: (Double -> Double) -> CalcState () unOp op = do x <- pop push $ op x

and the keystroke function for square root:

kSqrt :: Calculation kSqrt = unOp sqrt

We'll also take this opportunity to add the basic trigonometric functions,

kSin,kCos,kTan :: Calculation kSin = unOp sin kCos = unOp cos kTan = unOp tan

This enables us to define (in the CalcExample module in CalcExample.hs)

square :: Calculation square = do kDup kMul hypotenuse :: Calculation hypotenuse = do square kSwap square kAdd kSqrt

With this in hand, we can compute the hypotenuse of a 3-4-? triangle:

> perform $ kEnter 3 >> kEnter 4 >> hypotenuse 5.0

This is all pretty straightforward, if a bit nerdy, and in my case, maybe even a bit maudlin. That HP-35 died decades ago, but strangely enough I still have the slide rule it replaced. There's probably a lesson in that. Life, and computing, go on.

But let's push this a bit further. HP calculators, in addition to the stack, also contained a memory location as a part of their state. Let's suppose we wanted to implement the store and recall functionality. This presents us with a conundrum. How? The answer is going to take us back to Calc, and a more complicated model of the state that's being manipulated:

data InternalState = InternalState { stack :: [Double] , memory :: Double } type CalcState = State InternalState

This is obviously going to break things, but because of the abstraction barriers we've implemented, the breakage is limited to the Calc module, and indeed, because of an interal abstraction barrier within Calc to just the push, pop and perform functions, as they're the only functions that accessed the state directly:

pop :: CalcState Double pop = state $ \st -> case stack st of [] -> (0.0,st) (x:xs) -> (x,st {stack = xs}) push :: Double -> CalcState () push d = modify $ \st -> st { stack = d : stack st } perform :: Calculation -> Double perform ma = evalState (ma >> pop) startState where startState = InternalState { stack = [], memory = 0.0 }

With this, our existing code works, leaving us only to implement access to the memory part of the internal state.

---

© 2009–2015 Ravi Chugh, Stuart A. Kurtz
Last modified: December 30, 2015