FP(縮寫的Functional Programming)[2],是John Backus創立的支持函數級編程范型編程語言[2]。它允許消去命名變量

FP
編程範型函數級
設計者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自身在學術界之外從未被大量使用[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變換成一個常量值函數。函數是嚴格英語strict function的:

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  fg        这里    fg:x = f:(g:x)
construction [f1,...,fn] 这里   [f1,...,fn]:x =  〈f1:x,...,fn:x
condition (hf;g)    这里   (hf;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

方程函數

編輯

除了通過泛函構造自原始函數,函數也是通過方程來遞歸的定義,最簡單的一類方程是:

fEf

這裡的 Ef 是使用泛函從原始函數、其他定義的函數和函數符號自身f建造的表達式

FP84是擴展FP來包括無限序列,編程者定義的組合形式英語combining form(類似於Backus自己向FP的後繼者FL所增加的那樣),和惰性求值。不同於Backus自己的另一個FP變體FFP,FP84在對象和函數之間作出明確區分:就是說後者不再由前者的序列來表示。FP84的擴展是通過移除FP對序列構造只能應用於非⊥對象的限制來完成的:在FP84中表達式(包括其含義為⊥)的整個全集在序列構造下是閉合的。

FP84的語義被具體體現在程序的底層代數中,一組函數級方程可以被用於關於程序的操縱和推理。

參見

編輯
  • FL,Backus的FP後繼者

引用

編輯
  1. ^ The Conception, Evolution, and Application of Functional Programming Languages頁面存檔備份,存於網際網路檔案館) Paul Hudak, 1989
  2. ^ 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. 
  3. ^ Yang, Jean. Interview with Simon Peyton-Jones. People of Programming Languages. 2017 [2020-04-20]. (原始內容存檔於2020-02-18). 
  4. ^ 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實現