template metaprogramming 9

原文：https://docs.google.com/Doc?docid=0AR8C1hO5R8S1ZGZiNHZoeGZfMmdiNzJwcGZi&hl=zh_CN&pli=1

作者：Bartosz
翻译：hurd


“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.
为什么感到好笑呢？因为元编程被普遍认为是非常有难度的。我是说，比古鲁级宗师还难。我有幸认识处于此水平的两个朋友: 写《Modern C++ Programming》的Andrei Alexandrescu, 实现Boost::Xpressive的Eric Niebler。所以我知道它是多么恐怖的事情。

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.
为什么元编程这么难呢？很大一个原因是：即使友善的说，C++模板也不完善。对参数化容器或泛形算法它是称职的，但是对类型或类型组操作它就不合适。更糟的是，C++没有反射，因此像探测指针这样的事情都变的非常棘手。就算C++0x提供一些改进，像parameter packs;但是古鲁级的信誉仍然是必要的。

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. 

所以, 我近来在用D做模板元编程。D语言没有前向兼容的包袱，所以可以使很多程序编写变的更容易。但在开始前，我想先说说泛式编程和函数式编程，给函数式编程一展身手；然后再来点C++和D模式匹配及类型列表的例子。

<h3>It's not your father's language</h3>
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.
理解元编程的关键是要意识到它是一种与你常用语言不同的语言。C++和D都为了这个目的而使用函数化的模板形式。首先：没有mutation! 假如你传一些类型给模板，就不能再追加其他类型了。它会用旧列表创建一个全新的类型列表作为原始材料。

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).

坦白说：我不理解为什么在编译时不允许mutation，(所有的模板计算在编译时)。事实上，在D里用混入来和模板一起工作，我更愿意使用包含mutation的D子集相比于创建一种新语言。这个新子集工作的非常好，它使混入更容易使用了。（参见我写的DrDobbs）

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.
一旦你不允许mutation，你差不多就粘在函数式范例上了。比如，你不能有loops, 因为mutable loop包含一些mutable状态。所以你只能用递归了。

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.
你可能会想函数式编程会非常配元编程；除了它跳过了可怕的c++模板语法。函数式编程的一个好处是你非常容易定义和实现，你可以用几个公式化的语义操作来描述无类型的lambda算法。


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.

一个重要的事情是：元语言不能是强类型的，因为一个强类型的语言需要其他语言来实现它的泛式算法，所以终止元-元语言的话就需要一个无类型（至少是动态类型）的顶级元语言。我怀疑 c++0x理念如此凄惨的失败是因为它试图把元语言导向强类型。钉在C++理念棺木上的钉子是concept maps，强类型语言的隐式转换问题也是一致命伤。


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:
模板还不算是完全的无类型，他们的区别在类型参数（在c++里被类型名或类引入）,模板模板参数，类型模板参数。这里是一个例子显示了这3种情况：
<code>template<class T, template F, int n></code>


<h3>Functional Programming in a Nutshell</h3>
“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.
"在函数上的函数操作" - 这是函数式编程的主旨。其他都是语法糖，其中一些是非常重要的。例如，你想要内建的整数和数据类型列表，还有模式匹配调度。

Here’s a very simple compile-time function in the C++ template language:
这是一个在C++模板语言里非常简单的编译时函数：
<code>
template<class T>
struct IsPtr {
    static const bool apply = false;
}
</code>
If it doesn’t look much like a function to you, here it is in more normal ad-hoc notation:
如果你觉得它不像一个函数，这是一个更通用的特别写法:
<code>
IsPtr(T) {
    return false;
}
</code>

You can “execute” or “call” this meta-function by instantiating the template IsPtr with a type argument and accessing its member apply:
你可以通过一个类型参数实例化IsPtr模板来“执行”或“调用”这个元函数或和连接它的成员apply:
<code>IsPtr<int>::apply;</code>

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.
关于成员“apply”没什么魔法，你可以调用任何成员("result" 或"value"或任何其他流行的标识符)。这个典型的元函数返回布尔值，但任何编译时常量都是可以返回的。更重要的是，任何类型和模板也可以返回。 But let’s not get ahead of ourselves（这句麻烦）.

<h3>-Pattern matching</h3>
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*:


你可能奇怪这样一个总是返回false的叫IsPtr的函数（我在后面去掉了“元”前坠）有什么用处。进入函数式编程兵器库的下一个武器是:模式匹配。我们需要的是依据函数参数类匹配和执行不同的程序代码。具个特别的例子，我们期望匹配到参数T*时返回一不同的值。在C++元语言里这是通过模板特化来完成的。定义一个同名的模板匹配特化参数T*就可以了。
<code>
template<class T>
struct IsPtr<T*> {
    static const bool apply = true;
}
</code>
When faced with the call,
当调用时，
<code>IsPtr<int*>::apply</code>

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。在我们的例子里，参数int*匹配T*，所以返回true的模板被实例化了。连接实例化模板的apply成员将返回true,这正是我们期待的。让我们用更清晰的语法来重写这个例子。

<code>
IsPtr(T*) {
    return true;
}
IsPtr(T) { // default case
    return false;
}
</code>

D template syntax is slightly less complex than that of C++. The above example will read:
D模板语法比C++更简单，先前的例子是这样的:
<code>
template IsPtr(T) {
    static if (is (T dummy: U*, U))
        enum IsPtr = true;
    else
        enum IsPtr = false;
}
// 编译时测试
static assert( IsPtr!(int*) );
static assert( !IsPtr!(int) );
</code>

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.
如你所见，D提供编译时if语句和更泛化的模式匹配。这里的模式匹配语法有点复杂，但是更灵活。编译时常量最终被声明成为了枚举。

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.

让“函数调用”语法更清晰还有点麻烦。假如在这个模板里面，你用定义“apply”的语法定义了一个和模板同名的模板成员（我叫它同名成员）。除了那个在参数列表前的叹号标记（a D tradeoff for not using angle brackets），这个“调用”看起来就更像个调用。稍后我们介绍在更复杂的情况下同名成员的麻烦。

<h3>-Lists</h3>
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:

函数式语言的基本数据结构是列表。列表在递归算法之上是非常容易操作的。as it turns out, they can be used to define arbitrarily complex data structures.不要奇怪C++0x被迫引入编译时类型列表作为原生类型。它被调用为模板参数包，新语法是：
<code>template<class... T>Foo</code>

You can instantiate such a template with zero arguments,
你可以无参数的实例化这样的模板,
<code>Foo<></code>
one argument,
或者传一个参数,
<code>Foo<int></code>

or more arguments,
或更多参数,

<code>Foo<int, char*, void*></code>

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:


让我证明一个来自Garry Powell的论文《Variadic Templates》的简单的例子。它通过递归计算包长度。首先，零长度列表的情况。
<code>
template<>
struct count <> {
    static const int value = 0;
}
</code>
That is the full specialization of a template, so it will be tried first. Here’s the general case:
这个是完全特化模板，所以它将被第一个尝试。这是更泛化的情况：
<code>
template<typename Head, typename... Tail>
struct count<Head, Tail...> {
    static const int value = 1 + count<Tail...>::value;
}
</code>

Let’s see what it would look like in “normal” notation:
我们再看看更普通的写法：
<code>
count() {
    return 0;
}
count(head, tail) {
    return 1 + count(tail);
}
</code>
And here’s the D version:
D版本:
<code>
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);
</code>


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.
T...表示一个元组, 它支持数组式操作。获得第一个列表成员D使用数组切片，T[1..$]表示这个数组除掉地一个的剩余部分。我会在将来的文章解释C++包和D元组的重要不同。

<h3>Conclusion</h3>

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.

我将在下一次连载里讨论模板元变成更多有趣的部分。特别地，我将展示一些高阶元函数像Filter or Not，还有一些类型列表小把戏。