Reading 10: 抽象数据类型（Abstract Data Types）

目录 · ← l9 · l11 →

Reading 10: 抽象数据类型（Abstract Data Types）

说明：本讲 sp22 原版使用 TypeScript，本笔记按用户要求提供 Java 代码示例；类型/API 与 sp21（6.031 Java 版）原文保持一致。

概述

本讲要解决的核心问题是：客户端（client）对类型的内部表示（representation）做出假设——这是软件构造中特别危险的一类耦合，因为一旦实现者更换数据结构，所有偷偷依赖内部字段的客户端代码都会失效，而且这类失效经常连编译器都发现不了（Family 的 client3 就是典型）。为此 6.031 提出两个紧密相连的思想：抽象数据类型（abstract data type, ADT）——一个类型由「你能对它执行哪些操作」以及每个操作的规格来完整刻画，而不是由它内部怎么存来刻画；以及表示独立（representation independence）——客户端只依赖公开操作的规格，实现者因此可以自由替换表示。这两个思想同时服务于课程的三大目标：ADT 用「操作契约 + private 表示」把非法状态挡在编译期和调用边界之外（Safe from bugs），用「客户端只需读懂操作、不必读懂实现」降低理解成本（Easy to understand），用「换 rep 而不改客户端」让系统能够应对变化（Ready for change）。

核心概念与设计原则详解

抽象数据类型（Abstract Data Type, ADT）

• 定义与目的：ADT 是由一组操作及其规格完整刻画的数据类型：对类型 T 而言，「T 的全部含义」就等于「T 的这些操作所满足的规格」。它要解决的软件质量问题是：把「数据在程序里怎么被使用」与「数据本身以什么形式存在」分离开（sp22 原文的表述是 separate how we use a data structure in a program from the particular form of the data structure itself）。
• 直观解释（”它是什么？”）：数字是什么？是你能对它做加、减、乘、除的东西；字符串是什么？是你能对它做拼接、取子串的东西；布尔值是什么？是你能对它取反的东西。我们从来不关心编译器把 int 存成几个字节、字节序如何——ADT 就是把这种「只用操作说话」的态度搬到用户自定义类型上。ADT 的值是不透明的（opaque）：客户端不能「看进去」，除非通过操作。原文建议把它想象成一堵规格防火墙（specification firewall）之后的硬壳：壳里藏的不只是某一个函数的实现，而是一组相关操作的实现以及它们共享的数据（private 字段）。
• 关键规则与最佳实践：
  • 定义类型时，先列操作集合 + 每个操作的前置/后置条件；这套东西就是类型的规格，也是客户端唯一被允许知道的全部信息。
  • 值的内部数据必须不可被客户端直接读写；一切访问都走操作。
  • 明确区分两个词：操作集合 = 抽象（abstraction）（public，客户端可见）；实现类里的字段 = 一个具体的表示（representation）（private，只有实现者可见）。
  • 记住历史脉络能帮你理解为什么这么设计：Dahl（Simula）、Hoare（抽象类型的推理技术）、Parnas（提出 information hiding、主张按「模块封装了什么秘密」来组织程序）；MIT 的 Barbara Liskov 与 John Guttag 在抽象类型的规格与语言支持上做了奠基性工作，Liskov 因抽象类型相关研究获得图灵奖。
  • 在 Java 里「内置类型」与「用户自定义类型」的界限是模糊的：java.lang.Integer、Boolean 等用与用户类完全相同的类/对象抽象来定义，但 int、boolean 这类原始类型（primitive type）不能由用户扩展。写 ADT 时要意识到这一点：你不能给 int 加操作，只能另建一个类型。

使用者与实现者的分离：抽象边界（Client–Implementer Separation / Abstraction Barrier）

• 定义与目的：任何一个类型都有两类读者——只使用它的客户端，和实现它的人。抽象边界就是两者之间的那条分界线：线上只有操作与规格，线下才是字段、辅助类与算法细节。目的是让两边能够独立演化，把「误解」与「改一处坏一片」的耦合降到最低。
• 直观解释（”它是什么？”）：像汽车的驾驶舱与发动机舱。司机只操作方向盘、油门、刹车（操作），不需要知道喷油策略、气门正时（表示）。只要这套操作的含义不变，换一台完全不同的发动机，司机毫无感觉。
• 关键规则与最佳实践：
  • 客户端只允许了解公开操作及其规格；任何对 private 字段、内部辅助类的依赖都算越界，即使它「现在能编译」。
  • 实现者可以自由更换表示，前提是操作的可观察行为不变；这也是为什么规格必须写全前置条件与后置条件。
  • 规格不完整时，抽象边界是假的：客户端不知道能依赖什么，实现者也不知道能安全改什么（这一点由 Reading 06 规格说明与 Reading 07 设计规格奠定）。
  • 抽象边界同时是测试边界：客户端级测试是黑盒的（只通过操作），实现者级测试才是白盒的（可以检查 rep）。
  • 在源码里，抽象边界具体体现为 public / private 这两个关键字——它不是一个口头约定，而是有编译器背书的机制。

操作的分类：构造者、生产者、观察者、修改者（Classifying Operations: Creators, Producers, Observers, Mutators）

• 定义与目的：把 ADT 的操作按下述两个维度分成四类：输入/输出里有没有出现本类型 T、执行后对象本身是否被改变。目的是给出一张设计 ADT 时的检查清单——四类操作是否齐备、每一类是否都必要、某个操作是否放在了错误的类别里。
• 直观解释（”它是什么？”）：把类型想象成一台机器。构造者是从零造出一台机器（不需要已有机器）；生产者是拿旧机器造出一台新机器（旧机器不动）；观察者是读表盘（机器不动，返回的是别的信息）；修改者是扳动开关（机器本身被改变）。
• 关键规则与最佳实践（分类表格如下，重点看「输入是否含 T」「输出是否含 T」两列）：

• 记号含义：T 是抽象类型本身，t 是别的类型；+ 表示「出现一次或多次」，* 表示「零次或多次」，\| 表示「或」。例如生产者可以吃两个 T，就像 concat : String × String → String。
• 观察者可以完全不吃其他类型：size : List → int；也可以吃很多：regionMatches : String × boolean × int × String × int × int → boolean。
• 构造者常常实现为构造器（new ArrayList<>()），但也可以只是静态方法——List.of()、String.valueOf(...) 都是；用静态方法实现的构造者通常叫工厂方法（factory method）。
• 修改者常常返回 void（返回 void 的方法必然是为了副作用而调用），但不是必须：Set.add() 返回 boolean 表示集合是否真的被改动；AWT 的 Component.add() 返回对象本身，以便链式调用。
• 分类并不完美：复杂类型里可能出现同时是生产者和修改者的操作。本课程把这类方法同时称作生产者和修改者，也有人只叫它修改者，把「生产者」一词留给不做修改的操作。
• 分类时别忘了实例方法有一个隐藏的 this 参数——toUpperCase() 看起来没有输入，实际上输入就是一个 String，所以它是生产者而不是构造者。

常见操作归类练习（可用作自测）：

可变类型与不可变类型（Mutable vs Immutable Types）

• 定义与目的：可变类型的对象可以被改变——存在某个操作，执行之后对同一个对象调用其他操作会得到不同的结果（Date 是可变类型：调用 setMonth 后，getMonth 的返回值变了）。不可变类型的操作则创建新对象而不是修改已有对象（String 就是这样）。这个划分决定了别名（aliasing）与表示暴露（rep exposure）的风险等级，因而是 ADT 设计的第一决定。
• 直观解释（”它是什么？”）：不可变对象像刻在石头上的字——别人拿到同一个引用也无所谓，因为他改不了；可变对象像白板，谁拿到引用谁都能擦，所以你必须谨慎决定把白板交给谁。
• 关键规则与最佳实践：
  • 有些类型同时提供可变与不可变两个版本：String（不可变）与 StringBuilder（可变）——注意二者不是同一个 Java 类型、不可互换；List 与 Collections.unmodifiableList() 包装出的视图也是这种关系。
  • 不可变类型的字段应声明为 private final，并且不提供任何 mutator；但要牢记 final 只保证引用不再改变，不保证被引用对象的内容不变（private final Date timestamp 里的 Date 照样能被 setTime 改掉）。
  • 可变类型只要把可变对象的引用存进来（构造器保存参数）或发出去（观察者返回内部对象），就产生表示暴露；必须做防御性拷贝（defensive copy）。
  • 不可变性换来了一项重要的自由：多个对象可以共享同一块内部数据。MyString 的 substring 之所以能只记录 start/end 而不复制字符，正是因为它不可变；一旦加入 reverse() 这样的修改者，共享表示就会立刻变成 bug。
  • 把可变对象同时交给两个别名持有，一处修改会「隔空」改变另一处看到的值——这就是 Reading 08 不可变性里的快照图与别名分析要练习的内容。

本讲原文正是用 Java 库里的真实类型来对照这两类：int、String 是不可变的（没有 mutator），List、Date、StringBuilder 是可变的。下面这段代码把原文 “Classifying types and operations” 与 “Abstract data type examples” 两节列出的操作原样归类在一起：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Date;
import java.util.List;

class AdtExamples {
    void examples() {
        // int：Java 的原始整数类型，不可变 —— 没有 mutator
        int n = 0;                       // creator：字面量 0, 1, 2, ...
        int m = n + 1;                   // producer：算术运算符 + 返回新值，n 仍然是 0
        boolean positive = n > 0;        // observer：比较运算符 ==, !=, <, >

        // String：不可变 —— 没有 mutator，所有"看起来会改"的操作都返回新串
        String s = String.valueOf(true); // creator：valueOf 静态工厂方法
        String t = s.substring(1, 3);    // producer：substring 返回新 String
        String u = s.concat("!");        // producer：concat 返回新 String
        String v = s.toUpperCase();      // producer：toUpperCase 返回新 String
        int len = s.length();            // observer：length
        char c0 = s.charAt(0);           // observer：charAt

        // StringBuilder：String 的可变版本 —— 注意二者不是同一个 Java 类型，不可互换
        StringBuilder sb = new StringBuilder("ab");  // creator：构造器
        sb.append("c");                              // mutator：返回 this，内容变成 "abc"
        sb.reverse();                                // mutator：返回 this，内容变成 "cba"
        int sbLen = sb.length();                     // observer

        // Date：可变 —— 可以调用 setMonth 再用 getMonth 观察到变化
        Date d = new Date();             // creator
        d.setTime(0L);                   // mutator
        long ms = d.getTime();           // observer

        // List：可变，而且是接口 —— 真正的实现来自 ArrayList / LinkedList
        List<String> list = new ArrayList<>();       // creator：ArrayList 构造器
        list.add("x");                               // mutator：add
        int size = list.size();                      // observer：size
        String first = list.get(0);                  // observer：get
        List<String> ro = Collections.unmodifiableList(list);  // producer：不可变包装
    }
}

sp22 原版 TypeScript 写法（对照）：sp22 用 ReadonlyArray 作为 Array 的不可变版本，Java 里没有独立的不可变数组类型，对应手段是 Collections.unmodifiableList() 或 List.of() 这类返回不可修改视图/列表的操作（在 Reading 11 中还会讨论：这种包装只在运行时阻止修改，编译期不报错）。

补充示例（非本讲原文，取自 Reading 02/06）：同一份材料里还常拿”点”来对比可变与不可变——本讲 Reading 10 原文只用 MyString / List / String / StringBuilder / Date 做可变性对比，并没有 Point 这个例子，下面两块代码是本笔记借 Reading 02/06 的 Point 话题补充的：

// 补充示例（非本讲原文，取自 Reading 02/06）：同一个"点"的两种 ADT 设计
public final class Point {                 // 不可变版本：只有 creator / observer / producer
    private final int x;
    private final int y;

    public Point(int x, int y) { this.x = x; this.y = y; }   // creator

    public int getX() { return x; }                          // observer
    public int getY() { return y; }                          // observer

    public Point translate(int dx, int dy) {                 // producer：返回新点，旧点不动
        return new Point(x + dx, y + dy);
    }
}

class MutablePoint {                       // 可变版本：多出两个 mutator
    private int x;
    private int y;

    MutablePoint(int x, int y) { this.x = x; this.y = y; }

    public int getX() { return x; }
    public int getY() { return y; }
    public void setX(int x) { this.x = x; }                  // mutator
    public void setY(int y) { this.y = y; }                  // mutator
}

可变/不可变的取舍并非”越不可变越好”：不可变类型要为新值分配新对象，修改频繁时成本更高，所以 Java 才同时提供 String 与 StringBuilder。课程的建议是：默认选不可变，只有确有性能或建模需要（例如一个会被大量就地修改的累积器）才提供可变版本，并把它封装好。

表示独立（Representation Independence）

• 定义与目的：类型的使用与它的表示（实际采用的数据结构或数据字段）相互独立，因此表示的改变不影响类型之外的任何代码。这是本讲的第二个核心思想，直接对应「Ready for change」。
• 直观解释（”它是什么？”）：List 提供的操作与它内部是链表还是数组无关；MyString 的 charAt / length / substring 与它内部是「独占字符数组」还是「共享字符数组 + start/end」无关。客户端写的是「取子串」，不是「复制数组的第 start 到 end 个元素」。
• 关键规则与最佳实践：
  • 表示独立的前提是操作被完整规格化（前置条件 + 后置条件齐全）：这样客户端才知道可以依赖什么，实现者才知道可以安全改什么。
  • 表示独立 ≠ 表示不需要正确：客户端看不见 rep，但 rep 内部仍然必须满足不变量（表示不变量 RI 是 Reading 11 的主题）。
  • 表示独立靠 private 强制出来，而不是靠口头约定：只要字段是 public，客户端就可能依赖它（原文 Family 例子里 client1、client2 直接读写 f.people）。
  • 违反表示独立有三级后果：最轻的是静态错误（编译就报错，例如把 List 换成 Set 后 f.people.get(0) 不存在）；中等的是动态错误（运行时抛异常）；最危险的是静默给出错误答案（能编译、不抛异常，只是结果变了——client3 依赖元素顺序就属于这一类）。
  • 表示独立也让客户端代码更易读：读一个方法时不必跳进实现体去猜它是否修改了什么。

规格、表示与实现的三层划分（Specification / Representation / Implementation）

• 定义与目的：原文的 Family 练习要求把每一段代码归类为「规格 / 表示 / 实现」。三者分清之后，code review 才能准确指出「这是实现细节泄漏进了规格」。这是理解抽象边界的具体抓手。
• 直观解释（”它是什么？”）：规格是合同；表示是仓库里货物实际怎么摆放；实现是干活的动作序列。
• 关键规则与最佳实践（对照原文 Family 的七段代码）：
  • 规格：类上方的 Javadoc（/** Represents a family ... Families are mutable. */）、方法签名（public List<Person> getMembers()）、方法上方的 Javadoc（@return a list containing all the members ...）。
  • 表示：private List<Person> people; 这条字段声明，以及描述 rep 性质的注释（「sorted from oldest to youngest, with no duplicates」）。
  • 实现：方法体 return people;，以及内部算法、辅助类。
  • class Family { 这一行本身既不是规格也不是表示，它只是把三者打包在一起的语法外壳。
  • 一条实用的自查：如果一个客户端必须读懂某段代码才能正确使用这个类型，那么那段代码实际上已经是规格的一部分了——要么把它写进 Javadoc，要么把它藏起来（改成 private 实现细节）。

访问控制：private 与 public（Access Control）

• 定义与目的：Java 用 private / public（以及包级默认、protected）在语言层面建立抽象边界。private 表示「只有本类内部可见」，public 表示「任何地方可见」。目的是把越界访问变成静态错误，在编译期而不是运行时暴露问题。
• 直观解释（”它是什么？”）：private 是给字段和内部辅助方法上的一把锁，唯一的钥匙是「同一个类里的代码」——注意钥匙是按类发的，不是按对象发的。
• 关键规则与最佳实践（对照下面的 Wallet 例子）：
  • Java 的 private 是类级授权：在 Wallet 的方法里写 that.amount 去访问另一个 Wallet 对象的 private 字段是合法的。
  • 换到 Person 类里写 w.amount 就是静态错误（amount 在另一个类中是 private）；写 Wallet.amount == 0 更是双重错误——既 private，又是实例变量而非 static，不能通过类名访问。
  • Wallet.main 里写 w.amount = 100 在 sp21 的例子中是合法的，因为 main 恰好写在 Wallet 类内部。这说明可见性取决于「代码挂在哪一层」，而不是「谁在运行」。
  • 因此结论很直接：所有字段都应该是 private；只有确实构成抽象的操作才 public。不要用包级可见（默认）当「半公开」的捷径。
  • 注意构造器的可见性也是一个操作：不写任何构造器时 Java 会补一个 public 的默认构造器，等于凭空开放了一个 creator。若希望客户端只能通过工厂方法（或 substring()）拿到对象，就把构造器声明为 private。

class Wallet {
    private int amount;

    public void loanTo(Wallet that) {
        // put all of this wallet's money into that wallet
        that.amount += this.amount;   // 允许：private 按类授权，同类内部可见
        amount = 0;                   // 允许：等价于 this.amount = 0
    }

    public static void main(String[] args) {
        Wallet w = new Wallet();
        w.amount = 100;               // 允许：main 也写在 Wallet 类内部
        w.loanTo(w);                  // 允许：this 与 that 是同一个对象的别名
        System.out.println(w.amount); // 输出 0（先 += 变成 200，再被置 0）
    }
}

class Person {
    private Wallet w;

    public int getNetWorth() {
        return w.amount;              // 静态错误：amount 是 Wallet 的 private 字段
    }

    public boolean isBroke() {
        return Wallet.amount == 0;    // 静态错误：amount 既 private 又是实例变量
    }
}

sp22 原版 TypeScript 写法（对照）：

// sp22 原版 TypeScript 写法（节选，语义与上面的 Java 版一致）
class Wallet {
    private amount: number = 0;

    public loanTo(that: Wallet): void {
        that.amount += this.amount;   // 允许：同一类内部可以访问其它实例的 private 字段
        amount = 0;                   // 允许：省略 this 时默认指向本对象
    }
}

TypeScript 与 Java 在这里的规则几乎一样（都是类级授权、都允许省略 this），差别在语法与生态：TypeScript 没有”原始类型”这一层区分，而 Java 有 int / boolean 这些不可扩展的原始类型；TypeScript 用 readonly 表达”字段构造后不可再赋值”，Java 对应的是 final。

更有意思的对照是本讲的核心例子 MyString：sp22 与 sp21 给出的是同一个抽象、两种语言外壳，而且两边的 rep 都是 private 字段、两边的公开面都是那几个操作——这本身就是表示独立的最好演示（表示可以换，操作与规格不动）。

// sp22 原版 TypeScript 写法（原文的 MyString；rep 是 private 字段）
class MyString {
    private a: Uint16Array;          // 表示：16 位无符号整数数组

    /** @returns MyString representing the sequence of characters in s */
    public constructor(s: string) { /* ... */ }          // creator
    /** @returns number of characters in this string */
    public length(): number { /* ... */ }                // observer
    /** @param i character position (requires 0 <= i < string length) */
    public charAt(i: number): string { /* ... */ }       // observer
    /** @returns string consisting of charAt(start)...charAt(end-1) */
    public substring(start: number, end: number): MyString { /* ... */ }  // producer
}

// Java 对应写法（sp21 原文的 MyString）：同一个抽象，rep 换成 char[]，
// creator 换成静态工厂方法 valueOf —— 操作与规格的形态完全对应。
public class MyString {
    private char[] a;                // 表示：字符数组

    /** @param b a boolean value
     *  @return string representation of b, either "true" or "false" */
    public static MyString valueOf(boolean b) { /* ... */ }        // creator（工厂方法）

    /** @return number of characters in this string */
    public int length() { /* ... */ }                              // observer

    /** @param i character position (requires 0 <= i < string length)
     *  @return character at position i */
    public char charAt(int i) { /* ... */ }                        // observer

    /** @param start starting index
     *  @param end ending index. Requires 0 <= start <= end <= string length.
     *  @return string consisting of charAt(start)...charAt(end-1) */
    public MyString substring(int start, int end) { /* ... */ }    // producer
}

设计抽象类型的经验法则（Designing an Abstract Type）

• 定义与目的：设计 ADT 就是「挑选好的操作集合，并决定它们应该如何表现」。这些法则用来判断一个操作集合是否易于理解、不易出错、便于演化。
• 直观解释（”它是什么？”）：好的 ADT 像一套精简的工具箱——件数少、每件用途明确、能组合出很多活；坏的 ADT 像一个塞满专用扳手的抽屉，每个角落都要一把新扳手。
• 关键规则与最佳实践：
  • 少而简单 > 多而复杂：宁可要少量简单操作，让它们能强力组合，也不要一大堆复杂操作。
  • 每个操作目的明确、行为一致（coherent），而不是一堆特例。例如不该给 List 加 sum：对整数列表有用，那字符串列表怎么办？嵌套列表怎么办？这些特例会让 sum 变得难以理解和使用。
  • 操作集合要足够（adequate）：客户端想做的计算都要能做。原文给的检验方法是「对象的每一个性质都能被取出」——如果 List 没有 get，就根本取不出元素；size 严格说来并非必需（可以从下标 0 一直 get 到失败为止），但那样低效又难用，所以仍然值得提供。基本信息不应该难以获得。
  • 通用（generic）与领域特定（domain-specific）不要混：Deck（代表一副扑克牌的序列）不应该有接受任意对象的通用 add 方法（那会让 Deck 里混进整数或字符串）；反过来，把 dealCards 这种领域特定方法塞进通用的 List 也毫无意义。
  • 四类操作齐备性检查：能用 creator 造出来吗？producer 能否组合出需要的新值？observer 能否读出全部性质？mutator（如果是可变类型）是否覆盖了全部需要的变化？
  • 小固定值集合用枚举（enum）：一天的星期（原文举的例子）、罗盘方位、线段端点样式——这类 ADT 的值集小而有限，用 enum 一次定义所有命名值最省事，也最安全（原文的实现方式对照表把它列为 ADT 的三种实现手段之一）。

实现 ADT 概念的 Java 手段（Realizing ADT Concepts in Java）

• 定义与目的：同一个「大思想」在 Java 里往往有多种实现途径。理解「概念」与「实现手段」的对应关系，才能在不同场景下做出合适选择。
• 直观解释（”它是什么？”）：概念是「要做什么」，手段是「用哪个 Java 关键字/结构去做」。比如「构造者」这个概念，可以用构造器、工厂方法或常量三种手段实现。
• 关键规则与最佳实践（对照表沿用 sp21 原文）：

• 接口 + 类：List 只声明操作，ArrayList、LinkedList 各自提供表示。这是表示独立的结构性保证——客户端按 List 编程，实现可以随时换。
• 用常量作构造者：常见于不可变类型——最简单或最空的那个值就是一个 public 常量，其余复杂值靠 producer 从它搭出来（BigInteger.ZERO 就是这个模式）。
• 用枚举作 ADT：适合值集小而固定的类型，我们会在 Reading 12（接口、泛型与枚举）里展开。

测试抽象数据类型（Testing an ADT）

• 定义与目的：ADT 的测试套件是「为每一个操作写测试」。但它与函数测试有一个关键差别：ADT 的测试之间必然互相依赖——测试 creator / producer / mutator 的唯一方式就是对结果调用 observer；测试 observer 的唯一方式就是先造出对象让它观察。
• 直观解释（”它是什么？”）：你没法直接检查一个黑盒里装了什么，只能「做点什么」再「读出点什么」。所以一个测试用例天然是若干操作的合作演出。
• 关键规则与最佳实践：
  • 分区（partition）要基于抽象状态，不要基于 rep。原文明确要求：按字符串的抽象长度分区，而不是 rep 数组 a 的长度；按 substring() 的 start / end 入参分区，而不是 rep 里的 start / end 字段。
  • 分区可以使用客户端的知识：这个实例是「由哪个创造者产生、经过哪些操作变成现在这样」的，这常常是不同代码路径的分界。可变 ADT 尤其要覆盖不同的操作序列。
  • 在类型还没定义 equals 之前（见 Reading 15 相等性），不能直接用 assertEquals 比较两个 ADT 对象——只能用已经定义好的操作来断言（length()、charAt()）。
  • 由 substring() 返回的对象要单独作为一类 this 来测试，因为不同构造路径可能走完全不同的代码。

// testing strategy for each operation of MyString:
//
// valueOf():
//   partition on the boolean argument: true, false
// length(), charAt(), substring():
//   partition on string length: 0, 1, >1
//   partition on this: produced by valueOf(), produced by substring()
// charAt():
//   partition on i = 0, 0 < i < len-1, i = len-1
// substring():
//   partition on start = 0, 0 < start < len, start = len
//   partition on end   = 0, 0 < end   < len, end   = len
//   partition on end - start: 0, > 0

@Test public void testValueOfTrue() {
    MyString s = MyString.valueOf(true);
    assertEquals(4, s.length());
    assertEquals('t', s.charAt(0));
    assertEquals('r', s.charAt(1));
    assertEquals('u', s.charAt(2));
    assertEquals('e', s.charAt(3));
}

@Test public void testSubstringIsWholeString() {
    MyString s = MyString.valueOf(false).substring(0, 5);
    assertEquals(5, s.length());
    assertEquals('f', s.charAt(0));
    assertEquals('e', s.charAt(4));
}

@Test public void testSubstringOfEmptySubstring() {
    MyString s = MyString.valueOf(false).substring(1, 1).substring(0, 0);
    assertEquals(0, s.length());   // 注意：this 由 substring() 产生，覆盖了那条分区
}

注意 testValueOfTrue 的「单元」不是一个操作：它同时测试了 valueOf、length 和 charAt 四个 charAt 调用。这不是设计缺陷，而是 ADT 测试的固有形态。

为什么 ADT 同时提升安全性、易理解性与可修改性

• Safe from bugs（落到具体机制）：① private 字段让客户端无法把对象置于非法状态——越界访问是编译期静态错误，而不是运行时惊喜；② 表示不变量（RI）因此只需要在类内部少量位置维护，容易出现「所有修改都经过同一道关卡」的结构；③ 每个操作的前置/后置条件构成了客户端与实现者之间的合同，边界处的契约违规可以 fail fast（这与 Reading 09 避免调试的精神一致）；④ 不可变 ADT 天生免疫别名攻击，也天生线程安全（Reading 21 并发的基础）。
• Easy to understand（落到具体机制）：① 客户端只需要读操作签名与规格，不需要读实现，阅读量的量级直接下降；② 操作分类给出清晰的心智模型：哪些操作会改状态（mutator）、哪些只是读（observer），读代码时能立刻判断「这行之后对象变了吗」；③ 一个类型只负责一个 concern（separation of concerns），不会把无关功能堆进来；④ 抽象边界把「读代码时要搜索的范围」压缩到了一个类的公开 API。
• Ready for change（落到具体机制）：① 表示独立让 rep 可以整体替换——MyString 从「独占数组」换成「共享数组 + start/end」，Family 从 List 换成 Set，客户端代码一行不改；② 只要规格不变，实现可以在不通知客户端的情况下做性能优化；③ 「接口 + 实现类」让「多种实现共存、按需切换」成为默认设计（Reading 12）。

代码示例与对比分析

场景 1：Wallet 与 Person 的访问控制——public 字段让抽象边界彻底消失

❌ 错误代码

/** 错误：字段全部 public，"抽象边界"根本不存在。 */
public class Wallet {
    public int amount;                          // 错误：表示直接公开

    public Wallet(int amount) { this.amount = amount; }

    /** put all of this wallet's money into that wallet */
    public void loanTo(Wallet that) {
        that.amount += this.amount;
        this.amount = 0;
    }
}

class Person {
    public Wallet w;                            // 错误：连"人有钱包"这个字段也公开

    public Person(Wallet w) { this.w = w; }

    public int getNetWorth() {
        return w.amount;                        // 客户端直接读 Wallet 的 rep
    }

    public boolean isBroke() {
        return w.amount == 0;                   // 同一份 rep 依赖出现在多个类里
    }
}

class Client {
    void broken(Wallet mine, Person p) {
        mine.amount = -100;                     // 造出负余额，编译器不拦
        doubleIt(mine);                         // 别名：调用者手里的钱包被"隔空"改了
        p.w = null;                             // 连"这个人的钱包"都能被抹掉
        System.out.println(p.getNetWorth());    // 运行时 NullPointerException
    }

    /** 把传入钱包的钱翻倍 —— 它是个修改者，但没有任何操作约束 */
    void doubleIt(Wallet w) {
        w.amount *= 2;
    }
}

【错误代码的问题】

1. 抽象边界不存在：所有字段都是 public，客户端（Person、Client）可以直接读写 Wallet 与 Person 的 rep，这既是表示暴露，也让”这个类型的值始终合法”这一承诺无法兑现。
2. 不变量无处安放：amount 可以被设成负数（余额不变量被破坏），p.w 可以被置为 null（于是 getNetWorth() 抛 NullPointerException）。这些非法状态没有任何一个”关卡”能把它们挡住。
3. 表示再也换不掉：客户端依赖”Wallet 里有一个 int amount“这个实现事实。将来想改成 long、想改成”余额 = 现金 + 信用额度”的复合表示、或想加一笔交易日志，所有写过 w.amount 的代码都要跟着改——表示独立被彻底摧毁。
4. private 本可以在编译期就全部拦住：只要把这些字段设为 private，mine.amount = -100、p.w = null、doubleIt 里的 w.amount *= 2 会全部变成静态错误。这是”错误在编译期暴露”与”错误在运行时爆炸”的区别。

✅ 正确代码

/** 正确：private 字段 + 一组定义了抽象的操作（含前置条件校验）。 */
public class Wallet {
    private int amount;                     // 表示：只有本类内部可见

    /**
     * creator : int -> Wallet
     * @param amount 初始金额，要求 amount >= 0
     */
    public Wallet(int amount) {
        if (amount < 0) throw new IllegalArgumentException("negative amount");
        this.amount = amount;
    }

    /** observer : Wallet -> int */
    public int getAmount() { return amount; }

    /**
     * mutator : Wallet x Wallet -> void
     * @param that 收款方，要求 that != null
     */
    public void loanTo(Wallet that) {
        // put all of this wallet's money into that wallet
        that.amount += this.amount;         // 允许：private 按类授权，同类内部可见
        amount = 0;                         // 等价于 this.amount = 0
    }

    /**
     * mutator : Wallet x int -> void
     * @param delta 变动金额，要求 amount + delta >= 0
     */
    public void adjust(int delta) {
        if (amount + delta < 0) throw new IllegalArgumentException("would go negative");
        amount += delta;
    }
}

class Person {
    private Wallet w;                       // 表示：private

    public Person(Wallet w) { this.w = w; }

    /** observer : Person -> int */
    public int getNetWorth() {
        return w.getAmount();               // 通过操作读取，绝不碰别人的 rep
    }

    /** observer : Person -> boolean */
    public boolean isBroke() {
        return w.getAmount() == 0;          // 注意：原文写的 Wallet.amount == 0 是静态错误
    }
}

class Client {
    void correct(Wallet mine, Wallet yours, Person p) {
        mine.loanTo(yours);                 // 只有操作能改状态
        int worth = p.getNetWorth();        // 只有观察者能读状态
        // mine.amount = -100;              // 静态错误：amount has private access in Wallet
        // p.w = null;                      // 静态错误：w has private access in Person
    }
}

【为什么这样更好】

private 把表示关进类内部，客户端能用的只剩 Wallet(int)、getAmount()、loanTo(Wallet)、adjust(int) 与 Person.getNetWorth() / isBroke() 这几个操作，抽象边界由编译器强制。所有会改变状态的操作都集中在 loanTo 与 adjust 两处，adjust 在入口校验”不能变成负数”，构造器在入口校验”初始金额不能为负”——不变量因此有了单一守卫点。将来把 amount 换成 long、拆成复合表示、或加一层内部缓存，只要这些操作的规格不变，客户端一行都不用改。

【代码对比解说】

两个版本用的是完全相同的类名与操作名，差别只有两处：字段可见性，以及”改动状态是否必须经过带校验的操作”。这正说明抽象边界在 Java 里就是由 public / private 这两个关键字落地的。有三个细节值得记住：

• Java 的 private 是类级授权，不是对象级：loanTo 里写 that.amount += this.amount 访问另一个 Wallet 对象的 private 字段是合法的；而 Person 类里写 w.amount 就是静态错误；Wallet.amount == 0 更是双重错误——既 private，又是实例变量而非 static，不能通过类名访问。
• 原文的例子把 main 写在 Wallet 类内部，于是 w.amount = 100 竟然合法。这提醒我们：可见性取决于”代码挂在哪一层”，而不是”谁在运行”。把这样的代码放在 Wallet 类里能编译，不代表它是一个好的设计——它只是把客户端逻辑塞进了实现者的地盘。
• 原文还留了一个”别名 + 修改者”的思考题：w.loanTo(w) 时 this 与 that 是同一个对象，that.amount += this.amount 先把余额变成两倍，紧接着 amount = 0 又把它清零。操作能编译不等于语义明确——规格应当说明这种自转账情形下的预期结果，客户端才不会依赖某个偶然实现。

【设计原则透视】

这一组对比是抽象边界（abstraction barrier）的最直接演示：Wallet 的规格 = 四个操作及其前置/后置条件；private int amount 是表示；loanTo 的方法体是实现。三者分清之后，”这条 w.amount = 100 该不该存在”就有了判据：它把表示写进了客户端，属于越界。这也正是 Reading 06 规格说明所要求的”合同”、Reading 08 不可变性所强调的”不要让外部拿到可变状态”、以及 Reading 11 中”表示不变量与防表示暴露”的前置准备。注意 adjust 的 throw new IllegalArgumentException(...) 属于前置条件被违反时的快速失败（fail fast），与 Reading 09 避免调试中的思路一致：宁可响亮地崩，也不要静默地把对象弄坏。

场景 2：Family 的表示依赖——公开 rep 让客户端与「用 List 还是用 Set」死绑

❌ 错误代码

import java.util.List;

class Person {
    private final String name;
    private final int age;
    Person(String name, int age) { this.name = name; this.age = age; }
    public String getName() { return name; }
    public int getAge() { return age; }
}

/**
 * Represents a family that lives in a household together.
 * A family always has at least one person in it.
 * Families are mutable.
 */
class Family {
    // the people in the family, sorted from oldest to youngest, with no duplicates.
    public List<Person> people;              // 错误：表示直接公开

    /** @return a list containing all the members of the family, with no duplicates. */
    public List<Person> getMembers() {
        return people;                       // 错误：把 rep 本身返回出去
    }
}

class Client {
    void client1(Family f) {
        // get youngest person in the family
        Person baby = f.people.get(f.people.size() - 1);   // 依赖"people 是 List，且按年龄排序"
    }

    void client2(Family f) {
        int familySize = f.people.size();                  // 依赖 rep 的类型
    }

    void client3(Family f) {
        Person anybody = f.getMembers().get(0);            // 表面上走了操作，实际依赖返回顺序
    }

    void destroy(Family f) {
        f.people.clear();                                  // 客户端可以清空这个家庭
    }
}

【错误代码的问题】

1. 表示的变更会成为客户端的地震：把 people 从 List<Person> 换成 Set<Person>（一个语义上完全合理的等价表示）后，client1 与 client2 立刻变成静态错误——它们编译不过了，必须逐个改写。这正是原文 Representation 1 / 2 练习要你识别的情形。
2. 最危险的一类依赖连编译器都发现不了：client3 写的是 f.getMembers().get(0)，改动后依然能编译通过；如果 getMembers 的元素顺序变了（例如改用 HashSet 后），client3 会静默地得到另一个答案。原文 Representation 3 的答案就是这一类：依赖存在、无静态错误、无动态错误，但结果不同。
3. 不变量无法维护：getMembers() 返回 rep 本身，客户端一次 clear() 或 add() 就可能破坏”至少一人”“无重复”“按年龄排序”这些 rep 的内部约定，而实现者对此毫无办法。
4. 规格被实现细节污染：因为 people 是 public，它的类型与顺序事实上已成为规格的一部分，抽象边界形同虚设。

✅ 正确代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Person {
    private final String name;
    private final int age;
    Person(String name, int age) { this.name = name; this.age = age; }
    public String getName() { return name; }
    public int getAge() { return age; }
}

/**
 * Represents a family that lives in a household together.
 * A family always has at least one person in it. Families are mutable.
 */
class Family {
    // rep：成员按从长到幼排序，且无重复（对客户端不可见）
    private final List<Person> people;

    /**
     * creator : List<Person> -> Family
     * @param members 家庭的成员，必须至少有一人；
     *                调用者之后修改 members 不会影响本对象
     */
    public Family(List<Person> members) {
        if (members.isEmpty()) {
            throw new IllegalArgumentException("a family has at least one person in it");
        }
        this.people = new ArrayList<>(members);                                  // 防御性拷贝
        this.people.sort(Comparator.comparingInt(Person::getAge).reversed());    // 维护 rep 的顺序约定
    }

    /** mutator : Family x Person -> void */
    public void add(Person p) {
        people.add(p);
        people.sort(Comparator.comparingInt(Person::getAge).reversed());
    }

    /**
     * observer : Family -> List<Person>
     * @return a list containing all the members of the family, with no duplicates.
     */
    public List<Person> getMembers() {
        return new ArrayList<>(people);   // 返回副本：客户端改不动 rep
    }

    /** observer : Family -> int */
    public int size() {
        return people.size();
    }
}

class Client {
    void client2(Family f) {
        int familySize = f.size();        // 只依赖操作，不依赖 rep 的类型
    }
}

【为什么这样更好】

people 变成 private final（并做了防御性拷贝）之后，客户端能用的只剩 Family(...)、add、getMembers、size 这几个操作。此时把 rep 从 List<Person> 换成 Set<Person>（或换成两个字段 nuclear + others）都不影响客户端：size() 对 List 和 Set 都成立，getMembers() 里的 new ArrayList<>(people) 对任何 Collection 都成立。这就是表示独立的直接收益。同时，”至少一人”“无重复”“有序”这些约定被集中在构造器与 add 两处维护，任何一次修改都必须过这两道关卡，不变量难以被绕过。

【代码对比解说】

两种写法的 getMembers() 签名一模一样，差别只在 return people; 与 return new ArrayList<>(people); 这一行。这一行是”是否暴露表示”的分水岭。但请注意一个更深的层次：返回副本只解决了”结构被改”，没有解决”顺序被依赖”。如果规格只承诺”返回全部成员、无重复”，那么 client3 里 getMembers().get(0) 取到的究竟是”最年长者”还是”任意一人”就取决于实现——这是规格的充分性问题，只能靠把顺序写进后置条件（或干脆提供一个语义明确的 oldest() 观察者）来解决。原文 Representation 4 的练习正是在训练这种分层判断：哪一行是规格、哪一行是表示、哪一行是实现。

【设计原则透视】

这一组对比是表示独立（representation independence）的标准教案：private 字段 + 规格完整的 public 操作 = 客户端与表示解耦。返回副本则对应 Reading 08 的防御性拷贝与 Reading 11 的防表示暴露。Family 是可变类型（有 add 这个 mutator），因此返回副本是必需的；如果 Family 设计成不可变类型（add 改成返回新 Family 的 producer），客户端拿到共享引用也仍然安全——这是”用不可变性替代拷贝”的另一条路。

场景 3：MyString 的 creator 与表示替换——从「独占数组」换成「共享数组 + 区间」

❌ 错误代码

/** 错误：public 字段把表示变成规格；构造器保存调用者的数组；观察者返回内部数组。 */
public class MyString {
    public char[] a;                                  // 错误：rep 完全公开

    /** @param a 字符数组；长度为字符串长度 */
    public MyString(char[] a) {
        this.a = a;                                   // 错误：直接保存调用者的数组引用
    }

    /** @return number of characters in this string */
    public int length() { return a.length; }

    /** @param i character position (requires 0 <= i < string length) */
    public char charAt(int i) { return a[i]; }

    /** producer : MyString x int x int -> MyString */
    public MyString substring(int start, int end) {
        char[] sub = new char[end - start];
        System.arraycopy(this.a, start, sub, 0, end - start);
        return new MyString(sub);
    }
}

class Client {
    void broken(MyString s) {
        char c = s.a[0];                              // 直接读 rep：与"内部是 char[]"死绑
        s.a[0] = 'X';                                 // 直接改 rep：破坏对象内容
        char[] raw = new char[] { 'h', 'i' };
        MyString t = new MyString(raw);
        raw[0] = 'X';                                 // 别名：外部数组一改，t 也跟着变
    }
}

【错误代码的问题】

1. 表示无法更换：客户端只要写过一次 s.a，实现者就再也不能把 rep 换成别的结构（例如带 start/end 的共享数组），否则客户端编译不过。原文的正向例子（MyString 的两种 rep）之所以成立，正是因为字段是 private。
2. 别名导致内容可被外部篡改：new MyString(raw) 保存了 raw 的引用，随后 raw[0] = 'X' 会改变 t 看到的字符串——这个类型已经不再是”不可变的字符序列”了。
3. 不变量无守卫：没有校验也没有拷贝，客户端可以构造出与内部约定冲突的对象（例如 substring 的调用者拿到数组后自行缩短它）。
4. creator 集合失控：public 的 MyString(char[]) 加上隐式的默认构造器，意味着客户端可以用任何方式造出对象，实现者无法保证”每个 MyString 都处于合法状态”。

✅ 正确代码

/** MyString represents an immutable sequence of characters. */
public class MyString {

    //////////////////// 表示（private，客户端不可见） ////////////////////
    private char[] a;

    private MyString() { }   // 不开放默认构造器：客户端只能通过 valueOf / substring 得到对象

    //////////////////// Example of a creator operation ////////////////////
    /**
     * @param b a boolean value
     * @return string representation of b, either "true" or "false"
     */
    public static MyString valueOf(boolean b) {
        MyString s = new MyString();
        s.a = b ? new char[] { 't', 'r', 'u', 'e' }
                : new char[] { 'f', 'a', 'l', 's', 'e' };
        return s;
    }

    //////////////////// Examples of observer operations ////////////////////
    /**
     * @return number of characters in this string
     */
    public int length() { return a.length; }

    /**
     * @param i character position (requires 0 <= i < string length)
     * @return character at position i
     */
    public char charAt(int i) { return a[i]; }

    //////////////////// Example of a producer operation ////////////////////
    /**
     * Get the substring between start (inclusive) and end (exclusive).
     * @param start starting index
     * @param end ending index. Requires 0 <= start <= end <= string length.
     * @return string consisting of charAt(start)...charAt(end-1)
     */
    public MyString substring(int start, int end) {
        MyString that = new MyString();
        that.a = new char[end - start];
        System.arraycopy(this.a, start, that.a, 0, end - start);
        return that;
    }

    /////// no mutator operations (why not?)
}

class Client {
    void correct() {
        MyString s = MyString.valueOf(true);      // s 表示 "true"
        MyString t = s.substring(1, 3);           // t 表示 "ru"
        char c = t.charAt(0);                     // 只能通过观察者取值
        int n = t.length();                       // n == 2
    }
}

表示变更后的版本（客户端代码一行不改）：

/** MyString represents an immutable sequence of characters. */
public class MyString {

    // 新表示：共享同一个字符数组，用 [start, end) 区间描述本对象代表的那一段
    private char[] a;
    private int start;
    private int end;

    private MyString() { }

    public static MyString valueOf(boolean b) {
        MyString s = new MyString();
        s.a = b ? new char[] { 't', 'r', 'u', 'e' }
                : new char[] { 'f', 'a', 'l', 's', 'e' };
        s.start = 0;
        s.end = s.a.length;
        return s;
    }

    public int length() { return end - start; }

    public char charAt(int i) { return a[start + i]; }

    public MyString substring(int start, int end) {
        MyString that = new MyString();
        that.a = this.a;                       // 共享数组：只有不可变类型才敢这么做
        that.start = this.start + start;
        that.end = this.start + end;
        return that;
    }
}

【为什么这样更好】

表示变成 private 之后，客户端能观察到的只有 length() / charAt() / substring() 的行为。把「独占数组」换成「共享数组 + start/end」时，MyString.valueOf(true).substring(1,3).charAt(0) 的结果仍然是 'r'——客户端代码完全不需要修改，甚至不需要重新编译它的语义。这正是原文的结论：”Because MyString’s existing clients depend only on the specs of its public methods, not on its private fields, we can make this change without having to inspect and change all that client code. That’s the power of representation independence.”同时，把默认构造器改成 private 收紧了她 creator 集合：对象只能由 valueOf 或 substring 产生，实现者因此可以保证每个 MyString 的 rep 都合法。

【代码对比解说】

三个关键差异：① 字段从 public char[] a 变成 private char[] a（外加 private 构造器）；② 客户端从「读数组」变成「调操作」；③ 实现者获得了替换表示的许可。注意第二个版本做了一件在可变类型里绝对不允许的事：两个 MyString 对象共享同一个 char[]。它之所以安全，前提是没有任何 mutator 能改写这个数组——substring 只读、charAt 只读、length 只读。这也回答了原文的提问”为什么没有 mutator 操作？”：一旦加了 reverse() 之类的修改者，共享表示会把一个对象的修改传播到所有共享它的对象上，共享优化必须立刻回退成独占拷贝。另外注意原文示例的一个细节：sp21 原文里 valueOf 内部写的是 new MyString()，依赖 Java 隐式的默认构造器——那个默认构造器是 public 的，等于漏了一个 creator。本笔记的正确版本显式声明了 private MyString() { } 来堵住它。

【设计原则透视】

这是本讲的核心画面：操作集合 = 抽象（公开），字段 = 表示（私有），二者之间是抽象边界。valueOf 是构造者（boolean → MyString），length / charAt 是观察者（MyString × int → int/char），substring 是生产者（MyString × int × int → MyString），没有修改者——所以 MyString 是不可变类型。测试这个 ADT 时（Reading 03 测试与原文的 testing strategy），分区只能基于抽象状态（字符串长度、this 由 valueOf 还是 substring 产生），绝不能基于 rep 里的 a.length 或 start/end。

场景 4：String 与 StringBuilder——同一个”字符串”的可变版与不可变版，如何决定共享是否安全

❌ 错误代码

import java.util.ArrayList;
import java.util.List;

/** 错误：把可变的 StringBuilder 当作"值"到处传递与共享。 */
public class TextLog {
    private final StringBuilder buffer = new StringBuilder();   // rep 本身可变

    /** mutator : TextLog x String -> void */
    public void add(String line) {
        buffer.append(line).append('\n');
    }

    /** 错误：把内部可变对象直接发出去 */
    public StringBuilder getBuffer() {
        return buffer;
    }
}

class Client {
    void broken(TextLog log) {
        log.add("first");
        StringBuilder shared = log.getBuffer();
        shared.append("injected\n");        // 别名：隔空改了 log 的内容

        // 把同一个 StringBuilder 交给两个"值"
        StringBuilder sb = new StringBuilder("ab");
        List<StringBuilder> list = new ArrayList<>();
        list.add(sb);                        // list 与 sb 是别名
        sb.append("c");                      // list.get(0) 的内容也变了
        String snapshot = sb.toString();     // 只得手动"快照"才能得到稳定值
    }
}

【错误代码的问题】

1. 表示暴露：getBuffer() 返回内部 StringBuilder 的引用，客户端一次 append 就改掉了 TextLog 的内容，TextLog 对它自己的状态再也没有任何保证。
2. 别名导致”值”不稳定：sb 与 list.get(0) 指向同一个可变对象，sb.append("c") 会改变列表里那个元素看到的内容。如果这段代码依赖”我先记下这个字符串，稍后再比对”，结果就会随执行顺序变化——这正是 Reading 08 里可变对象与别名分析的经典陷阱。
3. 共享变得不可能：因为内容随时可能被改，任何”多处共享同一个 StringBuilder“的设计都要附带一整套纪律（谁都不许 append），而这种纪律无法由编译器强制。
4. 可变对象不能安全地”存起来当值用”：把它放进集合、作为键、或跨方法传递，都需要额外约定；StringBuilder 的 equals 是引用相等，因此它作为值类型也没有正确的语义（见 Reading 15 相等性）。

✅ 正确代码

import java.util.ArrayList;
import java.util.List;

/** 正确：把不可变的 String 当值用，producer 负责组合出新的 String。 */
public class TextLog {
    private String text = "";             // rep：不可变类型，因此"换值"就是换引用

    /** mutator : TextLog x String -> void */
    public void add(String line) {
        text = text.concat(line).concat("\n");   // String.concat 是 producer：产生新串
    }

    /** observer : TextLog -> String */
    public String getText() {
        return text;                      // 安全：String 不可变，发出去也没人能改
    }

    /** producer : TextLog -> TextLog（可选的不可变风格） */
    public TextLog withLine(String line) {
        TextLog that = new TextLog();
        that.text = this.text.concat(line).concat("\n");
        return that;
    }
}

class Client {
    void correct(TextLog log) {
        log.add("first");
        String snapshot = log.getText();   // snapshot 是稳定值，之后永不变
        log.add("second");                 // 不影响 snapshot
        boolean ok = snapshot.equals("first\n");   // 用 equals 比值（见 Reading 15）

        // 需要大量拼接时，才在"局部"使用 StringBuilder，用完立刻转成 String
        StringBuilder sb = new StringBuilder();
        for (String line : new ArrayList<String>()) {
            sb.append(line).append('\n');
        }
        String built = sb.toString();      // 到边界处立刻"不可变化"，不再外泄 sb
    }
}

【为什么这样更好】

TextLog 的 rep 换成不可变的 String：add 用 concat 产生新串并把字段指向它，于是”值”一旦读出（snapshot）就永远不会变——客户端可以放心地保存、传递、比较。getText() 直接返回内部 String 也没有任何风险，因为 String 是不可变类型：没有 append、setCharAt 这类 mutator，任何人都改不了它。只有在”需要大量就地拼接”时（String 每次 concat 都要复制，成本 O(n)）才在方法内部使用 StringBuilder，并在返回边界上立刻 toString() 转成不可变值——把可变性限制在一个尽可能小的作用域里，不让它跨过抽象边界。

【代码对比解说】

两个版本的公开操作几乎一样（add + 读取内容），差别在于 rep 的类型与是否有可变状态外泄的通道。这正好对应本讲原文对类型的分类：String 是不可变类型，没有 mutator，所有”看起来会改”的操作（concat、substring、toUpperCase）都是 producer；StringBuilder 是可变类型，append、reverse 既是 mutator 又返回 this（因此也是 producer），而原文特别提醒：StringBuilder 是 String 的可变版本，但二者不是同一个 Java 类型，也不能互换。还有一个容易被忽略的点：不可变带来的收益不只是”安全”，还有”可以自由共享”。MyString 的 substring 之所以能共享底层字符数组、String 之所以能在语言层面被广泛传递，都是因为没人能改它们；而一个可变的 StringBuilder 一旦被两个地方持有，就必须靠纪律（而不是靠编译器）来维持正确性。

【设计原则透视】

这是 Reading 08 不可变性在类型选择层面的应用：先决定”这个类型的值会不会变”，再决定 rep 用什么类型、观察者能否直接把 rep 发出去。TextLog 的 rep 若是可变的 StringBuilder，就必须做防御性拷贝（返回 new StringBuilder(buffer) 或 buffer.toString()）；若换成不可变的 String，把 private 字段直接返回也完全安全——不可变性可以替代拷贝。另外注意 StringBuilder 的 equals 是引用相等（没有覆写），所以它作为值类型是残缺的，这一点由 Reading 15 相等性展开；而 String 的 equals 是按内容比较，才让它真正能当”值”用。

场景 5：Deck 与 List——把通用特征和领域特征混进同一个 ADT 的代价

本讲原文在”设计抽象类型”一节给出一条规则：类型可以是通用的（generic，如 list / set / graph），也可以是领域特定的（domain-specific，如街道地图、员工数据库、电话簿），但不应该把两者混在一起——”一个用来表示一副扑克牌的 Deck 类型，不应该有接受整数或字符串这类任意对象的通用 add 方法；反过来，把 dealCards 这种领域特定方法塞进通用的 List 里也毫无意义。”原文只给了这条规则，下面两块代码是它的具体化（Deck 属于领域特定类型，List 属于通用类型）。

❌ 错误代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/** 错误一：领域特定的牌堆，却带了一个接受任意对象的通用 add。 */
public class Deck {
    private final List<Object> cards = new ArrayList<>();   // Object：什么都能塞

    /** 通用 add：签名上不限制类型，"一副牌"里可以混进整数和字符串 */
    public void add(Object item) {
        cards.add(item);
    }

    public void shuffle() {
        Collections.shuffle(cards);
    }

    public int size() { return cards.size(); }
}

/** 错误二：给通用的 List 加领域特定方法 —— 这里用工具类的形式演示同样的错误。 */
class ListUtils {
    /** 对"任意列表"做发牌，但发牌只对牌堆有意义 */
    public static List<Object> dealCards(List<Object> list, int hands) {
        List<Object> result = new ArrayList<>();
        for (int i = 0; i < hands; i++) {
            result.add(list.get(i % list.size()));
        }
        return result;
    }
}

class Client {
    void broken() {
        Deck deck = new Deck();
        deck.add("Ace of spades");   // 字符串，居然合法
        deck.add(42);                // 整数，也合法
        deck.add(new Deck());        // 连牌堆都能塞进牌堆
        deck.shuffle();              // 混着 Integer 和 Deck 的"牌"根本没法洗

        List<Object> notADeck = new ArrayList<>();   // 这是员工名单，不是牌堆
        ListUtils.dealCards(notADeck, 3);            // 却能被"发牌"
    }
}

【错误代码的问题】

1. 操作集合失去一致性（coherent）：Deck.add(Object) 在签名上对”牌”没有任何约束，客户端可以往一副牌里塞整数、字符串甚至另一个 Deck。类型名承诺的”一副扑克牌”与它实际能表示的值完全脱节。
2. 不变量被架空：Deck 想维护的任何性质（例如”只能有 52 张”“每张牌唯一”“花色只能是四种”）都无法在 add(Object) 这一层检查，因为参数类型里没有足够的信息。
3. 领域操作污染通用类型：dealCards 只对牌堆有意义，却被挂在一个”对任意列表都适用”的位置上。任何看到它的程序员都要先判断”这个列表到底是不是牌堆”，而编译器一个都不拦——List<Object> 员工名单 照样能被”发牌”。
4. 表示与语义都难以演化：因为 cards 是 List<Object>，将来想换成”按花色分桶”的表示、或想给 Deck 加 sortBySuit()，都会被”元素可能是任何东西”这个前提卡住。

✅ 正确代码

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/** 领域特定类型：元素类型固定，操作只谈"牌"这一件事。 */
public final class Deck {
    private final List<String> cards = new ArrayList<>();   // rep：只装"牌"的表示

    /** creator : -> Deck（一副 52 张的标准牌堆） */
    public Deck() {
        for (String suit : new String[] { "clubs", "diamonds", "hearts", "spades" }) {
            for (int rank = 1; rank <= 13; rank++) {
                cards.add(rank + " of " + suit);
            }
        }
    }

    /**
     * mutator : Deck x int -> List<String>
     * @param n 要发出的牌数，要求 0 <= n <= size()
     * @return 发出的 n 张牌（从牌堆顶部取走）
     */
    public List<String> dealCards(int n) {
        if (n < 0 || n > cards.size()) throw new IllegalArgumentException("bad n");
        List<String> hand = new ArrayList<>(cards.subList(0, n));
        cards.subList(0, n).clear();
        return hand;
    }

    /** mutator : Deck -> void */
    public void shuffle() { Collections.shuffle(cards); }

    /** observer : Deck -> int */
    public int size() { return cards.size(); }
}

class Client {
    void correct() {
        Deck deck = new Deck();          // 52 张，类型固定
        // deck.add("whatever");         // 静态错误：Deck 没有通用 add
        List<String> hand = deck.dealCards(5);
        int rest = deck.size();          // 47
    }
}

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/** 通用类型：只提供少量能强力组合的简单操作，绝不掺入领域概念。 */
class ListUtils {
    /** producer : List<T> x int -> List<T>（通用：与"牌"毫无关系） */
    public static <T> List<T> take(List<T> list, int n) {
        return new ArrayList<>(list.subList(0, n));
    }

    /** mutator : List<T> -> void */
    public static <T> void sort(List<T> list, java.util.Comparator<? super T> cmp) {
        Collections.sort(list, cmp);
    }
}

class Client2 {
    void correct() {
        // "发牌"由 Deck 提供；"取前 n 个"由通用工具提供，二者互不侵入
        Deck deck = new Deck();
        List<String> hand = ListUtils.take(new ArrayList<>(deck.dealCards(5)), 2);
    }
}

【为什么这样更好】

Deck 的元素类型被钉死为”牌”，构造器一次性保证”标准 52 张”这个不变量，所有操作都只说牌堆的语言（dealCards、shuffle、size），领域概念不会泄漏到别处。通用的 ListUtils.take 则刻意不认识”牌”：它是一个泛型方法，对任何 List<T> 都成立，因此放在通用层完全合理。两者的分工恰好对应原文的两句话——Deck 不该有通用 add，通用 List 不该有 dealCards。此外 Deck 只有 size 与 dealCards 两个读取入口、一个 shuffle 修改入口，操作集合”少而简单”，客户端能做的组合却足够多。

【代码对比解说】

错误版本的问题不在”少写了校验”，而在类型的粒度选错了：Deck 被写成了一个”可以装任何东西的容器”，于是它不再是一个 ADT，只是一个恰好叫 Deck 的 ArrayList。正确版本把”牌”这个领域概念固化进类型，把”取前 n 个元素”这类真正通用的能力留在通用层，于是每一层都只有一个 concern（separation of concerns）。这也顺带解决了另一类隐患：Deck.add(Object) 让 Deck 的规格无法写清（”能加什么？”答不上来），而 Deck.dealCards(int) 的规格一句话就写完（前置条件 0 <= n <= size()，后置条件”返回取走的牌、牌堆少 n 张”）。判断一个方法该挂在哪里，有个简单测试：把类型名遮住，这个方法还讲得通吗？ take(list, n) 遮住类型名依然成立；dealCards(list, n) 就不成立了——它偷偷假设了 list 是牌堆。

【设计原则透视】

这一组对比把本讲”设计抽象类型”的四条法则全部串了起来：① 少而简单（Deck 只有三个操作）；② 行为一致、无特例（dealCards 不需要”如果元素不是牌该怎么办”这种分支）；③ 操作集合足够（size + dealCards + shuffle 足够表达客户端要做的计算）；④ 通用与领域特定不混。它同时是”表示独立”的前提：只有当操作集合语义清晰，实现者才可能把 List<String> 换成”四个花色桶”甚至”一个 52 位掩码”而不影响客户端。这一点会在 Reading 12（接口与泛型）里以更形式化的方式出现——泛型参数 T 正是”通用 ADT”在类型系统里的写法，而领域特定类型则把它固定成具体的元素类型。

与其他设计原则的关联

• 与 Reading 06（规格说明 Specifications）：ADT 的规格就是「操作集合 + 每个操作的前置条件与后置条件」。本讲反复强调，只有当操作被完整规格化时，实现者才敢更换表示——因此 Reading 06 的规格写作能力是表示独立的前置技能。
• 与 Reading 07（设计规格 Designing Specifications）：规格的强弱、确定性、声明式写法决定了 ADT 留给实现者多少自由。规格写得过强（例如把”内部用数组”写进后置条件）会直接摧毁表示独立；写得过弱则客户端不敢依赖，抽象边界名存实亡。
• 与 Reading 08（不可变性 Immutability）：本讲把 Reading 08 的”可变 vs 不可变”“别名”“防御性拷贝”从单个对象提升到类型层面：可变类型与不可变类型各自需要什么样的字段可见性、是否必须拷贝、能否共享内部数据（MyString.substring 的共享数组优化）。
• 与 Reading 09（避免调试 Avoiding Debugging）：private 让越界访问变成编译期错误，这就是 fail fast 在类型边界上的版本；Wallet 例子里那几个”静态错误”正是这种保护的直接体现。
• 与 Reading 11（抽象函数与表示不变量 Abstraction Functions & Rep Invariants）：本讲说”要有 rep 且必须是 private”，Reading 11 接着回答”rep 与抽象值之间如何精确对应”——抽象函数（AF）、表示不变量（RI）、以及如何系统地排查表示暴露。两讲合起来才是完整的 ADT 设计方法。
• 与 Reading 12（接口与泛型，兼枚举 Interfaces, Generics, Enums）：List + ArrayList 展示了「接口声明操作、实现类提供表示」的结构，这是表示独立在语言层面的最强形式；泛型让 ADT 从”字符串的列表”变成”任意类型的列表”，也正是本讲 Deck（领域特定）与 List（通用）分工在类型系统里的写法；enum 则为小固定值集合（如原文举的 DayOfWeek）提供了一种现成的 ADT 实现方式。
• 与 Reading 15（相等性 Equality）：原文明确指出，在 MyString 还没有定义 equals 之前，测试里不能直接 assertEquals 两个 MyString 对象。相等性与哈希本身也是 ADT 的观察者/操作，必须按规格谨慎实现。
• 与 Reading 17（递归数据类型 Recursive Data Types）：ADT 的思想在递归数据类型里进一步升级为数据类型定义，例如 ImList<E> = Empty + Cons(first:E, rest:ImList<E>)——一个抽象类型由若干具体表示（Empty 与 Cons）共同实现，操作则按表示递归定义。
• 与 Reading 21 / 23（并发 Concurrency / 互斥 Mutual Exclusion）：不可变 ADT 天然线程安全，是并发编程里最省心的共享方式；可变 ADT 一旦被多线程共享，就必须靠锁把 mutator 保护起来。

关键要点

• 用操作定义类型：写一个类型时先写出它的操作集合与每个操作的规格；这套东西就是类型的全部含义，字段只是”若干种可能实现之一”。
• 字段一律 private，只有构成抽象的操作才 public；同时检查构造器可见性——不写构造器时 Java 会补一个 public 默认构造器，等于凭空开放了一个 creator。
• 把每个操作归类（creator / producer / observer / mutator），并用分类表核对：creator 的输入不含 T、输出是 T；producer 吃 T 返回新 T；observer 吃 T 返回别的类型；mutator 修改对象（返回值可以是 void、其他类型甚至 T）。别忘了实例方法的隐式 this。
• 可变类型必须做防御性拷贝（构造器入口 + 观察者出口，两个方向都要），并且在加入 mutator 后重新审视所有”共享内部数据”的优化；不可变类型则可以把 final 字段直接共享出去。
• 先定规格，再改表示：只要操作的规格不变，rep 就可以整体替换（char[] ↔ char[] + start/end、List ↔ Set）；反过来，只要客户端依赖了 rep，”改实现”就会变成”改所有客户端”。

常见陷阱与注意事项

• 把字段写成 public 图方便 → 表示暴露：客户端直接读写 rep，不可变类型的不可变性当场失效，而且从此无法再更换表示（原文的 Wallet.amount、Family 的 client1 直接读 f.people、MyString.a 都是这个坑）。
• 观察者直接返回内部的可变对象，或以为 final 就等于不可变 → 别名攻击：getTimestamp() 返回内部 Date 后，客户端一次 setHours 就改掉了对象内部状态；而 private final Date timestamp 也只保护”引用不被重新赋值”，Date 里的毫秒值照样能被 setTime 改掉。只在一侧做拷贝（只在构造器、或只在观察者）都不够，必须双向。
• 把隐式默认构造器当成”没有构造器” → 你其实开放了一个 public 的 creator：客户端可以 new MyString() 造出 rep 未初始化（字段为 null）的坏对象。要限制创建途径，就把构造器显式声明为 private，只用工厂方法对外。
• 客户端依赖 rep 但仍能编译 → 最危险的坏味道：如 f.getMembers().get(0) 依赖返回顺序、s.a[0] 依赖内部是数组。这类依赖既不给静态错误也不给动态错误，只在某次实现调整后静默给出错误答案。判断标准很简单：客户端代码里出现任何 rep 的类型或顺序假设，就是越界。
• 测试时按 rep 分区 → 测试与实现死死绑定：按 rep 数组的长度、rep 里的 start/end 分区，会让”换表示就换测试”，一组本可用于验证表示独立的测试全部作废。应当按抽象状态（抽象长度、this 由哪个 creator 产生）分区。
• 把通用特征与领域特征混在同一个 ADT 里 → 操作集合失去一致性：给 List 加 sum（对字符串列表、嵌套列表无从定义），或给 Deck 加接受任意 Object 的 add（牌堆里混进整数）。正确做法是另建专门的类型，或让客户端用简单操作组合出所需计算。

思考题（带答案）

问题 1：原文说”每个操作应该有明确的目的、行为一致（coherent），而不是一堆特例”，并举例说不应该给 List 加一个 sum 操作。请解释为什么 sum 会破坏 List 的一致性；并说明如果一个真实项目确实需要”把一串数字加起来”，按本讲的设计法则应该怎么做。

答案：List 是一个通用（generic）的 ADT：它的操作集合必须对所有可能的元素类型都有意义（get、size、add、remove……）。而 sum 只在”元素是可相加的数”时才有定义：List<String> 上没有意义；List<List<Integer>> 上要么无意义、要么需要额外规则（是”展平后求和”还是”元素求和”？）；元素是自定义类型时又需要某种累加协议。于是 sum 的规格里必然出现大量特例，客户端必须先判断”这个列表能不能 sum”，每个特例都增加理解成本。本讲的四条法则正好逐条命中：① “少而简单 > 多而复杂”——sum 是一个能用 get + 循环组合出来的复合操作；② “每个操作行为一致”，sum 做不到；③ “通用与领域特定不要混”，sum 是领域特征入侵通用类型；④ “操作集合要足够（adequate）”，List 已有的 get / size 已经足够表达求和的全部信息，所以撤掉 sum 不会让客户端”做不到某事”。正确做法是：让客户端用 get + 循环组合（这也是”少量简单操作可以强力组合”的体现），或者定义一个领域特定类型，让”求和”成为它自己领域内的操作（原文举的 Deck 就是这种”只谈自己领域概念、不掺通用特征”的类型）。反过来，把 dealCards 塞进通用的 List 是同一个错误的镜像。

问题 2：原文给出一个 ADT Bool，操作为 true : Bool、false : Bool、and : Bool × Bool → Bool、or : Bool × Bool → Bool、not : Bool → Bool，其规格就是这三个运算的常规真值表。下列五种实现方式中，哪些能够满足这些操作的规格？(a) 用一个比特，1 表示 true、0 表示 false；(b) 用一个数值，5 表示 true、8 表示 false；(c) 用一个字符串引用，"false" 表示 true、"true" 表示 false；(d) 用一个数值，所有取值都表示 true；(e) 用一个大于 1 的整数，素数表示 true、合数表示 false。

答案：(a)、(b)、(c) 都可以；(d)、(e) 不可以。

推理依据是”ADT 由操作与规格定义，与表示无关”这一核心思想：表示长什么样、编码取名多奇怪，都不影响它是否合法，唯一的标准是这些操作能否满足规格。

• (a) 可以。这是最自然的编码：and 用按位与、or 用按位或、not 用取反，真值表逐条成立。
• (b) 可以。只要把三个操作按 5 = true、8 = false 重新映射即可：not(5) = 8、not(8) = 5、and(5,5) = 5、and(5,8) = 8 等等。表示的具体数值完全不进入规格。
• (c) 可以。这一点最能说明”表示与语义无关”：编码字符串的字面意思（"true" 竟然表示 false）纯粹是内部约定，客户端永远看不到它，只看得到 and / or / not 的行为。
• (d) 不可以。规格要求 not(true) = false，也就是要求”取反后的结果与原来的值不同”；如果所有值都表示 true，那么 true 与 false 实际是同一个值，not 不可能把 true 变成 false。这说明 Bool 的规格蕴含了”类型至少有两个不同的值”。
• (e) 不可以。虽然”素数 / 合数”提供了一个二值划分，但 and(true, true) 要求值为 true，而两个素数之积必然是合数，按该编码 and 会返回 false，与真值表冲突。可见能否满足规格，取决于编码是否与所有操作相容，而不取决于编码本身是否”看起来合理”。

这题的实际意义是：当你要替换一个 ADT 的实现时，唯一需要检查的是”新表示能否满足全部操作的规格”——这正是”表示独立”的另一面。

问题 3：考虑原文的 Family ADT（成员构成一个 List<Person>，getMembers 返回全部成员、无重复）。(1) 原文的 client1（f.people.get(f.people.size()-1)）、client2（f.people.size()）、client3（f.getMembers().get(0)）在把 rep 从 List 改成 Set 之后分别会怎样？(2) 如果把 getMembers 改成 return new ArrayList<>(people);，是否就完全没有表示暴露了？请说明理由。

答案：

(1) 三者结果截然不同，正好构成”依赖表示”的三级后果：

• client1 直接读写 f.people，把 rep 当作 List 使用。改成 Set 后 Set 没有 get(int) 方法 → 静态错误（编译失败）。这类依赖至少是响亮的。
• client2 也直接访问 f.people.size()。Set 同样有 size()，看起来没问题——但它依赖的是rep 的类型：改动后如果换成一个没有 size() 的表示（例如换成两个字段 nuclear + others），立刻静态错误；即便这次侥幸编译通过，它的合法性完全靠”新表示恰好也有同名方法”来支撑，这是运气而非设计。原文把这一类归为”依赖表示、且没有被抽象边界保护”的情形。
• client3 走的是公开操作 f.getMembers()，改动后仍然编译通过、不抛异常，但结果可能不同：如果规格只承诺”包含所有成员、无重复”而未规定顺序，那么新实现返回的顺序变了，get(0) 取到的就不是原来那个人。这就是最危险的一类——静默地给出错误答案。它提醒我们：表示独立不仅仅是”不要读 private 字段”，还包括”不要依赖规格没有承诺的任何可观察性质”。

(2) 不够。返回 new ArrayList<>(people) 确实堵住了一个方向：客户端再也无法通过返回的列表改动 Family 的成员结构（不能 clear()、add()、sort()）。但它是浅拷贝：拷贝的只是”引用的序列”，Person 对象本身仍然是同一批对象。于是：① 如果 Person 是可变类型，客户端可以 getMembers().get(0).setName("X")，照样改掉 Family rep 里那个 Person 的内容，不变量（例如”按年龄排序”若依赖可变字段）被破坏；② 如果 rep 里存的是可变容器（例如 List<Person> 之外还有别的可变对象），浅拷贝同样挡不住。所以完整的做法是”两选一”：让元素类型不可变（Person 用 private final 字段、不提供 mutator），这样共享引用完全安全，浅拷贝足够；或者对可变元素做深拷贝（成本高、易漏，还要递归处理嵌套可变对象），并明确记录在规格里。此外还要注意：即使拷贝做全了，”返回顺序”这类性质仍需在规格里明确承诺，否则 client3 依然可能踩到静默错误。