Fixed point combinators in C++

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?

From stackoverflow 1800 INFORMATION

• If you want to do functional programming, why not make your life a lot easier and use a functional language?

  1800 INFORMATION : Because my wife and son like to eat?

  John Millikin : So write C++ for food, and Haskell for play. There's no excuse for code like in the OP to exist, and those libraries should never have gone beyond "practical joke" stage.
  From Hugh Allen

• Here is the same code converted into boost::bind notice the y-combinator and it's 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;
  }
  

  1800 INFORMATION : That's precisely what I was looking for. Wish I could vote you up twice
  From witkamp

• 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.

  From DrPizza