C++ CPS

cps_fib.cpp

#include <iostream>

int fib(int n)
{
  if (n <= 2)
    return 1;
  else
    return fib(n - 1)
           + fib(n - 2);
}

#if 0
// Runtime CPS
#include <functional>
void fib_cps(int n, std::function<void(int)> k)
{
  if (n <= 2)
    k(1);
  else
    fib_cps(n - 1, [n,&k](int r1){
      fib_cps(n - 2, [r1,&k](int r2){ k(r1 + r2); }); });
}
#else
// Complite-time CPS
template <int N>
struct fib_cps {
  template <class F>
  static void invoke(F k) {
    fib_cps<N-1>::invoke([&k](int r1){
      fib_cps<N-2>::invoke([r1,&k](int r2){ k(r1 + r2); }); });
  }
};
template <>
struct fib_cps<2> {
  template <class F>
  static void invoke(F k) { k(1); }
};
template <>
struct fib_cps<1> {
  template <class F>
  static void invoke(F k) { k(1); }
};
#endif

int main()
{
  std::cout << fib(10) << std::endl;
  //fib_cps(10, [](int r){ std::cout << r << std::endl; });
  fib_cps<10>::invoke([](int r){ std::cout << r << std::endl; });
}

gcc 4.6.3 with -O1 --> optimized to constant(55) on CT/CPS
gcc 4.6.3 with -O3 --> NOT optimized on RT/CPS

gcc 4.6.3 with -O3 --> NOT optimized on RT/func