逐步理解丘奇数(一)-活动日历-神都互动网游活动专题站

最近又翻到了sicp第二章，再一次看到了那惊鸿一瞥的Church numerals，才发现一年前我对它的理解有多么肤浅，没有仔细去想通其中的’魔法’更是一种不负责任；现在我要结合我目前对它的理解方式，逐步以文章系列的形式阐述，方便自己回味，也为别人提供一种参考。

这篇文章打算描述丘奇数的形式、一些基本特性以及我对它的理解思路，并逐步“想出”’自然数’、’加法运算’、’乘法运算’、’幂运算’的定义；

保持sicp传统，文中使用简单的scheme语言描述（只用到基本的define和lambda匿名函数）；出于兴趣以及没事找事做，我也打算在文章最后给出一份javascript语言描述的版本，作为福利。

丘奇数其实就是一种计数方法，建立在lambda演算的基础之上；

我们先来看看它对’0’和1的定义：

对’0’的定义：

(define zero

(lambda (f) (lambda (x) x)))

对’1’的定义：

(define one

(lambda (f) (lambda (x) (f x))))

可以看到，丘奇数其实就是用函数来表示数字，这些函数是怎样的函数呢？是能接受一个参数(f)的函数；

而且，真正传给它一个参数(f)之后，得到的结果还是一个函数，这个结果函数还能再接受一个参数(x)，再接受一个参数(x)之后，才能得到最终结果；

简单地说，丘奇数就是一系列能“分两个阶段”接受参数的函数，每个阶段分别接受一个参数（因为每个阶段都是一个lambda表达式）。

其实，我们只要再看看’0’和’1’之后的数字的定义，就能找到一些规律，比如’2’的定义：

(define two

(lambda (f) (lambda (x) (f (f x)))))

自然而然，3个数一比较，我们就会关注到这几个函数的’主体’部分——抛开形式化参数的部分：x, (f x)以及(f (f x))——很明显，“数字”其实就是’f’反复作用于函数’主体’的次数，比如’0’就是’x’，一个’f’也没有；’1’的话，’f’作用在了函数’主体’上一次:(f x)；’2’则作用了两次:(f (f x))，其它自然数依此类推。

那么，这种形式让我们想到了什么呢？或者说，拿什么来“类比”这种形式，才能帮助我们理解这种BT的计数方式呢？其实也很明显，让我们来观察：

zero: x

one: (f x)

常识告诉我们：’0’应该由’1’再’+1’得到，丘奇数是一种计数法，当然也是如此：one应该由zero通过某种形式’加一’得到；显然，丘奇数中的“加一”就是用’f’来作用一次——zero就是x，f作用于x，相当于“加一”，就得到了one，也就是(f x)；

既然如此，我们干脆就把x想象成自然数0，f想象成’+1’函数(++)，这样不就能把丘奇数“翻译”成我们熟悉的自然数了么，那我们来定义一个’++’函数：

(define (inc n)

(+ n 1))

OK，把这个‘inc’函数作为’f’，自然数’0’作为x，分两个阶段传入，立马就能把丘奇数zero、one、two…翻译成我们熟悉的自然数0,1,2…，比如，以下代码将得到自然数2：

((two inc) 0)

为啥会这样呢？道理很简单：丘奇数定义了一个’0’，然后定义了一个’+1’，那么也就归纳地定义出了所有的自然数；

其实，由传入inc和自然数0之后就能将丘奇数“翻译”成自然数这一点上看，我们的自然数体系已经被概括进丘奇计数法里了，我们熟悉的自然数成为了丘奇计数法的一种特例，这个以后再讨论；到这里为止，结合自然数的类比，我们已经对丘奇数的计数原理有个清晰的了解了，下面，我们要逐步在这一套计数法则之上定义各种运算。

首先我们来定义加法运算：

思路——如果需要计算m+n，也就是要把m中的所有’f’作用于n的函数’主体’之上，得到的结果中的’f’作用次数应该是m和n中’f’的作用次数之和，比如one 加 two，就是'(f x)’ 加 ‘(f (f x))’，结果应该是'(f (f (f x)))’；

那么怎样才能达到这个效果呢？这就要运用我们参数代入替换的能力：思考一下——如果能把two，也就是(f (f x))放到one的函数体的’x’的位置，那就变成three了，也就是(f two)；那么，加法的直观想法就应该是——把其中一个加数当做’x’的值，代入另一个加数中！那么’f’呢？’f’怎么办？’f’不管，它要的时候我直接喂一个’f’给它~

要计算m+n，先“喂”一个’f’，再“喂”一个’x’给n，得到函数值，即：((n f) x)；然后“喂”一个’f’给m，使m到达“准备接受一个’x’的状态”，再将“喂过”’f’和’x’的n作为参数传给“准备接受一个’x’状态”的m，就能得到m+n了！如此，加法运算定义为：

(define (add m n)

(lambda (f) (lambda (x) ((m f) ((n f) x)))))

好了，来验证一下我们定义的加法到底对不对：(add one two)之后再传入’inc和”0’方便我们查看结果

(((add one two) inc) 0)

输出：3

OK，到此为止，我们成功地定义出了个1+2=3的道理，是不是很舒服呢？本打算这里也一并介绍一下乘法、幂运算的分析过程的，但我发现这篇文章已经够长了，算了吧，那些应该是《逐步理解丘奇数(二)》的内容…

下面，说好的福利，我再用javascript把这些东西定义一遍，可以直接保存为html文件运行：

js版本看上去反不如scheme版本直观…不是么？