In the early days of computing, before the time of standardized instruction sets – or standardized anything really – software was decidedly non-portable. If you wrote a piece of software on machine A, it more than likely would not run on machine B, even if they were made by the same company!
Needless to say this was less than ideal: the same work was often carried out multiple times leading to wasted time, money, and resources. This was a major problem, from both a technical and business standpoint. Seeing how it was solved by computer scientists, the solution should come as no surprise to anyone: abstraction.
“What if”, a cunning computer scientist said “we emulated the machine and wrote our compilers to target the emulators instruction set instead of that of the physical machine the program runs on?”. This was quite the “aha!” moment. Instead of having to write a new compiler each time they wanted to use a specific programming language on a computer with a different instruction set, they would only need to write a virtual machine for each new architecture. The compiler would both target and run on the virtual machine. But not just compilers. Any software written for that virtual machine can now be run without being re-written. The problem of portability was solved.
The ideas behind bootstrapping a selfhosting compiler are fascinating, filled with technical nuances, and clever solutions, each one seemingly more brilliant than the last. For this post I’ll be focusing on just the virtual machine part of things for now. The ideas presented here are far from new. Languages like Burroughs Algol, Forth and the UCSD Pascal p-code system blazed the trail in the early days. More recently, the original implementation of the Java Virtual Machine was as an 8bit virtual stack machine, with many other programming languages using virtual stack machines as a compilation target.
The Stack Machine
Like their physical counterparts, there are a variety of different virtual machines. The two most commonly found are Stack machines and register machines. Stack machines are somewhat more straight forward to understand – though still quite powerful and so it is these that i will be describing.
The driving force behind stack machines is as the name would imply the stack data structure. As a program is executed, the stack machine maintains a stack which is used for processing data during execution. Items are added and removed from the stack in a Last In First Out fashion.
Lets start by designing a stack machine that will support four basic instructions:
- PUSH <item> – add an item to the top of the stack
- POP – remove an item from the top of the stack
- ADD – remove the top two items from the stack, add them together and push them back on to the stack
- SHOW – print the top value on the stack
We can of course add more instructions, but these four instructions are all we need to give us a basic idea of how a stack machine works. You can think of these instructions like a basic assembly language that our virtual machine is going to interpret and execute. With this in mind, let’s write our stack machines first program. For now, we can use an array of strings to store our program:
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<string> program = {
"push 7", // put 7 on the stack
"push 3", // put 3 on the stack
"add", // removes 3, then removes 7, adds result of 3 + 7 to stack
"show", // shows the top item on the stack: 10
"push 13", // adds 13 to the stack
"add", // removes 13 from the stack, removes 10, adds result of 10 + 13 to the stack
"show" // shows the top of the stack: 23
};
StackMachine sm;
sm.run(program);
return 0;
}
More advanced stack machines often have more than one stack, but we will start with just one, the data stack. The other major component is the ALU, or Arithmetic Logic Unit and it is responsible for exactly what it sounds like it is.
typedef int OPSTAT;
const OPSTAT OP_SUCCESS = 1;
const OPSTAT OP_ERROR = -1;
class StackMachine {
private:
//data stack
int top; //top os stack
int data[255]; //data stack
OPSTAT push(string arg);
OPSTAT push(int arg);
int pop();
OPSTAT show();
//alu
OPSTAT ALU(string op, string arg);
OPSTAT tosr; //top of stack register
OPSTAT add();
vector<string> smtokenizer(string expr, char DELIM);
int programCounter;
public:
StackMachine() {
top = 0;
tosr = 0;
programCounter = 0;
}
void run(vector<string>& program);
};
So we have designed our instructions grammar, and we have our data stack. The next step is to take our the program in the form of a list of instructions and perform the operation that is being instructed to execute. Because we’re keeping it simple at first and our stack machine is only executing straight line programs with no branching, we only need to step through our program line by line, extracting the instructions and any arguments that may be present. Think of the vector of strings as the program loaded into program memory on our stack machine and the variable programCounter is holding the address of the instruction we are executing.
void StackMachine::run(vector<string>& program) {
string op, arg;
int opCnt = 0;
for (programCounter = 0; programCounter < program.size(); programCounter++) {
string instr = program[programCounter]; //Fetch the next instruction in the program.
vector<string> tokens = smtokenizer(instr, ' '); //break the expression
op = tokens[0]; //down into operation and argument
arg = (tokens.size() > 1) ? tokens[1]:"";
cout<<"["<<opCnt++<<"] "<<op<<" "<<arg<<"\n";
//pass the instruction to the arithmetic and logic unit
OPSTAT stat = ALU(op, arg);
if (stat == OP_ERROR) {
cout<<"["<<stat<<"] ";
cout<<"[LAST INSTRUCTION FAILED.]\n";
}
}
}
You can implement tokenizer however you see fit, all it needs to do is take the input string, and break it down into its individual components, the following is how I did it, which is admittedly way overkill for the task at hand, but may come in handy later if we want to say, come up with a scripting language targeting a more advanced version of the virtual stack machine…
vector<string> StackMachine::smtokenizer(string expr, char DELIM) {
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);
return tokens;
}
And of course we have the functions for the instructions themselves:
OPSTAT StackMachine::push(string arg) {
return push(atoi(arg.c_str()));
}
OPSTAT StackMachine::push(int arg) {
data[top++] = arg;
tosr = arg;
return OP_SUCCESS;
}
int StackMachine::pop() {
tosr = data[--top];
return tosr;
}
OPSTAT StackMachine::add() {
int a = pop();
int b = pop();
tosr = a + b;
push(tosr);
return OP_SUCCESS;
}
OPSTAT StackMachine::show() {
cout<<"[TOP]"<<data[top-1]<<"\n";
return OP_SUCCESS;
}
int StackMachine::ALU(string op, string arg) {
if (op == "push") {
return push(arg);
} else if (op == "pop") {
return pop();
} else if (op == "add") {
return add();
} else if (op == "show") {
return show();
}
return OP_ERROR;
}
Now lets compile our stack machine, and run our program to see what happens:
max@MaxGorenLaptop:/mnt/c/Users/mgoren$ ./smex2
[0] push 7
[1] push 3
[2] add
[3] show
[TOP]10
[4] push 13
[5] add
[6] show
[TOP]23
max@MaxGorenLaptop:/mnt/c/Users/mgoren$
Sweet, so we can add things… I know, it’s nothing to get too excited about. that was just to give you a very basic idea of the strategy being employed. Lets at least add what we need to implement a basic calculator:
class StackMachine {
//...code....
OPSTAT mult();
OPSTAT sub();
OPSTAT div();
OPSTAT mod();
//..code...
};
OPSTAT StackMachine::mult() {
int a = pop();
int b = pop();
tosr = a*b;
push(tosr);
return OP_SUCCESS;
}
OPSTAT StackMachine::sub() {
int a = pop();
int b = pop();
tosr = b - a;
push(tosr);
return OP_SUCCESS;
}
OPSTAT StackMachine::div() {
int a = pop();
int b = pop();
tosr = b/a;
push(tosr);
return OP_SUCCESS;
}
OPSTAT StackMachine::mod() {
int a = pop();
int b = pop();
tosr = b % a;
push(tosr);
return OP_SUCCESS;
}
int StackMachine::ALU(string op, string arg) {
if (op == "push") {
return push(arg);
} else if (op == "pop") {
return pop();
} else if (op == "add") {
return add();
} else if (op == "mult") {
return mult();
} else if (op == "sub") {
return sub();
} else if (op == "div") {
return div();
} else if (op == "show") {
return show();
}
}
Still, I know what you’re probably thinking: “we’re a hell of a long way off from the JVM”. And you’re right, but when you stop to appreciate the simplicity, and then realize that with a little bit of effort we could implement a full instruction set that can be targetable by higher level languages and THAT is cool.
Until next time, happy hacking!
