Archive for the Template Metaprogramming Category

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):

struct matrix
{
    matrix(std::array<int,9> init) : vals(std::move(init)) {}

    int value(int i,int j) const
    {
        return vals[i * 3 + j];
    }

private:
    std::array<int, 9> vals;
};

template < typename Right
         , typename Left >
struct add_matrix
{
    add_matrix( Right const& r
              , Left const& l )
        : right(r)
        , left(l)
    {}

    add_matrix(add_matrix const& other)
        : right(other.right)
        , left(other.left)
    {}
    add_matrix & operator = (add_matrix const&) = delete;

    operator matrix () const
    {
        return matrix {{{ value(0,0), value(0,1), value(0,2)
                        , value(1,0), value(1,1), value(1,2)
                        , value(2,0), value(2,1), value(2,2) }}};
    }

    int value(int i, int j) const
    {
        return right.value(i,j) + left.value(i,j);
    }
private:
    Right const& right;
    Left const& left;
};

template < typename Right, typename Left >
auto operator + (Right const& r, Left const& l)
{
    return add_matrix<Right,Left>{r,l};
}

BOOST_AUTO_TEST_CASE(addition)
{
    auto m0 = matrix{{{ 1,2,3
                      , 4,5,6
                      , 7,8,9 }}};
    auto m1 = matrix{{{ 9,8,7
                      , 6,5,4
                      , 3,2,1 }}};

    auto exp = m0 + m1;
    matrix m = exp;

    for (int i = 0; i != 3; ++i)
    {
        for (int j = 0; j != 3; ++j)
        {
            BOOST_CHECK_EQUAL(exp.value(i,j), 10);
            BOOST_CHECK_EQUAL(m.value(i,j), 10);
        }
    }

    auto exp2 = m0 + m1;
    auto exp3 = exp + exp2;

    for (int i = 0; i != 3; ++i)
    {
        for (int j = 0; j != 3; ++j)
        {
            BOOST_CHECK_EQUAL(exp3.value(i,j), 20);
        }
    }
}

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.

Advertisements

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.

Arbitrary binding pt1 – What is boost::bind and why is it cool?

Posted in C++, Template Metaprogramming on April 22, 2012 by Crazy Eddie

The STL has always been a rather brilliant piece of generic coding. The principles applied created a rather wonderful set of tools that could be used for a variety of conditions without losing type safety and without introducing unnecessary coupling by forcing inheritance. The ability to write generic algorithms that work on any type matching a given concept really adds to the expressiveness and power of C++. Until the advent of boost::bind though, the actual, practical use of these generic algorithms was too painful to bother.

To understand what I mean by this claim, consider the following program that finds all employees that make more than 50k a year:

struct employee
{
    int salary() const;
private:
  // ...
};

// Write special function just to compare salary because binds don't nest:
bool makes_less_than(employee const& e, int amount)
{
    return e.salary() < amount;
}

std::vector<employee> find_all_that_make_50k(std::vector<employee> const& employees)
{
    std::vector<employee> rval;

    std::remove_copy_if(employees.begin(), employees.end(), std::back_inserter(rval), std::bind1st(std::ptr_fun(makes_less_than), 50000));

    return rval;
}

In reality you would either write a functor that does exactly what you need, inheriting from std::unary_function, or you’d just use a for loop because use of all these binds and can get really ugly really fast. Compare the above to the alternative version you can do with boost::bind or with the new std::bind.


std::vector<employee> find_all_that_make_50k(std::vector<employee> const& employees)
{
    std::vector<employee> rval;
 
    // standard version...
    std::remove_copy_if(employees.begin(), employees.end(), back_inserter(rval), bind(less<int>, bind(&employee::salary, _1), 50000));

    // boost version...
    std::remove_copy_if(employees.begin(), employees.end(), back_inserter(rval), bind(&employee::salary, _1) < 50000);

    return rval;
}

This bind construct is even more interesting that this. Say I have an object that will call a function when something happens and I want it to call a method on an object that only takes some of the arguments the other object supplies? In other words, consider what I would do here in this C++03 code:

struct does_something
{
    void set_callback(void (*)(int, double));
};

struct can_respond
{
    void functionA(double);
};

There’s really no reasonable way for me to bind those two things. The best kind of thing one might come up with is to use the observer pattern:

struct does_something_observer
{
    virtual ~does_something_observer() {}
    virtual respond(int, double) = 0;
};

struct does_something
{
    void set_observer(does_something_observer *);
};

struct can_respond : does_something_observer
{
    void function(double);
    void respond(int, double d) { function(d); }
};

This option is suboptimal for three reasons:

  1. It requires we couple can_respond to part of the interface of does_something by inheriting from its observer
  2. We can’t change constness. If we make the callback function const, then subclasses that change in response have to cast it away (dangerous). If we make it non-const then we can’t use const observers.
  3. We force can_respond to implement a signature it’s not interested in, it doesn’t care about the int

Furthermore, most observers have many signatures in them…which is why the Java API has “Adapters” you can inherit from when you only want to listen to one part of the signal interface. Not using this adapter requires that you implement all the functions in the observer interface even if only to make them empty. It’s just a bunch of extra garbage code that fills up the brain (because it has to read it and know why these empty functions are there) without doing anything.

However, when we add an arbitrary function object type like boost::function (which I describe on my old blog — go to “W0t” and follow there) we can get rid of both of these problems:

struct does_something
{
    void set_responder(function<void(int,double)>);
};

struct can_respond
{
    void function(double);
};

does_something ds;
can_respond cr;

ds.set_responder(bind(&can_respond::function, ref(cr), _2));

The great thing here is that we’ve created a 2 argument function object out of a binding that will only use 1 of those arguments to call a function that only accepts one of them. The binder object created by bind can take an arbitrary, implementation defined amount of arguments and they can be anything. Only upon being called (well, when the call has to be compiled) does the system check whether or not the target function can take the arguments supplied, whether they match types, or whether they can be converted and how to do it. Basically, when you assign the binder to the function object by calling set_responder it will attempt to compile operator () with the two arguments that function object’s signature represents. This then will decide what happens.

Using these concepts and adding some loop processing and connection management, the boost::signals and signals2 libraries create a signal/slot mechanism that really surpasses any of the alternatives in its expressive power and in helping keep the coupling to a minimum. Unlike any other event marshaling system, which all require adherence to some specific signature and/or inheritence from a particular object, this system allows you to connect events to any object that can respond to them…ignoring or accepting any information provided by the event source.

THAT is pretty darn cool and brilliantly expressive. It wouldn’t be even half as great without the arbitrary binder. How was this binder created? Stay tuned for the next episode of “Arbitrary Binding”: “How to write your own arbitrary binder”

An easier way to select types

Posted in cpp, Template Metaprogramming on February 16, 2011 by Crazy Eddie

The Boost Template Meta-Programming Library is a very powerful library but there are some things that become necessary that can make things really tough to read. One example is having to nest if ‘blocks’ instead of having an ‘else if’. Considder

template < typename T >
struct match_type
  : mpl::if_
    <
      std::is_same<T, mpl::true>
    , double
    , if_
      <
        std::is_same<T, int>
      , char*
      , long
      >::type
    >
{};

Imagine that this went on for 5 checks or more. It becomes quite ungainly.

With this specific example we could use an mpl::map and things would be much easier. What if we where doing something else though? What if we really did need to run some metafunction on T in order to decide?

So I decided to create something a bit simpler to work with, a sort of “select/case” mechanism though at this time it doesn’t exactly match the same semantics as your standard switch statement. At any rate, here it is:


#include <boost/mpl/identity.hpp>
#include <boost/mpl/bool.hpp>
#include <boost/mpl/if.hpp>
#include <boost/mpl/lambda.hpp>
#include <boost/mpl/placeholders.hpp>
#include <type_traits>

using namespace boost;
using namespace boost::mpl::placeholders;

template < typename Test, typename Result >
struct case_ : Result 
{
};
template < typename Result >
struct default_ : Result {};

struct null_ {};

template < typename Switch
         , typename C1 = null_
         , typename C2 = null_
         , typename C3 = null_
         , typename C4 = null_ >
struct select_ {};

template < typename Switch, typename C1Test, typename C1Result, typename C2, typename C3, typename C4 >
struct select_<Switch, case_<C1Test, C1Result>, C2, C3, C4>
  : mpl::if_
    <
      typename C1Test::template apply<Switch>::type
    , C1Result
    , select_<Switch, C2, C3, C4>
    >::type
{
};

template < typename Switch, typename C1Result, typename C2, typename C3, typename C4 >
struct select_<Switch, default_<C1Result>, typename C2, typename C3, typename C4 >
  : C1Result
{};

// test code...

#include <iostream>
#include <typeinfo>


template < typename Var >
struct test_select
  : select_
    < Var
    , case_
      <
        mpl::lambda< std::is_same<_, mpl::true_> >::type
      , mpl::identity<double> 
      >
    , case_
      <
        mpl::lambda< std::is_same<_, int> >::type
      , mpl::identity<char*>
      >
    , default_< mpl::identity<long> >
    >
{};


// select as metafunction class...

template < typename C1 = null_
         , typename C2 = null_
         , typename C3 = null_
         , typename C4 = null_ >
struct select
{
  template < typename Switch >
  struct apply : select_<Switch, C1,C2,C3,C4> {};
};

// test select as metafunction class.
typedef select
    < case_
      <
        mpl::lambda< std::is_same<_, mpl::true_> >::type
      , mpl::identity<double> 
      >
    , case_
      <
        mpl::lambda< std::is_same<double, int> >::type
      , mpl::identity<char*>
      >
    , default_< mpl::identity<long> >
    > my_select;

// visually verify answer
int main()
{
  std::cout << typeid( test_select<double>::type ).name() << std::endl;
  std::cout << typeid( my_select::apply<int>::type ).name() << std::endl;
}

This could be easily adjusted to run the second parameter to ‘case_’ as a metafunction instead of simply grabbing a type.

Hello world!

Posted in Template Metaprogramming on January 16, 2011 by Crazy Eddie

Yes, you can.

#include <boost/mpl/string.hpp>
#include <boost/mpl/insert.hpp>
#include <boost/mpl/end.hpp>

namespace mpl = boost::mpl;

template < typename S1, typename S2 >
struct concat 
  : mpl::insert
    <
      S1
    , typename mpl::end<S1>::type
    , S2
    > 
{};

typedef mpl::string<'hell', 'o'> hello;
typedef mpl::string<'worl', 'd!'> world;

typedef concat
< 
  concat
  <
    hello
  , mpl::string<' '> 
  >::type
  , world
>::type because_i_can;

#include <iostream>
int main()
{
  std::cout << mpl::c_str<because_i_can>::value << std::endl;
}