Thursday, November 15, 2012

Generalized Function Objects Explained (For the C++11 unfluent.)

It occurred to me that some of those who found my "Generic Function Objects" article were not all that familiar with C++11 syntax, and in particular, template template parameters and variadic templates. Learning these concepts is one thing--just takes some googling, reading, and a little practice. Understanding examples like in my article may be more difficult, so I will explain how it works line-by-line. I will not be explaining these features, or how and why they work as that is too much for one blog post to accomplish, but I will be explaining how they work in context.

Note that if one understood the article up to the definition of ConstructT, then feel free to skip to that section.

Update: I have attempted to improve the original article with some of this one, so it may be a little redundant.


Binary

Binary defines member functions for partially applying the first and last arguments. I wrote about this back in September.

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 >
    constexpr auto operator () ( Xs&& ...xs )
        -> decltype( f(x,declval<Xs>()...) )
    {
        return f( x, forward<Xs>(xs)... );
    }
};

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

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

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

template< class F > struct Binary {
    template< class X >
    constexpr Part<F,X> operator () ( X x ) {
        return Part<F,X>( F(), move(x) );
    }

    template< class X >
    constexpr RPart<F,X> with( X x ) {
        return RPart<F,X>( F(), move(x) );
    }
};

So, given some type, F, inherited from Binary<F>, F is defined as taking one argument (partial application), and calling the member function with (reverse-partial application). F must be a type that defines a two-argument operator() overload.

We define a derivation like so:

constexpr struct Add : public Binary<Add> {
    using Binary<Add>::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y ) 
        -> decltype( std::declval<X>() + std::declval<Y>() )
    {
        return std::forward<X>(x) + std::forward<Y>(y);
    }
} add{}; 


Add, is not a function in the C sense, it's a function type. add is an instance of Add and is a function object. Add does not inherit Binary's operator() overload by default, so we explicitly tell it to by saying "using Binary<Add>::operator()". Binary's with requires no work to inherit.

    auto inc = add(1); // Calls Binary<Add>::operator(); returns Part<Add,int>.
    auto dec = add.with(-1); // Calls Binary<Add>::with; returns RPart<Add,int>.
    int two = inc(1); // Calls Part<Add,int>::operator(); returns add(1,1).
    int one = dec(two); // returns add(2,-1).
    add(1,2) -- Calls Add::operator(); returns int(3).


Chainable.


template< class F > struct Chainable : Binary<F> {
    using Binary<F>::operator();

    template< class X, class Y >
    using R = typename std::result_of< F(X,Y) >::type;

    // Three arguments: unroll.
    template< class X, class Y, class Z >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z )
        -> R< R<X,Y>, Z >
    {
        return F()(
            F()( std::forward<X>(x), std::forward<Y>(y) ),
            std::forward<Z>(z)
        );
    }

    template< class X, class Y, class ...Z >
    using Unroll = typename std::result_of <
        Chainable<F>( typename std::result_of<F(X,Y)>, Z... )
    >::type;

    // Any more? recurse.
    template< class X, class Y, class Z, class H, class ...J >
    constexpr auto operator () ( X&& x, Y&& y, Z&& z, H&& h, J&& ...j )
        -> Unroll<X,Y,Z,H,J...>
    {
        // Notice how (*this) always gets applied at LEAST three arguments.
        return (*this)(
            F()( std::forward<X>(x), std::forward<Y>(y) ),
            std::forward<Z>(z), std::forward<H>(h), std::forward<J>(j)...
        );
    }
}; 

Chainable works in much the same way as Binary does, except that it extends F to take any arbitrary number of arguments (except for zero, but that'd be pretty useless anyway). Redefining Add to be Chainable is not hard.

constexpr struct Add : public Chainable<Add> {
    using Chainable<Add>::operator();

    template< class X, class Y >
    constexpr auto operator () ( X&& x, Y&& y ) 
        -> decltype( std::declval<X>() + std::declval<Y>() )
    {
        return std::forward<X>(x) + std::forward<Y>(y);
    }
} add{}; 

Only two lines have changed, however add's behaviour has changed dramatically.

    int x = add(1,2,3); // Calls Chainable<Add>::operator(X,Y,Z); returns (1+2)+3.
    int y = add(1,2,3,4,5,6); // Calls Chainable<Add>::operator(X,Y,Z,H,J...).
    auto inc = add(1); // Still calls Binary<Add>::operator().

The three arg version of Chainable<Add> calls add( add(x,y), z ), while the variadic version calls itself( add(x,y), z, h, j... ). It reduces the number of arguments to process by one, being supplied at least four. It is therefore never the base case and always ends by calling its three-arg version.


ConstructT.


template< template<class...> class T > struct ConstructT {
    template< class ...X, class R = T< typename std::decay<X>::type... > >
    constexpr R operator () ( X&& ...x ) {
        return R( forward<X>(x)... );
    }
};

The first template argument may be confusing to those who have not seen them before. We could write template<class> class T, and that would expect a T that took one type parameter. It may actually take one, zero, or several. template<class...> class T is the generic way to say "we know T takes type parameters, but we don't know how many (and it doesn't yet matter)". It might be std::vector, which can take two; the value type and allocator. It might be std::set, which can take three. (Though, neither vector nor set would work for ConstructT.)

We deduce the return type using the default template parameter, R. std::decay transforms the type such that if we pass in an int&, we get an int back.

    typename std::decay<const int&>::type = int
    typename std::decay<int&&>::type = int
    typename std::decay<int>::type = int

So, if T=std::pair and we pass in an int& and std::string&&, R = std::pair<int,std::string>.

ConstructT perfectly forwards the arguments to T's constructor, but decays the types to ensure that it holds the actual values.

Just the same as with add and Add, we must create an instance of ConstructT to call it.

    constexpr auto make_pair = ConstructT<std::pair>();

This version of make_pair behaves just like std::make_pair. Its type is equivalent to this:

template< struct ConstructPair {
    template< class ...X, class R = std::pair< typename std::decay<X>::type... > >
    constexpr R operator () ( X&& ...x ) {
        return R( forward<X>(x)... );
    }
};

Conclusion.

C++11 is very big and no one feature is incredibly useful, but in conjunction they build up a powerful synergy. If these features had been a part of the language to begin with, there is no question that they would be considered required reading, just as much as std::vector and the <algorithm> library are today. They solve problems that have led to years frustration in developers. Perhaps one of the reasons many hate C++ is because of the lacking of many of these features. Becoming fluent in them makes C++ a much nicer language to speak and communicate with.