计算之美——奇妙的λ演算

此篇文章可能会给你带来些许的不适,出现 烦躁, 头疼 均属正常情况。阅读前,请保证处于头脑清醒的状态 先来看一段函数 factorial

此篇文章可能会给你带来些许的不适,出现 烦躁, 头疼 均属正常情况。阅读前,请保证处于头脑清醒的状态

先来看一段函数

factorial = (lambda f: f(f))(

lambda f: (lambda n:

1 if n == 0 else

n * f(f)(n - 1)))

先来想想我们如果用递归来计算阶乘会怎么写

def factorial(n):

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

递归需要调用自身,那我们就需要明确自身是什么。比如这里我们使用了 factorial 这个函数名。那么如果我们非要使用匿名函数进行递归的话,我们该怎么做呢?

引入第一个概念 λ演算

在λ演算中,每个表达式都代表一个函数,这个函数有一个参数,并且返回一个值。不论是参数和返回值,也都是一个单参的函数。可以这么说,λ演算中,只有一种“类型”,那就是这种单参函数。

比如 f(x)=x+2

可以用λ演算表示为 λx.x + 2

。对于 3+2

我们这样来求值 (λx.x + 2) 3

。我们还可以将函数作为参数 (λf.f 3)(λx.x + 2)

对于多个参数的函数通过柯里化来解决

简言之是将一个具有多个参数的函数,转换成一系列的函数链式调用

def power(x):

return lambda n: x **n

power_of_2 = power(2)

看到这里也许你想到了偏函数

from functools import partial

def power(x, n):

return x ** n

power_of_2 = partial(power,2)

power_of_2(10)

偏函数是用特定的值来具体化参数,而柯里化则是变成了一条函数链。

说的更通俗一点就是偏函数可以固定参数 n ,而柯里化不能,因为这条链是有顺序的

让我们回到λ演算中来,并非所有的λ表达式都可以规约至确定值,考虑 (λ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,以此类推。

好吧,你不觉得这个 (λx.x x) 似曾相识么?

这个用 Python 写出来是这样的 lambda f: f(f)

,如果还记不起来请往上滑

试着将一个匿名函数作为参数传入

lambda f: (lambda n:

1 if n == 0 else

n * f(f)(n - 1))

返回了内层的 lambda 函数,并且由于闭包的性质,携带了 f 即匿名函数自身,这样我们就完成了对匿名函数的递归。

好了,是不是觉得很神奇?

我们再来看点专业点的解释,引自 wiki

递归是使用函数自身的函数定义;在表面上,lambda演算不允许这样。但是这种印象是误解。考虑个例子,阶乘函数f(n)递归的定义为

f(n):= if n = 0 then 1 else n·f(n-1)

在λ演算中,你不能定义包含自身的函数。要避免这样,你可以开始于定义一个函数,这里叫g,它接受一个函数f作为参数并返回接受n作为参数的另一个函数:

g := λf n.(if n = 0 then 1 else n·f(n-1))

函数g返回要么常量1,要么函数f对n-1的n次应用。使用ISZERO谓词,和上面描述的布尔和代数定义,函数g可以用lambda演算来定义。

但是,g自身仍然不是递归的;为了使用g来建立递归函数,作为参数传递给g的f函数必须有特殊的性质。也就是说,作为参数传递的f函数必须展开为调用带有一个参数的函数g,并且这个参数必须再次为f函数!

换句话说,f必须展开为g(f)。这个到g的调用将接着展开为上面的阶乘函数并计算下至另一层递归。在这个展开中函数f将再次出现,并将被再次展开为g(f)并继续递归。这种函数,这里的 f = g(f),叫做g的不动点,并且它可以在λ演算中使用叫做悖论算子或不动点算子来实现,它被表示为 Y 组合子:

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

对于 Y 组合子而言 Y g 等价于 g(Y g), 要推出这个还需要了解三条归约,概括如下

  • α-变换 变量的名称是不重要的,比如说λx.x和λy.y是同一个函数
  • β-归约 只允许从左至右来代入参数
  • η-变换

    两个函数对于所有的参数得到的结果都一致,当且仅当它们是同一个函数

推导过程如下

(Y g)

(λf.(λx.(f (x x)) λx.(f (x x))) g)

;(λf的β-归约 - 应用主函数于g)

(λx.(g (x x)) λx.(g (x x)))

;(α-转换 - 重命名约束变量)

(λy.(g (y y)) λx.(g (x x)))

;(λy的β-归约 - 应用左侧函数于右侧函数)

(g (λx.(g (x x)) λx.(g (x x))))

(g (Y g))

现在让我们改进一开始的例子,说实话用 Python 写这种代码挺费劲的

(lambda f:(

lambda n:(

1 if n == 0 else n * f(f)(n - 1))))

令 g=f(f)

(lambda f:(

lambda g:(

lambda n:(

1 if n == 0 else n * g(n - 1))

)(f(f))))

我们可以看到

lambda g:

lambda n:

1 if n == 0 else n * g(n - 1)

这一部分已经变得完美了,将这一部分再提取出来成为 f0

(lambda f0:(

lambda f:(

f0)(

f(f)))

)(lambda g:

lambda n:

1 if n == 0 else n * g(n - 1))

让我们来试试

factorial = (lambda f:

f(f))(

(lambda f0:(

lambda f:(

f0)(

f(f)))

)(lambda g:

lambda n:

1 if n == 0 else n * g(n - 1)))

factorial(10)

,,Ծ‸Ծ,, 栈溢出了, 什么鬼?

因为我们执行到这里

lambda f:(

f0)(

f(f))

对 f(f) 进行求值再应用于 f0 时,会陷入无穷。可以通过 η-变换 来解决

factorial = (lambda f:

f(f))(

(lambda f0:(

lambda f:(

f0)(

lambda s: f(f)(s)))

)(lambda g:

lambda n:

1 if n == 0 else n * g(n - 1)))

再进一步抽象

factorial = (lambda y:(

lambda f:

f(f))(

(lambda f0:(

lambda f:(

f0)(

lambda s: f(f)(s)))

)(y)))(

lambda g:

lambda n:

1 if n == 0 else n * g(n - 1))

大功告成, 这个就是 Y 了

(lambda y:(

lambda f:

f(f))(

(lambda f0:(

lambda f:(

f0)(

lambda s: f(f)(s)))

)(y)))

Reference

λ演算

不动点组合子

函数式编程的 Y Combinator 有哪些实用价值?

未登录用户
全部评论0
到底啦