Reading 26: 小语言 I（Little Languages I）

目录 · ← l25 · l27 →

Reading 26: 小语言 I（Little Languages I）

说明：本讲 sp22 原版使用 TypeScript（Music 接口、notes() 工厂函数、Pitch.make 等），本笔记按用户要求提供 Java 代码示例；类型/API 与 sp21（6.031 Java 版，Reading 27: Little Languages I）原文保持一致，并沿用课程的音乐语言（Music/Note/Rest/Concat/MusicLanguage/SequencePlayer/Pitch/Instrument）。凡属为演示目的而补充的内容（例如给 Reading 19 的 IntegerExpression 增加 Variable 变体以展示 eval(environment)），均明确标注为「补充说明」。

概述

本讲的主线只有一句话：当你需要解决一个问题时，不要只写一个解决这个问题的程序，而要构造一门能解决一整类相关问题的语言（when you need to solve a problem, instead of writing a program to solve just that one problem, build a language that can solve a range of related problems）。为此需要两个关键思想：一是把代码表示为数据（representing code as data），让表达式成为可以被存储、传递、操纵、延后求值的一等值；二是用递归数据类型（recursive data type）表示这门语言的抽象语法树，并按照解释器模式（Interpreter pattern）为它定义操作。它与三大目标的关系是：Safe from bugs（结构化表示替代大量重复的手写调用，减少人为失误；求值/解析逻辑可规格化、可测试）、Easy to understand（notes("C D E F G A B C'") 远比几十行 addNote 好读）、Ready for change（语言可以扩展出转调、变奏、混音等一整类新功能，而不必重写已有程序）。

核心概念与设计原则详解

把代码表示为数据（Representing Code as Data）

• 定义与目的：把”要做什么”编码成一个数据结构（Formula、IntegerExpression、Music），而不是写成一段立即执行的语句。它解决的是”我想在运行时操纵、保存、重复求值这段计算”的问题，直接关系到 Ready for change 与 Safe from bugs。
• 直观解释（”它是什么？”）：Java 里写 p && q，这个表达式一出现就被求值，结果是个 boolean；而 And(Variable("p"), Variable("q")) 是一个对象，它”记住”了这个公式的形状，你可以把它放进集合、写进文件、传给别的线程，也可以在需要时求值一次、两次或一百次。
• 关键规则与最佳实践：
  • 判断是否需要”把代码当数据”：是否需要在求值之前操纵它，或者需要求值多次/延后求值？是则建模为数据。
  • 课程的 Formula 类型是标准例子：命题逻辑公式 (p ∧ q) 表示为 And(Variable("p"), Variable("q"))；用文法与解析器的术语说，公式构成一门语言，而 Formula 是它的抽象语法树（abstract syntax tree, AST）。
  • 另一类”把代码当数据”的例子是函数对象（functional object）/一等函数：class AndFunction implements BiFunction<Boolean,Boolean,Boolean>，或 Java 的 lambda (p, q) -> p && q；它们同样是把计算变成可传递的值。
  • 数据的不可变性至关重要：AST 一旦构造就不再改变，才能安全地被共享、被多次求值（参见 Reading 8）。

小语言与领域特定语言（Little Language / Domain-Specific Language）

• 定义与目的：为某个狭窄领域设计的语言称为领域特定语言（domain-specific language, DSL），因为它的适用范围比 Java、Python 这类通用语言窄。本讲与下一讲要构造的音乐语言就是一门 DSL（little language）。它关系到 Easy to understand（领域内表达更简洁）与 Ready for change（语言可扩展）。
• 直观解释（”它是什么？”）：通用语言像”什么都能做的手术刀组合”；DSL 像专门切寿司的刀——只干一件事，但干得特别好、特别顺手。
• 关键规则与最佳实践：
  • 外部 DSL（external DSL）：自带语法与语义，独立于任何通用语言。本课程已经见过的例子是正则表达式、ParserLib 文法、以及 Problem Set 3 的语言（Memely）。
  • 内部 DSL（internal DSL）：嵌入在通用语言里，借用宿主语言的语法与抽象机制，不另造语法（课程在 sp22 用 TypeScript、sp21 用 Java）。一等函数与函数对象让内部 DSL 特别强大，因为可以把计算模式抽成可复用的抽象。音乐语言是内部 DSL。
  • 定义 ADT 本身就是”扩展语言”：新类型 = 新的名词（值），新操作 = 新的动词（操作），而这些名词动词又建立在既有的抽象之上。
  • 语言的威力在于解决一整类问题：从”写 p && q“到”设计 Formula 类型”，从”写一个矩阵乘法函数”到”设计 MatrixExpression 类型”，差别就在于此。

递归数据类型与抽象语法树（Recursive Data Type / Abstract Syntax Tree）

• 定义与目的：用递归数据类型描述语言的语法结构。课程的整数表达式（Reading 19）定义为 IntegerExpression = Number(n:int) + Plus(left:IntegerExpression, right:IntegerExpression)；音乐语言定义为 Music = Note(duration, pitch, instrument) + Rest(duration) + Concat(first, second)。它关系到 Safe from bugs（结构由类型系统静态检查）与 Easy to understand（结构直接对应语法）。
• 直观解释（”它是什么？”）：AST 是”句子的骨架图”：它保留了对语义重要的部分（怎么分组、有哪些数字/音符），而丢掉了无关的书写细节。
• 关键规则与最佳实践：
  • 抽象语法树 vs 具体语法树（concrete syntax tree）：2+2、((2)+(2))、0002+0002 产生三棵不同的具体语法树，却都对应同一个抽象值 Plus(Number(2), Number(2))。解析器的工作就是把前者变成后者。
  • 递归数据类型的每个变体对应文法中的一条产生式，变体名通常取产生式的名字（Because/Plus/Number/Note/Concat）。
  • 「补充说明」：不同教材习惯把变体命名为 PlusExpression、VariableExpression 之类（把类型名后缀带上）；6.031 的做法是直接用产生式的名字，例如 Plus、Concat、Variable，本笔记遵循课程命名。
  • 选择表示时要考虑未来：课程原文特别说明，音乐语言选择树形的 Concat 是”一个优雅的决定”，因为它让后续扩展（变奏、和声、重复）变得自然；真实的设过程可能需要多次迭代才能找到最合适的递归结构。

组合模式（Composite Pattern）

• 定义与目的：让单个对象（primitive，基元）与对象组（composite，组合）属于同一个类型，从而可以被同样对待。Music 正是组合模式：基元是 Note/Rest，组合是 Concat；Formula 的基元是 Variable，组合是 Not/And/Or。它关系到 Easy to understand（统一的递归操作）与 Ready for change（加新组合子不必改客户代码）。
• 直观解释（”它是什么？”）：像文件夹与文件：文件是基元，文件夹是组合，但两者都是”文件系统条目”，都能被”删除”“移动”“计算大小”。组合模式自然产生树：基元在叶子，组合在内部结点。
• 关键规则与最佳实践：
  • 组合变体（Concat、Not、And、Or）在实现操作时递归；基元变体（Note、Rest、Variable）实现基例（base case）。
  • 组合模式在真实系统中的例子：HTML 的 DOM（<img>/<input> 是基元，<div>/<span> 是组合，都实现共同的 Element 接口）；sp21 原文用 Swing 视图树（JLabel/JTextField 是基元，JPanel/JScrollPane 是组合，共同实现 JComponent）。
  • 组合模式让”对整棵树做一件事”变成三行递归代码；反之，若没有统一类型，就必须到处写 instanceof。
  • 组合结构必须是有向无环的（实际上这里是无环树），否则递归操作会无限循环。

表示的选择与”空”的表示（Choosing the Rep; Emptiness）

• 定义与目的：选定操作的规格之后就要选表示。音乐语言的表示由三个变体构成：Note(duration, pitch, instrument)、Rest(duration)、Concat(first, second)。空的概念必须有一个表示：课程明确拒绝使用 null，而选择用时值为 0 的 Rest 表示”空音乐”。它关系到 Safe from bugs（消除 NullPointerException）与 Easy to understand（”没有音乐”与”一段静音”语义一致）。
• 直观解释（”它是什么？”）：rest(0) 就像”长度为零的空白乐段”：它是一段合法的、可以参与拼接的音乐，只是听不见；而 null 是”这里什么都没有，谁碰到谁崩溃”。
• 关键规则与最佳实践：
  • 永远给”空”一个合法的表示，绝不用 null 或 undefined/null 作为哨兵值（与 Reading 9 的”避免 null、快速失败”一致）。
  • 选择 Rest(0) 的额外好处：duration()、play()、concat() 的实现无需任何特例分支，组合模式的一致性得以保持。若引入 Empty 变体，虽然也合法，但每个操作都要多写一个分支。
  • 避免表示依赖（representation dependence）：除了变体类本身，客户端应通过工厂函数 note(...)、rest(...)、concat(...) 构造音乐，而不是直接 new Concat(new Note(...), ...)。
  • 「补充说明」：Concat 的音乐树不是平衡的——notes("C D E") 会生成左深树 Concat(Concat(Rest(0), Note(C)), Note(D)) 之类；因此要留意递归深度与栈开销，必要时可以引入更聪明的构造策略。

为递归类型定义操作：解释器模式（Interpreter Pattern）

• 定义与目的：自课程引入递归数据类型以来，我们一直用解释器模式为这类类型实现函数：（1）在定义数据类型的接口中把操作声明为实例方法；（2）在每个具体变体类中实现它。它关系到 Easy to understand（每个变体的代码都在一起）与 Safe from bugs（静态检查保证每个变体都实现了操作）。
• 直观解释（”它是什么？”）：像给每个员工一句本岗位的作业指导书：Note 知道怎么算自己的时值、怎么被播放；Concat 知道怎么把两段合起来。客户端只说”给我你的时值”，具体由对象自己回答。
• 关键规则与最佳实践：
  • 动态分派（dynamic dispatch）是解释器模式的动力：m.duration() 执行哪个方法体，由 m 指向的对象实际类型（actual type / dynamic type）决定，而不是由变量声明的类型决定。
  • 声明类型与实际类型的区别要牢记：Java 中”声明类型（declared type）”来自声明，编译期可知；”实际类型”是对象构造时所用的类。实际类型必须是声明类型的子类型，这保证了”声明类型上能调用的方法，实际类型一定也有（规格相同或更强）”。
  • 接口没有构造器，因此实际类型永远是类；当声明类型是接口时，二者必然不同。
  • 组合变体递归实现，基元变体实现基例；递归调用写在变体自己的方法体里，因此编译器能检查每个变体都实现了新操作。
  • 由此产生的代价（本讲先埋下伏笔，Reading 27 展开）：操作代码分散在所有变体类中；新增一个操作必须修改接口与所有变体类。

操作放在哪里：实例方法 vs 独立工厂函数（Instance Methods vs Static Functions）

• 定义与目的：音乐语言的操作被分成两组：duration : Music → double 与 play : Music × SequencePlayer × double → void 作为 Music 接口的实例方法；而 notes : String × Instrument → Music（以及 note/rest/concat）作为 MusicLanguage 类的静态工厂方法。它关系到 Ready for change（把”构造”与”观察/变更”分开）与 Easy to understand（客户知道去哪里找什么）。
• 直观解释（”它是什么？”）：实例方法是”这段音乐自己会做的事”（多久、怎么放）；静态工厂是”造音乐的工具箱”（从文本造、从音符造、从两段拼）。
• 关键规则与最佳实践：
  • notes 可以放在 Music 里，课程选择放在单独的 MusicLanguage，为的是让所有”操作 Music 的函数”集中在一处，等这门语言长大后更好找。
  • 工厂函数（note/rest/concat）的价值是避免表示依赖：客户端不必知道 Note/Rest/Concat 的存在，将来换表示也不会牵动客户端代码（与 Reading 10/11 的抽象函数思想一致）。
  • concat 是音乐语言的第一个 producer 操作（返回新 Music 而不改变参数），它使语言具备组合能力：少量原语 + 组合子 = 表达能力。
  • 判断方法该放哪里的经验：需要访问私有表示的观察/变更操作放实例方法；纯粹构造值的工厂放静态工具类（「补充说明」：也可以用 Java 8 的静态接口方法，但课程采用了独立类）。
  • 变体的构造函数、checkRep、toString、equals/hashCode 仍需在各变体类中仔细实现（与 Reading 15 相等性一致）。

求值器与求值环境（Evaluator and the Environment）

• 定义与目的：对”把代码当数据”的类型，最典型的操作是求值（evaluate）。课程的规格是 evaluate : Formula × Map<String,Boolean> → boolean，前置条件是”公式里出现的所有变量都必须是 map 的键”，效果是”用 map 中的值替换变量后求值”。它关系到 Safe from bugs（前置条件明确、未绑定变量显式失败）与 Ready for change（同一个表达式可以用不同环境反复求值）。
• 直观解释（”它是什么？”）：环境（environment）就是”变量名 → 值”的字典，相当于把公式里的字母填上具体真值/数值；同一个公式换一本字典，就能得到不同结果——这正是”表达式是数据”的直接红利。
• 关键规则与最佳实践：
  • 环境必须作为参数传递（或作为不可变字段由构造函数注入），绝不能做成全局可变状态：否则同一表达式在不同线程、不同时刻求值结果不同，且无法并发使用。
  • 未绑定变量是前置条件违反，应当显式失败并给出可读信息（例如抛 IllegalArgumentException("unbound variable: x")）；注意 Map<String,Integer> 取值后自动拆箱会在 null 时抛 NullPointerException，信息量很差。
  • 求值器通常是纯函数：给定表达式与环境，结果唯一确定，且不修改环境——这让它可以被任意缓存、并行与测试。
  • 「补充说明」：把 Variable 变体加入 IntegerExpression 是为了演示 eval(environment) 这一常见写法（教材中常称 eval）；课程原文的整数表达式文法（Reading 19）只有 Number 与 Plus，变量与环境的例子出现在 Formula 的 evaluate 上。
  • 求值可以递归地进行：Plus.eval(env) 先递归求左右子表达式，再相加——组合模式的又一处体现。

把解析器与解释器串起来（Parser → AST → Interpreter）

• 定义与目的：语言要能被”写下来”，就需要文本记号（notation）与解析器（parser）。音乐语言选用简化版 abc 记号（文本音乐格式）：C D E F G A B C' B A G F E D C 是一个八度上下行的 C 大调音阶（C 是中央 C，C' 是高一个八度的 C，每个音是四分音符）；C/2 D/2 _E/2 F/2 G/2 _A/2 _B/2 C'/2 是升序 c 小调音阶、速度快一倍（E、A、B 为降号，每个音是八分音符）。它关系到 Easy to understand（文本可读、可 diff）与 Safe from bugs（解析器可测试）。
• 直观解释（”它是什么？”）：解析器是”翻译官”：把人类写的字符序列翻译成 AST；解释器/播放器是”演奏者”：让 AST 变成声音或结果。链路是 文本 → 具体语法树 / 词法切分 → 抽象语法树 → 求值/播放。
• 关键规则与最佳实践：
  • notes(String abc, Instrument instrument) 的实现策略：先把输入切成一个个符号（如 A,,/2、.1/2），从空音乐 rest(0) 开始，逐个解析符号并用 concat 累积。
  • parseSymbol(String, Instrument) 只负责解析类型（休止符或音符）与时值，把音高（字母、升降号、八度）交给 parsePitch。
  • parsePitch(String) 是递归的：基例是”单个字母（可带升降号）”；递归例是”末尾的 '/, 表示升降八度”，以及”开头的 ^/_ 表示升/降半音”。要能答出原文练习里的问题：C、_C 走基例，而 C'、C/2 不是基例处理的内容。
  • 解析器的结构应当跟随文法结构（与 Reading 19 的 makeAbstractSyntaxTree 完全同构：SUM 逐个 Plus 累积、NUMBER 用 parseInt 造基元）。
  • 解析失败要快速失败并给出可读错误（throw new IllegalArgumentException("bad abc symbol: ...")），不要返回半成品。
  • 课程原文的判断值得记住：写音乐用简化 abc 记号，比”一页又一页的 addNote“更易理解、更少 bug、更易修改——这就是小语言的价值。

播放器设计：为什么 play 要带 atBeat（Scheduling Instead of Waiting）

• 定义与目的：play : Music × SequencePlayer × double → void 的规格是”在给定的拍延迟之后，用给定播放器播放这段音乐”。为什么不”现在就播”？因为要播放由 Concat 组合起来的音符序列，就必须有时间轴；而播放器的 addNote 本来就设计成可以调度未来时刻的音符（它自己处理延迟）。它关系到 Safe from bugs（不依赖 sleep 的时序猜测）与 Easy to understand（每段音乐只关心”我从第几拍开始”）。
• 直观解释（”它是什么？”）：像给乐队写总谱：每个乐手被告知”你从第 16 拍开始演奏你的声部”，而不是让指挥拿着秒表逐个喊”现在轮到你”，更不是让人原地睡觉等轮到自己。
• 关键规则与最佳实践：
  • Note.play(player, atBeat) 调用 player.addNote(instrument, pitch, atBeat, duration)——把音符、开始时刻、时长交给调度器。
  • Rest.play(player, atBeat) 什么都不做：静音只贡献时长。
  • Concat.play(player, atBeat) 先播第一段（first.play(player, atBeat)），再让第二段从第一段结束处开始：second.play(player, atBeat + first.duration())。这就是为什么必须有 atBeat：只有 Concat 知道该给子音乐传什么起始时刻。
  • 不要在 play 里 sleep：那会阻塞调用线程（在 GUI 事件线程或网络服务器线程里是灾难），而且时序精度依赖操作系统调度；调度器已经替你完成延迟。
  • 把”具体播放器”（MidiSequencePlayer）与”音乐”解耦：Music 只依赖 SequencePlayer 接口，因此可以用假播放器做测试；课程用 MusicPlayer 这个工具类把两者接起来。

小语言的设计原则：简单、可组合、可扩展（Simple, Composable, Extensible）

• 定义与目的：一个好的小语言应当只有少量原语、由组合子拼出无限表达，并且能在不破坏已有代码的前提下扩展。它关系到三大目标的全部。
• 直观解释（”它是什么？”）：像乐高：只有几种基本块（原语），但靠”拼接”这一个组合子（Concat）就能搭出任何东西；要加”变速”功能时，加一个新块而不是重做所有块。
• 关键规则与最佳实践：
  • 选择少量、正交的原语：Note、Rest，加一个组合子 Concat 就够了。
  • 组合子要能任意嵌套（Concat 接受任意 Music，包括 Concat 自身），这是递归类型带来的表达力。
  • 让操作可扩展：把操作声明在接口上（解释器模式）；如果预期客户端要加很多新操作，则考虑 Reading 27 的访问者模式（Visitor pattern）。
  • 用文本记号 + 解析器替代手写构造代码，让”写音乐”这件事本身变得安全、可读、可改。
  • 注意 Music 的操作是尽量纯的：duration() 是观察者；play 有副作用（向播放器调度音符）；工厂是生产者/创造者——分清这些类别（Reading 6/7）有助于写出好规格。

代码示例与对比分析

场景 1：手写一长串 addNote vs 用简化 abc 记号构造音乐

❌ 错误代码

// 错误：把音乐"硬编码"成几十次 addNote，时刻全靠手算
SequencePlayer player = new MidiSequencePlayer();
Instrument instrument = PIANO;

// Row, row, row your boat 的前几个音（C C C D E ...）
player.addNote(instrument, new Pitch('C'), 0.0, 1.0);
player.addNote(instrument, new Pitch('C'), 1.0, 1.0);
player.addNote(instrument, new Pitch('C'), 2.0, 1.0);
player.addNote(instrument, new Pitch('D'), 3.0, 1.0);
player.addNote(instrument, new Pitch('E'), 4.0, 2.0);
player.addNote(instrument, new Pitch('E'), 6.0, 1.0);
player.addNote(instrument, new Pitch('D'), 7.0, 1.0);
player.addNote(instrument, new Pitch('E'), 8.0, 1.0);
player.addNote(instrument, new Pitch('F'), 9.0, 1.0);
player.addNote(instrument, new Pitch('G'), 10.0, 4.0);
// … 还有 20 多个音符，每个都要手算起始拍；改一个音的位置就要重算后面所有时刻
player.play();

【错误代码的问题】

1. 时序靠手工累加：任何一个音符的时值改动，后面所有音符的 atBeat 都要重算，改一处错一片（典型的”重复代码 + 手工一致”缺陷）。
2. 不可读：从上到下看不出旋律，代码与音乐之间没有直观对应，违反 Easy to understand；也无法与其他音乐师交流。
3. 不可复用：想把这段旋律移调、或在前面加一段前奏，必须重写所有行；没有任何”结构化”的操作空间。
4. 不可测试：没有中间产物（AST）可供断言，只能听声音判断对错。

✅ 正确代码

// 正确：用简化 abc 记号写成"程序"，解析成 Music（AST），再让 Music 自己播放
Music tune = notes("C C C D E E D E F G", PIANO);   // 文本可读、可 diff
double beats = tune.duration();                      // 观察者：总时长
tune.play(new MidiSequencePlayer(), 0.0);            // 从第 0 拍开始调度

// MusicLanguage 的核心实现（节选）
public final class MusicLanguage {
    private MusicLanguage() { }   // 工具类，不可实例化

    /** @param abc 简化 abc 记号写成的音乐字符串
     *  @param instrument 演奏这段音乐的乐器
     *  @return 与 abc 对应的 Music */
    public static Music notes(String abc, Instrument instrument) {
        Music music = rest(0);                        // 空音乐：时值为 0 的休止符
        for (String symbol : abc.trim().split("\\s+")) {
            if (symbol.equals("|")) continue;         // 小节线只是排版分隔符
            music = concat(music, parseSymbol(symbol, instrument));
        }
        return music;
    }

    public static Music note(double duration, Pitch pitch, Instrument instrument) {
        return new Note(duration, pitch, instrument);
    }

    public static Music rest(double duration) {
        return new Rest(duration);
    }

    public static Music concat(Music first, Music second) {
        return new Concat(first, second);
    }
    // parseSymbol / parsePitch 见场景 4
}

【为什么这样更好】 音乐变成数据：notes(...) 把文本一次解析成 AST，之后可以随时 duration()、play()、或把它们 concat 起来。时值只在文本里写一次，时刻由 Concat.play 递归计算，不再手工累加；想移调或加前奏，只需重新组合 AST。 【代码对比解说】 左侧代码是”解决方案的程序”，右侧是”解决问题的语言”。这一转变带来三点结构变化：（1）出现一个中间表示（Music 树），使计算与数据分离；（2）出现工厂函数把构造集中起来，客户端不依赖具体变体类；（3）出现解释器（duration/play）把”对 AST 求值”的实现按变体分散，使扩展变体成为局部修改。注意 MusicLanguage 的构造器是私有的：它只是静态方法的容器（「补充说明」：也可以用 final class + 私有构造或 Java 接口静态方法表达）。 【设计原则透视】 这是 Reading 10/11 的 ADT 设计（表示 + 操作 + 抽象边界）在”语言”尺度上的应用，也是 Reading 19 中”文法 → 解析器 → AST”链路的延续：notes 相当于针对音乐领域的 makeAbstractSyntaxTree。语法（abc 记号）与语义（AST）分离，正是”抽象语法 vs 具体语法”的教科书式体现。

场景 2：用 null 表示”空音乐” vs 用 rest(0)

❌ 错误代码

// 错误：用 null 表示"没有音乐"，于是每个操作都要防御性地判空
public static Music concat(Music first, Music second) {
    if (first == null && second == null) return null;        // 特例 1
    if (first == null) return second;                        // 特例 2
    if (second == null) return first;                        // 特例 3
    return new Concat(first, second);
}

public final class Concat implements Music {
    private final Music first, second;
    @Override public double duration() {
        double d1 = (first == null) ? 0 : first.duration();   // 判空散落各处
        double d2 = (second == null) ? 0 : second.duration();
        return d1 + d2;
    }
    @Override public void play(SequencePlayer player, double atBeat) {
        if (first != null) first.play(player, atBeat);
        if (second != null) second.play(player, atBeat + (first == null ? 0 : first.duration()));
    }
}

【错误代码的问题】

1. NullPointerException 潜伏在每一处遗漏的判空上：任何新操作（transpose、reverse）都必须记得重新写一遍判空逻辑，漏一处就是运行时崩溃。
2. 不变量无法表达：Concat 的表示不变量本应是”两段都是合法的 Music“，用 null 后这个 RI 变成”可能为 null”，checkRep 也就无从写起。
3. 表示依赖外泄：客户端会开始写 if (m != null) 这种防御代码，null 成了公开表示的一部分。
4. 语义混淆：”没有音乐”与”一段静音”被强行区分，客户必须理解这两种”空”的差异。

✅ 正确代码

// 正确：空音乐是一个合法的 Music —— 时值为 0 的 Rest
public static Music rest(double duration) {
    return new Rest(duration);
}

// 空音乐：rest(0)；拼接时无需任何特例
public static Music concat(Music first, Music second) {
    return new Concat(first, second);
}

public final class Rest implements Music {
    private final double duration;
    public Rest(double duration) {
        this.duration = duration;
        checkRep();
    }
    private void checkRep() {
        assert duration >= 0 : "rest duration must be non-negative";
    }
    @Override public double duration() { return duration; }
    @Override public void play(SequencePlayer player, double atBeat) {
        // 静音不发出任何声音，只贡献时值
    }
}

public final class Concat implements Music {
    private final Music first, second;
    public Concat(Music first, Music second) {
        if (first == null || second == null) {
            throw new NullPointerException("Concat requires non-null Music");
        }
        this.first = first;
        this.second = second;
    }
    @Override public double duration() { return first.duration() + second.duration(); }
    @Override public void play(SequencePlayer player, double atBeat) {
        first.play(player, atBeat);
        second.play(player, atBeat + first.duration());
    }
}

【为什么这样更好】 表示不变量恢复为”first、second 都是非 null 的 Music“，checkRep 可以真正检查它；duration() 与 play() 的实现不再有特例分支，客户代码也不需要判空。空音乐 rest(0) 在语义上也更干净：它是”零拍的静音”，与”有拍的静音”属于同一概念。 【代码对比解说】 关键差别是”用类型系统消灭非法状态“还是”用运行时判断补救非法状态”。前者让编译器与 RI 帮你守住边界；后者把正确性寄托在”每个代码路径都记得判空”上，而人一定会忘。注意正确版本在构造函数里对 null 快速失败（fail fast）：错误在构造点暴露，而不是在执行 play 五层递归之后才爆炸——这使定位成本从”追调用栈”降到”看栈顶”。 【设计原则透视】 对应 Reading 9（避免调试：用断言与 fail fast，避免 null） 与 Reading 11（表示不变量）：RI 必须能在 checkRep 中表达并被检查；任何让 RI 无法写清的表示（如用 null 当哨兵）都是坏表示。同时这也是组合模式成立的前提：只有当”基元”与”组合”共享同一套良构不变量时，统一递归操作才可能简洁。

场景 3：把求值环境做成全局可变状态 vs 把环境作为参数传递

❌ 错误代码

// 错误：环境是全局可变的静态表，求值器依赖隐藏状态
public interface IntegerExpression {
    /** @return 本表达式的值（从全局环境查变量） */
    int eval();
}

public final class Variable implements IntegerExpression {
    private final String name;
    public Variable(String name) { this.name = name; }

    @Override public int eval() {
        Integer value = GlobalEnvironment.get(name);   // 依赖全局状态
        return value;                                   // 未绑定时自动拆箱抛 NPE，信息极少
    }
}

public final class GlobalEnvironment {
    private static final Map<String, Integer> BINDINGS = new HashMap<>();
    public static void bind(String name, int value) { BINDINGS.put(name, value); }
    public static Integer get(String name) { return BINDINGS.get(name); }
}

// 客户端用法：必须先"设置好世界"，再求值
GlobalEnvironment.bind("x", 3);
GlobalEnvironment.bind("y", 4);
int a = new Plus(new Variable("x"), new Variable("y")).eval();   // 7
GlobalEnvironment.bind("x", 100);
int b = new Plus(new Variable("x"), new Variable("y")).eval();   // 104 —— 同一个表达式，结果变了

【错误代码的问题】

1. 同一表达式在不同时刻求值结果不同：表达式不再是”数据 + 求值规则”，而是”数据 + 隐式世界状态”，违反可理解性与可测试性。
2. 线程不安全：多线程并发 bind/get 一个 HashMap 会导致数据损坏（参见 Reading 21/23）；即使换成并发容器，语义上的”全局共享变量”仍然是设计缺陷。
3. 无法同时用两套环境：想比较”x=3 时”与”x=100 时”的结果，只能串行地反复改全局状态，无法并行、无法重放。
4. 错误信息差：未绑定变量表现为 NullPointerException（自动拆箱），调用者完全不知道是哪个变量没绑定。

✅ 正确代码

// 正确：环境是显式的、不可被求值器修改的输入
public interface IntegerExpression {
    /** @param environment 变量名到值的映射；
     *         前置条件：包含本表达式出现的所有变量名（见 variables()）
     *  @return 本表达式在 environment 下的值 */
    int eval(Map<String, Integer> environment);

    /** @return 本表达式出现的所有变量名 */
    Set<String> variables();
}

public final class Variable implements IntegerExpression {
    private final String name;
    public Variable(String name) {
        if (name == null || name.isEmpty()) {
            throw new IllegalArgumentException("variable name must be non-empty");
        }
        this.name = name;
    }
    public String name() { return name; }

    @Override public int eval(Map<String, Integer> environment) {
        Integer value = environment.get(name);
        if (value == null) {
            throw new IllegalArgumentException("unbound variable: " + name);
        }
        return value;
    }
    @Override public Set<String> variables() { return Set.of(name); }
    @Override public String toString() { return name; }
}

public final class Constant implements IntegerExpression {
    private final int value;
    public Constant(int value) { this.value = value; }
    @Override public int eval(Map<String, Integer> environment) { return value; }
    @Override public Set<String> variables() { return Set.of(); }
    @Override public String toString() { return Integer.toString(value); }
}

public final class Plus implements IntegerExpression {
    private final IntegerExpression left, right;
    public Plus(IntegerExpression left, IntegerExpression right) {
        this.left = left; this.right = right;
    }
    public IntegerExpression left() { return left; }
    public IntegerExpression right() { return right; }

    @Override public int eval(Map<String, Integer> environment) {
        return left.eval(environment) + right.eval(environment);   // 递归、纯函数
    }
    @Override public Set<String> variables() {
        Set<String> result = new HashSet<>(left.variables());
        result.addAll(right.variables());
        return Set.copyOf(result);                                 // 返回不可变集合
    }
    @Override public String toString() { return "(" + left + " + " + right + ")"; }
}

// 客户端用法：环境由调用者拥有，表达式可被反复、并行地求值
IntegerExpression e = new Plus(new Variable("x"), new Variable("y"));
Map<String, Integer> env1 = Map.of("x", 3, "y", 4);
Map<String, Integer> env2 = Map.of("x", 100, "y", 4);
int r1 = e.eval(env1);   // 7
int r2 = e.eval(env2);   // 104 —— 同一个表达式对象，两次求值互不影响

【为什么这样更好】 求值器成为纯函数：给定（表达式，环境）唯一确定结果，不修改任何状态，因此可并发、可缓存、可重放、可单元测试。变量的缺失变成明确的前置条件违反，错误信息带上变量名。variables() 让前置条件”环境必须覆盖所有变量”可以被程序化检查（environment.keySet().containsAll(e.variables())），而不是只写在注释里。 【代码对比解说】 两版的核心差别是”依赖是隐式的还是显式的“。全局环境把依赖藏进静态状态，调用点看起来像一个参数都没有的无参方法 eval()，但真实依赖却无处不在（这叫隐藏耦合）；显式参数则把依赖写在签名里，读者一眼就能看出”求值需要环境”。此外，正确版本还展示了 ADT 设计的两条细节：（1）Map 参数应被当作只读输入，求值器绝不 put；（2）variables() 返回不可变集合，避免把内部表示暴露给客户端改动。 【设计原则透视】 这是 Reading 8（可变性与不可变性）、Reading 21/23（并发与互斥） 与 Reading 6/7（规格） 的交汇：可变静态状态是最糟糕的选择（全局可见 + 线程不安全）；把状态提升为参数，就把”并发问题”从根上取消了。eval 的规格把前置条件显式写出，正符合 Reading 7 中”前置条件越弱越好、但要写清”的原则；而 variables() 则是一种”可检查的前置条件”，让调用者能在运行前自查。

场景 4：手工切割音符字符串 vs 递归的 parsePitch + 结构化解析

❌ 错误代码

// 错误：靠下标与特判"猜"记号结构，只支持一种八度与一种时值写法
private static Pitch parsePitch(String pitchText) {
    char letter = pitchText.charAt(0);          // "_E" 会被当成字母 '_'，直接出错
    if (pitchText.length() > 1 && pitchText.charAt(1) == '\'') {
        return new Pitch(letter).transpose(12); // 只能处理一个上八度，"C''" 就错
    }
    return new Pitch(letter);
}

private static Music parseSymbol(String symbol, Instrument instrument) {
    double duration = 1.0;
    if (symbol.length() > 2 && symbol.charAt(1) == '/') {
        duration = 1.0 / Double.parseDouble(symbol.substring(2));  // "2/4"、"C/2" 等等全乱
    }
    return new Note(duration, parsePitch(symbol.substring(0, 1)), instrument);
}

【错误代码的问题】

1. 混淆了”音高”与”时值”的解析：parseSymbol 用位置下标假设”第 1 个字符是音高、后面是时值”，于是一旦记号变成 _E/2 或 .1/2，切分位置就错了。
2. 递归结构被写死成一层：C''（两个八度）、C,,（低两个八度）都会解析错误，而这些在 abc 记号里完全合法。
3. 失败方式糟糕：越界或 NumberFormatException 让调用者不知道是哪个符号有问题，违反 Easy to understand。
4. 与文法脱节：文法里 pitch ::= accidental? letter octave* 是递归的，代码却写成了非递归的字符扫描，二者结构不一致，将来改文法必然改错代码。

✅ 正确代码

// 正确：解析器结构跟随文法，音高递归处理八度与升降号，时值单独处理
// 文法（本笔记采用的简化版）：
//   symbol     ::= rest | note
//   note       ::= pitch duration?
//   pitch      ::= accidental? letter octave*
//   accidental ::= '^' | '_' | '='
//   octave     ::= '\'' | ','
//   duration   ::= (digit+)? ( '/' digit+ )?

private static final Pattern SYMBOL_PATTERN =
        Pattern.compile("([.^_=A-Ga-g',]*)([0-9]*)(?:/([0-9]+))?");

/** @param symbol 单个 abc 符号，例如 "C"、"_E/2"、".1/2"、"C''"
 *  @return 对应的 Music（Rest 或 Note） */
private static Music parseSymbol(String symbol, Instrument instrument) {
    Matcher m = SYMBOL_PATTERN.matcher(symbol);
    if (!m.matches()) {
        throw new IllegalArgumentException("bad abc symbol: " + symbol);
    }
    String pitchOrRest = m.group(1);       // 音高部分或 "."
    String numerator   = m.group(2);       // 时值分子，可为空
    String denominator = m.group(3);       // 时值分母，可为 null

    double duration = 1.0;                 // 默认四分音符
    if (!numerator.isEmpty()) {
        duration *= Double.parseDouble(numerator);
    }
    if (denominator != null && !denominator.isEmpty()) {
        duration /= Double.parseDouble(denominator);
    }

    if (pitchOrRest.equals(".")) {
        return rest(duration);
    }
    return note(duration, parsePitch(pitchOrRest), instrument);
}

/** @param pitchText 形如 "C"、"_E"、"^F"、"C'"、"C,," 的音高文本（不含时值）
 *  @return 对应的 Pitch */
private static Pitch parsePitch(String pitchText) {
    if (pitchText.isEmpty()) {
        throw new IllegalArgumentException("empty pitch");
    }
    // 基例：只剩一个字母，没有升降号也没有八度记号
    if (pitchText.length() == 1 && Character.isLetter(pitchText.charAt(0))) {
        return new Pitch(pitchText.charAt(0));
    }
    // 递归例 1：末尾 ' 表示升高一个八度
    if (pitchText.endsWith("'")) {
        return parsePitch(pitchText.substring(0, pitchText.length() - 1)).transpose(12);
    }
    // 递归例 2：末尾 , 表示降低一个八度
    if (pitchText.endsWith(",")) {
        return parsePitch(pitchText.substring(0, pitchText.length() - 1)).transpose(-12);
    }
    // 递归例 3：开头的升降号
    switch (pitchText.charAt(0)) {
        case '^': return parsePitch(pitchText.substring(1)).transpose(1);    // 升半音
        case '_': return parsePitch(pitchText.substring(1)).transpose(-1);   // 降半音
        case '=': return parsePitch(pitchText.substring(1));                 // 还原号
        default:
            throw new IllegalArgumentException("bad pitch: " + pitchText);
    }
}

【为什么这样更好】 代码结构与文法结构同构：parseSymbol 负责”类型 + 时值”，parsePitch 用递归同时处理任意多个八度记号与升降号，C''、C,,、^F' 都自然成立。每个失败点都抛出带原文的异常，非法输入立即暴露。时值与音高分离，使将来新增记号（如附点、连音）时改动范围可预测。 【代码对比解说】 左侧代码把”解析”降级成”按下标取字符”，必须为每种写法特判；右侧代码把”解析”还原为”按文法递归下降”，特判只出现在文法真正分支的地方（. 是休止符、末尾是 '/,、开头是升降号）。注意基例与递归例的划分：基例是”单个字母”，递归例每次剥掉一个修饰符再递归，因此必然终止——这与 Reading 14（递归）中”递归必须向基例前进”的规则完全一致。此外，parsePitch 依赖 Pitch.transpose(int) 这一 producer 操作（返回新的 Pitch，不修改原对象），体现了不可变类型在解析器中的好用之处。 【设计原则透视】 这里同时用到 Reading 18（正则与文法）、Reading 19（解析器） 与 Reading 14（递归）：文法既是协议的规格，也是解析器的实现蓝图；parseSymbol/parsePitch 的分层对应”具体语法 → 抽象语法”的转换，与 Reading 19 中 makeAbstractSyntaxTree 按 EXPR/SUM/PRIMARY/NUMBER 逐条规则处理是同一手法。解析器本身也应当被单独规格化：前置条件是”输入符合文法”，后置条件是”返回与输入对应的 AST”，不在前置条件内的输入必须快速失败。

与其他设计原则的关联

• Reading 17（递归数据类型）：本讲的全部数据表示（Formula、Music、IntegerExpression）都是递归数据类型；本讲在它之上加了”语言”的视角——递归类型即 AST，变体即语法产生式。
• Reading 18（正则与文法）与 Reading 19（解析器）：abc 记号、HTTP 请求行、问题集语言都需要文法；notes/parseSymbol/parsePitch 是 Music 领域的 makeAbstractSyntaxTree，把具体语法树转成抽象语法树。外部 DSL（正则、ParserLib 文法、PS3 语言）与本讲的内部 DSL 形成对照。
• Reading 10（抽象数据类型）与 Reading 11（抽象函数与表示不变量）：选择 Music 的表示、写 checkRep、用工厂函数避免表示依赖，都是 ADT 设计的基本功；rest(0) 表示空音乐是”让 RI 可表达”的范例。
• Reading 12（接口、泛型、枚举、函数对象）：Music/SequencePlayer 是接口，Instrument 是枚举，MusicLanguage 是静态工厂集合；函数对象（BiFunction、lambda）让我们能把”计算”也当作值传递，是内部 DSL 的支柱。
• Reading 8（可变性与不可变性）：AST 节点必须是不可变的，才能被安全地共享与多次求值；Pitch.transpose 返回新对象而非修改自身（producer 而非 mutator）。
• Reading 6（规格说明）与 Reading 7（设计规格）：notes、duration、play、eval 都需要前置/后置条件；play 的 atBeat 参数正是为了让规格写清”从哪里开始”，避免把时间耦合进实现。
• Reading 9（避免调试）与 Reading 15（相等性）：解析失败要 fail fast；变体类需要正确实现 equals/hashCode/toString，否则音乐无法比较与调试。
• Reading 3（测试）与 Reading 4（代码评审）：解析器与求值器都是纯函数，最容易测试；Music 只依赖 SequencePlayer 接口，可以用假播放器断言 addNote 的调用序列。
• Reading 27（小语言 II）：本讲用解释器模式实现操作；下一讲指出它的两个缺点（代码分散、加新操作要改所有变体），引入访问者模式作为替代，并讨论表达式问题（expression problem）。
• Problem Set 3（Memely）：该问题集要求实现一门生成图片 meme 的语言（\| 水平拼接、--- 垂直拼接），正是”递归数据类型 + 解析器 + 解释器”的完整练习，与本讲的音乐语言同构。

关键要点

• 先问”能不能做成一门语言”，并把代码当数据：如果任务是一整类相关问题，就构造语言（递归数据类型 + 少量原语 + 组合子）而不是写一次性程序；表达式应当是可以存储、传递、延后求值、重复求值的一等值，这要求 AST 节点不可变。
• 递归类型 + 解释器模式：操作声明在接口、实现在每个变体；组合变体递归、基元变体实现基例；动态分派决定执行哪段代码。
• “空”必须有合法表示：用 rest(0) 而不是 null；让表示不变量可写、可检查，让 checkRep 有用。
• 显式依赖、纯求值：环境/播放器都应作为参数或构造注入，绝不做成全局可变状态；未绑定变量要显式失败。
• 解析器跟随文法，播放交给调度：递归下降解析文本 → AST；play(atBeat) 把时间轴交给播放器调度，绝不在 play 里 sleep。

常见陷阱与注意事项

1. 把 AST 写成可变对象 → 表达式被共享后，某处修改会悄悄影响其他地方（别名 bug）；且无法安全地并发求值。应让所有字段 final 并做防御性复制。
2. 用 null 表示空音乐，或忘记 checkRep → 前者让表示不变量无法表达、到处需要判空、NullPointerException 随机出现（应改用 rest(0) 或专门的空变体）；后者让非法状态（负时值、null 音高）流入系统，错误在很远的地方才暴露。
3. 把求值环境做成全局可变状态 → 同一表达式结果随外部状态变化，线程不安全，无法并行或重放；应作为参数或构造注入的不可变字段。
4. 在 play 里调用 Thread.sleep 或立即逐音播放 → 阻塞调用线程、时序不准、Concat 的两段会同时发声；应通过 atBeat 交给播放器调度。
5. 解析器用下标/特判代替递归 → C''、C,,、_E/2、.1/2 等合法记号解析错误，且改文法必然改错代码；应让代码结构与文法同构，并快速失败。
6. 客户端直接 new Note(...)/new Concat(...) → 表示依赖：换表示就要改客户端。应统一走 note/rest/concat/notes 工厂。

思考题（带答案）

问题 1：为什么 Music 需要 play(SequencePlayer player, double atBeat) 这样的签名，而不写成 play()（现在就开始播）？请结合 Concat 的递归实现说明，并解释为什么这比”在 play 里 Thread.sleep 等一拍”更好。

答案：因为要在时间轴上组合音乐。Concat(first, second) 的语义是”先 first 后 second“，如果 play 都从”现在”开始，两段音乐会被安排在同一个时刻，听起来是同时发声，语义被破坏。加入 atBeat 之后，Concat.play(player, atBeat) 写成 first.play(player, atBeat); second.play(player, atBeat + first.duration());——每个组合变体负责把正确的起始时刻传给子音乐，这就是”为什么必须有这个参数”的根本理由：只有 Concat 知道自己第一段的时长。底层的 SequencePlayer.addNote(instrument, pitch, atBeat, duration) 本来就能把音符调度到未来的某一拍，因此 play 完全不需要等待。相比之下，用 Thread.sleep 模拟”等一拍”有三个致命问题：（1）它阻塞调用线程（若在 GUI 事件线程或网络服务器线程中调用，会冻结界面或拖垮服务器）；（2）时序精度依赖操作系统的调度与计时器，抖动明显；（3）它让”播放”变成一段串行等待的过程，无法整体调度、无法中途取消、也无法用假播放器在测试中断言调用序列。把时间交给调度器，也让 Music 只依赖 SequencePlayer 接口，从而保持可替换性与可测试性。

问题 2：本讲说”把代码表示为数据”是语言设计的关键。请以 Formula（或 IntegerExpression）为例，说明”数据”相比”直接写表达式”多出了哪些能力，并指出这些能力分别对应三大目标中的哪一个。

答案：直接写 p && q 时，表达式在遇到它的那一刻就被求值，结果只剩一个布尔值，表达式本身消失了。改成数据 And(Variable("p"), Variable("q")) 后，额外获得四种能力：（1）存储与传递——AST 可以放进字段、集合、文件、网络消息，也可以跨线程传递，这支持 Ready for change（同一份表达式能被不同模块复用）；（2）延后求值——可以先构造、稍后再 eval(environment)，这在”先收集条件、稍后判断”的场景里必不可少，也支持 Easy to understand（构造与求值是两件清晰的事）；（3）多次求值与不同环境求值——同一个表达式可用不同的 Map 求值任意次，这是”配置化/参数化”的基础，支持 Ready for change 与 Safe from bugs（无需重建表达式，减少出错机会）；（4）分析与变换——可以遍历它、统计变量（variables()）、化简、转成合取范式、打印成字符串，这就是”编译器/优化器”的能力，支持 Ready for change。相反，直接写表达式得到的只是一个结果，无法再做任何结构上的处理。需要强调的是，这些能力的前提是 AST 节点不可变：如果 AST 可以被修改，”同一份表达式”这个概念就不存在了，共享与并发也就无从谈起。

问题 3：为什么课程选择用 Rest(duration: 0) 而不是新增一个 Empty 变体来表示”空音乐”？请从”操作的实现复杂度”“表示不变量”和”未来扩展”三个角度分析，并说明如果一定要用 Empty 变体，代价是什么。

答案：用 rest(0) 的好处有三点。第一，操作实现无需特例：duration() 就是返回 0，play() 什么都不做，Concat 照常递归——Rest 已经把所有需要的行为定义好了；新增 Empty 则要在每个操作里多写一个分支，分支越多越容易漏（Empty.duration() 忘了改、Empty.play() 抛异常等等）。第二，表示不变量保持统一：Rest 的 RI 只是”时值非负”，rest(0) 天然满足；若引入 Empty，就会出现”有的音乐有时值字段、有的没有”的不一致，Concat 也必须额外规定”Empty 不能出现在某个位置”之类的人为约束。第三，将来扩展更自然：一旦语言要支持”变速”“重复”“静音插入”等操作，rest(0) 与其他 Rest 一同处理，语义连续；Empty 则往往需要与 Rest 之间做转换，增加转换代码与出错机会。如果一定要用 Empty，代价是：每个操作多一个分支（解释器模式下分散在所有变体类里）、每个新操作都要记得处理它、客户端可能需要区分”空”与”零时长静音”两种语义上等价的状态，从而失去组合模式的简洁性。课程原文的立场很清楚：”永远应该有一个表示’什么都没有’的值，而我们当然不会用 null 或 undefined“——rest(0) 就是那个既合法又省事的表示。