On a Unix or Linux system, with GCC installed, you can compile the program by just typing make.
This is the new, experimental version from 2012.
Jump:
StackMachine.h |
StackMachine.cpp |
stacktest.cpp |
Makefile
Download:
StackMachine.h |
StackMachine.cpp |
stacktest.cpp |
Makefile
StackMachine.h
Download
// StackMachine.h -- interface file for the stack machine
// Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) 2003, 2012
class Exception {
private:
std::string the_message;
public:
Exception(const std::string& m) : the_message(m) { }
const std::string& message() const { return the_message; }
};
// Stack operations according to ASU-86 pp 65-66
// Warning! If you change this, you must change StackMachine.cpp too!
enum StackOp {
push, // Push a number
rvalue, // Push a reference to a variable
lvalue, // Push the contents of a variable
pop,
assign,
copy,
plus, minus, times, divide, modulo,
eq, ne, lt, gt, le, ge, // ==, !=, <, >, <=, >=
stackop_or, stackop_and, stackop_not, // ||, &&, !
stackop_read, stackop_write,
label, // Realistically, this shouldn't really be an instruction
jump,
gofalse,
gotrue,
halt
};
class Instruction {
private:
enum StackOp the_op;
int the_argument;
struct OpInfo {
enum StackOp op;
std::string name;
int nr_args;
};
static OpInfo op_info[];
public:
Instruction(enum StackOp op, int argument);
Instruction(enum StackOp op);
enum StackOp op() const { return the_op; }
int argument() const { return the_argument; }
friend std::ostream& operator<< (std::ostream& o, const Instruction& i);
};
class StackMachine {
private:
std::vector<int> stack; // Not std::stack, if we want to print it
std::vector<Instruction> program;
std::map<int, int, std::less<int> > labels;
std::map<int, int, std::less<int> > variables;
unsigned int pc;
int running;
int trace;
std::ostream& outstream;
void stackpush(int x);
int stackpop();
void internal_run();
void internal_cont();
void internal_step();
public:
StackMachine(std::ostream& os = std::cout);
void append(const Instruction& i);
void showstate() const;
void list_program() const;
void run();
void cont();
void single_step();
void set_trace(int t);
};
// StackMachine.cpp -- implementation file for the stack machine
// Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) 2003, 2012
#include <iostream>
#include <vector>
// #include <stack> -- (Perhaps surprisingly) not.
#include <map>
#include <string>
#include <sstream>
#include "StackMachine.h"
Instruction::Instruction(enum StackOp op, int argument)
: the_op(op), the_argument(argument)
{
if (op_info[op].nr_args != 1) {
std::stringstream s;
s << "Tried to create " << op_info[op].name
<< " instruction with an argument (" << argument << ").";
throw Exception(s.str());
}
}
Instruction::Instruction(enum StackOp op)
: the_op(op), the_argument(0)
{
if (op_info[op].nr_args != 0) {
std::stringstream s;
s << "Tried to create " << op_info[op].name
<< " instruction without an argument.";
throw Exception(s.str());
}
}
std::ostream& operator<< (std::ostream& o, const Instruction& i) {
o << i.op_info[i.op()].name;
if (i.op_info[i.op()].nr_args == 1)
o << "," << i.argument();
return o;
}
// Warning! If you change this, you must change StackMachine.h too!
Instruction::OpInfo Instruction::op_info[] = {
{ push, "push", 1 },
{ rvalue, "rvalue", 1 },
{ lvalue, "lvalue", 1 },
{ pop, "pop", 0 },
{ assign, "assign", 0 },
{ copy, "copy", 0 },
{ plus, "plus", 0 },
{ minus, "minus", 0 },
{ times, "times", 0 },
{ divide, "divide", 0 },
{ modulo, "modulo", 0 },
{ eq, "eq", 0 },
{ ne, "ne", 0 },
{ lt, "lt", 0 },
{ gt, "gt", 0 },
{ le, "le", 0 },
{ ge, "ge", 0 },
{ stackop_or, "or", 0 },
{ stackop_and, "and", 0 },
{ stackop_not, "not", 0 },
{ stackop_read, "read", 0 },
{ stackop_write, "write", 0 },
{ label, "label", 1 },
{ jump, "jump", 1 },
{ gofalse, "gofalse", 1 },
{ gotrue, "gotrue", 1 },
{ halt, "halt", 0 }
};
void StackMachine::stackpush(int x) {
stack.push_back(x);
}
int StackMachine::stackpop() {
if (stack.empty())
throw Exception("Program tried to pop from empty stack.");
int result = stack.back();
stack.pop_back();
return result;
}
void StackMachine::internal_run() {
pc = 0;
stack.clear();
variables.clear();
internal_cont();
}
void StackMachine::internal_cont() {
running = 1;
while (running) {
internal_step();
}
}
void StackMachine::internal_step() {
int r, l;
if (pc >= program.size()) {
std::stringstream s;
s << "PC " << pc << " outside program (0.." << program.size() - 1 << ").";
throw Exception(s.str());
}
int op = program[pc].op();
int arg = program[pc].argument();
if (trace) {
outstream << "Trace: " << pc << ": ";
outstream << program[pc];
outstream << std::endl;
}
switch (op) {
case push:
stackpush(arg);
pc++;
break;
case rvalue:
if (variables.find(arg) == variables.end()) {
std::stringstream s;
s << "Program tried to get value of unset variable (number " << arg << ").";
throw Exception(s.str());
}
stackpush(variables[arg]);
pc++;
break;
case lvalue:
stackpush(arg);
pc++;
break;
case pop:
stackpop();
pc++;
break;
case assign:
r = stackpop();
l = stackpop();
variables[l] = r;
pc++;
break;
case copy:
r = stackpop();
stackpush(r);
stackpush(r);
pc++;
break;
case plus:
r = stackpop();
l = stackpop();
stackpush(l + r);
pc++;
break;
case minus:
r = stackpop();
l = stackpop();
stackpush(l - r);
pc++;
break;
case times:
r = stackpop();
l = stackpop();
stackpush(l * r);
pc++;
break;
case divide:
r = stackpop();
l = stackpop();
if (r == 0) {
std::stringstream s;
s << "Program tried to calculate " << l << " / " << r << ".";
throw Exception(s.str());
}
stackpush(l / r);
pc++;
break;
case modulo:
r = stackpop();
l = stackpop();
if (r == 0) {
std::stringstream s;
s << "Program tried to calculate " << l << " % " << r << ".";
throw Exception(s.str());
}
stackpush(l % r);
pc++;
break;
case eq:
r = stackpop();
l = stackpop();
stackpush(l == r);
pc++;
break;
case ne:
r = stackpop();
l = stackpop();
stackpush(l != r);
pc++;
break;
case lt:
r = stackpop();
l = stackpop();
stackpush(l < r);
pc++;
break;
case gt:
r = stackpop();
l = stackpop();
stackpush(l > r);
pc++;
break;
case le:
r = stackpop();
l = stackpop();
stackpush(l <= r);
pc++;
break;
case ge:
r = stackpop();
l = stackpop();
stackpush(l >= r);
pc++;
break;
case stackop_or:
r = stackpop();
l = stackpop();
stackpush(l || r);
pc++;
break;
case stackop_and:
r = stackpop();
l = stackpop();
stackpush(l && r);
pc++;
break;
case stackop_not:
r = stackpop();
stackpush(! arg);
pc++;
break;
case stackop_read:
std::cout << "Enter an integer: ";
int new_value;
std::cin >> new_value;
stackpush(new_value);
pc++;
break;
case stackop_write:
r = stackpop();
std::cout << "Value: " << r << "\n";
pc++;
break;
case label:
// A nop ("no operation")
pc++;
break;
case jump:
if (labels.find(arg) == labels.end()) {
std::stringstream s;
s << "Program tried to jump to nonexistent label (number " << arg << ").";
throw Exception(s.str());
}
pc = labels[arg]; // We know this is inside the program
break;
case gofalse:
r = stackpop();
if (!r) {
if (labels.find(arg) == labels.end()) {
std::stringstream s;
s << "Program tried to jump to nonexistent label (number " << arg << ").";
throw Exception(s.str());
}
pc = labels[arg]; // We know this is inside the program
}
else
pc++;
break;
case gotrue:
r = stackpop();
if (r) {
if (labels.find(arg) == labels.end()) {
std::stringstream s;
s << "Program tried to jump to nonexistent label (number " << arg << ").";
throw Exception(s.str());
}
pc = labels[arg]; // We know this is inside the program
}
else
pc++;
break;
case halt:
pc++;
running = 0;
if (trace)
outstream << "Program halted." << std::endl;
break;
default:
std::stringstream s;
s << "Illegal instruction in program (instruction "
<< op << " at position " << pc << ").";
throw Exception(s.str());
break;
} // switch
} // internal_step
StackMachine::StackMachine(std::ostream& os)
: pc(0), running(0), trace(0), outstream(os)
{ }
void StackMachine::append(const Instruction& i) {
if (i.op() == label) {
if (labels.find(i.argument()) != labels.end()) {
std::stringstream s;
s << "Tried to re-define label " << i.argument() << ".";
throw Exception(s.str());
}
labels[i.argument()] = program.size();
}
program.push_back(i);
}
void StackMachine::showstate() const {
outstream << "State of the stack machine:\n";
outstream << " pc = " << pc;
if (pc >= program.size())
outstream << " (last program instruction is at " << program.size() - 1 << ")";
else {
outstream << " (instruction: ";
outstream << program[pc];
outstream << ")";
}
outstream << "\n";
outstream << " trace = " << trace << "\n";
outstream << " Stack (size " << stack.size() << ")\n";
if (!stack.empty()) {
outstream << " ";
for (std::vector<int>::const_iterator p = stack.begin();
p < stack.end();
++p)
outstream << *p << " ";
outstream << "\n";
}
outstream << " Variables (" << variables.size() << " " <<
(variables.size() == 1 ? "variable" : "variables") << ")\n";
if (!variables.empty()) {
outstream << " ";
for (std::map<int, int, std::less<int> >::const_iterator p = variables.begin();
p != variables.end();
++p)
outstream << (*p).first << "=" << (*p).second << " ";
outstream << "\n";
}
outstream << std::endl;
} // showstate
void StackMachine::list_program() const {
outstream << "Program listing (length " << program.size() << ")\n";
if (!program.empty()) {
unsigned int pos = 0;
for (std::vector<Instruction>::const_iterator p = program.begin();
p < program.end();
++p) {
outstream << " " << pos << ": ";
outstream << *p;
if (p->op() == label) {
for (unsigned int cfp = 0; cfp < program.size(); ++cfp) {
enum StackOp cfp_op = program[cfp].op();
if ( program[cfp].argument() == p->argument()
&& (cfp_op == jump || cfp_op == gofalse || cfp_op == gotrue)) {
outstream << " (target from " << cfp << ")";
}
}
}
if (pos == pc)
outstream << " <-- PC";
outstream << "\n";
++pos;
}
}
outstream << std::endl;
} // showsprogram
void StackMachine::run() {
if (trace)
outstream << "run(): Starting execution at position 0..." << std::endl;
internal_run();
}
void StackMachine::cont() {
if (trace)
outstream << "cont(): Continuing execution at position "
<< pc << "..." << std::endl;
internal_cont();
}
void StackMachine::single_step() {
if (trace)
outstream << "single_step(): Stepping one instruction at position "
<< pc << "..." << std::endl;
internal_step();
}
void StackMachine::set_trace(int t) {
trace = t;
}
// stacktest.cpp -- a small program to test the stack machine
// Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se) 2003, 2012
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <sstream>
#include "StackMachine.h"
int main() {
StackMachine sm;
try {
sm.append(Instruction(push, 10));
sm.append(Instruction(lvalue, 17));
sm.append(Instruction(push, 4711));
sm.append(Instruction(assign));
sm.append(Instruction(push, 100));
sm.append(Instruction(gofalse, 1));
// sm.append(Instruction(pop, 100));
sm.append(Instruction(pop));
sm.append(Instruction(push, 20));
sm.append(Instruction(rvalue, 17));
sm.append(Instruction(rvalue, 17));
sm.append(Instruction(rvalue, 17));
// sm.append(Instruction(rvalue, 18));
sm.append(Instruction(push, 30));
sm.append(Instruction(push, 10000));
sm.append(Instruction(plus));
sm.append(Instruction(plus));
sm.append(Instruction(label, 1));
sm.append(Instruction(label, 2));
sm.append(Instruction(push, 10));
sm.append(Instruction(label, 999));
sm.append(Instruction(push, 1));
sm.append(Instruction(minus));
sm.append(Instruction(copy));
sm.append(Instruction(gotrue, 999));
sm.append(Instruction(label, 1000));
sm.append(Instruction(push, 1));
sm.append(Instruction(push, 2));
sm.append(Instruction(push, 3));
sm.append(Instruction(push, 4));
sm.append(Instruction(push, 5));
sm.append(Instruction(push, 6));
sm.append(Instruction(plus));
sm.append(Instruction(minus));
sm.append(Instruction(times));
// sm.append(Instruction(push, 0));
sm.append(Instruction(push, 47));
sm.append(Instruction(push, 48));
sm.append(Instruction(push, 49));
sm.append(Instruction(assign));
sm.append(Instruction(divide));
sm.append(Instruction(push, 50));
sm.append(Instruction(modulo));
sm.append(Instruction(halt));
sm.showstate();
sm.list_program();
sm.set_trace(1);
sm.run();
sm.showstate();
}
catch(Exception& e) {
std::cout << "*** Exception caught: " << e.message() << std::endl;
sm.showstate();
sm.list_program();
}
catch(...) {
std::cout << "Unknown exception." << std::endl;
}
StackMachine sm2;
try {
sm2.append(Instruction(push, 10));
sm2.append(Instruction(plus));
std::cout << "--- Now, a deliberate error should be caught:" << std::endl;
sm2.run();
}
catch(Exception& e) {
std::cout << "*** Exception caught: " << e.message() << std::endl;
sm2.showstate();
sm2.list_program();
}
catch(...) {
std::cout << "Unknown exception." << std::endl;
}
StackMachine sm3;
try {
sm3.append(Instruction(lvalue, 13));
sm3.append(Instruction(stackop_read));
sm3.append(Instruction(assign));
sm3.append(Instruction(lvalue, 22));
sm3.append(Instruction(stackop_read));
sm3.append(Instruction(assign));
sm3.append(Instruction(rvalue, 13));
sm3.append(Instruction(rvalue, 22));
sm3.append(Instruction(plus));
sm3.append(Instruction(stackop_write));
sm3.append(Instruction(halt));
sm3.list_program();
sm3.run();
}
catch(Exception& e) {
std::cout << "*** Exception caught: " << e.message() << std::endl;
sm3.showstate();
sm3.list_program();
}
catch(...) {
std::cout << "Unknown exception." << std::endl;
}
return 0;
}
OFILES = stacktest.o StackMachine.o
CPPFLAGS = -g -Wall
stacktest: $(OFILES)
g++ -o stacktest $(OFILES)
StackMachine.o: StackMachine.h
stacktest.o: StackMachine.h
clean:
$(RM) $(OFILES) stacktest
archives: clean
cd ..; \
$(RM) StackMachine.tar StackMachine.tar.gz StackMachine.zip StackMachine-2012/StackMachine.tar StackMachine-2012/StackMachine.tar.gz StackMachine-2012/StackMachine.zip; \
tar -cvf StackMachine.tar StackMachine-2012; \
gzip -9 StackMachine.tar; \
zip -r StackMachine.zip StackMachine-2012; \
mv StackMachine.zip StackMachine-2012/StackMachine.zip; \
mv StackMachine.tar.gz StackMachine-2012/StackMachine.tar.gz