Lowering: AST to Stack Bytecode

Why this module exists

Your AST is good for analysis and validation, but not for direct execution. Lowering is the translation from structured syntax to linear instruction flow.

For this course stage, stack bytecode is a deliberate choice:

• tiny runtime engine
• explicit operand order
• easy tracing and teaching

1) Lowering is a semantic transformation

Every AST node must map to an instruction sequence with equivalent meaning.

Think in terms of contract:

• for every node kind, define exact emitted sequence
• preserve evaluation order
• preserve side effects
• preserve error behavior where applicable

This is why lowering is not string formatting. It is a compiler phase with correctness rules.

2) Stack bytecode model and canonical traversal

Stack bytecode is postfix (RPN):

• push operands first
• apply operator last

For 1 + 2 * 3:

PUSH_NUM 1
PUSH_NUM 2
PUSH_NUM 3
OpMul
OpAdd

The compiler side of this module is simply:

1. lower left
2. lower right
3. emit op for parent

Do left-first traversal unless your language explicitly defines another operand order.

3) Lowering rules by node family

Literals and identifiers

• Number(v) -> PUSH_NUM v
• String(s) -> PUSH_STR s
• Bool(b) -> PUSH_BOOL b
• Identifier(name) -> LOAD name

Unary operators

• lower operand first
• emit unary opcode

Examples:

• -x -> [lower x] OpNeg
• !x -> [lower x] OpNot

Binary operators

• lower left, then right
• emit operator opcode

Statement/list nodes

• lower each child in source order
• emit statement-level terminators exactly where needed

Calls

• lower arguments in source order
• emit CALL name arity

Blocks / scopes

• ENTER_SCOPE before block body
• emit body
• EXIT_SCOPE after body

This keeps scope behavior explicit and easy to inspect.

4) Determinism and idempotent tests

A tiny but high-value rule:

• lowering of the same AST must always produce identical bytecode text/instruction sequence.

This enables tests like:

1. AST -> bytecode
2. bytecode -> BC1
3. BC1 -> bytecode roundtrip checks
4. execution equality checks

If lowering is non-deterministic, every downstream stage becomes flaky.

5) Why order bugs are silent killers

Most lowering bugs still execute, just wrong:

• swapping left/right on subtraction/division
• popping arguments in reverse for calls that were meant to preserve user order
• omitting scope instructions, causing bindings to leak
• forgetting to emit a block delimiter

The VM might not crash, so your test oracles must assert result values and scope depth.

6) Extending lowering safely (future-proofing)

The simplest expansion path:

• keep base postfix emitter
• add optional lowering passes (peephole, constant folding, jump simplification)
• keep the same semantic contract and tests

Useful future targets:

• explicit temporaries / register IR
• control-flow graph lowering
• SSA conversion

All are easier after a stable stack-lowering baseline.

7) Practice checkpoints (almost solved)

1) In-order expression lowering
Input AST: (4 - 2) / 1
Expected bytecode:

PUSH_NUM 4
PUSH_NUM 2
OpSub
PUSH_NUM 1
OpDiv

2) Call lowering
Input: sum(1, a, b + 2)
Expected order:

PUSH_NUM 1
LOAD a
LOAD b
PUSH_NUM 2
OpAdd
CALL sum 3

3) Scope lowering
For block with local declaration and usage, the emitted sequence must include:

• ENTER_SCOPE before inner body
• EXIT_SCOPE after it

or locals can escape.

4) Side-effect ordering
If AST evaluates f(); g() as statements, emitted order must keep two calls in the same order.

5) Unary then binary
Input: -(a + b)
Expected pattern:

LOAD a
LOAD b
OpAdd
OpNeg

6) Determinism check
Given same AST twice, sequences should be byte-for-byte equal (ignoring BC1 formatting strategy).

7) Error-oriented check
If lowering sees an unknown node kind, fail the compiler stage with a meaningful diagnostic including node kind and source location.