跳至內容

閉包 (計算機科學)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

計算機科學中,閉包(英語:Closure),又稱詞法閉包Lexical Closure)或函數閉包function closures),是在支持頭等函數的編程語言中實現詞法綁定的一種技術。閉包在實現上是一個結構體,它存儲了一個函數(通常是其入口地址)和一個關聯的環境(相當於一個符號查找表)。環境裡是若干對符號和值的對應關係,它既要包括約束變量(該函數內部綁定的符號),也要包括自由變量(在函數外部定義但在函數內被引用),有些函數也可能沒有自由變量。閉包跟函數最大的不同在於,當捕捉閉包的時候,它的自由變量會在捕捉時被確定,這樣即便脫離了捕捉時的上下文,它也能照常運行。捕捉時對於值的處理可以是值拷貝,也可以是名稱引用,這通常由語言設計者決定,也可能由用戶自行指定(如C++)。

概述

[編輯]

閉包的概念出現於60年代,最早實現閉包的程序語言是Scheme。之後,閉包被廣泛使用於函數式編程語言如ML語言LISP。很多命令式程序語言也開始支持閉包。

在支持頭等函數的語言中,如果函數f內定義了函數g,那麼如果g存在自由變量,且這些自由變量沒有在編譯過程中被優化掉,那麼將產生閉包。

閉包和匿名函數經常被用作同義詞。但嚴格來說,匿名函數就是字面意義上沒有被賦予名稱的函數,而閉包則實際上是一個函數的實例,也就是說它是存在於內存里的某個結構體。如果從實現上來看的話,匿名函數如果沒有捕捉自由變量,那麼它其實可以被實現為一個函數指針,或者直接內聯到調用點,如果它捕捉了自由變量那麼它將是一個閉包;而閉包則意味着同時包括函數指針和環境兩個關鍵元素。在編譯優化當中,沒有捕捉自由變量的閉包可以被優化成普通函數,這樣就無需分配閉包結構體,這種編譯技巧被稱為函數躍升英語Lambda_lifting

詞源

[編輯]

閉包的概念是在1960年代為採用lambda演算的表達式的機器求值而開發的,它首次在1970年於PAL編程語言中完全實現,用來支持詞法作用域的頭等函數[1]

彼得·蘭丁(Peter Landin)在1964年將術語「閉包」定義為一種包含環境成分和控制成分的實體,用於在他的SECD機器上對表達式求值[2]Joel Moses英語Joel Moses認為是Landin發明了「閉包」這一術語,用來指代某些其開放綁定(自由變量)已經由其語法環境完成閉合(或者綁定)的lambda表達式,從而形成了閉合的表達式,或稱閉包。[3][4]。這一用法後來於1975年被SussmanSteele在定義 Scheme語言的時候予以採納[5],並廣為流傳。

語義

[編輯]

閉包和狀態表達

[編輯]

閉包可以用來在一個函數與一組「私有」變量之間建立關聯關係。在給定函數被多次調用的過程中,這些私有變量能夠保持其持久性。變量的作用域僅限於包含它們的函數,因此無法從其它程序代碼部分進行訪問。不過,變量的生存期是可以很長,在一次函數調用期間所建立所生成的值在下次函數調用時仍然存在。正因為這一特點,閉包可以用來完成信息隱藏,並進而應用於需要狀態表達的某些編程范型中。

不過,用這種方式來使用閉包時,閉包不再具有參照透明性英語Referential transparency,因此也不再是純函數。即便如此,在某些非純函數式編程語言,例如Scheme中,閉包還是得到了廣泛的使用。

閉包和頭類函數

[編輯]

典型的支持閉包的語言中,通常將函數當作頭等函數——在這些語言中,函數可以被當作參數傳遞、也可以作為函數返回值、綁定到變量名、就像字符串整數簡單類型。例如以下Scheme代碼:

; Return a list of all books with at least THRESHOLD copies sold.
(define (best-selling-books threshold)
  (filter
    (lambda (book)
      (>= (book-sales book) threshold))
    book-list))

在這個例子中,lambda表達式(lambda (book) (>= (book-sales book) threshold))出現在函數best-selling-books中。當這個lambda表達式被執行時,Scheme創造了一個包含此表達式以及對threshold變量的引用的閉包,其中threshold變量在lambda表達式中是自由變量

這個閉包接着被傳遞到filter函數。這個函數的功能是重複調用這個閉包以判斷哪些書需要增加到列表哪些書需要丟棄。因為閉包中引用了變量threshold,所以它在每次被filter調用時都可以使用這個變量,雖然filter可能定義在另一個文件中。

下面是用ECMAScript (JavaScript)寫的同一個例子:

// Return a list of all books with at least 'threshold' copies sold.
function bestSellingBooks(threshold) {
  return bookList.filter(
      function (book) { return book.sales >= threshold; }
    );
}

這裡,關鍵字function取代了lambdaArray.filter方法[6]取代了filter函數,但兩段代碼的功能是一樣的。

一個函數可以創建一個閉包並返回它,如下述JavaScript例子:

// Return a function that approximates the derivative of f
// using an interval of dx, which should be appropriately small.
function derivative(f, dx) {
  return function (x) {
    return (f(x + dx) - f(x)) / dx;
  };
}

因為在這個例子中閉包已經超出了創建它的函數的範圍,所以變量fdx將在函數derivative返回後繼續存在。在沒有閉包的語言中,變量的生命周期只限於創建它的環境。但在有閉包的語言中,只要有一個閉包引用了這個變量,它就會一直存在。清理不被任何函數引用的變量的工作通常由垃圾回收完成,但對於 C++ 這種沒有垃圾收集(起碼目前仍沒有一個為語言本身所認可的)的語言而言也不是難事——通過一些細緻而瑣碎的步驟。

閉包的用途

[編輯]
  • 因為閉包只有在被調用時才執行操作(暫且不論用於生成這個閉包對象本身的開銷,比如 C++ 中按值捕獲意味着執行複製構造函數),即「惰性求值」,所以它可以被用來定義控制結構。例如:在Smalltalk語言中,所有的控制結構,包括分支條件(if/then/else)和循環(while和for),都是通過閉包實現的。用戶也可以使用閉包定義自己的控制結構。
  • 多個函數可以使用一個相同的環境,這使得它們可以通過改變那個環境相互交流。比如在Scheme中:
(define foo #f)
(define bar #f)

(let ((secret-message "none"))
  (set! foo (lambda (msg) (set! secret-message msg)))
  (set! bar (lambda () secret-message)))

(display (bar)) ; prints "none"
(newline)
(foo "meet me by the docks at midnight")
(display (bar)) ; prints "meet me by the docks at midnight"

閉包的實現

[編輯]

典型實現方式是定義一個特殊的數據結構,保存了函數地址指針與閉包創建時的函數的詞法環境表示(那些非局部變量的綁定)。使用函數調用棧的語言實現閉包比較困難,因而這也說明了為什麼大多數實現閉包的語言是基於垃圾收集機制——當然,不使用垃圾收集也可以做到。

閉包的實現與函數對象很相似。

通過將自由變量放進參數表、並擴大函數名字的作用域,可以把一個閉包 / 匿名 / 內部函數變成一個普通的函數,這叫做「Lambda 提升英語Lambda lifting」。例:

void G(void){
    const std::wstring wstr=L"Hello, world!";
    std::function<wchar_t(size_t)> fn=[&wstr](size_t ui)->wchar_t{
        return wstr[ui%wstr.length()];
    };
    std::wcout<<fn(3)<<std::endl;//'l'
}
//那么 fn 是一个闭包,指向那个匿名函数。
//这里 wstr 是自由变量,首先将其放入参数表:
void G(void){
    const std::wstring wstr=L"Hello, world!";
    std::function<wchar_t(size_t, const std::wstring &)> fn=[](size_t ui, const std::wstring &wstr)->wchar_t{
        return wstr[ui%wstr.length()];
    };
    std::wcout<<fn(3, wstr)<<std::endl;//'l'
}
//现在 fn 中没有自由变量了。把这个匿名函数取个名之后放到全局命名空间里:
wchar_t fn(size_t ui, const std::wstring &wstr){
    return wstr[ui%wstr.length()];
}
void G(void){
    const std::wstring wstr=L"Hello, world!";
    std::wcout<<fn(3, wstr)<<std::endl;//'l'
}
//这就把 fn“提升”成了一个普通的函数。

各種語言中(類似)閉包的結構

[編輯]

C語言的回調函數

[編輯]

C語言中,支持回調函數的庫有時在註冊時需要兩個參數:一個函數指針,一個獨立的void*指針用以保存用戶數據。這樣的做法允許回調函數恢復其調用時的狀態。這樣的慣用法在功能上類似於閉包,但語法上有所不同。

gcc對C語言的擴展

[編輯]

gcc編譯器對C語言實現了一種閉包的程序特性。

C語言擴展:Blocks

[編輯]

C語言 (使用LLVM編譯器或蘋果修改版的GCC)支持。閉包變量用__block標記。同時,這個擴展也可以應用到Objective-CC++中。

typedef int (^IntBlock)();

IntBlock downCounter(int start) {
	 __block int i = start;
	 return Block_copy( ^int() {
		 return i--;
	 });
 }

IntBlock f = downCounter(5);
printf("%d", f());
printf("%d", f());
printf("%d", f());
Block_release(f);

C++函數對象

[編輯]

C++早期標準允許通過重載operator()來定義函數對象。這種對象的行為在某種程度上與函數式編程語言中的函數類似。它們可以在運行時動態創建、保存狀態,但是不能如閉包一般方便地隱式獲取局部變量,並且有「專物專用」的繁瑣問題——對於每一段閉包代碼都要單獨寫一個函數對象類。

C++11標準已經支持了閉包,這是一種特殊的函數對象,由特殊的語言結構——lambda表達式自動構建。C++閉包中保存了其代碼內全部向外引用的變量的拷貝或引用。如果是對外界環境中的對象的引用,且閉包執行時該外界環境的變量已經不存在(如在調用棧上已經展開),那麼可導致未定義行為,因為C++並不擴展這些被引用的外界環境的變量的生命期。示例代碼如下:

void foo(string myname) {
	typedef vector<string> names;
	int y;
	names n;
	// ...
	names::iterator i =
	 find_if(n.begin(), n.end(), [&](const string& s){return s != myname && s.size() > y;});	
	// 'i' 现在是'n.end()'或指向'n'中第一个
	// 不等于'myname'且长度大于'y'的字符串
}

參考文獻

[編輯]
  1. ^ David A. Turner (2012). "Some History of Functional Programming Languages"頁面存檔備份,存於網際網路檔案館). Trends in Functional Programming '12. Section 2, note 8 contains the claim about M-expressions.
  2. ^ 彼得·蘭丁, The mechanical evaluation of expressions (PDF), 1964 [2022-11-16], (原始內容存檔 (PDF)於2022-11-16), Also we represent the value of a λ-expression by a bundle of information called a "closure," comprising the λ-expression and the environment relative to which it was evaluated. We must therefore arrange that such a bundle is correctly interpreted whenever it has to be applied to some argument. More precisely:
      a closure has
        an environment part which is a list whose two items are:
          ⑴ an environment
          ⑵ an identifier or list of identifiers,
        and a control part which consists of a list whose sole item is an AE.
    The value relative to E of a λ-expression X is represented by the closure denoted by
      constructclosure((E, bvX), unitlist(bodyX))
     
  3. ^ Joel Moses, The Function of FUNCTION in LISP, or Why the FUNARG Problem Should Be Called the Environment Problem (PDF), June 1970 [2009-10-27], AI Memo 199, (原始內容存檔於2010-05-23), A useful metaphor for the difference between FUNCTION and QUOTE in LISP is to think of QUOTE as a porous or an open covering of the function since free variables escape to the current environment. FUNCTION acts as a closed or nonporous covering (hence the term "closure" used by Landin). Thus we talk of "open" Lambda expressions (functions in LISP are usually Lambda expressions) and "closed" Lambda expressions. [...] My interest in the environment problem began while Landin, who had a deep understanding of the problem, visited MIT during 1966-67. I then realized the correspondence between the FUNARG lists which are the results of the evaluation of "closed" Lambda expressions in LISP and ISWIM's Lambda Closures. 
  4. ^ Åke Wikström. Functional Programming using Standard ML. 1987. ISBN 0-13-331968-7. The reason it is called a "closure" is that an expression containing free variables is called an "open" expression, and by associating to it the bindings of its free variables, you close it. 
  5. ^ Gerald Jay Sussman and Guy L. Steele, Jr., Scheme: An Interpreter for the Extended Lambda Calculus, December 1975, AI Memo 349 
  6. ^ array.filter. Mozilla Developer Center. 10 January 2010 [2010-02-09]. (原始內容存檔於2008-10-15). 
  7. ^ Re: FP, OO and relations. Does anyone trump the others?. 29 December 1999 [2008-12-23]. (原始內容存檔於2008-12-26). 

外部連結

[編輯]