Wednesday, June 22, 2016

Modeling Recursive Sum Types in C++11 Using boost::variant

It's been a while. But here's something cool.

I used to love pattern matching with sum types in OCaml in college. But I also love how useful and ubiquitous C++ is. So I wanted pattern matching and sum types, but in C++. Well, people say boost::variant can be used as a sum type. The library boost::variant is fairly ubiquitous, well-maintained, and can even run on C++98, the older C++ standard. I can see how discriminated unions can implement “flat” sum types, but can it be used to implement recursive sum types?

Well, I decided to try it. It turns out, with a bit of scaffolding on my part, I was able to implement a recursive sum type. I tried to model the quintessential recursive type, the natural number, which is either zero or the successor to some other number. The following code shows the results of my efforts.

// sum_type.cpp
#include <iostream>
#include <boost/variant.hpp>
#include <memory>

struct zero {};
class successor;

typedef boost::variant<zero,successor> number;

class successor
{
private:
    std::unique_ptr<const number> num;
public:
    successor() = delete;
    successor(const number& n) : num(new number(n)) {}
    successor(const successor& s) : num(new number(s.n())) {}
    successor(successor&& s) : num(std::move(s.num)) {}

    const number& n() const {
        return *num;
    }
};

struct match_count : public boost::static_visitor<int>
{
    int operator ()(const zero& z) const
    {
        return 0;
    }
    int operator ()(const successor& s) const
    {
        // Do NOT use `return (*this)(s.n()) + 1`
        return boost::apply_visitor(*this, s.n()) + 1;
    }
};

number add(const number& a, const number& b)
{
    /*
     match a with
        0 => b
        S n => S add(n, b)
    */
    struct match_a : public boost::static_visitor
    {
        const number b;
        match_a(const number& b) : b(b) {}
        number operator()(const zero& a) const
        {
            return b;
        }
        number operator()(const successor& a) const
        {
            return successor(add(a.n(), b));
        }
    };
    return  boost::apply_visitor(match_a(b), a);
}

int main() {
    number a = zero();
    number b = successor(a);
    number c = successor(b);
    number d = add(b,c);
    match_count mc;
    int c_count = boost::apply_visitor(mc, c);
    int b_count = boost::apply_visitor(mc, b);
    int a_count = boost::apply_visitor(mc, a);
    int added = boost::apply_visitor(mc, d);
    std::cout << "a is " << a_count << std::endl;
    std::cout << "b is " << b_count << std::endl;
    std::cout << "c is " << c_count << std::endl;
    std::cout << "a + b is " << added << std::endl;
}

Output:

[ djhaskin987@djhaskin987-S301LA:~ ]$ g++ -o sum_type -std=c++11 sum_type.cpp
[ djhaskin987@djhaskin987-S301LA:~ ]$ ./sum_type
a is 0
b is 1
c is 2
a + b is 3
How about that?
I modelled the type as a discriminated union between “zero” and “successor”. Some interesting things I learned when I did this, or at least some things to note:
  • As long as you manage memory properly in the recursive cases, they work fine as part of the sum type using boost::variant.
  • It’s okay to have a type with no members (e.g. struct zero {};)
  • You can define anonymous classes inside function definitions. Here, they aren’t anonymous, but experimentation will show that you can (in C++11).
  • You can call functions recursively when you define structs inside those functions. That’s nice.
  • When defining “matching” structs inside functions, try to match variable names with class member names that they are used to construct. This saves time later reasoning about what’s going on.