Variables

At this point our interpreter boils down to a simple calculator. We can evaluate mathematical expressions like this:

(+ 1 2)
(+ 1 (+ 2 3))
(* 5 (+ 3 4))

While this is a calculator with the spirit of Lisp, it can hardly be called an interpreter for a programming language. The next natural step in building our interpreter is to introduce variables. Given the fact that Haskell doesn't allow mutable data and that our design is currently limited to four elements (integers, symbols, functions and lists), we're going to run into some problems.

The first problem is obvious: how are we going to implement mutable data in Haskell if it provides no support for it? We can't simply declare a global map of symbols that we can update - all Haskell "variables" can only be written to once. In order to solve this problem we're going to have to modify our design: the eval function will need to explicitly take the current state of the interpreter (a map of symbols) and return the update state along with the evaluated expression. Additionally we'll have to modify our Expr type because functions may end up modifying the symbol table. The resulting code looks like this:

type Context = Map.Map String Expr

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

eval :: Context -> Expr -> (Context, Expr)
eval ctx (BlaiseInt n) = (ctx, BlaiseInt n)

Our interpreter can now handle state! However, we still can't implement an assignment operator because of a more subtle problem. Consider the following expression:

(set i 5)

If we try to implement set as a function our interpreter will crash! The reason is rather simple - our code evaluates all arguments to functions as they are passed in. In the above example our interpreter will attempt to evaluate the symbol i and because it doesn't exist it will result in an error. Clearly functions aren't proper abstractions to implement such operators. We need to modify our Expr type again to introduce special kinds of functions that evaluate their arguments themselves. This way our implementation of set may choose to evaluate only the second argument and leave first as is. Lisp normally calls such functions special forms and we can easily define them like this:

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

The last thing we need to do before we can implement assignments is change our eval function to treat simple functions and special forms differently. We can easily achieve this with pattern matching like this:

eval ctx (BlaiseList (x:xs)) =
        let (new_ctx, fn) = (eval ctx x)
            (last_ctx, eval_args) = mapAccumL eval new_ctx xs
            apply (BlaiseFn f) = f last_ctx eval_args
            apply (BlaiseSpecial f) = f new_ctx xs
        in apply fn

We can now implement the actual assignment operator. It turns out to only take up three lines of code.

blaiseSet ctx [(BlaiseSymbol s), e] =
        (Map.insert s eval_e new_ctx, eval_e)
            where (new_ctx, eval_e) = eval ctx e

That's it! We now assign values to variables and use them in our expressions:

(set i 5)
(+ i 1)
(set j (+ i 5))
(set j (+ j 1))

While the changes take a rather long time to describe, the actual code modifications are minimal. You can see how well a Haskell program adapts to changing requirements - there are no classes to refactor, fewer dependencies to track down, and most importantly, no implicit state to worry about. The type system is expressive enough to warn us at compile time about most types of errors we may introduce with our changes. We also don't have to worry about breaking the order in which things are called or the possibility that we broke state other components expect - all state management is explicitly managed by us and type checked by Haskell. In the next two sections we'll see two more examples of Haskell's ability to easily adapt to changes.