8.1 函数式编程概述

函数式编程思想是一个非常古老的思想。我们简述如下：

• 我们就从1900 年 David Hilbert 的第 10 问题（能否通过有限步骤来判定不定方程是否存在有理整数解？） 开始说起吧。

• 1920，Schönfinkel，组合子逻辑(combinatory logic)。直到 Curry Haskell 1927 在普林斯顿大学当讲师时重新发现了 Moses Schönfinkel 关于组合子逻辑的成果。Moses Schönfinkel的成果预言了很多 Curry 在做的研究，于是他就跑去哥廷根大学与熟悉Moses Schönfinkel工作的Heinrich Behmann、Paul Bernays两人一起工作，并于 1930 年以一篇组合子逻辑的论文拿到了博士学位。Curry Brooks Haskell 整个职业生涯都在研究组合子，实际开创了这个研究领域，λ演算中用单参数函数来表示多个参数函数的方法被称为 Currying (柯里化)，虽然 Curry 同学多次指出这个其实是 Schönfinkel 已经搞出来的，不过其他人都是因为他用了才知道，所以这名字就这定下来了；并且有三门编程语言以他的名字命名，分别是：Curry, Brooks, Haskell。Curry 在 1928 开始开发类型系统，他搞的是基于组合子的 polymorphic，Church 则建立了基于函数的简单类型系统。

• 1929, 哥德尔(Kurt Gödel )完备性定理。Gödel 首先证明了一个形式系统中的所有公式都可以表示为自然数，并可以从一自然数反过来得出相应的公式。这对于今天的程序员都来说，数字编码、程序即数据计算机原理最核心、最基本的常识，在那个时代却脑洞大开的创见。

• 1933，λ 演算。 Church 在 1933 年搞出来一套以纯λ演算为基础的逻辑，以期对数学进行形式化描述。 λ 演算和递归函数理论就是函数式编程的基础。

• 1936，确定性问题（decision problem，德文 Entscheidungsproblem (发音 [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm]）。 Alan Turing 和 Alonzo Church，两人在同在1936年独立给出了否定答案。

1935-1936这个时间段上，我们有了三个有效计算模型：通用图灵机、通用递归函数、λ可定义。Rosser 1939 年正式确认这三个模型是等效的。

• 1953-1957，FORTRAN (FORmula TRANslating )，John Backus。1952 年 Halcombe Laning 提出了直接输入数学公式的设想，并制作了 GEORGE编译器演示该想法。受这个想法启发，1953 年 IBM 的 John Backus 团队给 IBM 704 主机研发数学公式翻译系统。第一个 FORTRAN (FORmula TRANslating 的缩写)编译器 1957.4 正式发行。FORTRAN 程序的代码行数比汇编少20倍。FORTRAN 的成功，让很多人认识到直接把代数公式输入进电脑是可行的，并开始渴望能用某种形式语言直接把自己的研究内容输入到电脑里进行运算。John Backus 在1970年代搞了 FP 语言，1977 年发表。虽然这门语言并不是最早的函数式编程语言，但他是 Functional Programming 这个词儿的创造者， 1977 年他的图灵奖演讲题为[“Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs”]

• 1956， LISP， John McCarthy。John McCarthy 1956年在 Dartmouth一台 IBM 704 上搞人工智能研究时，就想到要一个代数列表处理(algebraic list processing)语言。他的项目需要用某种形式语言来编写语句，以记录关于世界的信息，而他感觉列表结构这种形式挺合适，既方便编写，也方便推演。于是就创造了LISP。正因为是在 IBM 704 上开搞的，所以 LISP 的表处理函数才会有奇葩的名字： car/cdr 什么的。其实是取 IBM704 机器字的不同部分，c=content of，r=register number, a=address part, d=decrement part 。