笔记仓库

正常人的正常笔记集

Y分钟入门lambda演算

本文为我个人对Learn X in Y minutes系列的Lambda Calculus部分内容的中文翻译。非常推荐有能力的读者直接去阅读原文。

包含部分译者添加的细节补充


最初由Alonzo Church创造的lambda演算(λ-演算)是世界上最小的程序设计语言。虽然没有数(number),字符串(string),布尔型(boolean)或其他任何非函数(non-function)的数据类型,但lambda演算能用于表示任何图灵机。

lambda演算由3个元素组成:变量函数,和 应用

名称 语法 例子 解释
变量 <name> $x$ 一个名为$x$的变量
函数 λ<parameters>.<body> $\lambda x.x$ 一个形参为$x$主体为$x$的函数
应用 <function><variable or function> $(\lambda x.x)a$ 以实参$a$调用函数$(λx.x)$

最基本的函数是恒等函数:$\lambda x.x$,等同于$f(x)=x$,第一个$x$是函数的参数,第二个是函数体。

自由 vs. 约束变量:

  • 在函数$\lambda x.x$中$x$被称为约束变量,$x$被称为约束变量,因为它既在函数体中又是形参。
  • 在$\lambda x.y$中$y$被称为自由变量,因为它没有被预先声明。

求值:

求值通过β化简(β-Reduction)完成,本质上是词法作用域的替换。

当对表达式$(\lambda x.x)a$求值时,我们把函数体中所有出现的$x$都替换为$a$。

  • $(\lambda x.x)a$求值结果为: $a$
  • $(\lambda x.y)a$求值结果为: $y$

你甚至可以创造高阶函数:

  • $(\lambda x.(\lambda y.x))a$求值结果为:$λy.a$

虽然lambda演算传统上只支持单参数函数,但我们可以用一种被称为柯里化(currying)的技巧来创造多参数函数。

  • $(\lambda x.\lambda y.\lambda z.xyz)$等同于$f(x,y,z) = ((x\, y)\, z)$

有时$\lambda xy.$也可以与$\lambda x.\lambda y.$在用法上互换。


必须意识到传统的lambda演算没有数,字符,或任何非函数的数据类型!

布尔逻辑:

在lambda演算中没有True或False,甚至没有1或0。

而是有:

$T$ 表示为:$\lambda x.\lambda y.x$

$F$ 表示为:$\lambda x.\lambda y.y$

首先,我们定义一个if函数 $\lambda btf$,如果 $b$ 为True返回 $t$ ,如果 $b$ 为False返回$f$

IF等价于 $\lambda b.\lambda t.\lambda f.b \, t \, f$

译者注

在理论上这样的做法在该演算系统没有问题,但实践中的if语句if a then b else c要求bc有且只有一个被求值,在严格求值的语言(如Scheme)中不可以通过定义普通的函数(lambda表达式)来实现真正的if语句,否则bc都会被求值,需要通过宏或其他方法来改变求值行为。

使用IF,我们可以定义基本布尔逻辑运算符:

$a \, \text{AND} \, b$ 等价于 $\lambda ab.IF\, a \,b \,F$

$a \, \text{OR} \, b$ 等价于 $\lambda ab.IF \,a \,T \,b$

$a \, \text{NOT} \, b $ 等价于 $\lambda a.IF\, a\, F\, T$

注意:$IF\, a \, b \, c$ 实质上是在说 $IF((a \, b) \, c)$

译者注

NOT是一元运算符,我怀疑这里原文写错了,应该是NOT a,当然后面lambda演算表达式是正确的。我已向该项目提交相应的issue等待回应。

数:

虽然lambda演算没有数字,但我们可以用Church数来对数字编码。

对于任意数n:$n = \lambda f.{f^n}$ 所以有

$ 0 = \lambda f.\lambda x.x $

$ 1 = \lambda f.\lambda x.f\,x $

$ 2 = \lambda f.\lambda x.f(f\, x) $

$ 3 = \lambda f.\lambda x.f(f(f\, x)) $

为了增加一个Church数,我们用后继函数(successor function)$S(n)=n+1$ 即:

$S = \lambda n.\lambda f.\lambda x.f((n\,f)\,x)$

使用后继,我们可以定义加法:

$ADD = \lambda ab.(a \, S)b$

挑战: 试着自己定义乘法函数

译者注

写完或者根本想不出来可以参考http://www.cse.unt.edu/~tarau/teaching/PL/docs/Church%20encoding.pdf Section 1.1定义的mult函数,我就不直接写出来干扰思考了。

变得甚至更小:SKI, SK与Iota

译者注

想快速入门lambda演算的看到这里已经足够,可以直接根据更多进阶阅读材料的前三条参考链接开始进一步学习。而从这里开始和lambda演算的关系已经不是很大了,只是通过一系列化简计算来把它用“更小”的演算系统表示,假设用$A \to B$表示$A$语言的所有要素都可以用$B$语言来表示,即$A$可以被规约(化简)到$B$,那么接下来繁复的炫技演示了λ演算$\to$SKI演算$\to$SK演算$\to$ι演算的过程,语言的元素数量逐步减少。关于这些演算系统定义和发展的历史以及它们的关系,除了接下来的内容外,也可以见Wiki词条Combinatory logic

SKI组合子演算

令$S$,$K$和$I$为以下函数:

$I\,x = x$

$K\,x\,y = x$

$S\, x\, y\, z = x\, z\, (y\, z)$

我们可以把lambda演算中的表达式转换为SKI组合子演算中的表达式:

  1. $\lambda x.x = I$
  2. $\lambda x.c = Kc$
  3. $\lambda x.(y\, z) = S\, (λx.y) \,(λx.z)$

以church数2为例:

$ 2 = \lambda f.\lambda x.f(f\, x) $

对于内部的$\lambda x.f(f\, x) $部分:$$\begin{alignat}{2}
& \lambda x.f(f\,x) &\\
= & S \, (\lambda x.f) \, (\lambda x.(f\,x)) & \quad (case\, 3) \\
= & S\, (K\,f) \, (S\, (\lambda x.f) \, (\lambda x.x)) & \quad (case\, 2, 3) \\
= & S\, (K\, f) \, (S \,(K\, f) \,I) \, & \quad (case\, 2, 1)
\end{alignat}$$所以$$\begin{align}
& 2 \\
=& \lambda f.\lambda x.f(f\, x) \\
=& \lambda f.(S \,(K\, f) \,(S\, (K\, f)\, I)) \\
=& \lambda f.((S\, (K\, f)) \,(S \,(K \,f) \,I)) \\
=& S\, (\lambda f.(S \,(K \,f)))\, (\lambda f.(S\, (K \,f) \,I)) \quad (case 3)
\end{align}$$对于第一个参数$\lambda f.(S \, (K\, f))$ $$
\begin{alignat}{2}
& \lambda f.(S \, (K \, f)) \\\
=& S \, (\lambda f.S) \, (\lambda f.(K \, f)) & \quad (case \, 3) \\
=& S \, (K \, S) (S \, (\lambda f.K) \, (\lambda f.f)) &\quad (case \, 2, 3) \\
=& S \, (K \, S) \, (S \, (K \, K) \, I) \quad & (case \, 2, 3)
\end{alignat}$$对于第二个参数$\lambda f.(S \,(K \,f) \, I)$ $$
\begin{alignat}{2}
&\lambda f.(S\, (K \,f) \,I) &\\
=& \lambda f.((S \,(K \,f))\, I) &\\
=& S \,(\lambda f.(S \, (K \, f))) (\lambda f.I) & \quad (case \,3) \\
=& S \,(S\, (\lambda f.S) (\lambda f.(K \,f))) (K \,I) & \quad (case \,2, 3) \\
=& S \,(S \,(K\, S) \,(S\, (\lambda f.K) \,(\lambda f.f))) \,(K\, I) & \quad (case 1, 3) \\
=& S \,(S \,(K \,S)\, (S \,(K \,K)\, I))\, (K\, I) & \quad (case\, 1, 2)
\end{alignat}$$把它们合并起来$$\begin{align}
&2 \\
=& S \,(\lambda f.(S \,(K\, f))) \,(\lambda f.(S \,(K\, f) \,I)) \\
=& S \,(S\, (K\, S)\, (S\, (K \,K) \,I)) \,(S\, (S \,(K \,S) (S\, (K \,K) \,I)) \,(K\, I))
\end{align}$$ 展开它,我们最终会再次得到与Church数2相同的表达式。

SK组合子演算

SKI组合子演算还能被进一步化简,注意到$I=S\,K\,K$我们可以移除$I$组合子。我们把所有$I$替换为$S\,K\,K$

Iota组合子

SK组合子演算依然不是最小的,定义
$\iota = \lambda f.((f \, S) \, K)$
我们有$$
\begin{align}
I & = \iota \iota \\
K & = \iota (\iota I) = \iota (\iota (\iota \iota)) \\
S & = \iota (K) = \iota (\iota (\iota (\iota \iota)))
\end{align}$$

更多进阶阅读材料见

  1. A Tutorial Introduction to the Lambda Calculus
  2. Cornell CS 312 Recitation 26: The Lambda Calculus
  3. Wikipedia - Lambda Calculus
  4. Wikipedia - SKI combinator calculus
  5. Wikipedia - Iota and Jot