How Meaning Became Motion: Code Generation and the Compiler

Planted 02026-08-01

How can a tree become a sequence without losing what it means?

How can meaning become motion?

The parser has read this Jack statement:

let total = (price * quantity) + tax;

It has recovered a structure:

let statement
├── destination: total
└── expression
    ├── multiplication
    │   ├── price
    │   └── quantity
    └── addition with tax

The tree records what belongs together.

But nothing in the tree tells the virtual machine to move a value.

No operand has been pushed.

No multiplication has been performed.

No result has been stored.

The compiler must now flatten the structure into a sequence of commands—and the order of that sequence must preserve every relationship the parser discovered.

It must turn containment into time.

What the program is
        ↓
What the machine must do

This is code generation.

1. The tree that cannot act

A syntax tree is a description.

The virtual machine needs instructions.

For the order total, those instructions might eventually resemble:

push argument 0
push local 1
call Math.multiply 2
push this 2
add
pop local 0

The VM sequence contains details absent from the source.

price has become argument 0.

quantity has become local 1.

tax has become this 2.

The multiplication has become a call because the Hack VM has no primitive multiply command.

The destination total has become local 0.

Those choices are not visible in the spelling of the names.

The parser learned that price was an identifier inside an expression. It did not learn where the value would live at runtime. It learned that square.moveRight() was a qualified subroutine call. It did not determine whether square named a class or a particular object.

Structure is necessary.

It is not sufficient.

2. Why a compiler cannot replace words

An assembler can often translate a mnemonic using a direct agreement:

D+1 → these ALU control bits

A high-level compiler cannot rely on one replacement for each word.

Consider the name count:

static int count;
field int count;
var int count;

The same spelling can describe a class-wide value, a field belonging to one object, or a local value belonging to one invocation.

Each requires a different VM segment.

Consider the plus sign:

left + right

The compiler cannot emit add when it first encounters +. The values on both sides must be produced first.

Consider a method call:

do square.moveRight();

If square is a variable, its object address must be passed as an invisible argument. If the word before the dot is a class name, the call may be a function or constructor and no existing object needs to be pushed.

The correct output depends on relationships accumulated from declarations, grammatical structure, and calling conventions.

Code generation is not substitution.

It is decision-making under agreements established by every layer below.

3. The parentheses that logic wanted to escape

Long before compilers, logicians faced a problem of notation.

In ordinary infix notation, an operator sits between its operands:

price * quantity

Larger expressions require conventions or punctuation to preserve grouping:

(price * quantity) + tax

Without the parentheses, a reader needs rules about which operator binds first. With many nested operations, the marks accumulate.

The Polish logician Jan Łukasiewicz searched for a notation in which the structure of a logical formula could be recovered without parentheses.

In 1924, he developed what became known as Polish notation. The operator appears before its operands.

Ordinary infix form:

(p implies q) and r

Prefix form:

and implies p q r

If every operator has a known number of operands, the sequence carries its own grouping. The reader knows that implies consumes p and q, and that and combines that result with r.

Łukasiewicz devised the notation for logic, not for the stack machine we are building.

An attempt to make symbolic structure clearer would later become useful to people trying to make expressions executable.

4. The philosopher who turned the operators around

Charles Hamblin was an Australian philosopher and logician working with one of his country’s early electronic computers.

The machine was a DEUCE, derived from designs developed in Britain. Like other computers of its period, it did not receive ordinary algebra and somehow discover a good instruction sequence. Someone had to translate formulas into the operations and storage arrangements the machine could perform.

Hamblin explored a reversal of Łukasiewicz’s arrangement.

Instead of placing an operator before its operands, place it after them:

price quantity * tax +

This became known as reverse Polish notation, or postfix notation.

Hamblin used the idea in a programming system called GEORGE and paired it with a push-down, pop-up store—a stack-like mechanism he described as a running accumulator.

Other researchers reached related ideas independently.

In Germany, Friedrich Bauer and Klaus Samelson developed what they called the cellar principle while investigating the translation of algebraic expressions. Intermediate values and postponed operations could be placed into last-in, first-out storage and recovered in the reverse order.

The multiple paths matter.

No single person sat down and invented every modern use of the stack. Subroutine returns, recursive calls, formula translation, and automatic storage each placed people in situations where the newest unfinished thing needed attention first.

The stack kept reappearing because the shape of the problem kept demanding it.

5. An expression the stack can perform

Take the infix expression:

(price * quantity) + tax

Its postfix form is:

price quantity * tax +

Now read it from left to right with a stack.

First, place price on the stack:

price

Then place quantity above it:

quantity
price

The multiplication consumes the top two values and replaces them with their product:

price × quantity

Next, push tax:

tax
price × quantity

The addition consumes those values and leaves the completed result:

(price × quantity) + tax

No temporary value needed a human-facing name.

No instruction had to say where the intermediate product was stored.

The order of the postfix sequence and the rule of the stack preserved the expression’s structure together.

This is why a stack-based virtual machine is such a convenient destination for a compiler.

6. Walking the tree after its children

The parser recognized a multiplication node with two children:

multiplication
├── price
└── quantity

The code generator can process it in this order:

Generate code for price.
Generate code for quantity.
Generate code for multiplication.

For the larger addition:

addition
├── multiplication
│   ├── price
│   └── quantity
└── tax

the generator visits both children before emitting the parent operation:

push price
push quantity
multiply
push tax
add

This traversal is called postorder because the operation associated with a node appears after the work for its children.

The source expression was arranged for a human reader.

The generated sequence is arranged for a stack.

Both preserve the same operational relationship:

Multiply these two values.
Then add this third value.

The code generator retells spatial structure as temporal events.

7. The tree does not have to remain a tree

It is useful to imagine the parser building a tree and the code generator walking it later.

Many compilers do preserve an abstract syntax tree in memory. The tree can support analysis, optimization, error reporting, and several later passes.

The Jack compiler in Nand to Tetris can take a more direct route.

Its recursive-descent parser already visits the program in grammatical order. Instead of emitting XML tags when it recognizes a structure, it can emit VM commands.

Earlier compileExpression:
    recognize expression
    write XML describing it

Later compileExpression:
    recognize expression
    write VM commands performing it

The tree may remain conceptual rather than becoming a permanent object.

The recursive calls still follow its branches. The generated commands still reflect its relationships. The compiler simply produces the new representation while the structure is being recognized.

This is another example of abstraction without one required material form.

What matters is the relationship preserved, not whether a box labeled syntax tree exists in memory.

8. The compiler’s notebook of identities

Before an identifier can become a VM command, the compiler must know what role the name plays.

It keeps those relationships in a symbol table.

For one class, part of the table might contain:

Name        Kind       Type       Index
---------------------------------------
tax         field      int          2
orders      static     int          0

For one method, another part might contain:

Name        Kind       Type       Index
---------------------------------------
price       argument   int          0
quantity    var        int          1
total       var        int          0

The kind determines the VM segment:

static   → static
field    → this
argument → argument
var      → local

The index determines the location within that segment.

The type helps distinguish an object variable from a class name when the identifier appears before a dot.

When the compiler sees tax, it can now emit:

push this 2

When it sees quantity, it can emit:

push local 1

The source name disappears.

Its runtime relationship remains.

9. One name, many locations

The symbol table does not assign every variable one permanent RAM address.

It records a role relative to the active world.

local 1

means:

The second local value belonging to the current invocation.

If a function calls itself, several invocations may each possess a variable with the same source name and the same local index.

Their stack frames keep the physical values separate.

The compiler can therefore translate the name consistently without knowing the final RAM address used during every call.

This is a hidden collaboration between compiler and virtual machine:

The compiler preserves the variable’s relative role.
The VM calling convention preserves the active frame.
The stack preserves separate physical lives.

A name becomes executable because several layers agree on what its category and index mean.

10. Assignment becomes movement

For an ordinary assignment:

let total = (price * quantity) + tax;

the generator first emits commands that leave the expression’s value on top of the stack.

Then it removes the value into the destination resolved by the symbol table:

push argument 0
push local 1
call Math.multiply 2
push this 2
add
pop local 0

The word let has produced no single VM instruction.

Its meaning appears across the arrangement:

Calculate this expression.
Place its result in this variable’s runtime location.

The compiler preserves the assignment even though the assignment sign itself disappears.

11. A loop acquires geography

Source code expresses a loop structurally:

while (count < limit) {
    let count = count + 1;
}

The VM language has no command meaning while.

It has labels, comparisons, conditional jumps, and unconditional jumps.

The generator must invent locations:

label WHILE_TEST_4

push local 0
push argument 0
lt
not
if-goto WHILE_END_4

push local 0
push constant 1
add
pop local 0

goto WHILE_TEST_4
label WHILE_END_4

The source supplies the relationships:

This is the condition.
This block repeats while it remains true.
Execution continues after the loop when it becomes false.

The generator supplies the geography required to enact them.

Every loop needs unique labels so that its jumps do not enter another loop. The label names are not part of the programmer’s idea. They are private landmarks invented by the compiler.

12. The argument the programmer never wrote

Return to:

do square.moveRight();

The symbol table reveals that square is a variable whose type is Square.

The call is therefore not merely:

Run Square.moveRight.

It means:

Run Square.moveRight using this particular Square object.

The generator pushes the object’s address before any written arguments:

push local 2
call Square.moveRight 1

The VM call reports one argument even though the source contains empty parentheses.

That argument is the object itself.

At the beginning of the method, generated code makes the first argument the current this reference:

push argument 0
pop pointer 0

Now a field access such as:

let x = x + 2;

can use the this segment:

push this 0
push constant 2
add
pop this 0

The dot in the source has become a calling convention.

13. A constructor creates the world it needs

A method receives an existing object.

A constructor must create one.

Suppose a class declares three fields:

field int x;
field int y;
field int size;

The compiler’s symbol table can count them.

At the beginning of a constructor, generated code requests three words of memory:

push constant 3
call Memory.alloc 1
pop pointer 0

Memory.alloc returns the beginning address of a region large enough for the fields. Setting pointer 0 makes that address the current this base.

Afterward:

this 0 → x
this 1 → y
this 2 → size

The source language made an object look like a thing with named properties.

The code generator turns that promise into allocation, a base address, and offsets.

An object begins as memory that several pieces of software agree to interpret together.

14. The array value that must wait

An array assignment hides a more delicate sequence:

let values[index] = total;

The destination is not one fixed symbol-table location. The compiler must calculate it:

address of values
        +
value of index
        ↓
address of the selected element

It must also preserve total while arranging that address for the VM’s that segment.

A translation may:

Calculate the element address.
Calculate the value being assigned.
Temporarily save the value.
Make the element address the base of that.
Restore the value.
Pop it into that 0.

The temporary segment becomes a small waiting room.

The source presents one assignment.

The generated code coordinates two calculations whose results must meet in the correct order.

15. The string that must be built at runtime

Source code can contain a string as though it already exists:

"order complete"

The Hack machine has no native string literal.

It has sixteen-bit values and memory.

The compiler must turn the apparent object into a construction process.

It can first request a string with enough capacity:

push constant 14
call String.new 1

Then, for each character, it can push the character’s numerical code and call a routine that appends it:

push constant 111
call String.appendChar 2

push constant 114
call String.appendChar 2

...

What appeared static in the source becomes a sequence through time.

The quotation marks disappear.

Their promise survives as allocated memory containing an ordered series of character values.

16. The compiler becomes the suspect

Ordinarily, when a compiled program behaves incorrectly, a programmer first suspects the source.

The code-generation project in Nand to Tetris reverses that assumption.

Its supplied Jack programs are intended to be correct. If one behaves incorrectly after translation, the compiler is the part under investigation.

That shift reveals the compiler’s responsibility.

The source may be valid.

The parser may recover the correct structure.

The generated VM code may still:

push variables from the wrong segment;
reverse two operands;
reuse a label;
forget the object argument;
miscalculate an array address;
or leave an unwanted value on the stack.

Every one of those failures breaks the language’s promise.

The user wrote one permitted description. The compiler caused another behavior.

Translation is trustworthy only when the relationship survives.

17. From seven to Pong

The project tests code generation by increasing what the compiler must preserve.

The first program calculates:

(3 * 2) + 1

If the compiler is correct, the number 7 appears on the screen.

Later programs add variables, branches, functions, objects, methods, arrays, and strings.

Eventually the compiler translates Pong.

A ball moves.

A paddle responds to the keyboard.

Collisions change direction.

A score appears.

The game is a stronger test than comparing XML tags. Many generated agreements must survive together across thousands of VM commands.

Expression order
Variable identity
Object layout
Method calls
Control flow
Array addressing
String construction

The visible motion is evidence that invisible translations remained consistent.

The tree has become time, and time has become play.

18. What code generation really is

A code generator is often defined as the part of a compiler that produces target instructions.

That is correct.

But it can sound as though the output were merely a reformatted version of the source.

Code generation turns relationships into ordered effects:

Expression structure → stack order
Variable role        → segment and index
Assignment           → evaluation followed by storage
Loop or condition    → labels and jumps
Object ownership     → an implicit argument
Fields               → offsets from this
Constructor          → memory allocation
Array access         → address calculation
String literal       → runtime construction

The source and the VM code do not look alike.

They do not contain the same number of operations.

They do not name all the same intermediate things.

What they must preserve is operational meaning.

Given the same starting state,
the generated program must produce the behavior promised by the source.

The compiler does not know what an order means to a shopkeeper or what a square means to a player.

It understands a narrower world of variables, expressions, calls, objects, and control flow. Within that world, it connects two precise stories:

The program as people are allowed to describe it
                        ↓
The program as the virtual machine can perform it

The Jack compiler is now complete.

But its generated code repeatedly asks for services:

call Math.multiply
call Memory.alloc
call String.new
call Screen.drawRectangle
call Keyboard.keyPressed
call Output.printInt

The compiler can produce those requests.

The virtual machine can carry out the calling protocol.

Neither fact makes the requested service exist.

Some software must know how to multiply when the hardware cannot, how to find unused memory, how to represent a string, how to alter screen pixels, and how to turn keyboard state into a value a program can use.

The completed compiler has revealed another unfinished layer.

The next question is no longer how a high-level program becomes executable instructions.

It is who fulfills the promises those instructions assume.

How can software learn to serve every program?