FP語言
FP（縮寫的Functional Programming）[2]，是John Backus創立的支援函數級編程範式的程式語言[2]。它允許消去命名變數。
| 編程範型 | 函數級 |
|---|---|
| 設計者 | John Backus |
| 釋出時間 | 1977年 |
| 衍生副語言 | |
| FP84 | |
| 啟發語言 | |
| APL[1] | |
| 影響語言 | |
| FL, Haskell | |
歷史
FP語言是在Backus的1977年圖靈獎獲獎演講論文《編程可以從馮紐曼風格中解放出來嗎？程式的函數式風格及其代數》中提出的。這篇論文點燃了對函數式語言研究的興趣[3]，最終導致了現代函數式語言，但不是Backus曾希望的函數級範式。
在他的這篇圖靈獎論文中，Backus描述了FP風格與基於lambda演算的語言有着如何不同：
FP系統基於了對叫做泛函形式（functional form）的一組固定的組合形式的利用。它們加上簡單的定義，就是從現存函數建造新函數的唯一方式；它們不使用變數或替代（substitution）規則，並且它們成為程式相關的代數的運算操作（operation）。FP系統的所有函數都是一種類型的：它們對映對象到對象之上並總是接受一個單一實際參數（argument）。[2]
概述
FP程式對映所來所至的值（value）構成自一個集合，它在序列成形（sequence formation）下是閉合的：
如果x1,...,xn 是值，则序列〈x1,...,xn〉也是值
這些值可以建造自任何原子（atom）集合：布林值（boolean）、整數（integer）、實數（real）、字元（character）等：
boolean : {T, F}
integer : {0,1,2,...,∞}
character : {'a','b','c',...}
symbol : {x,y,...}
⊥是未定義（undefined）的值，或者叫底（bottom），序列是「底保持」的（bottom-preserving）：
〈x1,...,⊥,...,xn〉 = ⊥
FP程式是函數f，它們每個都對映一個單一的值x到另一個值：
f:x 表示将函数f应用到值x所得结果的值
函數要麼是原始（primitive）的（就是說由FP環境所提供），要麼是通過程式形成運算操作（program-forming operation）建造自原始函數，這種運算操作也叫泛函（functional）。
原始函數的一個例子是constant，它將一個值x變換成一個常數值函數x̄。函數是嚴格的：
f:⊥ = ⊥
原始函數的另一個例子是selector函數家族，指示為1,2,... 這裏的：
i:〈x1,...,xn〉 = xi 如果 1 ≤ i ≤ n
= ⊥ 其他情况下
泛函
與原始函數相反，泛函（functional）運算操作在其他函數之上。例如，一些函數有單位值，比如加法的0和乘法的1。泛函unit，在應用到有這種值的函數f的時候，產生這樣的一個值：
unit + = 0 unit × = 1 unit foo = ⊥
下面是FP的核心泛函，複合（composition）、構造（construction）、條件（condition）、應用於所有（apply-to-all），右側插入（insert-right），左側插入（insert-left）：
composition f∘g 这里 f∘g:x = f:(g:x)
construction [f1,...,fn] 这里 [f1,...,fn]:x = 〈f1:x,...,fn:x〉
condition (h ⇒ f;g) 这里 (h ⇒ f;g):x = f:x 如果 h:x = T
= g:x 如果 h:x = F
= ⊥ 其他情况
apply-to-all αf 这里 αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn〉
insert-right /f 这里 /f:〈x〉 = x
并且 /f:〈x1,x2,...,xn〉 = f:〈x1,/f:〈x2,...,xn〉〉
并且 /f:〈 〉 = unit f
insert-left \f 这里 \f:〈x〉 = x
并且 \f:〈x1,x2,...,xn〉 = f:〈\f:〈x1,...,xn-1〉,xn〉
并且 \f:〈 〉 = unit f
方程函數
除了通過泛函構造自原始函數，函數也是通過方程來遞歸的定義，最簡單的一類方程是：
f ≡ Ef
這裏的 Ef 是使用泛函從原始函數、其他定義的函數和函數符號自身f建造的表達式。
FP84
FP84是擴充FP來包括無限序列，編程者定義的組合形式（類似於Backus自己向FP的後繼者FL所增加的那樣），和惰性求值。不同於Backus自己的另一個FP變體FFP，FP84在對象和函數之間作出明確區分：就是說後者不再由前者的序列來表示。FP84的擴充是通過移除FP對序列構造只能應用於非⊥對象的限制來完成的：在FP84中表達式（包括其含義為⊥）的整個全集在序列構造下是閉合的。
FP84的語意被具體體現在程式的底層代數中，一組函數級方程可以被用於關於程式的操縱和推理。
參見
- FL，Backus的FP後繼者
參照
- ^ The Conception, Evolution, and Application of Functional Programming Languages （頁面存檔備份，存於互聯網檔案館） Paul Hudak, 1989
- ^ 2.0 2.1 2.2 Backus, J. Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs. Communications of the ACM. 1978, 21 (8): 613. doi:10.1145/359576.359579.
- ^ Yang, Jean. Interview with Simon Peyton-Jones. People of Programming Languages. 2017 [2020-04-20]. （原始內容存檔於2020-02-18）.
- ^ Hague, James. Functional Programming Archaeology. Programming in the Twenty-First Century. December 28, 2007 [2020-04-20]. （原始內容存檔於2018-05-20）.
- Sacrificing simplicity for convenience: Where do you draw the line?, John H. Williams and Edward L. Wimmers, IBM Almaden Research Center, Proceedings of the FIfteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, San Diego, CA, January 1988.
外部連結
- FP實現