頭等函數

一級函式(first-class function;第一級函數)是指在程序設計語言中,函數被當作頭等公民。這意味著,函數可以作為別的函數的參數、函數的返回值,賦值給變量或存儲在資料結構中。 [1] 有人主張應包括支持匿名函數(函數字面量,function literals)。[2]在這樣的語言中,函數的名字沒有特殊含義,它們被當作具有函數類型的普通的變量對待。[3]1960年代中期,克里斯多福·斯特雷奇在「functions as first-class citizens」中提出這一概念。[4]

一級函式是函數式程序設計所必須的。通常要使用高階函數map函數就是一個高階函數,其實參是一個函數及一個list,返回結果是把作為參數的函數作用於list的每個元素後的結果形成的list。

把函數作為函數參數與函數返回值會遇到特別的困難。特別是存在非局部變量英語non-local variable嵌套函數英語nested function匿名函數。歷史上,這被稱作函數參數問題英語funarg problem[5] 早期的指令式編程語言,或者不支持函數作為結果類型(如ALGOL 60, Pascal),或者忽略嵌套函數與非局部變量(如C語言)。早期的函數式語言Lisp採取了動態作用域方法,把非局部變量綁定到函數執行點最近的變量定義。Scheme語言支持詞法作用域的一級函式,把對函數的引用綁定到閉包(closure)而不是函數指針[4]這使得垃圾收集成為必須。

概念

在這一節,比較把函數視作頭等公民的典型的函數式語言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語言不支持嵌套函數的理由。[6]

高階函數:返回函數作為結果

返回結果為函數時,實際上返回的是該函數的閉包。對於C語言,函數退出時其局部變量也退出了各自的作用域,這使得構建閉包變得困難。這被稱為向上的函數參數問題英語upwards funarg problem

函數賦值給變量

把函數賦值給變量面臨著把函數當作返回結果一樣的困難:構建該函數的閉包:

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

函數的相等

判斷兩個函數是否相等,有不同的判據:[7]

外延相等
兩個函數fg如果是外延相等,當它們對同一輸入有相等的輸出。即(∀x. f(x) = g(x)). 決定外延相等通常是不可判定問題,甚至在函數的定義域是有限時也不可行。
以數學上的函數來舉例:R→R的函數f(x)=√(x²)和g(x)=|x|是外延相等的。
內涵相等
判斷兩個函數fg是否相等,可以比較二者編譯後的結果。
例:上面的f(x)和g(x)不是內涵相等的,因為其定義式以及運算過程不同。
引用相等(Reference equality)
由於外延相等與內涵相等都不切實際,大多數語言支持用兩個函數的引用是否同一來判斷。函數或閉包綁定到獨一的標識符(通常為其內存地址),根據其標識符確定相等。兩個分開定義但具有同樣內容的函數被判斷為不等。
引用相等破壞了引用透明英語referential transparency (computer science),因此純函數式語言如Haskell不採用這個方法。而另一方面,非純函數式的語言(如C++)也只能對函數/閉包對象與「空」判斷是否相等、即對象是否有引用到某函數上,而不定義兩個函數/閉包對象是否相等。

類型論

對於類型論,函數類型接受值類型A並返回值類型B可寫為ABBA。根據柯里-霍華德對應函數類型可對應於邏輯蘊涵,lambda抽象對應於discharging hypothetical assumptions,函數調用對應於肯定前件推理規則。類型論還使用頭等函數建模關聯數組與類似的資料結構。

對於範疇論,頭等函數對應於closed category英語closed category設置。例如,簡單類型λ演算 對應於笛卡兒閉範疇(CCC)的內部語言。

語言支持

函數式程序設計語言,如SchemeMLHaskellF#Scala,都具有完整的頭等函數。Lisp作為最早的函數式語言在當初設計時對頭等函數各方面還沒有適當的理解,導致了採用動態作用域。後來的Common Lisp已經改為使用詞法作用域的頭等函數。

許多腳本語言,如PerlPythonPHPLuaTcl/Tk、JavaScriptIo,有頭等函數。

指令式程序設計語言,Algol及Pascal族系、C族系,與現代有垃圾收集的語言非常不同。Algol族系允許嵌套函數與高階函數作為參數,但不允許函數作為返回值(除了Algol 68)。因為當時還不清楚如何處理內嵌函數作為返回值時的非局部變量問題(Algol 68對此會產生運行期錯誤)。

C族系允許函數作為參數與函數作為返回值,但由於不支持嵌套函數而避開了相關問題。因為返回嵌套函數並捕獲所使用的非局部變量被認為才是真正有用,因此C族系不被認為有頭等函數。

現代指令式程式語言由於有垃圾收集功能而使得頭等函數成為可能。很多語言的後續版本開始支持頭等函數,如C# 2.0,Apple公司的C、C++與Objective-C的Block擴展。C++11開始支持了匿名函數與閉包。

語言 高階函數 非局部變量 部份應用英語Partial application 注釋
實參 返回結果 嵌套函數 匿名函數 閉包
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
C++
C++11閉包可捕獲非局部變量通過傳引用(不擴展非局部變量的生存期)或者傳值的方式。
Java
Java 8閉包僅能捕獲immutable ("effectively final")局部變量。Java沒有函數類型。Java 8的匿名函數從上下文推導其類型,且必須是"functional interface" (只有一個方法的接口)。
Lisp
詞法作用域Lisp的變種支持閉包。動態作用域的變種不支持閉包,需要特別構造閉包。[18]
Common Lisp,函數名字空間的函數的標識符不能用於頭等函數的值的引用。必須要特殊運算符function來獲取函數的值,如:(function foo)得到一個函數對象。#'foo是一個快捷表示。若想應用這樣的函數對象,必須用funcall 函數:(funcall #'foo bar baz).
Perl
Perl 5隻允許匿名函數被嵌套。
Python
Python的匿名函數隻允許表達式作為函數體。
從2.5版,使用functools.partial來顯式部分應用[19],或從2.8版的operator.methodcaller[20]
Ruby
普通函數的標識符不能用作值或傳遞。必須通過MethodProc對象來獲取頭等數據。調用這種函數對象的語法不同於調用普通函數的語法。
嵌套方法定義並不實際嵌套作用域。
curry顯式currying操作[21]

注釋

  1. ^ Abelson, Harold; Sussman, Gerald Jay. Structure and Interpretation of Computer Programs. MIT Press. 1984. Section 1.3 Formulating Abstractions with Higher-Order Procedures. ISBN 0-262-01077-1. 
  2. ^ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming".
  3. ^ Roberto Ierusalimschy; Luiz Henrique de Figueiredo; Waldemar Celes. The Implementation of Lua 5.0 (PDF). [2015-06-15]. (原始內容 (PDF)存檔於2017-06-23). 
  4. ^ 4.0 4.1 Burstall, Rod; Strachey, Christopher. Understanding Programming Languages (PDF). Higher-Order and Symbolic Computation. 2000, 13 (52): 11–49 [2015-06-15]. doi:10.1023/A:1010052305354. (原始內容 (PDF)存檔於2010-02-16).  (also on 2010-02-16
  5. ^ Joel Moses. "The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem"頁面存檔備份,存於網際網路檔案館). MIT AI Memo 199, 1970.
  6. ^ "If you try to call the nested function through its address after the containing function has exited, all hell will break loose." (GNU Compiler Collection: Nested Functions頁面存檔備份,存於網際網路檔案館))
  7. ^ Andrew W. Appel (1995). "Intensional Equality ;=) for Continuations"頁面存檔備份,存於網際網路檔案館).
  8. ^ Tanenbaum, A.S. A comparison of PASCAL and Algol 68 (PDF). The Computer Journal. 1977, 21 (4): 319. doi:10.1093/comjnl/21.4.316. 
  9. ^ Nested functions using lambdas/closures
  10. ^ 10.0 10.1 Doc No. 1968頁面存檔備份,存於網際網路檔案館): V Samko; J Willcock, J Järvi, D Gregor, A Lumsdaine (February 26, 2006) Lambda expressions and closures for C++
  11. ^ 存档副本. [2015-06-15]. (原始內容存檔於2010-08-21). 
  12. ^ 存档副本. [2015-06-15]. (原始內容存檔於2015-05-15). 
  13. ^ 存档副本. [2015-06-15]. (原始內容存檔於2015-05-21). 
  14. ^ 存档副本. [2015-06-15]. (原始內容存檔於2011-03-19). 
  15. ^ 存档副本. [2015-06-15]. (原始內容存檔於2012-10-22). 
  16. ^ 存档副本. [2015-06-15]. (原始內容存檔於2013-11-02). 
  17. ^ 存档副本. [2015-06-15]. (原始內容存檔於2015-05-13). 
  18. ^ Closures in ZetaLisp. [2015-06-15]. (原始內容存檔於2012-03-19). 
  19. ^ functools.partial. [2015-06-15]. (原始內容存檔於2012-10-18). 
  20. ^ operator.methodcaller. [2015-06-15]. (原始內容存檔於2012-10-26). 
  21. ^ 存档副本. [2015-06-15]. (原始內容存檔於2022-06-03). 

參考文獻

參閲

外部連結