Tagged: Continuation passing style

Composing Continuations

We’ve seen how to use CPS and how to write new functions which combine other CPS functions. Combining functions by nesting lambdas, while neat, is pretty convoluted and an alternative way is sometimes preferred.

Previously we had something to this effect:

auto show = [](const auto& v){std::cout << v << "\n";};
auto one_cps = [](auto&& k){return k(1);};
auto double_cps = [](auto&& v, auto&& k){return k(v*2);};

And combining those to print 2 would look something like:

auto two_cps = [&](auto&& k)
{
    return one_cps([&](auto&& v){
            return double_cps(v,k);
        });
};

two_cps(show); // prints 2

The benefit of nesting lambdas is that you can capture the result of previous computations. In this case, there isn’t any need for that and we can use the alternative of writing continuations which return new CPS functions.

For example, another way of writing the double function would be:

auto double_cont = [](auto&& v)
{
   return [=](auto&& k){return k(v*2);};
};

The return value looks almost exactly like one_cps, but in this case, instead of 1 we use v*2.

We could get an equivalent two_cps by just calling double_cont with 1 as its argument, but since this is CPS the following is far more appropriate:

// prints 4
one_cps(double_cont)(double_cont)(show);

A very important detail is that the return value of double_cont captures v by value. We have no way of distinguishing values that may expire by the time this function is called with its own continuation. Therefore, to use this with references, std::ref and std::cref are required.

These special continuation functions are actually pretty versatile and can replicate the capturing that nested lambdas do as well. All we need is a continuation that returns a continuation which returns a CPS function!

Let’s implement the add_cont_cont, which has this behaviour. We want this function to return a continuation like double_cont that captures one of the arguments to our operation. We want that continuation to return a CPS function.

Starting from the inside:

[=](auto&& k){return k(lhs+rhs);};

So we have a CPS function that adds 2 things. Lets write a function that will return this, but with a captured variable, just as with double_cont:

[=](auto&& lhs){
    return [=](auto&& k){return k(lhs+rhs);};
};

Turns out, adding more arguments is just capturing it within a lambda:

auto add_cont_cont = [](auto&& rhs)
{
    return [=](auto&& lhs){
        return [=](auto&& k){return k(lhs+rhs);};
    };
};

This can be used like this:

// prints 3
one_cps(two_cps(add_cont_cont))(show);

One last concept I want to demonstrate is a sort of “meta-continuation”. A function which takes a continuation and returns another continuation but modified in a certain way.

For example this function will take a continuation, and return a continuation that applies itself twice into a CPS function:

auto twice_meta = [](auto&& cont)
{
    return [=](auto&& v)
    {
        return [=](auto&& k)
        {
            return cont(v)(cont)(k);
        };
    };
};

It’s return value is a typical continuation function. The innermost CPS function, however, calls the captured continuation twice before passing in the final continuation k.

The final result of all of these functions is a set of easy to compose functions, albeit with a rather different syntax:

// prints 10
one_cps(twice_meta(two_cps(add_cont_cont)))(double_cont)(show);

I’ve tested on gcc-4.9, and it actually compiles down to the exact same as std::cout << 10 << "\n"; which is also pretty neat.

Personal statement: This post is well over a year late and for that I apologize. A lot has happened in that year but I hope to resume my postings as irregular as they may be. Thanks for reading!

Advertisements

Continuation Passing Style

Let’s take a break from type classes and take a brief look at one of the more esoteric concepts of functional programming. Continuation passing style (CPS) is a method of programming which allows for intricate manipulation of control flow while still maintaining functional purity.

Continuations can be used to implement a whole range of things from exceptions to coroutines, but today we’ll just introduce them and a few interesting and useful concepts.

Suppose we have a show function which just prints things to the screen.

auto show = [](const auto& v){std::cout << v << "\n";};

Typically we deal with calling functions, storing and modifying return values, then passing those values on to the next functions:

auto make_one = [](){return 1;};

// prints 1
show(make_one());

In CPS, functions have an extra argument which is what handles the result. This is the continuation, named “k” by convention.

auto one_cps = [](auto&& k){return k(1);};

// Also prints 1
one_cps(show);

The one_cps takes a function as an argument and calls it with what would normally have been the return value. Note that it is written as a generic lambda, this is because we want to pass any type of function while avoiding “unresolved overloaded function” errors.

Other functions can be converted into CPS in a rather straightforward way:

auto add_cps = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs+rhs);
};

auto sub_cps = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs-rhs);
};

auto mul_cps = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs*rhs);
};

auto div_cps = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs/rhs);
};

auto eq_cps = []<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return k(lhs==rhs);
};

// etc...

add_cps(1,2,show); // prints 3
times_cps(3,4,show); // prints 12

More intricate functions can be written combining other CPS functions, for example this function which returns the sum of the squares of two numbers:

auto sum_of_squares_cps = [&]<class T>(const T& lhs, const T& rhs, auto&& k)
{
    return mul_cps(lhs,lhs,[&](const T& lhs2){
            return mul_cps(rhs,rhs,[&](const T& rhs2){
                return add_cps(lhs2,rhs2,k);
            });
        });
};

That’s quite a mess, let’s break it down by unwrapping it layer by layer. The outermost layer is a call to mult_cps which is used to square the left number:

return mul_cps(lhs,lhs,
        // ...
    );

The next layer is the continuation of the first layer:

[&](const T& lhs2){
    return mul_cps(rhs,rhs,
        // ....
    }

As with the outer layer, we are using mul_cps to square the right number.

Additionally, as the continuation of the first layer, we receive the argument lhs2. Now this is a clever trick, by passing it as the argument, we can access the result of the first computation by name despite never actually storing in a variable.

Note: We will be using this trick quite often in the future!

The last layer uses the trick as well:

[&](const T& rhs2){
        return add_cps(lhs2,rhs2,k);
    }

We capture lhs2 and finally compute the sum of the squares using add_cps. As this is the final result of the computation, the continuation is that of the entire sum_of_squares_cps function.

The function can then be used as expected:

sum_or_squares_cps(3,4,show); // prints 25

You can even write recursive functions using CPS! This rather hard to do generically, since resolving the templates will involve an infinite loop, but it’s possible to get something together:

std::function<void(int,const std::function<void(int)>&)> factorial_cps =
    [&](int n, const std::function<void(int)>& k){
        eq_cps(n,0,[&](bool done){
                if (done)
                    k(1);
                else
                    sub_cps(n,1,[&](int m){
                            factorial_cps(m,[&](int p){
                                    mul_cps(n,p,k);
                                });
                        });
            });
    };

Overall, continuation passing style is a pretty radical departure from the conventional way of programming and the next few posts will explore what can be done with these functions.

P.S. This stuff is pretty heavy on the lambda functions. Here is a good introduction to what you can do with lambda calculus.

Edit (2015-01-15): Changed function suffixes to _cps.