An Interpreter

• Compilers and interpreters are just programs.
• Basic arithmetic operations are just functions that have special notation.
• Programs can be represented as trees, which can be stored as nested lists.
• Interpreters recursively dispatch operations to functions that implement low-level steps.
• Programs store variables in stacked dictionaries called environments.
• One way to evaluate a program’s design is to ask how extensible it is.

Terms defined: compiler, control flow, defensive programming, dictionary comprehension, dynamic dispatch, environment, expression, infix notation, interpreter, introspection, prefix notation, runtime, statement, type hint

Chapter 2 and Chapter 6 introduced the idea that programs are just data. Compilers and interpreters are just programs too. Instead of calculating sums or drawing characters on a screen, compilers turn text into instructions for interpreters or hardware to run.

Most real programming languages have two parts: a parser that translates the source code into a data structure, and a runtime that executes the instructions in that data structure. Chapter 5 explored parsing; this chapter will build a runtime for a very simple interpreter, while Chapter 25 will look at how we can compile code so that it runs more efficiently.

Expressions

Let’s start by building something that can evaluate simple expressions such as 1+2 or abs(-3.5). We represent each expression as a list with the name of the operation as the first item and the values to be operated on as the other items. If we have multiple operations, we use nested lists:

["add", 1, 2]            # 1 + 2
["abs", -3.5]            # abs(-3.5)
["add", ["abs", -5], 9]  # abs(-5) + 9

The function to add two expressions looks like this:

def do_add(args):
    assert len(args) == 2
    left = do(args[0])
    right = do(args[1])
    return left + right

Its single parameter is a list containing the two sub-expressions to be evaluated and added. After checking that this list contains the required number of values, it calls an as-yet-unwritten function do to evaluate those sub-expressions. (We’ve called the function do instead of eval because Python already has a function called eval.) Once do_add has two actual values, it adds them and returns the result.

do_abs implements absolute values the same way. The only differences are that it expects one value instead of two and calculates a different return value:

def do_abs(args):
    assert len(args) == 1
    val = do(args[0])
    return abs(val)

Notice that do_abs and do_add have the same signature. As with the unit testing functions in Chapter 6, this allows us to call them interchangeably.

So how does do work? It starts by checking if its input is an integer. If so, it returns that value right away because integers “evaluate” to themselves. Otherwise, do checks that its parameter is a list and then uses the first value in the list to decide what other function to call.

def do(expr):
    # Integers evaluate to themselves.
    if isinstance(expr, int):
        return expr

    # Lists trigger function calls.
    assert isinstance(expr, list)
    if expr[0] == "abs":
        return do_abs(expr[1:])
    if expr[0] == "add":
        return do_add(expr[1:])
    assert False, f"Unknown operation {expr[0]}"

This lookup-and-call process is called dynamic dispatch, since the program decides who to give work to on the fly. It leads to a situation where do calls a function like do_add, which in turn calls do, which may then call do_add (or something other function) and so on (Figure 7.1). Having a function call itself either directly or indirectly is called recursion, which has a reputation for being hard to understand. As our interpreter shows, though, it’s a natural way to solve a wide range of problems: each recursive step handles a smaller part of the overall problem until we reach an integer or some other value that doesn’t require any further work.

With all of this code in place, the main body of the program can read the file containing the instructions to execute, call do, and print the result:

def main():
    assert len(sys.argv) == 2, "Usage: expr.py filename"
    with open(sys.argv[1], "r") as reader:
        program = json.load(reader)
    result = do(program)
    print(f"=> {result}")

if __name__ == "__main__":
    main()

The program we want to interpret is a list of lists of lists, so we can read it as JSON using json.load rather than writing our own parser. For example, if our program file contains:

["add", ["abs", -3], 2]

then our little interpreter prints:

=> 5

This is a lot of code to do something that Python already does, but it shows what Python (and other languages) do themselves. When we run:

python expr.py expr.tll

Python reads expr.py, turns it into a data structure with operation identifiers and constants, and uses those operation identifiers to decide what functions to call. The functions inside Python are written in C and have been compiled to machine instructions, but the cycle of lookup and call is exactly the same as it is in our little interpreter.

Variables

Doing arithmetic on constants is a start, but our programs will be easier to read if we can define variables that give names to values. We can add variables to our interpreter by passing around a dictionary containing all the variables seen so far. Such a dictionary is sometimes called an environment because it is the setting in which expressions are evaluated; the dictionaries returned by the globals and locals functions introduced in Chapter 6 are both environments.

Let’s modify do_add, do_abs, do, and main to take an environment as an extra parameter and pass it on as needed:

def do_abs(env, args):
    assert len(args) == 1
    val = do(env, args[0])
    return abs(val)

Looking up variables when we need their values is straightforward. We check that we have a variable name and that the name is in the environment, then return the stored value:

def do_get(env, args):
    assert len(args) == 1
    assert isinstance(args[0], str)
    assert args[0] in env, f"Unknown variable {args[0]}"
    return env[args[0]]

To define a new variable or change an existing one, we evaluate an expression and store its value in the environment:

def do_set(env, args):
    assert len(args) == 2
    assert isinstance(args[0], str)
    value = do(env, args[1])
    env[args[0]] = value
    return value

We need to add one more function to make this all work. Our programs no longer consist of a single expression; instead, we may have several expressions that set variables’ values and then use them in calculations. To handle this, we add a function do_seq that runs a sequence of expressions one by one. This function is our first piece of control flow: rather than calculating a value itself, it controls when and how other expressions are evaluated. Its implementation is:

def do_seq(env, args):
    assert len(args) > 0
    for item in args:
        result = do(env, item)
    return result

Let’s try it out. Our test program is:

[
    "seq",
    ["set", "alpha", 1],
    ["set", "beta", 2],
    ["add", ["get", "alpha"], ["get", "beta"]]
]

=> 3

# not actually legal Python
result =
    if a > 0:
        1
    elif a == 0:
        0
    else:
        -1

Introspection

Now that we have evaluation, function lookup, and environments, we can write small programs. However, our do function now looks like this:

def do(env, expr):
    if isinstance(expr, int):
        return expr
    assert isinstance(expr, list)
    if expr[0] == "abs":
        return do_abs(env, expr[1:])
    if expr[0] == "add":
        return do_add(env, expr[1:])
    if expr[0] == "get":
        return do_get(env, expr[1:])
    if expr[0] == "seq":
        return do_seq(env, expr[1:])
    if expr[0] == "set":
        return do_set(env, expr[1:])
    assert False, f"Unknown operation {expr[0]}"

The sequence of if statements that decide what function to call is becoming unwieldy. (Quick: can you see if any of the instruction names are accidentally duplicated?) We can replace this by using introspection to create a lookup table that stores every function whose name starts with do_ (Figure 7.2):

OPS = {
    name.replace("do_", ""): func
    for (name, func) in globals().items()
    if name.startswith("do_")
}

Line by line:

1. We use a dictionary comprehension to create a dictionary in a single statement.

2. We only add functions whose names start with do_.

3. Each key-value pair in the dictionary is the name of an operation and the function that implements the operation. The operation’s name is what comes after do_ in the function’s name.

With this lookup table in hand, the code to select and run an operation is:

def do(env, expr):
    # Integers evaluate to themselves.
    if isinstance(expr, int):
        return expr

    # Lists trigger function calls.
    assert isinstance(expr, list)
    assert expr[0] in OPS, f"Unknown operation {expr[0]}"
    func = OPS[expr[0]]
    return func(env, expr[1:])

As with unit test functions in Chapter 6, the do_* functions must have exactly the same signature so that we can call any of them with an environment and a list of arguments without knowing exactly which function we’re calling. And as with finding tests, introspection is more reliable than a hand-written lookup table but is harder to understand. If we write out the lookup table explicitly like this:

OPS = {
    "abs": do_abs,
    "add": do_add,
    "get": do_get,
    "seq": do_seq,
    "set": do_set,
}

then we can see exactly what operations are available and what their names are. If we use introspection, we have to search through the source file (or possibly several files) to find all the available operations, but we can write do once and never worry about it again.

Summary

Figure 7.3 summarizes the ideas introduced in this chapter. A lot is going on here, but the central idea is that a program is just another kind of data. Please see Appendix B for extra material related to these ideas.

Exercises

Arrays

Implement fixed-size, one-dimensional arrays: ["array", 10] creates an array of 10 elements, while other instructions that you design get and set particular array elements by index.

Better Error Handling

Several of the instruction functions started with assert statements, which means that users get a stack trace of TLL itself when there’s a bug in their program.

1. Define a new exception class called TLLException.

2. Write a utility function called check that raises a TLLException with a useful error message when there’s a problem.

3. Add a catch statement to handle these errors.

More Statements

Add print and repeat commands to the interpreter so that the following program produces the output shown:

[
    "seq",
    ["set", "a", 1],
    ["print", "initial", ["get", "a"]],
    [
        "repeat", 4,
        [
            "seq",
            ["set", "a", ["add", ["get", "a"], ["get", "a"]]],
        ["if",
        ["leq", ["get", "a"], 10],
        ["print", "small", ["get", "a"]],
        ["print", "large", ["get", "a"]]
        ]
        ]
    ]
]

initial 1
small 2
small 4
small 8
large 16
=> None

Does your repeat command handle “repeat zero times” correctly, i.e., does it handle the program below? If so, what does your do_repeat function return as a result in this case?

["repeat", 0, ["print", "zero"]]

Tracing

Add a --trace command-line flag to the interpreter. When enabled, it makes TLL print a message showing each function call and its result.

While Loops

Implement a while loop instruction. Your implementation can use either a Python while loop or recursion.

Internal Checks

Defensive programming is an approach to software development that starts from the assumption that people make mistakes and should therefore put checks in their code to catch “impossible” situations. These checks are typically implemented as assert statements that check the state of the program as it executes, like those in our interpreter that checks the lengths of lists.

1. What other assertions could we add to this code?

2. How many of these checks can be implemented as type hints instead?