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