維基百科

函數式程式設計

編程範式

函數式程式設計，或稱函式程式設計、泛函編程（英語：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等。

非純函數式程式設計語言可按型別系統分為兩類：

其他特殊風格的函數式程式設計語言有：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. The Calculi of Lambda-Conversion. Annals of Mathematics studies, no. 6. Lithoprinted. Princeton University Press, Princeton. 1941 [2021-09-24]. （原始內容存檔於2022-05-19）. 
  2. ^ 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）. 
  3. ^ Haskell Brooks Curry; Robert Feys（英語：Robert Feys）. Combinatory Logic. North-Holland Publishing Company. 1958 [2022-12-19]. （原始內容存檔於2022-12-19）. 
  4. ^ 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）. 
  5. ^ 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（英語：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)）. 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.) 
  7. ^ 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 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. A Programming Language. 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. A New Implementation Technique for Applicative Languages (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. 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）. 
  16. ^ Rod Burstall（英語：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.
  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. Functional Programming at Facebook. 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. Scala at EDF Trading: Implementing a Domain-Specific Language for Derivative Pricing with Scala. CUFP 2009. 2009 [2009-08-29]. （原始內容存檔於2009-10-17）. 
  24. ^ Emmanuel Schanzer of Bootstrap在TWiT.tv上的節目《Triangulation》的採訪（英文）
  25. ^ Typed Racket （頁面存檔備份，存於網際網路檔案館）

外部連結

編輯
取自「https://zh.wikipedia.org/w/index.php?title=函数式编程&oldid=84213220」