How a Machine Learned to Return: Functions and the Call Stack

Planted 02026-08-01

How can a machine preserve an unfinished world?

How can a machine leave one calculation unfinished, perform another, and return to the exact point it abandoned?

How can the same function be active several times at once without one invocation destroying the others?

The virtual machine gave software a computer of its own. A program could push values onto a stack, combine them, compare them, and move them through virtual memory segments without deciding which physical registers or RAM addresses performed every step.

But the machine still followed one continuous thread:

Do this.
Then this.
Then this.

A large program needs reusable parts.

One part must be able to ask another part to perform some work:

Calculate this value for me.
Then come back.

The request sounds simple because human language hides what must be preserved.

Where should execution resume?

Which values belong to the caller?

Where should the called function find its arguments?

Where should it keep its local variables?

What happens if it calls another function before returning?

What happens if it calls itself?

A function call does not merely send the machine somewhere else.

It preserves an unfinished world.

1. The routine no one wanted to copy again

When EDSAC began providing a computing service at the University of Cambridge, programmers repeatedly needed the same kinds of mathematical work.

A researcher might require a routine for division, trigonometric functions, numerical integration, or formatted output. Another researcher might need the same routine the following week.

The obvious solution was to copy the required instructions into every new program.

That worked, but it created several costs:

Every copy consumed scarce memory.
Every copy could contain a new mistake.
Every correction had to reach every copy.
Every programmer had to understand work already solved by someone else.

David Wheeler, a research student working with Maurice Wilkes’s group, helped develop another approach. Cambridge’s historical records credit Wheeler with the closed subroutine and with refining the Initial Orders that loaded and prepared EDSAC programs. The laboratory also began building a shared library of routines that other programmers could use.

A subroutine is a sequence of instructions written to perform a reusable task.

Instead of copying the task everywhere:

Program A
  ↓
Copy of routine

Program B
  ↓
Another copy of routine

Program C
  ↓
Another copy of routine

several callers could enter one shared sequence:

Caller A ─┐
Caller B ─┼──→ Shared routine
Caller C ─┘

The memory savings mattered.

The intellectual savings mattered too.

A tested routine could become part of the laboratory’s common infrastructure. One person’s difficult work could become another person’s dependable building block.

But the shared routine created a problem that a copied routine did not.

A copy already sits inside the caller’s path. When it finishes, execution naturally reaches the instruction that follows it.

A shared routine may be entered from many places.

When it finishes, how does it know where to go back?

2. The jump that could not return

The CPU already knows how to jump.

Ordinarily, the program counter advances:

42 → 43 → 44 → 45

A jump replaces that ordinary future:

42 → 200

Suppose instruction 42 asks the machine to use a multiplication routine beginning at address 200.

Jumping into the routine is easy:

Program counter = 200

But the caller was not finished.

Instruction 43 still matters. It is the place where the caller expects to continue after multiplication.

The routine cannot simply end with:

Jump to 43.

That would work only when called from instruction 42.

Another part of the program might call the same routine from instruction 91 and expect to resume at 92.

A third caller might expect to resume at 318.

The shared routine cannot contain one permanent return destination because its caller is not permanent.

The machine must preserve a value that changes with every call:

The address of the instruction immediately after this particular call.

That value is the return address.

The call is no longer merely:

Jump to the routine.

It becomes:

Remember where the caller should resume.
Jump to the routine.

And the routine’s ending becomes:

Recover the remembered address.
Place it in the program counter.

A reusable subroutine therefore requires two transfers of control:

Caller ──→ Callee
Caller ←── Callee

The first transfer is known when the call is written.

The second depends on where the call came from.

3. The caller leaves a note for its future self

Imagine this sequence:

Instruction 42: call multiply
Instruction 43: use the answer

Before leaving, the caller must preserve 43.

A modern assembly language might provide a dedicated call instruction that automatically saves the following address. Early systems developed their own mechanisms. Wheeler’s work on EDSAC became associated with the “Wheeler jump,” a calling technique for closed subroutines; Cambridge continues to credit him with pioneering that reusable form.

The Nand to Tetris virtual machine makes the agreement explicit.

A command such as:

call Math.multiply 2

must eventually produce host instructions that invent and preserve a unique return point.

Conceptually, the translator can generate:

Push the address of RETURN_17.
Prepare the function’s environment.
Jump to Math.multiply.

(RETURN_17)
Continue the caller.

The label RETURN_17 exists for the generated program. Another call receives another return label.

The return address is a message placed into memory for a later version of the machine:

When the borrowed computation finishes, resume here.

The bit pattern itself does not know that it represents a return.

While stored, it resembles any other number.

It becomes a return address because the call protocol saves it in the expected place and the return protocol eventually loads it into the program counter.

The meaning belongs to the agreement.

4. Why one return slot is not enough

The first design might reserve one fixed location:

RETURN_ADDRESS

Before calling a function, the machine writes the return address there.

The function finishes, reads the location, and returns.

For one level of calling, this works.

Then the function calls another function.

Suppose A calls B:

RETURN_ADDRESS = address inside A

Before B finishes, it calls C.

C needs its own return address:

RETURN_ADDRESS = address inside B

The second write destroys the first.

C can return to B.

But after B finishes, the address needed to return to A is gone.

The problem grows with every nested call:

A waits for B.
B waits for C.
C waits for D.

Each caller has left behind a different unfinished future.

One storage location cannot preserve them all.

We could assign every possible calling depth a separate return slot:

RETURN_1
RETURN_2
RETURN_3
...

But then the program must know in advance how deeply calls will nest.

A reusable function cannot safely assume that it will be called only at depth three, or ten, or one hundred.

The return destinations need a structure that can grow as calls occur and shrink as they finish.

They also have a useful order.

D was called last, so D must return first.

Then C can resume.

Then B.

Then A.

Last caller suspended
          ↓
First caller restored

That is exactly the order of a stack.

5. The stack finds a second purpose

The virtual machine already uses a stack for arithmetic.

To add two numbers:

push constant 7
push constant 5
add

the machine removes the two newest values and replaces them with their sum.

Function calls use the same last-in, first-out structure for a deeper purpose.

Each call places information needed for its eventual return.

Each return removes the information belonging to the most recent unfinished call.

Conceptually:

Return to A
Return to B
Return to C  ← newest

When C finishes, its return information is removed.

B’s information becomes the newest again.

The stack does not need to search for the correct caller. The history of calling has already arranged the callers in the order they must be restored.

This is why function calls and stacks fit one another so naturally:

Calls nest.
Returns unwind.

But a return address is only one piece of the caller’s unfinished world.

The caller may also be using local variables, argument locations, object-related memory segments, and temporary values.

If the callee takes over those structures without preserving them, returning to the right instruction will not be enough.

The caller will arrive home to find that its world has changed beyond recognition.

6. The context a caller cannot afford to lose

In the Nand to Tetris virtual machine, several pointers define the active program context:

LCL   → base of the current local segment
ARG   → base of the current argument segment
THIS  → base of the current this segment
THAT  → base of the current that segment

The caller may depend on all four.

A called function needs a local segment of its own.

It needs an argument segment identifying the values supplied for this call.

It may alter THIS or THAT while working with objects or arrays.

If it simply overwrites the caller’s pointers, the caller will no longer know where its own values live after the return.

The calling protocol therefore saves more than the return address.

Before transferring control, the Hack VM call implementation preserves:

Return address
LCL
ARG
THIS
THAT

Project 8 of Nand to Tetris extends the VM translator with program-flow commands and the complete function-calling protocol. Its tests deliberately exercise simple functions, nested calls, recursive Fibonacci, bootstrap initialization, and programs spread across several VM files.

The larger principle is:

Calling a function means saving enough of the present that the present can be reconstructed later.

The caller does not know how long the callee will run.

It does not know how many other functions the callee will call.

It does not know how much temporary state will accumulate above it.

It trusts the protocol to preserve the boundary between their worlds.

7. The stack frame: one invocation’s temporary world

The group of values associated with one active function call is commonly called a stack frame or activation record.

A simplified frame may include:

Arguments
Return address
Saved caller pointers
Local variables
Temporary expression values

The exact layout varies among systems.

The important property is not one universal diagram. It is separation:

The state belonging to this invocation must remain distinguishable from the state belonging to every other active invocation.

Suppose A calls B, and B calls C.

The runtime stack can be imagined as:

Older
┌─────────────────────┐
│ Frame for A         │
├─────────────────────┤
│ Frame for B         │
├─────────────────────┤
│ Frame for C         │ ← active
└─────────────────────┘
Newer

A’s code still exists in instruction memory.

Its execution has merely stopped at a call.

Its frame preserves what must survive while B works.

B is similarly suspended while C works.

Only C is currently active, but A and B remain present as obligations.

When C returns, C’s frame is dismantled.

B’s frame becomes active again.

The machine does not recreate B by rerunning it from the beginning. It restores the context B left behind.

A frame is therefore more than a region of storage.

It is a paused moment made recoverable.

8. Arguments cross into another world

A caller invokes a function because it wants work performed on particular values.

Suppose the VM program asks a function to add seven and five:

push constant 7
push constant 5
call Math.add 2

The final 2 says that two arguments have been placed on the stack.

Before the call, the top of the stack contains:

[..., 7, 5]

The calling protocol establishes the callee’s ARG pointer so that the function can refer to those values through its virtual argument segment:

argument 0 → 7
argument 1 → 5

The function does not need to know their absolute Hack RAM addresses.

It does not need to know how much caller state was placed above or below them.

It trusts the runtime agreement:

argument 0

means:

The first argument belonging to the active invocation.

This fulfills a promise made when virtual memory segments were introduced.

argument 0 is not one permanent cell.

Its physical address depends on the current frame.

The name remains stable while the location changes.

That stability makes one function body reusable:

function Math.add
    push argument 0
    push argument 1
    add
    return

Every call supplies different values.

The function uses the same relative names.

9. Local variables belong to a call, not merely to code

A function may also require private working values.

In the VM language, a declaration such as:

function Example.work 3

says that this function begins with three local variables.

Conceptually:

local 0
local 1
local 2

The function command creates and initializes storage for those locals when the function is entered.

The crucial phrase is when the function is entered.

Local variables do not belong only to the function’s written definition.

They belong to one active invocation of that definition.

Call the function once:

Invocation 1:
    local 0
    local 1
    local 2

Call it again before the first call returns:

Invocation 2:
    local 0
    local 1
    local 2

The names are the same.

The storage must be different.

Otherwise the newer invocation would overwrite the older invocation’s unfinished work.

This distinction between code and activation is easy to miss because source code normally shows the function only once.

At runtime:

One function definition
          ↓
Many possible active invocations
          ↓
One private frame for each

The code describes a repeatable kind of work.

The frame preserves one occurrence of that work.

10. Entering the callee

A VM call command must prepare the new function before jumping to it.

Conceptually, the protocol performs several acts:

1. Save a unique return address.
2. Save the caller’s LCL, ARG, THIS, and THAT.
3. Reposition ARG around the supplied arguments.
4. Set LCL to the top of the new frame.
5. Jump to the function.

The arithmetic hidden in these steps matters.

By the time the call begins, the stack contains the arguments.

The call then pushes five saved values:

Return address
LCL
ARG
THIS
THAT

To find the beginning of the callee’s arguments, the translator must account for both the number of supplied arguments and the five saved values.

Conceptually:

ARG = SP - number_of_arguments - 5

Then:

LCL = SP

marks the beginning of the callee’s local region.

These details can seem like arbitrary bookkeeping.

Narratively, each one protects a boundary:

ARG lets the callee see the values meant for it.
LCL gives the callee private working space.
the saved pointers preserve the caller’s interpretation of memory.
the return address preserves the caller’s future.

The protocol builds a temporary world before control enters it.

11. Returning is careful reconstruction

A call creates a frame.

A return must dismantle it.

The function has finished. Its return value is at the top of the stack.

But the caller expects the result to replace the arguments it supplied, and the caller’s saved state is buried inside the frame that is about to disappear.

The return protocol must conceptually:

1. Remember where the current frame begins.
2. Recover the saved return address.
3. Move the return value into the caller’s expected position.
4. Restore the caller’s stack pointer.
5. Restore THAT, THIS, ARG, and LCL.
6. Jump to the saved return address.

The order is delicate.

Suppose the implementation restores LCL before using it to find the saved return address.

The map to the current frame may disappear before the machine has recovered everything it needs.

The runtime therefore commonly preserves temporary references such as:

FRAME = LCL
RET   = *(FRAME - 5)

before dismantling the frame.

Then it can restore the saved segments in reverse order.

This reversal mirrors the stack itself:

Call:
    build a new world above the caller

Return:
    remove the new world and expose the caller beneath

The caller experiences the entire excursion almost as if one larger operation occurred.

It pushes arguments.

Later, one return value remains.

Everything in between has been hidden behind the function boundary.

12. The value that crosses back

Suppose the caller begins with:

[..., 7, 5]

and executes:

call Math.add 2

The function computes twelve and leaves it on top of its active stack.

During return, the runtime places twelve where the caller’s first argument began.

The arguments and callee frame are discarded.

The caller resumes with:

[..., 12]

This is an important illusion.

The caller can reason as though:

Two arguments went into the function.
One result came back.

Below that description, the machine:

generated a return label;
saved five pieces of caller context;
repositioned pointers;
created locals;
executed another instruction sequence;
retrieved a buried address;
restored four segments;
and changed the program counter.

Abstraction does not remove the work.

It gives the work a dependable shape.

The function’s promise is visible at the boundary:

Inputs supplied here.
Result returned here.

The frame machinery remains below.

13. Branches that belong to a function

Project 8 also adds VM commands for program flow:

label
goto
if-goto

A function can therefore contain loops and conditional paths:

label LOOP
    // work
    if-goto END
    goto LOOP
label END

Translation introduces a naming problem.

Two functions may both contain:

label LOOP

The labels mean different places.

If the translator emitted one global assembly label named LOOP, the functions would collide.

A common solution is to qualify a VM label with its function:

FunctionA$LOOP
FunctionB$LOOP

The programmer writes a simple local name.

The translator produces a globally unique host name.

This is the same division of labor seen in the assembler:

Programmer preserves local intention.
Translator preserves global uniqueness.

The function boundary affects not only variables and return addresses.

It also gives control-flow labels a scope.

The generated program can contain many loops named LOOP because the translator remembers which world each belongs to.

14. The function that calls itself

Nested calls already require several frames.

Recursion makes the reason unmistakable.

Consider factorial:

factorial(4)

Its definition can be expressed:

factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

The machine begins with one invocation:

factorial(4)

That invocation cannot finish until it knows:

factorial(3)

So it calls the same function again.

The new invocation cannot finish until it knows:

factorial(2)

Then:

factorial(1)

The source code exists once.

At runtime, several unfinished lives of that code coexist:

Frame: factorial(4)
    n = 4
    waiting to multiply by factorial(3)

Frame: factorial(3)
    n = 3
    waiting to multiply by factorial(2)

Frame: factorial(2)
    n = 2
    waiting to multiply by factorial(1)

Frame: factorial(1)
    n = 1
    ready to return

Each invocation needs its own n.

Each needs its own return address.

Each needs its own temporary values.

If they shared one set of locals, the newest call would destroy the older ones.

Frames give one function several simultaneous activations.

Then the returns unwind:

factorial(1) returns 1
factorial(2) resumes and returns 2
factorial(3) resumes and returns 6
factorial(4) resumes and returns 24

Recursion is not a function mysteriously existing inside itself.

It is ordinary calling repeated while earlier calls remain preserved.

15. The language promised what the runtime had to invent

By the late 1950s, language designers were pursuing forms of programming that described algorithms less directly in terms of one machine’s instruction sequence.

ALGOL 60 included recursive procedures: a procedure could call itself directly or through other procedures.

That linguistic freedom created an implementation problem.

How could several unfinished activations of the same procedure coexist?

Edsger Dijkstra later recalled working during 1959 on implementing recursion and consciously searching for a term that could serve as both noun and verb. He chose the Dutch stapel and stapelen, translated them as “stack” and “to stack,” and used the terminology in his 1960 paper “Recursive Programming.” He also later emphasized that he was one of many programmers developing stack ideas around that period, rather than the single origin of every stack use.

Dijkstra and J. A. Zonneveld were building an ALGOL 60 system for the Electrologica X1. Dijkstra remembered the compiler as the most ambitious implementation he had yet attempted. The X1 had only about 4,096 words of storage, so clarity and economy were not stylistic luxuries; uncontrolled runtime machinery could make the language impossible to realize on the available computer.

The language had made a promise:

A procedure may call itself.

The runtime had to construct a memory discipline capable of honoring it.

This is a recurring relationship between programming languages and implementations.

A language feature appears at the human level as an expressive possibility.

Below it, translators and runtime systems must invent machinery that makes the possibility dependable.

16. Text and activation are different things

Dijkstra later described recursion as forcing a distinction between the static procedure text and its dynamic activation—one written body versus one current “incarnation” of that body. Local variables are created for an activation and disappear when that activation ends, which is precisely what allows recursive procedures to be implemented using last-in, first-out storage.

This distinction is the conceptual center of the call stack.

The function text may say:

local total
local index

But during execution there may be several versions:

Invocation A:
    total = 12
    index = 3

Invocation B:
    total = 7
    index = 1

Invocation C:
    total = 0
    index = 0

The names come from one definition.

The values belong to separate activations.

The call stack preserves the dynamic instances that source text alone cannot show.

A useful way to see the layers is:

Function definition
    Describes a reusable pattern of work.

Function invocation
    One occurrence of that work.

Stack frame
    The stored state that keeps that occurrence distinct.

Confusing these layers makes recursion seem paradoxical.

Separating them makes recursion mechanical.

The same instructions can be entered again because the changing state does not live only inside the instructions.

It lives in frames.

17. Recursion stores deferred work

A recursive definition often appears elegant because it describes a large problem through smaller versions of itself.

Consider Fibonacci:

fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

The call fib(4) does not immediately produce an answer.

It produces obligations:

Need fib(3).
Need fib(2).
Later, add their results.

The active invocation preserves that unfinished addition while entering fib(3).

That call creates more obligations.

The stack becomes a record of deferred work.

Nand to Tetris uses a recursive Fibonacci program as one of the tests for the completed VM translator. The test depends on function calls, returns, bootstrap initialization, and translation across multiple VM files, forcing the implementation to preserve nested activations correctly.

The important insight is not that recursion is always the fastest way to calculate Fibonacci. It is that the runtime can support the semantics promised by recursive source code.

Each unfinished call waits.

Each base case begins an unwinding.

Each return resolves one deferred obligation.

The stack is therefore not only a history of where execution came from.

It is a history of what execution still owes.

18. The bootstrap: who calls the first function?

Once every function expects a caller, a circular question appears.

Who calls the first function?

A VM function expects:

a valid stack pointer;
the calling convention;
arguments in agreed positions;
saved state if a return will occur.

At physical startup, none of that virtual context exists automatically.

The completed Nand to Tetris translator emits bootstrap code.

Conceptually, it:

Set SP to the agreed beginning of the stack.
Call Sys.init.

Sys.init becomes the virtual program’s entry point.

Project 8 tests this initialization as part of its multi-file and recursive programs.

The bootstrap crosses the boundary between machines:

Raw Hack startup
        ↓
Host assembly establishes VM state
        ↓
The VM calling convention becomes valid
        ↓
Sys.init begins the virtual program

The virtual machine cannot invoke its first function until something beneath it has created the conditions under which “function” and “call” have meaning.

Every abstraction begins this way.

A lower layer performs enough work to make the higher layer’s promises true.

After that moment, programs above the boundary can usually forget how the beginning was arranged.

19. The stack pointer becomes a history pointer

In the previous essay, the stack pointer marked the boundary above the current values.

With function calls, its role becomes richer.

Below SP may lie:

arguments awaiting use;
saved return addresses;
preserved segment pointers;
local variables;
intermediate expression values;
several nested frames.

The stack pointer marks the edge of active computational history.

Moving it upward creates space for new values and new unfinished worlds.

Moving it downward removes work that has completed.

Nothing in RAM is physically labeled:

Caller
Callee
Return address
Local variable
Saved THAT

Those meanings come from position and protocol.

A word five places below a frame pointer becomes a return address because the calling convention put it there and the return convention retrieves it from there.

A value becomes local 2 because the active LCL pointer and the index identify it.

The structure remains invisible in the material.

It is made real through reliable relationships.

This is what software architecture increasingly becomes:

Meaning maintained by conventions that every participating part agrees to preserve.

20. The danger of an unfinished history

A call stack can grow only while memory remains available.

A recursive function with no reachable base case continues creating frames:

call
  call
    call
      call
        call
          ...

Eventually the stack reaches memory used for something else or exceeds the space the system can provide.

The abstraction fails physically.

This is stack overflow.

The failure reveals what the higher-level metaphor had hidden.

The function appeared able to call itself without limit.

The machine beneath it had finite memory.

The call stack is therefore both an expressive mechanism and a resource.

Every active invocation occupies space.

Every saved world has a cost.

Good narrative should preserve this limit because it prevents recursion from becoming magic. The machine can preserve unfinished work only by giving that work physical representation somewhere below.

No representation means no return.

21. What a function really is

A function is often defined as a named block of reusable code.

That definition describes the source.

At runtime, a function call is an agreement for creating, using, and dismantling a temporary world.

It has:

A return destination
Arguments supplied by the caller
Local values belonging to this invocation
A current point in the function’s instructions
Saved context needed by the caller
Possibly another unfinished call above it

The function’s code may exist once.

Its active lives may exist many times.

The calling convention makes those lives possible by deciding:

what the caller must save;
where arguments will appear;
how locals are created;
where a result will be left;
and how the caller will be restored.

The CPU does not understand any of those roles.

The stack pointer does not know that it marks unfinished history.

The return address does not know that it is a promise.

The frame does not know that it belongs to factorial rather than Fibonacci.

The meanings come from the protocol maintained by the translator and the running program.

A call places more than arguments on the stack.

It places a fragment of the future:

Resume here.
Restore these relationships.
Continue this unfinished work.

The called function receives a world of its own.

If it calls another function, its world becomes another unfinished layer.

If it calls itself, the same code acquires another life without destroying the earlier one.

Returning removes the newest world and restores the one beneath it.

The stack no longer holds only numbers.

It holds time.

The virtual machine can now support programs divided into reusable, nested, and recursive parts.

But someone still has to write those programs using stack commands, labels, virtual segments, and explicit calls.

A person must still translate an idea such as:

Find the total price of every item in the order.

into pushes, pops, branches, and VM function protocols.

The next question is no longer how one function can call another.

It is how people can describe an entire program without thinking about the stack at all.