计算机程序的构造和解释

计算机科学是介绍计算机使用的？

区分所做的事和所用之物。

如何对计算过程进行形式化的表示，如何去解决问题，结合两者发展一套对问题处理过程精确表述的方法

举个例子，数学中的平方根的定义

$ \sqrt{x} $ is the $ y $ such that $ y^2 = x $ and $ y \ge 0 $

这是一个很清晰的定义，但只定义了平方根是什么，并没有说如何去求。

如何去求？

一个算法，牛顿迭代法。

问题，给一个正数 $ a $，求 $ x = \sqrt{a} $。

改写成一个求零点问题 $ f(x) = x^2 - a = 0 $，找到这个方程的根，即为 $ \sqrt{a} $。

步骤，

猜测一个 $ x_0 $，做切线 $ l_0 $，找 $ l_0 $ 和 $ x $ 轴的交点 $ x_1 $

在 $ x_1 $ 做切线 $ l_1 $，找 $ l_1 $ 和 $ x $ 轴的交点 $ x_2 $

···

直到满足要求。

根据上面的思路，可以推导出公式

$$x_{n+1} = \frac{ x_n + a/x }{2}$$

直观理解：当前猜测值为 $ x_n $，真值应该满足 $ x = a/x $，所以取平均。

牛顿法，二阶收敛。

一个算法：连续均值求平方根法。给一个猜测值 $ g $ 。不断求猜测值 guess 与 X/guess 的平均值

找一个 $ \sqrt{x} $ 的近似值

• 猜测一个 $ g $

• 求 $ g $ 与 $ x/g $ 的平均值来提升精度

• 直到精度满足要求

上面这个就是一个计算过程。

如何完成一项工作，对应的陈述性知识。之间的对照。

什么是一个计算过程？很难定义，很抽象，

活在计算机里可以操作计算机的计算机神(财神)，

名为程序的规则模式指导着这类过程的进行。

lisp 被设计用来指导过程的进行，语法几乎没有，思想型语言。

emacs

接下来的内容，形式化这种如有关“怎么做”的指令性知识，并实际应用起来。

这些是计算机科学的真正议题，并不是看怎么求平方根本身，

问题出现在当我们尝试构建非常非常大的系统时，程序可能会很长，长到没有人能一下理解发生了什么，

大的系统能搞出来是因为我们有在大系统中控制复杂度的技术。

techniques for controlling complexity

这些技术也是这门课会讨论的。

这也是计算机科学讨论的一个点。

除了计算机的，还有很多人在做复杂度控制相关的工作，如航班系统。

计算机科学不是现实的，如工程师设计物理系统，由能摸得到的部件组成，

计算机处理的是理想化的组件，程序员对将要组合在一起的程序和数据了如指掌，没有公差，没有温漂。在构建大系统时，在理想和现实之间，不会有太大的鸿沟。

并不教怎么写程序

回答的更本质的问题：

• 什么是程序？

• 什么是计算？

• 如何系统地构造“复杂系统”？

这本书讲的东西

“抽象”——以及如何用抽象构造系统。

计算模型，从函数到实现一个解释器。

解决人如何控制系统的复杂性。当系统变大时，靠抽象让系统不崩溃。