Last updated on 2020年9月11日 at 下午11:07

本文献给 Alan。至于为什么要用 python 表示,主要是因为 Haskell 因为类型检查的缘故,跑不通。(待补充)

Update 9.6:(下)被我咕掉了。我有幸在 ref #3 的评论区和博主讨论了很久,可以在那里直接找到。

python在调用时会保证参数全部求值。上式 w(x)(*args) 不可求值,其余lambda式都有外层变量无法求值,因此停止计算。 后式中 w(lambda x: fac1(w(x))) 部分不包含外层变量,因此会反复对w与lambda进行求值。

(其实我现在还没看懂他全部的话 qaq……交给你们了!)


别的因素还有我最习惯写的语言还是 python(Haskell IO 杀我),朋友和我的“共同语言”也只有 python。

本文的目标在于推导递归函数的非递归定义并提出一般方法,并在此过程中引入 omega 组合子和 Y 组合子。

有一个问题至今未得到解决,详见下文。希望各位在(以数学观点)理解全文的基础之上,帮我找到答案。

有用的全部资料:

  1. 推导Y组合子 – 知乎
  2. 在Haskell中定义Y组合子 – 知乎
  3. 各语言Y组合子大比拼 | KAAAsS’s blog
  4. 神奇的λ演算 – 简书

前两篇由浅入深,第三篇给了一个总览,最后则是数学视角。考虑到本文只是上述文章的衍生作品,如果前面三篇能完全理解,那大可不必看这篇拙作。

基础:简述 python 中 lambda 写法

有介于目前我还不会在博客页面中内嵌可运行的代码片段,还请麻烦各位到 glot.io 手动运行下面给出的代码块。(如果有会的,希望能教我)

add = lambda a: lambda b: a + b
print(add(3)(4))
add = lambda a, b: a + b
print(add(3, 5))

后者是一般的写法。但我暑假学了 Haskell 之后,顺手就把从未写出过的前者写出来了……下文也统一采用这种写法,即类似“高阶函数”或“curry”的写法。

此样式表示点击展开:Haskell 中的写法 因为 Haskell 支持 currying,因此\x -> \y -> x + y\x, y -> x + y完全等价。
另外……下文很长都是第一篇文章的直译了……见谅……
python 中 lambda 的其它细节和用法 python 中 lambda 像是一个 hack,无法被help(lambda)查询。
python 中 lambda 运算的优先级最低(仅为 1),不过这极不重要(谁会搞混这个)
lambda 满足越靠里的匿名变量优先级越高。(因此换名的时候看清楚)
lambda 放在最前面可以表示读入参数。(Haskell 直接模式匹配就好)

下文注意运算顺序!函数调用左结合!除非在做某些证明(括号之外构造好了,需要证明括号内相等),否则不要从括号之内开始替换!实名函数按定义运算,匿名函数用括号后面第一个参数替换 lambda expression!

Update 9.11:上面有一点小错……函数调用的时候,其实需要保证内部的内容不可计算。详见《从惰性求值谈起》这篇文章。

阶乘函数的非递归定义

fac = lambda x: 1 if x == 0 else x*fac(x-1)
print(fac(6))

很平淡。

构造 h

定义 h 满足h(h) = fac,则有

h(h) = lambda x: 1 if x == 0 else x*h(h)(x-1)
h = lambda h: lambda x: 1 if x == 0 else x*h(h)(x-1)

注意到此时的 h 已经是一个纯的 lambda expression,因此(原文是因为)可以换名

h = lambda f: lambda x: 1 if x == 0 else x*f(f)(x-1)

也就是说,我们最终定义了一个h函数,这个函数满足h h = fac,而且是用一个纯的 lambda expression 定义的(非递归定义的)。

构造h可能是本文唯一一处不自然的东西。为什么要这么做?这一点我暂时也没想明白。

略过的一些文字 原文此处有一大块代码块来证明上式,我觉得没必要,不就是h作为参数填上了lambda f的位置吗?(需要的自己去找原文)
另外,Haskell 在这里已经跑不通了,因为h是个递归类型,过不了检查。(因此权当外链第一篇文章在写数学)

omega组合子和不动点

上一节给出了阶乘函数的非递归定义。本节指出,上一节的推导存在一般性,可以推广到所有一阶的递归函数。

本节首先对上一节的定义进行了一些等价变换,从而提出了 omega 组合子和不动点两个概念,然后给出了非递归定义递归函数的一般方法。

omega 组合子

fac的非递归定义:

h = lambda f: lambda x: 1 if x == 0 else x*f(f)(x-1)
fac = h(h)

我们首先的目的是化简这个定义。观察到这个定义中出现了相同的模式:f(f)h(h),可以定义一个函数来总结这种模式:

# function w: omega combinator
w = lambda f: f(f)

这个用字母w表示的函数称为 omega 组合子。有了这个函数,上面的定义可以被优化成:

w = lambda f: f(f)
h = lambda f: lambda x: 1 if x == 0 else x*w(f)(x-1)
fac = w(h)
omega 组合子一些其它奇妙的性质
w(w) = (lambda f: f(f))(w)
     = w(w)
亦即,w(w)运算得到的结果为其自身。
(别真这么算,python 没这么聪明,会一直按照运算规则运算,递归深度超限的。)

不动点

我们进一步尝试优化h函数。回归原始,首先审视fac函数的非递归定义。

fac = lambda x: 1 if x==0 else x*fac(x-1)

对上式进行beta reduction,把fac函数本身变成一个可以输入的参数:

fac = lambda x: 1 if x==0 else x*fac(x-1)
fac = (lambda fac: lambda x: 1 if x==0 else x*fac(x-1))(fac)
fac = (lambda f: lambda x: 1 if x==0 else x*f(x-1))(fac)

我们发现了fac1函数:

# function fac1 is defined based on the impure definition of function fac
fac1 = lambda f: lambda x: 1 if x==0 else x*f(x-1)
# satisfies: fac1(fac) = fac

这个函数的性质是fac1(fac) = fac。在这种情况,称facfac1不动点,就像数学里对不动点的定义一样。

对比fac1函数和h函数,注意到forall f, fac1(w(f)) = h(f),所以h = lambda x: fac1(w(x)),进而我们可以把阶乘函数的定义修改如下:

编者的一点备注 上面一段的话确实比较费解。在ls.py中,我花了比较长的篇幅写证明。
fac’ 换成 fac1 的缘故是两种语言的命名规则。
ref 第一篇里面的原文大抵长这样:
对比fac'函数和h函数,注意到forall f, fac' (w f) = h f,所以h = fac' . w,进而我们可以把阶乘函数的定义修改如下:
ls.py中的代码如下:
# %%
fac1 = lambda f: lambda x: 1 if not x else x*f(x-1)
# where fac1 satisfies: fac1 fac = fac, 唤之不动点

# fac1(w(f)) == h(f)
# 证明:
# 左边 = fac1(f(f)) = lambda x: 1 if not x else x * f(f)(x-1) 最右边的是 f(f)(x-1) 还是 f(f(x-1)) 自己想清楚,这就是 python 和 haskell 相比难受的地方了
# 右边 =              lambda x: 1 if not x else x * f(f)(x-1)

# 因此 h = lambda x: fac1(w(x)), 即 h = fac' . w (这样写,Haskell 看不懂的式子竟然看懂了)

# 进而我们可以把阶乘函数的定义修改如下:
w = lambda f: f(f) # 基础定义
fac1 = lambda f: lambda x: 1 if not x else x*f(x-1) # 最初的定义
h = lambda x: fac1(w(x)) # 就是上面的结论
fac = w(h) # 同上面的定义
证明 & 疑惑开始的地方 喜欢数学归纳法的请去 ref #1,本处只用 python 的运算模拟证明。
fac = w(h)
    = h(h)
    = fac1(w(h))
    = lambda x: 1 if not x else x*w(h)(x-1)
   != lambda x: 1 if not x else x*fac(x-1)
上面手动模拟的 python 都跑通了!
emmm 这就是问题所在。如果你细心,你会发现上面的代码开始,python 解释器都是跑不通的。定义fac的时候,就会报递归的错误。
目前我对此已经有了一点猜测。python 计算w(h)时,结果也包含w(h),必然导致无尽的递归计算。暂时等等,看看后面是怎么解决的。

递归函数的非递归定义:一般方法

结合本节以上内容,我们已经总结出了非递归定义递归函数的一般方法,以递归函数fac为例:

  • 一开始,递归函数的定义是这样的:fac = ...fac...
  • 我们根据递归函数的具体形式,提出这样的非递归函数:fac1 = lambda fac: ...fac...,此时这个函数满足fac1 fac = fac
  • 然后借助 omega 组合子,用非递归函数重新定义递归函数:fac = w(lambda x: fac1(w(x)))

对于这种一阶的递归函数(即定义中只因引用自身导致递归的函数),可以用以上的通式来给出纯 lambda expression 的定义。

提出 Y 组合子

本节主要是继续上一节的工作,引出Y组合子,并基于Y组合子给出更好的递归函数定义方法。

Y 组合子

试图化简fac = w(lambda x: fac1(w(x)))

fac = w(lambda x: fac1(w(x)))
    = (lambda fac1: w(lambda x: fac1(w(x))))(fac1) # beta abstraction
    = (lambda f: w(lambda x: f(w(x))))(fac1) # name changing

我们发现了函数Y = lambda f: w(lambda x: f(w(x))),使得fac = Y(fac1)。这里的Y函数称为Y组合子

Y 组合子的不动点性质

容易发现Y组合子的性质:forall f, Y(f) = f(Y(f)),以下是证明:

Y(f) =   w(lambda x: f(w(x)))
     = (lambda x: f(w(x)))(lambda x: f(w(x)))
     = f(w(lambda x: f(w(x))))
     = f(Y(f))
编者注 这里又有一点关于那个问题的猜想。从第三个等号跳到第四个等号,数学上是严谨的(大概?)但是按照严谨的 python 顺序,因为f未知,我们并不能通过继续运算得出答案。
这里应该还看不出什么,往下把fac1带入f的时候应该会明显一些。

我们把这个性质称为不动点性质。

通过不动点性质,Y 组合子实现了对函数f的无限递归调用:Y (f) = f (f (f (f ...)))。因此,可以将Y组合子和设置了停止条件的递归函数fac1组合使用,实现递归函数的逻辑。

递归函数的非递归定义:一般方法 + 化简

我们可以把刚才的定义进一步化简:

  • 递归函数f = ...f...
  • 提出非递归函数:f1 = lambda f: ...f...,满足f1(f) = f
  • 借助Y组合子,定义递归函数:f = Y(f1)

Y 组合子的其他有关性质

简单地展开一下这个式子:Y = lambda f: w(lambda x: f(w(x)))

Y = lambda f: w(lambda x: f(w(x)))
  = lambda f: (lambda x: f(w(x)))(lambda x: f(w(x)))
  = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))

我们把Y = lambda f: (lambda x: f(x(x)))(lambda x: f(x(x)))这个式子称为Y组合子的 curry 定义。

尾声

这篇文章只是基础知识……下篇文章会详细讨论遇到的错误和一个黑魔法。(翻了翻自己的ls.py,下面是有六分之五个屏幕宽一行的 lambda expression,怕了,真不知道 21 号清晨我是怎么算的)

4 对 “python 中的 Y 组合子(上)”的想法;

  1. Firefox 80.0 Firefox 80.0 Windows 10 x64 Edition Windows 10 x64 Edition

    一点纠正:好像“完整地出现”并不是递归定义出现的原因。毕竟黑魔法的推导过程中也出现了……也没有报错。

  2. Firefox 81.0 Firefox 81.0 GNU/Linux x64 GNU/Linux x64

    可运行的代码块与markdown文章结合可以试试jupyter notebook, 但具体的使用方法我不会(直球), 不过重度偏向于运行程序, markdown只是做解释, 可能不太适合写文章

    1. Firefox 80.0 Firefox 80.0 Windows 10 x64 Edition Windows 10 x64 Edition

      emmm 我的意思是类似网站里面嵌入一个 glot 类似的块
      另外 WordPress 并不是用 Markdown 写文章(虽然用 vscode 写 Markdown 然后把渲染结果复制到可视化编辑器完全可行)

发表评论

电子邮件地址不会被公开。 必填项已用*标注