Refactoring Using Monads

The previous section probably made both Java and Haskell programmers cry out in horror. We have to pass state explicitly?! Well, yes and no. The fact that we have to formalize exactly what state our program will need is a good thing - it lets us minimize dependencies and maximize encapsulation which results in more robust programs. The real problem is accepting and returning the state in every function that needs it. This results in a lot of boilerplate code that we have to waste time writing and maintaining.

Fortunately Haskell lets us avoid these issues with monads. I will not go into a detailed description of monads here as they are beyond the scope of this article - your favorite search engine should bring up plenty of monad tutorials. The idea, however, is rather simple - monads use Haskell type system in innovative ways to let us abstract the boilerplate code away. For example, the State monad deals with passing the state for us so we can focus our efforts on solving problems.

We can use the State monad in our interpreter to clean up the code written in the previous section. The first thing we'll do is clean up our declarations that pass state explicitly:

data Expr = BlaiseInt Integer |
        BlaiseSymbol String |
        BlaiseFn ([Expr]->BlaiseResult) |
        BlaiseSpecial ([Expr]->BlaiseResult) |
        BlaiseList [Expr]

eval :: Expr -> BlaiseResult

We define BlaiseResult in terms of StateT monad which allows us to do composition with IO:

type BlaiseResult = StateT Context IO Expr

We can now rewrite our code to take advantage of the monad and avoid passing the state explicitly. Effectively StateT monad abstracts this away from us - we only have to write code to modify the state. The code that passes it around is written once when the monad is implemented (StateT comes standard with Haskell).

blaiseSet [(BlaiseSymbol s), e] =
        do eval_e <- eval e
           modify (\sym_table->Map.insert s eval_e sym_table)
           return eval_e

eval (BlaiseInt n) = return (BlaiseInt n)
eval (BlaiseList (x:xs)) = do fn <- eval x
                              apply fn
    where apply (BlaiseSpecial f) = f xs
          apply (BlaiseFn f) = do args <- mapM eval xs
                                  f args

A common misconception among Haskell beginners is that monads are an unfortunate evil necessary in a a lazy, side-effect free language. While it is true that monads solve the lazy IO problem, it is only one example of their power. As I plunged deeper and deeper into Haskell I began to realize that monads are a desirable feature that allows the programmer to build otherwise impossible abstractions. Monads, together with higher order functions, provide excellent facilities for abstracting away boilerplate code. In this sense Haskell's monads serve a similar purpose to Lisp's macros (though the concept is entirely different). Languages like Java include a more verbose alternative to higher order functions in the form of classes but completely lack alternatives to Monads and macros. Many language features (including exceptions and continuations, for example) can be implemented via Monads or macros. Languages that lack these features leave us completely at the mercy of compiler writers - there's no way we're going to get continuations in Java until Sun decides this feature should make it into the language.