How Software Built a Machine: The Stack and the Virtual Machine

Planted 02026-08-01

Why invent another computer when we already have one?

Why invent an imaginary computer when we have already built a real one?

Why place another machine between a program and the processor that will ultimately execute it?

Assembly language gave people names for machine instructions. A programmer could write D=M+1 instead of remembering the sixteen bits that caused the Hack CPU to perform the same operation.

But the relief was limited.

The programmer still had to know the machine’s anatomy: its registers, instruction forms, addressing rules, and conventions for moving values through memory. A program written for Hack described Hack. Carry it to a processor with different registers or instructions, and the program no longer described a machine that existed.

The assembler had given human names to a physical computer.

The next layer would do something stranger.

It would give software a computer of its own.

1. The students waiting for the computer

In 1974, Kenneth Bowles returned to full-time teaching at the University of California, San Diego, after serving as director of the university’s computing center.

Computing education still revolved largely around shared mainframes. Students prepared programs, submitted them for batch processing, and waited for the central machine to reach their job. The delay separated writing from consequence. A student might make a small change and wait to discover what it actually did.

Bowles wanted students to work more directly. The emerging generation of microcomputers suggested a possibility: instead of competing for turns on one expensive machine, students might each interact with a smaller computer and revise their programs at their own pace.

But replacing one shared computer with many small ones exposed another problem.

The new machines did not all speak the same language.

A program prepared for one processor depended on that processor’s instruction set, registers, memory organization, and operating conventions. Another microcomputer might organize every one of those details differently. Giving students more computers threatened to divide their software into incompatible islands.

Bowles and a largely student-driven team developed the UCSD Pascal system around a portable intermediate language known as p-code. Pascal programs could be translated into p-code, while each physical computer supplied an implementation of the abstract p-machine that understood it. More than seventy students contributed to the project over time, writing system software, porting the environment, and distributing it to other institutions.

The strategy answered two human needs at once:

Give students direct access to small computers.
                    +
Keep their programs from belonging to only one of them.

The solution was not to erase the differences among processors.

It was to place a stable agreement above them.

2. The program that knew too much

Consider a small Hack assembly program:

@7
D=A
@5
D=D+A
@result
M=D

The program adds seven and five, then stores the result.

It also knows a surprising amount about its host.

It knows that Hack has an A register.

It knows that Hack has a D register.

It knows that M means the memory location whose address is currently held in A.

It knows how addition is written in Hack’s computation field.

It assumes that the assembler will turn result into a Hack RAM address.

This knowledge makes the program precise enough to execute.

It also makes the program dependent.

Move the source to a processor without A and D registers, and the names no longer refer to anything. Move it to a processor whose addition instruction accepts different operands, and D=D+A no longer describes a valid operation. Even when another machine can perform the same calculation, its path to the answer may be entirely different.

Assembly protected the programmer from binary encoding.

It did not protect the program from the architecture.

A portable layer would need to describe computation without borrowing the physical machine’s exact anatomy.

3. The multiplication of translators

Imagine three programming languages:

Language A
Language B
Language C

And three physical computers:

Machine X
Machine Y
Machine Z

If every language translates directly into every machine, the connections multiply:

A → X       B → X       C → X
A → Y       B → Y       C → Y
A → Z       B → Z       C → Z

Three languages and three machines require nine language–machine paths.

Add another language, and it needs support for every machine.

Add another processor, and every language needs a new way to target it.

The general problem grows like this:

Number of languages × Number of machines

Now place one intermediate machine between them:

Language A ─┐
Language B ─┼──→ Common intermediate machine
Language C ─┘

Common intermediate machine ──→ Machine X
                            ├──→ Machine Y
                            └──→ Machine Z

Each language learns to produce the intermediate form.

Each physical platform learns to implement the intermediate machine.

The work begins to resemble:

Number of languages + Number of machines

The intermediate machine is a treaty.

The languages above it agree on what commands they will produce.

The computers below it agree on what those commands must cause.

Neither side needs complete knowledge of the other.

4. The machine that was not in the room

Where is a virtual machine?

There may be no separate processor to point at.

No additional circuit board sits beside the Hack CPU. No hidden arithmetic unit performs virtual additions. No physical stack rises above the motherboard.

The virtual machine exists first as a specification:

these are its commands;
this is how its stack behaves;
these are its visible memory regions;
this is what each operation must leave behind.

A physical instruction such as Hack’s D=D+M has meaning because the CPU’s wiring responds to its encoded fields.

A virtual instruction such as add has meaning because some implementation—an interpreter, translator, or physical realization—preserves the behavior promised by the virtual-machine specification.

That behavior is not imaginary in the sense of being inconsequential.

After translation, real registers change. Real memory cells receive new bit patterns. Real gates switch according to the clock.

The virtual machine is abstract in its construction, but concrete in its effects.

A virtual machine is real as a behavior even when it is not real as a separate piece of hardware.

The Nand to Tetris VM is deliberately small. Its first stage supports stack-based arithmetic and logical commands, then adds push and pop operations for eight virtual memory segments. A translator turns each VM command into a sequence of Hack assembly instructions that accomplishes the same result.

The first question is why this invented machine performs its calculations using a stack.

5. The restriction that creates simplicity

A stack is a collection in which values are added and removed from one end.

Imagine a pile of plates.

A clean plate is placed on top.

The next plate is placed above it.

To remove one, you take the plate currently on top before reaching the plates beneath it.

A computational stack follows the same ordering rule:

Last value pushed
        ↓
First value popped

Suppose the stack contains:

Top →  5
       7
       2

Push eight:

Pop once, and eight is removed:

Top →  5
       7
       2

The stack restricts access. A command normally works with the values nearest the top rather than selecting any value anywhere.

That may appear less capable than a machine with many named registers.

But the restriction creates a simpler agreement.

An arithmetic command does not need to specify where every operand lives. The stack order already determines which values participate.

The top values become the machine’s immediate working set.

6. Addition without named registers

A stack program can add seven and five like this:

push constant 7
push constant 5
add

The stack changes step by step:

[]
      ↓ push constant 7
[7]
      ↓ push constant 5
[7, 5]
      ↓ add
[12]

The add command promises to:

remove the top value;
remove the value beneath it;
add them;
push the result.

The command does not identify a Hack register for seven.

It does not identify another register for five.

It does not explain which temporary location should preserve an operand while the other is retrieved.

It says only what must be true of the virtual stack before and after the operation:

Before: [..., x, y]
After:  [..., x + y]

The physical implementation may require many instructions.

The virtual program does not have to describe them.

This is the first major relief supplied by the stack:

The order of values can carry information that assembly would otherwise express through hardware-specific locations.

Longer expressions can be built from the same rule.

Consider:

(7 + 5) × 3

The first part of a stack-oriented representation is:

push constant 7
push constant 5
add
push constant 3

Those commands establish the important order:

[7]
[7, 5]
[12]
[12, 3]

The basic VM has no primitive multiplication command. A later routine could implement multiplication through simpler operations. The important point here is that the intermediate result waits on the stack until that later work needs it.

The program names neither a register nor a temporary RAM address.

7. The stack that does not physically grow

The plate metaphor is useful, but no physical tower rises inside the computer.

The translator represents the stack using ordinary Hack memory.

A stack pointer—conventionally called SP—records the address immediately above the current top value.

Suppose a region of RAM currently contains:

RAM[256] = 7
RAM[257] = 5
SP       = 258

The active stack contains the values in locations 256 and 257.

The pointer identifies the next available location.

To push a value:

Write the value into RAM[SP].
Increase SP.

To pop a value:

Decrease SP.
Read RAM[SP].

Nothing physically moves upward or downward.

The memory cells remain where they are.

The stack exists because the system consistently preserves two agreements:

Values below SP belong to the active stack.
SP identifies its current boundary.

The same physical RAM could be interpreted through another structure if different software maintained different relationships.

This repeats a pattern from earlier layers.

A variable was not a tiny box labeled counter; it was a name associated with an address.

A memory segment will not necessarily be a separate piece of memory; it will be a rule for locating values.

A stack is not a pile.

It is disciplined use of a region and a pointer.

8. One virtual command becomes many physical commands

The assembler usually converts one symbolic Hack instruction into one binary Hack instruction.

The VM translator does something different.

One virtual instruction may expand into many assembly instructions.

Consider:

push constant 7

To preserve its promised effect on Hack, the translated assembly must accomplish something like:

Load the number 7.
Find the RAM address stored in SP.
Write 7 into that location.
Increase SP.

Now consider:

add

The translation must accomplish something like:

Move SP toward the top operand.
Retrieve that operand.
Move toward the second operand.
Add the two values.
Store the result in the remaining stack position.
Leave SP just above the result.

The generated Hack instructions may mention SP, A, D, and M repeatedly.

The VM source mentions none of them.

The relationship is not:

One human symbol → one machine instruction

It is:

One abstract behavior
          ↓
Whatever sequence makes the host preserve that behavior

The translator is therefore freer than the assembler.

Its output need not resemble its input structurally.

It must resemble it consequentially.

Translation preserves what the program does, not necessarily how many steps it takes to do it.

9. The same program, another body

Suppose the stack program is:

push constant 7
push constant 5
add

On Hack, one translator may produce Hack assembly:

VM program
    ↓
Hack VM translator
    ↓
Hack assembly
    ↓
Hack machine code

A second computer may have different registers, different instructions, and a different representation of its stack pointer.

Its translator can produce an entirely different sequence:

Same VM program
      ↓
Translator for Machine Y
      ↓
Machine Y instructions

The two physical executions may share almost no low-level detail.

What they share is the visible result promised by the VM:

Before: []
After:  [12]

The virtual program is portable because its agreement is with the stack machine rather than directly with either processor.

The physical machines may disagree about:

register names;
instruction sizes;
available addressing modes;
how addition receives operands;
where the stack pointer is kept.

Those disagreements are confined below the VM boundary.

The virtual machine localizes disagreement.

The layers above it can remain stable while the implementation beneath it changes.

10. The segments that are not separate memories

A calculator could live entirely on a stack.

A larger program needs values that persist while other operations come and go.

The Nand to Tetris VM presents eight memory segments:

constant
local
argument
this
that
pointer
temp
static

Its basic translator supports commands such as:

push local 2
pop temp 4
push argument 0

Project 7 introduces these segments after the arithmetic commands, implementing the full family of push and pop operations in stages.

The names can make the segments sound like eight separate physical storage devices.

They are not.

They are eight addressing agreements presented by the virtual machine.

The constant segment is not stored memory at all. A command such as:

push constant 7

places the literal value seven on the stack.

The local, argument, this, and that segments are viewed relative to base addresses maintained by the running system.

A command such as:

push local 2

means conceptually:

Find the base of the current local segment.
Move two positions beyond it.
Read that value.
Push it onto the stack.

Other segments follow their own mapping rules.

The program sees a uniform command:

push segment index

The translator supplies the physical address calculation appropriate to that segment.

A virtual segment is therefore not defined primarily by where it sits.

It is defined by how a command locates it.

11. A location relative to a changing world

Assembly labels gave stable names to instruction addresses.

The VM introduces another form of distance from the hardware: locations relative to a current context.

Consider:

local 0
local 1
argument 0
argument 1

local 0 does not necessarily mean one permanent Hack RAM address.

It means:

The first value in whichever local region is active now.

If the local segment begins at one address, local 0 refers there.

If another computation later receives a different local region, the same VM command can refer somewhere else while preserving the same role.

This is a subtle transformation:

Fixed physical location
          ↓
Position relative to a named virtual region

The program can describe the relationship it needs rather than one permanent coordinate in memory.

The argument segment similarly prepares for values supplied to a reusable computation.

The full meaning of these changing regions will not become clear until functions enter the machine. For now, the important idea is that an address can be calculated from context rather than permanently embedded in the program.

The software becomes less dependent on where values happen to land.

12. The comparisons that rearrange the future

The basic VM supports more than arithmetic.

It also includes logical operations and comparisons such as:

and
or
not
eq
gt
lt

Like add, these commands consume values from the stack and push a result.

For example:

push constant 7
push constant 5
gt

asks whether seven is greater than five.

The translator may need to generate a small sequence of Hack assembly containing subtraction, labels, and jumps to determine which logical value should be pushed.

The VM programmer does not write those control paths each time.

They write:

gt

The translator recovers the machinery.

This is another form of compression.

A command can conceal not only several data movements but a temporary branching structure.

The stack receives the promised logical result, and later commands can use it without knowing how the host produced it.

Even at this early stage, the virtual instruction set is not merely renaming physical instructions.

It is defining larger units of behavior.

13. Executing an abstraction in two different ways

A virtual machine specification does not dictate one implementation strategy.

One system can interpret VM commands:

Read one VM command.
Perform the behavior it specifies.
Read the next command.

Another can translate the complete program into host instructions before execution:

Read the VM program.
Produce an equivalent host program.
Run the host program later.

Nand to Tetris supplies a VM emulator so learners can observe the intended behavior of VM programs. The project itself asks them to build a translator that emits Hack assembly, then test the generated assembly on the Hack CPU emulator.

The two routes look different:

VM commands ──→ VM emulator ──→ visible VM behavior

and:

VM commands ──→ translator ──→ Hack assembly ──→ Hack CPU

Yet both can honor the same virtual-machine contract.

The abstraction survives because its identity lies in the behavior visible to the program, not in the private route used to produce it.

One implementation may interpret every command.

Another may translate ahead of time.

Another system might translate portions only when execution reaches them.

The virtual machine remains stable while the strategy beneath it changes.

14. Bowles’s machine between machines

Return to Bowles and the UCSD students.

Their problem was not simply that microcomputers were small.

They were small in different ways.

The systems used processors such as Intel’s 8080 and Zilog’s Z80, and the UCSD Pascal environment had to fit within machines whose available memory could be measured in tens of kilobytes. Bowles’s team nevertheless built a programming language, operating environment, and collection of tools intended to travel across hardware platforms.

The p-machine supplied the stable target.

A Pascal compiler could produce p-code.

A new physical platform needed an implementation capable of enacting that p-code.

The same broad structure appears in Nand to Tetris:

Future high-level language
          ↓
VM commands
          ↓
Hack VM translator
          ↓
Hack assembly

The historical UCSD p-system and the educational Hack VM are not the same machine. Their commands, goals, and implementations differ.

What they share is a strategy:

Place a software-defined machine between the language people use and the processor that physically runs it.

The UCSD project became larger than Bowles alone. Graduate student Mark Overgaard and successive groups of undergraduates implemented components, ported the system, built tools, and helped distribute copies around the world. The project’s portability allowed institutions with different small computers to share a larger body of software and educational practice.

The virtual machine was not merely a technical convenience.

It helped turn incompatible hardware into a shared classroom.

15. The cost of the invented machine

An abstraction can remove work from the programmer without removing it from the system.

A VM command such as:

add

may expand into several Hack instructions.

A stack-oriented translation may move operands through memory that a skilled assembly programmer could keep in physical registers.

A general mapping may ignore a shortcut offered by one particular processor.

The imaginary machine can therefore cost:

execution time;
memory;
generated code size;
or access to hardware-specific capabilities.

The tradeoff can be expressed as tension:

Closer control of one physical machine
                 ↕
Portability and a simpler common model

Neither side wins every situation.

A performance-critical routine may benefit from knowledge of the actual processor.

An educational system serving many computers may benefit more from one portable target.

A compiler may value the ability to generate one intermediate language rather than many unrelated machine languages.

The virtual machine earns its place when separating the layers saves more complexity than the implementation adds.

It does not make hardware differences vanish.

It gives those differences fewer places to spread.

16. Software begins to resemble architecture

Until now, the word machine referred mainly to physical construction.

Relays, vacuum tubes, and transistors embodied logical rules.

Gates formed an ALU.

Registers formed memory.

The CPU turned instructions into state changes.

The VM introduces a second route to machinery:

Specify a set of behaviors.
Implement those behaviors using another computer.
Let programs rely on the specification.

A physical machine is built by arranging components until they fulfill an instruction-set promise.

A virtual machine is built by arranging software until the host fulfills another instruction-set promise.

Both establish a boundary.

Above the boundary, a program can behave as though the promised machine exists.

Below it, the implementation may be gates, assembly routines, an interpreter, or another chain of abstractions.

This is why the virtual machine is not merely a file format between two stages.

It is architecture expressed in software.

The programmer can reason about:

Push this value.
Push another.
Add them.
Store the result in a virtual segment.

Far below, the Hack processor still fetches binary instructions one at a time.

Both descriptions remain true.

17. What a virtual machine really is

A virtual machine is an agreement precise enough to behave like a computer.

Its promise might be written:

Give me these commands and this starting state.
I will produce the state required by the specification.

The complete descent remains available:

VM command
    ↓
Hack assembly
    ↓
Hack binary
    ↓
CPU control signals
    ↓
ALU, registers, and memory
    ↓
Changing electrical states

But a programmer working at the VM level can temporarily trust another story:

Push two values.
Add them.
Place the result in local storage.

The virtual machine is useful because the translator preserves the relationship between those stories.

The assembler had given human names to a physical machine.

The virtual machine gave software a machine of its own.

It also created a new kind of freedom.

A language could target the virtual machine without knowing which physical processor would eventually carry out its commands.

A processor could support the virtual machine without knowing which language had produced the program.

The intermediate layer connected them while allowing them to remain partly strangers.

But the new machine was still incomplete.

It could push values, perform arithmetic and logic, compare results, and move data through virtual memory segments.

It could evaluate an expression.

It could not yet safely leave one computation unfinished, enter another, and later return to the exact point it had abandoned.

A reusable function would need arguments.

It would need local values belonging only to that invocation.

It would need to remember where execution should resume.

If that function called another function, both unfinished computations would have to survive.

If it called itself, many versions of the same unfinished work would coexist.

The stack could hold numbers.

The next question was whether it could hold unfinished lives.