• entries
628
1454
• views
1010700

# Fun with templates. "Fun." Ha, ha.

1328 views

So I have an interesting situation where I wrote a math-intensive API to allow easy composition of various functions. The details are pretty easy so I'll just show an example of what the API usage looks like:

formula.Create() .Set(0.0f) .AddWithWeight(some_data_source, 0.5f) .Multiply(other_data_source) .Display();The API is meant to operate on non-primitive objects, such as 2D arrays. This gives the end user a really powerful way to stitch together different operations without making the code unreadable or long.

Internally it does what you would guess: Create() allocates some working space to do the math in, and the operations pretty much do what it says on the tin, using that working space. Each function simply returns a reference to the "formula" object (*this) so that the operations can be chained arbitrarily.

Now, here comes the interesting bit: I want to change the API to support not just 2D arrays, but more sophisticated data structures, like, say, a quadtree. Operations should be able to mix and match types so that you can do things like prune the quadtree to only reference certain cells, grab all the objects in those cells, and do some calculus on some property of those objects.

Also, dynamic allocation is forbidden (inside the API implementation itself) and the syntax needs to retain the readability and succinctness of the original.

My first thought (being obsessed with compilers) was to build a sort of syntax tree that represents the operations and then traverse that to do the math. This is a failure on the dynamic allocation front, though, and also introduces a lot of overhead in terms of understanding how the code works. In other words, it involves a lot of machinery that the end user shouldn't have to care about, and maintainers shouldn't be burdened with.

My second thought (being obsessed with compilers) was to throw template metaprogramming at it. This has only one weakness, namely that templates do not work with floating-point numbers - making it impossible to do things like the AddWithWeight() call in the first example. Well, impossible without some fudging, anyways.

To fix the limitation on floating point literals, I decided to use a simple layer of indirection. Instead of putting "1.0" or "7.5" in my code, I use an enumeration value like CONSTANT_ONE or CONSTANT_FOO, since those can be used for template specializations. Then I do just that: specialize some templates to yield the correct floating point numbers on demand.

The next step is to describe the API from a user's perspective. I fiddled around a bit and came up with this:

 CreateFormula< int, Add, Add, Multiply, DumpResult >();This does add some ugly to things, namely in that the "int" type is now littered all over the code. Frankly, though, I think this is more of a problem in the silly examples than in real life, because in real life the API is used with many different types, so being able to specify a type at each step of the process is pretty handy. It also opens up the door for template-specialization-based optimizations.

Now that I know what I want the API to look like, it's time to build the implementation:

#include enum EDataSource { DATA_SOURCE_CONSTANT_0, DATA_SOURCE_CONSTANT_1, DATA_SOURCE_CONSTANT_4,};template struct Add { };template struct Add { static void Invoke (T * state) { *state += T(1); }};template struct Multiply { };template struct Multiply { static void Invoke (T * state) { *state *= T(0); }};template struct Multiply { static void Invoke (T * state) { *state *= T(4); }};struct DumpResult { static void Invoke (int * state) { std::cout << *state << std::endl; }};struct Null { static void Invoke (int *) { }};template struct CreateFormula { CreateFormula () { T state = T(); O1::Invoke(&state); O2::Invoke(&state); O3::Invoke(&state); O4::Invoke(&state); }};int _tmain (int argc, _TCHAR* argv[]) { CreateFormula< int, Add, Multiply, DumpResult >(); CreateFormula< int, Add, Add, Multiply, DumpResult >(); return 0;}What we have here is pretty straightforward. Each operation is represented by a struct template. In this case, operations always take exactly two parameters: one to tell the code what type the operation works on, and one to specify the data for the operation. We then use template specialization, as described above, to yield specific data values based on the enumeration. In more realistic code, instead of just having constants, we could have things like "list containing the locations of all nearby sandwiches" or whatever else.

Note that the operation structs have a single static function, Invoke. Invoke takes some "state" and goofs with it; nothing more, nothing less. This is the guts of each operation.

There are two operations worth calling out: DumpResult and Null. DumpResult is simply a way to take the state from the previous operation and put it on the screen. Null is a way to say "don't do anything" - this will come in handy momentarily.

The ugly beast is the CreateFormula template. This guy needs lots of optional template parameters so we can have formulas of varying length. Each optional parameter defaults to Null so that operations which are omitted from the template's type definition can be elided entirely.

Internally, CreateFormula has a single constructor, which does something that should sound really familiar: creates some state, passes it off to a series of operations, and then returns. Note that no dynamic allocation is necessary here; more sophisticated data structure usage might make it tempting to add more dynamic allocations, but that's not really the API's problem - it's down to the user to do the right thing.

Last but not least, in the main() function we see two examples of the template in action. It looks pretty darn close to the original, exactly like the syntax we wanted for the new model, and has the added benefit (over the original) of being more explicit about what's going on at each step.

As you might guess, the real application for this is a lot more complex. It doesn't limit itself to simple operations like add and multiply - there's analytical differentiation, integration by sampling, optimization (i.e. "highest" and "lowest") queries, and so on. So the actual operations are much richer. This is the main reason why operator overloading is not useful; we simply run out of squiggly symbols for all the different operations.

Another thing worth mentioning here is that modern compilers are exceptionally good at figuring out what's really going on in this code. When using int as the state type, for example, Visual C++ compiles the entire thing out and just passes a literal result to std::cout. Pretty cool.

I have no idea if this is remotely useful, mostly because I'm not convinced it's useful to me even, but it was a nifty trick and I felt like sharing. So there.

There are no comments to display.

## Create an account

Register a new account