Loading AI tools
来自维基百科,自由的百科全书
头等函数(first-class function;第一级函数)是指在程序设计语言中,函数被当作头等公民。这意味着,函数可以作为别的函数的参数、函数的返回值,赋值给变量或存储在数据结构中。 [1] 有人主张应包括支持匿名函数(函数字面量,function literals)。[2]在这样的语言中,函数的名字没有特殊含义,它们被当作具有函数类型的普通的变量对待。[3]1960年代中期,克里斯托弗·斯特雷奇在“functions as first-class citizens”中提出这一概念。[4]
头等函数是函数式程序设计所必须的。通常要使用高阶函数。map函数就是一个高阶函数,其实参是一个函数及一个list,返回结果是把作为参数的函数作用于list的每个元素后的结果形成的list。
把函数作为函数参数与函数返回值会遇到特别的困难。特别是存在非局部变量与嵌套函数、匿名函数。历史上,这被称作函数参数问题。[5] 早期的指令式编程语言,或者不支持函数作为结果类型(如ALGOL 60, Pascal),或者忽略嵌套函数与非局部变量(如C语言)。早期的函数式语言Lisp采取了动态作用域方法,把非局部变量绑定到函数执行点最近的变量定义。Scheme语言支持词法作用域的头等函数,把对函数的引用绑定到闭包(closure)而不是函数指针,[4]这使得垃圾收集成为必须。
具有函数参数的函数,称为高阶函数。函数式语言如Haskell:
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs
函数不是头等公民的程序设计语言可以使用函数指针或delegate,实现函数作为参数。C语言例子:
void map(int (*f)(int), int x[], size_t n) {
for (int i = 0; i < n; i++)
x[i] = f(x[i]);
}
对于支持匿名函数的语言:
main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]
对于不支持匿名函数的语言,必须把函数绑定到一个名字上:
int f(int x) {
return 3 * x + 1;
}
int main() {
int list[] = {1, 2, 3, 4, 5};
map(f, list, 5);
}
一旦有了匿名函数与嵌套函数,引用函数体之外的变量(非局部变量)就很自然了:
main = let a = 3
b = 1
in map (\x -> a * x + b) [1, 2, 3, 4, 5]
如果函数只能用函数指针表示,如何把函数体之外的值传递给函数就是个问题。可以手工建立一个闭包,但显然这不能算作头等函数:
typedef struct {
int (*f)(int, int, int);
int *a;
int *b;
} closure_t;
void map(closure_t *closure, int x[], size_t n) {
for (int i = 0; i < n; ++i)
x[i] = (*closure->f)(*closure->a, *closure->b, x[i]);
}
int f(int a, int b, int x) {
return a * x + b;
}
void main() {
int l[] = {1, 2, 3, 4, 5};
int a = 3;
int b = 1;
closure_t closure = {f, &a, &b};
map(&closure, l, 5);
}
注意这里的map
是特化为使用当前环境外的两个int
。即使f
是个嵌套函数,仍然要面对同样问题,这也是C语言不支持嵌套函数的理由。[6]
返回结果为函数时,实际上返回的是该函数的闭包。对于C语言,函数退出时其局部变量也退出了各自的作用域,这使得构建闭包变得困难。这被称为向上的函数参数问题。
把函数赋值给变量面临着把函数当作返回结果一样的困难:构建该函数的闭包:
f :: [[Integer] -> [Integer]]
f = let a = 3
b = 1
in [map (\x -> a * x + b), map (\x -> b * x + a)]
判断两个函数是否相等,有不同的判据:[7]
对于类型论,函数类型接受值类型A并返回值类型B可写为A → B或BA。根据柯里-霍华德对应,函数类型可对应于逻辑蕴涵,lambda抽象对应于discharging hypothetical assumptions,函数调用对应于肯定前件推理规则。类型论还使用头等函数建模关联数组与类似的数据结构。
对于范畴论,头等函数对应于closed category设置。例如,简单类型λ演算 对应于笛卡儿闭范畴(CCC)的内部语言。
函数式程序设计语言,如Scheme、ML、Haskell、F#、Scala,都具有完整的头等函数。Lisp作为最早的函数式语言在当初设计时对头等函数各方面还没有适当的理解,导致了采用动态作用域。后来的Common Lisp已经改为使用词法作用域的头等函数。
许多脚本语言,如Perl、Python、PHP、Lua、Tcl/Tk、JavaScript、Io,有头等函数。
指令式程序设计语言,Algol及Pascal族系、C族系,与现代有垃圾收集的语言非常不同。Algol族系允许嵌套函数与高阶函数作为参数,但不允许函数作为返回值(除了Algol 68)。因为当时还不清楚如何处理内嵌函数作为返回值时的非局部变量问题(Algol 68对此会产生运行期错误)。
C族系允许函数作为参数与函数作为返回值,但由于不支持嵌套函数而避开了相关问题。因为返回嵌套函数并捕获所使用的非局部变量被认为才是真正有用,因此C族系不被认为有头等函数。
现代指令式编程语言由于有垃圾收集功能而使得头等函数成为可能。很多语言的后续版本开始支持头等函数,如C# 2.0,Apple公司的C、C++与Objective-C的Block扩展。C++11开始支持了匿名函数与闭包。
语言 | 高阶函数 | 非局部变量 | 部分应用 | 注释 | ||||
---|---|---|---|---|---|---|---|---|
实参 | 返回结果 | 嵌套函数 | 匿名函数 | 闭包 | ||||
Algol 家族 | ALGOL 60 | 是 | 否 | 是 | 否 | 否 | 否 | 有函数类型 |
ALGOL 68 | 是 | 是[8] | 是 | 是 | 否 | 否 | ||
Pascal | 是 | 否 | 是 | 否 | 否 | 否 | ||
Oberon | 是 | Non-nested only | 是 | 否 | 否 | 否 | ||
Delphi | 是 | 是 | 是 | 2009 | 2009 | 否 | ||
C 家族 | C | 是 | 是 | 否 | 否 | 否 | 否 | 有函数指针 |
C++ | 是 | 是 | C++11 closures[9] | C++11[10] | C++11[10] | C++11 | 有函数指针、函数对象。使用std::bind 可显式部分应用。
| |
C# | 是 | 是 | 7 | 2.0 / 3.0 | 2.0 | 3.0 | 有delegate(2.0)及lambda表达式(3.0) | |
Go | 是 | 是 | 是 | 是 | 是 | 否 | ||
Objective-C | 是 | 是 | 否 | 2.0 + Blocks[11] | 2.0 + Blocks | 否 | 有函数指针 | |
Java | 部分 | 部分 | 否 | Java 8 | Java 8 | 否 | 有匿名内部类. | |
Limbo | 是 | 是 | 是 | 是 | 是 | 否 | ||
Newsqueak | 是 | 是 | 是 | 是 | 是 | 否 | ||
Rust | 是 | 是 | 是 | 是 | 是 | 否 | ||
函数式语言 | Lisp | Syntax | Syntax | 是 | 是 | Common Lisp | 否 | (见下) |
Scheme | 是 | 是 | 是 | 是 | 是 | SRFI 26[12] | ||
Clojure | 是 | 是 | 是 | 是 | 是 | 是 | ||
ML | 是 | 是 | 是 | 是 | 是 | 是 | ||
Haskell | 是 | 是 | 是 | 是 | 是 | 是 | ||
Scala | 是 | 是 | 是 | 是 | 是 | 是 | ||
脚本语言 | JavaScript | 是 | 是 | 是 | 是 | 是 | ECMAScript 5 | 用户代码在ES3上有部分应用 [13] |
PHP | 是 | 是 | 5.3 closures | 5.3 closures | 5.3 closures | 否 | 用户代码可有部分应用 | |
Perl | 是 | 是 | anonymous, 6 | 是 | 是 | 6[14] | (见下) | |
Python | 是 | 是 | 是 | 部分 | 是 | 2.5[15] | (见下) | |
Ruby | Syntax | Syntax | Unscoped | 是 | 是 | 1.9 | (见下) | |
其他语言 | Io | 是 | 是 | 是 | 是 | 是 | 否 | |
Maple | 是 | 是 | 是 | 是 | 是 | 否 | ||
Mathematica | 是 | 是 | 是 | 是 | 是 | 否 | ||
MATLAB | 是 | 是 | 是 | 是[16] | 是 | 是 | 新的函数可自动产生部分应用[17] | |
Smalltalk | 是 | 是 | 是 | 是 | 是 | 部分 | 通过库可有部分应用 | |
Fortran | 是 | 是 | 是 | 否 | 否 | 否 | ||
Swift | 是 | 是 | 是 | 是 | 是 | 是 | ||
Ada | 是 | 是 | 是 | 否 | Downward Closure | 否 |
function
来获取函数的值,如:(function foo)
得到一个函数对象。#'foo
是一个快捷表示。若想应用这样的函数对象,必须用funcall
函数:(funcall #'foo bar baz)
.functools.partial
来显式部分应用[19],或从2.8版的operator.methodcaller
[20]Method
或Proc
对象来获取头等数据。调用这种函数对象的语法不同于调用普通函数的语法。curry
显式currying操作[21]