Software Design by Example: An Interpreter

<p>
  <a href="https://third-bit.com/sdxpy/">Software Design by Example</a>
</p>
<h1>An Interpreter</h1>
<div class="bottom">
  <a href="../">chapter</a>
</div>

---

## 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 <a class="gl-ref" href="../../glossary/#gl:parser" title="A function or program that reads text formatted according to some grammar and converts it to a data structure in memory. Every programming language has a parser that reads programs written in that language; parsers also exist for various data formats." markdown="1">parser</a> and a <a class="gl-ref" href="../../glossary/#gl:runtime" title="A program that implements the basic operations used in a programming language." markdown="1">runtime</a>
-   Look at the latter in this lesson to see how programs actually run

---

## Representing Expressions

-   Represent simple arithmetic operations as lists

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

-   We use special <a class="gl-ref" href="../../glossary/#gl:infix_notation" title="Writing expressions with operators between operands, as in `1 + 2` to add 1 and 2." markdown="1">infix notation</a> like `1+2` for historical reasons
-   Always putting the operation first makes processing easier

---

## Evaluating Expressions

```py
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

```py
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 <a class="x-ref" href="../../test/">Chapter 6</a>

---

## Dispatching Operations

-   Write a function that <a class="gl-ref" href="../../glossary/#gl:dynamic_dispatch" title="To find a function or a property of an object by name while a program is running. For example, instead of getting a specific property of an object using `obj.name`, a program might use `obj[someVariable]`, where `someVariable` could hold `"name"` or some other property name." markdown="1">dispatches</a> to actual operations

```py
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

---

## An Example

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

```sh
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 <a class="gl-ref" href="../../glossary/#gl:environment" title="The set of variables currently defined in a program." markdown="1">environment</a>

```py
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

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

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

```py
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 <a class="gl-ref" href="../../glossary/#gl:expression" title="A part of a program that produces a value, such as `1+2`." markdown="1">expressions</a> that produce values
    from <a class="gl-ref" href="../../glossary/#gl:statement" title="A part of a program that doesn't produce a value. `for` loops and `if` statements are statements in Python." markdown="1">statements</a> that don't
-   But it doesn't have to, and many languages don't

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

---

## Doubling

```tll
[
    "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

```py
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

```py
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 <a class="gl-ref" href="../../glossary/#gl:extensibility" title="How easily new features can be added to a program or existing features can be changed." markdown="1">extensible</a> 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 <a class="x-ref" href="../../func/">Chapter 8</a>

---

## Summary