“I’ve been doing some template metaprogramming lately,” he said nonchallantly.
Why is it funny? Because template metaprogramming is considered really hard. I mean, über-guru-level hard. I’m lucky to be friends with two such gurus, Andrei Alexandrescu who wrote the seminal “Modern C++ Programming,” and Eric Niebler, who implemented the Xpressive library for Boost; so I know the horrors.
But why is template metaprogramming so hard? Big part of it is that C++ templates are rather ill suited for metaprogramming, to put it mildly. They are fine for simple tasks like parameterized containers and some generic algorithms, but not for operations on types or lists of types. To make things worse, C++ doesn’t provide a lot in terms of reflection, so even such simple tasks like deciding whether a given type is a pointer are hard (see the example later). Granted, C++0x offers some improvements, like template parameter packs; but guru-level creds are still required.
So, I’ve been doing some template metaprogramming lately… in D. The D programming language doesn’t have the baggage of compatibility with previous botched attempts, so it makes many things considerably easier on programmers. But before I get to it, I’d like to talk a little about the connection between generic programming and functional programming, give a short intro to functional programming; and then show some examples in C++ and D that involve pattern matching and type lists.
It’s not your father’s language
The key to understanding metaprogramming is to realize that it’s done in a different language than the rest of your program. Both in C++ and D you use a form of functional language for that purpose. First of all, no mutation! If you pass a list of types to a template, it won’t be able to append another type to it. It will have to create a completely new list using the old list and the new type as raw materials.
Frankly, I don’t know why mutation should be disallowed at compile time (all template calculations are done at compile time). In fact, for templates that are used in D mixins, I proposed not to invent a new language but to use a subset of D that included mutation. It worked just fine and made mixins much easier to use (for an example, see my DrDobbs article).
Once you disallow mutation, you’re pretty much stuck with functional paradigm. For instance, you can’t have loops, which require a mutable loop counter or some other mutable state, so you have to use recursion.
You’d think functional programmers would love template metaprogramming; except that they flip over horrendous syntax of C++ templates. The one thing going for functional programming is that it’s easy to define and implement. You can describe typeless lambda calculus with just a few formulas in operational semantics.
One thing is important though: meta-language can’t be strongly typed, because a strongly typed language requires another language to implement generic algorithms on top of it. So to terminate the succession of meta-meta-meta… languages there’s a need for either a typeless, or at least dynamically-typed, top-level meta-language. My suspicion is that C++0x concepts failed so miserably because they dragged the metalanguage in the direction of strong typing. The nails in the coffin for C++ concepts were concept maps, the moral equivalent of implicit conversions in strongly-typed languages.
Templates are still not totally typeless. They distinguish between type arguments (introduced by typename or class in C++), template template arguments, and typed template arguments. Here’s an example that shows all three kinds:
template<class T, template<class X> class F, int n>
Functional Programming in a Nutshell
“Functions operating on functions”–that’s the gist of functional programming. The rest is syntactic sugar. Some of this sugar is very important. For instance, you want to have built-in integers and lists for data types, and pattern matching for dispatching.
-Functions
Here’s a very simple compile-time function in the C++ template language:
template<class T>
struct IsPtr {
static const bool apply = false;
}
If it doesn’t look much like a function to you, here it is in more normal ad-hoc notation:
IsPtr(T) {
return false;
}
You can “execute” or “call” this meta-function by instantiating the template IsPtr with a type argument and accessing its member apply:
IsPtr<int>::apply;
There is nothing magical about “apply”, you can call it anything (“result” or “value” are other popular identifiers). This particular meta-function returns a Boolean, but any compile-time constant may be returned. What’s more important, any type or a template may be returned. But let’s not get ahead of ourselves.
-Pattern matching
You might be wondering what the use is for a function (I’ll be dropping the “meta-” prefix in what follows) that always returns false and is called IsPtr. Enter the next weapon in the arsenal of functional programmers: pattern matching. What we need here is to be able to match function arguments to different patterns and execute different code depending on the match. In particular, we’d like to return a different value, true, for T matching the pattern T*. In the C++ metalanguage this is done by partial template specialization. It’s enough to define another template of the same name that matches a more specialized pattern, T*:
template<class T>
struct IsPtr<T*> {
static const bool apply = true;
}
When faced with the call,
IsPtr<int*>::apply
the compiler will first look for specializations of the template IsPtr, starting with the most specialized one. In our case, the argument int* matches the pattern T* so the version returning true will be instantiated. Accessing the apply member of this instantiation will result in the Boolean value true, which is exactly what we wanted. Let me rewrite this example using less obfuscated syntax.
IsPtr(T*) {
return true;
}
IsPtr(T) { // default case
return false;
}
D template syntax is slightly less complex than that of C++. The above example will read:
template IsPtr(T) {
static if (is (T dummy: U*, U))
enum IsPtr = true;
else
enum IsPtr = false;
}
// Compile-time tests
static assert( IsPtr!(int*) );
static assert( !IsPtr!(int) );
As you can see, D offers compile-time if statements and more general pattern matching. The syntax of pattern matching is not as clear as it could be (what’s with the dummy?), but it’s more flexible. Compile-time constants are declared as enums.
There is one little trick (a hack?) that makes the syntax of “function call” a little cleaner. If, inside the template, you define a member of the same name as the template itself (I call it the “eponymous” member) than you don’t have to use the “apply” syntax. The “call” looks more like a call, except for the exclamation mark before the argument list (a D tradeoff for not using angle brackets). You’ll see later how the eponymous trick fails for more complex cases.
-Lists
The fundamental data structure in all functional languages is a list. Lists are very easy to operate upon using recursive algorithms and, as it turns out, they can be used to define arbitrarily complex data structures. No wonder C++0x felt obliged to introduce a compile-time type list as a primitive. It’s called a template parameter pack and the new syntax is:
template<class... T>Foo
You can instantiate such a template with zero arguments,
Foo<>
one argument,
Foo<int>
or more arguments,
Foo<int, char*, void*>
How do you iterate over a type list? Well, there is no iteration in the metalanguge so the best you can do is to use recursion. To do that, you have to be able to separate the head of the list from its tail. Then you perform the action on the head and call yourself recursively with the tail. The head/tail separation is done using pattern matching.
Let me demonstrate a simple example from the paper Variadic Templates by Garry Powell et al. It calculates the length of a pack using recursion. First, the basic case–length-zero list:
template<>
struct count <> {
static const int value = 0;
}
That is the full specialization of a template, so it will be tried first. Here’s the general case:
template<typename Head, typename... Tail>
struct count<Head, Tail...> {
static const int value = 1 + count<Tail...>::value;
}
Let’s see what it would look like in “normal” notation:
count() {
return 0;
}
count(head, tail) {
return 1 + count(tail);
}
And here’s the D version:
template count(T...) {
static if (T.length == 0)
enum count = 0;
else
enum count = 1 + count!(T[1..$]);
}
// tests
static assert( count!() == 0);
static assert( count!(int, char*, char[]) == 3);
T… denotes a type tuple, which supports array-like access. To get to the tail of the list, D uses array slicing, where T[1..$] denotes the slice of the array starting from index 1 up to the length of the array (denoted by the dollar sign). I’ll explain the important differences between C++ pack and D tuple (including pack expansion) in the next installment.
Conclusion
When looked upon from the functional perspective, template metaprogramming doesn’t look as intimidating as it it seems at first. Knowing this interpretation makes you wonder if there isn’t a better syntax or even a better paradigm for metaprogramming.
I’ll discuss more interesting parts of template metaprogramming in the next installment (this one is getting too big already). In particular, I’ll show examples of higher order meta-functions like Filter or Not and some interesting tricks with type lists.
Spawning a thread in non-functional languages is considered a very low-level primitive. Often spawn or CreateThread takes a function pointer and an untyped (void) pointer to “data”. The newly created thread will execute the function, passing it the untyped pointer, and it’s up to the function to cast the data into something more palatable. This is indeed the lowest of the lowest. It’s the stinky gutters of programming.
Isn’t it much nicer to create a Thread or a Runnable object and let the ugly casting be done under the covers? But, as I argued before, the Thread object doesn’t really buy you much in terms of the most important safety issue: the avoidance of data races. So we can have a Thread object instead of a void pointer, and a run method that understands the format of the Thread object (or Runnable, take your pick). But because the Thread /Runnable object has reference semantics, we still end up inadvertently sharing data between threads. Unless the programmer consciously avoids or synchronizes shared access, he or she is left exposed to the most vile concurrency bugs–by default!
As they say, Cooks cover their mistakes with sauces; doctors, with six feet of dirt; language designers, with objects.
Requirements
But enough ranting! I have the opportunity to design the spawn function for D and I don’t want to do any more cover-ups beyond hiding the ugly systems’ APIs. Here are my design requirements:
- spawn should take an arbitrary function as the main argument. It should refuse (at compile time) delegates or closures, which would introduce back-door sharing. (This might be relaxed later as we gain experience in controlling the sharing.)
- It should take a variable number of arguments of the types compatible with those of the function parameters. It should detect type mismatches at compile time.
- It should refuse the types of arguments that are prone to introducing data races. For now, I’ll allow only value types, immutable types, and explicitly shared types (shared is a type modifier in D).
I wish I could use the more precise race-free type system that I’ve been describing in my previous posts, but since I can’t get it into D2, there’s still a little bit of “programmer beware” in this implementation.
These requirement seem like a tall order for any language other than D. I wouldn’t say it’s a piece of cake in D, but it’s well within the reach of a moderately experienced programmer.
Unit Tests
Let me start by writing a little use case for my design (Oh, the joys of extreme programming!):
S s = { 3.14 };
Tid tid = spawn(&thrFun, 2, s, "hello");
tid.join;
Here’s the definition of the function, thrFun:
void thrFun(int i, S s, string str) {
writeln("thread function called with: ", i, ", ", s.fl, " and ", str);
}
Its parameter types fulfill the restrictions I listed above. The int is a value and so is S (structs are value types in D, unless they contain references):
struct S {
float fl;
}
Interestingly, the string is okay too, because its reference part is immutable. In D, a string is defined as an array of immutable characters, immutable (char)[].
Besides positive tests, the even more important cases are negative. For instance, I don’t want spawn to accept a function that takes an Object as argument. Objects are reference types and (if not declared shared) can sneak in unprotected sharing.
How do you build unit tests whose compilation should fail? Well, D has a trick for that (ignore the ugly syntax):
void fo(Object o) {}
assert (!__traits(compiles,
(Object o) { return spawn(&fo, o); }));
This code asserts that the function literal (a lambda),
(Object o){ return spawn(&fo, o); }
does not compile with the thread function fo. Now that’s one useful construct worth remembering!
Implementation
Without further ado, I present you with the implementation of spawn that passes all the above tests (and more):
Tid spawn(T...)(void function(T) fp, T args)
if (isLocalMsgTypes!(T))
{
return core.thread.spawn( (){ fp(args); });
}
This attractively terse code uses quite a handful of D features, so let me first read it out loud for kicks:
As you may guess, the newly spawned thread runs the closure, so it has access to captured args from the original thread. In general, that’s a recipe for a data race. What saves the day is the predicate isLocalMsgTypes, which defines what types are safe to pass as inter-thread messages.
Note the important point: there should be no difference between the constraints imposed on the types of parameters passed to spawn and the types of messages that can be sent to a thread. You can think of spawn parameters as initial messages sent to a nascent thread. As I said before, message types include value types, immutable types and shared types (no support for unique types yet).
Useful D features
Let me explain some of D novelties I used in the definition of spawn.
A function with two sets of parenthesized parameters is automatically a template–the first set are template parameters, the second, runtime parameters.
-Tuples
Type tuples, like T…, represent arbitrary lists of types. Similar constructs have also been introduced in C++0x, presumably under pressure from Boost, to replace the unmanageably complex type lists.
What are the things that you can do with a type-tuple in D? You can retrieve its length (T.length), access its elements by index, or slice it; all at compile time. You can also define a variable-argument-list function, like spawn and use one symbol for a whole list of arguments, as in T args:
Tid spawn(T...)(void function(T) fp, T args)
Now let’s go back to my test:
Tid tid = spawn(&f, 2, s, "hello");
I spawn a thread to execute a function of three arguments, void f(int i, S s, string str). The spawn template is instantiated with a type tuple (int, S, string). At compile time, this tuple is successfully tested by the predicate isLocalMsgTypes. The actual arguments to spawn, besides the pointer to function, are (2, s, “hello”), which indeed are of correct types. They appear inside spawn under the collective name, args. They are then used as a collective argument to fp inside the closure, (){ fp(args); }.
-Closures
The closure captures the arguments to spawn. It is then passed to the internal function (not a template anymore),
core.thread.spawn(void delegate() dlg)
When the new thread is created, it calls the closure dlg, which calls fp with the captured arguments. At that point, the value arguments, i and s are copied, along with the shallow part of the string, str. The deep part of the string, the buffer, is not copied–and for a good reason too– it is immutable, so it can safely be read concurrently. At that point, the thread function is free to use those arguments without worrying about races.
-Restricted Templates
The if statement before the body of a template is D’s response to C++0x DOA concepts (yes, after years of design discussions, concepts were finally killed with extreme prejudice).
if (isLocalMsgTypes!(T))
The if is used to create “restricted templates”. It contains a logical compile-time expression that is checked before the template is instantiated. If the expression is false, the template doesn’t match and you get a compile error. Notice that template restrictions not only produce better error messages, but can also impose restrictions that are otherwise impossible or very hard to enforce. Without the restriction, spawn could be called with an unsuitable type, e.g. an Object not declared as shared and the compiler wouldn’t even blink.
(I will talk about template restrictions and templates in general in a future blog.)
–Message Types
Besides values, we may also pass to spawn objects that are declared as immutable or shared (in fact, we may pass them inside values as well). In D, shared objects are supposed to provide their own synchronization–their methods must either be synchronized or lock free. An example of a shared object that you’d want to pass to spawn is a message queue–to be shared between the parent thread and the spawned thread.
You might remember that my race-free type system proposal included unique types, which would be great for message passing, and consequently as arguments to spawn (there is a uniqueness proposal for Scala, and there’s the Kilim message-passing system for Java based on unique types). Unfortunately, unique types won’t be available in D2. Instead some kind of specialized Unique library classes might be defined for that purpose.
Conclusion
The D programming language has two faces. On the one hand, it’s easy to use even for a beginner. On the other hand, it provides enough expressive power to allow for the creation of sophisticated and safe libraries. What I tried to accomplish in this post is to give a peek at D from the perspective of a library writer. In particular I described mechanisms that help make the concurrency library safer to use.
This is still work in progress, so don’t expect to see it in the current releases of D2.
Bartosz Milewski's Programming Cafe 