LetItCrash

An interpreter is just an evaluator

LLM-authored, human-reviewed

Algorithms & theory

The parsing article left you holding a tree - {:plus, 3, {:times, 4, 2}} - and stopped. This article picks up there. A tree is not an answer. It is a plan. The last stage of the pipeline turns that plan into a value. That stage has a surprising name - evaluation - and a small implementation. An interpreter is not a big machine with a stack and a heap and a garbage collector. At its core, an interpreter is just an evaluator: a function that walks the tree, evaluates the children, and combines the results. This article is that one function, plus the reason the site’s /lambda section - a pure beta-reducer - is the same function for a smaller language.

The evaluator is one function per node

The parser built the tree with one function per grammar rule. The evaluator builds the value with one clause per node shape. It is shorter than the parser was:

defmodule Eval do
  def value({:plus, l, r}), do: value(l) + value(r)
  def value({:minus, l, r}), do: value(l) - value(r)
  def value({:times, l, r}), do: value(l) * value(r)
  def value({:div, l, r}), do: div(value(l), value(r))
  def value(n) when is_integer(n), do: n
end

IO.inspect(Eval.value({:plus, 3, {:times, 4, 2}}), label: "3 + 4 * 2")
IO.inspect(Eval.value({:times, {:plus, 3, 4}, 2}), label: "(3 + 4) * 2")
IO.inspect(Eval.value({:minus, 10, {:div, 4, 2}}), label: "10 - 4 / 2")

Run it. The trees from the previous article become numbers:

3 + 4 * 2    -> 11
(3 + 4) * 2  -> 14
10 - 4 / 2   -> 8

The whole interpreter is the recursion in value. Each operator clause calls value on its children before it combines them. {:plus, 3, {:times, 4, 2}} evaluates the leaf 3, then evaluates the {:times, 4, 2} subtree. That subtree evaluates its leaves and multiplies them. The outer clause then adds the results. This is a post-order tree walk: children first, parent second. It is the entire evaluation strategy. There is no stack to manage and no state to thread. The call stack is the evaluation order, just as it was the precedence in the parser.

Beta-reduction is the archetype evaluator

Strip away the arithmetic and the same walk remains. A lambda term is a tree, and its evaluator has one rule - beta-reduction, substituting an argument for a parameter. The lambda calculus article calls it “the only rule that makes anything happen.” As an evaluator, that rule is the “combine” step above: when the walk reaches an application (λx. M) N, it evaluates by substituting N for x in M and reducing the result. The site’s /lambda section is an interpreter for the smallest language there is. Its exercises are graded by “a pure-Elixir beta-reducer (never an LLM)”. The whole thing is the same value function: walk the tree, find the redex, apply the one rule, and repeat until a normal form.

The two examples use the same algorithm with different “combine” steps. Arithmetic evaluation combines children with + and *; lambda evaluation combines an abstraction and an argument with substitution. The walk is the same. Only the per-node operation changes. Here is the point: an interpreter is a tree walk plus a choice of what “combine” means, and that choice is the evaluator.

Code as data: the evaluator’s raw material

The tree the evaluator walks is not a special artifact of the parser. It has the same shape as the data the language manipulates. In Elixir, quote turns any expression into its AST as an ordinary data structure:

quote do: 3 + 4 * 2
# => {:+, [context: Elixir, ...], [3, {:*, [context: Elixir, ...], [4, 2]}]}

Compare that with the parser’s tree: {:plus, 3, {:times, 4, 2}}. The structure is the same - a three-element tuple, an operator atom, and a list of operands. The parser names its nodes :plus and :times; Elixir names them :+ and :*. The evaluator does not care which names it sees. It pattern matches on the shape. This is the point Chris McCord makes in Metaprogramming in Elixir: “Having the AST accessible by normal Elixir code lets you do very powerful things because you can operate at the level typically reserved only for compilers and language designers.” An interpreter is ordinary Elixir code operating on ordinary Elixir data. The AST is not a mystery the compiler hides. It is a tuple you can build, match, and walk. The metaprogramming article explains that fact; here, it is why an interpreter is so small.

Interpreter vs compiler: the same walk, a different output

One distinction makes the name honest. An interpreter walks the tree and produces a value at each node. A compiler walks the same tree and produces code at each node. The compilers article states it: the evaluator and the compiler share the tree, and “they differ only in what the walk emits.” Eval.value({:plus, l, r}) returns value(l) + value(r); a compiler’s clause for the same node returns the code add(l_code, r_code). The parser fixes the tree as the language’s meaning. Interpretation and compilation then make two walks over that meaning: one produces a value now, and the other produces code that produces the value later.

That is why “an interpreter is just an evaluator” is a precise claim, not a dismissal. Everything else an interpreter has - environments, scopes, a stack

  • is bookkeeping around the load-bearing fact: there is a function from tree to value, and it is short enough to read whole.

Where to go next

Parsing turned text into a tree; evaluation turns the tree into a value. It does that with a function small enough to hold in your head: walk the tree, evaluate the children, combine at the node. The lambda calculus is that function with the smallest possible “combine,” substitution, and Elixir’s quote shows that the tree was ordinary data all along. An interpreter is not a big machine. It is the smallest program that turns meaning into an answer, and the evaluator is the whole of it.

← Back to articles

Exercises