“I think F-algebras would be useful in Proto.” That’s how Bartosz Milewski planted the seed in my head that has now matured into this blog post. Bartosz had been writing a blog post about F-algebras, and in a bid to get me to review it, he dangled the Proto carrot. I bit.

In F-algebras, the evaluation of an expression is separate from the recursion. The algebra specifies how expression trees of one level are evaluated, and the rest is handled by a catamorphism, which is written once and shared across all algebras. I’m a lazy programmer. I’m also a sucker for some pretty math. So I was hooked.

Bartosz’s code is in Haskell, so my first step was to port it to C++. The rest of this post presents my port of the F-algebra code to C++11. You’ll want to first read Bartosz’ post, which is where the real meat is. When it all makes sense, come back here and see how this all maps to C++.

Disclaimer: This is not intended to be a readable introduction to F-algebras. For that read Bartosz’ blog.

The ExprF type in Haskell

Bartosz uses a simple expression tree as his driving example. It looks like this:

data ExprF a = Const Int
             | Add a a
             | Mul a a

type Expr = Fix ExprF

Of note is the fact that ExprF is not recursive; that is, ExprF isn’t implemented in terms of itself. Yet he claims this is a tree data structure, and trees are recursive. What gives?

The answer is that the recursion is provided externally by a type constructor called Fix. If ExprF Int is a tree of one level, and ExprF (ExprF Int) is a tree of two levels, then Fix ExprF is a tree of infinite levels. How do you know when you’ve reached infinity? When one more gets you back where you started. That’s a fixed point, and Fix is a fixed point. It fakes up an infinite number of applications of its parameter F. For any type constructor F, the type Fix F is such that another application of F gets you back to where you started. Let’s look at how Fix is defined.

The Fix Type

Fix lets you create recursive data structures from a non-recursive shell. Here’s the Haskell. I include the unFix function here as well.

newtype Fix f = Fx (f (Fix f))

unFix :: Fix f -> f (Fix f)
unFix (Fx x) = x

Here, f is a unary type constructor, and Fx is a data constructor that takes an f (Fix f) and returns a Fix f. In C++, a unary type constructor is a class template that takes one parameter. Fix, then, is a template that takes a unary class template as a parameter, and Fx is a function that returns a Fix:

template<template<typename> class F>
struct Fix
  : F<Fix<F>>
{
    explicit Fix(F<Fix<F>> f)
      : F<Fix<F>>(f)
    {}
};

template<template<typename> class F>
Fix<F> Fx(F<Fix<F>> f)
{
    return Fix<F>{f};
}

template<template<typename> class F>
F<Fix<F>> unFix(Fix<F> f)
{
    return f;
}    

From the C++ we can see that Fix really is a fixed point. Fix<F> inherits from F<Fix<F>>. Inheritance is an IS-A relationship, so a Fix<F> really is a F<Fix<F>>. (Whether you consider the inverse to be true — that is, whether a F<Fix<F>> is a Fix<F> — depends on how literal-minded you are. For my purposes, the Fx function makes it so.)

Back to Haskell. With Bartosz’ definition of ExprF and Fix, we can create expression trees of arbitrary depth as with the following somewhat verbose example:

testExpr = Fx $ 
               (Fx $ (Fx $ Const 2) `Add` (Fx $ Const 3))
                `Mul` (Fx $ Const 4)

But what is the best way to express ExprF in C++? That’s not obvious.

The ExprF type in C++

Let’s look again at the definition of ExprF in Haskell.

data ExprF a = Const Int
             | Add a a
             | Mul a a

We can read this as follows: if someone gives us an ExprF a, it could contain either a Const Int, an Add a a, or a Mul a a. This either/or spiel sounds a lot like a union. We could hack something like this up with C++11’s unrestricted unions, but Boost gives us a nicer way: boost::variant. Without further ado, here’s how I ported ExprF to C++:

struct Const_
{
    int value;
};

template<typename A>
struct Add_
{
    A left;
    A right;
};

template<typename A>
struct Mul_
{
    A left;
    A right;
};

template<typename A>
using ExprF_ =
    boost::variant<
        Const_
      , boost::recursive_wrapper<Add_<A> >
      , boost::recursive_wrapper<Mul_<A> >
    >;

template<typename A>
struct ExprF
  : ExprF_<A>
{
    typedef ExprF<A> tag;
    ExprF(Const_ c) : ExprF_<A>(c) {}
    ExprF(Add_<A> c) : ExprF_<A>(c) {}
    ExprF(Mul_<A> c) : ExprF_<A>(c) {}
};

using Expr = Fix<ExprF>;

This is verbose but mostly straightforward. But wait, what’s going on with boost::recursive_wrapper? Isn’t ExprF supposed to be non-recursive? Well yes, and technically, it still is. But once we start building trees, it is made recursive by Fix. In Haskell, recursive types are no problem. In C++ though, your struct S can’t have a member of type S. It can have a member of type S* though, and that’s essentially what boost::recursive_wrapper does for you under the covers.

Some utility functions for constructing ExprF objects will come in handy later:

template<typename A = Expr>
ExprF<A> Const(int val) {return Const_{val};}

template<typename A>
ExprF<A> Add(A a, A b) {return Add_<A>{a, b};}

template<typename A>
ExprF<A> Mul(A a, A b) {return Mul_<A>{a, b};}

The cata Function

Recursion in your data types is done externally by Fix, and recursion in your algorithms is done externally by a very general function called a catamorphism, or cata. Bartosz’ derivation of the cata function is very interesting, and I encourage you to read it. The result is here:

cata :: Functor f => (f a -> a) -> Fix f -> a
cata alg o = alg . fmap (cata alg) . unFix o

We read this, as we do all mathematical function compositions, from right to left. unFix o has the effect of unpacking one level of our recursive, fixed-point data structure. That yields a Functor that we can fmap over. Even without knowing how fmap is implemented for our type, we can see that it will be calling cata alg recursively. (It’s not clear at this point how the recursion ever ends. We’ll see that in a bit.)

This is cata in C++. Short and sweet … almost.

template<typename Alg, template<typename> class F>
???? cata(Alg alg, Fix<F> o)
{
    using std::placeholders::_1;
    return alg(fmap(std::bind(&cata<Alg, F>, alg, _1),
                    unFix(o)));
}

In Haskell, when you pass one argument to a function that expects two, you get a function that takes one argument. Cool. What you get when you do that in C++ is a compiler error. 😛 So instead, I use the very handy std::bind. Lambdas are more fashionable, but hey I’m a bit old-fashioned.

The only snag is when we try to declare the return type. cata returns whatever alg returns when passed a … what? Well, whatever fmap returns. But the type returned by fmap depends on a recursive call to cata, and we get stuck in a Catch-22 trying to compute it. What we can say about the return type of fmap is that it will be some instance of template F, but we don’t know which. So, I cheat:

// A horrible hack for the purpose of computing
// cata's return type. AnyF<F> stands in for a F<T>
// when T is unknown.
template<template<typename> class F>
struct AnyF
{
    template<typename T>
    operator F<T> &() const;
};

template<typename Alg, template<typename> class F>
typename std::result_of<Alg(AnyF<F>)>::type
cata(Alg alg, Fix<F> o)
{
    using std::placeholders::_1;
    return alg(fmap(std::bind(&cata<Alg, F>, alg, _1),
                    unFix(o)));
}

I won’t dwell on the horribleness of this hack, why it works, and why sometimes it won’t. The less said the better.

fmap

If you’re a Haskeller, you know that fmap means Functors. (That’s the mathematical “Functor” with a capital “F”, which is probably different from the C++ thing you may be familiar with.) If you’re not a Haskeller, here’s the skinny: Given an instance of a class template F<A> and a function that maps from A to B, it gives you a F<B> by doing something. That something is different for every fmap-able type.

Functor in Haskell is a type class. Type classes and instances are like concepts and concept maps in C++, if only we had them. So how should something like Haskell’s Functor type class be translated into C++? It’s an interesting question. For now, I make a simplifying assumption: all types modeling the “Functor” concept in C++ are implemented as a boost::variant. (Obviously, that’s the case for ExprF.)

Here is fmap in C++:

template<typename Fun, typename Tag>
struct functor_visitor;

template<typename Fun, typename Fa>
typename
    functor_visitor<Fun, typename Fa::tag>::result_type
fmap(Fun f, Fa fa)
{
    return boost::apply_visitor(
        functor_visitor<Fun, typename Fa::tag>{f}, fa);
}

boost::apply_visitor is a simple wrapper that checks to see which slot is occupied in the variant and dispatches to the right handler in functor_visitor. That is where you put the fmap logic for your type. Here is how functor_visitor is implemented for ExprF:

template<typename Fun, typename A>
struct functor_visitor<Fun, ExprF<A>>
  : boost::static_visitor<
        ExprF<typename std::result_of<Fun(A)>::type>>
{
    typedef typename std::result_of<Fun(A)>::type B;

    explicit functor_visitor(Fun f)
      : f_(f)
    {}

    ExprF<B> operator()(Const_ i) const
    {
        return Const<B>(i.value);
    }

    ExprF<B> operator()(Add_<A> e) const
    {
        return Add(f_(e.left), f_(e.right));
    }

    ExprF<B> operator()(Mul_<A> e) const
    {
        return Mul(f_(e.left), f_(e.right));
    }
private:
    Fun f_;
};

So, fmap with a function and an ExprF<A> does one of three things depending on what’s in the ExprF. Each operator() overload handles one possible case, and they all return ExprF<B>, where B is what Fun returns when passed an A.

Looking at cata, the function we’ll be fmap-ing over will be std::bind(&cata<Alg, F>, alg, _1). If the ExprF<A> contains an Add_ or a Mul_, then we end up recursively invoking cata. But when we reach a Const_, we don’t recurse. That’s good, because otherwise cata would never return!

F-algebra

So what is alg? That’s the best part: you decide! It’s an algebra; a way build expressions out of symbols and evaluate them. Below is a simple algebra in Haskell that will cause cata to evaluate the expression tree in a meaningful way:

alg :: ExprF Int -> Int

alg (Const i)   = i
alg (x `Add` y) = x + y
alg (x `Mul` y) = x * y

This is what it looks like in C++:

struct alg_visitor
  : boost::static_visitor<int>
{
    int operator()(Const_ i) const
    {
        return i.value;
    }

    int operator()(Add_<int> e) const
    {
        return e.left + e.right;
    }

    int operator()(Mul_<int> e) const
    {
        return e.left * e.right;
    }
};

int alg(ExprF<int> e)
{
    return boost::apply_visitor(alg_visitor{}, e);
}

And here’s an example of cata and alg evaluating an expression tree:

// (2+3)*4 == 20
Expr testExpr =
    Fx(Mul(
        Fx(Add(
            Fx(Const(2)),
            Fx(Const(3))
        )),
        Fx(Const(4))
    ));
int z = cata(alg, testExpr);
std::cout << z << std::endl;

This prints 20 like you might expect. You could easily define other algebras that would cause the same expression tree to be evaluated in different ways.

Summary

Notice that alg is not recursive. Something really cool has happened here. We only had to specify how to handle trees of one level, and for free we’re able to evaluate trees of any depth. Everything else is handled by Fix and cata.

Why do I care, besides the fact that it’s fun and cool? Boost.Proto, my library for building embedded domain-specific languages in C++, has a little DSL for specifying how expressions should be evaluated. In that DSL, the tree traversal logic is mixed in with the rest of the algorithm. This makes it tricky to write Proto algorithms. If only there were a way to get recursive evaluation for free while only specifying the interesting bits … Hence my interest in F-algebras.

Bartosz and I have been discussing how to extend this to work with my use cases. We’ve found that, when combined with the State monad, the cata function can be made to do folds, an important part of many expression evaluation schemes. But perhaps I’ll save that for later.

You can find this code in a slightly generalized form at my github repo. There you can also find my implementation of the State monad.