Open Is Good

Case Study: AST

struct Node {
    virtual double value() = 0;
};

const, memory management etc elided, code formatted to "slide style"

Case Study: AST

struct Number : Node {
  Number(double value) : val(value ) { }

  double value() override {
    return val;
  }

  double val;
};

Case Study: AST

struct Plus : Node {
    Plus(Node& left, Node& right)
    : left(left), right(right) { }

  double value() override {
    return left.value() + right.value();
  }

  Node &left, &right;
};

Case Study: AST

struct Times : Node {
    Times(Node& left, Node& right)
    : left(left), right(right) { }

    double value() override {
        return left.value() * right.value();
    }

    Node &left, &right;
};

Case Study: AST

int main() {
    Node* expr =
        new Times(*new Number(2),
                  *new Plus(*new Number(3), *new Number(4)));

    cout << expr->value() << "\n"; // 14

    return 0;
}

Case Study: AST

int main() {
    Node* expr =
        new Times(*new Number(2),
                  *new Plus(*new Number(3), *new Number(4)));

    cout /* string to RPN */
        << " = " << expr->value() << "\n";
    // 2 3 4 * + = 14

    return 0;
}

AST: Add a Virtual Function?

...if it needs to be virtual, make it a member function ???

struct Node {
    // as before
    virtual string toRPN() = 0;
};

struct Plus : Node {
    // as before
  string toRPN() override {
    return left.toRPN() + " " + right.toRPN() + " +";
  }
};

// same for Number and Times

banana -> gorilla -> jungle

AST: Type Switch?

string toRPN(Node& node) {
    if (auto expr = dynamic_cast<Number*>(&node)) {
        return to_string(expr->value());
    } else if (auto expr = dynamic_cast<Plus*>(&node)) {
        return toRPN(expr->left) + " " +
            toRPN(expr->right) + " +";
    } else if (auto expr = dynamic_cast<Times*>(&node)) {
        return toRPN(expr->left) + " " +
            toRPN(expr->right) + " *";
    }
    throw runtime_error("unknown node type");
}

needs modification each time a new Node subtype is added

AST: Visitor?


struct Node {
    // as before
    struct Visitor {
        virtual void accept(Number& expr) = 0;
        virtual void accept(Plus& expr) = 0;
        virtual void accept(Times& expr) = 0;
    };

    virtual void visit(Visitor& viz) = 0;
};

AST: Visitor?

struct Number : Node {
  // as before
  void visit(Visitor& viz) override { viz.accept(*this);
  }
};

struct Plus : Node {
  void visit(Visitor& viz) override { viz.accept(*this); }
};

struct Times : Node {
    void visit(Visitor& viz) override { viz.accept(*this); }
};

AST: Visitor?

struct RPNVisitor : Node::Visitor {
  string result;
  void accept(Number& expr) {
    result = to_string(expr.val);
  }
  void accept(Plus& expr) {
    expr.left.visit(*this);
    string l = result;
    expr.right.visit(*this);
    result = l + " " + result + " +";
  }
  void accept(Times& expr) { ... }
};

ugh, yuck!

AST: Visitor?


string toRPN(Node& node) {
  RPNVisitor viz;
  node.visit(viz);
  return viz.result;
}

my, that was a lot of work

and, what does it even gain us?

AST: Function Table?

using RPNFormatter = string (*)(Node&);
unordered_map<type_index, RPNFormatter> RPNformatters;

string toRPN(Node& node) {
  return RPNformatters[typeid(node)](node);
}

AST: Function Table?

namespace { struct Init {
  Init() {
    RPNformatters[typeid(Number)] = [](Node& node) {
     return to_string(static_cast<Number&>(node).val); };
    RPNformatters[typeid(Plus)] = [](Node& node) {
     auto expr = static_cast<Plus&>(node);
     return toRPN(expr.left) + " " + toRPN(expr.right)
       + " +"; };
    // same for Time
  }
};
Init init;
} }

not bad, actually

	Expense+Jet	Public+Bus+Train	Cab
Role	R,X	R,X	R,X
Employee	R,X	E,P	R,X
Manager	R,X	E,P	M,C
Founder	F,X	F,X	F,X

		gcc6	clang6
normal inheritance
virtual function	1-method	16%	17%
double dispatch	2-method	25%	35%
virtual inheritance
virtual function	1-method	19%	17%
double dispatch	2-method	40%	33%

Open Is Good