Exploring Stack Machines: One Stack Good, Two Stacks Better.

In my previous post I gave a brief history of stack machines, what they are and why they are relevant. The example I presented was little more than a RPN calculator with a verbose syntax. And if that was all I was aiming for, a stack machine would be way overkill, since we could do the whole shebang a whole lot easier using Dijkstra’s 2-stack (there’s that word again!) algorithm.

But I told you stack machines were powerful, and I want to show you how with the addition of a few simple constructs we can turn our stack machine into something that can (eventually) be targetable by compilers of higher level languages.

Up until this point our stack machine can only handle simple arithmetic. In this post I am going to expand our stack machines instruction set by adding the ability to perform conditional logic and branching. To do this we will also be adding a second stack: the return address stack.

Two Instruction of Deceptive Power

There are two instruction that will enable us to implement practically any higher level control flow (looping, if statements, etc). Truth be told, we could actually get by with just one of them, but since we are not planning on implementing this stack machine in silicon(i.e. purely virtual), nor are we in a resource constrained environment, so we might as well give ourselves a rich instruction set to make programming easier. The two instructions I’m talking about are jmpnz and jmpz, which stand for Jump If Not Zero and Jump If Zero, respectively.

jmpnz <address to jump to> "Jump If Not Zero"
jmpz <address to jump to>  "Jump If Zero"

These instructions perform an action predicated on the value of the top item on the data stack. They both perform a jump to the provided address, but jmpz jumps if the top value on the stack is zero, while jmpnz jumps when the top value on the stack is NOT zero.

How might that be useful you ask? Take for example the following program written in our stack machines assembly language:

[0] push 7
[1] show
[2] push 1
[3] sub
[4] jmpnz 1
[5] halt

This program counts down from 7, printing each digit out to the console. So how do we make this happen? It’s actually very easy.
What this instruction does is peeks at the top value on the stack, and if it is not zero, we change the program counter to the address we provide as an argument.

OPSTAT StackMachine::jmpnz(int addr) {
    if (data[top-1] != 0) {
        push(programCounter);
        pushr();               
        programCounter = addr;
        return OP_BRANCH;      
    }
    tosr = data[top-1]; //Otherwise proceed as normal
    return pop();
} 

But wait a minute.. Whats pushr()? And what’s with the new return code? For the simple counter program, they are actually not relevant. They ARE however EXTREMELY important to the implementation of some higher level constructs, so we I may as well cover it now.

The Address Return Stack

The address return stack, despite the name is identical to the data stack, with the limitation that it only supports push and pop. It’s called the address return stack because it’s primary purpose is for storing addresses to return to for implementing subroutines. The instructions for interacting with the return address stack are:

pushr
popr

pushr works slightly different to how push works with the data stack. As you remember, push takes an operand to be placed on the stack. But with pushr, it pops the first item off of the data stack and pushes it onto the return address stack. Likewise, popr removes the top item from the return address stack and pushes it on to the data stack.

 OPSTAT StackMachine::pushr() { 
    rets[rtop++] = pop(); 
    return OP_SUCCESS; 
}

OPSTAT StackMachine::popr() { 
    return push(rets[--rtop]); 
} 

The thing about pushr and popr is that except when you are using the return address stack in a way that you are not supposed to (more on this in a moment), these instructions are usually called by other instructions and not the programmer. The address return stack is really meant to support jmpnz, jmpz, call, and retf. I’ve explained jmpnz and jpmz already, the other two are new.

call
retf

These two instructions are for calling subroutines, and return from subroutines (or jumps), respectively. To use call, you first push the address of the starting instruction of the block of code you want to execute on to the data stack, and then issue the call instruction. The call instruction will put the return address on to the data stack, and then moves it to the return address stack. It then pops the jump target off the data stack and loads into the program counter. The retf instruction is pretty much the same actions in reverse.z

 
OPSTAT StackMachine::call() {
    push(programCounter+1);
    pushr();             
    programCounter = pop();
    return OP_BRANCH;
}

OPSTAT StackMachine::retf() {
    popr();
    programCounter = pop();
    return OP_BRANCH;
} 

Now that I’ve told you what the primary purpose of the address return stack is I can make you privy to a little secret: the return address stack can also be used for all manner of data. Being able to shuffle data between the two stacks gives us access to the items in the stack while preserving stack order. Do you know the data structure exercise of making a FIFO queue from two LIFO stacks? Have you ever wondered why and under what circumstances you would possibly ever need to do that? Now you know.

Testing Equality

I opened this post by demonstrating how to implement a simple loop in our stack machines assembly language using the jmpnz instruction. Since we know that we can jump based on the top value of the data stack, it only makes sense then to implement operations that compare the top two items, and push the result of that comparison.

 
OPSTAT StackMachine::cmpl() {
    return push(data[top-2] < data[top - 1]);
}

OPSTAT StackMachine::cmpg() {
    return push(data[top-2] > data[top - 1]);
}

OPSTAT StackMachine::cmpeq() {
    return push(data[top-2] == data[top - 1]);
}

With these operations, combined with the addres return stack we can do things like: “If x < y then do xyz” using our stack machine assembly language. Take a minute to study the following program:

push 7
push 3
cmpeq
jmpnz 7
cmpl
jmpnz 10
halt
push 13
show
retf
push 21
show
retf

Have you guessed what it does? It puts two values on the stack, and tests if they are equal, or if the top item is less than the second item on the stack. If they are equal it will print 13, or if the top item is less, it will print 21. When run on the stack machine (with debug tracing turned on) it produces the following output:

max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./smex2
 [0] push 7, Stack: []
 [1] push 3, Stack: [7 ]
 [2] cmpeq , Stack: [3 7 ]
 [3] jmpnz 7, Stack: [0 3 7 ]
 [0] [LAST INSTRUCTION FAILED.]
 [4] cmpl , Stack: [3 7 ]
 [5] jmpnz 10, Stack: [1 3 7 ]
 [5] pushr Stack: [6 1 3 7 ] raddr Stack: []
 [2] [BRANCHING TO: 10]
 [10] push 21, Stack: [1 3 7 ]
 [11] show , Stack: [21 1 3 7 ]
 [-]21
 [12] retf , Stack: [21 1 3 7 ]
 [12] popr Stack: [21 1 3 7 ] raddr Stack: [6 ]
 [2] [BRANCHING TO: 6]
 [6] halt , Stack: [21 1 3 7 ]
 max@MaxGorenLaptop:/mnt/c/Users/mgoren$

This may not seem very impressive. But then you realize that this code maps very nicely to something like:

if (3 == 7) {
    print(13)
}
if (3 < 7) {
    print(21)
}

And that code generation from an abstract syntax tree of a higher level language, to our stack machine assembly language would be fairly straight forward, things get far more interesting.

But before all that, lets make one small adjustment to our stack machine, and this one is purely out of convenience. It would be rather tiresome to have to manually calculate the memory address we want to jump to when writing our programs. Wouldn’t it be great if we could use some sort of name or label instead? Of course it would! and thankfully this a pretty straight forward to implement, with the changes to be made taking place in the tokenizer. First though, lets establish the new syntax.

:<label name>: - this demarcates the beginning of a code block
jmpnz :<label name>: - perform the jmpnz operation to the code block at label
jmpz :<label name>: - perform the jmpz operation to the code block at label

The previous program would now be written like this:

push 7
push 3
cmpeq
jmpnz :sub1:
cmpl
jmpnz :sub2:
halt
:sub1:
push 13
show
retf
:sub2:
push 21
show
retf

A bit easier to read, and a little less cryptic, don’t you think? Let’s make the changes to our tokenizer:

 
vector<string> StackMachine::smtokenizer(vector<string>& exprs, char DELIM) {
    string expr = exprs[programCounter];
    vector<string> tokens;
    int pos = 0, i = 0, si = 0; //position, index, starting index.
    while (i < expr.size()) {
        if (expr[i] == DELIM) {
            string subexpr = expr.substr(si, pos - si);
            tokens.push_back(subexpr);
            while (i < expr.size() && expr[i] == DELIM) {
                i++; pos++;
            }
            si = pos;
        } else {
            pos++; i++;
        }
    }
    string subexpr = expr.substr(si, pos - si);
    tokens.push_back(subexpr);
    if (tokens[0][0] == ':' && tokens[0][tokens[0].size() - 1] == ':') {
        if (debugMode) {
            cout<<"[Encountered Non Instruction: "<<tokens[0]<<"]\n";
            vector<string> ret;
            ret.push_back("nop");
            return ret;
        }
    }
    if (tokens.size() > 1 && tokens[1][0] == ':') {
        string label = tokens[1].substr(1, tokens[1].size() - 2);
        if (debugMode) {
            cout<<"[Found Text Label] [Calculating numerical address of: " <<label;
            cout<<"]\n";
        }
        for (int i = programCounter; i < exprs.size(); i++) {
            if (exprs[i] == tokens[1]) {
                tokens[1] = to_string(i + 1); //+1 because code starts after label. It is optional
                if (debugMode)            //but without +1 it would perform an unneccesary "nop" instruction
                    cout<<"[Address of "<<label<<" Found at: "<<tokens[1]<<"]\n";
                return tokens;
            }
        }
        if (debugMode) {
            cout<<"[ERROR] [Could not find codeblock with name: "<<label<<"]\n";
        }
        tokens.clear();
        tokens.push_back("halt");
        return tokens;
    }
    return tokens;
} 

Now if the tokenizer encounters a label instead of an address, it computes the proper address offset from the current program counter and replaces the label with the proper address of the code block being jumped to.

Right about now you should be realizing that we are starting to get to a point where we could implement some fairly complex programs on our stack machine, and this is where things get really fun!

But you’ll have to wait for my next post for that. So until then, Happy Hacking!

Further Reading

Stack Computers: 3.2 A GENERIC STACK MACHINE (cmu.edu) – a good description on the stack machine instructions, and forth instruction sets

The working implementation of the stack machine as discussed so far is available on my github: http://github.com/maxgoren/stackmachine