Archive for the Uncategorized Category

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.

Simple little cashing variable or property trick

Posted in Uncategorized on September 13, 2012 by Crazy Eddie

The trick I talked about earlier regarding exposing a single ‘variable’ to a friend can be used for other things as well. How useful I’ll leave you to determine. These ideas can likely be enhanced quite a bit to perform for more general solutions but I’ve not yet spent much time on them. Here goes:

Cached variable…

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; }
  

Mimicking “properties” (not sure why you would, but just because I can…)

// I didn't do a test on this but am fairly confident it works, or is at least close.
template < typename T >
struct property {
  property(function<void(T)> ass, function<T()> get)
    : assigner(ass)
    , getter(get)
  {}
  
  property& operator = (T t) { assigner(t); }
  operator (T) () const { return getter(); }

private:
  function<void(T)> assigner;
  function<T()> getter;
};

// use similarly.  Allows the calling of getter/setter using assignment syntax...
// object.property = value;
// type value = object.property;

Using wrappers like this for member variables can actually be used for all kinds of possibly useless stuff.

Does Karl Popper have anything to say on testing?

Posted in Uncategorized on May 24, 2012 by Crazy Eddie

I have noticed a tendency among many to hold what I consider a misunderstanding about testing, especially unit testing. For example, when I brought up the topic of testing critical sections, the first response and many after the fact seemed to focus on an inability to prove, through testing, that a multi-threaded component contains no bugs. Being the empiricist that I am, I tend to find this kind of response and this assumption about testing to be extremely questionable at best.

In some respects, and at a very theoretical level, computer programming is an a priori application of logic. Functions are mathematical constructs of pure logic that at least technically can be proven to be correct or incorrect through the rigorous application of predicate logic. In the older days I gather that this was the primary view of software development and programmers proved their code from start to finish.

Nobody does this today; nobody sane anyway. There are still a few adherents to the idea of proven code but instead of proving an entire program they prove individual functions. This seems a lot more realistic and practical, but it still runs into a fundamental problem with a priori understanding: the outcome of your proof is dictated more upon your understanding of the problem than on the reality of it.

Almost all developers in today’s landscape have learned that testing a product before releasing it is an absolute requirement. Many have also learned that you need to go even further than this and test each individual module or unit within the product as well. This is, however, a completely different approach from proofing and would be utterly unnecessary if proofing were possible or practical. Modern software engineering though has become way too complex to support the idea of proofing as a practical exercise and the difficulty in predicting behavior in parallel processing has perhaps made the idea ridiculous as well.

We don’t need to assert the impracticality or impossibility of proving a program at this point though. What only needs to be considered is how different the approaches between proof and testing are and to realize that while one method is entirely philosophical in its application, the other is empirical and scientific. Although math is considered a science by many, it is actually more in line with philosophical thinking and mathematical formulas, no matter how correct they seem…must always be checked against the real world to make sure the universe they model is the one we live in.

If proving your code is the philosophical approach then testing is the empirical one, the scientific one. I believe it worth reviewing then what this means in other sciences and what the philosophy of science itself says on the matter–unlike what Lawrence Krause might say I think the philosophy of science has done a great deal to improve the practice of science itself, especially the views of Karl Popper who did much to hone science into the workhorse it is today.

The definitive work on modern science and how it differs from pseudo-sciences like astrology was laid out in Popper’s article, Science as Falsification. Through it and other works he explains how science increases human knowledge not by showing what is true, but by showing what is false. We know that bricks of gold don’t fly not because we’ve proven that they don’t…but that we’ve shown that they do not. Relativity is viewed as true not because it’s been proven so, but because it’s the only theory that has not been proven false yet under most conditions. When a scientist comes up with a new theory it’s because they’re showing some previous theory wrong. When they test the theory they don’t go looking for ways to validate it, they look for ways to falsify it and if that cannot be done then the theory stands until it can be. This is the main reason why unfalsifiable statements are not scientific and I would go further to assert that they’re nonsense anyway.

This is the view that people should have toward software testing. When you’re writing your tests, be they integration, unit, or some other level of testing, you should focus not on proving that your code works but on showing that it doesn’t NOT work. Your code is your theory about how to solve a particular problem; your tests should attempt to falsify that theory. You should not view your tests as validating or justifying your code, but as a continuing effort to fix code that fails to work in some way.

With this in mind then it would become absurd to claim that tests prove code works or that tested code contains no bugs just like it is absurd to claim that any one of our scientific theories represents the whole and entire truth. Science works better than anything else for the very reason that it does NOT work in proofs nor make grandiose claims of absolute knowledge. Science works because the exercise of filtering away bad ideas, mistaken assumptions, and incomplete understanding sharpens our ability to manipulate the universe toward our own ends. Software development, as both a science and discipline of engineering, can and should be approached with the same understanding.

Being friendly without being a slut

Posted in Uncategorized on October 6, 2011 by Crazy Eddie

So you’ve got some sort of problem that you cannot solve without friendship. Being the design oriented developer you are you know that this level of coupling is pretty major and best to be avoided, but you simply can’t avoid it; you absolutely need access to some internal functionality to be exposed to special classes. Knowing how bad it is, and not wanting to encourage developers working on your friends to start molesting you freely, you want to show just enough skin to get the job done. But C++ doesn’t provide any way to do this… or does it?

#include <iostream>

struct almost_friendly
{
  struct funktor
  {
    funktor(almost_friendly * t) : this_(t) {}

  private:
    void operator() ()
    {
      this_->something_private();
    }
    almost_friendly * this_;

    friend struct has_special_access;
  };

  funktor fun;

  almost_friendly() : fun(this) {}

private:
  void something_private() { std::cout << "Only has_special_access can call this.\n"; }
};

struct has_special_access
{
  void fun() { almost_friendly().fun(); }
};

int main() { has_special_access().fun(); }

Lambda capture and object lifetime

Posted in Uncategorized on April 6, 2011 by Crazy Eddie

Someone brought up an issue in comp.lang.c++ today that might be unexpected enough to some that it warrants discussion. Consider the following code

include <functional>
struct up_chuck
{
  int x;

  std::function<int()> get_fun() const
  {
    return [=](){return x;}
  }
};

int main()
{
  auto fun = up_chuck().get_fun();
  
  fun();
}

What do you expect to happen here? If you expect the lambda clause to capture a copy of ‘x’ and create a function that returns it then you’d be quite unfortunately wrong. The issue here is that member variables are not captured directly; the variable that is actually captured is ‘this’! What this means of course is that the lambda captures the ‘this’ pointer by value, making a copy of it, and then using that pointer to access ‘x’ and return it. We can prove this with a different main function:

#include <iostream>
int main()
{
  up_chuck uc;
  uc.x = 0;

  auto fun = uc.get_fun();

  std::cout << fun() << std::endl;
  uc.x = 42;
  std::cout << fun() << std::endl;
}

If you expect that the output of this program should be “0\n0\n” then I suggest you run it and verify that you’ll NOT get that output.

So then, what will happen to our original program if we compile and run it? Well, since the lambda makes a copy of the ‘this’ pointer and accesses its x variable to return it, the behavior of the program is undefined. Since the object that ‘this’ points to is a temporary that is destroyed as soon as the line that creates the ‘fun’ variable is complete, the function that ‘fun’ is now makes use of a dangling pointer.

So what can we do in order to avoid running into this problem? The one thing I can think of is to never, ever use default capture clauses in your lambdas. If we’d written our lambda and attempted to capture ‘x’ by value it would become clear that we’ve got a problem. Then we could assign that value locally and capture that new variable and everything would work fine. If we really do need to capture ‘this’ then we do so explicitly and we know that we’re going to have lifetime issues because we’ve captured a pointer. Thus never using the default capture syntax can at least point out some possible problems to us.