Lets write a virtual machine.

Part 1 – Continued – The stack

The Stack
Before we get onto programming up our first virtual machine, there is one more feature of a CPU that I’d like to discuss, and that’s called the ‘Stack’. This is a feature which we’ll not need to understand initially, but will become critically important later on. You could be forgiven for skipping this page and returning later if you need to.

So what is this thing called the ‘Stack’?
Earlier we discussed the ‘program counter’ register. The program counter is a piece of memory inside the CPU which contains a number that represents a location in the ‘external’ memory, that-is, the memory device in our computer system. Well, most CPU’s will also have a stack register, and it’s pretty much the same thing. The stack register, often referred to as a stack pointer, ‘points’ to a location in the memory device. The way that the stack pointer differs however, is in the way that it behaves.

The program counter behaved as an index, and with each clock pulse of the CPU it would increment through memory to the next instruction. The stack pointer on the other hand, can move forwards or backwards through memory, and rather than progressing on every clock pulse, it is incremented or decremented by some additional CPU instructions.

It should be no surprise that no real CPU is so limited as the one in our model, with only three instructions our imaginary CPU isn’t actually very useful at all. Most CPU’s are capable of hundreds or thousands of different operations, all of them small, but offering a wide variety of function. Most CPU’s will therefore have instructions to perform two operations typically known as ‘PUSH’ and ‘PULL’. These operations can go by various names, and the ‘PULL’ instruction is frequently referred to as ‘POP’, so much so, that I accidentally used ‘POP’ and ‘PULL’ at different points in the video. So what do these instructions do?

Well, PUSH causes the CPU to write a value into memory at the location which is specified by the stack pointer register, and then to increment that registers value. The PULL/POP instruction does the reverse, first it decrements the value in the register and then reads a value from memory at that location into the CPU.

Why? Well, lets walk an example.

PUSH

In the above diagram, we have a CPU with it’s stack pointer initialized to zero. This is represented on the right by the arrow pointing to location zero in memory. We’re going to imagine that we have the value five in some CPU register, such as the accumulator for example, and we want to ‘PUSH’ that value into our stack.

Just as in our earlier model, our CPU puts the value zero from the stack register onto it’s address bus, sets it’s read-write pin to write, and places the value five onto it’s data bus. The memory then sees this request to write into location zero, and updates the value at that memory location to the five from the data bus…

At this point, the CPU increments the stack pointer, to point at location one in memory..

That’s it, the push instruction is completed. We say that we’ve ‘pushed’ the value of five onto the stack.
I’ll discuss the importance of this in a moment, but first, lets look at the pop instruction.

POP

The CPU’s POP instruction, as I’ve already said, performs the PUSH operation in reverse.
First, the CPU will decrement the value in the stack register (which is still set at one from the above push example), back to zero.

The CPU then places the value from the stack register (zero) onto the address bus, and sets the read-write pin to read. The memory responds by placing the value from address zero, in this case a five, onto the data bus for the CPU to read back into a register.

Okay, so what’s it all about?

As I mentioned earlier, computers have vast amounts of memory with billions of available locations to store data. The pop operations of the stack need not be called for every push. We could instead call push multiple times, storing values at sequential locations in memory as the stack pointer advances. This allows us to store arbitrary amounts of information generated by the CPU into memory, without needing to know in advance the amount of memory that we’ll need.

Typically, given the available size of computer memory, some large block of memory locations will be reserved by software developers to be used as the stack. This serves as a sort of scratch-pad storage area for the CPU. Programs can be written for the CPU which are aware of this reserved block of memory, and therefore avoid reading/writing that region of memory except through the PUSH and PULL stack instructions.

We’re going to look at one more example of using the stack for the sake of clarity, but also, to call out a particular property of the stack which is important to understand for its proper use.

LIFI – Last-In, First Out.

Suppose we want to write some data into the stack, and read it out later. We’re going to write in the sequence of numbers [048,108,108,101,072]. These numbers are codes representing characters in something called the ASCII character set (for the curious, American Standard Code for Information Interchange). Essentially, the ASCII character set is a mapping of the english alphabet in both upper and lower case, some numeric digits and other symbols, to numbers. This allows us to store text as a series of numbers in memory, to be manipulated by the CPU as required. Our example numbers [048,108,108,101,72] map to the characters [‘o’,’l’,’l’,’e’,’H’] respectively.

The following image sequence demonstrates ‘PUSHing’ these numbers onto the stack…

As you can see, the stack pointer continues to increment through memory as we push data into the stack. Now, lets read that data back from the stack using POP instructions…

Now I know you saw this coming much earlier, but I’ll state it because it’s important. The string of characters that we pulled back from the stack reads ‘Hello’, which is the reverse of the string we pushed onto the stack which read ‘olleH’. Most computer science texts will liken the memory stack to a stack of dishes, and I can’t think of a better example, and so it goes… When you pick up a dish from the top of a stack of dishes, the one you pick up was the last one placed on the top of the stack. Similarly, when you pull/pop a value from the sack, the value you get is the last one you pushed onto the stack.
In computer science this is known as a LIFO system, for ‘Last-In, First-Out’ and essentially has the effect of reversing any data that you stored on, and then later retrieved from the stack.