Λ演算

λ演算是一套從數學邏輯中發展，以變數繫結和替換的規則，來研究函式如何抽象化定義、函式如何被應用以及遞迴的形式系統。它由數學家阿隆佐·邱奇在20世紀30年代首次發表。lambda演算作為一種廣泛用途的計算模型，可以清晰地定義什麼是一個可計算函式，而任何可計算函式都能以這種形式表達和求值，它能模擬單一磁帶圖靈機的計算過程；儘管如此，lambda演算強調的是變換規則的運用，而非實現它們的具體機器。lambda演算可比擬是最根本的程式語言，它包括了一條變換規則的否定：關於兩個lambda運算式是否等價的命題，無法由一個「通用的演演算法」判斷，這是不可判定效能夠證明的頭一個問題，甚至還在停機問題之先。lambda演算包括了建構lambda項，和對lambda項執行歸約的操作。在最簡單的lambda演算中，只使用以下的規則來建構lambda項：產生了諸如：(λx.λy.(λz.(λx.zx)(λy.zy))(x y))的表示式。如果表示式是明確而沒有歧義的，則括號可以省略。對於某些應用，其中可能包括了邏輯和數學的常量以及相關操作。本文討論的是邱奇的“無型別lambda演算”，此後，已經研究出來了一些有型別lambda演算。解釋與應用.λ演算是圖靈完備的，也就是說，這是一個可以用於模擬任何圖靈機的通用模型。 λ也被用在λ表示式和λ項中，用來表示將一個變數繫結在一個函式上。λ演算可以是有型別或者無型別的，在有型別λ演算中的同時又希望能用以證明更多定理。λ演算在數學、哲學、語言學和計算機科學中都有許多應用。它在程式語言理論中佔有重要地位，函數語言程式設計實現了λ演算支援。λ演算在範疇論中也是一個研究熱點。歷史.作為對數學基礎研究的一部分，數學家阿隆佐·邱奇在20世紀30年代提出了λ演算。 但最初的λ演算系統被證明是邏輯上不自洽的——在1935年斯蒂芬·科爾·克萊尼和J. B. Rosser舉出了。隨後，在1936年邱奇把那個版本的關於計算的部分抽出獨立發表—現在這被稱為無型別λ演算。 在1940年，他創立了一個計算能力更弱但是邏輯上自洽的系統，這被稱為簡單型別λ演算。直到1960年，λ演算與程式語言的關係被確立了；在這之前它只是一個正規化。由於理查德·蒙塔古和其他語言學家將λ演算應用於自然語言語法的研究，λ演算已經開始在語言學和計算機科學學界擁有一席之地。至於為何邱奇選擇λ作為符號，連他本人的解釋也互相矛盾：最初是在1964年的一封信中，他明確解釋稱這是《數學原理》一書中的類抽象符號作為區分，然後又改成形狀類似的λ。他在1984年又重申了這一點，但再後來他又表示選擇λ純粹是偶然。非形式化的直覺描述.在λ演算中，每個表示式都代表一個函式，這個函式有一個引數，並且會返回一個值。不論是引數和返回值，也都是一個單參的函式。可以這麼說，λ演算中只有一種“型別”，那就是這種單參函式。函式是透過λ表示式匿名地定義的，這個表示式說明了此函式將對其引數進行什麼操作。例如，“加2”函式f(x)= x + 2可以用lambda演算表示為λx.x + 2是左結合的：f x y =(f x) y。考慮這麼一個函式：它把一個函式作為引數，這個函式將被作用在3上：λf.f 3。如果把這個函式作用於我們先前的“加2”函式上：(λf.f 3)(λx.x+2)，則明顯地，下述三個表示式：(λf.f 3)(λx.x+2) 與 (λx.x + 2) 3 與 3 + 2是等價的。有兩個引數的函式可以透過lambda演算這樣表達：一個單一引數的函式，它的返回值又是一個單一引數的函式。例如，函式f(x, y) = x - y可以寫作λx.λy.x - y。下述三個表示式：(λx.λy.x - y) 7 2 與 (λy.7 - y) 2 與 7 - 2也是等價的。然而這種lambda表示式之間的等價性，無法找到某個通用的函式來判定。並非所有的lambda表示式都能被歸約至上述那樣的確定值，考慮(λx.x x)(λx.x x)或(λx.x x x)(λx.x x x)然後試圖把第一個函式作用在它的引數上。(λx.x x)被稱為ω 組合子，((λx.x x)(λx.x x))被稱為Ω，而((λx.x x x) (λx.x x x))被稱為Ω2，以此類推。若僅形式化函式作用的概念而不允許lambda表示式，就得到了組合子邏輯。動機.在數學和電腦科學中，「可計算的」函式是基礎觀念。對於所謂的可計算性，λ-演算提供了一個簡單明確的語義，使計算的性質可以被形式化研究。λ-演算結合了兩種簡化方式，使得這個語義變得簡單。第一種簡化是不給予函式一個確定名稱，而“匿名”地對待它們。例如，兩數的平方和函式formula_2可以用匿名的形式重新寫為：formula_3同樣地，formula_5可以用匿名的形式重新寫為：formula_6第二個簡化是λ演算只使用單一個引數輸入的函式。如果普通函式需要兩個引數，例如formula_7函式，可轉成接受單一引數，傳給另一個函式中介，而中介函式也只接受一個引數，最後輸出結果。例如，formula_3可以重新寫成：formula_9這是稱為柯里化的方法，將多引數的函式轉換成為多個中介函式的複合鏈，每個中介函式都只接受一個引數。將formula_7函式應用於引數(5,2)，直接產生結果formula_11formula_12formula_13,而對於柯里化轉換版的評估，需要再多一步：formula_14formula_15 //在內層表示式中formula_16的定義為formula_17，這就像β-歸約一樣。formula_18 //formula_19的定義為formula_20，再次如同β-歸約。formula_13得出相同結果。lambda演算.lambda演算是由特定形式語法所組成的一種語言，一組轉換規則可操作其中的lambda項。這些轉換規則被看作是一個等式理論或者一個操作定義。如上節所述，lambda演算中的所有函式都是匿名的，它們沒有名稱，它們只接受一個輸入變數，柯里化用於實現有多個輸入變數的函式。lambda項.lambda演算的語法將一些表示式定義為有效的lambda演算式，而某一些表示式無效，就像C程式語言中有些字串有效，有些則不是。有效的lambda演算式稱為“lambda項”。以下三個規則給出了語法上有效的lambda項，如何建構的歸納定義：其它的都不是lambda項。因此，lambda項若且唯若可重複應用這三個規則取得時，才是有效的。一些括號根據某些規則可以省略。例如，最外面的括號通常不會寫入。“lambda抽象”是指一個匿名函式的定義，它將單一輸入的formula_29替換成formula_23的表示式，所以產生了一個匿名函式，它採用formula_16的值並返回formula_23。例如，formula_33是表示使用函式formula_34作為formula_23項的一個lambda抽象。lambda抽象只是先“設定”了函式定義，還沒使用它。這個抽象在formula_23項中綁定了變數formula_16。一個應用formula_38表示將函式formula_23應用在輸入formula_27，亦即對輸入formula_27使用函式formula_23產生formula_43。lambda演算中並沒有變數宣告的概念。如formula_44的定義中，lambda演算將formula_19當作尚未定義的變數。lambda抽象formula_47在語法上是有效的，並表示將其輸入新增到未知formula_19的函式。可用圓括弧對來消除歧義。例如，formula_49和formula_50表示不同的項。操作函式的函式.在lambda演算中，函式被認為是頭等物件，因此函式可以當作輸入，或作為其它函式的輸出返回。例如，formula_51表示對映到本身的函式，formula_6和formula_53表示將這個函式應用於formula_19。此外，formula_55則表示無論輸入為何，始終返回formula_19值的常數函式formula_57。lambda演算中的函式應用是左結合的，因此formula_58表示formula_59。有幾個“等價”和“化簡”的概念，允許將各個lambda項“縮減”為“相同”的lambda項。formula_60-等價.對於lambda項，等價的基本形式定義，是formula_60-等價。它捕捉了直覺概念，在lambda抽象中一個繫結變數的特別選擇並不重要。比如，formula_51和formula_63是formula_60-等價的lambda項，它們都表示相同的函式；但如formula_16和formula_19項則不是formula_60-等價的，因為它們並非以lambda抽象方式繫結的。在許多演示中，通常會確定formula_60-等價的lambda項。為了能夠定義formula_69-歸約，需要以下定義：自由變數.所謂的自由變數是那些在lambda抽象不受到繫結的變數。表示式中的一組自由變數定義歸納如下：例如，代表對映自身的formula_51，其中的lambda項沒有自由變數，但是在函式formula_79中的lambda項，有一個自由變數formula_19。避免捕獲的替換記法.假設formula_23，formula_27和formula_83是lambda項，而formula_16和formula_19是變數。如果寫成formula_86是一種"避免被捕獲"的記法方式，表示在formula_23這個lambda項中，以formula_83來替換formula_16變數的值。這定義為：例如，formula_101和formula_102。新鮮度條件對於確保替換不會改變函式的意義很重要。例如，忽視新鮮度條件的替代：formula_105。此替換會將原本意義為常量函式的formula_106，轉換成意義為對映自身函式的formula_51。一般來說，在無法滿足新鮮度條件的情況，可利用formula_60-重新命名使用一個合適的新變數來補救，切換回正確的替換概念；比如在formula_109中，使用一個新變數formula_110重新命名這個lambda抽象，獲取formula_111，則替換就能保留原本函式的義涵。formula_69-歸約.β-歸約規定了形式如formula_113的應用，可以化簡成formula_114項。符號記法formula_115用於表示formula_116 經過β-歸約轉換為formula_117。例如，對於每個formula_27，可轉換為formula_119。這表明formula_120實際上的應用是對映自身函式。同樣地，formula_121，表明了formula_122是一個常量函式。lambda演算可視為函數語言程式設計語言的理想化版本，如Haskell或ML語言。在這種觀點下，β-歸約對應於一組計算步驟。這個步驟重複應用β-轉換，一直到沒有東西能再被化簡。在無型別lambda演算中，如本文所述，這個歸約過程可能無法終止，比如formula_123，是個特殊的lambda項。這裡formula_124也就是說，該lambda項在一次β-歸約中化簡到本身，因此歸約過程將永遠不會終止。無型別lambda演算的另一方面是它並不區分不同種類的資料。例如，需要編寫只針對數字操作的功能。然而，在無型別的lambda演算中，沒有辦法避免函式被應用於真值、字串或其它非數字物件。形式化定義.形式化地，我們從一個識別符號的可數無窮集合開始，比如{a, b, c, ..., x, y, z, x1, x2, ...}，則所有的lambda表示式可以透過下述以BNF正規化表達的上下文無關文法描述：頭兩條規則用來生成函式，而第三條描述了函式是如何作用在引數上的。通常，lambda抽象lambda運算子被繫結到它後面的整個表示式。例如，表示式 (λx.x x)(λy.y) 可以簡寫成λ(x.x x) λy.y 。類似λx.(x y)這樣的lambda表示式並未定義一個函式，因為變數y的出現是自由的，即它並沒有被繫結到表示式中的任何一個λ上。一個lambda表示式的自由變數的集合是透過下述規則定義的：例，對於表示式λx.x，其中表達式x中，由1，它的自由變數集合是x，又由2，表示式λx.x的自由變數的集合是表示式x的自由變數集合減去變數x。所以對於表示式λx.x，它的自由變數集合是空。例，對於表示式λx.x x由形式化描述的第3點，我們把它看作((λx.x)(x))，(λx.x)和(x)分別為表示式，由上一例知道(λx.x)的自由變數集合為空，表示式(x)的變數集合為變數x，所以對於λx.x x，它的自由變數集合為x與空的並，即x。在lambda表示式的集合上定義了一個等價關係(在此用==標註)，“兩個表示式其實表示的是同一個函式”這樣的直覺性判斷即由此表述，這種等價關係是透過所謂的“alpha-變換規則”和“beta-歸約規則”。歸約.歸約的操作包括：α-變換.Alpha-變換規則表達的是，被繫結變數的名稱是不重要的。比如說λx.x和λy.y是同一個函式。儘管如此，這條規則並非像它看起來這麼簡單，關於被繫結的變數能否由另一個替換有一系列的限制。Alpha-變換規則陳述的是，若V與W均為變數，E是一個lambda表示式，同時E[V:=W]是指把表示式E中的所有的V的自由出現都替換為W，那麼在W不是E中的一個自由出現，且如果W替換了V，W不會被E中的λ繫結的情況下，有λV.E == λW.E[V:=W]這條規則告訴我們，例如λx.(λx.x) x這樣的表示式和λy.(λx.x) y是一樣的。β-歸約.Beta-歸約規則表達的是函式作用的概念。它陳述了若所有的E'的自由出現在E [V:=E']中仍然是自由的情況下，有((λV.E) E') == E [V:=E']成立。==關係被定義為滿足上述兩條規則的最小等價關係。對上述等價關係的一個更具操作性的定義可以這樣獲得：只允許從左至右來應用規則。不允許任何beta歸約的lambda表示式被稱為Beta正規化。並非所有的lambda表示式都存在與之等價的正規化，若存在，則對於相同的形式引數命名而言是唯一的。此外，有一個演算法使用者計算正規化，不斷地把最左邊的形式引數替換為實際引數，直到無法再作任何可能的規約為止。這個演算法當且僅當lambda表示式存在一個正規化時才會停止。Church-Rosser定理說明了，當且僅當兩個表示式等價時，它們會在形式引數換名後得到同一個正規化。η-變換.前兩條規則之後，還可以加入第三條規則，eta-變換，來形成一個新的等價關係。Eta-變換表達的是外延性的概念，在這裡外延性指的是，對於任一給定的引數，當且僅當兩個函式得到的結果都一致，則它們將被視同為一個函式。Eta-變換可以令 formula_125 和 formula_126 相互轉換，只要 formula_16 不是 formula_126 中的自由變數。下面說明了為何這條規則和外延性是等價的：若 formula_126 與 formula_130 外延地等價，即，formula_131 對所有的 formula_132 表示式 formula_133成立，則當取 formula_133 為在 formula_126 中不是自由出現的變數 formula_16時，我們有formula_137，因此 formula_138，由eta-變換f == g。所以只要eta-變換是有效的，會得到外延性也是有效的。相反地，若外延性是有效的，則由beta-歸約，對所有的y有(λx .f x) y == f y，可得λx .f x == f，即eta-變換也是有效的。資料型別的編碼.基本的lambda演演算法可用於建構布林值，算術，資料結構和遞迴的模型，如以下各小節所述。lambda演算中的算術.在lambda演算中有許多方式都可以定義自然數，但最常見的還是邱奇數，下面是它們的定義：0 = λf.λx.x1 = λf.λx.f x2 = λf.λx.f (f x)3 = λf.λx.f (f (f x))以此類推。直觀地說，lambda演算中的數字n就是一個把函式f作為引數並以f的n次冪為返回值的函式。換句話說，邱奇整數是一個高階函式 -- 以單一引數函式f為引數，返回另一個單一引數的函式。(注意在邱奇原來的lambda演算中，lambda表示式的形式引數在函式體中至少出現一次，這使得我們無法像上面那樣定義0)在邱奇整數定義的基礎上，我們可以定義一個後繼函式，它以n為引數，返回n + 1：SUCC = λn.λf.λx.f(n f x)加法是這樣定義的：PLUS = λm.λn.λf.λx.m f (n f x)PLUS可以被看作以兩個自然數為引數的函式，它返回的也是一個自然數。你可以試試驗證PLUS 2 3與5是否等價。乘法可以這樣定義：MULT = λm.λn.m (PLUS n) 0,即m乘以n等於在零的基礎上m次加n。另一種方式是MULT = λm.λn.λf.m (n f)正整數n的前驅元PRED n = n - 1要複雜一些：PRED = λn.λf.λx.n (λg.λh.h (g f)) (λu.x) (λu.u)或者PRED = λn.n(λg.λk.(g 1) (λu.PLUS(g k) 1) k) (λl.0) 0注意codice_1表示的是，當codice_2是零時，表示式的值是codice_3，否則是codice_4。邏輯與謂詞.習慣上，下述兩個定義被用作TRUE和FALSE這樣的布林值：TRUE := λx.λy.xFALSE := λx.λy.y(注意FALSE等價於前面定義邱奇數零)接著，透過這兩個λ-項，我們可以定義一些邏輯運算：AND := λp q.p q FALSEOR := λp q.p TRUE qNOT := λp.p FALSE TRUEIFTHENELSE := λp x y.p x y我們現在可以計算一些邏輯函式，比如：AND TRUE FALSE≡(λp q.p q FALSE) TRUE FALSE →β TRUE FALSE FALSE≡(λx y.x) FALSE FALSE →β FALSE我們見到AND TRUE FALSE等價於FALSE。“謂詞”是指返回布林值的函式。最基本的一個謂詞是ISZERO，當且僅當其引數為零時返回真，否則返回假：ISZERO := λn.n (λx.FALSE) TRUE運用謂詞與上述TRUE和FALSE的定義，使得"if-then-else"這類語句很容易用lambda演算寫出。有序對.有序對資料型別可以用TRUE、FALSE和IF來定義。CONS := λx y.λp.IF p x yCAR := λx.x TRUECDR := λx.x FALSE連結串列資料型別可以定義為，要麼是為空列表保留的值，要麼是CONS一個元素和一個更小的列表。附加的程式設計技術.lambda演算出現在相當大量的程式設計習慣用法中，其中許多程式語言最初以lambda演算作為語義基礎，在此背景下開發的；有效地利用lambda演算作為基底。因為幾個程式語言部份含括了lambda演算，所以這些技術也可以在實際的程式設計中見到，但有可能被認為是模糊或外來的。命名常數.在lambda演算中，函式庫將採用預先定義好的函式集合，其中lambda項僅僅是特定的常量。純粹的lambda演演算法並不具有命名常數的概念，因為所有的原子λ項都是變數；但是在程式主體中，我們可將一個變數當成常量的名稱，利用lambda抽象把這個變數繫結，並將該lambda抽象應用於預期的定義，來模擬命名常量的作法。因此在"N"，則寫成如下：(λ"f"."N") "M"作者經常引入類似如let的語法糖，允許以更直觀的次序撰寫上述內容：let "f" = "M" in "N"透過等號連結這個命名常數，即可將lambda演算“程式設計”的一個lambda項，寫為零或多個函式的定義，而使用構成程式主體的那些函式。這個let顯著的限制，是在"M"中並沒有定義"f"名稱，因為"M"不在繫結"f"的lambda抽象範疇之內；這意味著遞迴函式定義不能以let來使用"M"。更進步的letrec語法糖允許以直覺的方式編寫遞迴函式定義，而不需用到不動點組合子。遞迴與不動點.遞迴是使用函式自身的函式定義；在表面上，lambda演算不允許這樣。但是這種印象是誤解。考慮個例子，階乘函式f(n)遞迴的定義為f(n):= if n = 0 then 1 else n·f(n-1)。在lambda演算中，你不能定義包含自身的函式。要避免這樣，你可以開始於定義一個函式，這裡叫g，它接受一個函式f作為引數並返回接受n作為引數的另一個函式：g := λf n.(if n = 0 then 1 else n·f(n-1))。函式g返回要麼常量1，要麼函式f對n-1的n次應用。使用ISZERO謂詞，和上面描述的布林和代數定義，函式g可以用lambda演算來定義。但是，g自身仍然不是遞迴的；為了使用g來建立遞迴函式，作為引數傳遞給g的f函式必須有特殊的性質。也就是說，作為引數傳遞的f函式必須展開為呼叫帶有一個引數的函式g -- 並且這個引數必須再次f函式!換句話說，f必須展開為g(f)。這個到g的呼叫將接著展開為上面的階乘函式並計算下至另一層遞迴。在這個展開中函式f將再次出現，並將被再次展開為g(f)並繼續遞迴。這種函式，這裡的f = g(f)，叫做g的不動點，並且它可以在lambda演算中使用叫做悖論運算元或不動點運算元來實現，它被表示為Y -- Y組合子：Y = λg.(λx.g(x x))(λx.g(x x))在lambda演算中，Y g是g的不動點，因為它展開為g(Y g)。現在，要完成我們對階乘函式的遞迴呼叫，我們可以簡單的呼叫 g(Y g)n，這裡的n是我們要計算它的階乘的數。比如假定n = 5，它展開為：(λn.(if n = 0 then 1 else n·((Y g)(n-1)))) 5if 5 = 0 then 1 else 5·(g(Y g，5-1))5·(g(Y g)4)5·(λn.(if n = 0 then 1 else n·((Y g)(n-1))) 4)5·(if 4 = 0 then 1 else 4·(g(Y g，4-1)))5·(4·(g(Y g)3))5·(4·(λn.(if n = 0 then 1 else n·((Y g)(n-1))) 3))5·(4·(if 3 = 0 then 1 else 3·(g(Y g，3-1))))5·(4·(3·(g(Y g)2)))等等，遞迴的求值演算法的結構。所有遞迴定義的函式都可以看作某個其他適當的函式的不動點，因此，使用Y所有遞迴定義的函式都可以表達為lambda表示式。特別是，我們現在可以明晰的遞迴定義自然數的減法、乘法和比較謂詞。標準化的組合子名稱.某一些lambda項有普遍接受的名稱：I := λ"x"."x"K := λ"x".λ"y"."x"S := λ"x".λ"y".λ"z"."x" "z" ("y" "z")B := λ"x".λ"y".λ"z"."x" ("y" "z")C := λ"x".λ"y".λ"z"."x" "z" "y"W := λ"x".λ"y"."x" "y" "y"U := λ"x".λ"y"."y" ("x" "x" "y")ω := λ"x"."x" "x"Ω := ω ωY := λ"g".(λ"x"."g" ("x" "x")) (λ"x"."g" ("x" "x"))其中有幾個在“消除lambda抽象”中有直接的應用，將lambda項變為組合演算的術語。消除lambda抽象.如果"N"是一個沒有λ-抽象的lambda項，但可能包含了命名常量的λ"x"."N"；也可以被視為匿名變數，就如同"T"("x","N")從"N"之中刪除所有出現的"x"，同時仍然允許在"N"包含"x"的位置替換引數值。轉換函式"T"可由下式定義："T"("x", "x") := I"T"("x", "N") := K "N" if "x" is not free in "N"."T"("x", "M" "N") := S "T"("x", "M") "T"("x", "N")在這兩種情況下，形式"T"("x","N")"P"可藉由使初始的組合子I，K或S獲取引數"P"而化簡，就像(λ"x"."N") "P"經過β-歸約一樣。I返回那個引數。K則將引數拋棄，就像(λ"x"."N")，如果"x"在"N"中不是以自由變量出現。S將引數傳遞給應用程式的兩個子句，然後將第一個結果應用到第二個的結果之上。組合子B和C類似於S，但把引數傳遞給應用的一個子項，如果子項中沒有出現"x"，則儲存後續的K。與B和C相比，S組合子實際上混合了兩個功能：重新排列引數，並複製一個引數，以便它可以在兩個地方使用。W組合子只做後者，產生了SKI組合子演算的B，C，K，W系統。可計算函式和lambda演算.自然數的函式F: N → N是可計算函式，當且僅當存在著一個lambda表示式f，使得對於N中的每對x, y都有F(x) = y當且僅當f x == y，這裡的x和y分別是對應於x和y的邱奇數。這是定義可計算性的多種方式之一；關於其他方式和它們的等價者的討論請奇-圖靈論題。lambda演算與程式語言.匿名函式.比如計算平方的函式 square 在 Lisp 中可以表示為如下的 lambda 表示式符號 lambda 建立一個匿名函式，給定引數列表 (x) ，以及一個作為函式體的表示式 (* x x)。 匿名函式有時稱為 lambda 表示式。很多命令式語言都有函式指標或者類似的機制。但是函式指標並不是型別中的一等公民，函式是一等公民當且僅當函式可以在執行時建立。 下面一些語言支援函式的執行時建立： Smalltalk、 JavaScript、 Kotlin、 Scala、 Python3、 C# ("delegates")、 C++11等。