FP_(编程语言)

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

## 歷史

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

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

> FP 系統基於了對叫做泛函形式（functional form）的一組固定的組合形式的利用。它們加上簡單的定義，就是從現存函式建造新函式的唯一方式；它們不使用變數或替代（substitution）規則，並且它們成為程式相關的代數的運算操作（operation）。FP 系統的所有函式都是一種類型的：它們對映物件到物件之上並總是接受一個單一實際參數（argument）。
> 
> 

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

## 概述

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

```
如果**x**1,...,**x**n 是**值**，则**序列**〈**x**1,...,**x**n〉也是**值**
```

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

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

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

```
〈**x**1,...,**⊥**,...,**x**n〉  =  **⊥**
```

FP 程式是函式 **f**，它們每個都對映一個單一的值 **x** 到另一個值：

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

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

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

```
**f**:**⊥** = **⊥**
```

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

```
_**i**_:〈**x**1,...,**x**n〉  =  **x**i  如果 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** [**f**1,...,**f**n] 这里   [**f**1,...,**f**n]:**x** =  〈**f**1:**x**,...,**f**n:**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**1,...,**x**n〉  = 〈**f**:**x**1,...,**f**:**x**n〉
```

```
**insert-right**  /**f**       这里   /**f**:〈**x**〉             =  **x**
                       并且   /**f**:〈**x**1,**x**2,...,**x**n〉  =  **f**:〈**x**1,/**f**:〈**x**2,...,**x**n〉〉
                       并且   /**f**:〈 〉             =  **unit f**
```

```
**insert-left**  \**f**       这里   \**f**:〈**x**〉             =  **x**
                      并且   \**f**:〈**x**1,**x**2,...,**x**n〉  =  **f**:〈\**f**:〈**x**1,...,**x**n-1〉,**x**n〉
                      并且   \**f**:〈 〉             =  **unit f**
```

## 方程函式

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

```
**f** ≡ _E_**f**
```

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

## FP84

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

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

## 參見

* 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 1988.

## 外部連結

**FP 實現**

* Interactive FP（頁面存檔備份，存於網際網路檔案館） (requires Java), Help page（頁面存檔備份，存於網際網路檔案館）
* Furry Paws, FP compiler written in FP, Repo（頁面存檔備份，存於網際網路檔案館）
* FP interpreter in Lisp
* FP trivia（頁面存檔備份，存於網際網路檔案館） (German)