Partial Application in C++

All too often, one finds that std::for_each or std::transform are not enough and falls back to the plain old for loop. Or perhaps C++11's range-based for loop. Some examples:

    // Game loop:
    while( dont_quit() ) {
        t = update_time();
        for( auto& c : charactors 
            c = update( t , c );
    }

    // Vector multiplication (x,y) * k = (x*k, y*k).
    vec operator* ( vec v, float k ) {
        for( auto& x : v ) 
            x = x * k;
        return v;
    }

Partial application is one way of dealing with this. In Haskell I could write the last one as such:

    updateCharactors t cs = map (update t) cs
    mult xs k = map (* k) xs

where (*k) is the partial application of (*) with k. (*k) returns a function, f, such that f(x) = x*k.Haskell, using curried notation by default, allows a natural expression of partial application by simply declaring the function with less arguments than it takes. In C++ we have a little work to do.

Of coarse, std::bind exists, but it suffers from two problems: the horrid std::placeholders::_1 syntax and the requirement of the caller to explicitly state all of the unbound arguments with a _1 or _2. I find this syntax unfriendly, but generic. It allows one to switch arguments around, duplicate arguments, bind nested arguments, and all sorts of neat things. It does what it does well, but I want something easier to use.

Ones first thought will probably be to implement a function taking a function, f, and an argument, x, and return a lambda that will take a y. This assumes, however, that f only takes one more argument (it may take many or none) and that y will be the same type as x, which is not true in the about the update example.

A less obvious solution is to define a type that holds a function and one argument and overloads the () (function call) operator.

    #include <utility>

    using std::forward;
    using std::declval;

    template< class F, class X >
    struct Partial {
        F f;
        X x;

        // perfect forwarding
        template< class _F, class _X >
        constexpr Partial( _F&& f, _X&& x ) : f(forward<_F>(f)), x(forward<_X>(x)) { }

        // decltype declval
        template< class ...Y >
        decltype( f( x, declval<Y>()... ) )
        operator() ( Y&& ...y ) {
            return f( x, forward<Y>(y)... );
        }
    };

Now, we can make simple partial applications manually. Before trying to tackle the above examples of multiply and update, let's try a simpler one: plusOne. We'll use std::plus for simplicity and apply an int to it.

    auto addBy( int x ) -> Partial< std::plus<int>, int > {
        return Partial< std::plus<int>, int >( std::plus<int>(), x );
    }

    ...
    auto plusOne = addBy( 1 );
    cout << plusOne(3) << '\n'; // 4.

While this works, the syntax is highly inconvenient and overly verbose. We can write a generic function that applies an argument to a function with syntax like papply(f,x), but we have to decide how it passes x along. If we pass by reference, then when addBy returns, it will return a Partial with a reference to its argument, which will no longer exist (undefined behaviour.). If we copy x, then types with expensive copies will be inefficient to partially apply.

To have our cake and eat it too, we can define two functions, closure and closet. Closures carry references to arguments and a function object, but in languages like C++, they suffer from the upward funarg problem (as described above, with addBy). Languages that use reference counting allow variables to outlast the scope of their functions, but stay alive since another object references them. They usually rely on some form of garbage collection. In C++, we can instead define who owns the garbage. I use the word "closet" as a sort of mnemonic for "closed-in closure". It copies its arguments.

    template< class F, class X, class P = Partial<F,X> >
    constexpr P closure( F&& f, X&& x ) {
        return P( forward<F>(f), forward<X>(x) );
    }

    template< class F, class X, class P = Partial<F,X> >
    constexpr P closet( F f, X x ) {
        return P( move(f), move(x) );
    }

Now, we can revisit addBy and the examples at the top.

    auto addBy( int x ) -> decltype( closet(std::plus<int>(),x) ) {
        return closet( std::plus<int>(), x );
    }

    auto plusOne = addBy( 1 );

    // Game loop
    while( dont_quit() ) {
        std::transform( begin(charactors), end(charactors), begin(charactors),
            closure( update, update_time() ) );
    }
    vec operator* ( vec v, float k ) {
        std::transform( begin(v), end(v), begin(v), closure(std::multiplies<float>(),k) ); 
        return v;
    }

As you can see, we usually can use closure over closet, but they both have their uses. closure for passing down, closet for passing up.

I hope this has been useful, however it is still incomplete. closure and closet can be given variadic counter-parts which bind multiple arguments. We can also write versions to bind the last arguments (rclosure and rcloset?). I leave these as exercises for the reader. rclosure and -closet will require a new class, RPartial, but should be otherwise the same.

One could also use these techniques to write function transformations that do all sorts of weird things. For example, in stack-based languages, rot rotates the top three elements on the stack such that the bottom element (the first) becomes the top (last). Thinking of function arguments as a stack, one could write this:

    template< class F >
    struct Rot
    {
        F f;

        template< class _F >
        constexpr Rot( _F&& f ) : f( forward<_F>(f) ) { }

        template< class Arg1, class ...Args >
        constexpr auto operator() ( Arg1&& arg1, Args&& ...args )
            -> decltype( f(declval<Args>()..., declval<Arg1>()) )
        {
            return f( forward<Args>(args)..., forward<Arg1>(arg1) );
        }
    };

    template< class F >
    constexpr Rot<F> rot( F f )
    {
        return Rot<F>( move(f) );
    }

rot used with closure can partially apply the second or third argument or be used to flip the arguments of a binary function.