Fixed point combinators in C++

Question

I'm interested in actual examples of using fixed point combinators (such as the y-combinator in C++. Have you ever used a fixed point combinator with egg or bind in real live code?

I found this example in egg a little dense:

void egg_example()
{
    using bll::_1;
    using bll::_2;

    int r =
        fix2(
            bll::ret<int>(
                // \(f,a) -> a == 0 ? 1 : a * f(a-1)
                bll::if_then_else_return( _2 == 0,
                    1,
                    _2 * lazy(_1)(_2 - 1)
                )
            )
        ) (5);

    BOOST_CHECK(r == 5*4*3*2*1);
}

Can you explain how this all works?

Is there a nice simple example perhaps using bind with perhaps fewer dependancies than this one?

Alamo

If you write code that looks that that nobody will ever be able to maintain it, including yourself. – Misdeem

My point is not that I really want to write fixed point combinators or lambdas in C++, but rather that an example of those in C++ would be edifying for someone like me who isn't all that familiar with languages in which they might be more useful. – Alamo

Answer 1

Here is the same code converted into boost::bind notice the y-combinator and its application site in the main function. I hope this helps.

#include <boost/function.hpp>
#include <boost/bind.hpp>
#include <iostream>

// Y-combinator compatible factorial
int fact(boost::function<int(int)> f,int v)
{
  if(v == 0)
    return 1;
  else
    return v * f(v -1);
}

// Y-combinator for the int type
boost::function<int(int)>
    y(boost::function<int(boost::function<int(int)>,int)> f)
{
  return boost::bind(f,boost::bind(&y,f),_1);
}


int main(int argc,char** argv)
{
  boost::function<int(int)> factorial = y(fact);
  std::cout << factorial(5) << std::endl;
  return 0;
}

Moral

y references it self explicitly. This should not be an accepted answer. – Creole

Answer 2

#include <functional>
#include <iostream>

template <typename Lamba, typename Type>
auto y (std::function<Type(Lamba, Type)> f) -> std::function<Type(Type)>
{
    return std::bind(f, std::bind(&y<Lamba, Type>, f), std::placeholders::_1);
}

int main(int argc,char** argv)
{
    std::cout << y < std::function<int(int)>, int> ([](std::function<int(int)> f, int x) {
        return x == 0 ? 1 : x * f(x - 1);
    }) (5) << std::endl;
    return 0;
}

Beanie

Works great and is also pure C++ 11 – Annorah

The only issue with this and with the boost-based accepted answer is that, according to my readings about Y combinator, it is, strictly speaking, not allowed to name itself in its definition. – Annorah

As Tony said above this is not an Y combinator. In order to be an Y combinator it needs to be done solely using anonymous lambdas, without referencing itself explicitly and without any free variables. – Creole

Answer 3

Can you explain how this all works?

fix2 is a y-combinator (specifically, it is a combinator for functions with two arguments; the first argument is the function (for the purpose of recursion), the second argument is a "proper" function argument). It creates recursive functions.

bll::ret(...) appears to create some form of a function object, the body of which is

if(second arg == 0)
{
    return 1;
}
else
{
    return second arg * first arg(second arg - 1);
}

The "lazy" is presumably there to stop an infinite expansion of the first (function) argument (read up on the difference between lazy and strict y combinators to see why).

The code is quite horrible. Anonymous functions are nice to have, but the hackery to work around C++'s lack of syntactic support make them not worth the effort.

Spellman