*“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.

Hi Eric, I did almost the same stuff years ago, sometimes returning and playing with it. https://code.google.com/p/catatonic/ (look at the commit history for where the stuff is). In the meantime I prefer to simply do it in Haskell as it causes me _much_ less headaches.

Cheers, and keep up the good work.

I’m probably missing some thing obvious, but why not let the compiler do the heavy lifting:

`template<typename T>`

struct Const_ {

T value;

Const_(T _val)

: value(_val)

{ }

};

template<typename T>

inline Const_<T> Const(T value)

{

return Const_<T>(value);

}

template<typename X, typename Y>

struct Add_ {

const X& x;

const Y& y;

Add_(const X& _x, const Y& _y)

: x(_x), y(_y)

{ }

};

template<typename X, typename Y>

inline Add_<X,Y> Add(const X& x, const Y& y)

{

return Add_<X,Y>(x, y);

}

template<typename X, typename Y>

struct Mul_ {

const X& x;

const Y& y;

Mul_(const X& _x, const Y& _y)

: x(_x), y(_y)

{ }

};

template<typename X, typename Y>

inline Mul_<X,Y> Mul(const X& x, const Y& y)

{

return Mul_<X,Y>(x, y);

}

// evaluate value

inline int value(const Const_<int>& e)

{

return e.value;

}

template<typename X, typename Y>

inline int value(const Add_<X,Y>& e)

{

return value(e.x) + value(e.y);

}

template<typename X, typename Y>

inline int value(const Mul_<X,Y>& e)

{

return value(e.x) * value(e.y);

}

// expression

template<typename T>

inline string expr(const Const_<T>& e)

{

return to_string(e.value);

}

template<typename X, typename Y>

inline string expr(const Add_<X,Y>& e)

{

return expr(e.x).insert(0, "(")

.append(" + ").append(expr(e.y)).append(")");

}

template<typename X, typename Y>

inline string expr(const Mul_<X,Y>& e)

{

return expr(e.x).insert(0, "(")

.append(" * ").append(expr(e.y)).append(")");

}

int main()

{

int i;

auto e1 = Const(1);

i = value(e1);

assert (i == 1);

auto e2 = Add(Const(2), Const(3));

i = value(e2);

assert (i == 2 + 3);

// (2 + 3)*4

auto e3 = Mul(Add(Const(2), Const(3)), Const(4));

i = value(e3);

assert (i == (2 + 3)*4);

string s = expr(e3);

assert (s == "((2 + 3) * 4)");

`return 0;`

}

Keith “I work hard to be lazy” Lewis

That’s expression templates, and it’s a useful and not uncommon technique. Notice how your

`value`

and`expr`

algorithms are polymorphic and recursive. That mixes in a bunch of control-flow and data structure details in with the algorithm.The point of

`Fix`

and`cata`

is to isolate the data structure from the recursion from the algorithm. The data structure is not recursive — the recursion is externalized by`Fix`

. And the algorithm is not recursive — the recursion is externalized by`cata`

. Notice how the algorithm,`alg`

is neither recursive nor polymorphic. You say how to handle one level of the tree, and the rest is generated automatically. I think it’s very interesting.I agree that this is very interesting. It is true that the Y-combinator can hide the recursion, but your

`alg_visitor`

is polymorphic and it is not clear what advantage writinghas over

Can you ELI5? Or, better, since this isn’t something amenable to that, pretend we are pitching to Paul Graham and he is looking at the code side-by-side. What are the benefits with the more complicated approach aside from the coolness factor? I know about your terrific work on Proto and sincerely wonder about what lesson from that you are conveying.

BTW, great blog. I really enjoy reading it.

`alg_visitor`

isnotpolymorphic. Look again. Neither the struct or the overloaded function call operators are templates.`alg_visitor`

takes an expression where the left and right children are ordinary ints, so this:is simply adding two integers and returning the result. In the code you wrote, this:

is recursively evaluating

`value`

on a left subtree of unknown depth, ditto for the right, and then adding the result.It probably doesn’t make a big different for this little case, but every time you write an algorithm, you’ll be thinking about your algorithm

andabout the recursive evaluation. I’ll just be thinking about the algorithm.