--- title: "AST → Code" description: "Tree walker, IR, optimization passes" source: https://vizlearn.app/cs/compilers/ast-codegen access: premium (interactive player requires Lifetime; this doc is free) --- # 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.