A price rule typed by a manager
An online shop lets a manager type a price rule, such as price * count + 2, into a settings page. The rule changes every week.
Nobody wants to compile and restart the shop for each change. Instead, the shop keeps the rule's syntax tree and works it out, node by node, every time an order comes in.
By the end of this lesson
Note
I can run a syntax tree directly.
Key words
| Word | What it means | Example |
|---|---|---|
| Interpreter | a program that runs another program without making machine code | |
| Node | one point in a tree | BinOp |
| Evaluate | work out the value of a node | |
| Leaf | a node with nothing below it | Constant(value=2) |
| Environment | the names in reach and their values | {'price': 3} |
| Binding | one name paired with its value |
The cells students fill in are left blank in this preview.
Python will show you its tree
Python is a compiler too. Before it runs a line, it lexes and parses it into a syntax tree. The module ast prints that tree for a line read from the keyboard or a pipe. --mode eval says the line is one expression.
Each node has a name. A leaf has nothing below it. Compare the two trees the Runs print.
The tree for 2 + 3 * 4
echo "2 + 3 * 4" | python3 -m ast --mode evalShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
The tree for (2 + 3) * 4
echo "(2 + 3) * 4" | python3 -m ast --mode evalShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
A tree with names in it
echo "price * count" | python3 -m ast --mode evalShown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: the nodes Python printed
| Node | What it is | Its value comes from |
|---|---|---|
| Constant(value=3) | A leaf holding a number | The number itself |
| Name(id='price') | A leaf holding a name | Looking the name up |
| BinOp(left, op, right) | An operation with two sides | Both sides, then the op |
| Add() or Mult() | Which operation | Nothing: it is a label |
The cells students fill in are left blank in this preview.
Evaluate the children, then the node
A tree-walking interpreter is one function that evaluates a node. A leaf with a number gives the number. An operation first evaluates its left child and its right child, then does its own sum on the two answers.
Because a child can be a whole tree, the function calls itself. The demo handles + and * on numbers.
A tree-walking evaluator
# Evaluate a syntax tree: a number, or [op, left, right].
def evaluate(tree):
if type(tree) == int:
return tree
op = tree[0]
# Work out both sides first: this is the recursion.
left = evaluate(tree[1])
right = evaluate(tree[2])
if op == "+":
return left + right
if op == "*":
return left * right
return None
tree = ["+", 2, ["*", 3, 4]]
print(evaluate(tree))
# Change tree to ["*", ["+", 2, 3], 4] and run again.
A common mistake
Warning
Many people think an interpreter quietly turns the tree into machine code and runs that. A tree-walking interpreter never does. It visits the nodes and does the work as it goes, again each time it runs. That is why it is slower than compiled code, and why it can start at once.
Names are looked up in an environment
A leaf that holds a name needs a value from somewhere. The interpreter keeps an environment: each name in reach, paired with its value. Each pair is a binding.
Python's eval takes the environment as a dictionary. Give it a second dictionary and Python searches that one first. That is how an inner scope hides an outer name.
Evaluate with an environment
python3 -c "print(eval('price * count', {'price': 3, 'count': 4}))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Leave a name out
python3 -c "print(eval('price * count', {'price': 3}))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
An inner environment searched first
python3 -c "print(eval('price * count', {'price': 3, 'count': 4}, {'count': 10}))"Shown here, not run. Create a free account to press Run and type it into your own lab’s terminal.
Worked example: looking up price * count
| Run | price found in | count found in | Printed |
|---|---|---|---|
| First | The one dictionary: 3 | The one dictionary: 4 | 12 |
| Second | The one dictionary: 3 | Nowhere | NameError |
| Third | The outer dictionary: 3 | The inner dictionary: 10 | 30 |
The cells students fill in are left blank in this preview.
Going further
Add an if node to your evaluator: ["if", test, then, otherwise]. Evaluate the test. If it is not 0, evaluate then, otherwise evaluate otherwise.
Make sure only one of the two branches is ever evaluated. Write a test that proves it, using a branch that would raise NameError if it ran.