函数程序设计

**函式語言程式設計**，或稱**函式程式設計**、**泛函編程**（英語：Functional programming），是一種程式設計範式，它將電腦運算視為函式運算，並且避免使用程式狀態以及可變物件。

## 簡介

在函式語言程式設計中，函式是頭等物件即頭等函式，這意味著一個函式，既可以作為其它函式的輸入參數值，也可以從函式中返回值，被修改或者被分配給一個變數。λ 演算是這種範式最重要的基礎，λ 演算的函式可以接受函式作為輸入參數和輸出返回值。

比起指令式編程，函數式編程更加強調程式執行的結果而非執行的過程，倡導利用若干簡單的執行單元讓計算結果不斷漸進，逐層推導複雜的運算，而不是設計一個複雜的執行過程。

## 歷史

阿隆佐・邱奇在 1930 年代開發的 λ 演算，是建造自函式應用的一種計算形式系統。在 1937 年，艾倫・圖靈證明了 λ 演算和圖靈機是等價的計算模型，展示了 λ 演算是圖靈完備性的。λ 演算形成了所有函式語言程式設計語言的基礎。另一種等價的理論公式化是組合子邏輯，它由 Moses Schönfinkel 和哈斯凱爾・柯里在 1920 年代和 1930 年代開發。

邱奇後來又開發了簡單類型 λ 演算，它通過向所有的項指定一個類型而擴充了 λ 演算。這個系統形成了靜態型別函式語言程式設計的基礎。

於 20 世紀 50 年代後期，John McCarthy 在麻省理工學院，開發了早期的函數式語言 LISP，執行在大型 IBM 主機（IBM700/7000 系列）上。LISP 的函式定義借鑑了邱奇的 λ 表示法，並擴充了標籤構造來允許遞迴函式。最開始的 LISP 是多範式語言，並且隨著新的範式的發展，越來越多的編程風格得到了支援。後來發展出來的方言比如 Scheme、Clojure，和分支語言比如 Dylan 等，試圖圍繞一個清晰的函數式核心，來得出簡化和理性化的 LISP，而 Common Lisp 旨在保留並更新它所替代的各種更早先 LISP 方言的那些範式特徵。

而於 1956 年發明的 IPL 語言，一般被認為是第一個基於電腦的函式語言程式設計語言。 它是一種用於操縱符號列表的組譯式語言。它有一個生成器的概念，相當於一個接受函式作為參數的函式，並且，由於它是組譯級語言，代碼可以是資料，因此 IPL 可以被視為具有高階函式。但是，它在很大程度上依賴於改變列表的結構和類似的指令式編程特徵。

在 1960 年代早期，Kenneth E. Iverson 開發了 APL 語言，在他 1962 年出版的《A Programming Language》一書中對其有所介紹。APL 對 John Backus 的 FP 語言施加了巨大的影響。在 20 世紀 90 年代早期，Iverson 和 Roger Hui 創造了 J 語言。在 20 世紀 90 年代中期，以前曾與 Iverson 合作過的 Arthur Whitney 建立了 K 語言，後者在金融行業中與其衍生出來的 Q 語言一起被商業化使用。

1977 年 John Backus 在他的圖靈獎頒獎演講《編程可以從馮・諾依曼式風格中解放出來嗎？一種函數式風格及其程式代數》中，展示了他提出的 FP。他將函式語言程式設計定義為通過「組合形式」以分層方式構建，允許「程式代數」; 在現代語言中，這意味著函數式程式應遵循複合性原理。Backus 的論文推廣了函式語言程式設計的研究，雖然它強調的是函式級編程而不是現在所說的 λ 演算風格。

1973 年愛丁堡大學的 Robin Milner 發明了 ML 語言，它的語法受到了 ISWIM 的啟發。同年，David Turner 在聖安德魯斯大學開發了 SASL 語言，它基於了 ISWIM 的應用式子集。在 1976 年，Turner 重新設計並重新實現它為惰性求值語言。在 20 世紀 70 年代的愛丁堡，Rod Burstall 和 John Darlington 開發了 NPL 語言。 NPL 基於 Kleene 的遞迴方程，並在他們的程式轉換工作中首次引入。 然後 Rod Burstall、David MacQueen 和 Don Sannella 結合了來自 ML 的多型型別檢查，從 NPL 衍生出了 Hope 語言。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 中得到了應用，雖然在重新賦值上的限制（所有值都被當作常數），導致了不熟悉函式語言程式設計的使用者混淆。

## 應用

### 工業

函式語言程式設計長期以來在學術界流行，但幾乎沒有工業應用。造成這種局面的主因是函數式編程常被認為嚴重耗費 CPU 和記憶體資源 ，這是由於在早期實現函數式程式語言時並沒有考慮過效率問題，而且面向函式語言程式設計特性，如保證參照透明性等，要求獨特的資料結構和演算法。

然而，最近幾種函式語言程式設計語言已經在商業或工業系統中使用，例如：

* Erlang，它由瑞典公司愛立信在 20 世紀 80 年代後期開發，最初用於實現容錯電信系統。此後，它已在 Nortel、Facebook、Électricité de France 和 WhatsApp 等公司作為流行語言建立一系列應用程式。
* Scheme，它被用作早期 Apple Macintosh 電腦上的幾個應用程式的基礎，並且最近已應用於諸如訓練類比軟體和望遠鏡控制等方向。
* OCaml，它於 20 世紀 90 年代中期推出，已經在金融分析，驅動程式驗證，工業機器人編程和嵌入式軟體靜態分析等領域得到了商業應用。
* Haskell，它雖然最初是作為一種研究語言，也已被一系列公司應用於航空航天系統，硬體設計和網路編程等領域。

其他在工業中使用的函式語言程式設計語言套件括多範式的 Scala、F#，還有 Wolfram 語言、Common Lisp、Standard ML 和 Clojure 等。

### 教育

教育方面，函式語言程式設計一直受到了很大的重視，很多學校使用函式語言程式設計來教授演算法和幾何的相關概念。

## 典型的函式語言程式設計語言

純函式語言程式設計語言通常不允許直接使用程式狀態以及可變物件，典型語言有：Miranda、Haskell 和 Idris 等。

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

* 靜態類型語言：ML 家族的 Standard ML、OCaml、F#，還有 Scala、Typed Racket 等。
* 動態類型語言：Lisp 家族的 Scheme、Common Lisp、Clojure、Racket，還有 LOGO、Erlang、Wolfram 語言和 R 等。

其他特殊風格的函式語言程式設計語言有：APL/J 和 jq 等。

## 參考文獻

## 外部連結

* Why Functional Programming Matters （頁面存檔備份，存於網際網路檔案館）