函数式编程的历史戏说

2019独角兽企业重金招聘Python工程师标准>>>

戏说，所以以下内容没有经过考究。

话说90多年前的一天，也就是1928年，希尔伯特这位数学家（在现代数学史上，此人名头甚大，想要了解的去看看现代数学史，以及著名的希尔伯特的23个问题）提出了一个数学问题，这个数学问题甚唯深奥，非我等可表述，简而言之，用我们能够理解的话说就是，使用逻辑的规则，是否存在一个算法，能对给定的一系列逻辑化的声明条件，给出证明结果。

1936年两位数学家各自独立发表了其证明，其中一个数学家叫做图灵，此人在现代计算机科学教学历史上，是传奇人物，为此他使用了图灵机的理论，这也是现代计算机建立的理论基础，另一位数学家Church在计算机科学教程上名不见经传，而这位科学家实际上发明了一个等价的计算模式，就是lambda calculus，这也是现代Functional programming语言实现的基础模型。

细节暂且不表，回到问题的本身上来，对于逻辑这种东西，实际上在5000年人类历史上使用了已经有几千年的历史了，所谓对对，错错，都是非正规的逻辑使用方法，这种逻辑公式化是在现代数学上建立起来的，是由哈密顿，以及布尔等人建立的，对于布尔这个人，我们也算是知道了，他们所建立起来的系统的一部分，也就是我们知道的布尔代数了，那么为什么要说他们呢，因为实际上我们现代的计算机，就是布尔代数机器，留心这里的数学联系，计算机虽然是个机器，其实质就是一个数学实现。

因为布尔代数的数值局限在真或者假以及其断言上，所以数学家扩展了布尔代数，使得它能够用于一般的数学证明，这个时候，就引入了非逻辑的数据，比如数字，集合，字符串等等，细节我等不知，结果是，在这样的演算过程中，参数的名字和数值是不改变的，而对于表达式而言并没有特定的顺序。

19世纪后期的时候，皮亚诺，此人号称是数学界里面的怪才，开发了一套数字理论，其宣称所有的数字都起源于0，而其证明的方法，就是函数的递归。

然后罗素这位西方数学界，思想界的重量级人物在羡慕皮亚诺的工作的同时，力图推演出一套逻辑系统来描述整个算术，这个梦想是很大的，想要创造一个理论来创造算数，比想要创造一个AI来制造AI还要狂妄，细想一下，如果算术真的可以真的被人创造的理论来创造，这就在否定“人不是万物的主宰”这样一个最基本的自然逻辑，结果当然是不可能的，因为算数并非是人造的东西，人只是在学习而已。

上面的这些理论和研究的结果都是在延续同一个问题，就是这样一个逻辑的机器，而这些理论最终的结果，就演化成了现代的广义冯诺伊曼机器，也就是数字计算机，而数字计算机的发明，直接的影响就是图灵机器理论，递归函数理论以及lambda计算理论，每一个都是通过定义一些原始的操作，和规则来完成计算，而最重要的是，每一个都是可证明的。

所有这些计算模型的结果，从某种角度讲，都是等价的，而且和泛式的冯诺伊曼机器，即数字计算机是等价的，这也隐含的说明了这样一个结果，就是任何一个系统的结果都可能等价于另一个系统的结果，而任何一个系统都可以用另一个系统来模拟，然后lambda的创始人，Church这位数学家从理论上推想，所有对于计算的描述都是等价的，但是无法被证明，虽然如此，我们看到lambda计算能够在数字计算机上实现的，这也许就是一个事实上的例子。

而今天，lambda计算和递归函数理论就是函数式编程的基础。

现代的编程语言是在50年代被介绍使用的，而关于以上的计算的理论直接的影响了编程语言的设计，所谓的函数，所谓的变量名，变量值，参数的顺序，都是从以上对于计算理论的数学研究直接演变过来的。例如Pascal这种语言，就有递归以及基于lambda的函数调用，使用名字来传递的机制。

60年代计算机在米国得到了广泛的使用，1963年，由于受lambda计算和递归函数理论的影响，出现了LISP这种语言，而到了后几年，几位计算机科学上的先锋人物都建议使用lambda计算来构建现代的编程语言，并为几中语言写了lambda的解释器，这几位先锋人物采用的方法各不相同，但是影响了一大批的编程语言。

而对于函数式语言开始感兴趣的真正开始，是1977年Backus写的一篇论文，他认为计算，被现代数字计算机的结构以及imperative的编程语言（也就是基于冯诺伊曼机器的编程方法，诸如汇编，C等等）所限制，并建议使用函数式编程来解决程序开发的问题。为什么如此，因为一大堆函数式编程的优点，这里就不说了。简单而言，现代计算机的结构和直接支持的计算模式就是冯诺伊曼的方法，或者是类似图灵机器的一个简化这样的方法，通过指令，存储，以及计算单元，结构控制以及流程控制来实现不断的演算，这种机器直接的影响了诸如机器指令集合，汇编语言，以至于C语言等的传统的语言的设计，因为直接的支持，所以这些语言相对而言是性能上最高效的语言，所以诸如系统程序都是用它们写的。

函数式语言给予的理论和计算模型不同与冯诺伊曼方法，但是如前所诉，计算模型可能是等价的，所以函数式语言的实现，实际上是在非函数式计算机器上的模拟，因为是等价的，所以结果都能够重现并保持一致。但是正如同Backus写的论文一样，图灵机器或者冯诺伊曼机器依赖的是一种机械原理，诸如操作等等，而并不直接反映数学计算的表达，而把一种数学计算，翻译成一种机械计算模型，然后再得到一个数学计算的结果，对于数学计算而言，显然是效率不高的，更不要说还有很多副作用。

而函数式语言是基于lambda计算的，诸如其中的lambda表达式（名，函数，或者是函数应用），都直接和数学计算对应，而当使用函数编程来应对数据的处理的时候，就有着比传统处理更优越的表达方式，参数就是数据的集合，数据的处理无非就是从一个集合把数据转变到另一个集合，这种映射在数学中有着丰富的表达，而其实现也得到现代计算机的支持。而函数式的计算，并不依赖于参数的顺序，也不改变参数的数值，以及名字，这也就隐含说明了函数计算是可以并行实现的，无疑成为现代大数据处理过程中的更好的工具。

本文参照：

维基百科英文版关于函数式编程的介绍

An introduction to Functional Programming through lambda Calculus，Michaelson (PDF版可以到你可以找到的地方下载）

题外话，写完这个之后，无非是想要理一下函数式语言存在的历史以及搞清楚其为什么存在等等的一些额外的疑惑，看过几遍之后，想到几个问题，为什么我们对于函数式语言感到陌生？回顾我们的计算机技术的学习或者是学校的教育，其实很多地方都极大的忽略了这段历史，也就是函数式语言的发展以及影响，而基本的教育局现在imperative programming paradigm上，虽然也看过几本英文书讲述，programming paradigm，这一点比较好，不过我经历的教育里面丝毫没有，但是也很少讲到其中lambda计算的影响。这可能也是在学习函数式语言上感到陌生困难的地方，相对这种语言，仅仅是一个用户，而不知道其具体的原理所在，不像imperative programming，因为长期的教育，所以多多少少知道一点其为什么。

这个现象不仅是个人学习发现，更有趣的是，到youtube上或者公开课上看那些教授讲解函数式编程，只是基于对于编程语言的角度去理解函数式语言，诸如，这样方式好用了，这样如何如何表达自然了，这样如何用了等等，很少人去提其中的数学影响，现在能看到的书，80年代，90年代的更讲解函数式编程的理论，看看历史觉得挺有意思，原来我们学的布尔代数的作用是那样的。

转载于:https://my.oschina/hellomaya/blog/609288