SICP 第二章(构造数据抽象)

复合数据

在实际的程序设计中(模拟数学或现实系统), 操作(过程)要应用到的数据往往不是一个单独的基本类型数据, 而是多个基本类型数据复合起来的: 例如分数是由分子和分母确定起来的, 单一的分子和分母都不能称为分数. 而将分子和分母以某种方式复合起来比单独管理分子和分母具有更强的可读性, 减少了编码中的精力消耗; 同时加强分子和分母之间的关系(分子和分母的关系应当强于这两个符号之于别的数据的关系)也符合某种(哲学上的)道理.

为此, 我们需要构造一种抽象使得这两个数据被复合起来:

• 首先要有构造函数, 将这分子和分母复合为另一个新的数据
• 然后还要有选择函数, 因为在实际操作中我们需要操作分子和分母本身(来模拟分数的运算)而不是分数本身
• 最后, 分子和分母及其操作应当符合某些规则(即数学上分数运算上的规则)

这就是复合数据的需求: 将数据定义为一组适当的选择函数和构造函数, 以及为了使得这些过程成为一套合法表示, 它们就必须满足一组特定的条件.

关于复合数据抽象的形式化定义有两种:

抽象模型方法: 基于某种已有的模型(如数学上的分数运算模型), 形式化定义一套新的”过程+条件”的数据定义

代数规范: 将数据的过程作为抽象代数系统中的元素, 利用抽象代数检查过程正确性

…在 Scheme 中, 可以用 cons 将两个符号组合为一个序对: (define foo (cons a b)), 并且用 (car foo) 取出 a, 用 (cdr foo) 取出 b. 细心一点可以发现, 序对这种数据本身也满足上述复合数据的原则: 内置过程 cons 是构造函数, car 和 cdr 是选择函数, 而这些过程都满足条件: 经由 cons 构造出的 a 与 b 的复合数据 foo 应当能通过 car 过程取出 a 而能通过 cdr 过程取出 b.

(define (cons a b)
  (lambda (m) (m a b)))

(define (car z)
  (z (lambda (x y) x))) ;; cdr 改为 y 

这一例子体现了两点:

• 将复合数据作为一个过程(代码中用 lambda 实现)
• 这个过程本身也作为高阶函数接收另一个”选择函数”(lambda (x y) x)来实现选择函数

另: 注意 cdr 严格来说并不是”取出序对中的第二个元素”, 在以后涉及到列表时, (cdr z) 实际上是“z 中除了第一个元素以外的其他元素”

抽象屏障/边界

靠着这样的构造函数和选择函数, 我们最终构造了一层”屏障”隔离了使用分数的程序(如具体运算过程加减乘除)和分数本身的实现: 实现 add-rational 的人没有必要知道分数 z 底下是怎样实现的, 只要知道可以用 make-rational(其中可以用 cons实现, 也可以用其他方式实现) 构造, 用 number 和 denom (其中可以用 car cdr 实现也可以用其他方式实现) 取分子分母即可. 这样就形成了一层抽象屏障(abstraction barrier).

我们应当如何对待抽象屏障? ——不要打破抽象屏障. 在哪一个抽象层工作就思考哪个层次的问题, 不考虑下一个层次的细节.

区间问题的依赖性(来自 2.1.4 节扩展练习)

计算并联电阻的公式为 \(R = \frac{R_1R_2}{R_1+R_2}\) (鸡在河上飞)
分子分母同除以 \(R_1 R_2\) 得 \(R = \frac{1}{1/{R_1}+1/{R_2}}\)

这显然是等价的代数表达式, 但是在区间算术中可能会导致一些问题.

区间算数指的是这样的一种算数: 操作数并不是固定数值而是介于一个区间内存在, 可能为区间内任意取值
对于计算电阻的例子来说, \(R_1\) 和 \(R_2\) 可能分别取不同的区间.

对于原式, 不够健壮的程序可能会先计算 \(R_1 \cdot R_2\) 的值(也是一个区间), 再计算 \(R_1+R_2\) 的值(也是一个区间), 然后再对这两个区间进行除法 —— 但这可能是错的, 因为 \(R_1 \cdot R_2\) 和 \(R_1 +R_2\) 同时依赖 \(R_1\) 和 \(R_2\) 的区间, 很可能两者的某些值不能同时取到, 而第二个式子没有这个问题.

层次数据和数据的封闭性质

为了防止混淆, 这里 closure 还是写为封闭性

SICP 一些个人觉得翻译不太合理的地方

1. interface: inter 表示在…之间, face 为面, 实际为”在两个面之间”, 因此常被翻译为介面或界面, 这里的两个面可以指高抽象层次面和抽象屏障之下的低抽象层次面, 在其他语境下的 interface 也有其他的”面”的定义; 但是已经有”接口”这样较为更贴近实际含义的词语
2. frame: SICP 翻译为框架, 感觉翻译为帧更合适. 栈帧(stack frame)的概念和环境中 frame 的概念是相似的, 一些编程语言的局部环境就是靠栈帧实现的. frame 通常在应用程序开发框架中被译为框架, 在图形学或游戏开发中会翻译为帧
3. closure: 这个词有过计算机基础的确实是一眼闭包, 但是我觉得在这里翻译为闭包不太合适. SICP 作为 PLT 的某种入门书籍, 在抽象代数和 PLT 中都有(甚至离散数学里也有, 并且三者差距还是有一些的)的闭包概念与此处的概念并不相同(这里是说数据可以以同样的规则构造出自身同类的数据, 或者说数据可以包含自身同类的数据, 更类似代数中”基于S的运算最终产生的结果也是在S中”的闭包概念, 所以我认为这两个都应该被译为封闭性).

cons 可以 cons 一个 cons, 而非空列表可以多次地 cons 其他 cons 表达, 例如列表 1 1 4 5 1 4, 相当于
(cons 1 (cons 1 (cons 4 (cons 5 (cons 1 cons (4)))))), 由于这样写虽然很接近本质但是实在太蠢了所以 Scheme 有列表的语法糖 list, 非空列表相当于多层 cons, 例如上述例子 (list 1 1 4 5 1 4).

这涉及到一个重要的性质, 即 cons 可以 cons 自己, 数据可以包含与自己同类的数据, 或者说数据可以以同样的规则构造出自身同类的数据, 称之为数据的封闭性(或者闭包性质), 这一性质看似直观其实是很重要的, 例如拿 Scheme 和 C 构造某些数据结构做对比:

我觉得很多人初学数据结构时(甚至初学指针时)可能会想指针的作用在哪, 例如对于:

struct treeNode {
    int val;
    struct treeNode* left;
    struct treeNode* right;
};

为什么不干脆写 struct treeNode left 呢? 这是因为 C 的结构体要求类型必须是可计算大小的, 而这种递归的数据类型无法确认其大小: 对于一个 struct treeNode, 编译时无法得知其 right 和 left field 究竟是叶子节点还是空的还是一棵子树. 学习过 Rust 的人会很熟悉这个场景, 因为这就是 TRPL 在讲智能指针 Box<T> 作用时的例子, 因为指针本身的大小(在特定实现下)是固定的, 其指向堆内存上的数据. 这说明 C 无法完全满足数据的闭包性质. 深入其原因的话, C 更接近”操作本身应当是什么样的”, 抽象层次比较低.

而 Scheme 就没有什么负担了, 直接 cons 起来左右子树就好(或者 list), 用的时候查一下是不是 '()' 空表就行了

具有闭包性质的数据可以用递归很方便地处理: 每次处理当前的 car, 然后递归处理 cdr (还记得之前的介绍吗? cdr 并不是取出第二个, 而是取出除了 car 外剩下的). 这一性质的最典型应用就是树结构, 天然的递归友好结构.

通用的数据处理流程(序列作为一种约定的接口)

考察这样两个过程:

1. 找出一棵树所有的奇数叶子节点, 对这些奇数求平方和
2. 找出前 \(n\) 个斐波那契数中偶数形成一个表

看上去这两个操作差异较大, 但其实在某种程度上非常相似:
对现有的一些数据, 对其中每个数据进行某些转换, 根据某个条件进行筛选, 累积

对于 1 就是:

1. 对现有的一些数据(一棵树的叶子)
2. 根据某个条件进行筛选(奇数)
3. 对其中每个数据进行转换(求平方)
4. 积累(求和)

对于 2 就是:

1. 对现有的一些数据( \([0, n)\) 的整数)
2. 对其中每个数据 \(i\) 找出对应的 \(\text{Fib}(i)\)
3. 根据每个条件进行筛选(偶数)
4. 积累(形成表)

在每个单独的过程中, 数据像信号一样从上一个过程输入到这个过程中, 经过这个过程的处理又像信号一样传递到下个过程中, 而在这之中序列就成为了约定的接口(所有传递的数据都是数据的序列)

上述过程分别是:

1. 对现有的一些数据(枚举, enumerate)
2. 根据某个条件进行筛选(过滤器, filter)
3. 对其中每个数据进行转换(映射, map)
4. 积累, accumulate
5. 除此之外, 还有 for_each: 对每个数据进行操作但并不是映射到另一个数据

仔细考察这样的过程组合, 我们能发现一些特点:

1. 这些函数接受一些其他函数, 本身是高阶函数:

   map 接收一个转换函数; filter 接收一个谓词;

2. 这些函数的组合(或在一些语言中可以写为链式调用)只说明”要做什么(what)“而不说明”怎么做(how)”

   这是一种声明式编程

3. 数据不可变性:

   每个过程传递给下一个过程的数据本质上都是一份新产生的副本(当然这是逻辑上的, 在 scheme 的具体实现上会采用结构共享减少开销)

   如果有过并发编程的背景, 可以发现的是数据不可变性天然对并发程序友好

这些完美符合函数式编程的特点.

编程范式(或编程范型), 描述的是程序设计中的一种方法论, 主要分为 命令式编程 和 声明式编程.

命令式编程(或指令式编程)是大部分学校或课程面向初学者讲授编程所采用的范式, 因为其特点就是”利用可变状态一条条描述出要怎么做”, 并且也符合计算机的实际执行流程(见 CSAPP 第三章). 命令式编程主要分为 面向过程编程 和 面向对象编程, 这里不赘述 PP 和 OOP 的区别.

声明式编程是描述”我要达成什么样的局面/逻辑”, 直接描述逻辑或现象本身. 如逻辑式编程(如Prolog), 函数式编程(如Haskell)和数据库查询语言.

映射(map)过程也可以嵌套, 对某个序列进行映射, 映射规则是对其中元素 \(i\) 进一步拆分这个 \(i\) 为一个序列进行其他规则的映射.

同时, 这种通过某些基本过程的组合构造出复杂算法的方式增强了代码的复用性, 很多过程只要写一遍; 例如上述几个过程也能组合出新的功能不同的算法, 或者形式化某些数据的处理.

SICP 给了八皇后和一个图形绘画语言的例子.

一般学习回溯算法时一定会有一个八皇后的例子, 这里来看 SICP 是如何展现函数式的八皇后回溯写法的

整个算法可以描述为: 已经存在多个、不冲突的前 \(i\) 个皇后在棋盘上的局面, 对于每个局面, 尝试枚举列号并在第 \(i\) 行\(^{[1]}\)放下第 \(i+1\) 个皇后然后检查新皇后是否冲突, 然后将这些结果中符合条件(不冲突)的”总结”出来作为下一次放置的”前 \(i+1\) 个皇后”

\([1]:\) 原书是按列放置, 枚举行编号的, 这里个人不太习惯就换了一下, 是一样的.

事实上回溯法的关键是保证每次枚举叉出的状态独立方便回溯降低时间复杂度, 这里从开头几乎一直在讲递归操作(因为没有可变状态所以不用循环迭代, 见第一章), 所以天然具有这样的能力; 这里对八皇后算法本身不再赘述.

我们逐步考虑. 首先把防止前 \(k\) 行的功能实现为一个局部的 place-first-k-rows 函数,
那么首先考虑特殊情况特判

(define (place-first-k-rows k)
  (if (= k 0)
      (list empty-board)
      ;; TODO: k \neq 0
      )
  )

看算法描述: “已经存在前 \(i\) 个皇后在棋盘上的局面”, 则涉及到递归: (place-first-k-rows (- k 1))

“对于每个局面” 看上去像 map / foreach, 但其实 map 后还要把所有处理好后的局面”总结”为一个序列返回, 所以引入 flatmap, flatmap 是先对序列中每个元素 map 再 accumulate 为 list (这也是基本过程的组合, 较为常见的逻辑就单独抽象出来)

(define (place-first-k-rows k)
  (if (= k 0)
      (list empty-board)
      ;; k \neq 0
      
      (flatmap 
       (lambda 
         (rest-of-queens) 
         ;; TODO: for each placement... 
         )
       (place-first-k-rows (- k 1)))
      
      )
  )

然后关注得到前 \(k - 1\) 行之后如何放置第 \(k\) 行即可. 尝试枚举列号并在第 \(i\) 行 放下第 \(i+1\) 个皇后 (这是一个 map 过程: 把每个被枚举到的行号映射为在当前):

(define (place-first-k-rows k)
  (if (= k 0)
      (list empty-board)
      ;; k \neq 0
      (flatmap 
       (lambda 
         (rest-of-queens)
         
         ;; for each placement... 
         (map 
          (lambda 
            (new-col) 
            (apply-cols rest-of-queens k new-col)) 
          (enumerate-interval 1 board-size))	
         
         )
       (place-first-k-rows (- k 1)))
      )
  )

最后“检查新皇后是否冲突, 然后将这些结果中符合条件(不冲突)的”总结”出来作为下一次放置的”前 \(i+1\) 个皇后”“

(define (queen board-size)
  (define (place-first-k-rows k)
    (if (= k 0)
        (list empty-board)
        ;; k \neq 0
        
        ;; check validity
        (filter
         (lambda (placements) (safe? placements))
         (flatmap
          (lambda (rest-of-queens)
            
            ;; for each placement... 
            (map 
             (lambda (new-col)
               (apply-cols rest-of-queens k new-col))
             (enumerate-interval 1 board-size)))
          (place-first-k-rows (- k 1))))))
  
  (place-first-k-rows board-size))

(写到这里我还是不太适应 Lisp 这种括号和缩进, 给写眼花了说是)

具体的摆放方式可以直接用 list 存每一行的皇后列号, safe? 就是对新皇后(假设为在第 \(r\) 行 \(c\) 列)向上每一行做检查, 检查新皇后所在行向上 \(p\) 行的 \((c - p, r - p)\) 和 \((c + p, r - p)\) 位置是否被占据(具体可以画一下)

这就是把看似复杂的过程统一抽象为几个基本过程的方式, 增强复用性减少思考代价.

// TODO 图形那个例子考虑下要不要写

符号数据

以上我们讨论的数据几乎都建立在”值”(或数值)上. 数值是连续的, 可解释性较差的(光看数值难以理解含义)

数值反映了物理世界的客观属性(如年龄, 时间, 长度, 内存大小, 行列编号), 而符号则反映了人类的高级认知

符号是离散的不连续的, 可解释性较强(如看到 'apple 就知道这是一个苹果的符号), 但依赖上下文确定含义(伏笔, 如'apple 可以代表食物也可以代表 Apple Inc.)

数学柏拉图主义与维特根斯坦语言游戏

Mathematical Platonism 来自柏拉图的理念论, 强调数学对象的实在性, 如数、集合等是客观存在独立于人的心智的, 人类只是”发现”而非”发明”了这些概念, 甚至于是用自己的生理特质去理解这些概念并用自己的形式(语言)结构化描述出来.

Language Game Theory 强调语言是人类活动的一部分, 语言中的符号必须依赖语境上下文, 解决特定问题(表达思想或情感)才有实际价值, 也应当是这样(实践优先!) 经常对线的应该对抢夺定义权深有体会

前者展现了我们目前为止提及的以数值为核心复合组合构造起数据的某种原则, 这些数值是客观存在的, 人采用自己的方式描述和模拟出这些概念; 而接下来要说的符号数据是后者想要表达的思想: 靠一种”语境”(数据类型标记)构造一套符号语言系统来进行(模拟)人类活动

在 Scheme 中, 采用 ' 号来标记一个符号数据, 解释器会认定 ' 后的一个符号是符号而不是数值, 也可用于符合对象:'(a b c). 实际上 ' 是 quote 的语法糖, quote 是一种特殊形式, '(a b c) 就等价于 list (quote (a b c)), 而 '() 就是空表, 可以代替 nil

符号语言破坏了”对等的东西可以代换”的原则, 例如 \(3 = 1 + 2\), 但符号 "3" 却不能等于 \(1+2\). 符号重要的是其身份, 在上下文环境下所代表的实际意义. 从另一个角度看这个问题, 在引入符号概念后, 语言开始有更丰富的抽象层次(这也符合真实世界的复杂性), 这就导致了类型系统的改变: 引入以前的类型系统较为同质单一(数值和布尔值), 引入后强迫我们分辨不同的类型: number? symbol?, 这也为我们后续真正开始为数据的复合过程中加入类型标记打下基础.

总结来说, 引入符号为程序提供了这样的能力: 模拟真实世界的复杂性, 提供更丰富的抽象层次, 构造更复杂的数据结构

以简化的符号求导系统为例. 求 \(3x^{3}+5x^{2}+e^{x}\) 对 \(x\) 的导数, 我们意识到 \(3, 5, e, x, 2\) 虽然都是数字, 但明显是不同的, 其中系数指数和底数 \(3, 5, e, 2\) 是数值, 而 \(x\) 是符号, 因此需要区分类型, 甚至于说, 我们还需要区分和式, 乘式类型以及其构造函数和选择函数(为了套求导的规则)

---

抽象数据的多重表示

除了最基本的数值, 我们目前所有的数据类型几乎都是通过组合基本数值(设计构造函数与选择函数)以构造出的数据抽象; 但往往有些事物的构造方法不唯一, 例如复数可以通过直角坐标系坐标表示 (\(a+b \cdot \text{i}\) 表示为 \((啊, 不)\)) 也可以通过极坐标来表示.

假设有两个复数传递给 add-complex: 如果选择直角坐标, 那么 add-complex 所需的 real-part 就应该将复数中的两个数视为直角坐标系下的实部虚部, 直接返回前者即可; 如果选择极坐标则是通过模和辅角计算实部(\(r\cos\theta)\)). 良好的数据抽象和抽象边界的构造使得使用者只需要调用 add-complex 并传入复数就行了, 不需要查阅文档观察 real-part 将其视为什么, 但是开发者要考虑的可就多了 但是这样的方法有一些问题:

1. 实际上同时也只能选择一种表示方法, 因为无论如何构造函数还是不同的, 而且也不允许一个函数的多种语义
2. 过早许诺了表示方法. “最小许诺原则”指的是在信息不完整或不确定性较高的时候应该避免太早绑定具体方案, 而是保留多种可能性, 推迟决定的时间点. 举个有违公序良俗的例子: 一个人有很多暧昧对象, 如果选择其中一个作为配偶之后就丧失了其他人的可能性, 相反如果一直保持暧昧关系就能保留多种可能性, 推迟决定的时间点.

这只是举例用, 即使是在现在这样的社会, 也极不推荐这样的行为!

为了解决上述问题, 引入更大的灵活性, 需要给数据一个”标记”, 称作”类型”

数据类型的初步概念

为了构造抽象数据的多重表示

考虑我们为什么需要一个”类型”?

• 在一些底层场景中, 选取较小的数据类型(在取值允许, 不会溢出的情况下)可以节省内存空间
• 防止一些潜在的运算错误, 对两个本不应该运算的数据进行了错误的运算时(即两个数据类型不具有该运算), 编译器可以及时发现错误
• 一些过程对于不同的类型参数会有不同的反应 (多态类型)
• 可以通过继承类型增强代码复用性, 如 Dog 和 Bird 都继承自 Animal 父类 (D 和 B 是子类型)
• 可以通过组合特性增强代码复用性, 如 Dog 和 Bird 都实现了 Animal trait (D 和 B 都满足类型约束 Animal)
• 逻辑更清晰
• ….

总结来说, 就是说我们需要模拟或认定”一个数据不同于其他数据”或”这个数据与其他数据存在一定程度上的相似性”时, 就需要为数据指定一个类型

最直观的想法就是我们上面说的”打一个标记”:

(define (attach-tag type-tag contents) 
  (cons type-tag contents))

再定义 car x 为 (type-tag x), cdr x 为 (contents x), 设计一些谓词判断 x 的类型是否为某一类型即可. (实际上这还是构造数据抽象: 选择函数和构造函数)

而对于通用操作 real-part, 只需要检查 x 的类型是 `rect 还是 polar 就可以了(当然, 这是某种意义上的硬编码). 甚至不需要修改 add-complex 的代码, 因为 real-part 已经进化为通用操作了 (还是良好的数据抽象)

但是如果我们想要动态添加一些数据类型呢?

数据导向/信息传递

首先较为直观的想法是维护一个表格(或者别的你想的什么数据结构), 通过(put <op> <type> <item>) 把 item 放在 <type> 行的 <op> 列, 表明对于数据类型 <type>, 其 <op> 操作的具体指派是 <item>, 调用时通过 (get <op> <type>) 查表得到对应过程来应用.

op/type	Polar	Rectangular
real-part	real-part-polar	real-part-rect
imag-part	imag-part-polar	imag-part-rect
magnitude	magnitude-polar	magnitude-rect
angle	angle-polar	angle-rect

调用时直接 ((get 'real-part 'polar) x) 即可. 这种实现方式就是”数据导向”的程序设计, 采用”智能操作”通用地处理数据.

还有一种想法是采用”智能数据对象”而不是”智能操作”, 如下:

(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 ... 我忘了怎么算了))
      		...
            (else 
             (error "Unknown operation."))))
dispatch)

make-from-real-imag 返回的不再是一个表示复数的数据而是一个过程, 通过闭包(内部过程也是闭包)绑定 make-from-real-imag 的参数并返回这个闭包以延长其生命周期.

使用时 (x 'real-part) 或者封装一下均可. 这种风格叫做”消息传递”, 将”我要调用你的 real-part “这条消息传递给智能数据对象(虽然语法上是一个闭包), 由智能数据自己灵活处理

在一个较为复杂的系统中可能有多种类型层次, 每层与下一层之间的连接都借助一些通用型操作. 当一个数据被”向下”传输时, 用于引导它进入适当处理过程的最外层标志被剥除(通过使用 contents ), 下一层的标志(如果有的话)变成可见的, 并将被用于下一次分派.

不同类型数据的组合

前面提到:

(类型可以)防止一些潜在的运算错误, 对两个本不应该运算的数据进行了错误的运算时(即两个数据类型不具有该运算), 编译器可以及时发现错误

例如:

int temperature = 30;
int distance = 100;
int nonsense = temperature + distance; // WA :(

enum class Temperature { Celsius };
enum class Distance { Meters };

Temperature temp{30};
Distance dist{100};
auto bad = temp + dist;  // CE!

当然, 对于 C 来说还有很多选项不开全时编译器发现不了的问题, 比如:

"114"+514; // 未定义行为

"114" 字符串字面量在 C 中是 char[N] 的字符数组, 在这里退化成 const char * 参与与整型的运算, 相当于字符串首字母的地址 + 514 * sizeof(char), 然而整个字符串只有 3 个 char 和一个 '\0' 这么长, 会发生越界导致 UB.

当然, 也不全是所有的不同类型间操作都要禁止, 有些类型之间的操作是我们需要支持的.

下面是一些合法且(不严格来说)比较正常的例子

int nine = 9;
nine + '0'; // 合法, '0' 整型提升为 48, 结果为 48+9=57, int 类型
char digit = nine + '0'; // 合法, int 隐式转换为 char, 当然要注意范围
(digit - '0') * 10;  // 合法, 两个 char 整型提升后进行整型运算, * 10 还是整型

你可能会说: 为什么要设计各种隐式转换/整型提升, 而不是直接”规定” char 和 int 之间的运算呢?

比如说写一些自定义的类型, 可能也会有涉及到两个不同类型之间的运算, 你可能就直接 operator+ 或者 impl Add for 糊上去了, 但是如果类型多起来, 如果你的系统每两个类型之间都需要运算, 那么 \(n\) 个类型之间需要 $ n + $ (自加和不同类型相加), 相当于随着类型的增多, 需要手动定义的运算呈 \(n^2\) 平方级别增长. 那我写模板让编译器自己生成不就行了?

然而实际情况下, 很多所谓的”不同类型”之间是有相互关系的, 例如 常规数值 与 复数 相加, 可以把常规数值转换为虚部为 \(0\) 的复数(只需要 put 一个类型转换的过程进去, 在运算时若不能直接运算则查表看能否转换到同一类型). 还记得我们上面随口提一嘴的”子类型”吗? 这里整数就可以看作复数的子类型. 更一般地说, 有这样的关系: 复数<-实数<-有理数<-整数, 后者均为前者的子类型, 这就是一种塔形类型结构.

与之相应的还有树形类型结构, 例如各种凸多边形的分类, 看起来就像某些设计臃肿的类的继承图一样, 四边形包含了梯形, 筝形, 则后两者是前者的子类型; 甚至包括了令人发指的钻石型继承: 平行四边形包含了矩形和菱形, 但是正方形同时是矩形和菱形. 树形类型结构在转换时就需要更复杂的搜索. 当然这里的”臃肿”和”令人发指”的批判并非空穴来风, 毕竟:

“在设计大型系统时, 处理好一大批相互有关的类型而同时又能保持模块性, 这是一个非常困难的问题, 也是当前正在研究的一个领域.” (注: 这句话在书上写了 20 年, 依然适用)

---

说点题外话, 目前我接触过最大规模的工程代码还是 ArceOS, 当然也在其中遇到了很多类型相关的问题. 上面一块的内容一直在叙述类型之间的继承(子类型的存在)这件事, 而我们经常能听到一句”组合优于继承”, 那么组合是什么呢? 类似 Rust 的 trait 一样, 对不同类型之间做约束, 并提供约束检查等. 在现代语言中很少有需要手写一个 item-op 的表来实现类型系统的, 一般都是基本类型内置, 自定义类型的话大概分为静态分发(模板, 编译期静态生成代码)和动态分发(运行期间决定类型, 如 C++ 的虚函数和 Rust 的 trait 对象, 有趣的是前者的虚函数表常常被人诟病很慢, 但其实后者也要查虚表的\(^{[*]}\))

$[*]: $ 虚函数表和虚表的性能开销来源是类似的: 一是需要通过一个指针找到虚函数表在通过表中偏移量找到需要调用的函数, 多了一些寻址操作; 二是可能妨碍到编译器优化(这部分具体就不太懂了). C++ 的指向虚函数表的指针在对象内部的 vptr 中, Rust 是一个底子很好的指针一部分指向数据对象一部分指向虚函数表, 理论上应该都有开销的, 总之不太清楚风评是怎么回事.