algebra simplifier explanation, part 1: Python prototype

Context

This document is part of the scratchgen project — a Python library that generates Scratch (.sb3) files from code. Example 33 is an algebraic expression simplifier: a Scratch program that parses expressions like (a+b)*(a-b) and simplifies them step by step.

Before building the Scratch version, we prototyped the algorithm in Python. These prototypes served two purposes:

  1. Verify the math works correctly (recursive version)
  2. Prove it can work without recursion, using only flat lists and global variables — the constraints that Scratch imposes (iterative version)

The prototypes live in docs/examples/:

The Scratch engine (33_algebra_simplifier_bare_engine.py) is a direct translation of the iterative prototype. See 33_how_the_scratch_engine_works.md for how to read the Scratch version.

This document explains the Python prototypes — the algorithm, data structures, and how they connect to the final Scratch implementation.

The two prototypes

Both are standalone scripts — run them to see step-by-step simplification printed to the terminal.

The recursive prototype

Data types (the AST)

The expression tree uses Python dataclasses:

@dataclass(frozen=True)
class Num:
    value: float

@dataclass(frozen=True)
class Var:
    name: str

@dataclass(frozen=True)
class Sum:
    terms: tuple      # n-ary: (child, child, child, ...)

@dataclass(frozen=True)
class Prod:
    factors: tuple    # n-ary: (factor, factor, ...)

@dataclass(frozen=True)
class Neg:
    expr: 'Expr'

@dataclass(frozen=True)
class Frac:
    num: 'Expr'
    den: 'Expr'

Key insight: Sum and Prod are n-ary (any number of children), not binary. This means a + b + c is one Sum with 3 terms, not nested Sum(Sum(a,b), c). This eliminates most associativity headaches.

Parser

Standard recursive descent:

Subtraction is represented as Sum(a, Neg(b)) — there is no “minus” node.

Formatter (fmt)

Recursive function that turns the tree back into a string. Handles:

Simplifier (simplify_step)

Takes a tree, returns (new_tree, description) or (same_tree, "") if nothing to do. Applies exactly one rule per call:

  1. Try rules at the current node (constant fold, remove zeros, combine like terms, distribute, etc.)
  2. If nothing fires: recursively try each child
  3. If a child simplifies: rebuild the parent with the new child

The rules, in priority order:

Like-terms matching

extract_coeff(expr) returns (coefficient, variable_key):

Variable keys are sorted tuples, so a*b and b*a produce the same key. When two terms in a Sum have the same key, their coefficients are added.

Running it

python3 33_algebra_prototype_recursive.py

Output shows each expression and its simplification steps:

Input: (a + b) * (a - b)
  (a + b) * (a - b)
  → (a - b) * a + (a - b) * b    [distribute...]
  → a * a - a * b + b * a - b * b [flatten sum]
  → a * a + 0 - b * b            [combine: -a*b and b*a → 0]
  → a * a - b * b                [remove 0]
  ✓ done

The iterative prototype

Why it exists

Scratch can’t do recursion safely (global variables collide). This prototype proves the same algorithm works with:

Key differences from the recursive version

Tree storage: Three parallel lists (node_type, node_value, node_kids) indexed by integer. Same as the Scratch version.

Parser: Shunting-yard algorithm (iterative) instead of recursive descent. Uses operator stack + output stack.

Formatter: Post-order traversal with explicit stack. Stack entries are (node_index, phase) — phase 0 pushes children, phase 1 composes.

Simplifier: DFS with a “path stack” recording the descent. When a rule fires deep in the tree, the path is replayed upward to rebuild the root.

Sort key computation: Iterative post-order traversal (instead of recursive sort_key() function).

Variable discipline

Even in Python, this prototype uses global variables to simulate Scratch:

ret = 0          # "return value" from procedures
ret_str = ""     # string return
ret_changed = False

This is intentional — it’s testing that the approach works when you can’t have local scope or return values.

Running it

python3 33_algebra_prototype_iterative.py

Same output as the recursive version. If both produce identical results, the iterative version is ready to translate to Scratch blocks.

From prototype to Scratch

The Scratch version (33_algebra_simplifier_bare_engine.py) is a direct translation of the iterative prototype:

Python iterative Scratch equivalent
node_type list nT list
node_value list nV list
node_kids list nK list
while stack: loop repeat_until(stack.length = 0)
stack.append(x) stack.add(x)
stack.pop() item(length), delete(length)
def try_simplify_node(i) custom block try_simplify with t1 as input
return ret set ret variable, check ret_changed

The main challenge in translation wasn’t the algorithm — it was variable collisions. The Python prototype uses globals but Python doesn’t have nested procedure calls clobbering them. In Scratch, every call() shares the same variables, so dedicated variables per procedure became essential.

Summary