Recreating SICP 1:从一个计算器开始

作者:何岩,禁止转载。

0.前言 #

你知道MIT计算机专业的第一门课是什么吗?
那就是SICP(Structure and Interpretation of Computer Programs)
SICP被评为是一本神书。两位作者就像是炼金术士,将自己对计算机科学的真知灼见浓缩在不算厚的SICP之中。
虽然看上去SICP文字不多,但是信息量极大。很多我们常见的争论议题,例如面向对象和面向函数之争,SICP只需要几行文字就能点到本质。看完之后总有一种“原来这个问题的本质是这样!”的恍然大悟。然后才知道,之前的自己只是以为自己懂了。
SICP如此伟大,确少有人读,可谓最被忽略的宝藏。
我将用故事的形式,将其重新开采。
希望通过这个系列,让你可以“看见”SICP的光辉。

故事的主角来自神剧:Rick & Morty

1.png

1.Rick & Morty #

Morty家的车库是Rick的工作室。

Rick是全宇宙最聪明的科学家,大部分时间都在这里鼓捣他的发明创造。

Morty是他的外孙,身体总是软绵绵的,和他的智商一样让人觉得不可靠。

木头桌子前,Rick盯着电脑屏幕,用鸡爪一样的双手,敏捷的敲打着键盘。

电脑的另一端连着一个发光的立方体。

Morty指着立方体问:“Hi Rick,这是你的新发明吗?”

“这是我造的小宇宙,它可以像电池一样给我的太空船供电” Rick说

“现在它有点不正常,从外面看不出问题,得进去看看。”Rick拿出两支类似蓝牙耳机的设备:“来Morty,把这个插在耳朵里,用它可以进入小宇宙,它的名字叫做:MI(意识转换器,英文全称:Mind Interpreter)”

Morty看着手中的MI,心想为什么啥事都要拉上我,本来还想看会电视。

两人同时按了一下耳朵上的MI,便失去意识,倒在了地上。

2.BUG来自GC(垃圾回收器) #

Rick和Morty在一家咖啡馆醒来,墙上写着“Recreating Cafe”。

牛头人端着咖啡走过来:“Rick,你可来了!最近这里发生了一些特别可怕的事情。”

2.png

牛头人是宇宙联邦的一级通缉犯,为了不连累家庭,五年前自首后被处死了。自首之前,牛头人偷偷找到Rick,说自己还有一个梦想,想做出全宇宙最好喝的咖啡。Rick喜欢喝咖啡,就将他的意识上传到了小宇宙里,从此牛头人便在这里开起了咖啡馆。

“什么可怕的事啊?”Rick接过咖啡,品了一口,“ 嗯!牛头人,你的手艺又进步了!Morty快尝尝全宇宙最好喝的咖啡!”

Morty喝了一口,心想全世界的咖啡不都一个味吗。

牛头人没有等来Morty的赞叹,继续说:“大概一周前,一些人头顶会莫名的冒出一个光环,几天之后,同一个时刻…”牛头人打了个响指,“刷的一下,他们就那么消失了!”

Rick瞪着着眼睛:“就像天使一样的金色光环吗?”

“对!就是那种!“

“Morty!快跑!这里不安全!”Rick按下了MI的退出按钮

Morty紧跟着也做了同样的动作。

三个人面面相觑了几秒钟,结果什么也没有发生……

“R…Rick,MI坏了吗?”Mory问。

“MI没有坏,是小宇宙坏了。”Rick说。

“你可以修好它吗?”Morty问。

“不行,小宇宙的主程序Matrix并没有问题,问题出在辅助程序GC(垃圾回收器,英文全称:Gabage Collection)上,GC清理任何事物之前都会先用光环进行标记。正常情况下只会标记没人用的物品和已经死亡的生命,现在GC疯了,竟然标记起了活人。这真是太可怕了!”

“那你为什么不能修复它呢?”牛头人问

“修复GC必须要回到外面的世界,Matrix和GC是两个独立且平行的程序,他们同时运行在小宇宙这个硬件盒子里。在外面的世界我们可以同时看到他俩,但是现在我们置身其中一个,无法看到另一个。所以现在我无法修复GC。”

“本打算进来找到问题就回到外面的世界修复它,没想到是GC出了问题。GC其实很简单,我都能猜到是哪行代码出了问题。两周前我刚给GC做了升级,因为GC无法进行DEBUG(调试),只能靠脑子推算,看来我还是犯了错误。”

“Rick那么怎么办。我们会死在这里吗?”Morty问。

“也许哦!GC现在是随机清理,但愿下一轮GC不要标记你吧!刺激吧!”

“如果我们死在了Matrix,我们在真实世界的肉体也会死去吗?”

Rick忽然用水果刀划了一下Morty的手背,一道血痕缓缓出现。

“痛!”Morty叫到

Rick说:“此时此刻,你在外面的身体也会产生这道伤口”

“可是,我们现在不是在虚拟世界里吗?”

“你的意念让它成为了真实,身体无法不依赖意识而独自存在”

“牛头人,再给我来一杯咖啡吧,死之前我还想多喝几杯!”

3.那就重新写一个LISP版本的MI吧 #

“你犯的错误,你得修理好!我可不想死在这里!心里没数还要带我来!”Mory说

“你可是全宇宙最聪明的科学家,没有什么是你搞不定的”牛头人说

“没看到我正在思考吗?”Rick盯着脑子里虚幻景象。

忽然,Rick抓起笔,在一张白纸上写起来:

RECREATING.ORG #

( + 1 2)
=>

几秒钟之后,答案“3”自动出现在了末尾处:

RECREATING.ORG #

( + 1 2)
=>
3

“哈哈!有救了!”Rick说。

“怎么回事?”Morty问。

Rick说:“MI之所以不好使了,是因为MI是用Python编程语言写的,所有Python程序都要基于Python解释器才能运行,倒霉的是GC将Matrix里的Pyhton解释器搞坏了。所以,即便MI自身没问题,也无法运行。”

“但是我发现Matrix中的Lisp解释器还能用,还好之前我在Matrix里给自己留了一个后门,只要出现#RECREATING.ORG这行文字,Matrix就会认为到那是一个Lisp文件,并将其传递给Lisp解释器来运行。如果我用Lisp重新写一个MI,我们就可以回到外面的世界了,一但出去,我会马上修复GC,牛头人就安全了。”

“Rick!你真是太帅了!”牛头人说。

“希望GC不要再把Lisp解释器搞坏了。我得抓紧时间了!”Rick说。

“有什么我能帮上忙吗?”牛头人问。

“给我多拿些纸来,这里只能用手写代码了”Rick说。

“难道这个世界没有电脑吗?”Morty问。

“没有,这里的人们更怀念计算机发明之前的日子。所以我将Matrix模拟成了蒸汽时代。”Rick说。

“难道你不能先做出来一个计算机,然后用计算机来写代码吗?”Morty问。

“你是傻瓜吗?我连计算机都没有,我怎么造出一个计算机来?”

Rick把一摞纸放在面前,拿起笔,说:“这感觉太糟糕了,这就像一个厨师没有了刀和锅。”

“那你加油吧!我出去转转,我想去看看蒸汽时代的世界”Morty站起来要走。

“你还真有闲心!你要跟着我写代码,还要搞明白这一切,万一在我写完之前就被GC杀死了,你要继续写完。”Rick说

“可是我不会Lisp啊!虽然学校开了一门教Java的编程课”Mory说

“Lisp是这个世界上最简单的语言,你学过Java已经够了,跟着我,我会给你讲解的,难道你不想活了吗?不要抱着侥幸心理!”Rick说

“好…好吧!”

4.从一个简单的计算器开始 #

“我得想想,当初我是怎么设计的MI”Rick眼珠乱转。

“你不能查看Python版本的MI代码吗?”Morty问

“不能,MI和我们是平行的存在,就像我看不到眼前这只咖啡杯的代码一样”Rick说

Rick想了半天说:“我只能记得大体的设计思路,算了,让我们忘记过去重新开始吧!”

“我们从最基本的地方入手,那就是自然数的运算,从一个简单的计算器开始,然后一步一步,逐步添加更高级的功能,最终达到终点。这可真像是一场徒手攀岩。”

5.后记 #

Rick和Morty明确了自己要做的事,就是重新构建一个MI(意识转换器),首先从一个计算器开始,后面会加入各种复杂的功能,例如有理数的计算,复数的计算,解微积分等。通过构建MI将SICP前三章的精华挂接上来。

 
2
Kudos
 
2
Kudos

Now read this

305十年再相聚

2104年十一期间,305相聚在北京,happy的度过了美好的假期。 # 十年前的305,在长春理工寝室后面的树林子里。 现在的305,在国家大剧院音乐厅。 第1天-胖子驾到,老朱请吃铁板烧 # 胖子从哈尔滨做火车到达我们的小寝室。胖子还是那么…你懂得~~ 然后都到我家,等老朱,挫进我小猫 老朱姗姗来迟,结果遭到胖子撕咬,还是那么销魂。 俩人进屋就开始吃,还叼着蛋卷当雪茄,吊丝啊。 胖子弹钢琴 我和胖子 到了中午,老朱由于迟到啦,所以请我俩吃铁板烧。吃得猛了点,... Continue →