丘奇计数与“数”的本质
学习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,而在小孩子眼中,它有无限的可能,一个呼啦圈、一张大饼、一轮明月。。。而在对数的理解上,我们可能不如结绳计数的远古人。因此,我们不要忽视小孩子的创造力,也不必惊讶古代人那些“超前”的科技发明,因为他们有不同于我们的思考方式。
尝试着抛开那些束缚思维的成见,把自己当成天真的小孩与原始人,或许会有意想不到的收获。
相关推荐
《数据结构与算法分析——C语言描述》(原书第2版),英文版的名称是《Data Structures and Algorithm Analysis in C》,作者是:(美)Mark Allen Weiss。原书曾被评为20世纪顶尖的30部计算机著作之一。之所以选这...
资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download>>>https://github.com/wizardforcel/sicp-py-zh
SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版SICP中文第二版
SICP-Python版本
Python SICP epub版本,很适合学习抽象的思想,用Python版本比lisp更实用
SICP 使用的scheme解释器 以前叫DrScheme
sicp 2.2.4节图形语言的racket程序包,配置路径,C:\Users\Administrator\AppData\Roaming\Racket
SICP 解题集
我所选择的教材是《数据结构与算法分析——C语言描述》(原书第2版),英文版的名称是《Data Structures and Algorithm Analysis in C》,作者是:(美)Mark Allen Weiss。原书曾被评为20世纪顶尖的30部计算机著作之...
Learn_sicp 学习sicp的一些代码
SICP CHINESE ENGLISH THE SECOND EDITION SICP CHINESE ENGLISH THE SECOND EDITION
sicp 和 操作系统:精髓与设计原理第七版 文档打包。
SICP 习题答案 计算机程序的构造和解释 1-3章 习题答案
sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh
sicp_notes SICP笔记和练习 资源 笔记 使用第一版,最高为ex 1.24。 从ex 1.31开始切换到第二版。
SICP习题解答,主要第一章的内容习题答案
SICP绝对好书 需要学习scheme等知识,配合https://mitpress.mit.edu/sites/default/files/sicp/index.html英文原版阅读更佳
选择的教材是《数据结构与算法分析——C语言描述》(原书第2版),英文版的名称是《Data Structures and Algorithm Analysis in C》,作者是:(美)Mark Allen Weiss。原书曾被评为20世纪顶尖的30部计算机著作之一。...