头等函数

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

函數不是頭等公民的程序設計語言可以使用函數指針或 delegate，實現函數作為參數。C 語言例子:

### 匿名與嵌套函數

對於支持匿名函數的語言:

對於不支持匿名函數的語言，必須把函數綁定到一個名字上:

### 非局部變量與閉包

一旦有了匿名函數與嵌套函數，引用函數體之外的變量（非局部變量）就很自然了：

如果函數只能用函數指針表示，如何把函數體之外的值傳遞給函數就是個問題。可以手工建立一個閉包，但顯然這不能算作頭等函數：

注意這裡的 `map` 是特化為使用當前環境外的兩個 `int`。即使 `f` 是個嵌套函數，仍然要面對同樣問題，這也是 C 語言不支持嵌套函數的理由。

### 高階函數：返回函數作為結果

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

### 函數賦值給變量

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

### 函數的相等

判斷兩個函數是否相等，有不同的判據：

**外延相等**
: 兩個函數 _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 開始支持了匿名函數與閉包。

**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 操作

## 注釋

## 參考文獻

## 參閲

* Defunctionalization
* eval
* First-class message
* Kappa 演算 – 排除了頭等函數後的形式化
* 編譯器遞歸測試

## 外部連結

* First-class functions（頁面存檔備份，存於網際網路檔案館） on Rosetta Code.
* Higher order functions（頁面存檔備份，存於網際網路檔案館） at IBM developerWorks