Writing an Interpreter in Haskell

In an effort to learn Haskell, I built a Scheme interpreter over the course of a few weekends. Coming from an imperative programming background (mainly Python and C++), and being used to writing code with mutable state, it was refreshing to work in a purely functional language on a project that pushed me to think differently.

My toy interpreter successfully running basic Scheme programs.

Algebraic Data Types (ADTs)

Haskell’s algebraic data types are incredibly powerful and expressive. They allow you to model the structure of your program in a way that feels both concise and intuitive. For example, I used an ADT to represent the various types of expressions in my Scheme interpreter.

data Expr
    = Number Int
    | Symbol String
    | List [Expr]
    | Lambda [String] Expr
    | Builtin (Env -> [Expr] -> Either String Expr)

This allowed me to define the core building blocks of Scheme expressions in a single, elegant type. In Python, I might have achieved something similar with classes and inheritance, but it would likely have been bulkier and less clear.

`case` Expressions

Haskell’s case expressions make pattern matching a joy to use, especially when combined with ADTs. For instance, here’s a snippet from my interpreter’s evaluation function:

eval :: Env -> Expr -> Either String Expr
eval env expr = case expr of
    Number n -> Right $ Number n
    Symbol s -> maybe (Left $ "Unbound symbol: " ++ s) Right (lookup s env)
    List (Symbol "define" : Symbol var : val : _) -> do
        evaluatedVal <- eval env val
        Right $ extendEnv var evaluatedVal env
    List (Symbol "lambda" : List params : body : _) ->
        Right $ Lambda (map toSymbol params) body
    List (Symbol func : args) -> do
        function <- eval env (Symbol func)
        apply function env args
    _ -> Left "Unknown expression"

case expressions let me handle each variant of Expr in a way that feels natural and readable. Compared to Python’s if-elif chains or C++’s switch statements, the clarity and conciseness of Haskell’s pattern matching are unparalleled.

Immutability and Recursion

One of the most striking differences between Haskell and the languages I’m used to is the immutability of variables. In Haskell, once a value is assigned to a variable, it cannot be changed. This forced me to embrace recursion for tasks that would normally involve loops with mutable state, such as interpreting a list of expressions.

apply :: Expr -> Env -> [Expr] -> Either String Expr
apply (Builtin func) env args = func env args
apply (Lambda params body) env args = do
    let extendedEnv = foldl extendEnv env (zip params args)
    eval extendedEnv body
apply _ _ _ = Left "Invalid function application"

Here, the use of recursion to evaluate function arguments and extend the environment felt both natural and elegant. While recursion can sometimes feel verbose in Python or C++, in Haskell it often feels like the most natural solution.

Lazy Evaluation

Haskell’s lazy evaluation was another game-changer. It allows you to work with infinite structures effortlessly. For instance, I implemented a feature in my interpreter to support infinite lists using lazy evaluation.

infiniteOnes :: Expr
infiniteOnes = List $ repeat $ Number 1

This infiniteOnes expression creates an infinitely long list of 1s, but it doesn’t evaluate until explicitly needed. In Python or C++, I’d need to carefully manage lazy evaluation using iterators or generators, but in Haskell, it’s built into the language.

Higher-Order Functions

Haskell’s first-class support for higher-order functions made implementing language features like map and fold a breeze. For example, here’s how I implemented the map function in Scheme:

builtinMap :: Env -> [Expr] -> Either String Expr
builtinMap env [Lambda params body, List elems] = do
    mapped <- mapM (\e -> eval env (List [Lambda params body, e])) elems
    Right $ List mapped
builtinMap _ _ = Left "Invalid arguments to map"

The ability to pass functions as arguments and return them as values is core to Haskell, and it made implementing features like this feel seamless.

Inline Tests

Haskell makes it easy to write tests directly in the same file as your code, thanks to its lightweight testing libraries. Here’s a simple test for my eval function:

testEval :: IO ()
testEval = do
    let env = [("x", Number 42)]
    let expr = Symbol "x"
    print $ eval env expr == Right (Number 42)

Having tests right next to the functions they validate helped me stay focused and iterate quickly. This felt much smoother than the separate test files and frameworks I’ve used in Python or the complex build systems needed for testing in C++.

Conciseness

Overall, I found Haskell to be incredibly concise. My Scheme interpreter is only ~1,500 lines of code, yet it supports most of the core features of the language. If I had written this in Python or C++, it would have likely been at least double the size. Yet, despite its brevity, the code remains expressive and easy to follow.

type Env = [(String, Expr)]

extendEnv :: String -> Expr -> Env -> Env
extendEnv key value env = (key, value) : env

lookupEnv :: String -> Env -> Maybe Expr
lookupEnv key [] = Nothing
lookupEnv key ((k, v) : rest)
    | key == k  = Just v
    | otherwise = lookupEnv key rest

This code is straightforward and clear, thanks to Haskell’s pattern matching and type system. In Python, the same logic would likely involve more boilerplate, and in C++, it would be significantly more verbose.

Cabal and Stack

Haskell’s ecosystem includes tools like Cabal and Stack for managing dependencies and building projects. Having a standard way to specify dependencies and manage builds felt fantastic compared to the fragmented ecosystems of Python (pip vs conda vs virtualenv) or C++ (CMake vs Makefiles vs custom build scripts).

dependencies:
  - base >= 4.7 && < 5
  - containers
  - text

Being able to specify dependencies so cleanly made project setup and maintenance a breeze.

Conclusion

Overall, I thoroughly enjoyed building my Scheme interpreter in Haskell. The language’s focus on immutability, conciseness, and functional programming principles challenged me to think differently and write better code. While I don’t use Haskell in my day-to-day work, this project has inspired me to incorporate more functional programming ideas into my other projects.

Clara Xiao