精子创办了一档播客节目,大家可以在 iTunes 搜索「彩排」,或访问  caipai.fm  来收听。
标签 #技术

SICP 笔记:1 – 1.1.8

计算机程序的构造和解释 是这样的一本书:它将大量编程中的基本技巧,用一本正经的语言讲出来,帮助你在构建大型软件时使用这些技巧来控制代码中的复杂性。而这些技巧的共性之一就是,将复杂的事物,通过隐藏细节的方式进行组合和抽象。我认为如果一个合格的程序员只需要读三本书的话,这本书便位列其中。

写笔记是为了自己在读书的过程中能够更好地思考和理解,这份笔记的定位是排除书中的例子,将书中的结论和观点用自己的话重新描述一遍,以简体中文版为主,因为似乎翻译的质量不高,所以也会参考英文原版。本书的英文原版以 CC-BY-SA 发行,相信公开发布这份笔记没有版权方面的问题。

其实这份笔记对没有读过本书的人没有什么意义,因为本书的重要价值在于书中的例子,而这份笔记不会涉及这些例子,所以请纯当我在自言自语。

计算机程序的构造和解释

一个计算机语言不仅仅是让计算机去执行操作的一种方式,更是一种表述有关方法学思想的新颖的形式化媒介。因此,程序必须写得能够供人们阅读,顺便供计算机执行。在这一层次,最基本的材料并不是特定的程序设计语言的语法,不是能够有效地计算某种功能的巧妙算法,也不是算法的数学分析或计算的本质基础,而是一些能够用于控制大型软件系统的智力复杂性的技术。

我们希望读者能够对程序设计的风格要素和审美观有一种很好的感觉;他们应该掌握控制大型系统中的复杂性的主要技术;他们应该能够去读 50 页长的代码,并知道在什么时候哪些东西不需要去读,不需要去理解;应该有把握地去修改一个程序,而保持原来的作者的精神和风格。

这些技能并不仅仅限于计算机程序设计,对于所有工程设计都是通用的。我们应当在适当的时候隐藏起一些细节,通过创建抽象去控制复杂性;通过建立起约定,以一种「混合与匹配」的方式组合起一些标准的,易于理解的片段,去控制复杂性;通过发明新的程序设计语言,每种语言强调设计中的一个特定方面并降低其他方面的重要性,来控制复杂性。

1 构造抽象过程

「计算过程」是存在于计算机中的一类抽象事物,这些过程会去操作一些被称为「数据」的抽象事物,人们创造出一种被称为「程序」的规则模式,来指导这类过程的进行。

设计良好的计算机系统就像设计良好的汽车或核反应堆一样,具有某种模块化的设计,其中的各个部分都可以独立地构造、替换、排除错误。

虽然 Lisp 并不是一种主流语言,但其具有一些特征使它成为研究程序的设计、构造,以及各种数据结构的一种最佳媒介。其中最重要的是:计算过程的 Lisp 描述本身又可以作为 Lisp 的数据来表示和操作;它的重要性在于,现存的许多威力强大的程序设计技术,都是在致力于填平「数据」和「过程」之间的传统划分。

1.1 程序设计的基本元素

任何一个强有力的语言都必须提供三种机制:

  • 「基本的表达形式」表示最简单的个体
  • 「组合的方法」将简单个体组合成复合对象
  • 「抽象的方法」将复合对象作为一个整体单元来操作

1.1.1 表达式

1.1.2 命名和环境

在 Lisp 中,我们可以将值与符号关联,而后又能通过符号提取出这些值,这意味着解释器必须维护着某种储存能力,以保持有关的符号和值之间的映射,这种储存被称为「环境」。

1.1.3 组合式的求值

在 Lisp 中,对一个组合式的求值过程:先求值该组合式的各个子表达式;然后将最左子表达式的值所表示的过程,应用于其他子表达式所代表的参数。

我们可以用一棵树的形式来表示这一求值过程,其中每个组合式用一个带分支的节点表示,其分支对应于组合式中的运算符和运算对象,终端节点表示的是基本运算符和数值。

可以设想这些运算符和运算对象向上穿行,从终端节点开始,而后在越来越高的层次组合起来。

在性质上,这一求值过程是「递归」的,也就是说在这个计算过程中,包含着调用这个过程本身的步骤。我们应当将递归看做一种处理层次性结构的强有力的技术。

进一步的观察告诉我们,反复地应用第一个步骤,总可以将我们带到求值过程中的某一点,在这里遇到的不是组合式而是基本表达式,例如数值、内部运算符或者其他名字,处理这种基本情况的规则如下:

  • 数的值就是它们所表示的数值
  • 内部运算符的值就是能够完成相应操作的机器指令序列
  • 其他名字的值就是在环境中关联于这个名字的那个对象

环境所扮演的角色就是用于确定表达式中各个符号的意义,如果没有关于环境的任何信息,例如 (+ x 1) 这样的表达式的值是毫无意义的,因为需要有环境来为符号 x 提供意义,甚至需要环境来为符号 + 提供意义。环境是一种具有普遍性的概念,它为求值过程的进行提供了一种上下文。

define 是目前我们看到的唯一的一种特殊形式,每个特殊形式都有其自己的求职规则。各种拥有不同的求值规则的表达式组成了程序设计语言的语法形式。Lisp 的语法非常简单,也就是说,可以被描述成一个通用规则和一组针对不多的特殊形式的专门规则。

1.1.4 复合过程

「过程定义」可以为复合操作关联一个名字,而后就可以将这样的操作作为一个单元来使用了。

过程定义的一般形式是:(define (<name> <formal parameters>) <body>)

其中 name 是一个符号,这个符号将在环境中和这个过程关联起来;formal parameters 即形式参数是一些名字,在过程体中用于表示应用过程时与它们位置对应的各个实际参数。body 是一组表达式,在应用这个过程中,body 中的形式参数将被与之对应的实际参数取代,对这样被替换后的表达式进行求值,产出这个过程应用的结果。

我们还可以用过程作为基本构件去定义其他过程,复合过程的使用方式与基本过程完全一样,事实上如果人们只看到过程的名字,根本就无法分辨出来它是像一个基本过程一样被定义在解释器中,还是一个复合过程。

1.1.5 过程应用的代换模型

对复合过程进行应用的过程被称为「代换模型」,在应用一个过程时,先将过程体中的形式参数替换为实际参数,然后像对组合式求值那样,对替换后的过程体进行求值。当然,这里描述的过程知识一个简单的庆幸,在真正的解释器中并不是这么做的。

对组合式的求值可以有两种方式:先将组合式完全展开再进行求值的模型被称为「正则序求值」,与之对应的,先求值参数再应用过程的模型被称为「应用序求值」。对于前面提到的可以通过替换来应用的过程,正则序和应用序求值的结果将会是一样的。

Lisp 采用应用序求值,部分原因在于这样可以避免对表达式的重复求值,更重要的是在超出了替换方式模拟的过程应用之后,正则序的处理将会变得非常复杂。

1.1.6 条件表达式和谓词

我们用术语「谓词」指那些返回真或假的过程,也指那种能求出真或假的值的表达式。

andor 这些逻辑运算符用来构造复杂谓词。解释器将会对 andor 的参数从左至右逐个求值,直到一个参数的值是真作为结果,跳过对右边其他表达式的求值。andor 都是特殊形式而不是普通的过程,因为他们的子表达式不一定都会被求值,not 则是一个普通的过程。

1.1.7 实例:采用牛顿法求平方根

在数学中,人们通常关心的是说明性的知识(是什么), 而在计算机科学里,人们则通常关心行动性的描述(怎么做). 说明性描述和行动性描述有着内在的联系,例如,说一个程序产生的结果是「正确」的,就是给出了一个有关该程序性质的说明性描述。在编程中存在着大量的研究工作,其目标就是通过一些技术,来设法证明一个程序是正确的。其根源就是行动性描述(程序是由它们构筑起来的)和说明性描述(它们可以用来推导出某些结果)之间的差异。有一个在当前程序设计语言设计领域中很重要的问题,就是所谓的「终极语言」,在这种语言中编程就是写说明性的语句,通过将解释器做得足够复杂,程序员描述了需要做什么之后,解释器就能自动产生怎样做的知识。一般而言这是不可能做到的,但在这一领域人们已经取得了巨大的进步。

1.1.8 过程作为黑箱抽象

一个过程定义应该能隐藏一些细节,使过程的调用者不必考虑和了解这些细节,而是作为一个黑箱来接受它。

过程的调用者不需要关心的细节之一就是过程中形式参数的名字,过程的形式参数是局部于这个过程的,一个过程的定义约束了它的所有形式参数,这样的名字被称为「约束变量」。如果在一个完整的过程定义中将某个约束变量统一更名,这一过程的意义将不会有任何改变。一个名字的定义被约束于的那一集表达式被称为这个名字的作用域,在一个过程定义中,被声明为这个过程的形式参数的那些约束变量,就以这个过程的过程体作为它们的作用域。

如果一个变量不是被约束的,我们就称之为「自由」的。如果在一个过程的定义中,将一个自由的变量的名字加入参数列表就会引起一个错误,因为这样就将一个原本自由的名字变成了约束的,使其捕捉到了一个错误的值。

我们也可以将一个过程的定义局部于另一个过程,使这个过程成为其的子过程或者说是辅助过程。子过程还可以共享父级过程的约束变量,在父过程被调用的时候,约束变量被与实际参数关联起来,变成了子过程的自由变量,这种方式被称为「词法作用域」。

计算机程序的构造和解释 是这样的一本书:它将大量编程中的基本技巧,用一本正经的语言讲出来,帮助你在构建大型软件时使用这些技巧来控制代码中的复杂性。而这些技巧的共性之一就是,将复杂的事物,通过隐藏细节的方式进行组合和抽象。我认为如果一个合格的程序员只需要读三本书的话,这本书便位列其中。

RP主机一岁啦

阴差阳错,我竟然卖了一年多的虚拟主机,目前越搞越大,一两百个用户,已经不是说停就能停下来了。

按照惯例,我要感谢一些人,虽然整个 RootPanel 是我独立编码的,但我要感谢所有来捧场的,来帮忙测试,来付费的朋友们。

通过 RP 主机,我也认识了很多朋友,事实上通过 RP 主机,很多有着同样爱好的人被联系到了一起。

前些天还有人和我说不要再熬夜了,注意身体;我说这和你有几毛钱关系;她说,八元钱一个月的关系呗。

美好回忆什么的就不谈了,以前谈过很多次了:

第二个部分通常是谈责任,但说实话我觉得我没尽到应尽的责任吧。

每当生活和工作上遇到闹心的事情,对 RP 主机的维护和客服方面就会有所松懈,经常懒得回答用户的问题,然后把责任推给 GFW, ISP, VPS 提供商,上游软件作者等等的。UPTIME 也一直很不理想,面板有很多 Bug 迟迟没有改等等。

说好的 RootPanel 3 又跳票了,对它的上线时间我已经不想再承诺什么了 …

所以我要在此向用户致歉,向背黑锅的 GFW, ISP, VPS 提供商和上游软件作者致歉。

同时送点福利,该日志在我博客和 QQ 空间的各前十个回复,每人送 30 天的 RP 主机。

然后再挑 6 个评论写得好的 RP 主机现有(曾经)的用户,分别赠书一本,主要是关于 Node, Go, 和 Python 的 Web 编程入门书籍,它们都可以运行在 RP 主机上。

不要笑,这一共价值 400 元钱呢。

RP 主机的未来,在我的计划,在 RootPanel 3 完成之后,RP 主机不会再有更多的功能了,它会保持一个 KISS 的样子,一个正经儿的 Linux 虚拟主机。

同时 RootPanel 3 也会略微提高使用门槛,以将一部分不够 Geek 的站和不够 Geek 的用户排除出去。

规模方面,未来可能止于 4 个节点,这是因为毕竟在政策方面有风险,很难做大。

而且毕竟是面向低端客户,偏公益性质,就凭我在运维和客服上花的时间,真的只是个辛苦钱。

说实话,就现在,RP 主机的目标群体已经离我有一定距离了,我的网站已经陆陆续续地移到了我私有的 VPS 上。

我觉得这不是一个好的事情,不吃自己的「狗食」,又没多少利益,结果可想而知。

今后 RP 主机会更加侧重用户之间的社区的建设,围绕着这个产品,聚集起一群年轻的 Geek.

也许当我有正式的工作,不再有精力维护的时候,也许我会转交给别人,让它保持它原来的定位,继续下去,当然,届时一定会给大家提供退款的机会。

至于 RP 主机的价格,我在这里保证,永远都不会再提高,而配置会按照市场价格变动,按摩尔定律估计也是只增不减。

没有当年那么宏伟的目标了

人一生就那么长,很多时候必须妥协——和时间妥协。

突然想起知乎上有两个问题:

  • 世间有那么多美丽的女子,可我只能得到其中一个,每想到此,总是郁郁不得欢。
  • 世界上有那么多好书好电影好动漫注定看不完,我们对这个事实该持何种态度?

还有一个回答:

客亦知夫水与月乎?逝者如斯,而未尝往也;盈虚者如彼,而卒莫消长也,盖将自其变者而观之,则天地曾不能以一瞬;自其不变者而观之,则物与我皆无尽也,而又何羡乎?且夫天地之间,物各有主,苟非吾之所有,虽一毫而莫取。惟江上之清风,与山间之明月,耳得之而为声,目遇之而成色,取之无禁,用之不竭,是造物者之无尽藏也,而吾与子之所共适。

扯远了,其实这篇日志是用来挖坑的,前面只是给我还没填的坑找个借口。

想来想去,有三个轮子是必须要造的,以至于零毫秒都要退后,不然以后都不好意思说自己会 C++.

操作系统,编译器,数据结构。

写一个操作系统的想法在我初接触编程的时候已经有了,当时和小伙伴们设想得很宏大,也许也是当时知道自己不可能实现吧。

现在虽然一个操作系统的图景在我脑中并不明朗,但是我已经很清楚去哪去查找这些知识了。

要写一个仅实现了最基本功能的操作系统并不难不是么,去年还刚刚有一本译自日文版的<30 天自制操作系统="">.

当然,没有当年那么宏伟的目标了,只是当成一个玩具来写而已,我只打算实现 4 个部分:内存管理,进程管理,文件系统,TCP/IP 网络。

前 3 个应该说没有什么选择的余地吧,都是一个操作系统的必须组成部分,而网络部分,我还是非常希望实现一下的。

我打算自己设计一种编程语言,当然,也是当成玩具来设计,一开始我打算 JSON Based, 后来想想,JSON 还是表现能力有限,目前对于语系还没太多想法。

编译器分三个部分,由语言至中间字节码,由字节码自本地代码,字节码的解释器。

打算不借助其他工具,完全自行实现,这个工作量应该和操作系统还是差不多的。

数据结构这个要简单多了,就是用 C 和 C++ 各写一遍常见的数据结构。

用原始的 Makefile, 再调研调研 C++ 库的二进制兼容性有多么不堪。

1237

精子生于 1995.11.25, 20 岁,英文 ID jysperm.

订阅推送

通过邮件订阅精子的博客日志、产品和项目的最新动态,精子承诺每一封邮件都会认真撰写(历史邮件),有想和精子说的话也可以直接回复邮件。

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-SA 3.0  授权发布。最后生成于 2017-01-07.