本页使用了标题或全文手工转换

函数式编程

维基百科,自由的百科全书
(重定向自函數程式語言
跳到导航 跳到搜索

函数式编程英语:functional programming)或称函数程序设计泛函编程,是一种编程范式,它将电脑运算视为函数运算,并且避免使用程式状态以及易变物件。其中,λ演算(lambda calculus)为该语言最重要的基础。而且,λ演算的函数可以接受函数当作输入(引数)和输出(传出值)。

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

典型的函数式编程语言[编辑]

純函数式编程语言[编辑]

非純函数式编程语言[编辑]

其他函数式编程语言[编辑]

工业使用[编辑]

函数式编程长期以来在学术界流行,但几乎没有工业应用。[1]:page 11然而,最近几种函数式编程语言已经在商业或工业系统中使用。[2]例如, Erlang编程语言由瑞典公司Ericsson在20世纪80年代后期开发,最初用于实现容错电信系统。此后,它已在Nortel,Facebook,ÉlectricitédeFrance和WhatsApp等公司作为建立一系列应用程序的语言。[3][4]Lisp的Scheme分支被用作早期Apple Macintosh计算机上的几个应用程序的基础,并且最近已应用于诸如训练模拟软件和望远镜控制等方向。OCaml于20世纪90年代中期推出,已经在金融分析,驱动程序验证,工业机器人编程和嵌入式软件静态分析等领域得到了商业应用。Haskell虽然最初是作为一种研究语言,也已被一系列公司应用于航空航天系统,硬件设计和网络编程等领域。

其他在工业中使用的函数式编程语言包括Scala[5] , F#,(两者都是功能性面对对象编程的混合,支持纯函数和命令式编程),Wolfram语言,Lisp,Standard ML和 Clojure。

教育[编辑]

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

歷史[编辑]

函数式编程的理论基础是Lambda演算,其本身是一种数学的抽象但不是编程语言。另一个组合逻辑是比它更加古老和基础的数学根基。两者都是为了更好的表达数学基础才被开发的。[7]

早期的函数式语言例如 Lisp,是由 John McCarthy在麻省理工学院,于20世纪50年代后期开发的,运行在大型IBM机(IBM 700/7000 series)上。[8]Lisp最早引入了函数式的很多特性,最开始的lisp是多范式语言,并且随着新的范式的发展,越来越多的编程风格得到了支持。后来分支出来的语言,例如Scheme,Clojure ,Dylan和Julia等分支,试图简化Lisp,使它围绕一个功能核心,而Common Lisp旨在保留lisp的原始范式特征。[9]

而发明与1956年的IPL语言,一般被认为是第一个基于计算机的函数式编程语言。[10] 它是一种用于操纵符号列表的汇编式语言。它有一个生成器的概念,相当于一个接受函数作为参数的函数,并且,由于它是汇编级语言,代码可以是数据,因此IPL可以被视为具有更高阶函数。但是,它在很大程度上依赖于改变列表的结构和类似的命令性编程的功能。也就是说,并不是完全的现在所谓的函数式编程。

Kenneth E. Iverson在20世纪60年代早期开发了APL ,在他1962年出版的“ A Programming Language ”(ISBN 9780471430148) 一书中有介绍。 APL给John Backus的FP提供了巨大的影响。 在20世纪90年代早期,Iverson和Roger Hui创造了J语言。 在20世纪90年代中期,以前曾与Iverson合作过的Arthur Whitney创建了K语言,后者在金融行业中与其衍生出来的Q语言一起被商业化使用。

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

1973年ML语言由爱丁堡大学的 Robin Milner发明。同年,David Turner在圣安德鲁斯大学开发SASL语言。在20世纪70年代的爱丁堡,Burstall和Darlington开发了NPL语言。[12] NPL基于Kleene递推方程 ,并在他们的程序转换工作中首次引入。[13] 然后Burstall,MacQueen和Sannella将ML的多态类型检查结合起来,产生了Hope语言。[14]ML最终发展成几种语言,其中最常见的是OCaml和Standard ML。 同时,如有影响力的Lambda paper和经典的1985年教科书“Structure and Interpretation of Computer Programs”中所描述的, Scheme的发展,Lisp的功能子集和不完全的函数式语言分支,将函数式编程的影响力提升到更广泛的范围,让更多的编程语言社区接触到它们。

在20世纪80年代, Per Martin-Löf开发了intuitionistic type theory(也称为constructive type theory),它将函数式编程与表现为类型依赖的数学证明联系起来。这导致了交互式定理证明(interactive theorem proving)的新方法的产生,并影响了后续的函数式编程语言的发展。 David Turner开发的惰性求值函数式语言Miranda最初出现在1985年,对后来的Haskell有很强的影响。 由于Miranda是非公开的语言,所以Haskell社区于1987年开始达成共识,以形成函数式编程研究的开放标准,对标准的实现自1990年以来一直在进行中。

最近,它在基于CSG几何框架构建的OpenSCAD语言的参数CAD中得到了应用,虽然它无法区分左值和右值,导致了不熟悉函数式编程的用户混淆。 [15]

函數式編程更加現代一些的例子包括CleanClojureErlangHaskellMirandaScheme等。

速度和空間上的顧慮[编辑]

函數式編程常被認為嚴重耗費CPU和記憶體資源[16] 。主因有二:

  • 在實現早期的函數式編程語言時並沒有考慮過效率問題。
  • 面向函数式编程特性(如保证函数参数不变性等)的独特数据结构和算法。

参考文献[编辑]

  1. ^ Odersky, Martin; Spoon, Lex; Venners, Bill. Programming in Scala: A Comprehensive Step-by-step Guide 2nd. Artima. December 13, 2010: 883/852. ISBN 978-0-9815316-4-9. 
  2. ^ 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 (英语). 
  3. ^ Piro, Christopher. Functional Programming at Facebook. CUFP 2009. 2009 [2009-08-29]. 
  4. ^ 1 million is so 2011 // WhatsApp blog, 2012-01-06: "the last important piece of our infrastracture is Erlang"
  5. ^ Momtahan, Lee. Scala at EDF Trading: Implementing a Domain-Specific Language for Derivative Pricing with Scala. CUFP 2009. 2009 [2009-08-29]. 
  6. ^ Emmanuel Schanzer of BootstrapTWiT.tv上的節目《Triangulation》的採訪(英文)
  7. ^ Haskell Brooks Curry; Robert Feys. Combinatory Logic. North-Holland Publishing Company. 1958 [10 February 2013]. 
  8. ^ McCarthy, John. History of Lisp. In ACM/SIGPLAN History of Programming Languages Conference. June 1978: 217–223. doi:10.1145/800025.808387. 
  9. ^ Guy L. Steele; Richard P. Gabriel. The Evolution of Lisp (PDF). In ACM/SIGPLAN Second History of Programming Languages. February 1996: 233–330. ISBN 978-0-201-89502-5. doi:10.1145/234286.1057818. 
  10. ^ 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.
  11. ^ Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs (PDF). 
  12. ^ 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)
  13. ^ R.M. Burstall and J. Darlington. A transformation system for developing recursive programs. Journal of the Association for Computing Machinery 24(1):44–67 (1977)
  14. ^ R.M. Burstall, D.B. MacQueen and D.T. Sannella. HOPE: an experimental applicative language. Proc. 1980 LISP Conference, Stanford, 136–143 (1980).
  15. ^ Make discovering assign() easier!. OpenSCAD. 
  16. ^ Larry C. Paulson. ML for the Working Programmer. Cambridge University Press. 28 June 1996 [10 February 2013]. ISBN 978-0-521-56543-1. 

外部連結[编辑]