Collect from 追梦人物的博客
Modified by ACool

C++模板元编程初探感想

前言

Boost 库里面大量的模板编程,看得有点复杂,我便研究了一天C++的模板元编程(Template metaprogramming,简称TMP),突然发现大脑CPU逻辑模块性能不够用了。趁着CPU没有降温,我记录一下自己的感想和总结的一些要点。

正文

​TMP可以说完全是另一种编程的思想——函数式编程。进一步来说,它是图灵完备的,完全可以当做另一种语言来使用。

​最为神奇的是,C++设计之初根本没有想到会出现这种操作,感觉更像是在调戏编译器,或者更为贴切地说,TMP是被“发现”的,而不是被创造的。第一个TMP程序是94年 Erwin Unruh 写的求素数的方法(见这个网页 http://www.erwin-unruh.de/primorig.html ),这种方法,直到现在仍然是一种“最骨灰级的玩法”(左耳朵耗子陈皓 原话 )。现在在 Erwin Unruh 的个人网站上面还可以看到他自己对当时“发现“ TMP 的场景描述(原文为德语):

Wir diskutierten über die Möglichkeiten, Template Argumente aus einem Template zu bestimmen. Dabei kam die Frage hoch, ob das Inverse einer Funktion bestimmt werden könnte. Ob also aus " I+1 == 5 " geschlossen werden könnte, daß " I == 4 " ist. Dies wurde verneint, aber die Frage inspirierte mich zu der Idee, während der Übersetzung Primzahlen zu berechnen. Die erste Version bastelte ich am Montag zusammen, aber sie war grundlegend falsch. Bjarne Stroustrup meinte, so etwas würde prinzipiell nicht funktionieren.

Dies stachelte meinen Eifer an, und so hatte ich Mittwoch nachmittag das Gerüst des Programmes fertig. Am Mittwoch abend war noch ein Arbeitstreffen angesagt, wo ich etwas Luft hatte. Dort traf ich Tom Pennello, und wir setzen uns zusammen. Er hatte seinen Notebook dabei und wir tippten mein Programm kurz ein. Nach einigen Basteleien lief das Programm. Wir machten einen Lauf und druckten Programm und Fehlermeldung aus. Anschliessend kam Tom auf die Idee, doch eine kompliziertere Funktion zu nehmen. Wir wählten die Ackermann Funktion. Nach wenigen Stunden lief auch dies und berechnete den Wert der Ackermann-Funktion während der Übersetzung. Am Donnerstag zeigte ich den Ausdruck Bjarne. Er war äußerst verblüfft. Ich fertigte dann Kopien für alle Teilnehmer an und ließ dieses kuriose Programm offiziell verteilen. Ich hielt das ganze für einen Scherz.Ein paar Wochen später entwickelte ich einen Beweis, daß der Template-Mechanismus Turing-vollständig ist. Da dieser Beweis jedoch recht trocken war, habe ich ihn einfach zu den Akten gelegt. Die Notizen habe ich immer noch. Bei Gelegenheit werde ich diese mal eintippen und hier zur Verfügung stellen."【我们讨论了从模板定义模板参数的可能性。提出的问题是,是否可以确定函数的逆。那么是否可以从“I + 1 == 5”得出“I == 4”的结论。这被否定了,但这个问题激发了我在翻译过程中计算素数的热情。我在星期一制作了第一个版本,但这根本就是错误的。 Bjarne Stroustrup说原则上不行,这再次激发了我的热情,所以我在周三下午完成了该计划的框架。星期三晚上还在宣布工作会议,我有一些空气(没学过德语,这里不知道什么意思)。在那里,我遇到了汤姆·佩内洛,我们坐在一起。他有笔记本,我们输入了我的程序。经过一些修改,程序运行了。我们制作了一个运行和打印的程序和错误消息。然后汤姆想出了一个更复杂的功能。我们选择了Ackermann功能。几个小时后,这也运行并计算了翻译期间Ackermann函数的值。星期四,我展示了Bjarne的表情。他惊呆了。然后,我为所有参与者制作了副本,并正式分发了这个奇怪的程序。我以为这是个玩笑。几周后,我开发了一个证明模板机制是图灵完备的证据。但是,由于这个证据非常干燥,我只是简单地说。我还有笔记。有时我会输入这些时间并在此处提供。(By Google Translate,更多内容请访问他的网站)】

​ TMP是编译期计算的,而C++主要是是运行期计算的(说主要是因为宏也是编译期计算),一种运行时计算的语言的语法可以构成另一门编译时计算的语言,真的很神奇(注意这是我第二次用这个词)。但是这种未定义的特性也导致了C++TMP 的一些缺陷:

  • 语法比较丑陋,阅读起来十分痛苦(看了一天的感想),Code Review TMP 感觉是高智商逻辑烧脑活动
  • 调试困难,编译的开销大
  • 具有函数式编程语言的通病,即循环便是用递归实现,太慢了(因为函数式编程本来最开始就是用来做数值计算的)

所以这也是为什么工业级代码里面TMP用得很少的原因(除了Boost这种基础库)。 总结完毕,最后放一段代码吧。

实例

/*****用模板实现的条件 if 和 while 语句及其运用*******/
/************C++ 98及其以上版本********************/
template<bool c, typename Then, typename Else> class IF_ { };
template<typename Then, typename Else>
class IF_<true, Then, Else> { public: typedef Then reType; };
template<typename Then, typename Else>
class IF_<false,Then, Else> { public: typedef Else reType; };

// 隐含要求: Condition 返回值 ret,Statement 有类型 Next
template<template<typename> class Condition, typename Statement>
class WHILE_ {
    class STOP { public: typedef Statement reType; };
public:
    typedef typename
        IF_<Condition<Statement>::ret,
        WHILE_<Condition, typename Statement::Next>,
        STOP>::reType::reType
    reType;
};
// 计算 1^e+2^e+...+n^e
template<int n, int e>
class sum_pow {
    template<int i, int E> class pow_e{ public: enum{ ret=i*pow_e<i,E-1>::ret }; };
    template<int i> class pow_e<i,0>{ public: enum{ ret=1 }; };
    // 计算 i^e,嵌套类使得能够定义嵌套模板元函数,private 访问控制隐藏实现细节
    template<int i> class pow{ public: enum{ ret=pow_e<i,e>::ret }; };
    template<typename stat>
    class cond { public: enum{ ret=(stat::ri<=n) }; };
    template<int i, int sum>
    class stat { public: typedef stat<i+1, sum+pow<i>::ret> Next;
                         enum{ ri=i, ret=sum }; };
public:
    typedef stat<1,0> STAT
    enum{ ret = WHILE_<cond, STAT>::reType::ret };
};

int main() {
    std::cout << sum_pow<10, 2>::ret << '\n';
    return 0;
}
385

大多数第一次见到这种写法的人都会冒出这样的感叹:C++还能这样写?

是的,当然可以。