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]