SICP on lfkdsk's Blog

0x07：SICP 的魔法 - 元语言抽象

Mon, 18 Mar 2019 10:54:16 +0000

从这一篇文章开始就进入了 SICP 第四章的内容了，在前三章的内容之中我们接触了 数据抽象，过程抽象，模块化 三个，第四章的内容主要就是实现了一个元循环解释器 (meta-circular) 并对其进行不断地改造引申出别的问题。从篇幅内容来看这一章的主要内容反倒是对当时初读的我最为简单的，因为在学过编译原理的相关课程之后，笔者已经尝试使用了自举的方式实现了一些基于 JVM 的编程语言(这里也建议大家在学习理论的同时也要加强知识的运用，否则没有实际的使用过很多知识就不是那么立体)。本章我们对这个 Scheme 求值器的具体实现不会介绍的特别具体，毕竟书上已经把全部代码都贴上去了，这里更想关注一些引申的问题。

在之前的篇幅之中我们讨论了很多和程序设计相关的内容，主要研究的三个内容是：

数据抽象：如何组合程序的基本元素，构造更复杂的结构
过程抽象：如何将复杂的结构抽象出高层组件，提供更高维度的组合型
模块化，通过高抽象层次的组织方法，提高系统的模块性

通过这些手段已经足够我们设计大部分程序了，但是现实世界中遇到的问题可能更为复杂，或者可能类似的问题出现在同一个领域内。这时候我们可能就要在程序之中引入 DSL(领域内语言)了。本质上来讲我们引入 DSL 就是通过语言设计，为程序提供一种 语言层的抽象 ，来进一步提高我们程序的模块化。

元语言抽象

这节之中我们会试着用 Scheme 来实现一个 Scheme 的解释器，用一种语言实现其自身的求值器，称为元循环（meta-circular）。这里我们可以复习一下 3.2 节之中出现的求值模型，其中的求值流程分成两步：

求值组合式（非特殊形式）时
- 先求值组合式的各子表达式
- 把运算符子表达式的值作用于运算对象子表达式的值
把复合过程应用于实参，是在一个新环境里求值过程体
- 新环境：过程对象（里环境指针指向）的环境加一个新框架
- 新框架里是过程的形参与对应实参的约束

这两个步骤构成了 Scheme 求值的基本循环，这两个步骤也是能相互调用和递归 (自己递归或相互递归。求值的子表达式可能要应用复合过程，过程体本身通常又是组合式)，逐步规约到：

符号 (从 env 里面取值）
基本过程（直接调用基本过程的代码）
值类型 (primary type 直接取值)

以上的两个步骤可以被抽象为过程 eval 和 apply ，其中 eval 负责表达式的求值，apply 把一个过程对象应用于一组实际参数，这两者相互递归调用，eval 还有自递归。eval 和 apply 就像下图的这个像是太极图一样的图里，两者相互调用相互生成。

基础的递归解释器

核心 eval 和 apply

整个 eval 和 apply 的过程直接看代码实现就可以了，这里可以看到 eval 的过程就是接受一个表达式 exp 和一个环境变量 env ，根据表达式类型的不同进行分别处理。

0x06：SICP 的魔法 - 并发、时间与流模拟

Wed, 27 Sep 2017 10:16:16 +0000

在上一篇文章之中我们见识到了基于变动数据、内部状态的程序设计的能力，但是就像之前提及过多次的引用透明性的问题被打破，程序中引入了时间的概念，导致我们无论是求值顺序还是过程的运行都出现了一个时序性的问题，我们在 数字电路模拟 之中使用了一个 待处理表 的子过程，用来为我们的信号传播进行排序，通过模拟延时构造了程序的时序性。但是在现实世界中，我们不可能只通过一张表去排序构造顺序，现实系统中的对象都有更为复杂的同时的活动，为了构造这种更为现实的模拟系统，我们可能需要：

使用一组系统进行对同时发生的事情进行模拟
分解我们使用的模型，增强内部状态的演化，就是更为 模块化
能够支持多个进程的硬件支持

在多内核处理器普及的今天，硬件支持已经渐渐不是并发编程的难题了。但是并发编程的复杂性让然没有因为这个原因而降低难度。首先我们要承认正确的运用并行编程是有利的，能提升我们程序的运行效率和对硬件的利用率。

但是由于并发系统的时间的不确定性，两个同时运行并有所依赖的进程，我们并不能确定什么时候某个能运行完，而一个又不能对另一个的结果进行无限的等待。还有就是资源获取的问题，两个并行的程序如何对资源进行管理，比如第三章开始的那个例子，从银行取钱，如果无法控制程序对资源的有效管理就可能造成两个人同时使用一个账户同时取钱，都能取出来的情况出现。

这一节会谈及和并发相关的内容，对于有编程理论经验的同学，这并不是什么复杂的理论内容，其中涉及到的时序控制、锁和信号量等等的知识都是能在各种 OS 相关的课程和书中了解到的知识。

并发和时间

时间是一种设施，发明它就是为了不让所有事情都立即发生。

从抽象的角度来看时间就像是加在事件上的一种顺序，一件事情发生比另一件事情发生的早，只是事件顺序的相对关系，这个过程听起来能够非常原子的控制，但是本身事件还会消耗时间。这就引出了并发带来的一些问题，之前也已经提到了，来自于对相同资源的控制问题，和操作的顺序问题，解决这个问题我们就是在解决程序的 正确性 和 健壮性 的问题，通常我们可以这么去理解程序的正确性：

并发运行不受外界的影响
运行的表现要和不进行并发程序的状态是一样的

并发控制

对正确性的保证其实就是在做和 并发控制 相关的工作，其实质就是对并行操作进行一定的控制，书中谈到的很多策略其实在做开发中都是经常见到的：

禁止所有共享资源的并行操作

Tips :

锁粒度：简单说就是指不允许并行运行的加锁区域。

其实典型就是加了个锁，但是问题也比较明显，书中的反面 Demo 明显是一个锁粒度设定非常大的例子，这也是这种方案的一个比较突出的缺陷，并不是所有的时间都需要禁止并行进行。很多操作并非互相干扰的，比如非常常见的 读写分离 锁就是这样，我们很多时候对读操作和写操作的要求不同不能一概而论。

允许不互相干扰的并发

书中提到了另一种控制方式，是对一种想法的一种改进，这时候我们允许对很多的不互相干扰的并发执行，但是对结果的要求仅仅期望与某种顺序的运行方式相同，这样会有另一个方面的问题，并发结果有很多种，我们没办法对其结果进行预测。

串行控制器

串行化控制器的思路就是，程序可以并行执行，但是其中也有时序性的要求的部分，这部分无法并行执行程序的部分就靠一个控制器，将所有的执行过程通过一个集合控制起来，同一个时间段只会有一个过程在执行。最简单的应用我们可以借助共享变量去理解，同一个时间段可能有很多个进程在请求同一个资源，但是同时只能有一个进程能够获得这个资源，其余的将在等待队列中等待：

通过对程序的分组的方式来禁止不正当的并发行为，并且可通过程序控制将某个方法设置为 串行化 的方法。

我们引入一个内部方法 make-serializer 去提供这个是过程串行化的功能，make-serializer 接受一个过程作为参数返回同样行为的过程，参数与原过程保持一样，但保证其执行被串行化，我们可以继续使用之前的 make-account 的例子：

(define (make-account balance)
 (define (withdraw amount)
 (if (>= balance amount)
 (begin (set! balance (- balance amount)) balance)
 "Insufficient funds"))
 (define (deposit amount)
 (set! balance (+ balance amount))
 balance)
 ; 引入内部过程 make-serializer 
 (let ((protected (make-serializer)))
 (define (dispatch m)
 (cond ((eq? m 'withdraw) (protected withdraw))
 ((eq? m 'deposit) (protected deposit))
 ((eq? m 'balance) balance)
 (else (error "Unknown request -- MAKE-ACCOUNT" m))))
 dispatch))

可以看出我们引入了内部过程，通过对每个向外暴露的方法包装一层方法。

0x05：SICP 的魔法 - 实例:数字电路模拟

Tue, 08 Aug 2017 00:16:16 +0000

在第二章我们学到的和 数据抽象 相关的知识指出，如果想构造数据抽象，我们需要两个部分：

创建构造函数包含数据
创建选择函数分派数据

但是在经过了解了第三章相关的 模块化、状态、环境 的知识之后，我们认识到了新的问题，在实际编程之中，需要依赖程序的状态进行编程，那么程序中就要根据我们的环境求值的方式进行计算，那我们在重新设计和模拟系统大的时候就要多考虑几点了：

在系统中我们带状态的数据抽象
创建 改变函数(mutator) 去对数据进行重新修改

基于变动的模拟

在构建复杂的系统之中，我们最先面对的部分就是关于 同一性 的知识，这部分知识我们已经在上一章的 同一性发生了变化 的那个小节中简单的讨论过一次，我们可以在这个再重新讨论一下 共享和相等 的知识。

共享和相等

我们通过引入赋值的方式为系统引入了状态，但是造成了引用透明的危机，我们没办法再通过相同的结构来判断对象西相同，两个相同结构的对象并不能确定两个对象是否相同：

(define x (list 'a 'b))
(define z1 (cons x x))

我们定义了这样的一个结构，x 是'a 和 'b 组成的序对，然后 z1 是由两个 x 的组成的序对，我们还要在另外定义一个 z2：

(define z2 (cons (list 'a 'b) (list 'a 'b)))

这两个结构的定义起来，看起来的结构是一样的：

这里我们能看到放置 'a 和 'b 两个序对中的节点都指向了同一个节点，这是因为在 Scheme 中符号引用是共享的，因而他们都指向了同一个节点。但是很明显虽然 符号引用 都指向了同一个节点，但是整体的结构是两个结构指向了两个结构，直接使用：

(eq? z1 z2)

的结果肯定是不相等的，这意味着我们每次使用 cons 方法结成一个新的序对都是生成了一个新的对象并返回的是可操作该对象的 指针/引用 （虽然 Scheme 中没有显示的这种概念）。

这时候我们需要考虑另一个问题，就是在整个 数据抽象 都是不可变的情况下，我们对于数据结构是否使用了同样的引用是不可知的，但是当我们引入赋值我们共享的数据因为使用了同一个贡献的结构而变得复杂起来，修改其中的一个会导致另一个收到影响。

0x04：SICP 的魔法 - 模块化、状态、环境

Sun, 23 Apr 2017 15:37:48 +0000

现在我们终于到了 SICP 的第三章的内容了。就个人而言我觉得 SICP 的前三章都在着眼于构建各种层次的抽象系统，三章以后的内容才是 SICP 本身比较精髓和有趣的内容了。但是万丈高楼平地起，正是之前的这些和 “抽象”、“思想” 有关的东西构建了我们在后几章学到的解释器系统。

前两章我们见识到了 Scheme 在两个主要方向上的抽象能力。我们在第一章中学到了和过程抽象有关系的知识，我们把他认定为 Scheme 系统的第一公民，看到了各种高阶函数组合起来的魅力。在第二章我们主要讨论的问题是如何进行数据抽象，从一个 “有理数” 的 Demo 入手，建立了抽象屏蔽的系统层次，我们还引入了符号数据，进一步提升了运算的抽象层次，求导等写起来很麻烦的程序都可以借助符号数据来轻松实现。之后我们还见到了通过 dispatch 使用过程保存了对象的状态，学到了使用消息传递的构建方式，等等很多的和 “抽象” 有关的知识。

我们确实通过以上的知识，在上一节末构建了一个通用操作的复数系统。但是对于一个更为拟真、更为复杂的系统的时候，以上或是计算、或是对模型抽象的知识就显得远远不足了。我们还应该需要一系列模式或者是说原则去规定去构建这整个系统。换句话说，我们要学习如何去模拟这个世界。

模拟真实世界？

很多语言的设计者或是系统的实现者一直致力于让某种编程语言实现的系统去拟真现实世界，从中诞生了很多相关的思想和技术，OOP、OOC 还有各种设计模式都是这种努力的产出。另外很多语言也在致力于语法语义化，试图让编程语言 “看起来” 更像自然语言。

我们如何模拟世界

我们在学习很多 OOP 的语言的时候，都会讲很多 OOP 设计的好处，其中几个优点都有类似的特点，就是说 OOP 实际上是对现实世界的一种模拟，从开发人员的角度来说编写容易思考，而且从系统实现上也比较贴近现实。

在实现中我们可以从这两个角度去实现：

我们把现实中的每一种实体抽象为一个对应的程序对象（当然还可能会提取出对对象的抽象：类）
把每个现实中实现的具体方法模拟为一个程序中对应的活动。

通过对 “对象” 和 “活动” 的拟真，我们就可以用程序去对现实世界进行模拟。

我们遇到了一些问题

可以通过上面的两条去完成从现实到程序的一种转化。但是我们明显发现了一些问题，因为现实世界纷繁复杂，每时每刻的每个实体都在发生着不同的变化，而且每个实体都在发生着不同的动作，相互之间还有大量的交互，如果全部用程序去实现和模拟难以实现。

因而我们希望在程序在具体的实现之中，不要有大范围的甚至是全局的数据变化（这不好管理），我们希望把对象的增删修改、活动的产生消亡限定在一个有限的局部内。这样我们的整个系统会被分为不同的小的部分和结构，我们就把整个系统进行了分解的操作。

高内聚和低耦合

高内聚和低耦合是我们经常听到的设计方式，这样一个使用 模块化 的方式，其实是对这种设计思路的一种实践。高内聚是在说模块内聚化，功能内聚在对象之中，只留出相应的接口，使用接口进行交互，降低模块相互的耦合。

对象的世界

从 对象 的角度上来看，世界是什么样子的呢？对象的世界本质上是由一大堆对象组成的，对象有自己的属性和状态，随着时间的流逝，对象有一系列的状态的变迁。为此我们要通过一种方式去记录这个状态，通过这个被记录下的状态，我们能表现出这个对象的变化规程，而且还可以通过这个状态去继续计算对象的一系列后续的状态。

通过以上的这一系列的对 对象的世界 的描述，我们可以很容易的发现，我们描述的这种模块化、对象化的设计方式，其实和我们曾经学过的 Cpp、Java、CSharp 的世界非常的相近。我们从上帝的视角，把整个计算系统分解成对每个对象的计算的上去，用它们模拟真实系统中对象的行为。

但是对上面我们提到的那个 状态的变化 我们会发现，我们缺少一个我们很熟悉的东西——赋值 ，下面对对象世界的展开讨论就要从 赋值 这个基本操作开始谈。

0x03：SICP 的魔法 - 符号演算和数据表示方法

Mon, 20 Mar 2017 16:24:51 +0000

符号数据

有过CPP，Java等 OO 语言编程经验的人，肯定对基本类型和各种封箱的引用类型的区别有很大的感触。符号数据是什么，在这里的开始，我们可以先粗浅得把他理解成对象的引用，当然 Scheme 中的符号数据和这个还是有很大的区别的，理解这个符号我们可以先举一个这个例子：

两句话就能看明白 Symbol 和 Value 的区别，第一句话让我们说我们最喜欢的颜色，第二句是说“你最喜欢的颜色”。自然语言中能区分词语本身和词语的含义的不同，Scheme 中也有类似的机制。

表示符号数据

在 Scheme 的解释器中，我们之前已经了解到了，解释器就是一个不断接收数据的 eval() 循环：

每当我们输入表达式，就会接到表达式的返回值。同时我们还知道了，块级作用域的的实现本身是通过层层的 Map 来实现的，那我们只需要一个过程从对应的作用域表里面取出对应名字的引用就可以实现符号数据了。在 Sheme 中我们通常会使用 ' 符号代表这个值是一个符号类型而非基本类型：

> (define A 10)
> A
> ; Value: 10 使用的是基础类型
> 'A
> ; Value: a 使用的符号类型

但是直观上来看这个引号似乎破坏了 Scheme 中的语法，如果为了 ' 在解释器里单独实现一套机制难免得不偿失，而且是一种给解释器开洞的行为。但实际上在 Scheme 中这个问题被很轻松的解决了，' 本身实际上是 (quote x) 的一种语法糖。

Tips : eq? 和 equal? 和 symbol?

eq? 判断是不是一个引用

equal? 判断字面是否相等

symbol? 判断元素是不是符号

符号求导

书中讨论了简化版的求导函数，导函数完全由乘积和求和合成：

$$ \frac{dc}{dx} = 0 \ \frac{dx}{dx} = 1\ \frac{d(u+v)}{dx} = \frac{du}{dx} + \frac{dv}{dx} \ \frac{d(uv)}{dx} = u(\frac{dv}{dx}) + v(\frac{du}{dx}) $$

0x02：SICP 的魔法 - 数据抽象、层次抽象

Sat, 11 Mar 2017 18:17:35 +0000

在第一章里面，我们已经见识到了过程抽象的魔法，一个过程描述了一系列数据的计算过程，但本身又是一种元素可以出现在程序的任何部分，所以说过程是一种抽象，我们在使用的时候不需要知道任何和具体实现有关的东西，只需要调用我们已经定义好的过程就行了。

与此相类，数据本身也可以作为一种抽象，我们在之前接触的数据都是一些简单的数据，所以可能没什么感受。但是数据也可以包含不止一种的信息，使用的时候隐藏具体的实现细节，具体使用的时候又能作为元素出现在程序任意的位置，因此数据也是一种抽象。

有过 OO 语言经验的同学可以借助类的概念理解一下以上的概念

但是类的概念是无法完全概括的哦～

数据抽象

我们从最简单的数据抽象开始，首先说最小的数据抽象集合 —— 序对。

序对

要实现数据抽象首先要有能把数据打成一个包的方法，我们叫它构造函数，还应该有能把数据从捆中取出来的方法，我们叫他选择函数。

在 Scheme 中提供了能实现这些方法的 API:

Function Name	Usage
( cons p1 p2)	能把两个参数打包成一个对象
( car x )	能从 `cons` 打包出的对象取出其中的第一个数据
( cdr x )	能从 `cons` 打包出的对象取出其中的第二个数据

对于能非常方便构建 class 或是 struct 这样的数据结构的其他语言的使用者来看，这个序对的作用实在是微乎其微，但是大的抽象模式都是从最小的抽象方式开始的，我们这里使用序对也只是为了演示 Scheme 的抽象能力。

如何定义有理数？

这看起来似乎不是个问题，因为语言都会原生支持各种类型的浮点数，能轻松的用来表示有理数，但是请先忘了有关这方面的知识，单纯考虑当我们的系统只能支持整形数据的时候我们应该怎么表示有理数。

从上一小节的序对的知识出发，我们很容易找到答案，我们可以把有理数的小数点前后的部分，分别用一个整形数据来表示，再把他们用 cons 打包，当进行计算的时候再拆开计算就可以了。

所以我们对于有理数的定义甚至都可以用上面的函数来表示：

Function Name	Usage
( make-rat x y )	生成有理数 x.y
( number bundle )	获取 x.y 中的 x
( denom bundle )	获取 x.y 中的 y

写实现也很简单：

0x01：SICP 的魔法 - 过程的求值计算和高阶过程

Mon, 27 Feb 2017 12:01:15 +0000

过程的求值计算

这里面我们先来介绍一种最为简单、通用的求值模型，代换模型并不能概括全部的求值方式，但是我们先从这个开始。

代换模型

通用的表达式计算模式，描述起来其实非常简单，先求出各子表达式的值，找到要调用的过程的定义，用求出的实际参数代换过程体里的形式参数，再对过程体进行求值，本质上一种使用等价性的表达式的拆分机制，比如下例，是对一个平方和函数进行计算的详细步骤：

(define (sum-of-squares x y) 
			(+ (square x) (square y)))
; sum-of-squares 求两个数的平方和
(define (f x) (sum-of-squares (+ x 1) (+ x 2)))
(f 5) 
(sum-of-squares (+ 5 1) (* 5 2)) ; 注意这两行，首先算出来形参
(+ (square 6) (square 10)) 
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

Tips: 上面的代换方式又被称作应用序的计算方式，这也是 Scheme 解释器的计算方式，除此之外，还有一种被称作正则序的计算方式，正则性和上面不一样的地方在于，它不会先计算出调用过程的形参，反倒是一定要把整个表达式最小化到所有的东西都能直接计算的程序(摊开了的感觉):
(f 5) 
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1)) (square (* 5 2)) ); 注意这两行这里没往下计算形参
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10)) ; 反倒是都摊开了才开始进行规约
(+ 36 100)
136
PS: 有个很简单的Demo能证明所用的解释器到底用了什么计算顺序:
(define (p) (p))
(define (test x y)
 (if (= x 0)
 0
 y))
大家可以想想正则序和应用序分别会有什么结果。

0x00：SICP 的魔法 - Scheme 基础和黑盒抽象

Tue, 21 Feb 2017 22:22:14 +0000

作者：刘丰恺

作者博客：若梦浮生

转载需征得作者本人同意

计算机科学的内容包罗万象，其中的经典的课程也是不胜枚举。但是在这其中SICP(Structure and Interpretation of Computer Programs)绝对是其中的经典和翘楚，在2008年以前SICP的MIT6.001课程历来是CS相关专业必修入门课程。

SICP的核心内容是什么呢？众说纷云，有人说是一本有关Lisp／Scheme的书主要讲函数式编程的思想，有的说是一本有关解释器构造的入门书籍，和我们学过的龙书挂钩，但就我个人而言，SICP作为一本入门书更多的不是担负起介绍某一方面具体的知识的重任，而是从多个角度去教一个初学者从程序抽象、理解工程架构、学习DSL的构建方法……，不单纯介绍一方面的知识而是完备的形成一个闭环的去像你介绍什么是Computer Science。相比于这些当初选用MIT Scheme现在使用Python，不过是最大程度上减小编程语言本身的复杂度对学生理解的影响，个人觉得无足挂怀。

SICP的各个版本的封面，都选择了魔法师作为其中的主要素材，这里也作为我这个系列的名字，让我们一起领略SICP的魔法。

学习之前

在正式开始之前，我们先简单的了解几个问题。

我们如何看待Computer Science？

很惊人对吧，第一次看到这个NO COMPUTER NO SCIENCE的时候我也是被这种说法吓到了。但是对于这个说法的讲解倒也是能自圆其说。

首先是NO SCIENCE，作者在课上说CS不像是一门科学更像是一门艺术或者是工程。工程好理解，但是艺术听起来就很玄之又玄的感觉，但是这里笔者想谈谈自己的感受，对于笔者个人而言，编程像是一种写作，就想写作当前这篇文章的感觉是一样的，代码／文字从手中流淌出来，形成程序／文章，两者可以说是近乎相同的。

再说这个NO COMPUTER，作者认为这门学科也不是完全和计算机有关，就像几何学不一定合圆规和量角器有关系一样，文以载道，计算机只是帮助我们实现这些功能的工具而已，这也就是为什么变成会被称作和魔法相同，编写代码／编写咒语，即使我们生活在一个没有计算机的魔法世界，我们仍然能学习这门课程（当然不会再被称之为CS了）。

定义和过程的理解

我们首先来看这个公式，这是一个对于平方根的定义，和我们在数学书上学到的一样。给我们一个y的值我们可以很方便的确定是不是x的平方根，但是这个公式并不能告诉我们平方根到底是怎么求的，也就是说上文只是在告诉我们平方根到底是什么。

但是如果要涉及怎么求平方根，我们就需要借助牛顿迭代法了，通过猜测一个数字，再根据求出商，两者相加求平均值作为下一次的平方根猜测量，这样逐步逼近到达一个最接近的数值就是x的平方根。

如下求 2 的平方根

猜测量	商	平均值
1	2/1 = 2	(2 + 1) / 2 = 1.5
1.5	2 / 1.5 = 1.3333	(1.5 + 1.3333) / 2 = 1.4167
1.4167	2 / 1.4167 = 1.4118	(1.4167 + 1.4118 ) / 2 = 1.4142
1.4142	…

这个使用牛顿迭代法的步骤就可以称作为是过程，因为它解决了我们如何求解平方根这个问题，告诉了我们怎么做。