函數式編程，或稱函數程序設計、泛函編程（英語：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等。
非純函數式編程語言可按類型系統分為兩類：
參考文獻
外部連結
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
