AST → Code

Generating stack bytecode from an expression AST is a post-order walk: children first, operator last, one instruction per node. Source 1 + 2 * 3 therefore writes MUL before ADD because * sits deeper in the tree, not because anyone reordered the text. Time complexity is linear in the number of nodes.

Think of a stack of plates. You cannot add until both numbers are sitting there, so the operator is written after its operands. The IR panel — intermediate representation — is the program listing you are writing, not the runtime stack those plates would live on. The plates are why the listing is in that order. The source string is a serialization. The tree is the program.

How AST to code works

The compiler does not copy your source. A parser (the sibling lesson) has already turned the string into a tree of Lit, Name, and BinOp nodes. Codegen walks that tree and appends toy stack bytecode (LOAD_CONST, LOAD_NAME, ADD, MUL) for a later VM to run:

• a literal becomes LOAD_CONST
• a name becomes LOAD_NAME
• a + or * becomes ADD or MUL, after both children have been written

That last rule is the whole lesson. It is why 1 + 2 * 3 and (1 + 2) * 3 — the same tokens, two different trees — emit different programs. Precedence already happened at parse time. Codegen just reads the shape.

You write a pass like this when you ship a transpiler, an expression optimizer, or a VM backend: rewrite the tree first (fold constants, desugar a helper), then reuse the same emitter. Babel and TypeScript both work that way. Fold is that rewrite-then-emit split in miniature.

Fold is a second function that runs first. For each binop, fold the children, and if both came back literals, replace the binop with Lit(eval(op, left, right)). Then emit whatever remains. 1 + 2 * 3 collapses to LOAD_CONST 7. x + 2 * 3 still folds the *, then stops: a name is not a literal, so the + stays and you get three instructions instead of one.

AST → Code Step by Step

The default run is Naive on 1 + 2 * 3. The tree is +(1, *(2, 3)). The IR listing starts empty.

1. The program is the tree. + at the root, 1 on the left, * on the right with 2 and 3 under it. Nothing has been written yet.
2. Descend into 1. The operator waits. Children first.
3. LOAD_CONST 1. A leaf writes the constant.
4. Back to +. The left child is in the IR.
5. Descend into *. Still the right child of +.
6. Descend into 2. * waits the same way + did.
7. LOAD_CONST 2.
8. Back to *.
9. Descend into 3.
10. LOAD_CONST 3.
11. Back to *. Both children are in the IR.
12. MUL. Operator last. The source mentioned + first; the IR writes MUL first, because * was deeper.
13. Back to +.
14. ADD. The root emits last.
15. Five instructions. LOAD_CONST 1, LOAD_CONST 2, LOAD_CONST 3, MUL, ADD.

Flip the variant to Fold on the same tree. The walk skips leaves (they are already literals), rewrites 2 * 3 into 6, then 1 + 6 into 7, then emits LOAD_CONST 7. Same expression, five instructions become one. The x + 2 * 3 scenario is the breaking point: * still folds, + cannot, and the leftover tree emits LOAD_NAME x / LOAD_CONST 6 / ADD.

The Code panel highlights emit(node.left) and emit(node.right) on the descend beats, and only the LOAD_CONST line on a literal emit — never the LOAD_NAME line at the same time. Fold's return Lit(...) and return BinOp(...) are split the same way.

Why MUL before ADD

Instruction order is tree shape. (1 + 2) * 3 is the same numbers with + deeper, so Naive writes ADD then MUL. Nobody swapped the tokens. The parser built a different tree, and codegen is just walking it.

That is also why Fold is a rewrite, not a special emitter. The emit function is identical in both variants. The only change is the tree it is handed. If Fold rewrote a node before folding the children, 1 + 2 * 3 could not fold the + — the right child would still look like a *, and you would emit three instructions instead of one. Bottom-up is not a style choice. It is the condition the rewrite needs.

Naive cost is O(n) instructions for n nodes. Fold is O(n) to rewrite plus O(k) to emit the remainder, with k ≤ n. Equality holds when nothing folded — a tree like x + y, where no binop has two literal children. A name blocks every ancestor that depends on it, but independent literal subtrees still fold: x + 2 * 3 still folds 2 * 3, so k < n. You pay a linear rewrite for a possibly-shorter program, and you keep whatever the rewrite could not touch.

Edge Cases

• Parentheses change the tree, not the walk. (1 + 2) * 3 is a different shape, so it is a different program. The walk rule does not change.
• A name blocks its ancestors, not the cousins. In (x + 1) * 2 neither binop folds; x + 2 * 3 still folds 2 * 3.
• Two independent muls fold separately. 2 * 3 + 4 * 5 becomes 6 + 20 and then 26 under Fold, or seven instructions under Naive.
• A tree of one literal (what Fold leaves of 1 + 2 * 3) emits a single LOAD_CONST. There is no operator left to wait for children.
• There is no empty tree here. The canned expressions all have a root. An empty program is a parser problem.

Common Mistakes

• Emitting in source order. Writing ADD first because the string says 1 + ... is pre-order. A stack machine would underflow: the operator would run with an empty stack.
• Pretty-printing and codegen are not inverses. Unparsing puts the + back in the middle of the line. Codegen puts it last, because the consumer is a stack, not a reader.
• Folding top-down. If you rewrite the current node before the children have become literals, a constant expression that is not already a flat Lit op Lit will not collapse. The default tree is the counterexample.
• Treating Fold as a different emitter. Both variants share emit. If the Fold run still writes five instructions, the rewrite did not run, or it ran after emit.
• Reading the IR panel as a runtime stack. Those rows are the program being written. The plates metaphor is why operators come last in that listing, not a picture of execution. The stack the VM will use is the next lesson.

A Note on Simplification

This is an explainer, not a compiler backend. The IR is toy stack bytecode (LOAD_CONST, ADD, MUL). Real compilers lower to three-address code or SSA, run many passes (constant propagation, dead-code elimination, inlining), then instruction-select into machine code and allocate registers. There is no control flow here — no if, no loops — and no runtime stack shown.

Post-order emit and one instruction per node belong to this stack target; a source emitter like TypeScript's prints 1 + 2 * 3 infix. The split that stays true is rewrite-then-emit: change the tree, then emit. If you are writing a Babel plugin or a toy VM, you are already on it.