Beginning Template Meta-Programming: Introducing meta-functions

Posted in Template Metaprogramming on June 28, 2013 by Crazy Eddie

I intended this to be an article about “arbitrary binding” in template meta-programming, but I found that there was much I needed to introduce in order to do so and the article was becoming quite lengthy without actually providing much.  Thus I’ve decided to begin a series on template meta-programming that will introduce the topic and expand into more complex subjects, partial application being one of them.

Some history – expression templates

Meta-programming in C++ was pretty much a total accident.  The template system was defined without meta-programming in mind.  For many years in C++ development, and unfortunately still not as rare as it should be, developers were afraid of templates and in some cases avoided them entirely.  More than one team would have coding standards that dictated that no developer use templates.  The problem was that many compilers did not implement templates very well and in fact there are still issues with some of the more commonly used compilers.  If you chose to go down the road of becoming efficient at Template Meta-Programming (TMP) you are sure to run into a few compiler bugs.

Even so though, some brave souls embraced templates and came up with some very interesting constructs.  The STL is but one of the more fascinating examples.  Many of the ideas introduced there indicated that there was much potential for expressive power in templates.  One very early example of techniques that hinted at TMP though are expression templates.  If you search through the Internet for this term you’ll find a great many excellent articles and papers.  Expression templates are a powerful concept that can be used to reduce the amount of temporaries created during calculations of complex objects such as matrices.  The idea is that operators, such as addition, don’t actually perform addition at all but instead create an object that implements the functions that perform that task.  This is in some ways hinting at lazy evaluation except that (until C++11 changed the meaning of auto) nobody in their right mind wants to declare the type that would be necessary to store that lazy evaluator in a variable.  Instead, the act of assignment or access would perform all the calculations in the complete expression leaving out that which is unnecessary, encoding the evaluation of each cell into a single expression, and eliminating the need for temporary objects.  What follows is a very brief example (the rest of the operators are left as an exercise):

// represents a delayed addition operation.
// Represents a result but isn't itself one.
template < typename Right
         , typename Left >
struct matrix_addition
{
    matrix_addition( expr_matrix const& lh
                   , expr_matrix const& rh)
        : m1(lh)
        , m2(rh)
    {}

    int get_value(int x, int y) const
    {
        return m1.get_value(x,y) 
             + m2.get_value(x,y)
        ;
    }

    operator expr_matrix() const // perform the addition and return the result.
    {
        expr_matrix tmp;
        for (size_t i = 0; i < 3; ++i)
        {
            for (size_t j = 0; j < 3; ++j)
            {
                tmp.assign_value(i,j, get_value(i,j));
            }
        }
        return tmp;
    }

private:
    expr_matrix const& m1;
    expr_matrix const& m2;
};

// override '+' to return addition result representation.
template < typename Right 
         , typename Left >
matrix_addition<Right,Left> operator + (Right const& rh, Left const& lh)
{
    return matrix_addition<Right,Left>(rh,lh);
}

BOOST_AUTO_TEST_CASE(check_expr_approach)
{
    expr_matrix m1;
    expr_matrix m2;

    fill_test_matrices(m1,m2);

    // Creates a full result through implicit casting.
    expr_matrix result = m1 + m2;

    check_test_matrices(m1,m2,result);

    // The only additions performed here are on [0,0].  None of the others are performed.
    // A complete summation of the matrixes used is not done.
    BOOST_CHECK((m1 + m2).get_value(0,0) * 2 == (m1 + m2 + result).get_value(0,0));
}

Expression templates are an example of an embedded Domain Specific Language (DSL). They turn expressions involving the matched types and operator overloads into a set of recursively defined types that represent an abstract syntax tree.

Our first “pseudo” meta-function

One of the first examples of a metafunction generally introduced is the factorial function.  I’m going to call this a pseudo metafunction because it doesn’t match any defined protocol for creating a consistent language for template metaprogramming.  As with functional programming in general, this compile time factorial calculator is recursive in nature.  In something like Haskel or Scala you would use pattern matching on the argument to invoke a different calculation for the argument should it be general or should it be your base case.  In TMP you do this with template specialization:

template < size_t I > // general case
struct pre_tmp_fact
{
    // recursively invoke pre_tmp_fact
    // and multiply the result with the current value.
    enum { value = I * pre_tmp_fact<I-1>::value };
};

template < > // base case specialization
struct pre_tmp_fact<0>
{
    // 0! == 1
    enum { value = 1 };
};

BOOST_AUTO_TEST_CASE(first_example)
{
    BOOST_CHECK(pre_tmp_fact<5>::value == 5 * 4 * 3 * 2);
}

Defining a protocol

In C++ Template Metaprogramming, Abrahams and Gurtovoy define a protocol for implementing a consistent language for template metaprogramming in C++.  That protocol involves three basic definitions:

Meta-Function
A meta-function is a template that takes types as parameters and ‘returns’ a type in the form of an internal type typedef.
Value Meta-Function
Value meta-functions are metafunctions that represent values. They have all the characteristics of a meta-function and also an internal value member. They are “identity meta-functions” in that they return themselves as their type. If you create instances of them they are generally convertible to the underlying raw value type they represent, with the appropriate value of course.
Meta-Function Class
Since a meta-function is not a type it cannot be passed as a parameter to another meta-function. Therefor an additional concept, that of meta-function class, needs to be defined. It is a type that has an internal meta-function called apply.

Our first meta-function

With the above in mind, we can recreate our factorial metafunction using these concepts.  In this article I’ll implement very basic, minimally functional integer wrapper meta-functions.  In the future I will use the Template Metaprogramming Library (MPL), which is part of the boost library set.  It’s worth reviewing here, for instruction purposes, but it’s generally easy to use what other people have built and tested than reinventing the wheel.  This time though, we’ll reinvent the wheel, we just won’t add all the spokes and will not true it:


// integer value wrapper metafunction.
template < int I >
struct int_
{
    typedef int_<I> type;
    enum : int { value = I };
};

BOOST_AUTO_TEST_CASE(value_mf)
{
    // Has a value...
	BOOST_CHECK(int_<5>::value == 5);
	// Is an identity metafunction...
	BOOST_CHECK(int_<5>::type::value == 5);
	// This recursion is OK because the compiler won't instantiate until requested.
	// Can go on forever.
	BOOST_CHECK(int_<5>::type::type::value == 42);
}

// This is not how boost's MPL does it!

// Forward declaration of metafunction
template < typename T >
struct prev;

// Specialize for int_ wrappers.
template < int I >
struct prev<int_<I>>
{
    typedef int_<I-1> type;
    enum { value = int_<I-1>::value };
};

BOOST_AUTO_TEST_CASE(prev_int)
{
    BOOST_CHECK(prev<int_<5>>::value == 4);
}

// General case.
template < typename T >
struct tmp_fact
{
    typedef tmp_fact<T> type;
    enum { value = T::value * tmp_fact<typename prev<T>::type>::value };
};

// Specification for base case.
template < >
struct tmp_fact<int_<0>>
    : int_<1> // You can subclass the result sometimes, to be preferred.
{};

BOOST_AUTO_TEST_CASE(fact_check)
{
    BOOST_CHECK(tmp_fact<int_<5>>::value == 5 * 4 * 3 * 2);
}

Moving forward

If you are interested in continued study of template meta-programming in C++ then I suggest purchasing the book, C++ Template Metaprogramming.  I will also be continuing forward with some other instructional material in future blogs, including implementing named parameters and partial evaluation (arbitrary binding) in templates.  This has been but a rudimentary look at the very basics that will be needed by future blog entries.

I might suggest also playing with the above code and trying to improve it. There are a great many ways in which it can be. The factorial metafunction for example could use tail recursion and could even use subclassing all the way through. It is much easier to read and work on a metafunction that can be defined in terms of other metafunctions through simple inheritance, so unless you must do otherwise to leverage lazy evaluation (any time you can avoid explicitly refering to type within a metafunction you’re doing lazy evaluation) it should be preferred. Often this requires decomposition of more complex metafunctions into smaller, simpler ones. This is of course, like with your usual code, never a bad thing.

GotW #91

Posted in C++11, GotW on May 31, 2013 by Crazy Eddie

I can’t seem to post to Herb Sutter’s blog, my comments just never appear and ones I’ve made are gone.  Maybe he has me blocked for some mysterious reason.  So I thought I’d put my answer to the problems here.

Anyone that wants to write solid C++ should be reading his blog.  I suggest subscribing.

So, my answer to GotW 91 is:

#1 – Some extra locking and reference counting will take place. A new small object will be created on the stack. Not much will happen actually. The locking is the greatest concern.

#2 – I don’t believe it matters until threads are introduced. If you call this function via a thread spawning though you want to be sure that you do so by value. Doing it by reference can create a race condition in which you reduce the reference count while the pointer is being used or copied by the other side. When that happens it could be that you’re the last one holding the pointer and then the other side gets to have it’s resource yanked out from under it. This is bad voodoo.

#3 has made me want to come up with a set of smart pointer types that secure and ensure correct ownership semantics. In this case you’d take a pointer (by value) of the kind that specifies how you’ll use it. If only within scope then you’d specify that with type. It’s a pretty tough problem though…at least for me.

The answer to the question is one of three (given the types in the question):

1. Use reference – when in doubt, use a reference rather than pointer. If you don’t need a pointer, don’t use one.
2. Use unique_ptr by value – You intend to steal ownership of the pointer and you want this ownership transfered away from client code immediately.
3. The parameter could be null but you don’t want to steal it.  Use a raw pointer (for now at least…if I ever solve the above idea then you may have a smart pointer to use instead)

A case against naming conventions based on type

Posted in Uncategorized with tags on May 17, 2013 by Crazy Eddie

Many places I have worked have naming conventions that are, in my opinion, poorly conceived.  Naming conventions really should be limited to deciding between camel case, pascal case, and simply, “Give it a name that explains what it is supposed to be for.”  Unfortunately a lot of places go much further and do things like putting ‘m_’ before member variables, having different naming conventions for different classes of entities (Pascal for classes, underscore for functions, camel for variables, _t after typedefs, etc…).  These kinds of conventions miss the point of generic and object oriented programming and thus miss the point of C++ in a great way.

The issue is that what kind of thing an entity is doesn’t really matter so long as a certain interface is obeyed.  Take for example putting the “_t” postfix on typedefs, which many developers and firms do.  What happens now when someone comes along and decides that this type would be better implemented as a class of its own rather than a typedef of something else.  Since typedefs in C++ are weak this is not a surprising or all to rare thing to do.  Now in order to keep from breaking clients everywhere we need to follow the convention for naming classes and then add a typedef so that the “_t” name exists.  This is silly.

Another example comes up with regard to functors.  Functors are classes thats’ instances look and behave like functions that may have state.  If you’ve specified that variables must be named one way, and functions another, then in fact you’ve got a problem here because conceptually this variable is both a variable and a function!  If you replace a function with a functor someplace then again you are in the unfortunate position of having to violate naming conventions or do something silly like make a function to call the functor just so both names exist.

The C++ standard library has a pretty good C++ naming convention.  It uses one convention for almost everything with the caveats that template parameters are named differently (and this is important because of dependent name issues) and so are macros.  Both of these things require special consideration when using so it’s worthwhile to make them stand out.

In C++ types are strong at the time of compilation, but in the source they are interchangeable to a great degree.  So long as something obeys an interface, calling code shouldn’t have to change when you completely change the type some entity is.  Naming conventions that force you to change names based on type hinder this ideal.

CUDA without Visual Studio

Posted in Uncategorized on February 11, 2013 by Crazy Eddie

So I have a solid-state drive that I put my system on. It is only 55G in size and Windows 7 itself takes up over half of that, that’s before installing ANYTHING. Visual Studio takes up around 9G of drive space and though you can ask it to install on another drive, that only moves 1G…the rest INSISTS on being on your C drive.

I wanted to try out cuda development though and I don’t currently have a Linux install in anything but a VM (that will be remedied eventually). The CUDA development kit requires VS though.

It is possible though to get the compiler for VS only by downloading the SDK. The SDK can mostly be installed on another drive. Though there is stuff that insists on being on your system drive, it’s more like .5G rather than 6+. Even stuff that VS installs there and won’t anywhere else can be put on another drive this way. Of course, you won’t have the debugger or the idea…but in a pinch it works.

The next thing I had to argue about is getting the CUDA compiler part to recognize the configuration. I got a weird error saying it couldn’t find configuration “null” in the amd64 directory within bin of the SDK install. That is easily fixed by creating a file called “vsvars64.bat” in that directory that has a single line in it: “call drive:\path_to\SetEnv.cmd /x64″. The ‘path_to’ part will depend on where you installed the SDK.

Then you have to close that cmd window and start again for some reason–talking about the “Windows SDK Command Prompt” from the start menu. After this you can set the PATH to include your cudapath\bin and cudapath\open64\bin. You need to be able to run `nvcc` and `nvopencc`.

Once all this was done I was able to compile a basic cuda program from the command line with: `nvcc –cl-version 2010 –use-local-env file.cu`.

This took hours of pain, google research and forum posting. Hopefully the next person in my shoes can find this and it helps. Look forward to hearing success stories and otherwise.

“Universal design principle”

Posted in Uncategorized on January 17, 2013 by Crazy Eddie

In this video the presenter associates what he calls the Universal design principle to Scott Meyers. He also attributes him with the name. I can’t find another source on this but I have seen the principle passed around by others such as Robert C. Martin. The principle is, “Make interfaces hard to use incorrectly and easy to use correctly.” The presenter had a picture of a pestle and cup; the idea being that it’s really easy to use and can’t be used any other way.

That got me thinking and for the first time I think I believe that this principle is the wrong way to think about it. Why? Because being the kind of gutter thinker I am I immediately thought of other uses for that pestle…some places it could be stuck. I suppose this would be considered the “wrong” use and so it doesn’t follow the principle but wait!

What if you WANT to use it that way?

So I think that perhaps a more useful, a more defensive way of thinking about this principle is to say that, “The use of an interface in any way that works is ‘correct’.” In other words, regardless of the intention of the interface designer, if it can be used in a particular way then it’s a correct use of that interface. It then follows that it’s the duty of the designer to make sure that his or her intentions MUST be followed because they’re the only use that the interface supports.

We then get a sort of inversion of the principle that I think more clearly defines the intention of the principle: to make sure your interfaces are adequately specified and that implementations protect themselves from violations of that interface…BUT…your implementation must also handle correctly any correct use your interface allows. That way if someone decides they want to stick it where the sun doesn’t shine…then either it should not fit, or it at least shouldn’t break.

SFINAE — but sometimes it is.

Posted in Uncategorized on January 1, 2013 by Crazy Eddie

As I was writing up the code for my last article on bind expressions I actually learned something I had not expected and did not know before. As I often say, “Teaching is one of the best ways to learn,” and well, here’s a great example.

When I initially wrote the bind helper function I only had the one set:

template < typename Fun >
binder<typename return_of<Fun>::type, Fun, empty_list> bind(Fun f);

// further definitions for 1, 2, and 3 argument functions...

I then had a helper metafunction that would derive the return type:

template < typename T >
struct return_of { typedef typename T::type type; };

// one of many...
template < typename R >
struct return_of<R(*)()> { typedef R type; };

This worked just fine for function pointers and functors with a return_type subtype definition. The problem later came when I decided to add member function compatibility. This requires building an extra object to convert the calling convention to function syntax rather than member pointer. Here is one such function overload:

template < typename R
         , typename P1, typename A1
         , typename P2, typename A2 >
binder_t< R
        , mf1<R,P1,P2>
        , boost::fusion::vector<A1,A2> >
bind(R(P1::*f)(P2),A1 a1, A2 a2)
{
	typedef mf1<R,P1,P2> F;
	typedef boost::fusion::vector<A1,A2> L1;
	return binder_t<R, F, L1>(F(f), L1(a1,a2));
}

The assumption I had at this point, previous to compiling and after writing 20 lines of repetative overloads, was that the substitution of the member function pointer type in the previous overloads would cause a failure that the compiler would ignore because of SFINAE. Yeah…that’s not how it works.

There are a couple ways to consider why SFINAE will not apply here. The first is to look at 14.8.2 in the standard, note that these are the only allowed deduction failures that SFINAE can catch, and see that what’s going on here, instantiating something within another template that causes an error, is not in that list.

The more direct reason though is this: During the deduction of the types for the bind function we are instantiating another template. That template goes through its own deduction process and passes! There is no syntactic error caused by substituting a member function pointer into the template parameters for return_of. The deduction process is finished here and that template can be instantiated. Remember also that in C++ templates are only instantiated as they are needed. It is perfectly legal to instantiate a template class that has members that would cause syntax errors so long as you never use those members. So this process is finished and we are no longer within the realm where SFINAE even applies in the language with regard to return_of. We then instantiate type within this template and it has one…so again we can’t trigger SFINAE here because the type name exists! Now the instantiation phase happens for type and of course that results in the gibberish code R(T::*)(??)::type. This now is a syntax error, an ill-formed piece of code and we are well past the point of SFINAE, which happens only during deduction.

There are a few ways you can fix this issue. The first is what I chose in the article code: use T::type directly in the signature of my function so that its discovered during deduction where “substitution” actually occurs. This of course required that I write alternate overloads for function pointers.

Another way is to write result_of so that it won’t try define a type type member if type T doesn’t have one:

#include <boost/mpl/has_xxx.hpp>

BOOST_MPL_HAS_XXX_TYPE_DEF(type);

template < typename T, bool = has_type<T>::value>
struct return_of{};

template < typename T, true >
struct return_of { typedef typename T::type type; };

Now what happens in the original definition of bind is that the actual substitution going on is return_of<T> and then we’re trying to access type within that substitution, which fails. This is a substitution failure and it is not an error, it’s simply discarded as a viable overload.

Finally, one more way to fix this issue is to force the definition of return_of::type to occur during the deduction phase of return_of while the template parameter is being substituted in for T:

template < typename T, typename Type = typename T::type>
struct return_of { typedef Type type; };

Now the substitution failure is happening within the result_of deduction, which must be deduced to finish deducing bind. This substitution failure is also “not an error” and the whole works is discarded as a viable overload for bind

It’s an interesting little gotcha. Some people I’ve talked to claim that what I did was legal in C++03 but only due to unclear language in the standard, which has now been clarified. Others claim that the standard already defines what I first did as ill-formed. I tend to believe the latter as it seems to coincide with my interpretation, but either way you certainly cannot depend on it working and if it does you should simply ignore that fact as a fluke. If you have code that relies on this working, get working on replacing it with whichever of the above best fits the problem. If you’re just learning how to use SFINAE to do type introspection and function overloading…keep this in mind and be better armed with a better understanding of the mechanism.

Until next time, happy coding!

Arbitrary binding pt3 – type safe version

Posted in Template Metaprogramming, Uncategorized on December 31, 2012 by Crazy Eddie

In this installment I’m going to explain how to take the concepts we used in the last article and apply them, with a lot of template magic, to create a bind expression system that works with the static type system rather than RTTI. This version requires much more familiarity with templates and a lot more repetition, as you’ll soon see. I am going to use constructs from boost that match the constructs we used before, leveraging other peoples’ work to implement a binder expression system. In the next article I will show how boost’s bind system implements these things in a custom manner as well as some additional things that library does and why. This implementation I’m about to show is not meant to replace your boost bind or std bind but may help you understand them.

Addendum to pt2 – composition

First though I would like to create an addendum to the last article. In the last article we did not make it possible to compose bind expressions. This is a very important omission that I will now remedy. The test:

BOOST_AUTO_TEST_CASE(composition) {

	Integer i1{42};
	Integer i2{5};

	FUNPTR fun = reinterpret_cast<FUNPTR>(add_two);

	binder bound(fun, a1, new binder(fun, a1, a2, END_ARGS), END_ARGS);

	BOOST_CHECK(static_cast<Integer*>(bound(&i1,&i2,END_ARGS))->get() == 89);
}

Now all that is needed is an additional check in the lookup function followed by a simple, added function to the binder class:

Object* select_arg(std::vector<Object*> const& args, Object * key) {
	if (Placeholder * ph = dynamic_cast<Placeholder*>(key)) {
		return args[ph->get()];
	}
	if (binder * bound = dynamic_cast<binder*>(key))
	{
		return bound->eval(args);
	}
	return key;
}

Object * binder::eval(std::vector<Object*> const& args_b) const {
	return invokers[args.size()](fun, args, args_b);
}

As you can see, no big deal but it greatly improves the utility of the system.

Also, I was mistaken when I said that the standard for return type deduction was to have a result_of typedef in your functor. The actual typename is result_type just as the STL uses in unary and binary functions.

Review

If you’ll remember from the last article, the bind system requires a few basic parts:

  1. Two lists of arguments, the first may contain placeholders or bind expressions.
  2. A translation function that will take an argument and either return it, evaluate it if it’s a bind, or return the item in the list if it’s a placeholder.
  3. A set of invokers that use the above to generate a final list of arguments and invoke the function
  4. An object to track the initial bind and provide a way to invoke it.

In the last article I used std::vector to implement argument lists; in this case I have chosen boost::fusion::vector to do the same. This structure guarantees constant time lookup of its elements, just as std::vector does, but does so through the type system rather than as an allocated block of memory. Each element in this structure has its static type attached to it and you access these values through templated functions, passing in the index to the item you want. I could have used boost::tuple, which would be more in line with what the now current standard has (std::tuple) but this construct is a cons list that requires linear lookup rather than constant. This translates not into runtime complexity but into compile time complexity, making your builds take longer. One frustrating part of working in C++, especially when you start working with templates and more so TMP, is that it takes a while to compile.

Lookup and placeholders

Previously we needed a placeholder object that inherited from the base object in order to allow RTTI to decide what to do during lookup. This time we simply need to wrap an integral into a type. We could use something like boost::mpl::int_ but it’s more complex than we need (not by much) and it’s nice to have our own name to do pattern matching against. Thus we just make a template and stick some instances into an anonymous namespace:

template < int I >
struct placeholder {};

namespace {
placeholder<0> a1;
placeholder<1> a2;
placeholder<2> a3;
}

When doing generic programming in C++, and most especially when doing TMP, you should be thinking more in the functional paradigm than most others. In functional programming there is the concept of “pattern matching” that lets you dictate various different things to do based on the type of the object passed into your function. In C++ this is done through template specialization, partial specialization and function overloading. What we want to do here is the same as before, if we get a placeholder as our index we dereference the argument list at that index. Anything else and we simply return that index (I’ll go over composition at the end). With that in mind, here’s the test code for our lookup function:

BOOST_AUTO_TEST_CASE(lookup_check)
{
	boost::fusion::vector<int, char, std::string> args(42, 'c', "Hello");

	BOOST_CHECK(lookup(args, 13) == 13);
	BOOST_CHECK(lookup(args, a3) == "Hello");
}

Next, our two overloads of lookup. The first covers the general case and the second specializes for placeholder types:

template < typename ARGS
         , typename IDX >
IDX lookup(ARGS&, IDX idx) { return idx; }

template < typename ARGS
         , int IDX >
typename boost::fusion::result_of::at
<
  ARGS
, boost::mpl::int_<IDX>
>::type lookup(ARGS & args, placeholder<IDX>)
{
	return boost::fusion::at_c<IDX>(args);
}

Note how the second version uses a template metafunction, or a type trait if you prefer (though it’s actually much more complicated than a simple trait usually is), to discover what the return type should be. Recall that now we’re using type safe construct that will leverage the template system rather than dynamic type information to do our thing. We can’t just specify any old return, we need to ask the fusion sequence (a vector in our case) what the type at the given index will be. Unfortunately there’s no at_c within the result_of namespace so we have to wrap the int into an MPL integral (per requirements of the function we’re calling).

If I were assuming that we could use C++11 constructs then this function could have been turned into something more simple, something like this:

template < typename ARGS
         , int IDX >
auto lookup(ARGS & args, placeholder<IDX>) -> decltype(boost::fusion::at_c<IDX>(args))
{
	return boost::fusion::at_c<IDX>(args);
}

Clearly this is simpler and easier to understand if you are familiar with the new constructs, but I have the ability to code this with C++03 in mind and intend to make it useful in that context. Furthermore, the boost version works in C++03 and I figure it will be easier to instruct how it’s doing its thing if we focus on learning constructs that work in the old C++. This shows though that we have a lot to look forward to when everyone is coding in C++11 rather than C++03 and earlier.

The Invoker

The invoker in this case doesn’t work a whole lot differently than in the previous version. We’re still going to use the count of arguments in the first list to decide which invoker to use. With all the templating stuff going on though, I found it easier to approach this as a distinct feature that needs unit testing. Here’s the test:

int fun(int i, int j)
{
	return i + j;
}

BOOST_AUTO_TEST_CASE(invoke_check)
{
	boost::fusion::vector<int, placeholder<1> > args1(42, a2);
	boost::fusion::vector<double, int> args2(10.3, 8);

	BOOST_CHECK(invoke<int>(fun, args1, args2) == 50);
}

The code that implements it uses a templated struct parameterized by an integral representing the size of the argument list. The invoke function then performs this calculation and uses a static call function within that template. Again, we’re going to limit ourselves to three arguments for the sake of sanity:

template < int I >
struct invoker;

template <>
struct invoker<0>
{
	template < typename R
	         , typename F
	         , typename L1
	         , typename L2 >
	static R call(F f, L1 & l1, L2 & l2) { return f(); }
};

template <>
struct invoker<1>
{
	template < typename R
	         , typename F
	         , typename L1
	         , typename L2 >
	static R call(F f, L1 & l1, L2 & l2)
	{
		return f(lookup(l2, boost::fusion::at_c<0>(l1)));
	}
};

template <>
struct invoker<2>
{
	template < typename R
	         , typename F
	         , typename L1
	         , typename L2 >
	static R call(F f, L1 & l1, L2 & l2)
	{
		return f( lookup(l2, boost::fusion::at_c<0>(l1))
	            , lookup(l2, boost::fusion::at_c<1>(l1)) );
	}
};

template <>
struct invoker<3>
{
	template < typename R
	         , typename F
	         , typename L1
	         , typename L2 >
	static R call(F f, L1 & l1, L2 & l2)
	{
		return f( lookup(l2, boost::fusion::at_c<0>(l1))
				, lookup(l2, boost::fusion::at_c<1>(l1))
				, lookup(l2, boost::fusion::at_c<2>(l1)) );
	}
};

template < typename R
         , typename F
         , typename L1
         , typename L2 >
R invoke(F f, L1 & l1, L2 & l2)
{
	return invoker
		   <
		     boost::fusion::result_of::size<L1>::type::value
		   >::template call<R>(f, l1, l2);
}

Although the syntax is a lot less intuitive, if you compare this version to the version in the last article you will see that they essentially do exactly the same thing except this one does it through types and pattern matching while the other used dynamic dispatch and a simple jump table.

Putting it together

While last time I talked about building the bound argument list before I talked about the invoked one, this time I have to reverse that trend. The type of the binder object is going to be governed by the things you are attempting to bind. First I’ll show how such a thing is constructed by hand and then activated, and how that activation is done, and then next I will show you how to use helper functions to discover the binder template parameters and build the thing. With the helper function you can then create bind expressions without having to declare their types unless you want a variable of that type (and in C++11 you can use auto–C++03 I recommend using boost::function even though it introduces indirection).

First things first, the test for creating and invoking a binder:

BOOST_AUTO_TEST_CASE(binder_t_check)
{
	boost::fusion::vector<int, placeholder<1> > args1(42, a2);
	binder_t<int, int(*)(int,int), boost::fusion::vector<int, placeholder<1> > > bound(fun, args1);

	BOOST_CHECK(bound(10.3, 8) == 50);
}

The binder itself is not difficult to create, just repetitive. First of all, we simply store the function (or functor) and the bound arguments as member variables:

template < typename R, typename F, typename L1 >
struct binder_t
{
	...

	binder_t(F f, L1 l1) : f(f), l1(l1) {}

private:
	F f;
	L1 l1;
};

The next part we need is the functor operator and we need as many of these as we allow arguments, from zero to some maximum. Again, I chose three here for my own sanity (boost allows 10):

template < typename R, typename F, typename L1 >
struct binder_t
{
	R operator() ()
	{
		boost::fusion::vector<> l2();
		return invoke<R>(f, l1, l2);
	}
	template < typename A1 >
	R operator()(A1 & a1)
	{
		boost::fusion::vector<A1> l2(a1);
		return invoke<R>(f, l1, l2);
	}
	template < typename A1
	         , typename A2 >
	R operator()(A1 a1, A2 a2)
	{
		boost::fusion::vector<A1,A2> l2(a1,a2);
		return invoke<R>(f, l1, l2);
	}
	template < typename A1
	         , typename A2
	         , typename A3 >
	R operator()(A1 a1, A2 a2, A3 a3)
	{
		boost::fusion::vector<A1,A2,A3> l2(a1,a2,a3);
		return invoke<R>(f, l1, l2);
	}
	...
};

In each case here we simply construct the argument list and use it to call invoke. This is similar to the variadic function iteration we did in the last article except that iteration is not necessary (the overload figures it out) and it’s all done by different functions. You could use the boost preprocessor library to reduce some of this repetition (at least from the programmer’s perspective) but this makes the code harder to understand and neither I nor boost used this technique. I leave it as an exercise for the reader (or you can see how I apply it in a possible future article about self returning function wrappers). This is far from the last time you’ll see repetition being required in this system. Although it makes calling code less repetitious and simpler, the templated bind system contains several header files filled with many repeating constructs (and in boost each one is repeated 10 times).

The next thing we need to do is build one of these binder things. We could leave it like it is, and it works OK, but what a hassle! A helper function is in order. We start with a unit test that checks functionality with functors (defined to have a result_type typedef), functions, and member functions. The boost system actually adds a few more options here but I didn’t feel like writing all that but to instead describe how they did it in the next article. Here is that test:

struct functor
{
	typedef int result_type;

	result_type operator()(int i, int j)
	{
		return i + j;
	}
};

struct something
{
	int add_to_42(int i) { return 42 + i; }
};

BOOST_AUTO_TEST_CASE(helper_check)
{
	BOOST_CHECK(bind(fun, 42, a2)(10.3, 8) == 50);
	BOOST_CHECK(bind(functor(), 42, a2)(10.3, 8) == 50);
	BOOST_CHECK(bind(&something::add_to_42, something(), a2)(10.3, 8) == 50);
}

Here two more test constructs were added, functor and something, and fun from above is reused. This isn’t a particularly great unit test since it fails to address a great many permutations of the interface, instead using the same values and number of arguments, but it’s good enough for this exercise (if this were used in a real product we should have better tests).

The functor version of this bind function is quite easy but we still need four definitions for our rather limited interface:

template < typename F >
binder_t< typename F::result_type
        , F
        , boost::fusion::vector<> >
bind(F f)
{
	typedef typename F::result_type R;
	typedef boost::fusion::vector<> L1;
	return binder_t<R, F, L1>(f, L1());
}

template < typename F, typename A1 >
binder_t< typename F::result_type
        , F
        , boost::fusion::vector<A1> >
bind(F f, A1 a1)
{
	typedef typename F::result_type R;
	typedef boost::fusion::vector<A1> L1;
	return binder_t<R, F, L1>(f, L1(a1));
}

template < typename F, typename A1, typename A2 >
binder_t< typename F::result_type
        , F
        , boost::fusion::vector<A1,A2> >
bind(F f,A1 a1, A2 a2)
{
	typedef typename F::result_type R;
	typedef boost::fusion::vector<A1,A2> L1;
	return binder_t<R, F, L1>(f, L1(a1,a2));
}

template < typename F, typename A1, typename A2, typename A3 >
binder_t< typename F::result_type
        , F
        , boost::fusion::vector<A1,A2,A3> >
bind(F f, A1 a1, A2 a2, A3 a3)
{
	typedef typename F::result_type R;
	typedef boost::fusion::vector<A1,A2,A3> L1;
	return binder_t<R, F, L1>(f, L1(a1,a2,a3));
}

Again, we’re basically implementing a statically variant variadic function through function overloads.

For the function and member function versions I’m just going to show the two argument variation (the one we tested). The interesting thing here is that we need to use almost twice as many template parameters because the function argument types may very well not match the argument types passed into our helper (especially if a placeholder is being used). The function version requires no extra objects:

template < typename R
         , typename P1, typename A1
         , typename P2, typename A2 >
binder_t< R
        , R(*)(P1,P2)
        , boost::fusion::vector<A1,A2> >
bind(R(*f)(P1,P2), A1 a1, A2 a2)
{
	typedef R(*F)(P1,P2);
	typedef boost::fusion::vector<A1,A2> L1;
	return binder_t<R,F,L1>(f,L1(a1,a2));
}

The member function version on the other hand does. Here we want to convert member function pointer call syntax from (var.*ptr)() to mem_fn(var). We do this with a simple wrapper class:

template < typename R, typename T >
struct mf0
{
	R operator()(T t)
	{
		return (t.*f)();
	}

	mf0(R(T::*f)()) : f(f) {}

private:
	R(T::*f)();
};
template < typename R, typename T, typename A1 >
struct mf1
{
	R operator()(T t, A1 a1) { return (t.*f)(a1); }

	mf1(R(T::*f)(A1)) : f(f) {}

private:
	R(T::*f)(A1);
};
template < typename R, typename T, typename A1, typename A2 >
struct mf2
{
	R operator()(T t, A1 a1, A2 a2) { return (t.*f)(a1,a2); }

	mf2(R(T::*f)(A1,A2)) : f(f) {}

private:
	R(T::*f)(A1,A2);
};

Once again, much repetition. The boost library also adds a “dm” type that creates this same call syntax for member variable pointers. I have chosen not to replicate that here. Once we have this construct we can build the many versions of “bind” that will create the binder object (again only the two argument version shown):

template < typename R
         , typename P1, typename A1
         , typename P2, typename A2 >
binder_t< R
        , mf1<R,P1,P2>
        , boost::fusion::vector<A1,A2> >
bind(R(P1::*f)(P2),A1 a1, A2 a2)
{
	typedef mf1<R,P1,P2> F;
	typedef boost::fusion::vector<A1,A2> L1;
	return binder_t<R, F, L1>(F(f), L1(a1,a2));
}

Note that the “mf” we use is mf1, not mf2. That is because that number represents how many arguments the member function takes. We actually call that object with one extra argument, the first argument: this.

Composition

We again want to be able to call this bind expression such that we can compose many functions into one, each taking certain parameters from the invokation parameters and using other, bound values along with them. We do so in pretty much exactly the same way as we did before. We first pattern match on the binder template type in place of IDX or placeholder and call an eval function within that binder with the arguments being passed to lookup:

template < typename R, typename F, typename L1 >
// we need to forward declare binder_t if it appears later in the file, and it does in my case:
template < typename R, typename F, typename L > struct binder_t;

template < typename ARGS
         , typename R
         , typename F
         , typename L1 >
R lookup(ARGS & args, binder_t<R,F,L1> & binder)
{
	return binder.eval(args);
}

struct binder_t
{
	...

	template < typename L2 >
	R eval(L2 l2)
	{
		return invoke<R>(f, l1, l2);
	}
};

Conclusion

Now you should have a starting point to be able to reference the bind expressions in both boost and the C++11 standard library. I did it a very different way, but the same constructs are there all the same. You should now have some idea how monotonous developing template based, variadic functions can be without the ability built into the language. It used to be that any time you wanted to write a variadic interface that was templated you had to do it like this. Now, in C++11, we have variadic templates. In a future installment I may show how you would do all of this with variadic templates. Even though this language feature now exists however, it may not be prudent to use it in all cases where you’d do something like this. Variadic templates, as defined in C++11, require recursive processing. This means you can not replicate the constant time lookup of things like boost::fusion::vector. You could, however, implement much of the helper objects with variadic templates and build the vector argument list with them. Any time you do this though your compile times are going to be slower for the most part…so it’s a cost/benefit analysis that you’ll need to perform.

One very important aspect of this version you should pay special attention to is that at no point is there any virtual function being called, no pointer indirection (unless the F parameter is one) and absolutely no RTTI such as dynamic_cast. This means that although there’s a good 200 lines of code or so here, the compiler can and often will get rid of all of that and just call the function directly! All of the above can be inlined. If you use functor objects instead of function pointers I’ve actually seen compilers generate VERY tight, small, inlined code where no function calls exist. Thus C++ can be a very good language for environments where speed and/or memory footprint are tight, such as embedded platforms (contrary to what many C fans will say :P). Although my last article focused on how binders can be made easily with dynamic dispatch and thus could be implemented in languages like C or Objective-C, and “missed the point of C++” as one silly comenter mentioned, this article extends the exact same concepts but leverages the full power of the C++ typing and template system.

Until next time, where I will discuss how the boost authors implemented the above and the additions they made, have fun.

Follow

Get every new post delivered to your Inbox.

Join 26 other followers