λ演算

λ演算,λ(Lambda(大写Λ,小写λ)读音:lan b(m) da(兰亩达)['læ;mdə])演算是一套用于研究函数定义、函数应用和递归的形式系统。它由 Alonzo Church 和 Stephen Cole Kleene 在 20 世纪三十年代引入,Church 运用 lambda 演算在 1936 年给出 判定性问题 (Entscheidungsproblem) 的一个否定的答案。这种演算可以用来清晰地定义什么是一个可计算函数。关于两个 lambda 演算表达式是否等价的命题无法通过一个通用的算法来解决,这是不可判定性能够证明的头一个问题,甚至还在停机问题之先。

λ 演算可以被称为最小的通用欠肯备程序设计语言。它包括一条变换规则 (变量替换) 和一条函数定义方式,λ演算之通用在于,任何一个可计算函数都能用这种形式来表达和求值。因而,它是等价于图灵机的。尽管如此,λ演算强调的是变换规则的运用,而非实现它们的具体机器。可以认为这是一种更接近软件而非硬件的方式。它一个数理逻辑形式系统,使用变量代入和置换来研究基于函数定义和应用的计算。希腊字母λ被用来在λ演算模型中表示将一个变量绑定在一个函数中。

λ演算可以是有类型的也可以是无类型的,仅仅当输入的的数据类型对于有类型的λ演算函数来说是可以接受的时,有类型的λ演算函数才能被使用。λ演算模型在数学,物理学,语言学和计算机科学等不同领域有着广泛的应用。它在编程语言的理论发展上起到了很重要的作用,并对函数式编程起到了很大的影响,甚至可以捆元说函数式编程就是对λ演算模型的一种实现。同时,它也是范畴论的当前研究对象之一。

λ演算模型最初的形式系统在1935年被 Stephen Kleene 和 J. B. Rosser提出的Kleene–Rosser悖论证明为是前后矛盾的,接着,在1936年,Church单独出版了λ演算模型中的和纯计算有关的部分,也就是如今被称为的无类型λ演算。在1940年,他提出了一个弱化计算,但是逻辑自洽的形式系统,如今被称之为简单类型λ演算。

在20世纪60年代之前,λ演算和编程语言之间的关系被厘兵验再清之前,λ演算模型一直都仅仅是一个理论上的形式系统,多亏了Montague和其他的几位语言学家在自然语言的语义方面的研究,λ演算谅殃匪喇开始在语言学和计算机科学的研究中占有一席拘良遥之地。

在 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 上:λ x. x 3。如果把这个 (用函数作参数的) 函数作用于我们先前的“加 2”函数上:(λ x. x 3) (λ x. x+2),则明显地,下述三个表达式:

(λ x. x 3) (λ x. x+2) 与 (λ x. x + 2) 3 与 3 + 2

是等价的。有两个参数的函数可以通过 lambda 演算这么表达:一个单一参数的函数的返回值又是一个单一参数的函数 (参见 Currying)。例如,函数 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) 被称为 ω 组合子 (combinator),((λ x. x x) (λ x. x x)) 被称为 Ω,而 ((λ x. x x x) (λ x. x x x)) 被称为 Ω2,以此类推。

若仅有形式化函数作用的注记而不允许 lambda 表兆挨照达式,就得到了组合子逻辑 (combinatory logic)。

形式化定义

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

<expr> ::= <identifier>

<expr> ::= (λ <identifier> . <expr>)

<expr> ::= (<expr> <expr>)

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

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

在表达式 V 中,V 是变元,则这个表达式里变元 V 只有一次自由出现。

在表达式 λ V . E 中 (V 是变元,E 是另一个表达式),变元自由出现的次数是 E 中变元自由出现的次数,减去 E 中 V 自由出现的次数。因而,E 中那些 V 被称为绑定在 λ 上。

在表达式 (E E' ) 中,变元自由出现的次数是 E 和 E' 中变元自由出现次数之和。

在 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 表达式被称为范式。并非所有的 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 演算中有许多方式都可以定义自然数,但最常见的还是Church 整数,下面是它们的定义:

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 次幂为返回值的函数。换句话说,Church 整数是一个高阶函数 -- 以单一参数函数 f 为参数,返回另一个单一参数的函数。

(注意在 Church 原来的 lambda 演算中,lambda 表达式的形式参数在函数体中至少出现一次,这使得我们无法像上面那样定义 0) 在 Church 整数定义的基础上,我们可以定义一个后继函数,它以 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 等于在零的基础上 n 次加 m。另一种方式是

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。

逻辑与断言

习惯上,下述两个定义 (称为 Church 布尔值) 被用作 TRUE 和 FALSE 这样的布尔值:

TRUE = λ u. λ v. u

FALSE = λ u. λ v. v

断言是指返回布尔值的函数。最基本的一个断言 ISZERO,当且仅当其参数为零时返回真:

ISZERO = λ n. n (λ x. FALSE) TRUE

断言的运用与上述 TRUE 和 FALSE 的定义,使得 "if-then-else" 这类语句很容易用 lambda 演算写出。

递归

递归是一种以函数自身迭代自身变元的算法,一般是通过函数自身来定义函数的方式实现。表面看来 lambda 演算不允许递归,其实这是一种对递归的误解。考虑阶乘函数 f(n) 一般这样递归地定义:

f(n) = 1, 若 n = 0; n·f(n-1), 若 n>0.

λ语言示例

FACT = λ n. n (λ u. MULT n (FACT (PRED n))) 1

用 Y-组合子 在 λ语言 中合法地定义:

FACT = Y (λ g. λ n. n (λ u. MULT n (g (PRED n))) 1)

Y = λ f. ((λ x. f (x x)) (λ x. f (x x)))

正如Peter Landin1965年在论文 A Correspondence between ALGOL 60 and Church's Lambda-notation中指出的一样,面向过程的程序设计语言在λ演算模型的体系中是可以理解的,因为它提供了基本的过程抽象和程序应用机制。

以Lisp中的乘方函数为例,它可以使用lambda表达式表达为:

(lambda (x) (* x x))

以上是一个可以用作头等函数的例子。在这个表达式中,lambda创造了一个匿名函数并给予了它一个参数列表(x),虽然它只有一个参数,而(* x x)则是函数的主体。这个函数在Haskell中的实现是完全一样的。匿名函数有时候也被叫做lambda表达式。

再举个例子,Pascal和其它的命令式语言 长期以来都支持将通过函数指针的机制来将子程序 作为参数传递到其它子程序里面去。然而,函数指针并不是 函数成为头等函数类型的充分条件,因为一个头等数据类型必须要能够在运行时创建出一个它的实例。而支持运行时创建函数的语言有Smalltalk,Javascript,和最近的Scala,Eiffel,C#和C++11等。

在编程语言的理论研究中,求值策略(Evaluation strategy)是一组用来确定程序设计语言中的表达式求值的规则。求值策略主要规定了在什么时候和用什么样的顺序给函数的实际参数求值,何时把参数代换入函数内,和用怎样的形式来进行代换。通常,人们使用λ演算模型中的归约策略来建模求值策略。

无论一个表达式是否为标准状态,将这个这个表达式化为标准型所需要的工作量很大程度上依赖于归约策略的使用。而归约策略的不同又和函数式编程中的及早求值还有惰性求值之间的不同有关。

1.完全β-归约 (Full β-reduction)

任何参数在任何时候都可以被归约,其实就是没有任何的归约策略,天知道会发生什么。

2.应用次序 (Applicative order)

最右边,最内部的表达式总是首先被归约,直观上可以知道,这意味着函数的参数总是在函数调用之前就被归约了。应用次序总是企图用标准形式去调用函数,即便在很多时候这是不可能的。 大多数的程序设计语言(包括Lisp,ML和命令式语言C和Java等)都被描述为严格类型语言,意思是使用了不正确形式参数的函数是形式不正确的。它们在实际上就是使用了应用次序和传值调用归约,但通常被成为及早求值策略。

3.正常次序 (Normal order) 最左边,最外部的表达式总是首先被归约,这也就意味着无论什么时候,参数都是再被归约之前就被替换进了抽象的函数体里面了。

4.传名调用 (Call by name) 和正常次序一样,但是不会在抽象的函数体中再进行归约,比如说,λx.(λx.x)x在这个策略中是正常形式, 虽然它包含了可归约的表达式(λx.x)x

5.传值调用 只有最外部的表达式被归约:一个表达式仅仅当它的右边已经被规约为一个值了才会被归约

6.传需求调用 “传需求调用”和传名调用类似,如果函数的实参被求值了,这个值就会被存储起来已备未来使用。它产生的结果和传名调用一样;但是如果函数的这个实参被调用了多次,那么传需求调用可以提高程序运行效率。它在现实语境中也被叫做惰性求值。

函数式编程在一开始就是面向并发处理的,这也得益于lambda的性质,lambda演算的Church-Rosser性质意味着归约(β归约)可以以任何顺序进行,甚至是并行来进行。这意味着各种不同的非确定性归约策略都是相近的。然而,lambda演算并不提供任何直接的并行结构。一个人可以添加像Futures结构体这样的并发结构体到lambda演算中去。相关的进程代数已经为了进程通信和并发而被研究了出来。

在λ-演算的基础上,发展起来的π-演算、χ-演算,成为近年来的并发程序的理论工具之一,许多经典的并发程序模型就是以π-演算为框架的。

相关词汇