FP语言

FP（缩写的Functional Programming），是John Backus创立的支持函数级编程范型的编程语言。它允许消去命名变量。

历史
FP语言是在Backus的1977年图灵奖获奖演讲论文《编程可以从冯诺依曼风格中解放出来吗？程序的函数式风格及其代数》中提出的。这篇论文点燃了对函数式语言研究的兴趣，最终导致了现代函数式语言，但不是Backus曾希望的函数级范型。

在他的这篇图灵奖论文中，Backus描述了FP风格与基于lambda演算的语言有着如何不同：

FP自身在学术界之外从未被大量使用。在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̄。函数是的：
 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来包括无限序列，编程者定义的（类似于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)

Category:学术的编程语言
Category:函数式编程语言
Category:函数级语言
Category:1977年建立的程式語言