FP語言
![本頁使用了標題或全文手工轉換](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
編程範型 | 函式級 |
---|---|
設計者 | John Backus |
面市時間 | 1977年 |
衍生副語言 | |
FP84 | |
啟發語言 | |
APL[1] | |
影響語言 | |
FL, Haskell |
FP(縮寫的Functional Programming)[2],是John Backus創立的支援函式級編程範式的程式語言[2]。它允許消去命名變數。
歷史
[編輯]FP語言是在Backus的1977年圖靈獎獲獎演講論文《編程可以從馮諾伊曼風格中解放出來嗎?程式的函數式風格及其代數》中提出的。這篇論文點燃了對函數式語言研究的興趣[3],最終導致了現代函數式語言,但不是Backus曾希望的函式級範式。
在他的這篇圖靈獎論文中,Backus描述了FP風格與基於lambda演算的語言有著如何不同:
FP系統基於了對叫做泛函形式(functional form)的一組固定的組合形式的利用。它們加上簡單的定義,就是從現存函式建造新函式的唯一方式;它們不使用變數或替代(substitution)規則,並且它們成為程式相關的代數的運算操作(operation)。FP系統的所有函式都是一種類型的:它們對映對象到對象之上並總是接受一個單一實際參數(argument)。[2]
FP自身在學術界之外從未被大量使用[4]。在1980年代,Backus建立了後繼語言FL,它也保持為研究專案。
概述
[編輯]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實現