Monday, September 3, 2012

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.


7 comments:

  1. of course you can do it. the real question is: is it really worth it, for a lone coder, or for a team of typical game programmers? i'd love to hear your thoughts on this, as someone who toys around with forcing functional programming into non-functional languages.

    ReplyDelete
    Replies
    1. For a lone coder:
      There are no rules. You can do whatever you want. Personally, I'm working on my own Haskell-like library because, while I'm not a huge fan of Haskell, it scratches the right itch. As a hobbyist, my highest freedom is no one being able to tell me not to use my own library that does what i want it to do. For the consumer of my software, it only matters that it compiles or executes.

      BTW: I do not consider C++ a non-functional language. It is a multi-paradigm language, agnostic of FP.

      For a team:
      ...or a larger matter: the C++ community at-large. C++ is a very formal language with various ideas of "good form" and "bad practise" in the back of one's mind. That which we see causes disorder or chaos we consider "bad form" and ban it. So it's really important that everyone on a project agree that partial application is good form. Is it?

      An existing practise is to create a function object that holds some data which it recalls when you call it. A comparator predicate object, for use in std::find_if, might hold a parameter that equals the value searched for.

      A generalization of that is std::bind, which could take your comparator and one argument (plus one std::placeholders::_n), and be passed to std::find_if. Instead of having to write a new struct for each comparison, one could write a normal function and wrap it in a bind.

      The closed and closure i defined can be thought of as specializations of std::bind. They are not foreign practises inserted into the language, but rather a less generic way of doing what's in the standard. Furthermore, they offer a more convenient syntax and can be used to write more generic functions than std::bind. (A higher-order-function using std::bind must know the function's arity. One using closure has no need.)

      I would like to see more use of functions like this, not because they are conventional, but because I would like to see them become conventional.

      Not just partial application, but composition (next article) and a generic fmap (future article). I'm on a kick right now for FP in C++. A lot of this stuff has only just recently become possible to do in C++ because of the inclusion of decltype, declval, perfect forwarding, rvalue-references, and all those other things that make people complain that C++ is too complex.

      Delete
  2. Lots of typos, reading your code is very noisy and painful. Can you fix syntax errors?

    ReplyDelete
    Replies
    1. I do appreciate constructive criticism, but if I recognized my own faults, I would have already corrected them. Could you be more specific?

      I did realize that i had forgotten the ouput iterator in the call to std::transform. Also, making operator* a move operation was wrong.

      As for how to make the code less noisy or painful: I do not often get a chance to hear what anyone has to say about my code. If you suggest an improvement, I will listen.

      Delete
  3. Thank for sharing your ideas! I also have interest using C++ in functional style. And there is a very good boost library called 'phoenix'. Let's try to implement partial application using 'phoenix':

    #include
    #include
    #include
    #include

    namespace fs = boost::phoenix;

    BOOST_PHOENIX_ADAPT_CALLABLE(plus, std::plus, 2);

    int main()
    {
    using fs::arg_names::arg1;

    auto plusone = plus(arg1, 1);
    std::cout << plusone(2) << std::endl;

    return 0;
    }

    That's all. :-) So, my question is: could be better to implement a thin wrapper around 'phoenix' library in order to mimic Haskell functionality?

    ReplyDelete
    Replies
    1. I'm not familiar with Pheonix, but in terms of mimicking Haskell...

      A couple months after writing this article, I thought more about currying and function objects. I've been meaning to rewrite this article. Really mimicking Haskell would mean you could do something like this:

      auto plusOne = std::plus< int >()(1);

      Which is, of course, impossible. But you reminded me of something I had been procrastinating on: https://gist.github.com/4606174

      Back to your original question, it sounds like a fine idea. As I said, I'm not familiar with the library, which is a result of my own ignorance, but I hear about it a lot (seems popular) and I can see it offers a flexibility my solution doesn't (re-ordering arguments, applying the last argument, etc.) similar to std::bind. I think I've read that it's great for operator overloading, too.

      Not sure how I could better answer your question, but good luck.

      Delete

Please feel free to post any comments, concerns, questions, thoughts and ideas. I am perhaps more interested in what you have to say than you are in what I do.