Build an Interpreter

In this module, you will build an interpreter for a small language that we invent along the way. We start with simple things like evaluating numbers and arithmetic, and end with a language that has variables, functions, conditionals, and data structures.

We will not build a lexer or parser, which means we need another language to host our language. We will use JavaScript for that.

You may wonder what the point is of building a language inside another one. It is actually a standard technique, used to build Embedded Domain Specific Languages. Here, the goal is not a production language. It is to see the very core of how programming works, with nothing hidden from you.

You’ll write an evaluate function that grows with each problem, adding new rules for how your language works. Each rule is small. Each problem extends what you’ve already built. By the end, you’ve made something that runs real programs, and you understand every line of it.

Here is what programs in your finished language look like:

// Factorial
define(
  "factorial",
  fn("n", iff(eq("n", 0), 1, mul("n", call("factorial", sub("n", 1))))),
);

call("factorial", 5); // 120

None of this is a built-in feature. Variables, functions, closures, recursion, pairs, lists, you build each one yourself. define, fn, iff, eq, mul, sub, call are not part of the evaluator. They are syntactic sugar: tiny JavaScript helpers that produce the same arrays you would otherwise write by hand.

Under the hood, every program is just nested arrays and strings. Here is the same factorial, desugared:

[
  "factorial",
  "=",
  [
    "lambda",
    "n",
    ["if", ["n", "==", 0], 1, ["n", "*", ["factorial", ["n", "-", 1]]]],
  ],
];

The two snippets are the same program. define produces the "=" form, fn produces "lambda", iff produces "if", and eq, mul, sub produce the "==", "*", "-" operators. The sugar is only there to make the arrays readable. Your evaluate function walks this tree and gives it meaning.

---

What you will build

• Evaluating expressions: numbers, arithmetic, nested expressions, and the recursive evaluator that handles them
• Variables and functions: environments, name lookup, lambdas, closures
• Conditionals: booleans, comparison, and branching with if
• Currying: refactoring multi-argument functions into single-argument chains
• Recursion: recursive definitions, scope, and the connection between recursion and environments
• Programs: factorial, fibonacci, sum-to, power, compose, and boolean logic — written in your language
• Syntactic sugar: JavaScript helpers that make the raw arrays readable
• Pairs and lists: data structures built from closures, not from new syntax
• Interpreters: tagged expression trees, and a final twist; writing a small interpreter as a program in the language you built

Each problem builds on the last. You carry your own code forward within a problem. At problem boundaries, you get clean implementations of prior work, so you can focus on the new concept.

---

Acknowledgment

Many ideas in this module, such as, building a language from an evaluator, the progression from arithmetic to closures to recursion, and the distinction between recursive and iterative processes, are inspired by Structure and Interpretation of Computer Programs by Harold Abelson, Gerald Jay Sussman, and Julie Sussman (MIT Press), licensed under CC BY-SA 4.0.