Lowering: AST to Stack Bytecode

Why this module exists

Once you have an AST, you need a form that is easy to execute or optimize. A simple stack-based bytecode is a good first target. It is small, readable, and predictable.

1) Stack bytecode in one minute

A stack machine evaluates expressions by pushing values and applying operators.

Example for 1 + 2 * 3:

PUSH 1
PUSH 2
PUSH 3
MUL
ADD

The order (left, right, operator) is called postfix or reverse Polish.

2) Lowering rules

Given an AST:

• Number: PUSH <value>
• Identifier: PUSH_IDENT <name>
• Unary: lower operand, then unary op
• Binary: lower left, lower right, then binary op
• Call: lower args in order, then CALL <name> <arity>

These rules are simple and deterministic.

3) Readable output helps debugging

When bytecode is easy to read, you can test and debug the compiler faster. Clever encodings are fine later, but clarity wins early.

4) Open-ended design

This is only one possible IR. You could also lower to:

• A tree-based IR
• A register-based bytecode
• SSA form

The key is consistency with the AST.