另发表于知乎。


作为FP的基础,Lambda 演算将一切视为函数,对函数进行演算。

Lambda 演算本是 Church 为解释停机问题而提出,与 Turing 的解释并列。


Lambda-Calculus

Lambda 演算用三个语法构建合法的表达式。

语法解释
x\tt x一个对象,可以替换为任何字母。
λx.(   )\tt \lambda x.(\ \ \ )一个以 x\tt x 为变量的函数,括号作为返回值。
(   )(   )\tt (\ \ \ )(\ \ \ )将左侧括号视为函数,右侧括号视为变量,进行一次应用。

括号可以替换为三个语法之一。一个合法例子是 λa.(λb.(ab))\tt \lambda a.(\lambda b.(ab)) 。

Lambda 演算中最基本的对象是恒等函数 λx.x\tt \lambda x.x 。

Beta-Reduction

通过 Beta 归约可以进行表达式求值。

例如,对于一个表达式 (λx.(λy.(xy)))a\tt (\lambda x.(\lambda y.(xy)))a ,即将 a\tt a 应用于函数
λx.(λy.(xy))\tt \lambda x.(\lambda y.(xy)) ,对它进行 Beta 归约的步骤如下:

  1. 函数以 x\tt x 为变量,而 x\tt x 的值为 a\tt a 。
  2. 只保留表达式中的函数体 λy.(xy)\tt \lambda y.(xy) 。
  3. 将 x\tt x 替换为 a\tt a ,即为 λy.(ay)\tt \lambda y.(ay) 。

由此完成了一次 Beta 归约,得到了新函数 λy.(ay)\tt \lambda y.(ay) 。这个新函数接受一个 y\tt y 为变量,返回 y\tt y 应用于 a\tt a 的结果。

为了让函数接受多个参数,可以应用 Currying 思想。形式上,可以这样定义加法函数(事实上,由于我们还没有定义什么是“整数”,无法给出加法定义。关于加法的合法定义见整数。):

PLUS:=λx.(λy.(x+y))\tt PLUS := \lambda x.(\lambda y.(x + y))

计算 3+5\tt 3+5 的值,需要计算 (PLUS 3)5\tt (PLUS\ 3)5 ,也即 ((λx.(λy.(x+y)))3)5\tt ((\lambda x.(\lambda y.(x + y)))3)5 ,要进行两次 Beta 归约:

  • 第一次 Beta 归约:化简 (λx.(λy.(x+y)))3\tt (\lambda x.(\lambda y.(x + y)))3 。

    1. 函数以 x\tt x 为变量,而 x\tt x 的值为 3\tt 3 。
    2. 只保留表达式中的函数体 λy.(x+y)\tt \lambda y.(x + y) 。
    3. 将 x\tt x 替换为 3\tt 3 ,即为 λy.(3+y)\tt \lambda y.(3 + y) 。
  • 第二次 Beta 归约:化简 (λy.(3+y))5\tt (\lambda y.(3 + y))5 。

    1. 函数以 y\tt y 为变量,而 y\tt y 的值为 5\tt 5 。
    2. 只保留表达式中的函数体 3+y\tt 3 + y 。
    3. 将 y\tt y 替换为 5\tt 5 ,即为 3+5\tt 3 + 5 。

Boole 逻辑

Lambda 演算中,TRUE\tt TRUE 和 FALSE\tt FALSE 定义为接受两个参数的参数选择器:

TRUE:=λx.(λy.x)\tt TRUE := \lambda x.(\lambda y.x)
FALSE:=λx.(λy.y)\tt FALSE := \lambda x.(\lambda y.y)

TRUE\tt TRUE 选择第一个参数,FALSE\tt FALSE 选择第二个参数。

例如,对 (TRUE a)b\tt (TRUE\ a)b 进行 Beta 规约:

  1. 先展开:((λx.(λy.x))a)b\tt ((\lambda x.(\lambda y.x))a)b 。
  2. 代入 a\tt a : (λy.a)b\tt (\lambda y.a)b 。
  3. 代入 b\tt b : a\tt a ,确实选择了第一个参数。

可以实现 Boole 运算:

函数解释
NOT:=λa.((a FALSE)TRUE)\tt NOT := \lambda a.((a\ FALSE)TRUE)非:当 a\tt a 为 TRUE\tt TRUE 时,选择 FALSE\tt FALSE,否则选择 TRUE\tt TRUE 。
AND:=λa.(λb.((a b)FALSE))\tt AND := \lambda a.(\lambda b.((a\ b)FALSE))与:当 a\tt a 为 TRUE\tt TRUE 时,选择 b\tt b,否则选择 FALSE\tt FALSE 。
OR:=λa.(λb.((a TRUE)b))\tt OR := \lambda a.(\lambda b.((a\ TRUE)b))或:当 a\tt a 为 TRUE\tt TRUE 时,选择 TRUE\tt TRUE,否则选择 b\tt b 。

这些 Boole 运算可以得到 TRUE\tt TRUE 或 FALSE\tt FALSE ,以用来选择其他变量。

整数

Lambda 演算将整数视作函数。函数接受两个参数,一个是 f\tt f ,一个是 x\tt x 。整数将 x\tt x 作为变量应用于 f\tt f 多次,应用次数即为整数值:

0:=λf.(λx.x)\tt 0 := \lambda f. (\lambda x.x)
1:=λf.(λx.(fx))\tt 1 := \lambda f. (\lambda x.(fx))
2:=λf.(λx.(f(fx)))\tt 2 := \lambda f. (\lambda x.(f(fx)))
3:=λf.(λx.(f(f(fx))))\tt 3 := \lambda f. (\lambda x.(f(f(fx))))
…\tt …

这样定义的好处之一是,可以方便地定义加法,但是先让我们定义后继:

SUCC:=λn.(λf.(λx.((nf)x)))\tt SUCC := \lambda n.(\lambda f.(\lambda x.((nf)x)))

将 n\tt n 传入 SUCC\tt SUCC 后,得到的函数 n+1\tt n + 1 次将 x\tt x 应用于 f\tt f ,即得到了 n+1n + 1。因此,自然地得到加法:

ADD:=λa.(λb.((a SUCC)b))\tt ADD := \lambda a.(\lambda b.((a\ SUCC)b))

乘法(例如 a∗b\tt a * b )有更容易理解的定义,因为它相当于将 b\tt b 应用 a\tt a 次:

MUL:=λa.(λb.(λf.(a(bf))))\tt MUL := \lambda a.(\lambda b.(\lambda f.(a(bf))))

幂的定义比较紧凑:

POW:=λa.(λb.(ba))\tt POW := \lambda a.(\lambda b.(ba))

它表示将 a\tt a 复合 b\tt b 次,例如,计算 (POW 2)3\tt (POW\ 2) 3 :

  1. 代入 POW\tt POW : 3 2\tt 3\ 2 。
  2. 代入 3\tt 3 和 2\tt 2 : (λa.(λb.(a(a(ab)))))(λc.(λd.(c(cd))))\tt (\lambda a. (\lambda b.(a(a(ab)))))(\lambda c. (\lambda d.(c(cd)))) 。
  3. 归约:λb.((λg.(λh.(g(gh))))((λe.(λf.(e(ef))))(λd.(b(bd)))))\tt \lambda b.(\textcolor{red}{(\lambda g. (\lambda h.(g(gh))))}(\textcolor{orange}{(\lambda e. (\lambda f.(e(ef))))}\textcolor{blue}{(\lambda d.(b(bd)))})) 。
  4. 归约:λb.((λg.(λh.(g(gh))))(λf.((λd.(b(bd)))(b(bf)))))\tt \lambda b.(\textcolor{red}{(\lambda g. (\lambda h.(g(gh))))}\textcolor{orange}{(\lambda f.(\textcolor{blue}{(\lambda d.(b(bd)))}(b(bf))))}) 。
  5. 归约:λb.((λg.(λh.(g(gh))))(λf.(b(b(b(bf))))))\tt \lambda b.(\textcolor{red}{(\lambda g. (\lambda h.(g(gh))))}\textcolor{orange}{(\lambda f.(b(b(b(bf)))))}) 。
  6. 归约:λb.(λh.((λf.(b(b(b(bf)))))(b(b(b(bh))))))\tt \lambda b.(\textcolor{red}{\lambda h.(\textcolor{orange}{(\lambda f.(b(b(b(bf)))))}(b(b(b(bh)))))}) 。
  7. 归约:λb.(λh.(b(b(b(b(b(b(b(bh)))))))))\tt \lambda b.(\lambda h.(b(b(b(b(b(b(b(bh))))))))) 。
  8. 变量重命名:λf.(λx.(f(f(f(f(f(f(f(fx)))))))))\tt \lambda f.(\lambda x.(f(f(f(f(f(f(f(fx))))))))) 。

可见 (POW 2)3=8\tt (POW\ 2) 3 = 8 。

递归与 Turing 不动点组合子

可以采用递归的形式表达阶乘函数:

python
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

假设我们有了一个可以判断变量是否为 0\tt 0 的函数 IS_ZERO\tt IS\_ZERO ,形式上,阶乘函数应该写为:

FAC=λn.(((IS_ZERO n)1)((×n)(FAC((−n)1))))\tt FAC = \lambda n.(((IS\_ZERO\ n)1)((\times n)(FAC((-n)1))))

但是这是不合法的,包含了递归调用。

为此,引入 Turing 不动点组合子 Θ\tt \Theta:

Θ:=UU\tt \Theta := UU

其中:

U=λx.(λy.(y((xx)y)))\tt U = \lambda x.(\lambda y.(y((xx)y)))

假设有一函数 F\tt F ,计算 ΘF\tt \Theta F :

  1. 代入 Θ\tt \Theta :(UU)F\tt (UU)F 。
  2. 代入一个 U\tt U :((λx.(λy.(y((xx)y))))U)F\tt ((\lambda x.(\lambda y.(y((xx)y))))U)F 。
  3. 归约:(λy.(y((UU)y)))F\tt (\lambda y.(y((UU)y)))F 。
  4. 归约:F((UU)F)\tt F((UU)F) 。
  5. 用 Θ\tt \Theta 替换 UU\tt UU :F(ΘF)\tt F(\Theta F) 。

由此可见,ΘF\tt \Theta F 是 F\tt F 的不动点。

现在,考虑一个函数:

F:=λf.(λn.(((IS_ZERO n)1)((×n)(f((−n)1)))))\tt F := \lambda f.(\lambda n.(((IS\_ZERO\ n)1)((\times n)(f((-n)1)))))

将 Θ\tt \Theta 作用于 F\tt F :

ΘF=F(ΘF)=λn.(((IS_ZERO n)1)((×n)((ΘF(−n)1))))\tt \Theta F = F(\Theta F) = \lambda n.(((IS\_ZERO\ n)1)((\times n)((\Theta F(-n)1))))

可见 ΘF\tt \Theta F 就是阶乘函数。


Lambda 演算的理论意义在于为 Lisp、Haskell 等语言提供理论基础,闭包也在很多编程语言中出现,Python 中也有lambda匿名函数。