Functional Programming与C++的模板元编程

feiyang10086

转：winter-cn
先来看一个例子:

1. #include <stdio.h>
   
2. template <int depth>
   
3. class Fibnacci
   
4. {
   
5. public:
   
6.     static const int value = Fibnacci<depth-1>::value + Fibnacci<depth-2>::value;
   
7. };
   
8. 
   
9. template <>
   
10. class Fibnacci<0>
    
11. {
    
12. public:
    
13.     static const int value = 0;
    
14. };
    
15. 
    
16. template <>
    
17. class Fibnacci<1>
    
18. {
    
19. public:
    
20.     static const int value = 1;
    
21. };
    
22. 
    
23. template <int depth>
    
24. void printFibnacci()
    
25. {
    
26.     printFibnacci<depth-1>();
    
27.     wprintf(L"%d\n", Fibnacci<depth>::value);
    
28. }
    
29. 
    
30. template <>
    
31. void printFibnacci<0>()
    
32. {
    
33.     wprintf(L"%d\n", Fibnacci<0>::value);
    
34. }
    
35. 
    
36. int main()
    
37. {
    
38.     printFibnacci<8>();
    
39.     return 0;
    
40. }

复制代码

Fibnacci数列，相信是个程序员都能写出来，重点是，这个Fibnacci数列的计算完全是在编译时完成！后面的print也是如此，当你把参数调得很大时，运行时间不会有任何改变，但是你会花费长时间在编译阶段。
如果你听说过一些模板元编程，你一定会知道"C++模板是图灵完备的"这个说法。模板元是如何图灵完备的？答案是，模板元跟Functional原理是一样的。
模板的本质是定义与替换，lambda函数的本质也是定义与替换，这里的替换实际上符合的是数学中的lambda演算理论：

Lambda演算
λ演算（lambda calculus）是一套用于研究函数定义、函数应用和递归的形式系统。它由丘奇（Alonzo Church）和他的學生克莱尼（Stephen Cole Kleene）在20世纪30年代引入。Church 运用λ演算在1936年给出判定性问题（Entscheidungsproblem）的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个 lambda 演算表达式是否等价的命题无法通过一个“通用的算法”来解决，这是不可判定性能够证明的头一个问题，甚至还在停机问题之先。Lambda 演算对函数式编程语言有巨大的影响，比如 Lisp 语言、ML 语言和 Haskell 语言。

Lambda 演算可以被称为最小的通用程序设计语言。它包括一条变换规则（变量替换）和一条函数定义方式，Lambda 演算之通用在于，任何一个可计算函数都能用这种形式来表达和求值。因而，它是等价于图灵机的。尽管如此，Lambda 演算强调的是变换规则的运用，而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。v
所以C++的模板元编程实际上属于函数式风格编程，这也是很多C++程序员觉得它不舒服的原因。

另外说一点，所谓图灵完备的语言，则必定可以用它来表达任何算法，那么我们现在使用的这个直接Fibnacci是一个非常低效的算法。
有一个常见的说法"Fibnacci的迭代算法比递归算法快"，这里我想强调，递归只是形式，与算法无关，下面奉上O(n)的Fibnacci算法（这回就不那么折磨编译器了）:

1. #include <stdio.h>
   
2. template <int depth>
   
3. class Fibnacci
   
4. {
   
5. public:
   
6.     static const int value = Fibnacci<depth-1>::value + Fibnacci<depth-1>::last;
   
7.     static const int last = Fibnacci<depth-1>::value ;
   
8. };
   
9. 
   
10. template <>
    
11. class Fibnacci<0>
    
12. {
    
13. public:
    
14.     static const int value = 0;
    
15. };
    
16. 
    
17. template <>
    
18. class Fibnacci<1>
    
19. {
    
20. public:
    
21.     static const int value = 1;
    
22.     static const int last = 0;
    
23. };
    
24. 
    
25. template <int depth>
    
26. void printFibnacci()
    
27. {
    
28.     printFibnacci<depth-1>();
    
29.     wprintf(L"%d\n", Fibnacci<depth>::value);
    
30. }
    
31. 
    
32. template <>
    
33. void printFibnacci<0>()
    
34. {
    
35.     wprintf(L"%d\n", Fibnacci<0>::value);
    
36. }
    
37. 
    
38. int main()
    
39. {
    
40.     printFibnacci<8>();
    
41.     return 0;
    
42. }

复制代码

最后留一道题目，各位看官如果有兴趣，可以做做，回复在下面或者留下链接均可，用C++模板或C#lambda函数都可以：
1994年的一次会议上，Erwin Unruh写了一个程序，在编译错误里面打印出一个素数序列。这个程序当时震惊了当时在场的包括C++之父Bjarne Stroustrup在内的几位大师，这个事情正标志了C++模板系统的图灵完备性被发现。那么，让我们也来向先辈致敬，来实现这个打印出一个素数序列的模板吧！