SICP学习笔记——丘奇计数与“数”的本质【脑洞大开】

丘奇计数与“数”的本质

学习SICP有一段时间了，对Lambda表达式以及过程为参数等特性的强大并没有概念，直到看到习题2.6中提到的丘奇计数（Church counting），才有种脑洞大开，恍然大悟的赶脚，便迫不及待的和大家分享一下——尼玛，原来“数”还可以这样玩！

首先，题目抛砖引玉，丢出了两个定义，一个是0的定义：

 

(define zero
  (lambda (f)(lambda (x) x)))

 

然后是操作+1的定义

 

(define (add-1 n)
  (lambda (f)(lambda (x) (f ((n f) x)))))

 

接着就要求我们在此基础上，给出1、2以及操作+的定义。

说实话，笔者第一眼看到这三行代码也是一头雾水——这代码和数字有半毛钱关系吗？

凝视了这三行代码10分钟，笔者终于承认自己被智商碾压（显然已经不是第一次了），乖乖拿起笔和键盘，由于是有了这篇博文。

 

在讲解之前，我们需要首先明白一点，那就是“数”究竟是什么。

我们从小学一年级就学会了写1 2 3，却很少有人思考真正的“数”是什么，直接的证据就是，现在的你基本无法给“1”“2”“3”下一个明确的定义！

为了回答这个问题，我们不妨把时间调回上古时代。那个年头，还没有阿拉伯数字，人们计数的方法也似乎很可笑：假如一个人有10头羊，他会找来一根绳子，每走到一头羊的面前便系一个绳结，当他走遍所有的羊群，便得到了一条系着10个绳结的绳子，这样，他以后只要每次把绳结与羊再对应一遍，就能知道他的羊有没有少，这就是大名鼎鼎的“结绳计数法”。

固然，数一遍羊然后写个“10”更省事，但在我看来，原始人比我们更懂得“数”的含义。因为我们习惯性地把数字理解成了符号，而忽略了那符号背后代表的东西，或者换个富有诗意的说法——

谁说只有符号“0”才能代表“零”呢，一个空空的口袋不能代表“零”吗？又是谁说只有符号“1”才代表“壹”，在苍茫大地上孤独行走的我不能代表“壹”吗？

如果能把脑洞开到这个程度，我相信你就能理解丘奇计数了。

 

先简单分析一下zero与add-1两个定义，他们都返回一个嵌套了两层的lambda匿名函数，每层各需要一个参数，或者为了让大家看的更明白，我们把它看成是经过Currying的2参数lambda表达式，即：

 

(define zero (lambda (f x) (x)))
(define (add-1 n) (lambda (f x) (f (n f x))))

 

 

（看不懂lambda与Currying的读者不要急，我会在下一篇博客中给大家详细介绍。）

 

         根据题意，我们不难想到one的定义：

       

(define one (add-1 zero))

 

 

替换宏替换后得：

 

(define one (lambda (f x) (f x))

 

或者：

 

(define one
  (lambda (f) (lambda (x) (f x))))

 

同理，我们得到two的定义： 

 

(define two
  (lambda (f) (lambda (x) (f (f x)))))

       或者

(define two (lambda (f x) (f (f x))))

 

怎么样，发现规律了吧？其实这里的“数”指的是函数的调用次数！

同样的，我们也可以轻松地得到three的定义：

(define three (lambda (f x) (f (f (f x)))))

现在问题来了，加法又该如何定义呢？我们不妨参考一下add-1的定义，（add-1 n）不过就是在调用n次f的基础上外层在调用一次f，所以，(add m n)不过是在调用n次的基础上再调用m次罢了：

(define (add m n)
  (lambda (f x) (m (n x))))

你可能抱怨看不懂lisp代码，但这正体现了lambda表达式的强大，因为我们几乎无法用java、C++这些语言重写这几行代码！

至此，我们已经完美解决了这看似“莫名其妙”的丘奇计数问题。不知读者是不是理解了丘奇大师的思想，反正我是脑洞大开，获益匪浅。他向我们展示了一种新的数的表示，计算机中的“数”也远不只0101那么简单。

 

反思一下，我们在发明各种数学符号的同时，是否也把思维局限在了这些符号之间？面对“0”，我们的第一反应可能只是阿拉伯数字0或者字母o，而在小孩子眼中，它有无限的可能，一个呼啦圈、一张大饼、一轮明月。。。而在对数的理解上，我们可能不如结绳计数的远古人。因此，我们不要忽视小孩子的创造力，也不必惊讶古代人那些“超前”的科技发明，因为他们有不同于我们的思考方式。

 

尝试着抛开那些束缚思维的成见，把自己当成天真的小孩与原始人，或许会有意想不到的收获。

评论

1 楼 布林一角 2015-04-02  

我认为加法的定义应该是这样的：

(define (add m n) 
  (lambda (f x) (m ((n f) x))))