Experiments and implementations · Intermediate

Evaluate an expression tree with an explicit environment

Evaluate one tree under two environments and test the difference between valid syntax, defined names and legal arithmetic operations.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Separate the tree from the environment
  2. State the arithmetic rules
  3. Trace evaluation from subtrees
  4. Run a self-contained interpreter
  5. Distinguish syntax from available values
  6. Change data separately from structure
  7. Exercise: explain the chosen semantics
  8. Ask Logeia about this articleCheck your understanding

Separate the tree from the environment

A syntax tree describes structure, not every value required to compute a result. For x + 3 * (4 - 1), a separate environment maps the name x to a value. With x equal to twelve the result is twenty-one; with x equal to two it is eleven. We parse the expression only once and reuse that same tree under both dictionaries. This makes the division of responsibilities observable: changing a variable value does not require regrouping the expression. Here environment means the explicit name-to-value mapping supplied to the evaluator, not operating-system environment variables. Being able to identify exactly what a table contains is more useful than relying on a familiar implementation term whose meaning changes between systems.

State the arithmetic rules

A num node returns its stored integer. A name node looks up a spelling in the supplied environment. A binary node evaluates its left child, then its right child, and applies the indicated operation. Our teaching language defines slash as floor integer division, so (0 - 7) / 3 produces negative three. That is different from a language that truncates integer division toward zero. Although the implementation uses Python operations, its language contract must still be stated explicitly. Values are represented with Python integers, so this is not a simulation of fixed-width integer overflow either. Naming these choices before running negative or large inputs lets you distinguish an implementation bug from an intentional difference in arithmetic semantics.

Trace evaluation from subtrees

For the running expression, evaluation first obtains x from the left child of the root addition. It then visits the multiplication on the right, obtaining three from its left child and three from the subtraction subtree on its right. Multiplication returns nine, which is finally added to x. Each recursive return supplies one value for one subtree. There is no need to flatten the tree and decide operator precedence again: the parser has already encoded precedence in parent-child relationships. Repeated occurrences of a name perform repeated lookups. This small evaluator has no assignment or callback that mutates the environment during a traversal. Adding such features would require reconsidering state and evaluation order rather than assuming that the current pure-expression behavior still applies.

Run a self-contained interpreter

Save the complete program as interpreter.py and run it with Python 3.12 or a compatible later version. The scanner and parser are included, so the experiment has no dependency on files edited in earlier lessons. The final output is 21 11, the values produced from one tree under two explicit environments. A separate assertion checks negative division. Two deliberate failure tests then verify the types of exception produced by an undefined name and a zero divisor. Successfully detecting those failures counts as a passing experiment. A lack of uncaught error text alone is therefore not the result to interpret; follow which assertions establish each behavior. Fresh dictionaries also prevent a previous interactive assignment to x from accidentally becoming part of the test conditions.

python
import re

def scan(source):
    tokens = []
    i = 0
    while i < len(source):
        if source[i].isspace():
            i += 1
            continue
        match = re.match(r'[0-9]+|[A-Za-z_][A-Za-z_0-9]*|[()+*\-/]', source[i:])
        if not match:
            raise SyntaxError(f'character at {i}')
        word = match.group()
        kind = 'NUM' if word.isdecimal() else 'NAME' if word[0].isalpha() or word[0] == '_' else word
        tokens.append((kind, word, i))
        i += len(word)
    tokens.append(('EOF', '', i))
    return tokens

class Parser:
    def __init__(self, source):
        self.tokens = scan(source)
        self.i = 0
    def take(self, kind):
        token = self.tokens[self.i]
        if token[0] != kind:
            raise SyntaxError(f'expected {kind} at {token[2]}')
        self.i += 1
        return token
    def atom(self):
        kind, word, pos = self.tokens[self.i]
        if kind == 'NUM':
            self.take('NUM')
            return ('num', int(word))
        if kind == 'NAME':
            self.take('NAME')
            return ('name', word)
        if kind == '(':
            self.take('(')
            node = self.expr()
            self.take(')')
            return node
        raise SyntaxError(f'atom at {pos}')
    def term(self):
        left = self.atom()
        while self.tokens[self.i][0] in ('*', '/'):
            op = self.take(self.tokens[self.i][0])[0]
            left = (op, left, self.atom())
        return left
    def expr(self):
        left = self.term()
        while self.tokens[self.i][0] in ('+', '-'):
            op = self.take(self.tokens[self.i][0])[0]
            left = (op, left, self.term())
        return left
    def parse(self):
        tree = self.expr()
        self.take('EOF')
        return tree

def evaluate(node, env):
    kind = node[0]
    if kind == 'num':
        return node[1]
    if kind == 'name':
        return env[node[1]]
    left, right = evaluate(node[1], env), evaluate(node[2], env)
    if kind == '+': return left + right
    if kind == '-': return left - right
    if kind == '*': return left * right
    if kind == '/':
        if right == 0: raise ZeroDivisionError('zero divisor')
        return left // right
    raise ValueError(kind)

tree = Parser("x + 3 * (4 - 1)").parse()
assert evaluate(tree, {'x':12}) == 21
assert evaluate(tree, {'x':2}) == 11
assert evaluate(Parser("(0 - 7) / 3").parse(), {}) == -3
for source, env, error_type in [('x + 1', {}, KeyError), ('12 / 0', {}, ZeroDivisionError)]:
    try:
        evaluate(Parser(source).parse(), env)
    except error_type:
        pass
    else:
        raise AssertionError(source)
print(evaluate(tree, {'x':12}), evaluate(tree, {'x':2}))

Distinguish syntax from available values

The parser can construct a tree for x + 1 even when an empty environment later produces KeyError. It can also construct a tree for 12 / 0 even though evaluation produces ZeroDivisionError. Neither failure means the parser misread a parenthesis or operator. Converting every problem to SyntaxError would hide whether a reader should repair the expression structure or supply a missing value. This implementation leaves the exception classes visible as teaching observations. A product could attach a name occurrence or operator location to a user-facing diagnostic, but that requires retaining source positions in the tree. A later presentation layer cannot reliably reconstruct information that earlier stages discarded. Representation contracts therefore influence diagnostic quality as well as computation.

Change data separately from structure

Changing x while retaining the tree isolates the effect of input values. Removing parentheses or changing an operator changes the tree itself. Altering both at once makes the result harder to explain. First evaluate the original tree with x equal to zero and twelve, observing that its right subtree still contributes nine. Then fix x at twelve and change 3 * (4 - 1) to 3 * 4 - 1, which changes grouping and the overall result. Re-evaluating the current tree does not modify its dictionary because the language has no assignment operation. It also performs neither application authorization nor general validation of arbitrary Python objects. Keep the stated assumption that the environment contains integer values when interpreting these examples.

Exercise: explain the chosen semantics

Evaluate one tree for y * 2 + x under two environments: x equals one and y equals four, then x equals five and y still equals four. The worked answers are nine and thirteen. Only the final added value changes. Omitting y instead produces an undefined-name failure while evaluating the multiplication. Next predict (0 - 8) / 3. Floor division gives negative three, not negative two. Explaining that difference demonstrates that you are following the evaluator’s declared rules rather than importing another language’s arithmetic behavior. Finally notice that the implementation never calls Python eval. It handles only the node kinds defined for this teaching language, which keeps the representation and traversal inspectable instead of outsourcing them to another expression evaluator.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 20

Choose a learning path