《计算机程序构造与解释》读书笔记（2）

「爱情、让人受尽委屈。」 2022-11-28 10:27 116阅读 0赞

#  #

### 文章目录 ###

*  
 *   *  1. 写在最前面
     *  2. 构造数据抽象
     *   *  2.1 原因
         *  2.2 数据抽象导引
         *  2.3 层次性数据和闭包性质
         *   *  2.3.1 序列作为一种约定的界面
         *  2.4 符号数据
         *   *  2.4.1 引号
             *  2.4.2 集合的表示
         *  2.5 抽象数据的多重表示
         *   *  2.5.1 带有标志数据
             *  2.5.2 数据导向的程序设计和可加性
         *  2.6 带有通用性操作的系统
         *   *  2.6.1 通用型算术包
             *  2.6.2 不同类型数据的组合
         *  2.7 思考
     *  3 碎碎念

## 1. 写在最前面 ##

「李白写过那么多诗，他自己会背吗？」

「像李白那么不羁的人，估计写完就忘，放不下的是我们俗人自己。」

写这篇笔记的时候，脑海里突然就浮现出了这句话。猜测跟我总是没办法完整的记住看过书的内容有关联性，但是突然就想通了，其实有的时候记住和忘记又有多大的关系呢？

## 2. 构造数据抽象 ##

> 所谓面向对象，对象是有行为的，所谓面向过程，实际上还是对象的行为构成了过程。

> 现在到了数学抽象中最关键的一步：让我们忘记这些符号所表示的对象。…… （数学家）不应该在这里停步，有许多操作可以应用于这些符号，而根本不必考虑它们到底代表着什么东西。—— 《思维的数学方式》

### 2.1 原因 ###

问：为什么在程序设计语言里需要复合数据呢？

答：为了简化流程，解耦，用同样大小的空间保存更多的信息。（ps 书中原文为——为了提升我们在设计程序时所位于的概念层次，提高设计的模块性，增强语言的表达能力。比如将程序中处理数据对象的表示的部分，与处理数据对象的使用的部分相互隔离的技术，就是一种常用的**数据抽象**方式。

> 注：数据抽象使我们能在程序的不同部分之间建立起适当的抽象屏障。

### 2.2 数据抽象导引 ###

数据抽象的基本思想就是「为每一类数据对象标识出**一组操作**，使得对这类对象的所有操作都可以基于它们表述，而且操作这些数据对象时也只使用它们」。发现没，其实很多时候，语法的出现都不是人空想出来的，而是更加符合使用场景的。比如 golang 的 interface 就是方便针对抽象提出的语法糖。

**选择函数和构造函数的定义**

> 在实际系统里，两个部分之间的界面将是一组过程，称为选择函数和构造函数。它们是基于具体操作之上提出的抽象操作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center]

后续部分的数据的抽象，将基于有理数的算术运算展开。希望实现基于有理数的加减乘除运算，比较两个有理数是否相等操作。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 1]

有理数算数运算中，我们使用序对这一抽象数据结构来表示有理数，使得上层无需记录分子和分母的位置。

### 2.3 层次性数据和闭包性质 ###

序对：提供了一种用于构造复合数据的基本「粘结剂」。

> 注：可以建立元素本身也是序对的序对。
> 
>  满足闭包性质意味着，通过它组合起来的数据对象得到的结果本身还可以通过同样的操作进行组合，而序对满足闭包性质。
> 
>  可以用序对来表示序列和树。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 2]

为了便于操作序列和树，所以其一般具有两种类型的操作：

*  基本操作：比如求序列长度、查询序列指定值是否存在、查询树的叶子节点的个数等操作
 *  高阶操作：映射操作，将某种变换应用于一个序列或者树的所有元素，比如将一个表中的所有元素按照给定因子进行一次缩放操作。

#### 2.3.1 序列作为一种约定的界面 ####

「序列作为一种约定的界面」是不是看完还是没懂它写的到底是啥意思？

其实就是抽象出不同程序的共性，然后用子模块化 + 序列传递数据的方式实现抽象。（ps 实在是想不出更好的写法了，不过配上下图，应该会很好理解

下面以抽象两个看似并无共性程序的例子来解释「序列作为一种约定的界面」。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 3]

抽象前后的代码描述如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 4]

> 注：代码在很多时候需要兼顾可读性和可执行性两种特性，从前后对比来看，明显抽象的方式更加易读和理解。

### 2.4 符号数据 ###

仅支持从数据出发构造起来的数据是不够的，为了扩充语言的表达能力，必须引入「将任意符号作为数据的能力」。

#### 2.4.1 引号 ####

如果 (define a 1) 中 a 代表 1， 那么想要表示 a 本身改用什么呢？

答：该用引号 ‘a 表示 a 对象本身，这应该就是值引用和指针引用的区别吧

#### 2.4.2 集合的表示 ####

集合就是一些不同对象的汇集，其中任何对象的出现不超过一次。那么如何设计一个集合呢？  
答：从数据抽象的观点看，我们在底层设计实现上有充分的自由，只要最后设计出来的数据能够实现集合的固定操作，比如，union-set、element-of-set ? 等

*  设计 1 ：集合作为未排序的表
 *  设计 2：集合作为排序的表
 *  设计 3：集合作为二叉树

> 注：数据对象的表示的选择会深刻影响到使用该数据的程序性能。所以在选择数据结构的时候，需要考虑
> 
> 读写的使用场景 + 插入和查询的的 O(?) 值 + 占用的存储空间
> 
> 「橘生淮南则为橘，生于淮北则为枳」，大抵这世间万物并无好坏、对错之分，很多时候只是角度不同罢了

### 2.5 抽象数据的多重表示 ###

复数的表示可以分为极坐标和直角坐标两种，而两种表示方式之间可以互相转化如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 5]

为了能够构造出一种抽象，无论负数底层使用的是哪种表示方式，在使用上都支持 add-complex、sub-complex、mul-complex、div-complex 四种使用，所以在构造上有两种具体的方式：

#### 2.5.1 带有标志数据 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 6]

为了实现带有标志数据，我们需要：

*  type-tag：rectangular (直角坐标系)，polar（极坐标系)
 *  contents：操作的参数
 *  attach-tag：以标志和实际内容为参数，生成出一个带有标志的数据对象
 *  带有标志位的实现：real-part-rectangular、real-part-polar

该种方式的缺点：

*  限制具体实现的命名不能重名，一般实现是加入带有标志位的后缀，比如 real-part-rectangular
 *  新增一种表示的时候改动大，假设除了极坐标和直角坐标系以外还有另外一种表示，则所有定义都需要改动

#### 2.5.2 数据导向的程序设计和可加性 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 7]

数据导向的程序设计就是一种使程序能够直接利用这种表格工作的程序设计技术。

> 注：前面是基于显示的类型划分，在算数运算和两个表示包之间操作的界面，而数据导向是将其实现为一个过程，它由操作名和参数类型的组合在表格中查找，以便找出应该调用的适当过程。

所以数据导向的具体实现需要：

*  抽象 get 和 put 过程用于查找、放置具体实现:
    
     *  (get <op> <type>)
     *  (put <op> <type> <item>)
 *  在 rectangular 和 polar 中分别实现复数的操作并将之 put 到全局的查找表中

> 注：具体代码示例参考书中的 P125

**消息传递**

既然表格可以按照行的维度进行抽象，那么也可以按照列的维度进行，按照列的维度，我们称之为消息传递。具体代码实现如下：

(define (make-from-real-imag x y)
      (define (dispatch op)
        (cond ((eq? op 'real-part) x)
              ((eq? op 'imag-part) y)
              ((eq? op 'magnitude)
                (sqrt (x (square x) (square y)))
              ((eq? op 'angle) (atan y x)
              (else
                (error "Unknow op -- MAKE-FROM-REAL-IMAG" op))))))

### 2.6 带有通用性操作的系统 ###

#### 2.6.1 通用型算术包 ####

一个支持 + 、- 、\*、/ 的使用了数据导向的方式实现的算数包，具体实现参考 P129。

#### 2.6.2 不同类型数据的组合 ####

思考一个问题：为什么高级语言都支持了类型强转呢？

或许看了 P133 应该会有答案。（ps 提示抽象

### 2.7 思考 ###

写到这里突然想到一个构造复数包的另外一种解决方式，在构造的时候统一先将极坐标系的入参转成直角坐标系，然后在后面均按照直角坐标系运算是不是也阔以？

额，所以说看书重要的应该是思考过程吧。

## 3 碎碎念 ##

下次买花茶的时候要看好，茉莉花和茉莉花茶还是有区别的，但愿明天还能按时早起（ps 八月份的丧会和八月一起过去的，要加油

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/b9dbe3aac0db472db16df9781733e4e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/d50309cf08ad40ec948f69e80663b378.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/4000983e2fe2439b8291bbca37234cc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221124/f261178be79a42349978edf922b8e7da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221124/bb2f66f4929545aab8c7ebf8c6869876.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221124/b1068687e10747a986d7170a00546675.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221124/b7f36b4c19f34b88aa62dfe93b62d359.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3BoYW50b21fMTEx_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221124/433729167c60497cbce61c0355809bbd.png