Tutorial: an interpreter for the OCaml AST

In the AST tutorial you built an algebraic data type for a tiny subset of OCaml: integer and boolean literals, addition, variables, and let ... in. We constructed example trees but never walked them. This lecture closes the loop. We will write three walkers over the same AST: a pretty printer, a depth function, and the centrepiece, an interpreter that evaluates an expression to a value. The interpreter is the natural home for almost everything we have seen in Module 5, from basic patterns to or-patterns to exhaustiveness.

We will extend the OCaml AST with one new constructor, If, so that the existing Bool constructor has somewhere to flow. Everything else stays as it was. The interpreter uses nothing beyond the language features introduced in Modules 1 through 5: pattern matching, recursion, option, lists. No higher-order functions, no exceptions, no modules.

The type, extended with If

The OCaml AST's final form from the previous tutorial, with If (cond, then, else) added so that Bool actually does something. The annotation on Let_in is ty option to preserve the make-illegal-states-unrepresentable choice from the AST tutorial: programs either supplied a type or did not.

Six constructors. Three of them carry payloads with sub- expressions (Add, If, Let_in), so they are recursive. The other three (Int, Bool, Var) are leaves at the AST level: they carry data but no sub-expressions. Every walker will have one clause per constructor, three of which recurse.

A small example program to test our walkers on. In OCaml syntax:

let x : int = 10 in
if true then x + 5 else 0

The same in our AST:

Every constructor of expr appears at least once. The program should pretty-print back to something resembling the source, have a small finite depth, and evaluate to 15.

let x : int = 10 in
if true then x + 5 else 0

Function 1: pretty

A pretty printer turns an expr back into a string. We will parenthesise every internal node so we never have to worry about operator precedence. Two clauses are interesting: If prints all three sub-expressions; Let_in has to decide whether to emit the optional type annotation.

The Let_in clause uses an inner match on the ty option: present or absent, decided once, plugged back into the surrounding string. This is the pattern-inside-a-constructor shape, used here at the sub-result level rather than at the outer pattern.

Function 2: depth

depth returns the height of the AST. The three leaf constructors all return 1; we can fold them into a single clause with an or-pattern, since they share the same right-hand side.

The or-pattern Int _ | Bool _ | Var _ collapses three clauses into one. The depth of example is 4: Let_in at the top, If underneath, Add underneath that, Var (or Int) at the bottom.

Function 3: eval

eval is the heart of the tutorial. Given an expression and an environment mapping variable names to values, return the value the expression reduces to.

A value is either an integer or a boolean. We model this with a new variant; we cannot reuse OCaml's own int or bool directly, because the same eval has to return both kinds of result depending on the expression. An environment is a list of (name, value) pairs:

eval can fail. If we ask for Add (Bool true, Int 1) the expression is type-incorrect and we have no answer. We have not covered exceptions yet (Module 7), so we return value option: Some v on success, None on any runtime mismatch. That matches the make-illegal-states-unrepresentable slogan from Module 4: the type forces the caller to handle the failure.

We also need to look up a variable in the environment. A plain recursive function over the list; returns None if the name is absent:

Now eval itself. One clause per constructor of expr. The recursive cases use nested matches on the sub-results to propagate None and to enforce the expected value shape (an Add needs two VInts, an If needs a VBool condition).

Reading the clauses:

• Int n and Bool b are leaves; they evaluate to themselves.
• Add evaluates both sub-expressions, then requires both to be VInt. The nested pattern Some (VInt a), Some (VInt b) binds the two integers and rebuilds a VInt. Anything else (a None, a VBool) collapses to None.
• If evaluates the condition, requires it to be VBool, and picks the branch. The runtime annotation ty option is ignored: it would matter to a type checker, not to the interpreter.
• Var delegates to lookup.
• Let_in evaluates the bound expression, extends the environment, and evaluates the body. The type annotation is again ignored at runtime.

eval [] example returns Some (VInt 15).

let rec eval (env : env) e =
  match e with
  | Int n  -> Some (VInt n)
  | Bool b -> Some (VBool b)
  | Add (e1, e2) ->
    (match eval env e1, eval env e2 with
     | Some (VInt a), Some (VInt b) -> Some (VInt (a + b))
     | _ -> None)
  | ...

  | If (c, t, f) ->
    (match eval env c with
     | Some (VBool true)  -> eval env t
     | Some (VBool false) -> eval env f
     | _ -> None)
  | Var x -> lookup x env
  | Let_in (x, _, e1, e2) ->
    (match eval env e1 with
     | Some v -> eval ((x, v) :: env) e2
     | None   -> None)

More examples

With eval defined, we can run it on a few small expressions. For each one we show the pretty output (so you can read the program as surface syntax) and the eval result.

Let_in extends the environment with ("x", VInt 10) :: [], then evaluates the body under that env. Var "x" finds it via lookup.

The condition Bool true evaluates to VBool true, so the then-branch wins; the else-branch is never touched.

When eval returns None

The interpreter is total in the sense that it never raises an exception, but it does report failure with None. There are two ways for an expr to fail at runtime: a value of the wrong kind in an operator position, and a Var whose name is unbound in the current environment.

Add expects two VInt payloads, and the first sub-expression evaluates to a VBool. The nested match inside the Add clause falls through to _ -> None.

lookup "y" [] walks the empty environment and returns None, which propagates to the top.

The condition is an integer, not a boolean. The nested match inside the If clause falls through to _ -> None.

Two looming questions

There are two things to be uncomfortable about with this interpreter, and both have proper answers in Module 8.

Why so much None-bookkeeping? Look at every recursive clause: Add, If, Let_in. Each one does the same dance: evaluate a sub-expression, pattern-match on the Some _ / None result, propagate None if it appears. The clauses are near-copies of each other with different right-hand sides. This boilerplate is exactly what the option monad captures, with a let* operator that compresses each nested match to one line. We take this same interpreter and rewrite it with let* in the option-monad lecture. The shape stays the same; the noise disappears.

Why can eval fail at all? Look at bad1: Add (Bool true, Int 1) is a well-typed OCaml value of type expr, but it represents a program that makes no sense. The OCaml type system cannot see this, because our expr lumps integer expressions and boolean expressions together. GADTs, in the GADT lectures, let you index expr by what it produces (int vs bool). With that indexing, the type system rules out Add (Bool true, _) at compile time, and the option return type disappears entirely.

For Module 5, we accept the boilerplate and the runtime failure as a fact of life. Both get repaired by the end of Module 8.

The meta-pattern

Three different walkers, one shared skeleton. Each function has exactly one clause per constructor. The base cases are the leaves; the recursive cases recurse on the sub-expressions and combine the results.

let rec f e =
  match e with
  | Int _ -> <leaf answer>
  | Bool _ -> <leaf answer>
  | Add (e1, e2) -> <combine f e1 and f e2>
  | If (c, t, f') -> <combine f c, f t, f f'>
  | Var _ -> <leaf answer>
  | Let_in (_, _, e1, e2) -> <combine f e1 and f e2>

The type definition gives the template; you fill in the actions. The compiler will complain if you skip a constructor. After Module 5 this should be muscle memory: "I have a recursive ADT; my function has one clause per constructor; I recurse on the sub-expressions and combine."

Two checks

The code task extends the interpreter. It leans on the supporting definitions from the eval walkthrough, which are still in scope; for reference:

type value = VInt of int | VBool of bool
type env   = (string * value) list

val lookup : string -> env -> value option   (* None if unbound *)

Activity

The point of the activity is to see the refactoring-with-the-compiler loop end to end. Add two constructors. Build. Read the warnings. Update each match site.

Run the build before reading on. The compiler should report three sites that need attention.

(* depth: extend the binary or-pattern *)
| Add (e1, e2) | Sub (e1, e2) | Mul (e1, e2) ->
    1 + max (depth e1) (depth e2)

(* eval: one clause per new operator *)
| Sub (e1, e2) ->
  (match eval env e1, eval env e2 with
   | Some (VInt a), Some (VInt b) -> Some (VInt (a - b))
   | _ -> None)
| Mul (e1, e2) ->
  (match eval env e1, eval env e2 with
   | Some (VInt a), Some (VInt b) -> Some (VInt (a * b))
   | _ -> None)

What's next

This tutorial closes Module 5. You have seen pattern matching on flat values (Lecture 1), on recursive structures (Lecture 2), inside other patterns (records, inline records, the diagonal idiom, or-patterns) (Lecture 3), constrained by guards (Lecture 4), and under the exhaustiveness checker (Lecture 5). The interpreter above brings all of those together on a single recursive ADT.

Common pitfalls of interpreters

A handful of mistakes catch almost everyone the first time they write an interpreter.

Reading

• Cornell CS3110, Walking an AST: https://cs3110.github.io/textbook/chapters/data/pattern_matching.html
• Real World OCaml, Lists and patterns (the trees and walkers section): https://dev.realworldocaml.org/lists-and-patterns.html
• John Whitington, OCaml from the Very Beginning, Chapter 8 (data types and pattern matching).

Sources

The AST in this lecture is the one we built in the AST tutorial, extended with a single If constructor. The interpreter, its environment representation, and the worked walkers (pretty, depth, eval) are original to this course. The "refactoring with the compiler" idea is folklore in the OCaml/SML community and is also discussed in Cornell CS3110, chapter on pattern matching.