algebra simplifier explanation, part 2: Scratch

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 takes mathematical expressions and simplifies them step by step, showing each transformation visually.

The project has several files (all in docs/examples/):

33_algebra_simplifier.py — full version with graphical UI (keyboard, stamps)
33_algebra_simplifier_bare_engine.py — engine only, minimal UI (this doc describes it)
33_algebra_ui.py — UI shell with engine stubbed out
33_algebra_prototype_recursive.py — Python prototype (clean, recursive)
33_algebra_prototype_iterative.py — Python prototype (iterative, Scratch-compatible)
33_how_the_python_prototypes_work.md — companion doc explaining the Python prototypes

This document explains how the math engine works inside Scratch — how it’s structured, what each procedure does, and how to follow the code. If you’ve opened the .sb3 in the Scratch editor and are looking at ~1800 blocks thinking “where do I even start?” — this is your map.

What it does

Takes an algebraic expression like 2*(x+3) or (a+b)*(a-b) and simplifies it step by step:

2*(x+3)  →  2*x + 2*3  →  2*x + 6

It knows: distribute, combine like terms, constant fold, cancel fractions, GCD, and more.

Execution flow — bird’s eye view

expression (text)
     │
     ▼
   parse          ← turns text into a tree (AST)
     │
     ▼
   format         ← turns tree back into text for display
     │
     ▼
   ┌─────────────────────┐
   │  simplify_step      │  ← press Space: applies one rule
   │  format             │  ← shows the new expression
   │  (repeat until done)│
   └─────────────────────┘

Set the expression variable to your input text.
parse is called — builds the tree in lists nT, nV, nK. Sets root.
format is called — walks the tree, produces readable text in display.
Each Space press calls simplify_step — finds one rule to apply, transforms the tree, then format displays the result.
When no rule applies, simplification is done.

The tree structure (AST)

Scratch has no objects or pointers, so the tree lives in three parallel lists:

List	Contains	Example
`nT`	node type	`"SUM"`
`nV`	node value	`""` (empty for SUM/PROD/NEG/FRAC)
`nK`	children (comma-separated indices)	`"1,4"` (children are nodes 1 and 4)

Position = node index. If nT[5] = "SUM" and nK[5] = "1,2", that means node 5 is an addition of node 1 and node 2.

Node types:

NUM — a number (value in nV)
VAR — a variable letter (value in nV)
SUM — addition (2 or more children)
PROD — multiplication (2 or more children)
NEG — negation (1 child)
FRAC — division (2 children: numerator, denominator)

Nodes are append-only — once created, never modified. Simplification creates new nodes and a new root each time.

The parser — procedure by procedure

`tokenize`

Reads expression character by character. Groups consecutive digits into multi-digit numbers. Outputs to the tokens list.

"2*(x+3)" → ["2", "*", "(", "x", "+", "3", ")"]

`mark_unary`

Scans tokens. Any - at the start, after (, or after an operator is renamed to "NEG" (unary minus, not subtraction).

`parse`

The main parser. Uses the shunting-yard algorithm with two stacks:

opStk — operators waiting to be applied
outStk — finished tree nodes (indices)

Reads tokens left to right:

Number/variable → alloc_node creates a leaf node, pushes index to outStk
Operator → pops higher-priority ops from opStk (calling apply_op), then pushes itself
( → pushed to opStk as a marker
) → pops and applies operators until ( is found

After all tokens: pops remaining operators. The single node on outStk becomes root.

`apply_op`

Pops operands from outStk, creates a new node:

+ → SUM (extends left child if it’s already a SUM — makes n-ary)
- → SUM with right child wrapped in NEG
* → PROD (extends left if already PROD)
/ → FRAC
NEG → wraps one operand in NEG (or just negates a number directly)

The simplifier — procedure by procedure

`simplify_step`

The workhorse. Depth-first search through the tree:

Start at root, call try_simplify
If nothing fires (ret_changed = 0): descend to first child
If still nothing: backtrack to parent, try next child
When a rule fires: rebuild the path from that node back to root

Uses pN/pC lists (path nodes / path child-index) to remember the descent.

`try_simplify`

The brain. Checks the node type and tries all applicable rules:

%NEG rules%

Child is NUM → negate the number
Child is NEG → double negative, unwrap
Child is SUM → distribute: -(a+b) → (-a)+(-b)

%SUM rules%

Flatten: child is SUM → inline its children
Remove zeros: drop any NUM 0 child
Combine like terms: extract_coeff decomposes each child into (coefficient, variable-key). Matching keys → merge. Uses sort_varkey so a*b = b*a.

%PROD rules%

Flatten: child is PROD → inline
Multiply by 0 → result is 0
Remove × 1 → drop that factor
Constant fold: multiply NUM factors together (2*3*x → 6*x)
Pull minus out: NEG factor → move outside the product
Distribute: SUM factor → expand (a*(b+c) → a*b + a*c)

%FRAC rules%

x/1 → x
0/x → 0
x/x → 1
Cancel common variable from numerator PROD
GCD: divide both numbers by greatest common divisor
Reduce: NUM / PROD(NUM, …) → divide both NUMs by GCD

`extract_coeff`

Splits a term into coefficient + variable key:

3*x*y → coeff=3, varkey="xy"
x → coeff=1, varkey="x"
-2*a → coeff=-2, varkey="a"

Calls sort_varkey to normalize: b*a and a*b both get varkey "ab".

`make_term`

Builds a node from coefficient + variable factors:

coeff=0 → NUM 0
coeff=1 → just the vars
coeff=-1 → NEG(vars)
other → PROD(coeff, vars)

The formatter

`format`

Post-order traversal using stack fStk. Entries: "nodeIndex,phase".

Phase 0: leaf → store its value; non-leaf → push children, schedule phase 1
Phase 1: compose from children’s cached strings

Uses fmt_lookup / fmt_store with cache lists fN/fS.

Formatting rules:

NUM/VAR → just the value
NEG → "-" + child (parentheses if child is complex)
SUM → join with " + ", NEG children shown as " - "
PROD → join with " * ", parentheses around SUM/NEG children
FRAC → numerator " / " denominator, parentheses where needed

Utility procedures

Procedure	Input	Output	What it does
`alloc_node`	t5=type, t6=value, ret_str=kids	ret=new index	Appends to nT/nV/nK
`get_kid`	t1=node, t2=which (1-based)	ret=child index	Parses comma-separated nK
`kid_count`	t1=node	ret=count	Counts children
`kids_to_list`	t1=node	kT list filled	Splits nK into list
`list_to_kids`	kT list	ret_str=joined	Joins list back
`sort_varkey`	ret_varkey string	ret_varkey sorted	Bubble-sorts characters

Why so many variables?

Scratch variables are global. If two procedures both use i as a loop counter, one clobbers the other. Each procedure gets dedicated variables:

ui — only kids_to_list and list_to_kids
gk — only get_kid
si, sj, sf — only sort_varkey
fi — only flatten operations
ni — only neg-distribute and frac cancel
ga, gb, gt — only GCD computation

General temps t1–t8 are shared by simplifier rules, but ret2 saves the original node before try_simplify (which clobbers t1/t3).

Tips for exploring

Start simple: expression "3+5", step through. Parse creates 3 nodes, simplify combines them into NUM 8.
Distribution: try "2*(x+3)". Watch PROD(2, SUM(x,3)) become SUM(PROD(2,x), PROD(2,3)), then constant fold gives 2*x + 6.
Full experience: "(a+b)*(a-b)" — distribute, flatten, cancel like terms, end up with a*a - b*b.
Enable logs: check the logs list in the variables panel. Shows which nodes are visited and which rules fire.
Run tests: press "t" — 17 built-in tests verify correctness.
Add a rule: look at FRAC x/x → 1 — simplest example. Check condition, build new node with alloc_node, set ret_str and ret_changed=1.