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

副标题#e#

先来看一个例子:

#include　<stdio.h>
template　<int　depth>
class　Fibnacci
{
public:
　　　　static　const　int　value　=　Fibnacci<depth-1>::value　+　Fibnacci<depth-2>::value;
};

template　<>
class　Fibnacci<0>
{
public:
　　　　static　const　int　value　=　0;
};

template　<>
class　Fibnacci<1>
{
public:
　　　　static　const　int　value　=　1;
};

template　<int　depth>
void　printFibnacci()
{
　　　　printFibnacci<depth-1>();
　　　　wprintf(L"%d\n",　Fibnacci<depth>::value);
}

template　<>
void　printFibnacci<0>()
{
　　　　wprintf(L"%d\n",　Fibnacci<0>::value);
}

int　main()
{
　　　　printFibnacci<8>();
　　　　return　0;
}

Fibnacci数列，相信是个措施员都能写出来，重点是，这个Fibnacci数列的计较完全是在编译时完成！后头的print也是如此，当你把参数调得很大时，运行时间不会有任何改变，可是你会耗费长时间在编译阶段。

假如你传闻过一些模板元编程，你必然会知道"C++模板是图灵完备的"这个说法。模板元是如何图灵完备的？谜底是，模板元跟Functional道理是一样的。

模板的本质是界说与替换，lambda函数的本质也是界说与替换，这里的替换实际上切合的是数学中的lambda演算理论：

#p#副标题#e#

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算法（这回就不那么熬煎编译器了）:

#include　<stdio.h>
template　<int　depth>
class　Fibnacci
{
public:
　　　　static　const　int　value　=　Fibnacci<depth-1>::value　+　Fibnacci<depth-1>::last;
　　　　static　const　int　last　=　Fibnacci<depth-1>::value　;
};

template　<>
class　Fibnacci<0>
{
public:
　　　　static　const　int　value　=　0;
};

template　<>
class　Fibnacci<1>
{
public:
　　　　static　const　int　value　=　1;
　　　　static　const　int　last　=　0;
};

template　<int　depth>
void　printFibnacci()
{
　　　　printFibnacci<depth-1>();
　　　　wprintf(L"%d\n",　Fibnacci<depth>::value);
}

template　<>
void　printFibnacci<0>()
{
　　　　wprintf(L"%d\n",　Fibnacci<0>::value);
}

int　main()
{
　　　　printFibnacci<8>();
　　　　return　0;
}

最后留一道题目，列位看官假如有乐趣，可以做做，回覆在下面可能留下链接均可，用C++模板或C#lambda函数都可以：

1994年的一次集会会议上，Erwin Unruh写了一个措施，在编译错误内里打印出一个素数序列。这个措施其时震惊了其时在场的包罗C++之父Bjarne Stroustrup在内的几位大家，这个工作正符号了C++模板系统的图灵完备性被发明。那么，让我们也来向先辈致敬，来实现这个打印出一个素数序列的模板吧！