StackMachine

This is the source code for the stack machine class StackMachine, to be used in exercise 7. You can also download all the files as a compressed tar file or as a ZIP file.

On a Unix or Linux system, with gcc installed, you can compile the program by just typing make.

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@tech.oru.se) 2003

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 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,
  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;
  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

Download
// StackMachine.h -- implementation file for the stack machine
// Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 2003

#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();
}

// 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 },
  { 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 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()) {
    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 (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

Download
// stacktest.cpp -- a small program to test the stack machine
// Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) 2003

#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;
  }


  return 0;
}

Makefile

Download
OFILES = stacktest.o StackMachine.o

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/StackMachine.tar StackMachine/StackMachine.tar.gz StackMachine/StackMachine.zip; tar -cvf StackMachine.tar StackMachine; gzip -9 StackMachine.tar; zip -r StackMachine.zip StackMachine; mv StackMachine.zip StackMachine/StackMachine.zip; mv StackMachine.tar.gz StackMachine/StackMachine.tar.gz


Thomas Padron-McCarthy (Thomas.Padron-McCarthy@tech.oru.se) January 12, 2004