Templates (code that generates code) usually fall in the advanced techniques category, and rightly so. Yet, D's approach to templates is so down-to-earth, and programming with D's templates is so exhilarating, it would be unjust to introduce D without giving a flavor of what its templates look like.
Templates started out in C++ as parameterized types (useful for things like generic containers and algorithms), but soon their use has grown well beyond that, getting into full-blown code generation. Harnessing such power is as much a black art as is mastering LISP macros—another generative technique. To wit, some later languages (such as Java or C#) have given up the code generation aspect, focusing exclusively on the easily tamed parameterized types à la "container of T." D's approach to templates is unleashing full-blown code generation, a symbolic approach to parameterization (code can be parameterized on any symbol, not only types), and thorough compile-time introspection. We will get into all the juicy details in good order in Chapter ??. For now, let's just take a quick look at some basic parameterized code. It's hard to make a good choice when it comes about such a comprehensive feature, so let's set out for no more and no less that Stepanov's three litmus tests.
Stepanov's Litmus Tests
In an interview , Alexander Stepanov, the creator of C++'s Standard Template Library (STL), mentions:
- These are my litmus tests: if a language allows me to implement max and swap and linear search generically—then it has some potential.
To clarify, generic implementation means that you implement the operation once for all types, and that the result is as good as a hand-written implementation tuned for each pertinent type in terms of safety, convenience, and last but not least, performance. Costly abstractions are a dime a dozen.
Stepanov makes the point that these three are very simple and fundamental algorithmic primitives, and that a language with a claim to fame should implement them with ease and panache. To further clarify the requirements, the charge is to implement the following three primitives:
- Write a generic function to compute the maximum of n ≥ 2 numbers. The function should apply to all ordered types.
- Write a generic function to swap two values efficiently (e.g. constant memory consumption).
- Write a generic function to linearly search for an item in any collection. The collection can be built-in or user-defined following whatever protocol the language prescribes for collections.
All implementations must be as efficient as their manually-written and inlined implementation. Let's set out to implementing the three functions in D.