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变换成一个常量值函数。函数是严格英语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  fg        这里    fg:x = f:(g:x)
construction [f1,...,fn] 这里   [f1,...,fn]:x =  〈f1:x,...,fn:x
condition (hf;g)    这里   (hf;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

方程函数

编辑

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

fEf

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

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. ^ 2.0 2.1 2.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实现