4. Interpreter

An interpreter is a program that executes the source code directly, without turning it into machine code first.

An interpreter is not a mandatory part of the course project, and indeed compilers don’t usually come with interpreters. That said, unless you’ve found everything so far easy and feel very comfortable with recursion, it’s not recommended to skip this chapter, because the same techniques will be applied to more difficult problems in the next two chapters.

For most languages, it’s easiest to write an interpreter that operates recursively on an AST. Production-quality interpreters like Python’s tend to first translate the AST to a flat sequence of commands, sometimes called ”bytecode”, and interpret that, because that’s more efficient.

We’ll write an AST-based interpreter, because it’s more valuable to practice recursing over the AST at this stage, and because it’s more fun to get your project to run programs sooner rather than later.

Recursion over an AST

Let’s look at the AST for the following expression

if x < 10 then print_int(x + 7) else print_int(0)

The AST has the following types of nodes:

• Constant literals: 10, 7 and 0.
• Variables: x and print_int
• Operators: < and +
• Function calls: name(arguments)
• An if-then-else expression

We need to define how to compute the result for each of these.

• Constants are super easy: just return the constant value.
• Variables need to look up the value from somewhere - we’ll get back this.
• Operators and function calls need to recursively evaluate their arguments and then apply the operator or function on the results.
• If-then-else expressions need to recursively evaluate the condition and then decide which branch to recursively evaluate.

The code for a very simple interpreter, without support for variables and with very poor error checking, might look something like this:

# src/compiler/interpreter.py
from typing import Any
from compiler import ast

type Value = int | bool | None

def interpret(node: ast.Expr) -> Value:
    match node:
        case ast.Literal():
            return node.value

        case ast.BinaryOp():
            a: Any = interpret(node.left)
            b: Any = interpret(node.right)
            if node.op == '+':
                return a + b
            elif node.op == '<':
                return a < b
            else:
                raise ...

        case ast.IfThenElse():
            if interpret(node.condition):
                return interpret(node.then_branch)
            else:
                return interpret(node.else_branch)
        ...

You are now ready to do task 1.

Symbol tables

An interpreter needs some place to look up the values for variables. Such a place is usually called a symbol table. A symbol table is almost always needed when recursing over the AST – the next two chapters (type checker and IR generator) will use one too.

Our first thought might be that a symbol table is just a dictionary that maps variable names to values, but that is not enough.

Consider nested blocks that may define new variables. These variables must only be visible inside that block, i.e. the block defines a scope. Variables defined in a scope may hide i.e. shadow variables of the same name in outer scopes.

Example:

{
    var x = 1;
    {  # <----------- Inner scope begins
        var x = 2;  # Shadows the 'x' in the outer scope
        var y = 3;
        print_int(x);   # Prints 2
        print_int(y);   # Prints 3
    }  # <----------- Inner scope ends
    print_int(x);  # Prints 1
    print_int(y);  # Error: 'y' does not exist in this outer scope
}

We could just ban shadowing (e.g. C# does so, mostly), but shadowing is sometimes useful (e.g. Rust even encourages it).

We’ll definitely want to support shadowing later when we add functions to the language. We at least want to be able to add a global variable even if some function happens to use the same variable name internally.

The solution is a hierarchical symbol table. It contains two things:

• locals: a dictionary of variable names to values – contains variables defined in the current scope,
• parent: an optional reference to the outer scope’s symbol table – we consult this recursively when a variable is not found in locals.

In the example above, at the first print_int(x), the hierarchical symbol table would look like this:

The top-level symbol table is where global things like our built-in functions and operators are defined. We’ll put them there in task 3.

Tasks

Task 1

Task 2

Task 3

Task 4

var evaluated_right_hand_side = false;
true or { evaluated_right_hand_side = true; true };
evaluated_right_hand_side  # Should be false

Task 5