An Interpreter · Software Design by Example

Background

Programs are just data
Compilers and interpreters are just programs
- Compiler: generate instructions once in advance
- Interpreter: generate instructions on the fly
- Differences are increasingly blurry in practice
Most have a parser and a runtime
Look at the latter in this lesson to see how programs actually run

Representing Expressions

Represent simple arithmetic operations as lists

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

We use special infix notation like 1+2 for historical reasons
Always putting the operation first makes processing easier

Evaluating Expressions

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

args is everything except the name of the operation
Use an as-yet-unwritten function do to evaluate the operands
Then add their values

Evaluating Expressions

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

All the do_ functions can be called interchangeably
Like the unit test functions of Chapter 6

Dispatching Operations

Write a function that dispatches to actual operations

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]}"

Dispatching Operations

Recursive evaluation of an expression tree — Figure 1: Recursively evaluating an expression tree

An Example

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

python expr.py expr.tll

=> 5

Environments

Store variables in a dictionary that's passed to every do_ function
- Like the dictionary returned by the globals function
- An environment

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

Getting Variables' Values

Choices for getting variables' values:
1. Assume strings are variable names
2. Define another function that we call explicitly

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]]

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

Sequencing

Need a way to set values before evaluating expressions
["seq", ["set", "a", 1], ["add", ["get", "a"], 2]]

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

Everything Is An Expression

Python distinguishes expressions that produce values from statements that don't
But it doesn't have to, and many languages don't

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

Doubling

[
    "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"]]
	    ]
        ]
    ]
]

Doubling

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

This Is Tedious

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]}"

But we know what to do

Introspection

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

How Good Is Our Design?

One way to evaluate a design is to ask how extensible it is
The answer for the interpreter is "pretty easily"
The answer for our little language is "not at all"
We need a way to define and call functions of our own
We will tackle this in Chapter 8

Summary