FP语言

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变换成一个常量值函数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 f∘g 这里 f∘g:x = f:(g:x) 

construction [f1,...,fn] 这里 [f1,...,fn]:x = 〈f1:x,...,fn:x〉 

condition (h ⇒ f;g) 这里 (h ⇒ f;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 

方程函数

除了通过泛函构造自原始函数，函数也是通过方程来递归的定义，最简单的一类方程是：

f ≡ Ef 

这里的 Ef 是使用泛函从原始函数、其他定义的函数和函数符号自身f建造的表达式。

FP84

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. 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实现

• Interactive FP（页面存档备份，存于互联网档案馆） (requires Java), Help page（页面存档备份，存于互联网档案馆）
• , FP compiler written in FP, Repo（页面存档备份，存于互联网档案馆）
• FP interpreter in Lisp （页面存档备份，存于互联网档案馆）
• （页面存档备份，存于互联网档案馆） (German)