本页使用了标题或全文手工转换

λ演算

维基百科,自由的百科全书
跳转至: 导航搜索

λ演算(英語:lambda calculus,λ-calculus)是一套從數學邏輯中發展,以變數綁定和替換的規則,來研究函式如何抽象化定義、函式如何被應用以及遞迴形式系統。它由數學家阿隆佐·邱奇在20世紀30年代首次發表。Lambda演算作為一種廣泛用途的計算模型,可以清晰地定義什麼是一個可計算函式,而任何可計算函式都能以這種形式表達和求值,它能模擬單一磁帶图灵机的計算過程;儘管如此,Lambda演算強調的是變換規則的運用,而非實現它們的具體機器。

Lambda演算可比擬是最根本的編程語言,它包括了一條變換規則(變數替換)和一條將函式抽象化定義的方式。因此普遍公認是一種更接近軟體而非硬體的方式。對函數式編程語言造成很大影響,比如LispML语言Haskell语言。在1936年邱奇利用λ演算給出了對於判定性問題(Entscheidungsproblem)的否定:關於兩個lambda運算式是否等價的命題,無法由一個「通用的演算法」判斷,這是不可判定效能夠證明的頭一個問題,甚至還在停机问题之先。

Lambda演算包括了建構lambda項,和對lambda項執行歸約的操作。在最簡單的lambda演算中,只使用以下的規則來建構lambda項:

語法 名稱 描述
a 變量 表示參數或數學/邏輯值的字元或字串
(λx.M) 抽象化 函數定義(M是一個lambda項)。變量x在表達式中已被綁定。
(M N) 應用 將函數應用於參數。 M 和 N 是 lambda 項。

產生了諸如:(λx.λy.(λz.(λx.zx)(λy.zy))(x y)的表達式。如果表達式是明確而沒有歧義的,則括號可以省略。對於某些應用,其中可能包括了邏輯和數學的常量以及相關操作。

本文讨论的是邱奇的“无类型lambda演算”,此后,已经研究出来了一些有类型lambda演算

历史[编辑]

最开始,邱奇试图创制一套完整的形式系统作为数学的基础,当他发现这个系统易受罗素悖论的影响时,就把lambda演算单独分离出来,用于研究可计算性,最终导致了他对判定性问题的否定回答。

非形式化的直覺描述[编辑]

在λ演算中,每个表达式都代表一个函数,这个函数有一个参数,并且會返回一个值。不论是参数和返回值,也都是一个单参的函数。可以这么说,λ演算中只有一种“类型”,那就是这种单参函数。函数是通过λ表达式匿名地定义的,这个表达式说明了此函数将对其参数进行什么操作。

例如,“加2”函数f(x)= x + 2可以用lambda演算表示为λx.x + 2(或者λy.y + 2,参数的取名无关紧要),而f(3)的值可以写作(λx.x + 2) 3。函数的应用(application)是左结合的: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表达式,就得到了组合子逻辑

動機[编辑]

在數學和計算機科學中,「可計算的」函式是基礎觀念。對於所謂的可計算性,λ-演算提供了一個簡單明確的語義,使計算的性質可以被形式化研究。λ-演算結合了兩種簡化方式,使得這個語義變得簡單。第一種簡化是不給予函式一個確定名稱,而“匿名”地對待它們。例如,兩數的平方和函式

可以用匿名的形式重新寫為:

(理解成一包含xy的數組被映射到

同樣地,

可以用匿名的形式重新寫為:

(即輸入是直接對應到它本身。)

第二個簡化是λ演算只使用單一個參數輸入的函數。如果普通函數需要兩個參數,例如函數,可轉成接受單一參數,傳給另一個函數中介,而中介函數也只接受一個參數,最後輸出結果。例如,

可以重新寫成:

這是稱為柯里化的方法,將多參數的函數轉換成為多個中介函數的複合鏈,每個中介函數都只接受一個參數。 將函數應用於參數(5,2),直接產生結果

,

而對於柯里化轉換版的評估,需要再多一步:

//在內層表達式中的定義為,這就像β-歸約一樣。
//的定義為,再次如同β-歸約。

得出相同結果。

lambda演算[编辑]

lambda演算是由特定形式語法所組成的一種語言,一組轉換規則可操作其中的lambda項。這些轉換規則被看作是一個等式理論或者一個操作定義。如上節所述,lambda演算中的所有函數都是匿名的,它們沒有名稱,它們只接受一個輸入變量,柯里化用於實現有多個輸入變量的函數。

Lambda項[编辑]

lambda演算的語法將一些表達式定義為有效的lambda演算式,而某一些表達式無效,就像C編程語言中有些字串有效,有些則不是。有效的lambda演算式稱為“lambda項”。

以下三個規則給出了語法上有效的lambda項,如何建構的歸納定義:

  • 變量本身就是一個有效的lambda項
  • 如果是一個lambda項,而是一個變量,則 是一個lambda項(稱為lambda抽象);
  • 如果是lambda項,那麼是一個lambda項(稱為應用)。

其它的都不是lambda項。因此,lambda項若且唯若可重複應用這三個規則取得時,才是有效的。一些括號根據某些規則可以省略。例如,最外面的括號通常不會寫入。

“lambda抽象”是指一個匿名函數的定義,它將單一輸入的替換成的表達式,所以產生了一個匿名函數,它採用的值並返回。例如,是表示使用函數作為項的一個lambda抽象。lambda抽象只是先“設置”了函數定義,還沒使用它。這個抽象在項中綁定了變量。一個應用表示將函數應用在輸入,亦即對輸入使用函數產生

lambda演算中並沒有變量聲明的概念。如(即)的定義中,lambda演算將當作尚未定義的變量。lambda抽象在語法上是有效的,並表示將其輸入添加到未知的函數。

可用圓括弧對來消除歧義。例如,表示不同的項(儘管它們剛好化簡到相同值)。這裡第一個例子定義了一個包含子函數的抽象,並將子函數應用於x(先應用後傳回)的結果;而第二個例子定義了一個傳回任何輸入的函數,然後在應用過程中傳回對輸入為x的應用(返回函數然後應用)。

操作函數的函數[编辑]

在lambda演算中,函數被認為是第一類物件,因此函數可以當作輸入,或作為其它函數的輸出返回。

例如,表示映射到本身的函數,表示將這個函數應用於。此外,則表示無論輸入為何,始終返回值的常數函數。lambda演算中的函數應用是左結合的,因此表示

有幾個“等價”和“化簡”的概念,允許將各個lambda項“縮減”為“相同”的lambda項。

-等價[编辑]

對於lambda項,等價的基本形式定義,是-等價。它捕捉了直覺概念,在lambda抽象中一個綁定變量的特別選擇(通常)並不重要。 比如,-等價的lambda項,它們都表示相同的函數(自映射函數);但如項則不是-等價的,因為它們並非以lambda抽象方式綁定的。 在許多演示中,通常會確定-等價的lambda項。

為了能夠定義-歸約,需要以下定義:

自由變量[编辑]

所謂的自由變量是那些在lambda抽象不受到綁定的變量。表達式中的一組自由變量定義歸納如下:

  • 的自由變量就只是
  • 的自由變量集合,是在中移除了的自由變量集合。
  • 的自由變量是的一組自由變量,與的一組自由變量,這兩項變量的並集。

例如,代表映射自身的,其中的lambda項沒有自由變量,但是在函數中的lambda項,有一個自由變量

避免捕獲的替換記法[编辑]

假設是lambda項,而是變量。如果寫成是一種避免被捕獲的記法方式,表示在這個lambda項中,以來替換變量的值。這定義為:

  • ,如果
  • 如果而且不在lambda項的自由變量中,則。對於lambda項,變量被稱為是“新鮮”的。

例如,

新鮮度條件(要求不在lambda項中的自由變量中)對於確保替換不會改變函數的意義很重要。例如,忽視新鮮度條件的替代:。此替換會將原本意義為常量函數的,轉換成意義為映射自身函數的

一般來說,在無法滿足新鮮度條件的情況,可利用-重新命名使用一個合適的新變量來補救,切換回正確的替換概念;比如在中,使用一個新變量重新命名這個lambda抽象,獲取,則替換就能保留原本函數的義涵。

-歸約[编辑]

β-歸約規定了形式如的應用,可以化簡成項。符號記法用於表示 經過β-歸約轉換為。例如,對於每個,可轉換為。這表明實際上的應用是映射自身函數。同樣地,,表明了是一個常量函數。

lambda演算可視為函數式編程語言的理想化版本,如HaskellML語言。在這種觀點下,β-歸約對應於一組計算步驟。 這個步驟重複應用β-轉換,一直到沒有東西能再被化簡。在無型別lambda演算中,如本文所述,這個歸約過程可能無法終止, 比如,是個特殊的lambda項。這裡 也就是說,該lambda項在一次β-歸約中化簡到本身,因此歸約過程將永遠不會終止。

無型別lambda演算的另一方面是它並不區分不同種類的資料。例如,需要編寫只針對數字操作的功能。然而,在無型別的lambda演算中,沒有辦法避免函數被應用於真值、字串或其它非數字物件。

形式化定义[编辑]

形式化地,我们从一个标识符(identifier)的可数无穷集合开始,比如{a, b, c, ..., x, y, z, x1, x2, ...},则所有的lambda表达式可以通过下述以BNF范式表达的上下文无关文法描述:

  1. <表达式> ::= <标识符>
  2. <表达式> ::= (λ<标识符>.<表达式>)
  3. <表达式> ::= (<表达式> <表达式>)

头两条规则用来生成函数,而第三条描述了函数是如何作用在参数上的。通常,lambda抽象(规则2)和函数作用(规则3)中的括弧在不会产生歧义的情况下可以省略。如下假定保证了不会产生歧义:(1)函数的作用是左结合的,和(2)lambda操作符被绑定到它后面的整个表达式。例如,表达式 (λx.x x)(λy.y) 可以简写成λ(x.x x) λy.y 。

类似λx.(x y)这样的lambda表达式并未定义一个函数,因为变量y的出现是自由的,即它并没有被绑定到表达式中的任何一个λ上。一个lambda表达式的自由变量的集合是通过下述规则(基于lambda表达式的结构归纳地)定义的:

  1. 在表达式V中,V是变量,则这个表达式里自由变量的集合只有V。
  2. 在表达式λV .E中(V是变量,E是另一个表达式),自由变量的集合是E中自由变量的集合减去变量V。因而,E中那些V被称为绑定在λ上。
  3. 在表达式 (E E')中,自由变量的集合是E和E'中自由变量集合的并集。

例,对于表达式λx.x(我们将第一个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-归约规则”。

歸約[编辑]

歸約的操作包括:

操作 名稱 描述
(λx.M[x]) → (λy.M[y]) α-轉換 重新命名表達式中的綁定(形式)變量。用於避免名稱衝突。
((λx.M) E) → (M[x:=E]) β-歸約 在抽象化的函數定義體中,以參數表達式代替綁定變量。

α-变换[编辑]

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-变换可以令λx .f x和f相互转换,只要x不是f中的自由出现。下面说明了为何这条规则和外延性是等价的:

若f与g外延地等价,即,f a == g a对所有的lambda表达式a成立,则当取a为在f中不是自由出现的变量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演算法可用於建構布爾值,算術,資料結構和遞歸的模型,如以下各小節所述。

lambda演算中的算術[编辑]

在lambda演算中有许多方式都可以定义自然数,但最常见的还是邱奇数,下面是它们的定义:

0 = λf.λx.x
1 = λf.λx.f x
2 = λ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的前驱元(predecessesor)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

注意(g 1)(λu.PLUS(g k) 1) k表示的是,当g(1)是零时,表达式的值是k,否则是g(k)+ 1

逻辑与谓词[编辑]

习惯上,下述两个定义(称为邱奇布尔值)被用作TRUEFALSE这样的布尔值:

TRUE := λx.λy.x
FALSE := λx.λy.y
(注意FALSE等价于前面定义邱奇数零)

接着,通过这两个λ-项,我们可以定义一些逻辑运算

AND := λp q.p q FALSE
OR := λp q.p TRUE q
NOT := λp.p FALSE TRUE
IFTHENELSE := λ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

运用谓词与上述TRUEFALSE的定义,使得"if-then-else"这类语句很容易用lambda演算写出。

有序对[编辑]

有序对(2-元组)数据类型可以用TRUEFALSEIF来定义。

CONS := λx y.λp.IF p x y
CAR := λx.x TRUE
CDR := λx.x FALSE

链表数据类型可以定义为,要么是为空列表保留的值(e.g.FALSE),要么是CONS一个元素和一个更小的列表。

附加的編程技術[编辑]

lambda演算出現在相當大量的編程習慣用法中,其中許多編程語言最初以lambda演算作為語義基礎,在此背景下開發的;有效地利用lambda演算作為基底。因為幾個編程語言部份含括了lambda演算(或者非常相似的東西),所以這些技術也可以在實際的編程中見到,但有可能被認為是模糊或外來的。

命名常數[编辑]

在lambda演算中,函式庫將採用預先定義好的函數集合,其中lambda項僅僅是特定的常量。純粹的lambda演算法並不具有命名常數的概念,因為所有的原子λ項都是變量;但是在程序主體中,我們可將一個變量當成常量的名稱,利用lambda抽象把這個變量綁定,並將該lambda抽象應用於預期的定義,來模擬命名常量的作法。因此在N(“主程序”的另一個lambda項)中,要以f來表示M(一些明確的lambda項),則寫成如下:

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,要么函数fn-1的n次应用。使用ISZERO谓词,和上面描述的布尔和代数定义,函数g可以用lambda演算来定义。

但是,g自身仍然不是递归的;为了使用g来建立递归函数,作为参数传递给gf函数必须有特殊的性质。也就是说,作为参数传递的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 gg的不动点,因为它展开为g(Y g)。现在,要完成我们对阶乘函数的递归调用,我们可以简单的调用 g(Y g)n,这裡的n是我们要计算它的阶乘的数。

比如假定n = 5,它展开为:

(λn.(if n = 0 then 1 else n·((Y g)(n-1)))) 5
if 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 := λxy.x
S := λxyz.x z (y z)
B := λxyz.x (y z)
C := λxyz.x z y
W := λxy.x y y
U := λxy.y (x x y)
ω := λx.x x
Ω := ω ω
Y := λg.(λx.g (x x)) (λx.g (x x))

其中有幾個在“消除lambda抽象”中有直接的應用,將lambda項變為組合演算的術語。

消除lambda抽象[编辑]

如果N是一個沒有λ-抽象的lambda項,但可能包含了命名常量(組合子),則存在一個lambda項T(x,N),這相同於一個缺少λ-抽象(除了作為命名常量的一部份,如果這些被認為是非原子的)的λ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可藉由使初始的組合子IKS獲取參數P而化簡, 就像x.N) P經過β-歸約一樣。I返回那個參數。K則將參數拋棄,就像x.N),如果xN中不是以自由變量出現。S將參數傳遞給應用程序的兩個子句,然後將第一個結果應用到第二個的結果之上。

組合子BC類似於S,但把參數傳遞給應用的一個子項(B傳給“參數”子項,而C傳給“函數”子項),如果子項中沒有出現x,則保存後續的K。與BC相比,S組合子實際上混合了兩個功能: 重新排列參數,並複製一個參數,以便它可以在兩個地方使用。W組合子只做後者,產生了SKI组合子演算的B,C,K,W系統。

可计算函数和lambda演算[编辑]

自然数的函数F: NN可计算函数当且仅当存在着一个lambda表达式f,使得对于N中的每对x, y都有F(x) = y当且仅当f x == y,这裡的xy分别是对应于x和y的邱奇数。这是定义可计算性的多种方式之一;关于其他方式和它们的等价者的讨论请参见邱奇-图灵论题

lambda演算與編程語言[编辑]

匿名函數[编辑]

化簡策略[编辑]

關於複雜度的註釋[编辑]

並行與並發[编辑]

参见[编辑]

外部連結[编辑]