NCL 401: The Value Stack

So far, whenever we wanted to keep a value around, we put it in a register.

That works well when the value has a clear purpose and deserves its own register.

Sometimes, though, we only need to put a value aside for a moment.

Suppose we want to temporarily reuse r0:

MOVE r0 42
MOVE r1 r0

MOVE r0 100
D.TXT r0

MOVE r0 r1
D.TXT r0
D.BLT

This works.

r1 is acting as temporary storage while we use r0 for something else.

NCL gives us another place to store temporary values: the value stack.

Pushing a Value

The PUSH instruction places a value onto the value stack.

PUSH <value>

For example:

MOVE r0 42
PUSH r0

This copies the current value of r0 onto the stack.

It does not change r0.

We can now overwrite the register without losing the value we pushed:

MOVE r0 42
PUSH r0

MOVE r0 100

At this point, r0 contains 100, while the stack still contains 42.

Popping a Value

The POP instruction removes the most recently pushed value and stores it in a destination register.

POP <dst>

For example:

MOVE r0 42
PUSH r0

MOVE r0 100
POP r0

After the POP, r0 contains 42 again.

Unlike reading a register, POP removes the value from the stack.

We can rewrite our earlier example without using r1 as temporary storage:

MOVE r0 42
PUSH r0

MOVE r0 100
D.TXT r0

POP r0
D.TXT r0
D.BLT

The stack lets us put a value aside, use the register for something else, then recover the original value later.

Last In, First Out

The value stack can hold more than one value.

Consider:

PUSH 10
PUSH 20
PUSH 30

POP r0
POP r1
POP r2

We can trace the stack as each instruction executes.

In this table, the top of the stack is on the right.

Instruction	Value stack	`r0`	`r1`	`r2`
`PUSH 10`	`10`	—	—	—
`PUSH 20`	`10, 20`	—	—	—
`PUSH 30`	`10, 20, 30`	—	—	—
`POP r0`	`10, 20`	30	—	—
`POP r1`	`10`	30	20	—
`POP r2`	empty	30	20	10

Notice the order.

10 was pushed first, but popped last.

30 was pushed last, but popped first.

This is called last in, first out, usually shortened to LIFO.

The most recently pushed value is called the top of the stack.

PUSH adds a value to the top.

POP removes the value from the top.

Using the Stack as Temporary Storage

LIFO behavior is especially useful when several temporary values need to be preserved.

For example:

MOVE r0 5
PUSH r0

MUL r0 r0 4
PUSH r0

ADD r0 r0 3
D.TXT r0
D.TXT " "

POP r0
D.TXT r0
D.TXT " "

POP r0
D.TXT r0
D.BLT

The values change like this:

5
20
23

Then the stack restores the earlier values in reverse order:

23 20 5

Each PUSH remembers a value.

Each POP returns to the most recently remembered one.

Building a Register Swap

Suppose two registers contain:

MOVE r0 10
MOVE r1 20

We want to exchange their values so that:

r0 = 20
r1 = 10

Using only MOVE, we need a third register to hold one value temporarily:

MOVE r2 r0
MOVE r0 r1
MOVE r1 r2

Instruction	`r0`	`r1`	`r2`
Before	10	20	—
`MOVE r2 r0`	10	20	10
`MOVE r0 r1`	20	20	10
`MOVE r1 r2`	20	10	10

Now that we have the value stack, we can avoid using a scratch register:

PUSH r0
MOVE r0 r1
POP r1

The stack temporarily holds the original value of r0.

Instruction	Value stack	`r0`	`r1`
Before	empty	10	20
`PUSH r0`	`10`	10	20
`MOVE r0 r1`	`10`	20	20
`POP r1`	empty	20	10

This is already useful: temporary storage no longer needs to occupy another register.

Swapping two registers is common enough that NCL also provides a direct instruction:

SWAP r0 r1

This exchanges the values in the two registers in a single instruction.

So we now know three ways to perform the same operation:

Method	Instructions	Scratch register required
Three `MOVE`s	3	Yes
`PUSH`, `MOVE`, `POP`	3	No
`SWAP`	1	No

The more specialized instruction does not give the processor a fundamentally new ability.

It gives a useful operation a direct name.

Keeping the Stack Balanced

When the value stack is being used for temporary storage, values pushed onto it should eventually be removed again.

For example:

PUSH 10
PUSH 20

POP r0

After this code runs, 20 has been popped into r0, but 10 is still on the stack.

Nothing automatically removes it.

If code repeatedly pushes more values than it pops, values continue accumulating on the stack.

A section of code that restores the stack to the state it had before is often described as being balanced.

For example:

PUSH r0
PUSH r1

POP r1
POP r0

adds two values, then removes two values.

The stack ends exactly as it began.

Stack Limits

The NCS/e value stack can hold up to 128 values.

Trying to push another value when all 128 positions are occupied is called stack overflow.

Trying to pop a value when the stack is empty is called stack underflow.

Both conditions cause a fatal STACK_ERROR.

Operation	Invalid condition	Result
`PUSH`	Value stack is full	Fatal `STACK_ERROR`
`POP`	Value stack is empty	Fatal `STACK_ERROR`

A stack error usually means that the program's pushes and pops do not match the way the program expects.

Try it

Start with:

MOVE r0 10
PUSH r0

ADD r0 r0 5
PUSH r0

MUL r0 r0 2

At this point:

r0 = 30

and two earlier values are waiting on the stack.

Using POP, D.TXT, and D.BLT, display:

30 15 10

Try tracing the stack before running the program.

PUSH and POP let us use the value stack without worrying about where its values are stored.

In the next lesson, NCL 402: Indexed Data, we'll look at how the processor keeps track of that storage — and what happens when we control it ourselves.