// Simple stack-based VM.
// Extended with DIV.
// Integrated with QuickCheck
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <memory>
#include <cstdlib>
#include <functional>
#include <algorithm>
using namespace std;
///////////////////////////////////////
// VM code
typedef enum {
PLUS,
MULT,
MINUS,
ONE,
TWO
} Code_t;
string show(Code_t c) {
switch(c) {
case ONE: return "1";
case TWO: return "2";
case PLUS: return "+";
case MINUS: return "-";
case MULT: return "*";
}
}
string show(vector<Code_t> cs) {
string s;
for(int i=0; i < cs.size(); i++) {
s = s + show(cs[i]);
if(i < cs.size() - 1) {
s = s + " ";
}
}
return s;
}
///////////////////////////////////////
// Expressions
// - eval (interpreter)
// - convert to "reverse polish notation"
// Operands come first
// Computations require a single stack
class Exp {
public:
virtual int eval() = 0;
virtual vector<Code_t>convert() = 0;
virtual string show() = 0;
};
class IntExp : public Exp {
public:
int x;
IntExp(int x) {
if(x == 1 || x == 2) {
this->x = x;
}
else {
this->x = 1;
cout << "\nmust be 1 or 2";
}
}
string show() { return to_string(x); }
int eval() { return this->x; }
vector<Code_t>convert() {
vector<Code_t> v;
auto n = x == 1 ? ONE : TWO;
v.push_back(n);
return v;
}
};
class PlusExp : public Exp {
public:
shared_ptr<Exp> left, right;
PlusExp(shared_ptr<Exp> left, shared_ptr<Exp> right) {
this->left = left; this->right = right;
}
string show() {
string s("(");
s.append(left->show());
s.append("+");
s.append(right->show());
s.append(")");
return s;
}
int eval() { return left->eval() + right->eval(); }
vector<Code_t>convert() {
auto v1 = left->convert();
auto v2 = right->convert();
v1.insert(v1.end(),v2.begin(),v2.end()); // append v2 to v1
v1.push_back(PLUS);
return v1;
}
};
class MultExp : public Exp {
public:
shared_ptr<Exp> left, right;
MultExp(shared_ptr<Exp> left, shared_ptr<Exp>right) {
this->left = left; this->right = right;
}
string show() {
string s("(");
s.append(left->show());
s.append("*");
s.append(right->show());
s.append(")");
return s;
}
int eval() { return left->eval() * right->eval(); }
vector<Code_t>convert() {
auto v1 = left->convert();
auto v2 = right->convert();
v1.insert(v1.end(),v2.begin(),v2.end()); // append v2 to v1
v1.push_back(MULT);
return v1;
}
};
class MinExp : public Exp {
public:
shared_ptr<Exp> left, right;
MinExp(shared_ptr<Exp> left, shared_ptr<Exp>right) {
this->left = left; this->right = right;
}
string show() {
string s("(");
s.append(left->show());
s.append("-");
s.append(right->show());
s.append(")");
return s;
}
int eval() { return left->eval() - right->eval(); }
vector<Code_t>convert() {
auto v1 = left->convert();
auto v2 = right->convert();
v1.insert(v1.end(),v2.begin(),v2.end()); // append v2 to v1
v1.push_back(MINUS);
return v1;
}
};
// Helper functions
shared_ptr<Exp> newInt(int i) {
return make_shared<IntExp>(i);
}
shared_ptr<Exp> newPlus(shared_ptr<Exp> left, shared_ptr<Exp> right) {
return make_shared<PlusExp>(PlusExp(left,right));
}
shared_ptr<Exp> newMult(shared_ptr<Exp> left, shared_ptr<Exp> right) {
return make_shared<MultExp>(MultExp(left,right));
}
shared_ptr<Exp> newMin(shared_ptr<Exp> left, shared_ptr<Exp> right) {
return make_shared<MinExp>(MinExp(left,right));
}
///////////////////////////////////////
// VM run-time
class VM {
vector<Code_t> code;
public:
VM(vector<Code_t> c) : code(c) {}
void showRunConvert() {
cout << "\n VM code: " << show(code);
cout << "\n => " << run();
cout << "\n Exp: " << convert()->eval();
}
int run() {
stack<int> s;
for(int i = 0; i < code.size(); i++) {
switch(code[i]) {
case ONE:
s.push(1);
break;
case TWO:
s.push(2);
break;
case MULT: {
auto right = s.top();
s.pop();
auto left = s.top();
s.pop();
s.push(left * right);
break;
}
case MINUS: {
auto right = s.top();
s.pop();
auto left = s.top();
s.pop();
s.push(left - right);
break;
}
case PLUS: {
auto right = s.top();
s.pop();
auto left = s.top();
s.pop();
s.push(left + right);
break;
}
} // switch
} // for
return s.top();
} // run
shared_ptr<Exp> convert() {
stack<shared_ptr<Exp>> s;
for(int i = 0; i < code.size(); i++) {
switch(code[i]) {
case ONE:
s.push(newInt(1));
break;
case TWO:
s.push(newInt(2));
break;
case MULT: {
auto right = s.top();
s.pop();
auto left = s.top();
s.pop();
s.push(newMult(left,right));
break;
}
case MINUS: {
auto right = s.top();
s.pop();
auto left = s.top();
s.pop();
s.push(newMin(left,right));
break;
}
case PLUS: {
auto right = s.top();
s.pop();
auto left = s.top();
s.pop();
s.push(newPlus(left,right));
break;
}
} // switch
} // for
return s.top();
} // convert
};
///////////////////////////////////////
// QuickCheck
// Generation
template<typename T>
class Gen {
public:
Gen() {};
Gen(function<T()> gen_) { gen = function<T()>(gen_); }
function<T()> gen;
T generate() { return gen(); };
};
template<typename T>
Gen<T> arbitrary();
// Stop at a certain nesting depth.
// Give prio to basic integer expressions.
#define MAX_NESTED 5
shared_ptr<Exp> genSExp(int n) {
int i = rand() % 8;
if(n >= MAX_NESTED || i < 4) {
return newInt((rand()%2)+1);
}
auto l = genSExp(n+1);
auto r = genSExp(n+1);
int j = rand() & 3;
if(j == 0) {
return newPlus(l,r);
}
if(j == 1) {
return newMin(l,r);
}
// j == 2
return newMult(l,r);
}
template<>
Gen<shared_ptr<Exp>> arbitrary() {
return Gen<shared_ptr<Exp>>([] () -> shared_ptr<Exp> {
return genSExp(0); });
}
void genExp() {
auto e = arbitrary<shared_ptr<Exp>>();
cout << "\nRandom expressions\n";
for(int i=0; i < 20; i++) {
cout << "\n" << e.generate()->show();
}
}
// Properties
template<typename T>
void quickCheck(bool p(T)) {
Gen<T> g = arbitrary<T>();
for(int i =0; i < 20; i++) {
auto b = p(g.generate());
if (b) {
cout << "\n +++ OK";
} else {
cout << "\n *** Failed";
}
}
}
// 1. Evaluate e
// 2. (a) Convert e to VM code.
// (b) Run VM code.
// Property states that both cases must yield the same result.
bool prop1(shared_ptr<Exp> e) {
return e->eval() == VM(e->convert()).run();
}
// Further properties (todo, requires further generators)
// 1. Run VM code
// 2. (b) Convert VM code to Exp
// (a) Evaluate Exp
void testQC() {
cout << "\n**** prop1 \n";
quickCheck<shared_ptr<Exp>>(prop1);
}
///////////////////////////////////////
// Examples
void testVM() {
{
vector<Code_t> cs{
ONE, TWO, TWO, PLUS, MULT
};
VM(cs).showRunConvert();
}
{
vector<Code_t> cs{
ONE, TWO, PLUS, TWO, MULT
};
VM(cs).showRunConvert();
}
}
void testExp() {
auto e = newPlus(newMult(newInt(1),newInt(2)), newInt(1));
auto run = [](shared_ptr<Exp> e) {
cout << "\n Exp yields " << e->eval();
auto vm = VM(e->convert());
vm.showRunConvert();
};
run(e);
}
int main() {
// testVM();
// testExp();
// genExp();
testQC();
}
