NCL 403: The Call Stack

We've been using subroutines since NCL 309.

A call looks like this:

CALL $draw_cell

And the subroutine eventually returns:

$draw_cell
...
RET

Before CALL and RET, we had to remember the return destination ourselves:

MOVE #return $after_draw
JUMP $draw_cell

$after_draw

The shared code could later return with:

JUMP #return

CALL and RET removed that bookkeeping from our program.

But there is an important question we haven't answered yet:

Where does CALL remember where to return?

Remembering the Return

When the processor executes:

CALL $work

it does two things:

Remembers where execution should continue afterward.
Jumps to $work.

When $work eventually executes:

RET

the processor retrieves that remembered destination and continues there.

For a single call, this might sound like it only requires one hidden value.

But we've already done something more interesting than that.

A subroutine can call another subroutine:

CALL $outer
D.TXT "Done"
D.BLT
JUMP 0

$outer
D.TXT "Outer "
CALL $inner
D.TXT "Again "
RET

$inner
D.TXT "Inner "
RET

The display eventually shows:

Outer Inner Again Done

When the program calls $outer, the processor remembers where the main program should continue.

Then $outer calls $inner.

The processor can't forget the first return destination. $inner needs somewhere to return, but $outer still needs to return afterward too.

There are now two return destinations waiting.

That should sound familiar.

The Call Stack

NCL maintains a second stack called the call stack.

It is separate from the value stack we used in the previous two lessons.

Value stack	Call stack
Stores program values	Stores return destinations
Used by `PUSH` and `POP`	Used by `CALL` and `RET`
Accessible through `sp` and `sv`	Not directly accessible
128 positions	16 positions

Each CALL places a return destination on the call stack.

Each RET removes the most recent return destination and continues execution there.

For our nested example:

Event	Pending returns
Program starts	none
Main program calls `$outer`	main program
`$outer` calls `$inner`	main program, `$outer`
`$inner` executes `RET`	main program
`$outer` executes `RET`	none

Just like the value stack, the call stack is last in, first out.

The most recent call returns first.

That is exactly what nested subroutines need.

Return Obligations

It can be useful to think of each CALL as creating a return obligation.

When we write:

CALL $work

we are saying:

Run $work, then come back here.

That pending return stays on the call stack until RET fulfills it:

$work
...
RET

So:

CALL creates a return obligation. RET fulfills it.

This works no matter how many subroutines are nested, as long as the call stack has room.

Calling Yourself

A subroutine can call another subroutine.

There is no requirement that it has to be a different subroutine.

A subroutine can call itself.

This is called recursion.

Here's a recursive countdown:

MOVE r0 5
CALL $count
JUMP 0

$count
D.TXT r0
D.TXT " "

DEC r0
BEQ $done r0 0

CALL $count

$done
RET

The display shows:

5 4 3 2 1

Let's follow what happens.

The first call enters $count with r0 containing 5.

It displays 5, decreases r0 to 4, and then calls $count again.

That new invocation displays 4, decreases the value again, and calls $count again.

Each recursive call creates another pending return:

`r0` when `$count` is entered	Pending returns
5	1
4	2
3	3
2	4
1	5

When r0 reaches 0, the branch skips the next recursive call and reaches:

RET

That fulfills the most recent return obligation.

Execution returns to the previous invocation of $count, which has also reached its own RET.

That return takes us to the one before it.

The calls now unwind in reverse order until the original call has returned.

The Base Case

A recursive subroutine needs some condition that eventually stops it from calling itself.

This is commonly called its base case.

In our countdown, this is the base case:

BEQ $done r0 0

Once r0 reaches zero, the subroutine stops making new calls and begins returning through the calls that are already waiting.

Without a base case, recursion can continue until the call stack runs out of room.

For example:

$again
CALL $again
RET

The RET is never reached.

Every call to $again calls $again again first, creating another pending return.

The call stack can hold 16 return destinations. Attempting another CALL when all 16 positions are occupied causes a fatal STACK_ERROR.

Our countdown could be written more simply as a loop. We're using recursion here because its behavior is easy to follow.

Recursion becomes particularly useful when a problem naturally contains smaller versions of itself. It can make some otherwise complicated problems surprisingly direct.

But each recursive call consumes another position on the call stack. With 16 positions available, recursion in NCL is best suited to problems with a naturally limited depth. When work might repeat many times, a loop or another iterative approach will often scale better.

Call Stack Errors

The call stack can contain up to 16 return destinations.

Operation	Invalid condition	Result
`CALL`	Call stack is full	Fatal `STACK_ERROR`
`RET`	Call stack is empty	Fatal `STACK_ERROR`

The value stack and call stack are separate. Filling one does not consume positions from the other.

They simply share some familiar behavior: both are last in, first out, and both produce a STACK_ERROR when an operation cannot be completed.

Try it

Write three subroutines named $one, $two, and $three.

Arrange their calls so that this:

D.TXT "START "
CALL $one
D.TXT "DONE"
D.BLT

produces:

START ONE TWO THREE TWO AGAIN ONE AGAIN DONE

Each subroutine should display its first message before calling the next subroutine and its second message after that call returns.

$three does not need to call another subroutine.

Follow the pending return destinations as the program runs. Notice that the calls build inward:

$one
$two
$three

and the returns unwind outward:

$three
$two
$one

CALL and RET give subroutines their own way to remember where execution came from.

Our subroutines still need an agreed place to exchange values with their callers, though. So far, we've mostly reserved particular registers for that job.

In the next lesson, NCL 404: Passing Values to Subroutines, we'll use the value stack to pass values into subroutines and bring results back out.