FP語言

FP（縮寫的 Functional Programming）， 是 John Backus 創立的支援函式級編程範式的程式語言。伊允准消去號名變數。

歷史

FP 語言是佇咧 Backus 的一九七七年圖靈獎獲獎演講論文《編程會當對馮諾依曼風格內底共解放出來？程式的函數式風格佮其代數》中提出的。這篇論文點著矣對函數式語言研究的興趣，終其尾致使現代函數式的語言，但是毋是 Backus 捌希望的函式級範式。

佇伊的這篇圖靈獎論文內底，Backus 咧講矣 FP 風格佮是無的 lambda 演算的語言有按怎無仝：

> FP 系統因為矣著叫做泛函形式（functional form）的一組固定的組合形式的利用。𪜶加上簡單的定義，就是對現存函式來建造新函式的唯一方式；𪜶無使用變數抑是代替（substitution）規則，並且𪜶成做程式相關的代數的運算操作（operation）。 FP 系統的所有函式攏是一種類型的：𪜶對映物件到物件以上總是接受一个單一實際參數（argument）。 > >

FP 家己佇學術界之外毋捌予大量使用。佇一九八Ｏ年代，Backus 建立了後繼續語言 FL，伊嘛保持為研究專案。

概述

FP 程式對映所來所至的值（value）構成自一个集合，伊佇咧序列成形（sequence formation）落去是合的：

` ` ` 若是x一 , . . . ,xn 是值，ua-sá-bih序列〈x一 , . . . ,xn〉嘛是啦值 ` ` `

遮的值得建造自任何的原子（atom）集合矣：布林值（boolean）、 整數（integer）、 實數（real）、 字元（character）等：

` ` ` boolean  : {T,F} integer  : { 零 , 一 , 二 , . . . , ∞ } character  : {'a','b','c', . . . } symbol  : {x,y, . . . } ` ` `

⊥是未定義（undefined）的值，抑是講叫做底（bottom）， 序列是「底保持」的（bottom-preserving）：

` ` ` 〈x一 , . . . ,⊥, . . . ,xn〉=⊥ ` ` `

FP 程式是函式f，𪜶逐个攏對映一个單一的值x到另外一个值：

` ` ` f:x表示否函熹 f扳用著值 x所得人抹的值 ` ` `

函式欲按怎是原始（primitive）的（就是說由 FP 環境所提供）， 抑若欲通過程式形成運算操作（program-forming operation）建造自原始函式，這款的運算操作嘛叫泛函（functional）。

原始函式的一个例是constant，伊將一个值x變換做一个常數值函式x̄。函式是嚴格的：

` ` ` f:⊥=⊥ ` ` `

原始函式的另外一个例是selector函式家族，指示為講一,二, . . . 遮的：

` ` ` _i_ :〈x一 , . . . ,xn〉=xi 若一 ≤ _i_ ≤ n =⊥ 其他情影落 ` ` `

泛函

佮原始函式相反，泛函（functional）算操作佇其他函式的頂懸。比如講，一寡函式有單位值，比如加法的零佮乘法的一。泛函unit，咧應用有這種值的函式 f的時陣，產生按呢的一个值：

` ` ` unit +=零 unit ×=一 unit foo=⊥ ` ` `

下跤是 FP 的核心泛函，複合（composition）、 構造（construction）、 條件（condition）、 應用佇所有（apply-to-all）， 正爿插入（insert-right）， 倒爿插入（insert-left）：

` ` ` composition'f∘gma里f∘g:x=f: ('g:x) ` ` `

` ` ` construction[f一 , . . . ,fn ] ma里 [f一 , . . . ,fn ] :x=〈f一 :x, . . . ,fn :x〉 ` ` `

` ` ` condition(h⇒f;g) ma里 (h⇒f;g) :x=f:x若是h:x=T =g:x若是h:x=F =⊥其他情批 ` ` `

` ` ` apply-to-all_ α _fma里 _ α _f:〈x一 , . . . ,xn〉=〈f:x一 , . . . ,f:xn〉 ` ` `

` ` ` insert-right/fma里 /f:〈x〉=x 影響而且 /f:〈x一 ,x二 , . . . ,xn〉=f:〈x一 , /f:〈x二 , . . . ,xn〉〉 影響而且 /f:〈〉=unit f ` ` `

` ` ` insert-left\fma里 \f:〈x〉=x 影響而且 \f:〈x一 ,x二 , . . . ,xn〉=f:〈\f:〈x一 , . . . ,xn 影一〉,xn〉 影響而且 \f:〈〉=unit f ` ` `

方程函式

除了通過函構造自原始函式，函式嘛是通過方程來遞迴的定義，上簡單的一類方式是：

` ` ` f≡ _ E _f ` ` `

遮的 _ E _f是用函對原始函式、其他定義的函式佮函式符號自身f起造的表達式。

FP 八十四

FP 八十四是擴充 FP 來包括無限列的，編程者定義的組合形式（類似 Backus 家己向 FP 的後繼者 FL 咧增加的彼款）， 佮慢性求值。無仝 Backus 家己的另外一个 FP 變體 FFP，FP 八十四佇物件佮函式之間做出明確區分：就是講後者無閣由前者的序列來表示。FP 八十四的擴充是通過徙掉 FP 對序列構造只會當應用非 ⊥ 物件的限制來完成的：佇咧 FP 八十四表達式（包括伊的意義做 ⊥）的規个攏集佇咧起鼓造下是合的。

FP 八十四的語意被具體這馬程式的底層代數中，一組函式級方程會當被用佇咧關於程式的操縱佮推理。

參見

• FL，Backus 的 FP 後繼者

參照

• _ 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 一千九百八十八 .

外部連結

FP 實現

• Interactive FP ( requires Java ) , Help page
• Furry Paws , FP compiler written in FP , Repo
• FP interpreter in Lisp
• FP trivia ( German )