函数式编程

函数式编程，或称函数程序设计、泛函编程（英語：Functional programming），是一种编程范型，它将电脑运算视为函数运算，并且避免使用程式状态（英语：State (computer science)）以及可變物件。

简介

在函数式编程中，函数是头等对象即头等函数，这意味着一个函数，既可以作为其它函数的输入参数值，也可以从函数中返回值，被修改或者被分配给一个变量。λ演算是这种范型最重要的基础，λ演算的函数可以接受函数作为输入參數和输出返回值。

比起指令式編程，函數式編程更加強調程序执行的结果而非执行的过程，倡导利用若干简单的执行单元让计算结果不断渐进，逐层推导复杂的运算，而不是设计一个复杂的执行过程。

歷史

阿隆佐·邱奇在1930年代开发的λ演算^[1]，是建造自函数应用（英语：Function application）的一种计算形式系统。在1937年，艾伦·图灵证明了λ演算和图灵机是等价的计算模型^[2]，展示了λ演算是图灵完备性的。λ演算形成了所有函数式编程语言的基础。另一种等价的理论公式化是组合子逻辑，它由Moses Schönfinkel（英语：Moses Schönfinkel）和哈斯凯尔·柯里在1920年代和1930年代开发^[3]。

邱奇后来又开发了简单类型λ演算，它通过向所有的项指定一个类型而扩展了λ演算。^[4]这个系统形成了静态类型函数式编程的基础。

于20世纪50年代后期，John McCarthy在麻省理工学院，开发了早期的函数式语言LISP，运行在大型IBM主机（IBM700/7000系列（英语：IBM 700/7000 series））上^[5]。LISP的函数定义借鉴了邱奇的λ表示法^[6]，并扩展了标签构造来允许递归函数^[7]。最开始的LISP是多范型语言，并且随着新的范型的发展，越来越多的编程风格得到了支持。后来发展出来的方言比如Scheme、Clojure，和分支语言比如Dylan等，试图围绕一个清晰的函数式核心，来得出简化和理性化的LISP，而Common Lisp旨在保留并更新它所替代的各种更早先LISP方言的那些范型特征。^[8]

而于1956年发明的IPL语言，一般被认为是第一个基于计算机的函数式编程语言。^[9] 它是一种用于操纵符号列表的汇编式语言。它有一个生成器的概念，相当于一个接受函数作为参数的函数，并且，由于它是汇编级语言，代码可以是数据，因此IPL可以被视为具有高阶函数。但是，它在很大程度上依赖于改变列表的结构和类似的指令式编程特征。

在1960年代早期，Kenneth E. Iverson开发了APL语言，在他1962年出版的《A Programming Language》一书中对其有所介绍。^[10]APL对John Backus的FP语言施加了巨大的影响。在20世纪90年代早期，Iverson和Roger Hui（英语：Roger Hui）创造了J语言。在20世纪90年代中期，以前曾与Iverson合作过的Arthur Whitney（英语：Arthur Whitney (computer scientist)）创建了K语言，后者在金融行业中与其衍生出来的Q（英语：Q (programming language from Kx Systems)）语言一起被商业化使用。

1977年John Backus在他的图灵奖颁奖演讲《编程可以从冯·诺依曼式风格中解放出来吗？一种函数式风格及其程序代数》中，展示了他提出的FP^[11]。他将函数式编程定义为通过“组合形式”以分层方式构建，允许“程序代数”; 在现代语言中，这意味着函数式程序应遵循复合性原理。Backus的论文推广了函数式编程的研究，虽然它强调的是函数级编程而不是现在所说的λ演算风格。

1973年爱丁堡大学的Robin Milner发明了ML语言，它的语法受到了ISWIM的启发。同年，David Turner（英语：David Turner (computer scientist)）在圣安德鲁斯大学开发了SASL语言，它基于了ISWIM的应用式子集^[12]。在1976年，Turner重新设计并重新实现它为惰性求值语言^[13]。在20世纪70年代的爱丁堡，Rod Burstall（英语：Rod Burstall）和John Darlington开发了NPL语言。^[14] NPL基于Kleene的递归方程，并在他们的程序转换工作中首次引入。^[15] 然后Rod Burstall、David MacQueen和Don Sannella（英语：Don Sannella）结合了来自ML的多态类型检查，从NPL派生出了Hope语言。^[16]ML最终发展成几种语言，其中最常见的是OCaml和Standard ML。

在1970年代，Guy L. Steele和Gerald Jay Sussman开发了Scheme，如有影响力的“λ论文集”和经典的1985年教科书《计算机程序的构造和解释》中所描述的那样。Scheme是使用词法作用域和尾调用优化的第一个Lisp方言，将函数式编程的影响力提升到更广泛的范围，让更多的编程语言社区接触到它们。

在1980年代，佩尔·马丁-洛夫开发了直觉类型论（也称为构造类型论），它将函数式编程与表现为依赖类型的数学证明联系起来。这导致了交互式定理证明（英语：Proof assistant）的新方法的产生，并影响了后续的函数式编程语言的发展。

在1985年David Turner（英语：David Turner (computer scientist)）开发的惰性求值函数式语言Miranda出现，它採用了來自ML與Hope语言的概念，作為他先前所設計的SASL和KRC语言的後繼者。Miranda对后来的Haskell有很强的影响，由于它当时是专有软件，所以Haskell社区于1987年开始达成共识，以形成函数式编程研究的开放标准，对标准的实现自1990年以来一直在进行中。

最近，它在基于CSG几何框架构建的OpenSCAD语言的参数CAD中得到了应用，虽然在重新赋值上的限制（所有值都被当作常量），导致了不熟悉函数式编程的用户混淆。^[17]

应用

工业

函数式编程长期以来在学术界流行，但几乎没有工业应用。造成这种局面的主因是函數式編程常被認為嚴重耗費CPU和記憶體資源^[18] ，这是由于在早期實現函數式編程語言時並沒有考慮過效率問題，而且面向函数式编程特性，如保证参照透明性（英语：Referential transparency）等，要求独特的数据结构和算法。^[19]

然而，最近几种函数式编程语言已经在商业或工业系统中使用^[20]，例如：

• Erlang，它由瑞典公司爱立信在20世纪80年代后期开发，最初用于实现容错电信系统。此后，它已在Nortel、Facebook、Électricité de France和WhatsApp等公司作为流行语言建立一系列应用程序。^[21][22]
• Scheme，它被用作早期Apple Macintosh计算机上的几个应用程序的基础，并且最近已应用于诸如训练模拟软件和望远镜控制等方向。
• OCaml，它于20世纪90年代中期推出，已经在金融分析，驱动程序验证，工业机器人编程和嵌入式软件静态分析等领域得到了商业应用。
• Haskell，它虽然最初是作为一种研究语言，也已被一系列公司应用于航空航天系统，硬件设计和网络编程等领域。

其他在工业中使用的函数式编程语言包括多范型的Scala^[23]、F#，还有Wolfram语言、Common Lisp、Standard ML和Clojure等。

教育

教育方面，函数式编程一直受到了很大的重视，很多学校使用函数式编程来教授算法和几何的相关概念^[24]。

典型的函数式编程语言

純函数式编程语言通常不允许直接使用程式状态（英语：State (computer science)）以及可变对象，典型语言有：Miranda、Haskell和Idris等。

非純函数式编程语言可按类型系统分为两类：

• 靜態類型语言：ML家族的Standard ML、OCaml、F#，还有Scala、Typed Racket^[25]等。
• 動態類型语言：Lisp家族的Scheme、Common Lisp、Clojure、Racket，还有LOGO、Erlang、Wolfram语言和R等。

其他特殊风格的函数式编程语言有：APL/J和jq（英语：jq (programming language)）等。

参考文献

1. Alonzo Church. A set of postulates for the foundation of logic (PDF). Annals of Mathematics. Series 2. 1932, 33 (2): 346–366 [2022-12-19]. JSTOR 1968337. doi:10.2307/1968337. （原始内容 (PDF)于2022-12-19）. 
   Alonzo Church. . Annals of Mathematics studies, no. 6. Lithoprinted. Princeton University Press, Princeton. 1941 [2021-09-24]. （原始内容存档于2022-05-19）. 
2. Turing, A. M. (PDF). The Journal of Symbolic Logic (Cambridge University Press). 1937, 2 (4): 153–163 [2021-09-24]. JSTOR 2268280. doi:10.2307/2268280. （原始内容 (PDF)存档于2021-09-24）. 
3. Haskell Brooks Curry; Robert Feys（英语：Robert Feys）. Combinatory Logic. North-Holland Publishing Company. 1958 [2022-12-19]. （原始内容于2022-12-19）. 
4. Church, A. (PDF). Journal of Symbolic Logic. 1940, 5 (2): 56–68 [2021-09-24]. JSTOR 2266170. doi:10.2307/2266170. （原始内容 (PDF)存档于2021-05-07）. 
5. McCarthy, John. (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-09-23]. （原始内容 (PDF)存档于2020-11-07）. There were two motivations for developing a language for the IBM 704. First, IBM was generously establishing a New England Computation Center at M.I.T. …… Second, IBM was undertaking to develop a program for proving theorems in plane geometry (based on an idea of Marvin Minsky’s), ……. ……
   In connection with IBM’s plane geometry project, Nathaniel Rochester and Herbert Gelernter（英语：Herbert Gelernter） (on the advice of McCarthy) decided to implement a list processing language within FORTRAN, ……. This work was undertaken by Herbert Gelernter and Carl Gerberich at IBM and led to FLPL, standing for FORTRAN List Processing Language. ……
   I spent the summer of 1958 at the IBM Information Research Department at the invitation of Nathaniel Rochester and chose differentiating algebraic expressions as a sample problem. It led to the following innovations beyond FLPL:
   a. Writing recursive function definitions using conditional expressions. …… b. The maplist function that forms a list of applications of a functional argument to the elements of a list. …… c. To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers. d. The recursive definition of differentiation made no provision for erasure of abandoned list structure. ……
   The implementation of LISP began in Fall 1958. …… The programs to be hand-compiled were written in an informal notation called M-expressions（英语：M-expression） intended to resemble FORTRAN as much as possible. 
6. John McCarthy. History of Lisp (PDF). Artificial Intelligence Laboratory, Stanford University. 12 February 1979 [2021-09-23]. （原始内容 (PDF)于2020-11-07）. To use functions as arguments, one needs a notation for functions, and it seemed natural to use the λ-notation of Church (1941). I didn’t understand the rest of his book, so I wasn’t tempted to try to implement his more general mechanism for defining functions. Church used higher order functionals instead of using conditional expressions. Conditional expressions are much more readily implemented on computers. 
   David Turner（英语：David Turner (computer scientist)）. (PDF). [2021-10-25]. （原始内容 (PDF)存档于2020-04-15）. LISP was not based on the lambda calculus, despite using the word “LAMBDA” to denote functions. At the time he invented LISP, McCarthy was aware of (Church 1941) but had not studied it. The theoretical model behind LISP was Kleene’s theory of first order recursive functions. (McCarthy made these statements, or very similar ones, in a contribution from the floor at the 1982 ACM symposium on LISP and functional programming in Pittsburgh. No written version of this exists, as far as know.) 
7. John McCarthy. (PDF). Communications of the ACM (ACM New York, NY, USA). 1960, 3 (4): 184–195 [2021-02-24]. doi:10.1145/367177.367199. （原始内容 (PDF)存档于2021-02-19）. 
   John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart, Michael I. Levin. (PDF) 2nd. MIT Press. 1985 [1962] [2021-09-23]. ISBN 0-262-13011-4. （原始内容 (PDF)存档于2021-03-02）. A function can be simply a name. In this case its meaning must be previously understood. A function may be defined by using the lambda notation and establishing a correspondence between the arguments and the variables used in a form. If the function is recursive, it must be given a name by using a label. ……
   When a symbol stands for a function, the situation is similar to that in which a symbol stands for an argument. When a function is recursive, it must be given a name. This is done by means of the form LABEL, which pairs the name with the function definition on the a-list. The name is then bound to the function definition, just as a variable is bound to its value.
   In actual practice, LABEL is seldom used. It is usually more convenient to attach the name to the definition in a uniform manner. This is done by putting on the property list of the name, the symbol EXPR followed by the function definition. The pseudo-function define used at the beginning of this section accomplishes this. When apply interprets a function represented by an atomic symbol, it searches the p-list of the atomic symbol before searching the current a-list. Thus a define will override a LABEL. 
8. Guy L. Steele; Richard P. Gabriel. The Evolution of Lisp (PDF). In ACM/SIGPLAN Second History of Programming Languages. February 1996: 233–330 [2019-05-12]. ISBN 978-0-201-89502-5. doi:10.1145/234286.1057818. （原始内容 (PDF)于2020-11-12）. 
9. The memoir of Herbert A. Simon (1991), Models of My Life pp.189-190 ISBN 0-465-04640-1 claims that he, Al Newell, and Cliff Shaw are "...commonly adjudged to be the parents of [the] artificial intelligence [field]," for writing Logic Theorist, a program that proved theorems from Principia Mathematica automatically. To accomplish this, they had to invent a language and a paradigm that, viewed retrospectively, embeds functional programming.
10. Kenneth E. Iverson. . Wiley. 1962 [2021-09-24]. （原始内容存档于2019-04-01）. 
11. Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs (PDF). [2019-05-12]. （原始内容 (PDF)于2020-11-08）. 
12. Turner, D.A. An Implementation of SASL. University of St. Andrews, Department of Computer Science Technical Report. 
13. D.A. Turner. (PDF). [2021-09-24]. （原始内容 (PDF)存档于2021-09-06）. 
14. R.M. Burstall. Design considerations for a functional programming language. Invited paper, Proc. Infotech State of the Art Conf. "The Software Revolution", Copenhagen, 45–57 (1977)
15. R.M. Burstall, J. Darlington. . Journal of the Association for Computing Machinery: 24(1):44–67. 1977 [2021-09-24]. （原始内容存档于2020-01-28）. 
16. Rod Burstall（英语：Rod Burstall）, D.B. MacQueen, D.T. Sannella. (PDF). 1980 [2021-09-24]. （原始内容 (PDF)存档于2022-01-28）.  Conference Record of the 1980 LISP Conference, Stanford University, pp. 136-143.
17. Make discovering assign() easier!. OpenSCAD. [2019-05-12]. （原始内容于2020-09-28）. 
18. Larry C. Paulson. ML for the Working Programmer. Cambridge University Press. 28 June 1996 [10 February 2013]. ISBN 978-0-521-56543-1. （原始内容于2020-04-09）. 
19. Odersky, Martin; Spoon, Lex; Venners, Bill. Programming in Scala: A Comprehensive Step-by-step Guide 2nd. Artima. December 13, 2010: 883/852 [2019-05-12]. ISBN 978-0-9815316-4-9. （原始内容于2016-04-30）. 
20. Ray, Baishakhi; Posnett, Daryl; Devanbu, Premkumar; Filkov, Vladimir. A large-scale study of programming languages and code quality in GitHub. Communications of the ACM. 2017-09-25, 60 (10): 92. doi:10.1145/3126905 （英语）. 
21. Piro, Christopher. . CUFP 2009. 2009 [2009-08-29]. （原始内容存档于2009-10-17）. 
22. 1 million is so 2011 （页面存档备份，存于互联网档案馆） // WhatsApp blog, 2012-01-06: "the last important piece of our infrastracture is Erlang"
23. Momtahan, Lee. . CUFP 2009. 2009 [2009-08-29]. （原始内容存档于2009-10-17）. 
24. Emmanuel Schanzer of Bootstrap在TWiT.tv上的節目《Triangulation》的採訪（英文）
25. Typed Racket （页面存档备份，存于互联网档案馆）

外部連結

• Why Functional Programming Matters （页面存档备份，存于互联网档案馆）