頭等函數

一級函式（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