Cleanest C++ code I've ever written is still verbose and ugly

validity_one.cpp

// Based on validity.py which is copyright (c) Feb 2000, by Denys
// Duchier, Universitaet des Saarlandes
//
// Transliterated (badly) from Python to C++ by Johnicholas Hines,
// but with the two-continuation model changed to the one-continuation model.
// (The failure continuation is the C++ stack.)

#include <string>
#include <tr1/memory>
using std::tr1::shared_ptr;

// Forward declarations
class Answer;
typedef shared_ptr<Answer> AnswerPtr;
class Environment;
typedef shared_ptr<Environment> EnvironmentPtr;
class Formula;
typedef shared_ptr<Formula> FormulaPtr;
class LookupHandler;
typedef shared_ptr<LookupHandler> LookupHandlerPtr;

// Represents an answer to the question 'is this formula valid?'
class Answer {
public:
  virtual void print() = 0;
  virtual bool isfail() = 0;
};

// An environment maps names to booleans.
class Environment {
public:
  virtual AnswerPtr lookup(std::string name, LookupHandlerPtr handler) = 0;
  virtual void print() = 0;
};

// The empty environment answers every lookup with not found.
class Empty : public Environment {
public:
  AnswerPtr lookup(std::string name, LookupHandlerPtr handler);
  void print();
};

// These represent the tasks still to be done in case of success.
class SuccessK {
public:
  virtual AnswerPtr success(EnvironmentPtr env) = 0;
};
typedef shared_ptr<SuccessK> SuccessKPtr;

// NotValidK is a success continuation that constructs a No answer.
class NotValidK : public SuccessK {
public:
  AnswerPtr success(EnvironmentPtr env);
};

// Formula represents a boolean expression. Note that isvalid is not virtual!
class Formula {
public:
  virtual AnswerPtr satisfy(EnvironmentPtr env, SuccessKPtr yes) = 0;
  virtual AnswerPtr falsify(EnvironmentPtr env, SuccessKPtr yes) = 0;
  virtual void print() = 0;
  AnswerPtr isvalid() {
    EnvironmentPtr empty(new Empty());
    SuccessKPtr notvalidk(new NotValidK());
    return falsify(empty, notvalidk);
  }
};

// LookupHandler handles lookups by extending an environment.
class LookupHandler {
public:
  LookupHandler(EnvironmentPtr env, SuccessKPtr yes, bool desired_value)
    : env(env), yes(yes), desired_value(desired_value) {}
  AnswerPtr found(bool actual_value);
  AnswerPtr notfound(std::string name);
private:
  EnvironmentPtr env;
  SuccessKPtr yes;
  bool desired_value;
};

// SatAndK represents the task of satisfying the second formula of an And.
class SatAndK : public SuccessK {
public:
  SatAndK(FormulaPtr formula, SuccessKPtr yes)
    : formula(formula), yes(yes) {} 
  AnswerPtr success(EnvironmentPtr env);
private:
  FormulaPtr formula;
  SuccessKPtr yes;
};

// And represents the conjunction of the two formulas.
class And : public Formula {
public:
  And(FormulaPtr p, FormulaPtr q)
    : p(p), q(q) {}
  AnswerPtr satisfy(EnvironmentPtr env, SuccessKPtr yes);
  AnswerPtr falsify(EnvironmentPtr env, SuccessKPtr yes);
  void print();
private:
  FormulaPtr p;
  FormulaPtr q;
};

// FalsifyOrK represents the task of falsifying the second formula of an Or.
class FalsifyOrK : public SuccessK {
public:
  FalsifyOrK(FormulaPtr formula, SuccessKPtr yes)
    : formula(formula), yes(yes) {} 
  AnswerPtr success(EnvironmentPtr env);
private:
  FormulaPtr formula;
  SuccessKPtr yes;
};

// Or represents the disjunction aka alternation of two formulas.
class Or : public Formula {
public:
  Or(FormulaPtr p, FormulaPtr q)
    : p(p), q(q) {}
  AnswerPtr satisfy(EnvironmentPtr env, SuccessKPtr yes);
  AnswerPtr falsify(EnvironmentPtr env, SuccessKPtr yes);
  void print();
private:
  FormulaPtr p;
  FormulaPtr q;
};

// Bind represents a nonempty environment.
class Bind : public Environment {
public:
  Bind(std::string name, bool value, EnvironmentPtr env)
    : name(name), value(value), env(env) {}
  AnswerPtr lookup(std::string name, LookupHandlerPtr handler);
  void print();
private:
  std::string name;
  bool value;
  EnvironmentPtr env;
};

// Var represents an occurrence of a propositional variable.
class Var : public Formula {
public:
  Var(std::string name)
    : name(name) {}
  AnswerPtr satisfy(EnvironmentPtr env, SuccessKPtr yes);
  AnswerPtr falsify(EnvironmentPtr env, SuccessKPtr yes);
  void print();
private:
  std::string name;
};

// Not represents the negation of a formula.
class Not : public Formula {
public:
  Not(FormulaPtr formula)
    : formula(formula) {}
  AnswerPtr satisfy(EnvironmentPtr env, SuccessKPtr yes);
  AnswerPtr falsify(EnvironmentPtr env, SuccessKPtr yes);
  void print();
private:
  FormulaPtr formula;
};

// No is an answer. The env is one possible way that it could be false.
class No : public Answer {
public:
  No(EnvironmentPtr env)
    : env(env) {}
  void print();
  bool isfail() { return false; }
private:
  EnvironmentPtr env;
};

// Yes is an answer to the question 'is this formula valid?'.
class Yes : public Answer {
public:
  void print();
  bool isfail() { return true; }
};

/////////////////////////////////////////////////////////// End of declarations

#include <iostream>

AnswerPtr SatAndK::success(EnvironmentPtr env) {
  return formula->satisfy(env, yes);
}

AnswerPtr And::satisfy(EnvironmentPtr env, SuccessKPtr yes) {
  SuccessKPtr todo(new SatAndK(q, yes));
  return p->satisfy(env, todo);
}

AnswerPtr And::falsify(EnvironmentPtr env, SuccessKPtr yes) {
  AnswerPtr a = p->falsify(env, yes);
  if (a->isfail()) {
    return q->falsify(env, yes);
  } else {
    return a;
  }
}

void And::print() {
  std::cout << "AND(";
  p->print();
  std::cout << ", ";
  q->print();
  std::cout << ")";
}

AnswerPtr FalsifyOrK::success(EnvironmentPtr env) {
  return formula->falsify(env, yes);
}

AnswerPtr Or::satisfy(EnvironmentPtr env, SuccessKPtr yes) {
  AnswerPtr a = p->satisfy(env, yes);
  if (a->isfail()) {
    return q->satisfy(env, yes);
  } else {
    return a;
  }
}

AnswerPtr Or::falsify(EnvironmentPtr env, SuccessKPtr yes) {
  SuccessKPtr todo(new FalsifyOrK(q, yes));
  return p->falsify(env, todo);
}

void Or::print() {
  std::cout << "OR(";
  p->print();
  std::cout << ", ";
  q->print();
  std::cout << ")";
}

AnswerPtr Bind::lookup(std::string to_find, LookupHandlerPtr handler) {
  if (name == to_find) {
    return handler->found(value);
  } else {
    return env->lookup(to_find, handler);
  }
}

void Bind::print() {
  std::cout << "BIND(\""
            << name << "\", "
            << (value?"true":"false") << ", ";
  env->print();
  std::cout << ")";
}

AnswerPtr LookupHandler::found(bool actual_value) {
  if (actual_value == desired_value) {
    return yes->success(env);
  } else {
    AnswerPtr yes(new Yes());
    return yes;
  }
}

AnswerPtr LookupHandler::notfound(std::string name) {
  EnvironmentPtr bind(new Bind(name, desired_value, env));
  return yes->success(bind);
}

AnswerPtr Var::falsify(EnvironmentPtr env, SuccessKPtr yes) {
  LookupHandlerPtr handler(new LookupHandler(env, yes, false));
  return env->lookup(name, handler);
}

AnswerPtr Var::satisfy(EnvironmentPtr env, SuccessKPtr yes) {
  LookupHandlerPtr handler(new LookupHandler(env, yes, true));
  return env->lookup(name, handler);
}

void Var::print() {
  std::cout << "VAR(\"" << name << "\")";
}

AnswerPtr Not::satisfy(EnvironmentPtr env, SuccessKPtr yes) {
  return formula->falsify(env, yes);
}

AnswerPtr Not::falsify(EnvironmentPtr env, SuccessKPtr yes) {
  return formula->satisfy(env, yes);
}

void Not::print() {
  std::cout << "NOT(";
  formula->print();
  std::cout << ")";
}

AnswerPtr Empty::lookup(std::string name, LookupHandlerPtr handler) {
  return handler->notfound(name);
}

void Empty::print() {
  std::cout << "EMPTY()";
}

void No::print() {
  std::cout << "NO(";
  env->print();
  std::cout << ")";
}

AnswerPtr NotValidK::success(EnvironmentPtr env) {
  AnswerPtr no(new No(env));
  return no;
}

void Yes::print() {
  std::cout << "YES()";
}

//////////////////////////////////////////////////////////////// End of library

#include <cassert>

bool test(FormulaPtr to_test) {
  to_test->print();
  std::cout << "\n";
  AnswerPtr answer = to_test->isvalid();
  answer->print();
  std::cout << "\n";
  return answer->isfail();
}

// Note: using temporary shared_ptrs like this is NOT EXCEPTION SAFE!
// However, I know that the code as a whole does not use exceptions,
// and it would be a pain to rewrite these trees in a flat,
// name-every-temporary form.
#define VAR(x) FormulaPtr(new Var(x))
#define AND(p, q) FormulaPtr(new And(p, q))
#define OR(p, q) FormulaPtr(new Or(p, q))
#define NOT(p) FormulaPtr(new Not(p))

int main(int argc, char* argv[]) {
  assert(test(VAR("p")) == false);
  std::cout << "\n";
  assert(test(AND(VAR("p"), VAR("p"))) == false);
  std::cout << "\n";
  assert(test(AND(VAR("p"), VAR("q"))) == false);
  std::cout << "\n";
  assert(test(OR(VAR("p"), VAR("p"))) == false);
  std::cout << "\n";
  assert(test(OR(VAR("p"), VAR("q"))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(VAR("p")), VAR("q"))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(VAR("p")), VAR("p"))) == true);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("r")),
                            OR(NOT(VAR("q")),
                               VAR("r")))),
                    VAR("r")))) == true);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("x"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("r")),
                            OR(NOT(VAR("q")),
                               VAR("r")))),
                    VAR("r"
                        ))))
         == false);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("x"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("r")),
                            OR(NOT(VAR("q")),
                               VAR("r")))),
                    VAR("r")))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("x")),
                               VAR("r")),
                            OR(NOT(VAR("q")),
                               VAR("r")))),
                    VAR("r")))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("x")),
                            OR(NOT(VAR("q")),
                               VAR("r")))),
                    VAR("r")))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("r")),
                            OR(NOT(VAR("x")),
                               VAR("r")))),
                    VAR("r")))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("r")),
                            OR(NOT(VAR("q")),
                               VAR("x")))),
                    VAR("r")))) == false);
  std::cout << "\n";
  assert(test(OR(NOT(OR(VAR("p"), VAR("q"))),
                 OR(NOT(AND(OR(NOT(VAR("p")),
                               VAR("r")),
                            OR(NOT(VAR("q")),
                               VAR("r")))),
                    VAR("x")))) == false);
  return 0;
}