λ演算与邱奇编码

假设我们有一门只能使用Lambda演算的语言,它的计算能力有多强?

要讨论这个问题,让我们先从定义自然数开始。

邱奇编码(church encoding)

邱奇定义过一种仅使用lambda演算的数据编码,称为邱奇编码(church encoding)。

邱奇数

我们先来看看邱奇是怎么定义自然数, 即邱奇数(church numerals)的:

(define 0 (lambda (f x) x))
(define 1 (lambda (f x) (f x)))
(define 2 (lambda (f x) (f (f x))))
(define 3 (lambda (f x) (f (f (f x)))))

可以看出来,自然数n可以通过将函数f在x上应用n次得到。

但是我们不可能定义全部的自然数,所以必须要有方法来表示后继,即

(define suc (lambda n) ...)

根据自然数的定义,一个数的后继即是将f再多应用一次,那么我们就可以得到后继的定义

(define suc (lambda n) (lambda (f x) (f (n f x))))

这样我们就能得到整个自然数域。

四则运算

让我们从加法开始。加法可以通过后继实现,即(m+n)是n的m个后继,即对n求m次后继。

(define + (lambda (m n) (m suc n)))

在这里,我们用(m suc n)表示将求n的m个后继,这看起来有些难以理解。

还记得自然数的定义吗?n可以表示为(lambda (f x) (f (f (... (f x)))))。那么类似
的,(m suc n)的运算过程可以表示为

(m suc n)
=>
((lambda (f x) (f (f (f ... (f x))))) suc n)
=>
(suc (suc (suc (suc ... (suc n)))))

写到这里就很清晰了,我们将(suc n)重复了m次。

我们也可以参考自然数的定义,加法先将函数f在x上应用n次,然后再应用函数f m次,
得到一个在x上应用(m+n)次的函数。根据自然数的定义,这个函数就是值(m+n)。

(define + (lambda (m n) (lambda (f x) (m f (n f x)))))
;; alternative defination
(define + (lambda (m n f x) (m f (n f x))))

在有了加法之后,我们就可以定义乘法了。利用加法来定义乘法是一个好思路。(m*n)可以
通过对0求m次(+ n)操作得到,即:

(define * (lambda (m n) (m (+ n) 0)))

直接定义乘法:将函数f在x上应用n次,在将这个过程应用m次。

(define * (lambda m n) ((lambda f) (m (n f))))
;; alternative defination
(define * (lambda m n f) (m (n f)))

继续推进,我们还可以定义指数函数。类似于利用加法定义乘法:

(define ^ (lambda (m n) (n (* m) 1)))

类似的,利用指数函数的定义:m^n表示n个m相乘

(define ^ (lambda (m n) (n m)))

减法的定义比较复杂,我们稍后再谈。

布尔

现在我们已经有了一套自然数的体系,并且有了对自然数的操作(加法、乘法、指数函数)。

该怎么定义布尔类型呢?

先来思考下,布尔类型在什么样的情况下会用到呢?

最常用的是用对与错做选择吧,那么我们就可以把布尔编码成返回两个变量中的一个函数。

(define #t (lambda (a b) a))
(define #f (lambda (a b) b))

在这里,对返回两个变量中的前一个,错返回后一个。

顺序其实并不重要,我们只需要在实现控制流的时候反映出布尔的定义即可。

有了对和错,让我们来实现if吧。

if接受三个变量,由第一个变量决定是返回第二个还是第三个变量。还记得我们怎么定
义布尔的吗?它接受两个变量并返回其中一个。那么我们直接利用布尔的定义就可以实现
if:

(define if (lambda (c a b) (c a b)))

c在这里是一个布尔,它接受a b两个参数,当c为真时,返回a,反之为b

那么andornot呢?

(define and (lambda a b) (a b #f))
(define or (lambda (a b) (a a b)))
(define not (lambda x) (x #f #t))

to be continued
しかし彼女の記憶は続かない