Tagged: c++11

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!

Tuple Forwarding

C++11 provides the very useful std::forward_as_tuple function. Unfortunately, there isn’t any standard way to unpack the tuple to the parameters of a function.

To do this, template recursion and forwarding can be used. Recursing over a tuple allows for the extraction of the arguments, at the end eval can evaluate the result:

template<size_t index>
struct tuple_eval_helper
{
    template<class Func,class TArgs,class... Args>
    static auto evaluate(Func&& f, TArgs&& t_args, Args&&... args)
        -> decltype(tuple_eval_helper<index-1>::evaluate(
            std::forward<Func>(f),
            std::forward<TArgs>(t_args),
            std::get<index>(std::forward<TArgs>(t_args)),
            std::forward<Args>(args)...
            ))
    {
        return tuple_eval_helper<index-1>::evaluate(
            std::forward<Func>(f),
            std::forward<TArgs>(t_args),
            std::get<index>(std::forward<TArgs>(t_args)),
            std::forward<Args>(args)...
            );
    }
};

template<>
struct tuple_eval_helper<0>
{
    template<class Func,class TArgs,class... Args>
    static auto evaluate(Func&& f, TArgs&& t_args, Args&&... args)
        -> decltype(eval(
            std::forward<Func>(f),
            std::get<0>(std::forward<TArgs>(t_args)),
            std::forward<Args>(args)...
            ))
    {
        return eval(
            std::forward<Func>(f),
            std::get<0>(std::forward<TArgs>(t_args)),
            std::forward<Args>(args)...
            );
    }
};

template<class Func,class TArgs>
auto tuple_eval(Func&& f, TArgs&& t_args)
    -> decltype(tuple_eval_helper<std::tuple_size<
            typename std::remove_reference<TArgs>::type>::value-1>::evaluate(
        std::forward<Func>(f),
        std::forward<TArgs>(t_args)
        ))
{
    return tuple_eval_helper<std::tuple_size<
            typename std::remove_reference<TArgs>::type>::value-1>::evaluate(
        std::forward<Func>(f),
        std::forward<TArgs>(t_args)
        );
}

Which you can use like this:

tuple_eval(std::plus<int>(),std::forward_as_tuple(1,2));

Now, suppose you have a tuple of functions that you want to call with the parameters? In similar fashion, recursively extract the functions, evaluate them and forward the result to the end where they are repackaged into another tuple:

template<size_t index>
struct multi_tuple_eval_helper
{
    template<class TFuncs,class TArgs,class... Results>
    static auto evaluate(TFuncs&& t_funcs, TArgs&& t_args, Results&&... results)
        -> decltype(multi_tuple_eval_helper<index-1>::evaluate(
            std::forward<TFuncs>(t_funcs),
            std::forward<TArgs>(t_args),
            tuple_eval(std::get<index>(t_funcs),t_args),
            std::forward<Results>(results)...
            ))
    {
        return multi_tuple_eval_helper<index-1>::evaluate(
            std::forward<TFuncs>(t_funcs),
            std::forward<TArgs>(t_args),
            tuple_eval(std::get<index>(t_funcs),t_args),
            std::forward<Results>(results)...
            );
    }
};

template<>
struct multi_tuple_eval_helper<0>
{
    template<class TFuncs,class TArgs,class... Results>
    static auto evaluate(TFuncs&& t_funcs, TArgs&& t_args, Results&&... results)
        -> decltype(std::tuple<decltype(tuple_eval(std::get<0>(t_funcs),t_args)),Results...>(
            tuple_eval(std::get<0>(t_funcs),t_args),
            std::forward<Results>(results)...
            ))
    {
        return std::tuple<decltype(tuple_eval(std::get<0>(t_funcs),t_args)),Results...>(
            tuple_eval(std::get<0>(t_funcs),t_args),
            std::forward<Results>(results)...
            );
    }
};

template<class TFuncs,class TArgs>
auto multi_tuple_eval(TFuncs&& t_funcs, TArgs&& t_args)
    -> decltype(multi_tuple_eval_helper<std::tuple_size<
            typename std::remove_reference<TFuncs>::type>::value-1>::evaluate(
        std::forward<TFuncs>(t_funcs),
        std::forward<TArgs>(t_args)
        ))
{
    return multi_tuple_eval_helper<std::tuple_size<
            typename std::remove_reference<TFuncs>::type>::value-1>::evaluate(
        std::forward<TFuncs>(t_funcs),
        std::forward<TArgs>(t_args)
        );
}

Which can be used like this:

multi_tuple_eval(
    std::forward_as_tuple(std::plus<int>(),std::multiplies<int>()),
    std::forward_as_tuple(3,4)
    );

The result is the tuple (7,12).

Esoteric and abusive to the compiler, that’s what we’re about here at Functional C++!

Note: Be careful with move semantics and invalidating stuff when using this.

Edit: Changed multi_tuple_eval to use the tuple constructor. It will now correctly return references.