Pages

About Me - 关于我

My photo
Madison, WI, United States
Joy Young ~~

2012/07/21

Y-combinator in C++

YCombinator serves as an important role in lamda calculas. I was not interested in it until C++ introduced lamda function as a new feature in C++ 11. Then C++ is facing a same critical issue that rises in lamda calculas: As a lamda function is nameless, how could we write a recursive lamda function?
In lamda calculas, it is extremly difficult. The research on this topic results in the birth of Y-combinator, which is one of the most beatiful operator in mathematics and MIT math department adpot it as its department elblem. Y-combinator can convert a non-recursive version of a function into a recursive one. I was wondering if it is possible to implement Y-combinator in C++. Unfortuately, a real Y-combinator is not possible, because in lamda calculas, the Y combinator cant be recursive either. But, inspired by a post on stack overflow, we can relax this restriction: why can't we simply write a Y combinator in a recursive way in C++. I finally got a solution to it:
The following code must run with C++11 support.


//inspired by & referencing a post on stack overflow
#include <functional>
#include <iostream>
using namespace std;
template<class ArgType, class RetType>
function<RetType(ArgType)> YCombinator(function<RetType(function<RetType(ArgType)>, ArgType)> pseudo_recur_func)
{
  return bind(pseudo_recur_func, bind(&YCombinator<ArgType, RetType>, pseudo_recur_func), placeholders::_1);
}

int main()
{

       //pass a pseudo-recursive lambda function (in the sense that the 'self' argument is actually not itself)
      //to Y Combinator, which returns an equivalent real-recusive function of lambda.
       auto fibonacci = YCombinator<int, int>(
              [](function<int(int)> self , int n){return n <= 1 ? 1 : self(n - 2) + self(n - 1);}//this is the pseudo recusive lambda
              );
       //test 0~9
       for(int i = 0; i < 10; ++i)
              cout<<fibonacci(i)<<ends;
       return 0;
}

1 comment:

  1. A "real Y-combinator" is possible. See http://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/.

    Your code is faster than my code. However, none beats the performance of the new proposal to the C++ committee: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html

    ReplyDelete