本頁使用了標題或全文手工轉換

函式語言程式設計

維基百科,自由的百科全書
跳至導覽 跳至搜尋

函式語言程式設計(英語: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. 

外部連結[編輯]