Saturday, December 1, 2012

std::move and lambda? It's just partial application!

So, "Learn how to capture by move" was posted on isocpp.org and then this morning, "Another Alternative to lambda move capture" was on reddit. These are both impressive solutions and I look forward to seeing what other creative answers the C++ community will come up with. I also want to go over how this problem can be solved with partial application.

First, here's the definition.

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

    template< class _F, class _X >
    constexpr Part( _F&& f, _X&& x )
        : f(forward<_F>(f)), x(forward<_X>(x))
    {
    }

    template< class ... Xs >
    auto operator () ( Xs&& ...xs ) 
        -> decltype( f(x,declval<Xs>()...) )
    {
        return f( x, forward<Xs>(xs)... );
    }
};

template< class F, class X >
constexpr Part<F,X> closet( F f, X x ) {
    return Part<F,X>( std::move(f), std::move(x) );
}

So, there's this thing called the upward funarg problem. Let's say we wrote a function like this:

std::function<std::vector<int>()> bad_originate() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    return [&]{ return v; };
}
 
auto bad = bad_originate();
bad(); // Runtime error!

This fails because the reference to v becomes invalidated when it goes out of scope. We could copy v into the lambda, but our goal is a move.

So can we fix this with partial application? Let's add a bit to the example by including a function to partially apply.

std::vector<int> add_all( std::vector<int>& v, int x ) {
    // Arbitrarily move v.
    auto w = std::move(v);

    std::transform( w.begin(), w.end(), w.begin(),
                    closet(std::plus<int>(),x) );

    return w;
}

using Origin = Part<decltype(add_all)*,std::vector<int>>;
Origin originate() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    return closet( add_all, std::move(v) );
}

And it ain't hard at all.

Origin f = originate();
print_vec( "original : ", f.x );
print_vec( "added 10 : ", f(10) );
print_vec( "original : ", f.x );

will output

    original :  = 1 2 3 4 5
    added 10 :  = 11 12 13 14 15
    original :  =


Maybe one would prefer that add_all take its argument by value; now, composition becomes useful.

template< class F, class G > struct Composition {
    F f = F();
    G g = G();

    Composition() { }
    Composition( F f, G g) 
        : f(move(f)), g(move(g)) { }

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

template< class F, class G > 
Composition<F,G> comp( F f, G g ) {
    return Composition<F,G>( std::move(f), std::move(g) );
}

constexpr struct Mover {
    template< class X >
    X&& operator () ( X& x ) const {
        return std::move(x);
    }
} mover{}; 

std::vector<int> add_all2( std::vector<int> w, int x ) {
    std::transform( w.begin(), w.end(), w.begin(),
                    closet(std::plus<int>(),x) );

    return w;
}
 
using MoveAddAll = decltype( comp(add_all2,mover) );
using Origin2 = Part< MoveAddAll, std::vector<int> >;
Origin2 originate2() {
    std::vector<int> v = { 1, 2, 3, 4, 5 };
    return Origin2( comp(add_all2,mover), std::move(v) );
}

and

Origin2 g = originate2();
print_vec( "original : ", g.x );
print_vec( "added 10 : ", g(10) );
print_vec( "original : ", g.x );

will output the same as above.

The code to this mini-article can be found here: https://gist.github.com/4182570