计算机程序的构造和解释

计算机程序的构造和解释读书笔记

构造抽象过程

本章内容是关于计算过程的基础知识，计算过程是存在与计算机的一类抽象事物，在其演化过程中，这些过程回去操作一些被称为数据的抽象事物，人创造出一些被称为程序的规则模式，用以指导这类过程的进行，从作用上看，就像是我们在通过自己的协作魔力去控制计算机里面的精灵。

程序设计中的基本元素

一个强有力的程序设计语言，不仅仅值一种指挥计算机执行任务的方式，它还应该是一种框架，使开发者能够在其中组织自己有关计算过程的思想，当描述一个语言的时候，就需要将注意力特别放在这一种语言所提供的，能够将简单的认识组合起来形成更为复杂认识的方法方面，每一种强有力的语言为此提供了三种机制：

• 基本表达式，用于表示语言所关系的最简单的个体
• 组合的方法，通过它们可以从比较简单的东西出发，构造出复合的元素
• 抽象的方法，通过它们可以为复合对象命名，并将它们当做单元去操作

在程序设计中，处理两种要素：过程和数据 ，非形式的说，数据是一种我们希望去操作的东西，而过程就是有关这些数据的规则描述，这样，任何强有力的程序设计语言都必须能表述基本数据和基本的过程，同时还需要提供对过程和数据进行组合和抽象的方法。

表达式

假设坐在一台计算机的终端前，用键盘输入了一个表达式，解释器的相应就是将它对这一表达式的求值结果显示出来。

那么可以键入的一种基本表达式就是数，更准确的说，键入的是由数字组成的表达式，它表示的是以 10 作为基数的数。

可以用基本的过程表达式，将数的表达式组合起来，形成复合表达式，例如

589

100 + 200

(-100)

像这种表达式被称为组合式，其构成方式就是用一对括号扩起来一些表达式，从而形成一个表，用于表示一个过程应用，在表里面最左的元素称为运算对象，要得到这种组合式的值，采用的方式就是将由运算符所刻画的过程应用于有关的实际参数，而所谓的实际参数也就是这些运算对象的值

将运算符放在所有对象最左边，这种表达方式称为前缀表示，这和常规数学表示有很大的差别，然而前缀表示有一些优点，其中之一就是它完全适用于可能带有任意个实参的过程，例如

(+ 21 35 12 7） = 75

(* 25 4 12) = 1200

这里运算过程不会出现歧义，因为运算符总是在左边，而表达式的边界也由括号界定。前缀表达式第二个优点是它可以直接扩充，允许出现组合式嵌套的情况，例如

(+ (* 35) (- 10 6) ) = 19

从原则来讲，对于这种嵌套的深度，对于任何语言都是没有难度的，但是这种表达式对于人来说，很容易搞错。

即使对于非常复杂的表达式，解释器也总是按照基本循环运作，从终端输入一个表达，对这个表达进行求值，而后打印得出的结果，这种模式被人说成解释器运行在一个 读取 – 求值 – 打印 的循环之中，这里没有必要显示的要求解释器打印表达式的值。

命名和环境

程序设计语言中一个必不可少的方面，就是它需要提供一种通过名字去使用计算对象的方法，将名字标识符称为变量，它的值也就是所对应的哪个对象。

例如在 JavaScript 中定义一个变量

​ const size = 20；

这里就会导致解释器将 20 和 size 进行关联，之后就可以通过这个 size 去访问引用值。

一般而言，计算得到的对象完全可以具有非常复杂的结构，每次使用他们的时候，就可以通过一系列交互动作，创建所需要的名字 – 对象关联，这种特征鼓励人们采用递增的方式开发和调试程序，在很大程度上，也提出另一个事实，一个复杂的程序通常由一大批相对简单的过程组成的。

从这里可以看到，我们可以将值与符号关联，而后又能提取这些值，这意味着编译器必须维护某种储存能力，以便保持有关的名字 – 值对偶的轨迹，这种储存被称为环境

组合式的求值

组合式的求值问题，解释器本身就是按照下面过程工作的

• 要求值一个组合式，需要做下面的事情：
  1. 求值该组合式的各个子表达式
  2. 将作为最左子表达式（运算符）的值的那个过程应用于相应的实际参数，所谓实参数也就是其他子表达式（运算对象）的值。

为了实现对一个组合式的求值过程，我们必须先对组合式里的每个元素执行同样的求值过程，因此，在性质上，这一求值过程，先对组合式里的每个元素执行同样的求值过程，因此在性质上，这一求值过程是递归的。

对于一个组合式，反复的应用第一步骤，即对各子项求值，重复这个过程总会将我们带到求值中的某一点，这里遇到的不是组合，而是基本表达式，例如数、内部运算符或者其他名字，处理这些基础情况的方式也有如下规定：

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

对于初学者，应该之处的关键一点就是，环境所扮演的角色就是用于确定表达式中各个符号的意义，在任何语言中，如果没哟关于环境的任何信息，那么说例如表达式（+ x 1）的值是毫无意义的，因为需要有环境为符号 x 提供意义，甚至需要为 + 提供意义，环境是具有普遍性的，他为求值郭恒提供了一种上下文，对于理解程序执行起着极其重要的作用。

复合过程

在任何一种强有力的程序设计语言中，这些东西包括：

• 数和算术是基本的数据和过程
• 组合式的嵌套提供了一种组织起多个操作的方法
• 定义是一种受限的抽象手段，它为名字关联相应的值

过程定义，这是一种威力 2 更加强大的抽象技术，通过它可以为复合操作提供名字，而后就可以将这样的操作作为一个单元使用。

在 Lisp 语言中可以这样定义一个函数，用来求一个值的平方

(define (square x)(* x x))

前面了解了一下前缀表达式，应该可以看懂吧。调用这个函数（不知道说函数对不对，书上没说这是个函数，书上叫复合过程）

(square 21)  得到值 441

(square (+ 2 5)) 得到 49 (+ 2 5) 是 7

得到了 square 作为基本构件，那么可以去定义其他过程，例如定义一个求两个数的平方根

(define (sum-of-squares x y))
  (+ (square x) (square y))

调用函数
(sum-of-squares 3 4) 得到值 25

继而又可以使用 sum-of-squares 去构建其他过程。

复合过程的使用方式和基本过程完全一样，实际上，实际上，如果人们只看上面的 sum-of-squares的定义，根本无法分辨出square就是像前缀表达式一样直接在解释器里，还是被定义为一个复合过程。

过程应用的代换模型

为了求值一个组合式，其运算符是一个复合过程的名字，解释器的工作方式将完全按照上面描述那样，采用与以运算符名为基本过程的组合式一样的计算过程，也就是说，解释器将对组合式的各个元素求值，而后将得到的哪个过程，也就是该组合式里运算符的值，应用于哪些实际参数。

实际上就是将表达式中的变量名换成实际的值的这一个过程。

Lisp 采用应用序求值，部分原因在于这样做能够避免对表达式的重复请求，从而可以提高一些效率，更重要的是，在抄书了可以采用替换方式模拟的过程范围之后，正则序的处理将变得复杂的多，而在另一些方面，正则序也可以称为特别有价值的工具。

条件表达式和谓词

至此，还没有办法定义一个过程，例如它能计算出一个数的绝对值，那么它要完成此事需要检查一个数到底是正数、负数、或者是零。而后依据不同的情况按照下面采取不同的动作

那么分析这种结构称为分情况分析，在 Lisp 里面右针对这类情况分析的特殊形式，比如 JavaScript 里面的条件表达式。而 Lisp 形式如下：

(define (abs x))
	(cond (> x 0) x)
		((= x 0) x)
		((< x 0) (- x))

JavaScript 里面就是

function abs(x) {
  if (x >= 0) {
    return x;
  } else if (x < 0) {
    return -x; // 负负得正
  }
}

上面的话用自然语言也很简单，如果一个数大于或者等于 0 那么他的绝对值就是他自己，如果小于 0，那么他的绝对值就是它的正数

在 List 中还有其他的表达式

(and (> x 5) (< x 10)) //逻辑运算，就是x 大于5，小于10
(define (>= x y))
	(or (> x y) (= x y))

实例： 采用牛顿法求平方根

求平方根的例子，

(define (sqrt x)
	(the y (and (>= y 0)))
		(= (square y)x))

函数与过程之间的矛盾，不过是在藐视意见事情的特征，与如何去做这件事之间，的普通性差异的一个具体反应，换一种说法，人们有时也将它说成是说明性的知识与性东西的知识之间的插件，在数学里，人们通常关心的是说明性的描述是什么，而在计算机科学里，人们通常关心行动性的描述，怎么做这个问题。

那么计算机是如何计算出平方根的，最常用的就是牛顿的逐步逼近法，这一方法告诉我们，如果对 x 的平方根的值有了一个猜测 y，那么就可以通过执行一个简单的操作去得到一个更好的测试，只要求出 y 和 x/y 的平均值，它更接近于实际的平方根

现在设法使用过程的语言描述这一个计算过程，开始时候，我们有了一个被开瓶费数的值，要做的就是算出他的平方根，和一个猜测值，如果猜测值已经足够好了，有关工作就完成了，若不然，就需要重复上述计算过程去改进猜测值，那么将这一基本步骤携程下面的过程

(define (sqrt-iter guess x)
    (if (good-enough ? quess x))
    	quess
    	(sqrt-iter (improve guess x)
                   x))

看不懂上面写了什么

局部名

过程是用户不必关心的实现细节之一，就是在有关的过程里面形式参数的名字，这是由实现者所选用的，也就是说，下面两个过程，定义应该是无法区分的：

(define (square x) (* x x))
(define (square y) (× y y))

这样原则，从表面来看非常明显，但是影响却非常深远，最直接的影响是，过程的形式参数必须局部有关的过程体

想想一下如果参数不是他们所在的过程体里局部的东西，那么参数之间就会产生混淆，如果这样，一个函数会被另外一个不想关的函数所影响，那么函数就不是一个黑箱。

过程的形式参数在过程体里扮演者一种非常特殊的角色，在这里，形式参数的具体名字是什么，其实完全没有关系，这样的名字称为约束变量，所以说，一个过程的定义约束了它的所有形式参数，如果在一个完整的过程定义里将某个约束变量统一换名，称之为自由 的，一个名字的定义被约束于的哪一集表达式称为这个名字的作用域，在一个过程定义里，被声明为这个过程的形式参数的哪些约束变量，就以这个过程的体作为他们的作用域

原来作用域有这么个来源，以前只知道什么是作用域，并不知道为什么有作用域和为什么作用域这么重要。

树形递归

一种常见的计算模式称为树形递归，作为一个例子，现在考虑斐波那契数列的计算，这一个序列中的每个数都是前面两个数之和

0,1,1,2,3,5,8,13,21…

那么皆可以将上面的计算斐波那契数列的递归过程

(define (fib n)
    (cond ((= n 0)0)
        ((= n 1)1)
        (else (+ (fib (- n 1))
         		(fib(- n 2))
                 ))
        )
    )

fib过程的每个调用中两次递归调用自身的事实

构造数据抽象

前面关注的是计算过程，以及过程在沉痼中所扮演的角色，在哪里还看到了如何使用基本数据和基本操作，怎样通过复合、条件，以及参数的使用将一些过程组合起来，形成复合的过程，还可以讲一个过程看做一类计算演化的一个模式，做了一些分类和推理，接下来将去考察更为复杂的数据，许多程序在设计时就为了模拟复杂的现象，因此他们就常常需要构造一些计算对象，这些对象都是由一些部分组成的，以便去模拟真是世界里面具有若干侧面的现象。

本章实现一个有理数算术系统，它将称为后面复合数据和数据抽象的一个基础，和复合过程一样，这里需要考虑的主要问题，也是将抽象作为克服复杂性的一种技术，下面将会看到，数据抽象将如何使我们能在程序的不同不部分之间建立适当的抽象屏障

在复合数据中，有一个关键性思想闭包的概念，–也就是说，用于组合数据对性的粘合剂不但能用于组合基本的数据对象，同样也可以用于复合的数据对象，另一个关键思想是，复合数据对象能够为混合和匹配的方式组合程序模块的方便界面

数据抽象引导

在构造更为复杂的过程时，可以将一个过程用作其中的元素，这样的过程不但可以看做是一组特定操作，还可以看做一个抽象过程，也就是说，有关过程的实现细节可以被隐藏起来，这个特定过程完全可以由另一个具有同样整体行为的过程取代，换计划说，我们可以这样造成一个抽象，他将这一过程的使用方式，与该过程究竟如何通过更基本的过程实现的具体细节相互分离，针对复合数据的类似概念被称为数据抽象，数据抽象是一种方法学，它使我们能将一个复合数据对象的使用，与该数据对象怎样由更基本的数据对象狗仔起来的细节隔离开。

实例 有理数的算术运算

假定我们希望做有理数上的算术，希望能做有理数的加减乘除，比较两个有理数是否相等，等等。

作为开始，我们假定已经有了一个从分子和分母构造有理数的方法，并且进一步假定，如果有了一个有理数，我们有一种方法取得了他的分子和分母，现在在假定的构造函数和选择函数都可以作为过程使用：

• (make-rat n d) 返回一个有理数，其分子是整数 n ，分母是整数 d
• (numer x) 返回有理数 x 的分子
• (denom x) 返回有理数 x 的分母