茶年 · 中文维基百科

头等函数

Wikipedia · 2026-06-08 维基百科 👁 2 阅读

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

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

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

高阶函数：返回函数作为结果
返回结果为函数时，实际上返回的是该函数的闭包。对于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或BA。根据柯里-霍华德对应，函数类型可对应于逻辑蕴涵，lambda抽象对应于discharging hypothetical assumptions，函数调用对应于肯定前件推理规则。类型论还使用头等函数建模关联数组与类似的数据结构。

对于范畴论，头等函数对应于设置。例如，简单类型λ演算 对应于笛卡儿闭范畴(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开始支持了匿名函数与闭包。

; C++: C++11闭包可捕获非局部变量通过传引用（不扩展非局部变量的生存期）或者传值的方式。
; Java: Java 8闭包仅能捕获不可变（“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操作

注释
参考文献

参閲
*

  • eval

*

  • – 排除了头等函数后的形式化
  • 编译器递归测试

外部链接

#数据类型 #子程序 #函數式編程 #程序设计语言理论

评论 (0)

  • 还没有评论，来抢沙发吧。