头等函数

头等函数（first-class function；第一級函數）是指在程序设计语言中，函数被当作头等公民。这意味着，函数可以作为别的函数的参数、函数的返回值，赋值给变量或存储在数据结构中。 有人主张应包括支持匿名函数（函数字面量，function literals）。在这样的语言中，函数的名字没有特殊含义，它们被当作具有函数类型的普通的变量对待。1960年代中期，克里斯托弗·斯特雷奇在“functions as first-class citizens”中提出这一概念。

头等函数是函数式程序设计所必须的。通常要使用高阶函数。map函数就是一个高阶函数，其实参是一个函数及一个list，返回结果是把作为参数的函数作用于list的每个元素后的结果形成的list。

把函数作为函数参数与函数返回值会遇到特别的困难。特别是存在非局部变量与嵌套函数、匿名函数。历史上，这被称作函数参数问题。 早期的指令式编程语言，或者不支持函数作为结果类型（如ALGOL 60, Pascal），或者忽略嵌套函数与非局部变量（如C语言）。早期的函数式语言Lisp采取了动态作用域方法，把非局部变量绑定到函数执行点最近的变量定义。Scheme语言支持词法作用域的头等函数，把对函数的引用绑定到闭包（closure）而不是函数指针，这使得垃圾收集成为必须。

概念

在这一节，比较把函数视作头等公民的典型的函数式语言Haskell与把函数视作二等公民的指令式编程的C语言的有关概念。

高阶函数：函数作为实参传递

更多信息：高阶函数

具有函数参数的函数，称为高阶函数。函数式语言如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语言不支持嵌套函数的理由。

高阶函数：返回函数作为结果

返回结果为函数时，实际上返回的是该函数的闭包。对于C语言，函数退出时其局部变量也退出了各自的作用域，这使得构建闭包变得困难。这被称为向上的函数参数问题。

函数赋值给变量

把函数赋值给变量面临着把函数当作返回结果一样的困难：构建该函数的闭包：

f :: [[Integer] -> [Integer]]
f = let a = 3
        b = 1
     in [map (\x -> a * x + b), map (\x -> b * x + a)]

函数的相等

判断两个函数是否相等，有不同的判据：

外延相等

两个函数f与g如果是外延相等，当它们对同一输入有相等的输出。即(∀x. f(x) = g(x)). 决定外延相等通常是不可判定问题，甚至在函数的定义域是有限时也不可行。

以数学上的函数来举例：R→R的函数f(x)=√(x²)和g(x)=|x|是外延相等的。

内涵相等

判断两个函数f与g是否相等，可以比较二者编译后的结果。

例：上面的f(x)和g(x)不是内涵相等的，因为其定义式以及运算过程不同。

引用相等（Reference equality）

由于外延相等与内涵相等都不切实际，大多数语言支持用两个函数的引用是否同一来判断。函数或闭包绑定到独一的标识符（通常为其内存地址），根据其标识符确定相等。两个分开定义但具有同样内容的函数被判断为不等。

引用相等破坏了引用透明，因此纯函数式语言如Haskell不采用这个方法。而另一方面，非纯函数式的语言（如C++）也只能对函数/闭包对象与“空”判断是否相等、即对象是否有引用到某函数上，而不定义两个函数/闭包对象是否相等。

类型论

主条目：函数类型

对于类型论，函数类型接受值类型A并返回值类型B可写为A → B或B^A。根据柯里-霍华德对应，函数类型可对应于逻辑蕴涵，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	是	是	是	是	否	否
	Pascal	是	否	是	否	否	否
	Oberon	是	Non-nested only	是	否	否	否
	Delphi	是	是	是	2009	2009	否
C 家族	C	是	是	否	否	否	否	有函数指针
	C++	是	是	C++11 closures	C++11	C++11	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	2.0 + Blocks	否	有函数指针
	Java	部份	部份	否	Java 8	Java 8	否	有匿名内部类.
	Limbo	是	是	是	是	是	否
	Newsqueak	是	是	是	是	是	否
	Rust	是	是	是	是	是	否
函数式语言	Lisp	Syntax	Syntax	是	是	Common Lisp	否	(见下)
	Scheme	是	是	是	是	是	SRFI 26
	Clojure	是	是	是	是	是	是
	ML	是	是	是	是	是	是
	Haskell	是	是	是	是	是	是
	Scala	是	是	是	是	是	是
脚本语言	JavaScript	是	是	是	是	是	ECMAScript 5	用户代码在ES3上有部份应用
	PHP	是	是	5.3 closures	5.3 closures	5.3 closures	否	用户代码可有部份应用
	Perl	是	是	anonymous, 6	是	是	6	(见下)
	Python	是	是	是	部份	是	2.5	(见下)
	Ruby	Syntax	Syntax	Unscoped	是	是	1.9	(见下)
其他语言	Io	是	是	是	是	是	否
	Maple	是	是	是	是	是	否
	Mathematica	是	是	是	是	是	否
	MATLAB	是	是	是	是	是	是	新的函数可自动产生部份应用
	Smalltalk	是	是	是	是	是	部份	通过库可有部份应用
	Fortran	是	是	是	否	否	否
	Swift	是	是	是	是	是	是
	Ada	是	是	是	否	Downward Closure	否

C++

C++11闭包可捕获非局部变量通过传引用（不扩展非局部变量的生存期）或者传值的方式。

Java

Java 8闭包仅能捕获immutable ("effectively final")局部变量。Java没有函数类型。Java 8的匿名函数从上下文推导其类型，且必须是"functional interface" （只有一个方法的接口）。

Lisp

词法作用域Lisp的变种支持闭包。动态作用域的变种不支持闭包，需要特别构造闭包。

Common Lisp，函数名字空间的函数的标识符不能用于头等函数的值的引用。必须要特殊运算符function来获取函数的值，如：(function foo)得到一个函数对象。#'foo是一个快捷表示。若想应用这样的函数对象，必须用funcall 函数：(funcall #'foo bar baz).

Perl

Perl 5只允许匿名函数被嵌套。

Python

Python的匿名函数只允许表达式作为函数体。

从2.5版，使用functools.partial来显式部分应用，或从2.8版的operator.methodcaller

Ruby

普通函数的标识符不能用作值或传递。必须通过Method或Proc对象来获取头等数据。调用这种函数对象的语法不同于调用普通函数的语法。

嵌套方法定义并不实际嵌套作用域。

用curry显式currying操作

参考文献

• Leonidas Fegaras. "Functional Languages and Higher-Order Functions". CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.

参閲

• Defunctionalization
• eval
• First-class message
• Kappa演算 – 排除了头等函数后的形式化
• 编译器递归测试

外部链接

• First-class functions（页面存档备份，存于互联网档案馆） on Rosetta Code.
• Higher order functions（页面存档备份，存于互联网档案馆） at IBM developerWorks