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.

Advertisements

6 comments

  1. kou4307

    typos in the sub_cont having ‘lhs + rhs’ and mul_cont instead of time_cont?. great post by the way. looking for more

    • whanhee

      Oops, missed that on the sub_cont. Wasn’t sure what t call the multiplication one, but mul has 3 letters and lines up nicely with add and sub 🙂

      Thanks for reading!

  2. Yakk

    It isn’t hard to write `*then*` which takes a usual function (non-cps) on the left hand side, and a continuation on the right, unpacking tuples if the right hand side will take them. You should also be able to kill the std function overhead in your recursive example and make it returnable with a y combinator (as it stands that callable is only valid within its own scope) — in C++14 the y is even elegant (at least I think that is what I wrote…)

  3. dzada

    Hello

    Nice and clear article, thank you. (really makes me think of the waterfall Js)
    Also I wondered if in you next articles you could mention about the possible performance overhead.

    From what I’ve done with lambdas and std::function, I would say: low overhead with Lambdas, and heavy with std::functions on MSVC, quite heavy for both on CLang (3.1 if i remember well). Which was a bit sad.
    Maybe this will change as compilers are evolving quite fast and probably just starting on these. Although I can imagine it to be easier to optimize for a compiler when simply written with ad hoc code.

    Best

    • whanhee

      I did a bit of poking around, dealing with primitives with cps and crazy lambdas in general tends to give you the exact same code as if you just wrote something like std::cout << whateverl since lambdas inline quite well. STL functions are a special objects so they take a fair bit more overhead in general.

      I'm trying to learn assembly just so I can better comment on performance stuff, but I'm far from expert at it.

      I work in gcc 4.9 your mileage may vary.

      Thanks for reading!

  4. Yakk

    You might enjoy http://coliru.stacked-crooked.com/a/fec4013aff8f8214 — a *then* operator that converts a function returning an element or a tuple into a continuation call. func(a,b,c) *then* [&]( int x, int y ){ std::cout << x << "," << y <Z ) would require a bit more work, and dealing with the issue that function names are not passable objects in C++ (as they represent entire overload sets). I also threw in std::future support for giggles.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s