Tag: monad

Quick interpreters with the Reader monad

~ Don Stewart ~ Leave a comment

Rolling your own interpreters in Haskell is one of the joys of using this language, due to the support for:

  • algebraic data types
  • pattern matching on data
  • monadic environments
  • higher order functions

Here’s a quick, complete interpreter for a simple math language of binary operators, with support for variables. It uses the Reader monad for a natural embedding of lexical scoping. Writing interpreters in Haskell is just so easy, no wonder Pugs was written in it.

import qualified Data.Map as M
import Control.Monad.Reader

--
-- A syntax tree type for simple math, with variables
--
data Exp = IntE Int
         | OpE  Op Exp Exp
         | VarE String
         | LetE String Exp Exp

type Op = Int -> Int -> Int

--
-- The interpreter
--
eval (IntE n)       = return n
eval (OpE op e1 e2) = liftM2 op (eval e1) (eval e2)

eval (VarE x)       = do
    env <- ask
    return $ maybe (error "undefined variable") id (M.lookup x env)

eval (LetE x e1 e2) = do
    env <- ask
    v   <- eval e1
    local (M.insert x v) (eval e2)

--
-- Run the interpreter
--
main = print $ runReader (eval test) M.empty

--
-- A simple text expression:
--
--      let x =
--          let y = 5 + 6
--          in y / 5
--      in x * 3
-- 
-- ==>  6
--
test = LetE "x" (LetE "y" (OpE (+) (IntE 5) (IntE 6))
                      (OpE div y (IntE 5)))
                (OpE (*) x (IntE 3))
    where x = VarE "x"
          y = VarE "y"

Let’s run the test program:

$ runhaskell A.hs
6

Adding a front end (with Parsec), and then implementing the rest of Ruby, is left as an exercise for the reader.

The computational view of monads

~ Don Stewart ~ Leave a comment

I originally wrote this article as a comment to the programming subreddit, however I’ve found myself referring to it a few times since then, and reproduce it here for posterity. It attempts to motivate monads for people coming from imperative, stateful languages (already living in IO).

In Haskell, a purely functional language, we use monads to provide a library-based approach to sequential, imperative evaluation: the famous IO monad. No wonder Haskell people talk about it a lot: library-based imperative programming in a purely functional language is fun.

But monads don’t stop there! In languages with builtin sequential evaluation the IO monad must seem boring or silly — no wonder it all seems a puzzle.

This is where it gets interesting. Since monads provide an abstraction over evaluation order, they can be used in other languages (and Haskell) to implement *non*-sequential evaluation order, as a library, also!

So instead of special language support for, say, exceptions and callcc, you just implement monads as a library, and get:

Perhaps this gives a flavour for non-Haskell people for why they’re so useful. Continuations as a library! Non-deterministic evaluation as a library!

So just as its well known that with continuations you can implement threaded control or exceptions as a library, with monads you can implement continuations themselves as a library, along with all the other fun toys. Then, using monad transformers, you can compose separate monads, providing, say, exception handling over a state encapsulation: you can specify precisely what programming language concepts a particular program requires. Here is:

Users of other languages are likely, and rightly so, to be less interested in the solution to IO based on monads, and far far more interested in things like library-based continuations or exceptions (see for example monadic delimited continuations in OCaml).

Hope that gives a hint towards what this monad stuff is all about.