亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

歷史

最開始，邱奇試圖創(chuàng)制一套完整的形式系統(tǒng)作為數(shù)學(xué)的基礎(chǔ)，當(dāng)他發(fā)現(xiàn)這個系統(tǒng)易受羅素悖論的影響時，就把lambda演算單獨分離出來，用于研究可計算性，最終導(dǎo)致了他對判定性問題的否定回答。

非形式化的描述

在λ演算中，每個表達(dá)式都代表一個函數(shù)，這個函數(shù)有一個參數(shù)，并且返回一個值。不論是參數(shù)和返回值，也都是一個單參的函數(shù)。可以這么說，λ演算中，只有一種“類型”，那就是這種單參函數(shù)。

函數(shù)是通過λ表達(dá)式匿名地定義的，這個表達(dá)式說明了此函數(shù)將對其參數(shù)進(jìn)行什么操作。例如，“加2”函數(shù)f(x)= x + 2可以用lambda演算表示為λx.x + 2 (或者λy.y + 2，參數(shù)的取名無關(guān)緊要)而f(3)的值可以寫作(λx.x + 2) 3。函數(shù)的應(yīng)用（application）是左結(jié)合的：f x y =(f x) y。

考慮這么一個函數(shù)：它把一個函數(shù)作為參數(shù)，這個函數(shù)將被作用在3上：λf.f 3。如果把這個（用函數(shù)作參數(shù)的）函數(shù)作用于我們先前的“加2”函數(shù)上：(λf.f 3)(λx.x+2)，則明顯地，下述三個表達(dá)式：

是等價的。有兩個參數(shù)的函數(shù)可以通過lambda演算這么表達(dá)：一個單一參數(shù)的函數(shù)的返回值又是一個單一參數(shù)的函數(shù)（參見Currying）。例如，函數(shù)f(x, y) = x - y可以寫作λx.λy.x - y。下述三個表達(dá)式：

也是等價的。然而這種lambda表達(dá)式之間的等價性無法找到一個通用的函數(shù)來判定。

并非所有的lambda表達(dá)式都可以規(guī)約至上述那樣的確定值，考慮

或

然后試圖把第一個函數(shù)作用在它的參數(shù)上。 (λx.x x)被稱為ω組合子，((λx.x x)(λx.x x))被稱為Ω，而((λx.x x x) (λx.x x x))被稱為Ω2，以此類推。

若僅形式化函數(shù)作用的概念而不允許lambda表達(dá)式，就得到了組合子邏輯。

形式化定義

形式化地，我們從一個標(biāo)識符（identifier）的可數(shù)無窮集合開始，比如{a, b, c, ..., x, y, z, x1, x2, ...}，則所有的lambda表達(dá)式可以通過下述以BNF范式表達(dá)的上下文無關(guān)文法描述：

 ::=

 ::= (λ.)

 ::= ( )

頭兩條規(guī)則用來生成函數(shù)，而第三條描述了函數(shù)是如何作用在參數(shù)上的。通常，lambda抽象（規(guī)則2）和函數(shù)作用（規(guī)則3）中的括號在不會產(chǎn)生歧義的情況下可以省略。如下假定保證了不會產(chǎn)生歧義：（1）函數(shù)的作用是左結(jié)合的，和（2）lambda操作符被綁定到它后面的整個表達(dá)式。例如，表達(dá)式 (λx.x x)(λy.y) 可以簡寫成λ(x.x x) λy.y 。

類似λx.(x y)這樣的lambda表達(dá)式并未定義一個函數(shù)，因為變量y的出現(xiàn)是自由的，即它并沒有被綁定到表達(dá)式中的任何一個λ上。一個lambda表達(dá)式的自由變量的集合是通過下述規(guī)則（基于lambda表達(dá)式的結(jié)構(gòu)歸納地）定義的：

在表達(dá)式V中，V是變量，則這個表達(dá)式里自由變量的集合只有V。

在表達(dá)式λV .E中（V是變量，E是另一個表達(dá)式），自由變量的集合是E中自由變量的集合減去變量V。因而，E中那些V被稱為綁定在λ上。

在表達(dá)式 (E E")中，自由變量的集合是E和E"中自由變量集合的并集。

例，對于表達(dá)式λx.x（我們將第一個x視作變量，第二個x視作表達(dá)式），其中表達(dá)式x中，由1，它的自由變量集合是x，又由2，表達(dá)式λx.x的自由變量的集合是表達(dá)式x的自由變量集合減去變量x。所以對于表達(dá)式λx.x，它的自由變量集合是空。 例，對于表達(dá)式λx.x x由形式化描述的第3點，我們把它看作((λx.x)(x))，(λx.x)和(x)分別為表達(dá)式，由上一例知道(λx.x)的自由變量集合為空，表達(dá)式(x)的變量集合為變量x，所以對于λx.x x，它的自由變量集合為x與空的并，即x。

在lambda表達(dá)式的集合上定義了一個等價關(guān)系(在此用==標(biāo)注)，“兩個表達(dá)式其實表示的是同一個函數(shù)”這樣的直覺性判斷即由此表述，這種等價關(guān)系是通過所謂的“alpha-變換規(guī)則”和“beta-歸約規(guī)則”。

歸約

α-變換

Alpha-變換規(guī)則表達(dá)的是，被綁定變量的名稱是不重要的。比如說λx.x和λy.y是同一個函數(shù)。盡管如此，這條規(guī)則并非像它看起來這么簡單，關(guān)于被綁定的變量能否由另一個替換有一系列的限制。

Alpha-變換規(guī)則陳述的是，若V與W均為變量，E是一個lambda表達(dá)式，同時E[V:=W]是指把表達(dá)式E中的所有的V的自由出現(xiàn)都替換為W，那么在W不是 E中的一個自由出現(xiàn)，且如果W替換了V，W不會被E中的λ綁定的情況下，有

這條規(guī)則告訴我們，例如λx.(λx.x) x這樣的表達(dá)式和λy.(λx.x) y是一樣的。

β-歸約

Beta-歸約規(guī)則表達(dá)的是函數(shù)作用的概念。它陳述了若所有的E"的自由出現(xiàn)在E [V:=E"]中仍然是自由的情況下，有

成立。

==關(guān)系被定義為滿足上述兩條規(guī)則的最小等價關(guān)系（即在這個等價關(guān)系中減去任何一個映射，它將不再是一個等價關(guān)系）。

對上述等價關(guān)系的一個更具操作性的定義可以這樣獲得：只允許從左至右來應(yīng)用規(guī)則。不允許任何beta歸約的lambda表達(dá)式被稱為Beta范式。并非所有的lambda表達(dá)式都存在與之等價的范式，若存在，則對于相同的形式參數(shù)命名而言是唯一的。此外，有一個算法用戶計算范式，不斷地把最左邊的形式參數(shù)替換為實際參數(shù)，直到無法再作任何可能的規(guī)約為止。這個算法當(dāng)且僅當(dāng)lambda表達(dá)式存在一個范式時才會停止。Church-Rosser定理說明了，當(dāng)且僅當(dāng)兩個表達(dá)式等價時，它們會在形式參數(shù)換名后得到同一個范式。

η-變換

前兩條規(guī)則之后，還可以加入第三條規(guī)則，eta-變換，來形成一個新的等價關(guān)系。Eta-變換表達(dá)的是外延性的概念，在這里外延性指的是，兩個函數(shù)對于所有的參數(shù)得到的結(jié)果都一致，當(dāng)且僅當(dāng)它們是同一個函數(shù)。Eta-變換可以令λx .f x和f相互轉(zhuǎn)換，只要x不是f中的自由出現(xiàn)。下面說明了為何這條規(guī)則和外延性是等價的：

若f與g外延地等價，即，f a == g a對所有的lambda表達(dá)式a成立，則當(dāng)取a為在f中不是自由出現(xiàn)的變量x時，我們有f x == g x，因此λx .f x == λx .g x，由eta-變換f == g。所以只要eta-變換是有效的，會得到外延性也是有效的。

相反地，若外延性是有效的，則由beta-歸約，對所有的y有(λx .f x) y == f y，可得λx .f x == f，即eta-變換也是有效的。

lambda演算中的算術(shù)

在lambda演算中有許多方式都可以定義自然數(shù)，但最常見的還是邱奇數(shù)，下面是它們的定義：

以此類推。直觀地說，lambda演算中的數(shù)字n就是一個把函數(shù)f作為參數(shù)并以f的n次冪為返回值的函數(shù)。換句話說，邱奇整數(shù)是一個高階函數(shù)-- 以單一參數(shù)函數(shù)f為參數(shù)，返回另一個單一參數(shù)的函數(shù)。

(注意在邱奇原來的lambda演算中，lambda表達(dá)式的形式參數(shù)在函數(shù)體中至少出現(xiàn)一次，這使得我們無法像上面那樣定義0)在邱奇整數(shù)定義的基礎(chǔ)上，我們可以定義一個后繼函數(shù)，它以n為參數(shù)，返回n + 1：

加法是這樣定義的：

PLUS可以被看作以兩個自然數(shù)為參數(shù)的函數(shù)，它返回的也是一個自然數(shù)。你可以試試驗證

與5是否等價。乘法可以這樣定義：

即m乘以n等于在零的基礎(chǔ)上m次加n。另一種方式是

正整數(shù)n的前驅(qū)元（predecessesor）PRED n = n - 1要復(fù)雜一些：

或者

注意(g 1)(λu.PLUS(g k) 1) k表示的是，當(dāng)g(1)是零時，表達(dá)式的值是k，否則是g(k)+ 1。

邏輯與謂詞

習(xí)慣上，下述兩個定義（稱為邱奇布爾值）被用作TRUE和FALSE這樣的布爾值：

接著，通過這兩個λ-項，我們可以定義一些邏輯運算：

我們現(xiàn)在可以計算一些邏輯函數(shù)，比如：

我們見到AND TRUE FALSE等價于FALSE。

“謂詞”是指返回布爾值的函數(shù)。最基本的一個謂詞是ISZERO，當(dāng)且僅當(dāng)其參數(shù)為零時返回真，否則返回假：

運用謂詞與上述TRUE和FALSE的定義，使得"if-then-else"這類語句很容易用lambda演算寫出。

有序?qū)?/span>

有序?qū)Γ?-元組）數(shù)據(jù)類型可以用TRUE、FALSE和IF來定義。

鏈表數(shù)據(jù)類型可以定義為，要么是為空列表保留的值（e.g.FALSE），要么是CONS一個元素和一個更小的列表。

遞歸

遞歸是使用函數(shù)自身的函數(shù)定義；在表面上，lambda演算不允許這樣。但是這種印象是誤解?？紤]個例子，階乘函數(shù)f(n)遞歸的定義為

在lambda演算中，你不能定義包含自身的函數(shù)。要避免這樣，你可以開始于定義一個函數(shù)，這里叫g(shù)，它接受一個函數(shù)f作為參數(shù)并返回接受n作為參數(shù)的另一個函數(shù)：

函數(shù)g返回要么常量1，要么函數(shù)f對n-1的n次應(yīng)用。使用ISZERO謂詞，和上面描述的布爾和代數(shù)定義，函數(shù)g可以用lambda演算來定義。

但是，g自身仍然不是遞歸的；為了使用g來創(chuàng)建遞歸函數(shù)，作為參數(shù)傳遞給g的f函數(shù)必須有特殊的性質(zhì)。也就是說，作為參數(shù)傳遞的f函數(shù)必須展開為調(diào)用帶有一個參數(shù)的函數(shù)g -- 并且這個參數(shù)必須再次f函數(shù)!

換句話說，f必須展開為g(f)。這個到g的調(diào)用將接著展開為上面的階乘函數(shù)并計算下至另一層遞歸。在這個展開中函數(shù)f將再次出現(xiàn)，并將被再次展開為g(f)并繼續(xù)遞歸。這種函數(shù)，這里的f = g(f)，叫做g的不動點，并且它可以在lambda演算中使用叫做悖論算子或不動點算子來實現(xiàn)，它被表示為Y --Y組合子：

在lambda演算中，Y g是g的不動點，因為它展開為g(Y g)?，F(xiàn)在，要完成我們對階乘函數(shù)的遞歸調(diào)用，我們可以簡單的調(diào)用 g(Y g)n，這里的n是我們要計算它的階乘的數(shù)。

比如假定n = 5，它展開為：

等等，遞歸的求值算法的結(jié)構(gòu)。所有遞歸定義的函數(shù)都可以看作某個其他適當(dāng)?shù)暮瘮?shù)的不動點，因此，使用Y所有遞歸定義的函數(shù)都可以表達(dá)為lambda表達(dá)式。特別是，我們現(xiàn)在可以明晰的遞歸定義自然數(shù)的減法、乘法和比較謂詞。

可計算函數(shù)和lambda演算

自然數(shù)的函數(shù)F: N → N是可計算函數(shù)，當(dāng)且僅當(dāng)存在著一個lambda表達(dá)式f，使得對于N中的每對x, y都有F(x) = y當(dāng)且僅當(dāng)f x == y，這里的x和y分別是對應(yīng)于x和y的邱奇數(shù)。這是定義可計算性的多種方式之一；關(guān)于其他方式和它們的等價者的討論請參見邱奇-圖靈論題。

參見

邱奇-圖靈論題

遞歸函數(shù)

可計算函數(shù)

柯里化

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。