Experiments and implementations · Intermediate

Implement constant folding without hiding failures

Replace constant subtrees with computed values, comparing both successful results and error behavior before and after the transformation.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Define what the transformation must preserve
  2. Fold children before considering a parent
  3. Do not turn a failing computation into success
  4. Compare observations before and after folding
  5. Match the target arithmetic rather than the host by accident
  6. Choose tests that exercise different cases
  7. Exercise: explain why failure remains observable
  8. Ask Logeia about this articleCheck your understanding

Define what the transformation must preserve

Constant folding replaces a subtree whose value is known in advance with that value. In x + 3 * (4 - 1), the right subtree becomes nine even though x remains unknown. A shorter tree is not itself evidence of correctness. For this experiment, preserve values and error classes when the same integer environment is supplied to the original and transformed trees. Evaluation visits the left child before the right, and slash means floor integer division. State those choices before comparing outcomes. Floating-point arithmetic, function calls, side effects and fixed-width overflow are outside this teaching language. An optimization that is valid for this deliberately narrow set of rules cannot automatically be transferred to a larger implementation with different observable behavior.

Fold children before considering a parent

The fold function returns literal and name nodes unchanged. For a binary node it recursively transforms both children, builds a candidate node from those results, and evaluates that candidate only when both children are literals. This order first turns 4 - 1 into three, then turns the surrounding multiplication into nine. Inspecting only the parent before its children could miss that opportunity because one child initially contains another operation. Returning new tuples keeps the original tree available for direct comparison. That is a convenient teaching choice, not a universal requirement for compiler internals. Name nodes are not replaced using a convenient environment value: x is allowed to vary between executions, so fixing it during transformation would change the stated contract.

Do not turn a failing computation into success

Consider 0 * (1 / 0). Replacing the whole expression with zero based only on the outer multiplication would hide a zero-divisor failure, because the original evaluator visits the right operand as well. This implementation deliberately avoids that algebraic shortcut. Even a constant-only subtree such as 1 / 0 cannot be replaced with a value. The folder catches that expected arithmetic failure and leaves the operation node for evaluation later. This expresses a policy about error timing instead of moving the failure into the transformation stage accidentally. Real language specifications differ in what behavior their optimizers must preserve. Here the policy is explicit, and tests include inputs for which no ordinary numeric result exists.

Compare observations before and after folding

Save the complete code as fold.py and execute it with Python 3.12 or a compatible later version. It includes scanning, parsing and evaluation. The printed optimized tree retains the addition involving x and has a literal nine as its right child. Assertions compare both trees under three environments with x set to negative ten, zero and twelve. Additional cases record whether evaluation returned a value or raised a particular error class. Converting every failure to the same placeholder would conceal meaningful differences, so KeyError and ZeroDivisionError remain distinct observations. Passing establishes the intended simplification and preserved outcomes for these cases. It is not a proof covering every possible program or every feature of another language.

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)

def fold(node):
    if node[0] in ('num', 'name'):
        return node
    left, right = fold(node[1]), fold(node[2])
    candidate = (node[0], left, right)
    if left[0] == right[0] == 'num':
        try:
            return ('num', evaluate(candidate, {}))
        except ZeroDivisionError:
            return candidate
    return candidate

tree = Parser("x + 3 * (4 - 1)").parse()
optimized = fold(tree)
assert optimized == ('+', ('name','x'), ('num',9))
for x in [-10, 0, 12]:
    assert evaluate(tree, {'x':x}) == evaluate(optimized, {'x':x})
for source in ['0 * (1 / 0)', 'unknown + (2 * 3)']:
    before, after = Parser(source).parse(), fold(Parser(source).parse())
    outcomes = []
    for node in [before, after]:
        try:
            outcomes.append(('value', evaluate(node, {})))
        except (KeyError, ZeroDivisionError) as error:
            outcomes.append(('error', type(error).__name__))
    assert outcomes[0] == outcomes[1]
print(optimized)

Match the target arithmetic rather than the host by accident

Python integers do not model wraparound at a fixed bit width. Folding a very large sum here therefore does not represent the behavior of every machine-integer language. A compiler for a fixed-width target needs constant evaluation that matches the target’s overflow and conversion rules. Negative division provides another distinction between floor and truncation-toward-zero semantics. Adding floating-point values introduces rounding, special values and restrictions on reassociation. Using a host-language arithmetic operator does not automatically preserve a target language’s meaning. In this small system, transformation and evaluation intentionally share the same declared rules. Identify that premise before interpreting the successful examples as evidence for a broader class of optimizations.

Choose tests that exercise different cases

Include a fully constant expression, a name alone, a mixture of names and constants, and a constant subtree that fails. These cover different transformation paths instead of repeating similar additions. For example, x + 2 * 3 folds only its right subtree, while x * y retains both names. Grouping is already encoded in the tree, so the folder never turns nodes back into source text to reinterpret them. Enumerating small integer environments can strengthen testing, but a finite collection of examples still does not prove equivalence for every input. Explain the premises of each transformation rule and search for cases that would violate them. If measuring performance, keep tree node count separate from elapsed time: fewer nodes alone do not establish a speedup on a real machine.

Exercise: explain why failure remains observable

Predict the transformed trees for (2 + 3) * x and 0 * unknown. The first replaces its left subtree with five but retains x. The second retains the name and the multiplication; evaluating it under an empty environment still raises KeyError. Replacing it with zero would violate this experiment’s observation contract. Now fold (0 - 7) / 3. Both operands become constants, so the whole expression is replaced with the literal negative three under floor division. Compare your predicted trees with the actual output and identify exactly which subtrees changed. Preserve these examples as regression tests when extending the folder. No external resource needs cleanup. The referential-transparency lesson explains why adding stateful calls makes seemingly simple replacement rules harder to justify.

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