Archive for December, 2012

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.

Advertisements

Arbitrary binding pt2 – rolling your own.

Posted in Uncategorized on December 29, 2012 by Crazy Eddie

This article will discuss how arbitrary binding expressions work. Since the template syntax and meta-programming system can be a sticking point for some students, a runtime version will be described first to discuss the fundamentals. This also paves the way for readers interested in implementing this in some language that lacks generics or templates. Following this version will be a simplified template version that will be limited to 3 arguments. Upon conclusion you should be better prepared to understand the source code for boost::bind or std::bind.

Basic Object System

Since the runtime version of arbitrary binding requires a protocol for introspection a bit beyond what the C++ language does for its classes, a basic object system needs to be used and everything that can be an argument in a binder must inherit from a single base class. What follows is a very elementary set of such objects that will be used for further discussion. This can be done in any language–I’ve implemented this in C in the past–but C++ is used here because it’s just plain easier.


// This is basically all that is needed.  Every object in the system
// must inherit from this base class to allow the parameter system to work
// and then RTTI will take care of the rest because it's a polymorphic class.
struct Object {
  virtual ~Object() {}
};

// A couple obvious example classes...
struct Integer : Object {
	Integer(int i) : value(i) {}
	Integer() : value(0) {}

	Integer& operator = (int i) { value = i; return *this; }
	int get() const { return value; }

private:
	int value;
};

struct Double : Object {
	Double(double d) : value(d) {}
	Double() : value(0.) {}

	Double& operator = (double d) { value = d; return *this; }
	double get() const { return value; }

private:
	double value;
};

This basically provides a dynamic type system for C++. If everything inherits from Object then you can pass around anything as this base type. It’s like void pointers with a touch more predictability. This will be important for our non-templated bind expression system because in order to run arbitrary functions we need to be able to pass arbitrary types of information.

Placeholders and argument lists

The bind system is actually a fairly simple set of constructs and operations that correctly dispatch a call to the requested function with the correct arguments. What we will have is two lists of arguments, a function to call, a lookup operation that will translate arguments into values based on the argument lists and the parameters passed in, and a set of invokers that can be used to translate the two argument lists into a function call and invoke that function. The first argument list is what is provided when you bind to a function and it can contain placeholders. These placeholders point to indices within the second set of arguments, which are the arguments the bind type was invoked with. It is a very simple algorithm, but wrapping your head around it can be difficult without examples and explanation.

The first part of the system then is the argument list. In our case a vector of pointers to Object is quite sufficient. To make the lookup operation for this type then is not all that difficult. We first come up with a test:

BOOST_AUTO_TEST_CASE(lookup) {
	std::vector<Object*> args{ new Integer(0), new Integer(1), new Integer(2) };

	BOOST_CHECK(select_arg(args, a2) == args[1]); // pointer to the second element

	Integer * i = new Integer(42);
	BOOST_CHECK(select_arg(args, i) == i); // pointer to the parameter we passed in
}

In this case what we are testing is that when we pass in a placeholder–the a2 variable–we want the item from the argument list but when we pass in something else, anything else, we want that very same thing back instead. A placeholder then needs to simply be an index wrapped up in a very specific type:

struct Placeholder : Object {
	Placeholder(size_t i) : index(i) {}

	size_t get() const { return index; }

private:
	size_t index;
};

We also need access to particular placeholders to make our lives easier and to provide a well understood language for expressing, “I want the nth argument to go here in the invocation of function ‘f’.” In this runtime system we simply declare a few in the header and then later initialize them as constant globals:

// binder.h:
extern Placeholder *const a1;
extern Placeholder *const a2;
extern Placeholder *const a3;

// binder.cpp:
Placeholder *const a1 = new Placeholder(0);
Placeholder *const a2 = new Placeholder(1);
Placeholder *const a3 = new Placeholder(2);

Now the lookup function is rather rudimentary:

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

This will later serve as the central point to the bind invocation algorithm set.

Building argument lists

In this system we want to be able to bind to a function of arbitrary parameter count that can then be invoked with as many arguments as the call site provides. This requires variadic functionality and in our runtime system that means C-style variadic functions, the kind with ‘…’ as an argument. This will be done in at least two places: binder creation and binder invocation. Thus it is prudent to make this a separate operation that can be reused. First, the test:

std::vector<Object*> call_build_args(Object * obj, ...) {
	va_list ap{};
	va_start(ap, obj);
	std::vector<Object*> args = build_args(obj, &ap);
	va_end(ap);
	return args;
}

BOOST_AUTO_TEST_CASE(build_args_test) {
	std::vector<Object*> args = call_build_args(new Integer(2), new Integer(3), new Integer(5), END_ARGS);

	BOOST_CHECK(args.size() == 3);
	BOOST_CHECK(static_cast<Integer*>(args[0])->get() == 2);
	BOOST_CHECK(static_cast<Integer*>(args[1])->get() == 3);
	BOOST_CHECK(static_cast<Integer*>(args[2])->get() == 5);

	for(Object * obj : args) {
		delete obj;
	}

	args = call_build_args(END_ARGS);
	BOOST_CHECK(args.size() == 0);
}

The “call_build_args” function simply makes it easier to call our utility function that will actually require a va_list as its second argument. There’s no way to just build a va_list outside the parameters of a variadic function. You’ll note above the use of another constant called “END_ARGS”. This can be implemented with a special type if desired, but I simply implemented it by making a placeholder I’d never, ever use:

// binder.h:
extern Placeholder *const END_ARGS;

//binder.cpp:
Placeholder *const END_ARGS = new Placeholder(-1);

The “build_args” function now is again quite simple:

std::vector<Object*> build_args(Object * obj, va_list * ap) {
	std::vector<Object*> args{};

	while (obj != END_ARGS) {
		args.push_back(obj);
		obj = va_arg(*ap, Object*);
	}
	return args;
}

All we are doing is iterating the va_list we receive until we reach the end, which we must have a way of finding out and has been shown with the END_ARGS value, and shove the arguments into a vector of Object pointers. Now we have a way to easily construct our argument lists from any variadic function.

Invokers

The next major piece of the puzzle is an operation that can take a function, two lists of parameters, convert the two lists into a list of actual arguments and call the target function with them. This operation is actually going to be done here with the use of a dispatch table based on the number of parameters the target function takes. We know how many the target function takes because it’s the same amount that was provided to the binder creation.

To begin with we need a way to hand an arbitrary function type around to the invokers. This requires some type casting and by C++ standard it is type casting of the worst kind: reinterpret_cast. Used correctly though this construct’s use of reinterpret_cast won’t pose a major problem.

I did not write a unit test for this aspect of the system because it’s quite hidden within and is rather trivial. So here it is in full:

// binder.h
typedef void (*FUNPTR)();

// binder.cpp
typedef Object* (*INVOKER_T)(FUNPTR, std::vector<Object*> const&, std::vector<Object*> const&);

namespace {
Object* invoker0(FUNPTR fun, std::vector<Object*> const&, std::vector<Object*> const&) {
	return reinterpret_cast<Object*(*)()>(fun)();
}
Object* invoker1(FUNPTR fun, std::vector<Object*> const& a, std::vector<Object*> const& b) {
	return reinterpret_cast<Object*(*)(Object*)>(fun)(select_arg(b, a[0]));
}
Object* invoker2(FUNPTR fun, std::vector<Object*> const& a, std::vector<Object*> const& b) {
	return reinterpret_cast<Object*(*)(Object*,Object*)>(fun)(select_arg(b, a[0]), select_arg(b, a[1]));
}
Object* invoker3(FUNPTR fun, std::vector<Object*> const& a, std::vector<Object*> const& b) {
	return reinterpret_cast<Object*(*)(Object*,Object*,Object*)>(fun)(select_arg(b, a[0]), select_arg(b, a[1]), select_arg(b, a[2]));
}
std::vector<INVOKER_T> invokers{invoker0, invoker1, invoker2, invoker3 };
}

Our system is thus limited to functions that can take 3 or less parameters, though we are not bound in any way by how many arguments we can provide when we invoke it…which you will see in the next section.

Note how each invoker that invokes a function that has arguments is asking to select the argument from the second list based on the element in the first at the relative position in the argument list. This is the important step that does all the work. If, for example, the list of arguments we created the bind with were “0, 2, 3” then we want f called with those exact elements. However, if we say instead something like “a2, 2, 3”, then what we’re really creating is a binder that expects at least two arguments and that second argument will form the FIRST in the actual function call.

The last piece

The last piece of the puzzle is the actual binder object that can be created with a bind expression and then later invoked. The test first:

Object* add_two(Object * obj1, Object * obj2) {
	Integer *int1 = dynamic_cast<Integer*>(obj1);
	Integer *int2 = dynamic_cast<Integer*>(obj2);

	return new Integer(int1->get() + int2->get());
}

BOOST_AUTO_TEST_CASE(final_binder_check) {
	Integer i1{42};
	Integer i2{5};

	binder b1{reinterpret_cast<FUNPTR>(add_two), &i1, &i2, END_ARGS};

	Integer * result = static_cast<Integer*>(b1(END_ARGS));
	BOOST_CHECK(result->get() == 47);
	delete result;

	result = static_cast<Integer*>(b1(&i2, END_ARGS));
	BOOST_CHECK(result->get() == 47);
	delete result;

	binder b2(reinterpret_cast<FUNPTR>(add_two), &i1, a2, END_ARGS);
	result = static_cast<Integer*>(b2(0, &i1, END_ARGS));
	BOOST_CHECK(result->get() == 84);
	delete result;
}

Here we make sure that various combinations of placeholder vs. true argument are applied correctly. For example, in the last test for the b2 binder we are making sure that i1 is taken from the creation site, i1 again from the call site, and used together to call “add_two” to get the appropriate result of i1 + i1.

This then gives us the interface we must create:

struct binder : Object {
	binder(FUNPTR, Object * obj, ...);

	Object* operator()(Object * obj, ...) const;

private:
	FUNPTR fun;
	std::vector<Object*> args;
};

The first step then is to create the first set of arguments from the creation site and store them for later:

binder::binder(FUNPTR f, Object * obj, ...) : fun(f), args() {
	va_list ap{};
	va_start(ap, obj);
	args = build_args(obj, &ap);
	va_end(ap);
}

We then simply use our dispatch table to find the invoker that calls functions with the correct set of arguments (based on what was supplied to us at the creation site) and call it:

Object * binder::operator() (Object * obj, ...) const {
	va_list ap{};
	va_start(ap, obj);
	std::vector<Object*> args_b = build_args(obj, &ap);
	Object * rval = invokers[args.size()](fun, args, args_b);
	va_end(ap);
	return rval;
}

And that is that. We are done!

Conclusion

So as you can see, the algorithm for arbitrary binders is actually quite basic. Take two lists of arguments, one given at the bind creation site and the second at the point of invokation; use the first list to decide which elements in the second to use and in what order, and then invoke the bound function with a thus combined set of arguments. Any time you want to create a bind type of expression this is how it is done. In future installment(s) I will show how to take this exact same algorithm and apply it with templates to a type-safe bind expression that is much faster, and also to template meta-programming to recreate the boost MPL lambda construct. You will find that these concepts apply directly in all three cases though the application is of course quite different.

I have left many bugs in this system. The most obvious of course is that this thing doesn’t take any care about memory leaks at all. If I ran my unit tests in valgrind I’d be yelled at a lot. You will need to account for this somehow but the directions you can go here are so numerous and which you use completely beside the point of this exercise that I just left it out both for my own sanity and to keep things here quite simple. When I wrote arbitrary binding expressions in C I used an Objective-C like system of autorelease pools in all objects so the memory issues are fairly easy to deal with. There are other ways however and assuming they’re consistent you should have no problem at all applying this concept to your own object system to get good results.

Improvements to the caching variable trick

Posted in Uncategorized on December 29, 2012 by Crazy Eddie

In my last article, I explained how you can use functors to replicate lazy evaluation and caching. Several people mentioned some problems with that trick and I am going to now explain what those are and how to fix them. For review, here is the code from the last article:

template < typename T >
struct cached_value {
  cached_value(function<T()> c) : calculator(c) {}
  void invalidate() { cache_valid = false; }

  T operator() () {
    if (!cache_valid) {
      value = calculator();
      cache_valid = true;
    }
    return value;
  }  

private:
  bool cache_valid;
  T value;
  function<T()> calculator;
};

struct has_cache_value {
  cached_value<int> my_value;

  has_cache_value() 
    : my_value(bind(&has_cache_value::calculate, this))
  {}
private:
  int calculate() { return 5; }
  

The first one is rather glaring and points out that I need to be more careful about what I’m posting sometimes:

template < typename T >
struct cached_value {

  T operator() ();

};

There are some valid reasons why one might want to return a value rather than a reference, and to make my article much easier to read and limit the amount of assumptions made about the type, I decided to go with by value. This assumes though that the cost of copying T outweighs the cost of calculating it with the function attached to this caching functor. Furthermore, if your type is a raw type like a double, an integer, a pointer, etc…then passing by value can be cheaper than by reference. We should also consider making this function a const function.

First thing we need to do is establish what the return type will be. A standard used by many boost metafunctions is for functors to have a “result_of” typedef within them. This makes them easier to use with a variety of constructs including bind. So the first thing that’s going to happen is to calculate that type from the type of the template parameter. To do that we need a test (instructional articles from now on will include unit test code):

#include <boost/type_traits.hpp>
#include "../include/cached.hpp"

struct object
{
};

// Meta-function that returns a bool-type
// representing whether cached<T>::result_of
// is a reference.
template < typename T >
struct reference_check
  : boost::is_reference<typename cached<T>::result_of>
{};

BOOST_AUTO_TEST_CASE(reference_vs_value)
{
	BOOST_CHECK(!reference_check<int>::value);
	BOOST_CHECK(!reference_check<object*>::value);
	BOOST_CHECK(reference_check<object>::value);
}

The code that passes this test uses the boost MPL and type traits modules to decide if a reference should be added to type T for the result of the caching operator:

#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/or.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/type_traits.hpp>

template < typename T >
struct cached
{
	typedef typename boost::mpl::eval_if<
	  boost::mpl::or_<
	    boost::is_fundamental<T>
	  , boost::is_pointer<T>
	  >
	, boost::mpl::identity<T>
	, boost::add_reference<typename boost::add_const<T>::type>
	>::type result_of;
};

The second issue is more interesting. Many objects that we might want to cache are not default constructable and this cache class requires they are by holding a default initialized variable of type T. To change this, we’re going to have to use some alignment tricks and placement new/delete.

First though, lets finish the caching interface with the above changes and make unit tests for it:

// new headers in test code...
#include <boost/bind.hpp>

// altered 'object' definition...
struct object
{
	object() {}
	object(int i) : val(i) {}
	int val;
};

// test function...
object fun(int & count) { 
    ++count;
    return object(42); 
}

// test for caching...
BOOST_AUTO_TEST_CASE(non_default_construct)
{
	int count = 0;
	cached<object> cache(boost::bind(fun, boost::ref(count)));

	BOOST_CHECK(cache().val == 42);
	BOOST_CHECK(cache().val == 42);

	BOOST_CHECK(count == 1);

	cache.invalidate();

	BOOST_CHECK(cache().val == 42);
	BOOST_CHECK(count == 2);
	BOOST_CHECK(cache().val == 42);
	BOOST_CHECK(count == 2);
}

And the code that passes it:

template < typename T >
struct cached
{
	typedef typename ... result_of;

	result_of operator()() const {
		if (!valid) {
			valid = true;
			value = fun();
		}
		return value;
	}
	void invalidate() { valid = false; }

	cached(boost::function<T()> const& f)
	  : value()
	  , fun(f)
	  , valid(false)
	{}

private:
	mutable T value;
	boost::function<T()> fun;
	mutable bool valid;
};

Now we know that it works the way it should and can move on by removing the default constructor definition to ‘object’:

struct object
{
	object(int i) : val(i) {}
	int val;
};

And we get the failure we expect:

In file included from workspace/cached_variable/test/cacher_test.cpp:8:0:
workspace/cached_variable/test/../include/cached.hpp: In constructor ‘cached::cached(const boost::function&) [with T = object]’:
workspace/cached_variable/test/cacher_test.cpp:36:58: instantiated from here
workspace/cached_variable/test/../include/cached.hpp:33:17: error: no matching function for call to ‘object::object()’

To fix this we need to use placement new and have a storage buffer within which to do so. It is tempting to simply use a byte array for this but you can read Andrei Alexandrescu’s article on discriminated unions to see why this is a problem. To fix that problem we’ll use some boost type traits (that are included in the C++11 standard library) to calculate alignment and provide a correctly aligned buffer for storage of our type:

template < typename T >
struct cached
{
	typedef typename boost::mpl::eval_if<
	  boost::mpl::or_<
	    boost::is_fundamental<T>
	  , boost::is_pointer<T>
	  >
	, boost::mpl::identity<T>
	, boost::add_reference<typename boost::add_const<T>::type >
	>::type result_of;

	result_of operator()() const {
		if (!valid) {
			valid = true;
			new (value) T(fun()); // build from copy in place
		}
		return *value;
	}

	void invalidate() {
		if (valid) value->~T(); // destroy old one
		valid = false;
	}

	cached(boost::function<T()> const& f)
	  : storage()
	  , value(reinterpret_cast<T*>(&storage))
	  , fun(f)
	  , valid(false)
	{}

	~cached() { if (valid) value->~T(); }

private:
	typedef typename boost::aligned_storage<
	  sizeof(T)
	, boost::alignment_of<T>::value
	>::type storage_t;

	mutable storage_t storage;
	T * value;
	boost::function<T()> fun;
	mutable bool valid;
};

Now the only requirement of this object is that the value type it contains is copyable. Since it’s basically useless without this feature this requirement is acceptable. We can now cache any type we might want to and do so efficiently. There’s only one piece of improvement that I can immediately think of that needs to be done to this construct and that is to allow the user the power to override the result_of so that it can return references when it otherwise would not, or visa-versa. This is a relatively simple change to make. First the test:

BOOST_AUTO_TEST_CASE(reference_override)
{
	using namespace boost;
	BOOST_CHECK((is_reference<cached<int,int const&>::result_of>::value));
	BOOST_CHECK((!is_reference<cached<object,object>::result_of>::value));
}

And the production code where we simply move the calculation of result_of to a default template parameter:

template <
  typename T
, typename RESULT_OF = typename boost::mpl::eval_if<
    boost::mpl::or_<
      boost::is_fundamental<T>
    , boost::is_pointer<T>
    >
  , boost::mpl::identity<T>
  , boost::add_reference<typename boost::add_const<T>::type>
  >::type
>
struct cached
{
  typedef RESULT_OF result_of;
  ...
};      

It would also be possible to allow the user to override the storage mechanism but I’m not seeing much utility in that. At any rate, it is left to you, the reader, to perform that task if you need it.