无类型lambda演算

给定以下三条规则

1. a 变量 表示参数或数学/逻辑值的字符或字符串
2. (λx.M) 抽象化 函数定义（M是一个lambda项）。变量x在表达式中已被绑定。
3. (M N) 应用 将函数应用于参数。 M 和 N 是 lambda 项。

穷人的不动点

假设我我要写N的累加 1+2+3+...n (伪代码警告) let f = lambda n. n==1?1:f(n-1) 但问题在于 lambda 定义部分中的f 在函数未定义时是不存在的. 那么

let f = lambda self,n. n==1?1:n+self(n-1)
f(f,n)

不过上述代码其实是有问题的 因为f要求有两个参数 而我们使用self时只传了n-1 这一个参数. 所以实际上是

let f = lambda self,n. n==1?1:n+self(self,n-1)
f(f,n)

这就是所谓的 >穷人的不动点

为什么有了Y组合子之后就能表达递归

Y组合子指的是某种magic使得 Y(g) = g(Y(g)) 可以通俗的理解为 存在某种操作(函数,实际上是高阶函数)Y,给Y一个g(函数), Y(g) 实际上能够产生出函数 g(Y(g)) 也就是讲 Y(g)等同于以Y(g)作为参数调用g

这样的话 我们的穷人的不动点就可以升级为正常的不动点了

// 公式1
let f = Y(lambda self,n. n==1?1:n+self(n-1))
f 3

但为什么呢? 为什么有了Y组合子之后就能表达递归 为了理解我们需要 手动展开 来演练一下 首先是 g 在上述函数中 g 实际上指的是 lambda self,n. n==1?1:self(n-1),总而言之 是一个有两个函数的参数, 并且在计算的过程中我们会一某种程度上减小了问题规则的参数来a调用self 展开

f 3 => Y(g)(3)          # Y(g) 会返回某个函数 我们以3为参数调用他
      => g(Y(g))(3)     # Y(g) 实际上返回的函数是g(Y(g)) 已经被填充一个参数的双参函数 以3为参数去调用他 实际上是在以 Y(g)和3为参数在调用g
      => 3+ Y(g)(2)     # 还记得g的定义 n==1?1+n+self(n-1) 此时这里的self 就是Y(g)
      => 3 + g(Y(g))(2) # 这里已经可以看到递归的形成了  g(Y(g))(3) 变成了3 + g(Y(g))(2)
      => 3 + 2 + Y(g)1
      => 3 + 2 + g(Y(g))1
      => 3 + 2 + 1      # 到达了g的终止条件 n==1

Y组合子的特性

Y := λf.(λx.(f(x x)) λx.(f(x x))) 这一坨看上去就很痛苦,理解起来其实也比较痛苦 不过注意到一点 λx.(f (x x)) 实际上出现了两次 我们暂且把他称作a Y := λf.(a) a) 即 Y 会以a为参数调用a (参数是我 函数也是我) a : λx.(f (x x)) 传入一个函数 以这个函数为参数调用这个函数 (参数是我 函数也是我) 以其结果为参数调用f,这里的f就是Y的参数 所以说Y真正做的事情是,当任意的函数g作为Y的参数传入时

Y: a(a)
a(fa): g(fa(fa)) # fa指的是某个传给a的a函数 
Y: g(a(a))       # 因为传给a的函数就是a自身 所以Y就是 以a(a)为参数调用g

奇妙的事情发生的就是这么的突然 Y(g)=g(Y(g))

a实际上有两个参数 一个是f,一个是x. 其做的事情就是以 x(x)的返回值为参数调用f 当我们以a自身为参数调用a时,发生的事情实际上是 以a自身为参数调用a的返回值为参数调用f 说起来有点绕,其实也很绕. 但让我们退后一步想想a的意义是什么.

f(a)=a(a)
f(f1) //  研究a为f的情况
->f1(f1) 
-> f1(f1)
-> f1(f1)

一个可以无限展开的循环. 向其中注入函数x

t(a)=x(a(a)) => t(t)=>x(t(t))

(lambda x. x x ) (lambda x. x x ) 注意在展开后继续下次展开是执行权限被交到x的手中,x可以选择根据条件不在执行self(终止循环)

ref