úlfurinn

Unrolling a list with variadic templates

Prelude

I’ve been entertaining the idea of making my own programming language, simply because it’s good fun. A lot of inspiration comes from Ruby, especially the ease of hooking native functions into the runtime:


rb_define_method( myClass, "method_name", &method_function, 2 );

and then calling it:


rb_funcall( instance, rb_intern("method_name"), 2, arg0, arg1 );

The runtime then takes care of forwarding the arguments into the appropriate C function. The underlying code, of course, is not quite so pretty. If you trace it down to the point where the actual function call takes place, it looks like this (in vm_insnhelper.c):


...
case 0:
    return (*func) (recv);
    break;
case 1:
    return (*func) (recv, argv[0]);
    break;
case 2:
    return (*func) (recv, argv[0], argv[1]);
    break;
...
case 15:
    return (*func) (recv, argv[0], argv[1], argv[2], argv[3], argv[4],
        argv[5], argv[6], argv[7], argv[8], argv[9], argv[10],
        argv[11], argv[12], argv[13], argv[14]);
    break;

My fingers itch to clean up all this repetition, and I don’t like the “magic” limit of 15 arguments (although, of course, having 15 positional arguments in a function is borderline insanity anyway, but let’s ignore that point for now). Besides, C allows you to fiddle with pointers like that, but I’m doing the project in C++ (because it’s also good fun, though in a kinkier way), which goes out of its way to discourage such things.

From the language features I have settled on so far I can anticipate that I will need to accumulate function arguments in temporary lists and then pass them on to the function as individual arguments, if I want to have native functions with natural-looking signatures; something like this:


int f( int, int, int );
some_magic_type f_p( &f );
vector<int> v = { 1, 2, 3 };
f_p( v );    //    => f( 1, 2, 3 );

Ruby offers this in the form of the splat operator; could there be a way of doing this in C++ without resorting to the sort of monstrosity shown above? Beasts like Boost.Function and Boost.Bind use the repetition pattern for dealing with arity… doesn’t look good.

The play

I should note that at this point I am in no way concerned with performance figures; all I care about is having fun with the type system and mining it for all the gold it has. I’m already using C++11 features in the project, so… enter variadic templates.

The common technique for processing argument packs is recursively splicing them into head and tail — something functional languages do on a daily basis; there’s an example of using it to convert an argument pack into a list. But the head and tail method also works for constructing lists; could we do something similar here to make the inverse conversion?

In fact, that’s exactly how it works. After several hours of trying out dead ends (marked by GCC saying “lol you can’t do that”… hey, I don’t have The Standard memorized, certainly not the parts that deal with template specialization), I found a way of doing precisely what I need.

The recursive part that does the actual unrolling looks like this:


//  recursion step, argument accumulation
template< int remaining, typename Ret, typename F, typename Container >
class invoker {
public:
    template< typename ... Args >
    static inline Ret invoke( F f, Container args, Args ... unrolled_args ) {
        return invoker< remaining - 1, Ret, F, Container >::invoke( f, args,
                args[ remaining - 1 ], unrolled_args... );
    }
};
//  recursion terminator, actual call
template< typename Ret, typename F, typename Container >
class invoker< 0, Ret, F, Container > {
public:
    template< typename ... Args >
    static inline Ret invoke( F f, Container args, Args ... unrolled_args ) {
        return f( unrolled_args... );
    }
};

Initially, unrolled_args is an empty pack, and we take the last element of args and pass it in front of unrolled_args. In the next step, they are matched together as unrolled_args, which is the gist of head|tail construction. Then we prepend another element and so on. Keep in mind that is all done in compile time, so there’s no way of knowing how long args is, and we need to have the remaining counter to detect the recursion end. When it reaches zero, we hit the specialized template that does the actual call.

To initialize remaining and to compute the type F we use another class:


template< typename Ret, typename ... P >
class fun_wrap {
public:
    static const unsigned arity = sizeof...(P);
    fun_wrap( Ret(*func)( P... ) ) :
            f( func ) {
    }
    template< typename Container >
    Ret invoke( Container args ) {
        if ( args.size() != arity )
            throw std::invalid_argument( "Arity mismatch" );
        return invoker< arity, Ret, Ret(*)( P... ), Container >::invoke( f, args );
    }
private:
    Ret (*f)( P... );
};
template< typename Ret, typename ... P >
fun_wrap< Ret, P... > wrap( Ret(*f)( P... ) ) {
    return fun_wrap< Ret, P... >( f ) );
}

The entry point is the wrap function (the point of using functions instead of creating class instances by hand is that the compiler deduces the template arguments for functions, but for classes you have to specify them by hand). The function’s argument signature is bound to P, which lets us determine the function’s arity and seed remaining.

Finally, an example of using it:


int fun1( int a ) {
    return a;
}
int fun2( int a, int b ) {
    return a + b;
}
int main( ) {
    auto f1 = wrap( &fun1 );
    auto f2 = wrap( &fun2 );
    cout << f1( vector< int >( { 1 } ) ) << endl;
    cout << f2( vector< int >( { 1, 2 } ) ) << endl;
}

Goal accomplished.

The final version adds an opaque method class that hides all the templating nonsense from the client code and does not depend on function signature. It also works with class member functions and operates on class instances, but this does not affect the technique. Limitations

The obvious one is that all arguments must be of the same type, being given in a homogenous container. Also, like I mentioned, performance is not a concern, but having N nested calls doesn’t look all that good, and there’s no way around using recursion with variadic templates. I can only hope GCC is smart enough to inline and/or unroll them, but I haven’t verified this.