Tiny AST and expression evaluator inspired by Dave Abrahams' Mutable Value Semantic talk.

mvs_ast.cpp

// Tiny AST and expression evaluator inspired by Dave Abrahams' Mutable Value Semantic talk.

#include <string> 
#include <variant>
#include <vector>
#include <iostream>
#include <map>

// Strong identifier.
struct NodeId {
    std::size_t n; 
};

// AST NODES AND TREE

struct IntNode {
    int n;
};

struct VarNode {
    std::string name;
};

struct AddNode {
    NodeId lhs, rhs;
};

using Node = std::variant<IntNode, VarNode, AddNode>;

class Ast {
public:
    NodeId new_var(const std::string& name) {
        nodes_.push_back(VarNode{name});
        return {nodes_.size() - 1};
    }

    NodeId new_int(int n) {
        nodes_.push_back(IntNode{n});
        return {nodes_.size() - 1};
    }

    NodeId new_add(NodeId lhs, NodeId rhs) {
        nodes_.push_back(AddNode{lhs, rhs});
        return {nodes_.size() - 1};
    }

    // Slight deviation from pure MVS?
    // Returned reference should not be stored.
    const Node& from_id(NodeId id) const {
        return nodes_.at(id.n);
    }

private:
    std::vector<Node> nodes_;

};

// AST EVALUATOR

using Env = std::map<std::string, int>;

struct Evaluator {
    explicit Evaluator(const Ast& ast, const Env& env)
        : ast_(ast), env_(env) {}

    int operator()(const IntNode& n) { return n.n; }

    int operator()(const VarNode& n) {
        auto it =  env_.find(n.name);
        if (it != env_.end()) {
            return it->second;
        }
        throw "unknown variable";
    }

    int operator()(const AddNode& n) {
        return std::visit(*this, ast_.from_id(n.lhs)) + 
               std::visit(*this, ast_.from_id(n.rhs));
    }

    const Ast& ast_;
    const Env& env_;
};

int main() {
    Ast ast;
    NodeId root = ast.new_add(ast.new_int(42), ast.new_var("foo"));
    const Env env = { {"foo", 2} };
    const auto result = std::visit(Evaluator{ast, env}, ast.from_id(root));
    std::cout << result << '\n';
}