计算机程序的构造和解释

现在到了数学抽象中最关键的一步：让我们忘记这些符号所表示的对象。(数学家）不应在这里停步，有许多操作可以应用于这些符号，而根本不必考虑它们到底代表着什么东西。 邱奇数可以帮我们充分理解上面这句话和数据抽象的含义,于是符号语言表示自然数和和四则运算表达如下：

(define (inc n)
  (+ n 1))
(define zero
  (lambda (f zero)
    zero))
(define one
  (lambda (f zero)
    (f zero)))
(define two
  (lambda (f zero)
    (f (f zero))))

(define (add x y)
  (lambda (f zero)
    (x f (y f zero))))


(define three (add two one))

;; 3+3
(define (multiply x y)
  (lambda (f zero)
    (x (lambda (z)
         (y f z))
       zero)))

(define four (multiply two three))
(four inc 0)

邱奇数可以很好的将数学计算，用符号演算构造出来，并得到所有（可计算的）“自然数”（符号）。（将操作应用于符号，而不必考虑他们到底代表什么东西） 其实邱奇的lambda calculus建立一个强大的符号演算系统，利用这个（抽象）符号操作概念可以建立一个强大的形式语言，从而实现一个图灵等价的计算模型。符号演算可以模拟出数学世界里的所有计算模型，而数学计算只是这个形式语言的其中一个具体罢了。 关于邱奇-图灵理论，停机问题，Y 组合子，不完备性定理，可以参考一下2篇好文： http://blog.csdn.net/pongba/article/details/1336028 http://blog.csdn.net/pongba/article/details/621723

原文 P3

将数值作为"简单数据"看待实际上完全是作为一种虚张声势.事实上,对于数值的处理是任何程序设计语言里最错综复杂而且也最迷惑人的事项之一.其中涉及的典型问题包括: 某些计算机系统区分了整数(例如2)和实数(例如2.71).那么实数2.00和整数2不同吗?用于整数的算术运算是否与用于实数的运算相同呢?用6除以2的结果是3还是3.0?我们可以表示的最大的数是多少?最多能表示的精度包含了多少个十进制位?整数的表示范围与实数一样吗?......

tertio注解:这里的难点关键在于理论模型和实现模型的关系,一般认为关于数的理论,是无法直接用于计算机的,要么无法表示,要么效率低下,但实际上如果构造出理论到具体内存位的映射,有办法解决这个理论与实践的两难问题.原文 P10

虽然代换模型看起来似乎非常简单,但令人吃惊的是,给出代换过程的严格数学定义却异常复杂.问题在于,用作过程中形式参数的名字,可能会与该过程可能应用的那些表达式中的(同样)名字相互混淆.在逻辑和程序设计的语义学文献里,关于代换的充满错误的定义有一个很长的历史.

tertio注解:这里应该指的是term rewriting,一种非常类似人的纸面推导和证明的方法.至于这里的名称混淆问题,可能涉及到高阶的模式匹配,但不是没有办法解决的.原文 P14

说明性描述和行动性描述有着内在的联系,就像数学和计算机科学有内在的联系一样.举个例子,说一个程序产生的结果"正确",就是给出了一个有关该程序性质的说明性语句.存在着大量的研究工作,其目标就是创建起一些技术,设法证明一个程序是正确的.在这一领域中有许多技术性困难,究其根源,都出自需要在行动性语句(程序是有它们构造起来的)和说明性语句(它们可以用于推导出某些结果)之间转来转去

tertio注解:这是语言之谜的一个复杂而又关键的地方,此时此刻做某事,这是一个行动性语句,然而上升到更高的层次,你又可以给出一个命题,当某时某刻做某事之后,某个命题成立.在这段注释省略掉的后半段,这种甚高级语言试图全部用说明性语句来解决问题的方式是不对的,这个思路忽视了人类的语言特征:人类常常从不同的层次描述同一个问题,因而行动性描述和说明性描述都是需要的,而且,在计算机语言中,只有为这两种描述提供转换方法,才能符合人类的思维特征.原文P65

术语"闭包"来自于抽象代数,在抽象代数里,一集元素称为在某个运算(操作)之下封闭,如果将该运算作用于这一集合的元素,产生出的仍然是该集合里的元素.然而lisp社团(很不幸)还用术语"闭包"描述另一个与此毫不相干的概念.闭包也是一种为带有自由变量的过程而用的实现技术.本书没有采用闭包这一术语的第二种意义.

tertio注解:用抽象代数来理解lisp和函数式的都是棒槌.原文P136

...开发出一种有用的,具有一般意义的框架,以描述不同类型的对象之间的关系(这在哲学中称为"本体论").看来是一件极其困难的工作.在10年前存在的混乱和今天存在的混乱之间的主要差异在于,今天已经有了一批各式各样的并不合适的本体理论,它们已经被嵌入到数量过多而又先天不足的各种程序设计语言里.举例来说,面向对象语言的大部分复杂性---以及当前各种面向对象语言之间细微的而且使人迷惑的差异的核心,就是对类型之间通用型操作的处理....事实上,我们的猜想是,如果没有知识表示和自动推理工作的帮助,这些问题是无法仅仅通过计算机语言设计的方式合理处理的.

tertio注解:吐得一口好槽,最后一句话尤其关键,一下子就点明了构造哲学意义上的本体的方向----知识表示与自动推理.现有的走向前台的计算机语言,完全没有达到这个层次.原文P148

在处理变动数据对象的共享问题时,最微妙的地方正好就反应了3.1.3节里提出的有关"同一"和"变化"的基本问题.我们在那里说过,如果希望这个语言里容许做修改,那么每个复合对象就必须有一个"标识",这应该是某种不同于构造起它的那些片段的东西.在lisp里,我们所认为的"同一"也就是检查课题之间的eq?,采用指针相等表示.这是因为在大部分lisp实现里,一个指针本质就是一个存储地址,在这里"解决"对象标识的方式,是假设数据对象"本身"也是一些信息,存储在计算机中某一些特定的存储位置,对于简单的lisp程序而言,这也就足够了.但是这并不是解决计算模型中"同一"问题的一般性方法.

tertio注解:哲学上的同一性问题在古希腊时代就得到了深入的思考,"赫拉克利特的河流","特修斯之船"...而且从罗素的指称到克里普克的专名理论,哲学家们已经给出了很好的答案.在计算机程序设计中,解决同一性的方式就得以这些理论作为基础,而不是搬弄数学.原文P247

物理中也类似,当我们观察一个正在移动的粒子时,我们说该粒子的位置(状态)正在变化,然而,从粒子的世界线的观点看,这里根本就不涉及任何变化

tertio注解:这是前面提到的语义层次的问题,当我们和粒子处于同一个世界中的时候(正在观察),粒子的状态随真实的时间发生变化,而当我们为其建立运动理论的时候,就可以把粒子的状态和时间之间建立对应关系,这时候,这里所说的时间无非是一个坐标轴而已,不是真实的时间,因而也不涉及什么变化.函数式通过将状态变化当做流或其他结构来处理,避免了状态变化和赋值的问题,但问题是,一旦系统有了真实的IO,就很难再保持纯粹了.原文P248

对象模型对世界的近似在于将其分割为独立的片段，函数式模型则不是沿着对象的边界去做模块化。当“对象”之间不共享的状态远远大于它们所共享的状态时，对象模型就特别好用。这种对象观点失效的一个地方就是量子力学，在那里，将物体看做独立粒子就会导致悖论和混乱。将对象观点和函数式观点合并可能与程序设计的关系不大，而是与基本认识论有关的论题。

tertio注解:这里提到量子力学可能不是一个恰当的类比。但同意，不回到最根本的认识论上，不足以解决这个问题。在这方面的探索，分析哲学家已经做出了大量的努力，是时候在计算机程序设计领域引入这些成果了。原文P248正文

本章开始时提出了一个目标，那就是构造出一些计算模型，使其结构能够符合我们对于试图去模拟的真实世界的看法。我们可以将这一世界模拟为一集相互分离的、受时间约束的、具有状态的相互交流的对象。或者可以将它模拟为单一的、无时间也无状态的统一体。每种观点都有其强有力的优势，但就其自身而言，又没有一种方式能够完全令人满意。我们还在等待一个大统一的出现。

tertio注解：大统一是可期待的，因为不论把世界看做什么，但自始自终我们无法摆脱的是所采用的语言和思维方式，一旦在计算机中构造出了在各个层次都符合思维规律的语言，大统一就不可避免了。原文P317

一般而言,匹配是一种代价高昂的工作,因为我们希望避免将完整的匹配应用于数据库里的每一个元素,通常可以通过将这个过程分解为快速的粗略匹配和最终匹配而达到加速的目的.其中的粗略匹配过滤数据库,为最终匹配产生出很小的一组候选.我们也可以仔细安排这个数据库,使得粗略匹配的工作在数据库的构造过程中完成,而不是等着需要找出候选的时候再做.这称为数据库的索引....

tertio注解:要略略纠正一下这个说法,匹配并不是一种代价高昂的工作,因为对每个元素进行匹配是必不可少的工作.而提高效率的方法,一方面是让搜索回答更少的问题(降低问题的难度),另一方面是避免重复的匹配.而在构造数据库时就可以做的那些粗略匹配,相当于是把大多数搜索所需要的匹配提前做完,从而在搜索的时候,避免这些重复的匹配工作.------从信息的角度讲,没有任何一个匹配是真正可以避免的

读书笔记第一章题解~ http://www.freopen.com/?p=10382第二章题解~最后两个通用系统的练习没写,代码量太大~ http://www.freopen.com/?p=10385第三章已经看完了,不过最近比较忙,练习需要等等再写~P.S.建了一个"计算机科学"的QQ群:20076724~欢迎加入!~很欢乐的写了一个C++版的解释器,各种泄漏内存.可以深入探讨一下,如果不存在赋值语句,应该可以保证永远不存在环结构,从而使用计数器来管理内存.

勘误，第一段的最后一行：『也就是说，当且仅当一个或门的两个输入信号之一为 1 时，其输出为 1 ，否则其输出就是 0 。』原文（http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-22.html#%_sec_3.3.4）：『That is, the output will become 1 if at least one of the input signals is 1; otherwise the output will become 0.』这里译者将 OR 的意思译成了 XOR 的意思了，正确翻译应该是：『。。。如果至少有一个输入信号为 1 ，那么输出为 1 ；否则。。。』