Continuation-passing style (wiki) is a theoretical concept from functional programming that Scheme came up with in 1975. Well now that it’s 2010 and functions are first-class citizens of the C++ universe, too, along with closures. So I figured.. can I write CPS in C++? Yes, I can! We can have functional programming now!
Here’s Scheme example from the wiki:
(define (factorial n k)
(cps= n 0 (lambda (b)
(cps-if b
(k 1)
(cps- n 1 (lambda (nm1)
(factorial nm1 (lambda (f)
(cps* n f k)))))))))
And here’s what I made with C++
void factorial(int n, function<void (int)> k) {
cps2(equal_to<int>(), 0, n,
[&](bool b){cps_ifthen(b,
[&](){k(1);},
[&](){cps2(minus<int>(), n, 1,
[&](int nm1){factorial(nm1,
[&](int f){cps2(multiplies<int>(), n, f, k);});});});});
}
To compile the function above, I had to define a couple CPS primitives, of course, just like in Scheme:
#include <iostream>
#include <functional>
#include <cmath>
using namespace std;
template<typename F, typename A, typename K>
void cps1(F f, A a, K k) { k(f(a)); }
template<typename F, typename A1, typename A2, typename K>
void cps2(F f, A1 a1, A2 a2, K k) { k(f(a1, a2)); }
template<typename F1, typename F2>
void cps_ifthen(bool x, F1 k1, F2 k2) {x ? k1() : k2();}
void factorial(int n, function<void (int)> k)
{
cps2(equal_to<int>(), 0, n,
[&](bool b){cps_ifthen(b,
[&](){k(1);},
[&](){cps2(minus<int>(), n, 1,
[&](int nm1){factorial(nm1,
[&](int f){cps2(multiplies<int>(), n, f, k);});});});});
}
int main()
{
for(int i=0; i<10; ++i) {
cout << "F("<<i<<"): " << tgamma(i+1) << " or ";
factorial(i, [](int a) {cout << a << '\n';});
}
}
test run:
cubbi@gummadoon ~ $ g++ -std=c++0x -pedantic -Wall -Wextra -o cps cps.cc
cubbi@gummadoon ~ $ ./cps
F(0): 1 or 1
F(1): 1 or 1
F(2): 2 or 2
F(3): 6 or 6
F(4): 24 or 24
F(5): 120 or 120
F(6): 720 or 720
F(7): 5040 or 5040
F(8): 40320 or 40320
F(9): 362880 or 362880
I could simplify cps1 and cps2 into a variadic version
template<typename K, typename F, typename... A>
void cps(K k, F f, A... a) { k(f(a...)); }
but then the order of arguments would make it look too different for neat juxtaposition, since variadic parameter pack must be in the end of the argument list.
Crossposted from Livejournal