函數式編程
函數式編程，或稱函數程序設計、泛函編程（英語：Functional programming），是一種編程范型，它將電腦運算視為函數運算，並且避免使用程式狀態以及可變物件。
簡介
[編輯]在函數式編程中，函數是頭等對象即頭等函數，這意味着一個函數，既可以作為其它函數的輸入參數值，也可以從函數中返回值，被修改或者被分配給一個變量。λ演算是這種范型最重要的基礎，λ演算的函數可以接受函數作為輸入參數和輸出返回值。
比起指令式編程，函數式編程更加強調程序執行的結果而非執行的過程，倡導利用若干簡單的執行單元讓計算結果不斷漸進，逐層推導複雜的運算，而不是設計一個複雜的執行過程。
歷史
[編輯]阿隆佐·邱奇在1930年代開發的λ演算[1]，是建造自函數應用的一種計算形式系統。在1937年，艾倫·圖靈證明了λ演算和圖靈機是等價的計算模型[2]，展示了λ演算是圖靈完備性的。λ演算形成了所有函數式編程語言的基礎。另一種等價的理論公式化是組合子邏輯，它由Moses Schönfinkel和哈斯凱爾·柯里在1920年代和1930年代開發[3]。
邱奇後來又開發了簡單類型λ演算，它通過向所有的項指定一個類型而擴展了λ演算。[4]這個系統形成了靜態類型函數式編程的基礎。
於20世紀50年代後期，John McCarthy在麻省理工學院，開發了早期的函數式語言LISP，運行在大型IBM主機（IBM700/7000系列）上[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創造了J語言。在20世紀90年代中期，以前曾與Iverson合作過的Arthur Whitney創建了K語言，後者在金融行業中與其衍生出來的Q語言一起被商業化使用。
1977年John Backus在他的圖靈獎頒獎演講《編程可以從馮·諾依曼式風格中解放出來嗎？一種函數式風格及其程序代數》中，展示了他提出的FP[11]。他將函數式編程定義為通過「組合形式」以分層方式構建，允許「程序代數」; 在現代語言中，這意味着函數式程序應遵循複合性原理。Backus的論文推廣了函數式編程的研究，雖然它強調的是函數級編程而不是現在所說的λ演算風格。
1973年愛丁堡大學的Robin Milner發明了ML語言，它的語法受到了ISWIM的啟發。同年，David Turner在聖安德魯斯大學開發了SASL語言，它基於了ISWIM的應用式子集[12]。在1976年，Turner重新設計並重新實現它為惰性求值語言[13]。在20世紀70年代的愛丁堡，Rod Burstall和John Darlington開發了NPL語言。[14] NPL基於Kleene的遞歸方程，並在他們的程序轉換工作中首次引入。[15] 然後Rod Burstall、David MacQueen和Don Sannella結合了來自ML的多態類型檢查，從NPL派生出了Hope語言。[16]ML最終發展成幾種語言，其中最常見的是OCaml和Standard ML。
在1970年代，Guy L. Steele和Gerald Jay Sussman開發了Scheme，如有影響力的「λ論文集」和經典的1985年教科書《計算機程序的構造和解釋》中所描述的那樣。Scheme是使用詞法作用域和尾調用優化的第一個Lisp方言，將函數式編程的影響力提升到更廣泛的範圍，讓更多的編程語言社區接觸到它們。
在1980年代，佩爾·馬丁-洛夫開發了直覺類型論（也稱為構造類型論），它將函數式編程與表現為依賴類型的數學證明聯繫起來。這導致了交互式定理證明的新方法的產生，並影響了後續的函數式編程語言的發展。
在1985年David Turner開發的惰性求值函數式語言Miranda出現，它採用了來自ML與Hope語言的概念，作為他先前所設計的SASL和KRC語言的後繼者。Miranda對後來的Haskell有很強的影響，由於它當時是專有軟件，所以Haskell社區於1987年開始達成共識，以形成函數式編程研究的開放標準，對標準的實現自1990年以來一直在進行中。
最近，它在基於CSG幾何框架構建的OpenSCAD語言的參數CAD中得到了應用，雖然在重新賦值上的限制（所有值都被當作常量），導致了不熟悉函數式編程的用戶混淆。[17]
應用
[編輯]工業
[編輯]函數式編程長期以來在學術界流行，但幾乎沒有工業應用。造成這種局面的主因是函數式編程常被認為嚴重耗費CPU和記憶體資源[18] ，這是由於在早期實現函數式編程語言時並沒有考慮過效率問題，而且面向函數式編程特性，如保證參照透明性等，要求獨特的數據結構和算法。[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]。
典型的函數式編程語言
[編輯]純函數式編程語言通常不允許直接使用程式狀態以及可變對象，典型語言有：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等。
參考文獻
[編輯]- ^ 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. The Calculi of Lambda-Conversion. Annals of Mathematics studies, no. 6. Lithoprinted. Princeton University Press, Princeton. 1941 [2021-09-24]. （原始內容存檔於2022-05-19）. - ^ Turing, A. M. Computability and λ-definability (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）.
- ^ Haskell Brooks Curry; Robert Feys. Combinatory Logic. North-Holland Publishing Company. 1958 [2022-12-19]. （原始內容存檔於2022-12-19）.
- ^ Church, A. A Formulation of the Simple Theory of Types (PDF). Journal of Symbolic Logic. 1940, 5 (2): 56–68 [2021-09-24]. JSTOR 2266170. doi:10.2307/2266170. （原始內容 (PDF)存檔於2021-05-07）.
- ^
McCarthy, John. History of Lisp (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 (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 intended to resemble FORTRAN as much as possible. - ^ 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. Some History of Functional Programming Languages (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.)
- ^
John McCarthy. Recursive functions of symbolic expressions and their computation by machine, Part I. (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. LISP 1.5 Programmer's Manual (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 formLABEL, 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,LABELis 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 symbolEXPRfollowed by the function definition. The pseudo-functiondefineused at the beginning of this section accomplishes this. Whenapplyinterprets a function represented by an atomic symbol, it searches the p-list of the atomic symbol before searching the current a-list. Thus adefinewill override aLABEL. - ^ 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）.
- ^ 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.
- ^ Kenneth E. Iverson. A Programming Language. Wiley. 1962 [2021-09-24]. （原始內容存檔於2019-04-01）.
- ^ 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）.
- ^ Turner, D.A. An Implementation of SASL. University of St. Andrews, Department of Computer Science Technical Report.
- ^ D.A. Turner. A New Implementation Technique for Applicative Languages (PDF). [2021-09-24]. （原始內容 (PDF)存檔於2021-09-06）.
- ^ 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)
- ^ R.M. Burstall, J. Darlington. A transformation system for developing recursive programs. Journal of the Association for Computing Machinery: 24(1):44–67. 1977 [2021-09-24]. （原始內容存檔於2020-01-28）.
- ^ Rod Burstall, D.B. MacQueen, D.T. Sannella. Hope: An Experimental Applicative Language (PDF). 1980 [2021-09-24]. （原始內容 (PDF)存檔於2022-01-28）. Conference Record of the 1980 LISP Conference, Stanford University, pp. 136-143.
- ^ Make discovering assign() easier!. OpenSCAD. [2019-05-12]. （原始內容存檔於2020-09-28）.
- ^ 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）.
- ^ 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）.
- ^ 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 （英語）.
- ^ Piro, Christopher. Functional Programming at Facebook. CUFP 2009. 2009 [2009-08-29]. （原始內容存檔於2009-10-17）.
- ^ 1 million is so 2011 （頁面存檔備份，存於網際網路檔案館） // WhatsApp blog, 2012-01-06: "the last important piece of our infrastracture is Erlang"
- ^ Momtahan, Lee. Scala at EDF Trading: Implementing a Domain-Specific Language for Derivative Pricing with Scala. CUFP 2009. 2009 [2009-08-29]. （原始內容存檔於2009-10-17）.
- ^ Emmanuel Schanzer of Bootstrap在TWiT.tv上的節目《Triangulation》的採訪（英文）
- ^ Typed Racket （頁面存檔備份，存於網際網路檔案館）
