FP語言

FP（縮寫的Functional Programming），是John Backus創立的支持函數級編程范型的程式語言。它允許消去命名變量。

## 歷史

FP語言是在Backus的1977年圖靈獎獲獎演講論文《編程可以從馮諾依曼風格中解放出來嗎？程序的函數式風格及其代數》中提出的。這篇論文點燃了對函數式語言研究的興趣，最終導致了現代函數式語言，但不是Backus曾希望的函數級范型。

在他的這篇圖靈獎論文中，Backus描述了FP風格與基於lambda演算的語言有著如何不同：

FP自身在學術界之外從未被大量使用。在1980年代，Backus建立了後繼語言FL，它也保持為研究項目。

## 概述

### 值

FP程序映射所來所至的值（value）構成自一個集合，它在序列成形（sequence formation）下是閉合的：

```
如果'''x'''<sub>1</sub>,...,'''x'''<sub>n</sub> 是'''值'''，则'''序列'''〈'''x'''<sub>1</sub>,...,'''x'''<sub>n</sub>〉也是'''值'''
```

這些值可以建造自任何原子（atom）集合：布爾值（boolean）、整數（integer）、實數（real）、字符（character）等：

```
'''boolean'''   : {'''T''', '''F'''}
'''integer'''   : {0,1,2,...,∞}
'''character''' : {'a','b','c',...}
'''symbol'''    : {'''x''','''y''',...}
```

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

```
〈'''x'''<sub>1</sub>,...,'''⊥''',...,'''x'''<sub>n</sub>〉  =  '''⊥'''
```

### 函數

FP程序是函數f，它們每個都映射一個單一的值x到另一個值：

```
'''f''':'''x'''  表示将'''函数f'''应用到'''值x'''所得结果的'''值''' 
```

函數要麼是原始（primitive）的（就是說由FP環境所提供），要麼是通過程序形成運算操作（program-forming operation）建造自原始函數，這種運算操作也叫泛函（functional）。

原始函數的一個例子是constant，它將一個值x變換成一個常量值函數x̄。函數是嚴格函數的：

```
'''f''':'''⊥''' = '''⊥'''
```

原始函數的另一個例子是selector函數家族，指示為1,2,... 這裡的：

```
'''''i''''':〈'''x'''<sub>1</sub>,...,'''x'''<sub>n</sub>〉  =  '''x'''<sub>i</sub>  如果 1 ≤ '''''i''''' ≤ n
                =  ⊥   其他情况下
```

## 泛函

與原始函數相反，泛函（functional）運算操作在其他函數之上。例如，一些函數有單位值，比如加法的0和乘法的1。泛函unit，在應用到有這種值的函數f的時候，產生這樣的一個值：

```
'''unit +'''   =  0
'''unit &times;'''   =  1
'''unit foo''' =  ⊥
```

下面是FP的核心泛函，複合（composition）、構造（construction）、條件（condition）、應用於所有（apply-to-all），右側插入（insert-right），左側插入（insert-left）：

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

'''construction''' ['''f'''<sub>1</sub>,...,'''f'''<sub>n</sub>] 这里   ['''f'''<sub>1</sub>,...,'''f'''<sub>n</sub>]:'''x''' =  〈'''f'''<sub>1</sub>:'''x''',...,'''f'''<sub>n</sub>:'''x'''〉

'''condition''' ('''h''' ⇒ '''f''';'''g''')    这里   ('''h''' ⇒ '''f''';'''g'''):'''x'''   =  '''f''':'''x'''   如果   '''h''':'''x'''  =  '''T'''
                                           =  '''g''':'''x'''   如果   '''h''':'''x'''  =  '''F'''
                                           =  '''⊥'''     其他情况

'''apply-to-all'''  ''α'''''f'''       这里   ''α'''''f''':〈'''x'''<sub>1</sub>,...,'''x'''<sub>n</sub>〉  = 〈'''f''':'''x'''<sub>1</sub>,...,'''f''':'''x'''<sub>n</sub>〉

'''insert-right'''  /'''f'''       这里   /'''f''':〈'''x'''〉             =  '''x'''
                       并且   /'''f''':〈'''x'''<sub>1</sub>,'''x'''<sub>2</sub>,...,'''x'''<sub>n</sub>〉  =  '''f''':〈'''x'''<sub>1</sub>,/'''f''':〈'''x'''<sub>2</sub>,...,'''x'''<sub>n</sub>〉〉
                       并且   /'''f''':〈 〉             =  '''unit f'''

'''insert-left'''  \'''f'''       这里   \'''f''':〈'''x'''〉             =  '''x'''
                      并且   \'''f''':〈'''x'''<sub>1</sub>,'''x'''<sub>2</sub>,...,'''x'''<sub>n</sub>〉  =  '''f''':〈\'''f''':〈'''x'''<sub>1</sub>,...,'''x'''<sub>n-1</sub>〉,'''x'''<sub>n</sub>〉
                      并且   \'''f''':〈 〉             =  '''unit f'''
```

## 方程函數

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

```
'''f''' ≡ ''E'''''f'''
```

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

## FP84

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

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

## 參見

- FL，Backus的FP後繼者

## 外部連結

FP實現

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

## 基本資料

- 日語原文：FP
- 編程范型：函數級
- 發行時間：1977年
- 設計者：John Backus
- dialects：FP84
- 受影響於：APL
- 施影響於：FL, Haskell