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
data Exp = IntE Int
| OpE Op Exp Exp
| VarE String
| LetE String Exp Exp
type Op = Int -> Int -> Int
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)
main = print $ runReader (eval test) M.empty
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.

### Like this:

Like Loading...

*Related*

## Published by Don Stewart

Functional programmer, PhD in computer science, and ex-quantitative finance developer. I've built a lot of Haskell stuff, now trying out Rust.
I'm also a software engineer at Facebook. In the past I've held engineering management and software dev roles in finance, tech and applied research.
Views expressed are my own.
View all posts by Don Stewart