2. Engineering a compiler. 第3章，语法分析器

简介
- 语法分析的主要目的，是判断输入的单词流(每个单词都被标注成某个语法范畴(syntactic category))，是否是一个语法上有效的语句(sentence)。为了回答这个成员判定问题，我们首先需要一种形式化的方法描述语言。通过将语言限制到上下文无关语言这个集合，我们能够保证高效的回答这个判定问题。
- 语法分析：对于形式文法(formal grammar)G，以及单词流s，词法分析要做的就是找到G生成语句s的一个推导
  - 推导应该无歧义。推导过程的graph描述，就是语法树(concrete syntax tree, parse tree)
  - 语法分析的输入是单词流，输出是推导(或者失败时的诊断信息)。如果不需要完整的推导信息(parse tree)，可以只输出抽象语法树(AST)，或者采用其他语义动作(semantic action)，直接进行解释
- 总结：
  - 对于输入的单词流/字符流(如果没有经过Scanner的话)，语法分析尝试判定它是否是特定语言L(G)的成员。L(G)本身是无限集合，成员判定方法不明，通过将G限制为CFG，得到另一种高效的成员判断方法，即，在CFG中，能否找到唯一的一个推导，生成输入的句子。通过自底向上/自顶向下的parse，语法分析器输出错误，或者输出一个推导作为结果。推导的等价表示是具体语法树，一般不需要这样多的信息，而是输出AST，或者通过语义动作，输出其他属性值，比如表达式parse中，可以直接解释结果并返回。
语法的表示
- RE无法描述程序语言，因为它无法计数，只包含有限的状态
  - RE只是CFG的一个子集，对应产生式：A->a, A->a B
- 我们需要比RE更强大的语言，同时具备高性能的特点。CFL正是传统的解决方案，尤其是的它的子集LR(1)、LL(1)，都能生成高效的识别器。
- 术语(Glossary)
  - Context free grammar(上下文无关文法): 对于语言L，CFG定义了表示L中有效Sentence的集合
    - CFG的定义包括4个元素：T，NT，P，S，分别是终结符、非终结符、产生式、开始符号
  - Sentence(语句): 可以从grammar rules推导出的符号串(string of symbol)
  - Production(产生式): CFG中的每个规则(grammar rule)都称为一个产生式
  - Nonterminal symbol(非终结符): 是语法变量(syntactic variable)，用来进行抽象(abstraction)和表达结构(structure)
    - 正是因为NT的存在，CFG支持递归，进而比RE更强大
  - Terminal symbol(终结符): L(G)中单词的集合，对应Scanner输出的语法范畴(syntactic category)
  - Goal symbol/Start symbol(开始符号):
  - Derivation(推导): 对开始符号，应用一系列重写(rewrite，选择产生式来替换非终结符)，得到语句的过程。
  - Sentential form(句型): 有效推导过程中出现的符号串(string of symbol)
    - 句型对应推导过程中部分完成的Parse tree的下边缘
  - Parse tree/Syntax tree(语法分析树/语法树)：A graph that represents a derivation
  - Leftmost derivation、Rightmost derivation(最左/最右推导): 一种推导，每次都重写最左/右的非终结符
  - Ambiguity(二义性): 如果L(G)中的某个句子有多个最左/最右推导，则说文法G具有二义性
- CFG的层次结构，由大到小
  - 任意CFG：Earley算法可以在O(n^3)的时间内解析
  - LR(1): 从左到右扫描，右推导，允许lookahead一个单词
  - LL(1):
  - RG: 正则文法，和RE等价
自顶向下语法分析(Top-down parsing)
- 使用Topdown-parsing的时候，CFG的很大一个子集可以无需回溯的高效Parse——即Backtrack-free grammar(Predicate grammar)
- Top-down parser需要消除左递归，否则将是死循环
  - 直接左递归(direct left recursion):
    - 通过EBNF的star手法来消除
    - BNF中，实际上是：A->A b | c，改写为A -> c A2; A2->e | b A2
  - 间接左递归(indirect left recursion):
    - 使用消除循环引用的方法，即forward subsituation
    - 图算法：已知二维的有向图，先将每个节点编码成数字，于是，有向边分别指向左和右。我们通过消除指向左边的边，来使得引用总是从i指向i+1或更大，从而避免循环引用。
      1. 当i==0时，消除指向自身的引用，从而有向边总是指向0以上
      2. 对i>1，先从j=0，到j=i-1，替换每个i->j的边，每次都将得到j+1以上的边；因此，当j==i-1的时候，i将只有i以上的边；此时再消除i->i的引用，将只剩下指向右边的边
    - 在左递归文法这里，所谓i->j的边，其实是Ni -> Nj xxx，即，产生式右边的第1个位置的非终结符号，构成一条边。我们要做的就是，反复展开右边的Nj，使得右边的序号增大，直到右边只剩下i以上的非终结符好，最后再利用消除直接左递归的手法，消除i->i的引用。over
      - 这里消除直接左递归引入的新符号，不会形成左递归
- 提取左因子(left factoring)
  - 提取左因子，使得基于预测的高效Parser成为可能
  - 形如，A-> L R1| L R2| C1 | C2，改写成 A-> L N | C1 |C2，N->R1 | R2
- 为了减少回溯，甚至不回溯，给出Backtrack-free grammar(Predicate grammar)的定义(对应的Parser，叫Predicative Parser)
  - 首先是FirstSet: 给定终结符/非终结符，返回它的第1个终结符集合
    - 终结符(包括EOF和Empty)，其FirsetSet是自身
    - 非终结符的FirstSet，通过不动点算法来求
      - 当任意非终结符的FirstSet仍然在变化的时候，继续迭代
      - 非终结符N的FirstSet是其各个产生式右边符号序列的FirstSet的并，即FirstSet(N) = FirstSet(p1.body) | FirstSet(p2.body) | ...
      - 符号序列seq的FirstSet定义为，(FS(s1) - Empty) | (FS(s2) - Empty) | ... FS(sn)，这里，s1 s2 .. sn是seq的一个前缀，sn是第1个FirstSet不包含Empty的符号
  - 然后是FollowSet: 给定非终结符，返回它之后可能出现的终结符
    - 仍然是不同点算法
      - 对产生式p，它的定义是N -> A1 A2 ... An。初始化 tail=FollowSet(N)，从右到左迭代；如果Ai是终结符，则tail=FirstSet(Ai)；如果Ai是非终结符，先FollowSet(Ai) |= tail，然后，如果FirstSet(Ai)包括Empty，则tail |= FirstSet(Ai)，否则tail = FirstSet(Ai)
  - 最后是First+Set: 给定产生式，返回它可能的第1个终结符
    - 如果FirstSet(p.body)包含Empty，则First+Set是FirstSet(p.body) | FollowSet(p.nonTerm)，否则First+Set等于FirstSet(p.body)
  - 所谓Backtrack-free grammar，是指，文法中，对任意非终结符N，它的任意两个产生式，其First+Set不相交
    - 因此，当开始Parse非终结符N时，给定输入终结符T，总是能唯一的确定产生式，从而避免回溯
    - 即使文法不是LL1的，Predicate信息仍然能用来优化Top-down parser的性能；当然，由于需要有回溯逻辑，会比LL1 Parser慢
    - ANTLR实现了LL(k)算法
- 没有算法能保证将任意CFG改写成LL1，但是，一般通过左递归消除、提取左因子，我们能得到LL1，或者接近LL1；前者能得到高效的无回溯Parser，后者的Predicate信息可用于提高回溯Parser的性能
- 常见的Topdown-parsing方案包括
  - 回溯Parser
    - 注意要确保成功，应该支持非确定性Parse，这意味着，parse函数的返回应该是序列
    - Parser combinator
      - 性能取决于library的2次处理
      - 左递归
        
        手工改写直接左递归为EBNF的rep
        
        小心避免间接左递归
      - 回溯
        
        手工提取左因子
        
        尽量写成LL1的，否则开销是指数的
      - 错误处理
        
        当不是LL1的时候，失败回溯可能不容易做(当需要到兄弟节点的子孙去回溯的时候)
    - Top-down parser:
      - 可以递归或通过状态栈来迭代
      - 写成非确定性递归，比如，parse的返回值是Stream[Result]
      - 很容易通过First/Follow算法整合向前看信息，即使文法不是LL1的，也可以减少回溯的分支数，从而提高性能
    - 手工递归下降(hand-code recursive descent parsing)
      - 优点是是可以实施各种优化手段，比如不同的非终结符采用不同的LL(k)向前看
      - 缺点是要为每个编译器编写递归主体
  - LL1 Parser
    - 手工递归下降
      - 先处理文法(或者找源语言已有的LL1文法)：G -> 消除直接、间接左递归 -> 提取左公因子 -> 计算First+Set，最后提供每个产生式的预测符号给编码者
      - 每个非终结符内部都可以进行细节调优
    - Table driven LL1 Parser
      - G -> remove left recursion -> left factoring -> Map[NonTerm, Map[Term, Production]]，最后编写Parser主体(递归/迭代)，根据Predicate table来选择产生式
    - Direct code LL1 Parser
      - 根据Predicate table生成一组递归调用的函数
  - LL(k) Parser
    - ANTLR
自底向上语法分析(Bottom-up parsing)
- 推导，是从开始符号，经历一系列句型，最终得到语句的过程。推导的过程是Top-down的，因此，Bottom-up，就是推导的逆过程，即，从语句开始，经历一系列句型得到开始符号。Top-down过程，每次选择最左的产生式进行rewrite，因此是Leftmost derivation；而Bottom-up过程，由于输入单词流，是从左到右的，每次需要归约当前符号串，所以，相当于reversed rightmost derivation。
- Top-down parser，是从开始符号往下完成Parse tree，任何时候，栈上保存的是部分完成的Parse tree的下边缘；Bottom-up parser，是从单词流往上完成Parse tree，任何时候，栈中保存的是部分完成的Parse tree的上边缘。
- LR(0)乃至LR(k)，识别的上下文无关语言是一样大的，只是接受的文法不同，k越大，接受的文法越多，而k越小，则要求文法编写者以更复杂的方式提供文法。
- 判断一个文法是否是LR的，最简单的办法是构建LR Parser，看是否产生Shift-reduce或者Reduce-reduce冲突。
- 术语
  - Handle(句柄): 由产生式p和位置k一起构成了一个句柄。(A->B, k)，意思是，在LR语法分析器的累积状态k处，进行一次A->B的归约，得到的新的句型(由累积状态作为前缀，还未接受的单词流作为后缀)是有效推导的句型序列的一部分
  - Shift(移入): 把输入单词流中的下一个单词放入累积符号栈中，并更新DFA状态
  - Reduce(归约): 将当前累积符号栈的栈顶符号序列，重写为一个非终结符，并更新DFA状态
  - Reduce-reduce conflict: 下一个单词，导致的归约有多个，不确定应该执行哪个操作。Ambiguity grammar
  - Shift-reduce conflict: 下一个单词，既可以移入，也可以归约。Ambiguity grammar
  - LR0 item(LR0 项): 由产生式，及当前位置构成。当前位置的取值是0~p.body.length
    - 根据位置的情况，项可能分三种：
      1. Possibility: 可能的，pos == 0
      2. Complete: 完成的。可归约，pos == p.body.length
      3. Partially complete: 部分完成的。pos > 0 && pos < p.body.length
  - LR1 item(LR1 项): LR0 item的基础上，加上一个Lookahead符号(终结符)
  - Core LR1 item: 开始符号的所有项，或者非开始符号的位置>0的项
    - 所有非核心项，都可以从核心项closure出来。所谓closure操作，即，如果位置pos后紧接一个非终极符，那么，将它的所有Possibility项加入集合，递归该过程直到不动点
  - set of LR1 items: LR1 item的集合。因为LR parser的状态机，本质上是支持递归的DFA，所以如果把LR1 item看做NFA状态，那么，set of LR1 items就是LR1 item的配置，对应DFA状态
  - Canonical collection of sets of LR1 items: LR1项集的规范簇。看做整个DFA
- LR语法分析器算法
  1. 准备Action表
    - Action表是2维表，第1维输入是状态号，第2维输入是终结符
    - 查表结果有三种
      1. Reduce p: 表示归约产生式p
      2. Shift j: 移入当前符号，并转移到状态j。DFA查询
      3. Accept: 当前输入合法。输入流应该只剩下List(Eof)
  2. 准备Goto表
    - Goto表是2维表，第1维输入是状态号，第2维是非终结符
    - 查表结果是另一个状态号，表示归约的结果。这里也是DFA查询
  3. 算法
    1. 准备状态栈和符号栈，状态栈用于支持递归的DFA句柄查找，符号栈用于根据语义动作(Semantic action)聚合结果，输出CST、AST等
    2. 将初始状态入栈
    3. 查询Action表，Action(stateStack.top, scanner.top)，差别结果：
      - Shift j: 将输入token压入符号栈，将DFA转移的目标状态j压入状态栈，递归
      - Reduce p: 从符号栈弹出p.body个符号并执行语义动作然后压栈；从状态栈弹出p.body个状态，然后查Goto(stateStack.top, p.nonTerm)并压入状态栈，递归
      - Accept: 如果输入只剩下List(Eof)，则语言识别成功，将此时符号栈上的结果输出
  - 本质上，LR算法其实是通过DFA来查找句柄，只不过通过栈引入了递归逻辑；每次归约的时候，从栈上弹出产生式的body，恢复DFA的上一个状态，然后根据归约的NonTerm继续进行DFA查找
    - 之所以可以通过DFA查找句柄，是因为，由句柄的集合构成的语言，是有限的，而有限的语言，总是可以通过DFA描述
- Action、Goto表的构建算法
  - 公共步骤，构建DFA：从开始符号的0位置项集出发，closure过后，遍历所有终结符/非终结符，move(set, symbol)得到各个衍生核心项集。这里的每个核心项集，是一个DFA状态。
  - LR(0): 没有向前看符号。先构建DFA后，可以开始构建Action、Goto表。每个DFA状态之间的NonTerm迁移，添到Goto表中作为一项。Term迁移，作为Action表中的Shift动作。如果一个项集，有Term迁移，同时也有归约项，则构成Shift-reduce conflict，如果有多个归约项，则构成Reduce-reduce conflict。一般处理成，Term边构成Shift，非Term边一律Reduce
    - DFA状态少，容易conflict
    - 每个DFA状态，一旦有多个Reduce项、或者同时有Reduce项和Term边，都conflict。因此接受的文法少
  - SLR: 在LR0的基础上，对于有Reduce项的项集，只以其产生式左边的NonTerm的FollowSet作为向前看符号，因此，允许单一DFA状态有多个Reduce项或同时有Term项，只要FollowSet不想交，都不构成conflict
    - DFA状态少。和LR(0)状态数一样
    - Reduce的FollowSet相交(或者与Term边相交)才构成conflict。因此接收的文法比LR(0)大
  - LALR: 先构建DFA。对于每个项集(DFA状态)中的项(表示为项集号+项)，计算它的自生成向前看符号，以及它和其他项的传播关系，然后用不动点的方式，传播向前看符号。最终DFA中的每个状态的项，都带有一个向前看符号集合，这个集合是FollowSet的子集，因此允许的文法比SLR大
    - 自生成向前看符号和传播关系
      - 对于核心项(p, pos)，以SPECIAL_TERM为向前看符号计算closure并move，如果一个target项，以SPECIAL_TERM为向前看符号，则原始项和target项构成传播关系；否则，产生的lookAhead作为target项的自生成符号，用于将来的传播
    - DFA状态少。和LR(0)状态数一样
    - 通过生成、传播的方式构造每个项的向前看符号集，因为它总是FollowSet的子集，所以conflict更少，接收的文法范围更大(注意LR parse接收的语言都一样)
  - LR(1): 以带Lookahead的开始项，构建DFA。最后Reduce的时候，以自带的Lookahead作为向前看符号
    - DFA状态多，因为Lookahead将区别不同的核心项集。状态多，因此更少的conflict，接收更大的文法；但同时空间开销大，C语言的Parser对应的LALR只需要数百状态，LR1需要数千状态
    - 每个Reduce的Lookahead集合更精确，是LALR传播生成的Term集合子集，所以更少冲突
      - 构造LALR的另外一种方法，是先构造LR(1)，然后合并所有LR0部分相同的LR1项集，向前看符号取并集。这里的合并，不会产生Shift-reduce conflict，但是会产生Reduce-reduce conflict，这也说明LALR接收的文法比LR1小
- Bottom-up parser类型
  - Table driven LR parser: LR Parser的标准算法
  - Direct code LR parser: 根据Action、Goto表生成代码。以代码的方式模拟带递归的DFA
实践中的问题(Practical issues)
- Error recovery
  - 由于ide等工具的需要，编译器应该能一次parse反馈尽量多的错误
  - 一种做法是，通过synchronizing word来同步parser状态
    - LL1 parser：发现错误后(调用中抛出的异常)，忽略一系列输入，直到发现对应当前NonTerm帧的同步单词，然后从当前NonTerm帧返回代表错误的语法树
    - LR1 parser: 发现错误后，忽略输入直到找到同步单词，然后连续弹出状态栈，直到发现某个状态存在Goto[s, NonTerm]，于是压栈Goto项，当做Parse成功(得到是错误语法树)
    - 常用的同步单词是“;”、“}”等
- Unary operator
  - 添加一元运算符要谨慎
- Handing context-sensitive ambiguity
  - 比如，在C语言中，如果不通过[]和()区分数组访问和函数调用的话，那么，由于无法区分Factor中的array-ident ( opt-exp-list )与function-ident ( opt-exp-list )，必然导致歧义
    - 可以在CFG中合并两个产生式，然后在语义分析中通过类型来区分
    - 也可以将类型信息通过符号表反馈给Scanner，然后Scanner对不同类型的ident分别输出array-ident、function-ident等
- Left recursion versus Right recursion
  - Top-down parser只能右递归，没得选(需要的话，必须将直接/间接左递归转换成右递归)
  - 对于Bottom-up的LR parser来说，左递归、右递归都是允许的
    - 左递归的状态栈深度固定，边移入边归约；而右递归对栈的需求是线性的，只有移入所有子节点后，才进行连续的归约
    - 无论左递归还是右递归，显然语义不能破坏，比如结合性
高级主题
- 优化文法(Optimizing a grammar)
  - 如果能改写文法，使得推导的语法树高度减小，那么，对于LL parser来说，意味着更少的递归调用；对LR来说，意味着更少的Reduce(显然Shift次数不会变，恒等于输入流长度)，那么，性能会有所提高
  - 减少语法树层次的一种方法是，将useless production(即其右边只有一个符号的产生式)代入到每个引用中，这将减小最终语法树的层次。但由于产生式代换有可能导致产生式总数目增加，对LR parser来说，意味着更多的状态，所以反而有可能降低性能(对dcache不友好)；而如果是LL parser，可以通过人工调整代码，稍微弥补产生式数量增加带来的开销
- 压缩LR1表
  - 分别压缩Action表和Goto表，使得相同的行/列被合并，在每次查表之前，经过一个状态->行号、符号->列号的映射
  - 在文法上面，合并引用相同的终结符号
  - 将Table driven parser改为Direct code parser，后者将不再处理空的单元格。同时由于避免了循环(label+goto)，通过适当调整代码排布，有可能得到更好的icache亲和性
  - 如果语言足够简单，不容易conflict的话，考虑SLR、LALR，他们的状态数和LR0一样

8. Design Patterns: Elements of Reusable Object-Oriented Software

Creational Patterns(创建型模式)
- Abstract factory(抽象工厂)
  - Intent(意图)：提供一个创建一系列相关或相互依赖的对象的接口，而无需指定它们具体的类
  - Motivation(动机): 考虑LookAndFeel，为保证客户代码可以无缝切换不同的LAF，客户不应该直接使用具体LAF下的窗口组件，而应该通过LAF工厂来创建窗口组件的接口，然后在组件接口集上进行操作
  - Applicability(适用性)
    - 系统要独立于产品的创建、组合和表示时
    - 系统想要在多个产品系列之一做配置时
  - Participants(参与者)
    - AbstractFactory => WidgetFactory
    - ConcreteFactory => WindowsWidgetFactory, MacWidgetFactory
    - AbstractProduct => Button, ScrollBar
    - ConcreteProduct => WindowsButton, WindowsScrollBar
  - Consequences(效果)
    - 分离具体的类：客户只依赖于抽象工厂接口，而不依赖于具体工厂和具体产品
    - 易于切换产品系列。只需传入不同的具体工厂
    - 利于产品的一致。即，任意时刻，只能访问同一个具体工厂创建的产品，不可能出现WindowsDialog+MacButton的组合
    - 难以添加新产品，因为那样需要修改抽象工厂和所有具体工厂
  - Known uses(已知应用)
    - LookAndFeel
    - WindowSystem
    - RDBMS API
      - 比如Python的PEP249规定的DB-API 2.0，符合这组API的模块，如sqlite、mysql等，可以无缝切换，客户代码完全不用修改(唯一的变换是import和connection创建)
      - 微软的OLE DB也是例子
  - Related Patterns(相关模式)
    - Abstract factory通常被实现为工厂方法(Factory method)的集合，但是也可以通过Prototype实现
    - 具体工厂一般是Singleton
- Builder(构建者)
  - Intent: 将一个复杂的创建过程，与创建的结果分离，使得基于同样的创建过程，可以创建不同类型的对象
  - Motivation: 考虑将RTF(Rich text format)转换成其他格式。因为RTF的parse过程很复杂，为每种格式编写转换过程，将非常困难。通过抽象出Builder接口，然后在Parse过程中将相应的事件转发给Builder的方法，从而允许传入代表不同目标格式的具体Builder，复用同一套Parse+Build代码
  - Applicability
    - 创建对象的复杂算法，应该独立于对象的组成、装配方式时
    - 构造过程允许创建不同的表示(具体产品)时
  - Participants
    - Builder => RTFConverter
    - ConcreteBuilder => ASCIIConverter, TeXConverter, TextWidgetConverter
    - Director => RTFParser (或者RTFReader)
    - Product => ASCIIText, TeXText, TextWidget
  - Consequences
    - 允许改变产品
    - 将构造代码和表示代码分离
    - 可以对构造过程进行精细控制(相比构造函数的一步到位，Builder pattern可以一步步来做)
  - Known uses
    - RTFConverter
    - Parser作为Director，ProgramBuilder作为Builder，ASTBuilder、Evaluator作为ConcreteBuilder
    - ClassBuilder: 客户代码去一步步创建类的字段、方法
    - ByteCodeStream: 客户代码去逐步添加指令(操作码+操作数)
  - Related patterns
    - Builder与Abstract factory相比，前者强调的是，一步步去创建一个复杂对象，而后者是强调创建一组关联对象(通常单个创建是一步到位的)
- Factory method(工厂方法)
  - Intent: 定义创建对象的接口，然后由具体实现去决定实例化哪个产品
  - Motivation: 比如，在框架中创建产品，而具体产品可配置(通过配置不同的工厂方法)，客户代码仅依赖于产品接口和工厂方法接口
  - Applicability
    - 不想依赖具体的产品类型时
    - 希望延迟产品的创建到子类时
    - 将产品的创建委托给帮助类，从而将产品类型的选择，局部化到帮助类中(抽象工厂模式是一个例子，其中某个具体工厂就是一个局部化了类型选择的帮助类)
  - Participants
    - Product
    - ConcreteProduct
    - Creator
    - ConcreteCreator
  - Consequences
    - 将具体产品的创建延迟到子类，相当于向子类开放了一个Hook
  - Known uses
    - MVC
  - Related patterns
    - 常被用于Abstract factory、Template methods
- Prototype(原型)
  - Intent: 用原型实例指定创建对象的类型及数据，通过拷贝原型创建新对象
  - Motivation: 常见文档编辑工具提供的模板文档功能，比如Unity中的Prefab
  - Applicability
    - 当类的实例状态只有有限的组合、或常见初始状态只有有限组合时，可以枚举这些组合存储为原型，然后在需要的时候拷贝
  - Participants
    - Prototype
    - ConcretePrototype
      - 事实上，不要求类型不同，只要实例状态不同、代表常见案例即可
    - Client
  - Consequences
    - 具有Abstract factory、Builder模式的优点，客户不依赖于具体原型的类型
    - 允许运行时修改原型列表
    - 允许改变属性值来添加新的原型
      - 相比之下，其他Creational pattern是用于抽象创建的类型，而Prototype是抽象创建的实例的(当然也能抽象创建的类型)，比前者更动态
    - 增加原型数量并不需要增加新的类型
  - Known uses
    - 文档编辑器允许定义文档模板
    - 窗口编辑器允许自定义控件模板
    - 常见的游戏引擎都支持定义游戏对象模板
  - Related pattern
    - Abstract factory、Composite、Decorator都可以从Prototype中受益
- Singleton(单例)
  - Intent: 保证一个对象只有一个实例，并提供全局访问点
  - Motivation: 相比全局变量，Singleton追加了唯一实例的保证
  - Applicability
    - 要求唯一实例
    - 要求唯一实例，且实例的具体类型能够被延迟到子类中决定
  - Participants
    - Singleton
  - Consequences
    - 对唯一实例的受控访问
    - 允许对表示精细化：具体实例可以由子类决定
    - 可以以类似方式，将实例个数控制到K个
  - Known uses
  - Related patterns
    - ConcreteFactory、ConreteBuilder都可以被实现为Singleton
Structural Patterns(结构型模式)
- Adapter(适配器)
  - Intent: 将一个类的接口转换为客户希望的另一个接口，使得原本不兼容的代码可以一同工作
  - Also known as: Wrapper
  - Motivation: 有时，为复用被设计的类不能被复用，仅仅是接口不兼容，所以可以加一层适配器
  - Applicability
    - 相比适配一个具体类，如果改为适配一个接口的话，相当于为目标接口实现了一组具体类
  - Participants
    - Target
    - Client
    - Adaptee: 被适配的接口
    - Adapter: 实现Target接口的Adaptee的Wrapper
  - Consequences
  - Known uses
  - Related patterns
    - Adapter对比Decorator，虽然同为Wrapper，但前者源/目的类型不同，而后者相同，结果是后者可递归组合
    - 对比Proxy，和Decorator类似，Proxy的源/目的类型也相同
- Bridge(桥接)
  - Intent: 将抽象和实现分离，使得它们都可以独立变化(接口变化，和类层次变化都可)
  - Motivation: 抽象和实现通过继承来关联，在某些时候可能太强了，因为，这意味着，抽象和实现接口应该相同，类层次应该相同；但实际上，很有可能抽象中的大部分代码，都是与实现无关的，因此，可以通过增加一个额外层次，通过组合而非继承来关联抽象和实现，于是双方都可以独立变化，抽象中与实现无关的代码，可以放在抽象的接口中，从而复用。简单来说，就是将一个抽象层拆分成两个抽象层
  - Applicability
    - 你需要抽象和实现动态绑定，即允许运行时切换实现部分
    - 需要允许分别扩充抽象和实现的类层次
  - Participants
    - Abstraction: 持有Implementor实例
    - RefinedAbstraction: Abstraction的子类
    - Implementor
    - ConcreteImplementor: Implementor的子类
  - Consequences
  - Known uses
    - WindowSystem: Window(Abstraction), ResizableWindow(RefinedAbstraction), WindowImpl(Implementor), WindowsWindowImpl(ConcreteImplementor), MacWindowImpl(ConcreteImplementor)
    - STL的Stack/Queue接收一个序列类型作为参数，这里的Stack/Queue即是Abstraction，序列类型是Implementor，Vector/List可以作为ConcreteImplementor参数
  - Related patterns
    - Abstract factory可以用来配置一个Bridge
- Composite(组合)
  - Intent: 将对象组合成树形结构，并且单个对象和对象的组合，对用户提供一致的抽象，用户可以不加区分的使用(即Combinator)
  - Motivation: Line、Rectangle、Picture等Graphic对象的组合，仍然是Graphic对象
  - Applicability
    - 想向用户提供组合的能力，并且允许用户统一的使用组合结果
  - Participants
    - Component => Graphic
    - Leaf => Line、Rect、Text
    - Composite => Picture，即包含子Component的Component
    - Client
  - Consequences
    - 组合可以递归，任何用到基本对象的地方都可以使用组合对象，客户代码避免了选择等分支，新增加基本对象也可以无缝接入
  - Known uses
    - GUI
    - AST中的Expr
  - Related patterns
    - Decorator可能被用在Composite中
    - Iterator可以遍历Composite
    - Visitor将分布在Composite的各个子类中的操作局部化(对操作开放，对类型封闭)
- Decorator(装饰)
  - Intent: 动态的给对象添加功能，比派生子类更灵活
  - Also known as: Wrapper
  - Motivation: 动态的给对象添加功能；相比通过派生子类的方式来静态的添加功能，Decorator可以控制类型、顺序
  - Applicability
    - 不影响其他对象的情况下，动态、透明的方式添加职责
    - 某些正交的职责，如果通过子类的方式来组合，将导致组合爆炸
  - Participants
    - Component
    - ConcreteComponent
    - Decorator: 实现Component接口，并持有另一个Component指针
    - ConcreteDecorator: 添加各种职责
  - Consequences
    - 比继承更灵活，甚至可以重复添加同一个特性
  - Known uses
    - Logger(扩展得更厉害一点就成了Combinator了(即Composite))
    - Stream
  - Related patterns
    - vs Adapter: Decorator改变职责但不改变接口；Adapter改变接口但不改变职责
    - vs Composite: Decorator可以看做蜕化的Composite。而且Decorator本身也完全没有对象聚合的意思
    - vs Strategy: Decorator增加职责，但接口不变，提供一致的语义；而Strategy虽然接口不变，但语义变化
- Facade(外观)
  - Indent: 为子系统中的一组接口提供一个高层接口，这个接口更容易使用
  - Motivation: 一个常见的使子系统间通信和依赖最小化的办法，即使用一个外观对象
  - Applicability
    - 各种模式的使用，使得产生各种更小的类，从而更可定制，但对于不需要定制的上层用户，需要一个简单的接口
    - 引入Facade类使得子系统对客户不可见，从而可升级和移植
    - 在层次系统中，为每个层次提供Facade类，简化子系统的依赖关系
  - Participants
    - Facade => Compiler
    - Subsystem classes => Scanner、Parser、AST
  - Consequences
    - 对客户屏蔽了子系统组件类，使得客户依赖的类数量减少，同时接口也更简化
    - 客户也可以绕过Facade类直接访问子系统类，从而得到定制能力
  - Known uses
    - Compiler
    - Webkit
  - Related patterns
    - vs Mediator: 外观类用于沟通客户代码和子系统，子系统并不知道外观类的存在，子系统间的通信不经过外观类；中介者存在于子系统类之间，子系统类可能并不知道另一个类，而是只知道中介者
- Flyweight(享元)
  - Intent: 运用共享技术有效的支持大量细粒度对象
  - Motivation: 有些技术受益于对象化的抽象，但是这种简化实现代价很大，比如文本编辑器中的单个字符如果都支持字体颜色不同的话。通过将状态划分为外部状态和内部状态，并共享内部状态到flyweight池中的flyweight对象中，然后在上下文相关的外部状态被引用时，访问共享的flyweight状态并传入外部状态进行操作
  - Applicability
    - 对象数量大，内存占用多，能够区别内部/外部状态，并且将内部状态共享的话，能够显著减少内存占用，同时内部状态不应该有标识符
  - Participants
    - Flyweight
    - ConcreteFlyweight: 包含内部状态
    - FlyweightFactory: Flyweight pool的角色，让get or create的动作透明化
    - Client: 负责维护外部状态和访问Flyweight pool
  - Consequences
    - 会引入额外的时间开销，因此，仅当共享的内部状态够多时，才有价值。如果外部状态是通过内部状态计算出来的，空间效益最大化
  - Known uses
    - 文档编辑器中，将每个符号作为对象，而将Glyph等信息作为内部状态，只将位置作为外部状态
    - GUI中的Layout，首先它是Strategy的应用，其次，它可以被实现为Flyweight
    - String interning
  - Related patterns
    - 在Composite中，以Flyweight的方式实现叶节点
    - 常用Flyweight实现State、Strategy
- Proxy(代理)
  - Intent: 为其他对象提供一种代理以控制对对象的访问
  - Motivation: LazyValue是一种Proxy的使用
  - Applicability
    - Remote Proxy: 为对象在不同地址空间提供局部代表
    - Virtual Proxy: LazyValue的使用就是Virtual proxy，意在控制对象创建的开销，在访问的时候才执行
    - Protection Proxy: 为对象的访问权限
    - Smart reference: 为指针访问附加操作，如引用计数
  - Participants
    - Subject
    - RealSubject
    - Proxy: 实现了Subject接口
  - Consequences
    - 在引用时附加操作，比如隐藏地址空间不同的事实，按需创建对象，附加内务处理包括Copy-on-write等
  - Known uses
    - 远程代理、延迟加载
  - Related patterns
    - vs Adapter: Proxy的输入输出接口相同，或者输出是输入接口的子集(Protection proxy)；而Adapter的输入输出接口不同
    - vs Decorator: 某些种类的Proxy的确是Decorator，但一般Proxy不支持动态的添加/分离
Behavioral Patterns(行为模式)
- Chain of responsibility(责任链)
  - Intent: 使得多个对象都有机会处理请求，从而避免发送者和接受者的耦合；通过将对象组织成一个链，然后沿链传播请求，直到被处理
  - Motivation: GUI中的消息传递机制
  - Applicability
    - 允许多个接受者
    - 发送者无需显示指定接受者
    - 接受者集合可运行时变更
  - Participants
    - Handler
    - ConcreteHandler
    - Client
  - Consequences
    - 降低耦合
    - 增强了指定职责的灵活性
    - 不保证被接收
  - Known uses
    - GUI的输入事件响应
  - Related patterns
    - 相比链式传播，也可以与Composite合用，从子控件传递到父控件
- Command(命令)
  - Intent: 将行为和参数封装成请求对象，从而允许将请求用于队列、日志，以及支持undo操作
  - Motivation: 将菜单的响应封装成一个个Command对象，在点击菜单的时候执行命令
  - Applicability
    - 需要Callback、Closure的场合，老的OO语言可以用Command模式
    - Command对象与请求对象的生命期可以不同，甚至地址空间也可以不同，可以被序列化
    - 允许Command在Do的时候备份状态，那么，就能实现Undo
    - 可以用来做修改日志，从而实现Durability
  - Participants
    - Command
    - ConcreteCommand
    - Client
    - Inoker: 请求发起者
    - Receiver: ConcreteCommand用来实现动作的对象
  - Consequences
    - 调用者不再需要知道响应的具体实现
    - 可以将多个Command利用Composite组合起来，从而实现MacroCommand等超级命令
    - 增加Command无需改变任何已有类
  - Known uses
    - 支持Do/Undo的Command
  - Related patterns
    - 和Composite一起实现宏命令
    - 和Memento一起实现可撤销命令
- Interpreter(解释器)
  - Intent: 对给定语言的表示，解释执行
  - Motivation: 如果一个特定类型的问题发生频率够高，就应该考虑定制一款DSL，然后通过解释器来执行。典型的例子是正则表达式
  - Applicability
    - DSL
    - 抽象解释(Abstract interpretation)
  - Participants
    - AbstractExpression
    - TerminalExpression: 叶子节点
    - NonterminalExpressin: 中间节点
    - Context
    - Client
  - Consequences
    - 易于改变和扩展。一般还和Parser搭配
    - 易于实现。相比编译器来说..
    - 语义动作可以多种多样，不一定是求值，也可以是序列化等。如果语义动作的多样性是主题，考虑Visitor或Builder
  - Known uses
    - 解释器、编译器
  - Related patterns
    - Composite模式用来描述要被解释的对象
    - Flyweight表示叶子节点
    - Iterator可以线性的遍历树
    - Visitor可以将语法树中的行为局部化
- Iterator(迭代器)
  - Intent: 提供一个方法顺序的访问聚合对象的各个元素，而又不暴露对象的具体表示
  - Also known as: Cursor
  - Motivation: 容器遍历
  - Applicability
    - 不想暴露聚合的表示，同时提供遍历的能力。另一种方法是内部迭代器(Internal iterator，即接收lambda的foreach)
    - 支持多次遍历
    - 为不同结构提供抽象迭代器。比如Set<Int>、Vector<Int>都返回Iterator<Int>
  - Participants
    - Iterator
    - ConcreteIterator
    - Aggregate
    - ConcreteAggregate: 具体的容器
  - Consequences
    - 通过不同的ConcreteIterator，实现对同一个ConcreteAggregate的不同算法的遍历
    - 遍历的中间状态保存在Iterator中，从而允许同时多趟遍历
  - Known uses
    - 各种容器库
  - Related patterns
    - Iterator常被用在Composite对象上
    - 通过Factory method来创建具体的迭代器子类
- Mediator(中介者)
  - Intent: 通过中介者来封装对象的交互，减少对象间的直接引用，从而降低耦合
  - Motivation: OO倾向于分割大量的类从而提高复用性，但是，一个类知道的类越多，它的可复用性就越低。于是可以通过中介者来隔离
  - Applicability
    - 一组对象定义良好，但是通信方式复杂，产生的依赖关系混乱难以管理
    - 一个对象引用其他对象并直接与他们通信，导致难以复用该对象
  - Participants
    - Mediator
    - ConcreteMediator
    - Colleague class
  - Consequences
    - 使得各个Colleague解耦
    - 简化了对象间的协议
    - 控制集中化
  - Known uses
  - Related patterns
    - vs Facade: Facade和其抽象的子系统组件间，是单向的关系，子系统组件不知道Facade存在；而Mediator是双向的
    - Colleague可以通过Observer与Mediator通信
- Memento(备忘录)
  - Intent: 在不破坏封装的前提下，捕获对象的内部状态，然后在将来的某个时刻恢复状态
  - Motivation: 允许提取状态，用于取消操作或错误恢复(如果不提供专门的接口的话，Clone、Serialize/Deserailize都能做到...)
  - Applicability
    - 提取的状态应该只是抽象的，不暴露内部表示
  - Participants
    - Memento: 存储对象的内部状态
    - Originator: 允许GetMemento返回内部状态的抽象，以及SetMemento应用状态抽象
    - Caretaker: Originator返回的Memento的保管者
  - Consequences
    - 没有破坏封装
    - 可能代价高昂
  - Known uses
  - Related patterns
    - Command用Memento实现Undo
    - 支持Memento的迭代器可以多路迭代
- Observer(观察者)
  - Intent: 定义一种一对多的关系，当一个对象改变的时候，所有依赖它的对象都得到通知
  - Also known as: Dependents、Publish/Subscribe
  - Motivation: 将类拆分细化的一个副作用是，要维护对象间的一致性更困难，而我们又不希望让对象紧耦合，所以Observer是个好办法
  - Applicability
    - 存在依赖关系的多个对象，希望他们能独立的变化和复用
    - 当一个对象要通知它自身的变化，但不知道有多少个关注者
  - Participants
    - Subject: 被观察方
    - ConcreteSubject
    - Observer
    - ConcreteObserver
  - Consequences
    - Subject和Observer间的低耦合
    - 支持广播
  - Known uses
    - MVC
  - Related patterns
- State(状态)
  - Intent: 允许状态改变的同时，修改自身行为，看起来像是改变了类
  - Motivation: TCPConnection对象的状态维护
  - Applicability
    - 允许运行时根据状态改变行为
    - 状态机。状态机的一种实现，是通过if/switch，基于当前状态然后进行内层translate；State pattern，是将不同的状态枚举，拆分成不同的子类，然后translate动作在子类内部分派，从而允许状态的扩展、降低耦合
  - Participants
    - Context: 状态持有者，将事件委托给State，可能同时会把自身的引用传给State
    - State: 处理事件的抽象接口
    - ConcreteState
  - Consequences
    - 将特定状态的行为局部化
    - 突出状态的切换：状态切换是Context中唯一的State赋值
    - 由于State在Context中被表示成单一变量，也避免了同时维护多变量可能出现的状态不一致问题
  - Known uses
    - 网络协议、游戏等各种状态机
  - Related patterns
    - 如果具体状态无数据字段，那么可以通过Flyweight或者Singleton共享
- Strategy(策略)
  - Intent: 封装算法，使得算法可以独立于客户变化
  - Also known as: Policy
  - Motivation: 提供不同的算法供运行时选择
  - Applicability
    - 需要不同的算法在空间/时间中权衡，而尽量不影响客户代码
    - 一个类定义了多种行为，通过if/else来区别，可以尝试替换成Strategy
  - Participants
    - Strategy
    - ConcreteStrategy
    - Context: 将客户请求转发给Strategy，同时可能需要将自身的引用传入
  - Consequences
    - 可以将不同算法的公共部分，提取到Strategy的较低层次，从而复用
    - 相比通过在Template的子类中重写算法，Strategy很像是一个Bridge
    - 允许运行时算法的选择
  - Known uses
    - Compiler中，用Strategy定义Register allocation、Instructin scheduling方案
    - GUI中不同的Layout算法
    - 不同的电路布局算法
  - Related patterns
    - Flyweight、Singleton可以用于实现没有实例字段的Strategy
    - vs State: State强调自动的状态迁移(由输入驱动)，而Strategy一般是主动的算法选择
- Template method(模板方法)
  - Intent: 定义一个算法的主要框架，将其中一些决策延迟到子类中，从而允许不动骨架就重写特定步骤
  - Motivation: 各种框架
  - Applicability
    - 一次性实现算法不变的部分，而将可变的行为留给子类
    - 提取子类中公共的部分到父类
  - Participants
    - AbstractClass
    - ConcreteClass
  - Consequences
    - 是一种代码复用技术，在类库中尤其重要
    - 是一种Inverse of control，又叫好莱坞法则“别找我们，我们找你”
    - Hook operations
  - Known uses
    - 任何一个抽象类都是为了使用Template pattern才定义的
  - Related patterns
    - Factory method常出现在Template中
    - vs Strategy: Template使用继承来改变定制算法的一部分，而Strategy通过委托来改变整个算法
- Visitor(访问者)
  - Intent: 表示作用于某对象结构中各元素的操作，使得无需修改元素即可扩展新操作
  - Motivation: 编译器中对AST执行GenerateCode、PrettyPrint、TypeCheck等操作，以及可以扩展任意多个新操作而无需修改AST子类
  - Applicability
    - 对象结构中有各种类型，你想针对不同的子类派发专门的操作
    - 需要对类型执行各种不相关操作，你不想让这些操作污染类型
    - 对象结构的元素子类很少变，但是却经常定义新操作。如果元素类型经常变化，还是直接在类型中定义操作更好
  - Participants
    - Visitor
    - ConcreteVisitor: 定义具体的操作
    - Element
    - ConcreteElement
  - Consequences
    - 易于扩展新操作
    - 针对每个类型的操作被局部化
    - 添加新的ConcreteElement很困难，需要修改所有的ConcreteVisitor
    - 可以在Visitor中累积状态，而不像Pattern matching需要在递归参数中累积状态
    - 会破坏ConcreteElement的封装
  - Known uses
    - 编译器：AST、ASTVisitor
    - 游戏：ScheneNode、ScheneNodeVisitor
  - Related patterns
    - Visitor一般用来对Composite对象进行操作
    - Visitor也可以代替Interpter用于解释执行
总结
- Creational patterns
  - Abstract factory
    - 目的：将产品系列的创建抽象出来，提供切换整个系列而不改变客户代码的能力
    - 例子：IQueryResult result = Modules["Sqlite"]["Connection"].New().CreateQuery("select * from db"), IQueryResult result = Modules["Mysql"]["Connection"].New().CreateQuery("select * from db")
    - 场合：框架或库
  - Builder
    - 目的：对于复杂的创建过程，抽象创建器，从而复用同一份创建代码，生成不同的产品
    - 例子：new JsonBuilder().BeginArray().Value(1).Value(2).EndArray().Result()、new BisonBuilder().BeginArray().Value(1).Value(2).EndArray().Result()
    - 场合：一个类的创建过程很复杂，如树/图的构建，或参数很多如GUI控件
  - Factory method
    - 目的：提供动态类型创建能力
    - 例子：ISet set = Module.GetType("HashSet").New()、ISet set = Module.GetType("OrderedSet").New()
  - Prototype
    - 目的：通过状态(而非代码)来区分不同的模板。如果行为的不同，必须通过代码来区别，这往往意味着不同的类型；而如果仅由不同的数据状态，就能驱动行为，那仅需要相同类型的不同实例即可；前者是First class type，后者是Prototype
    - 例子：Human h = CharacterTemplates["Soldier"].Clone()、Human h = CharacterTemplates["Doctor"].Clone()
    - 场合：First class type的动态性仍不足以满足需要时，Prototype列表可运行时修改这一特性，可能正好满足需求；游戏引擎、Word/PPT中常见
  - Singleton
    - 目的: 唯一实例
    - 例子：Application.onExit = ()=>{println("Application exit");}
    - 场合：逻辑上应该避免多实例的情况，比如只有一个StringPool做intern
- Structural patterns
  - Adapter
    - 目的：适配接口(又叫Wrapper)
    - 例子：new InputStream(libc.stdin)
  - Bridge
    - 目的：在抽象和实现之间，引入一个新的抽象-实现层，通过将原本的实现中大量重复代码，提取成implemention-independent代码，作为抽象中的代码复用。即，原来是A1 - I2，现在是A1 - I1, A2- I2，代码提取过后，两个类层次和接口都可以分别变化，典型的例子是，层次1大而深，但接口都很简单，而层次2小，接口比较复杂。
    - 例子：Window::DrawRect() { windowImpl->DrawLine(); ... windowImpl->DrawLine(); }, ResizeableWindow::Draw() { super.DrawRect(); }, WindowImpl::DrawLine() {}, MacWindowImpl::DrawLine() {}
    - 场合：实现代码中，如果不依赖具体实现的代码很多，那么可以将它们抽象出来，使得他们只依赖实现的抽象，这样的通过组合进行的层次刨分，更大程度的复用了代码
  - Composite
    - 目的：提供可组合语义，其实就是Combinator
    - 例子：Expr = Add(Const(1), Variable("x"))
    - 场合：概念本身递归、可组合；做DSL
  - Decorator
    - 目的：蜕化版的Composite，透明、动态的添加职责
    - 例子：new ZipInputStream(new FileStream("1.zip"))
    - 场合：可能有多个正交的概念需要组合，同时组合的顺序、次数也不限，此时用继承会导致类型爆炸
  - Facade
    - 目的：打包一组类对外提供简单的接口，在子系统类和客户代码之间，起到解耦和简化API的作用
    - 例子：lua的那组c api
    - 场合：提供简化的接口，或者出于减小层次子系统间依赖的考虑
  - Flyweight
    - 目的：大量对象时共享状态从而节省空间。注意要求能区分内部/外部状态
    - 例子：String interning，树的叶节点
    - 场合：空间压力大，重复数据多
  - Proxy
    - 目的：在引用对象的时候附加额外操作
    - 例子：远程代理、延迟加载(LazyValue)
    - 场合：需要控制对象访问时
- Behavioral Patterns
  - Chain of responsibility
    - 目的：降低事件触发方和处理方的耦合，同时允许多个处理者以任何方式组合
    - 例子：UIElement->OnKeyDown(keyEvent)
    - 场合：需要接收方可定制、多播的时候
  - Command
    - 目的：封装行为和参数，使得请求方无需依赖具体的响应方
    - 例子: Commands["Copy"]()
    - 场合：各种需要Callback、Closure的地方。同时也很容易支持Undo操作
  - Interpreter
    - 目的：对于重复出现问题，定制DSL，然后解释语义
    - 例子：正则表达式
    - 场合：解释器、抽象解释
  - Iterator
    - 目的：在不暴露聚合的内部表示的情况下，提供统一的遍历接口
    - 例子：各种容器
    - 场合：概念本身就是Iterable<T>的
  - Medaitor
    - 目的：简化子系统中类的依赖关系，减少类的依赖项，从而提高可复用度
    - 场合：类的依赖关系过于复杂的时候
  - Memento
    - 目的：允许剥离和应用状态，从而支持回滚
    - 例子：Clone、Serialize、Copy assignment，都相当于实现了Memento语义，只是粒度较大
    - 场合：想要支持回滚的时候
  - Observer
    - 目的：以松耦合的方式，保持对象间的状态一致性，同时允许多播
    - 例子：Delegate等发布/订阅系统
  - State
    - 目的：将状态机的状态枚举，拆分成独立的子类，从而使得可扩展，且避免出现状态不一致的问题(因为在Context中只有单一State变量，状态切换必然表现为变量赋值)
    - 例子：各种状态机
    - 场合：简单的两层if/switch分派已经过度复杂，且状态一致性难以保证的时候
  - Strategy
    - 目的：将各种可选的算法封装抽象，从而允许做不同的权衡
    - 例子：STL容器的Hash、Equal算法
    - 场合：多个方案各有利弊的时候
  - Template method
    - 目的：基类构造算法的主题，子类定制算法的某个部分
    - 例子：任何abstract class的声明，都是为了以继承的方式复用代码
    - 场合：通过继承复用代码
  - Visitor
    - 目的：能够对一组Composite对象施加操作，而不需要修改Element子类。对操作开放，对类型封闭
    - 例子：各种Composite访问器
    - 场合：Element子类很少变化，而操作可能任意追加的时候；典型的情况是语言向用户开放AST访问能力，显然这里的AST不会变化，而Visitor可能多种多样
Wiki
- Creational pattern: Creational patterns are ones that create objects for you, rather than having you instantiate objects directly. This gives your program more flexibility in deciding which objects need to be created for a given case.
  - Abstract Factory: groups object factories that have a common theme.
  - Builder constructs: complex objects by separating construction and representation.
  - Factory Method: creates objects without specifying the exact class to create.
  - Prototype: creates objects by cloning an existing object.
  - Singleton: restricts object creation for a class to only one instance.
- Structural pattern: These concern class and object composition. They use inheritance to compose interfaces and define ways to compose objects to obtain new functionality.
  - Adapter: allows classes with incompatible interfaces to work together by wrapping its own interface around that of an already existing class.
  - Bridge: decouples an abstraction from its implementation so that the two can vary independently.
  - Composite: composes zero-or-more similar objects so that they can be manipulated as one object.
  - Decorator: dynamically adds/overrides behaviour in an existing method of an object.
  - Facade: provides a simplified interface to a large body of code.
  - Flyweight: reduces the cost of creating and manipulating a large number of similar objects.
  - Proxy: provides a placeholder for another object to control access, reduce cost, and reduce complexity.
- Behavioral pattern: Most of these design patterns are specifically concerned with communication between objects.
  - Chain of responsibility: delegates commands to a chain of processing objects.
  - Command: creates objects which encapsulate actions and parameters.
  - Interpreter: implements a specialized language.
  - Iterator: accesses the elements of an object sequentially without exposing its underlying representation.
  - Mediator: allows loose coupling between classes by being the only class that has detailed knowledge of their methods.
  - Memento: provides the ability to restore an object to its previous state (undo).
  - Observer: is a publish/subscribe pattern which allows a number of observer objects to see an event.
  - State: allows an object to alter its behavior when its internal state changes.
  - Strategy: allows one of a family of algorithms to be selected on-the-fly at runtime.
  - Template method: defines the skeleton of an algorithm as an abstract class, allowing its subclasses to provide concrete behavior.
  - Visitor: separates an algorithm from an object structure by moving the hierarchy of methods into one object.

20. Polymorphism

概念：函数的行为，因参数个数、类型的不同而不同
三种
- Ad-hoc polymorphism
  - 形参类型是一个有限集合，针对形参类型的每个组合，都可以提供单独的实现(函数体)
  - 例子:
    - Static polymorphism: function overloading、operator overloading、template specialization、typeclass
    - Dynamic polymorphism: 各种语言中通过注册类型tuple和处理函数，来进行multiple dispatch，比如碰撞处理
- Parametric polymorphism
  - 形参类型带类型参数，输出具体类型取决于实参类型。支持的类型集合不限
  - 例子：
    - Static polymorphism: OO语言的Generic programming; FP的Polymorphism method
    - Dynamic polymorphism: 动态语言的Duck typing，如Scheme的map类型其实是(list of A) x (A->B) => list of B
- Subtyping
  - 通过运行时子类型来定义操作
    - OO语言中，Subtyping被叫做Polymorphism
    - 常见OO语言是Dynamic polymorphism(late-binding)，且是Single dispatch; CLOS支持Multiple dispatch

20. Parser的一点补充

一般一个Parser可以被定义为String -> (Success value String | Failure)，即，将输入的串，Parse过后，得到Failure，或者Success，这里的Success，是Parse值和剩余串的Pair。如果输出只有一个，则是确定性Parser(Deterministic Parser)，如果输出是一个流，则是非确定性Parser(Nondeterministic Parser)
CFG(Context-free grammar)
- Deterministic CFG
  - LL(k): 基于limited lookahead的高性能Predicative parser。k越大，语言越大。
  - LR(k): 基于Shift-reduce的Bottom-up parser，高性能。这里的k越大，grammar的灵活性越大，但是描述的CFL都是相同的。
- General CFG
  - 简单的parse方案是Top-down backtracking parser，非确定性的(因为每个非终结符有多个产生式，导致多个输出；一个符号可能多个输出，进而导致每个产生式也有多个parse结果)；直接的Backtracing parser由于Eponential time的渐进复杂度，开销极大，但是可以通过LL(k)的Predicative信息，来对备选Production进行剪枝，进而加速；但是由于非确定性，不适合用Memoizing手法做成Packrat parser
  - 相比LLBacktracking可以利用LL预测信息来优化非确定性搜索，非确定性的LR算法即GLR，也可以在非确定性搜索中利用LR的Action/Goto表来优化，两者都可以完全搜索，且效率不错
PEG(Parsing expression grammar)
- PEG是对简单Recursive descent parser的抽象，相比CFG，它使用First choice操作符而非Alternation，即直接返回第1个parse成功的产生式、抛弃后续可能的方案，来得到确定性parse的行为(因此必然无歧义，哪怕结果不“正确”)。由于PEG的First choice，实际上是通过贪心策略来消除歧义的，因此，要使得消除歧义的选择是正确的，需要精心安排产生式顺序，同时好好利用PEG提供的前向断言的无限lookahead能力。
- 由于文法上选择第1个成功parse的产生式，因此LL(k)、LR(k)那种基于任意选择的算法无法使用
- 因为只能进行Backtracking，PEG是比LL(k)、LR(k)低效的，如果和非确定性的LLBacktracking parser相比的话，PEG是确定性的，这方面有性能优势，但是LLBacktracking可以利用LL的预测信息，于是PEG只能利用Packrat来弥补了
  - 关于Error recovery
    - LL(k)、LR(k)这种确定性parser，发现错误的时候，是输入真的非法，因此记录错误信息，并进行错误恢复
    - LLBacktracking parser、PEG Parser这种会进行Backtracking的Parser，发现错误的时候，并不一定是输入非法，因此，它们不会进行错误恢复，而是尝试其他路径
- 由于PEG需要在多个产生式中查找第一个成功项，这里有backtracking行为；且PEG要求无限lookahead能力；所以经常的，PEG用Packrat parser实现
  - Packrat parser
    - 要求：确定性Parser
    - 优点
      - 避免了exponential time，复杂度是len(input) * k
      - 语法灵活性(flexibility)，如向前看、前向否定、后向断言
      - 允许左递归(特殊算法)
    - 缺点
      - 空间开销太大，len(input) * k

20. Engineering a compiler. 第4章，上下文相关分析

简介
- Attribute grammars are a functional formalism for specifying context-sensitive computation
  - 是一种经常使用的原理性自动化方法
- Ad hoc syntax-directed translation provides a simple framework where the compileer writer can hang arbitrary code snippets to perfom theses checks
  - 被广泛实际运用的技术
- 一般来说，上下文相关分析(context-sensitive analysis)可以与语法分析并行不悖的进行，也可以在语法分析后用专门的pass来进行(遍历IR)
- 为积累进一步转换所需要的上下文知识，编译器需要一些方法从语法之外考查程序某个方面的抽象，如类型系统、Storage map、Control-flow graph、Call graph
- C89那种声明语句前置的做法，可以通过在Grammar中提供专门的Declrations非终结符实现；但要确保变量先声明再使用，仍然需要上下文相关分析，需要引入符号表(这里的先声明再使用的语义分析，即使强上上下文相关语言也搞不定，因为语法是基于syntax category的，得不到变量名，又不可能去枚举变量名(空间太大))
类型系统(Type system)
- 大多数语言都将一组性质关联到每个值，我们将这组性质叫做类型
- 目标(The purpose of type system): 安全性、表达力、效率
  - 确保运行时类型安全(Ensuring runtime safety)
    - 类型系统应该确保程序是良性的(well-behavied)：即，任何病态(ill-formed)的程序都能在触发运行时错误之前被编译器(compile time checking)或运行时系统(runtime checking)识别出来
      - 比如将整数识别成浮点(无类型的汇编就可能将装有整数的地址中的值加载到浮点寄存器中)
      - 比如将整数、浮点表达式用作分支判断
    - 跟安全相关的概念是强类型/弱类型
      - Strongly typed: 每个表达式都能分配一个无歧义的类型
      - Weekly typed: 只能对多数表达式分配无歧义类型
      - Untyped:
        
        如汇编和BCPL(所有的值都是Cell)
    - 跟类型的binding time相关的概念是静态类型、动态类型
      - Statically typed: 每个表达式都能在编译期确定类型
      - Dynamically typed: 某些表达式只能在运行时确定类型
  - 提高表达力(Improving expressiveness)
    - 能够利用类型，提供多态，从而以相同的表现形式提供不同的语义，如运算符重载。事实证明程序员很擅长理解多态
  - 生成更优的代码(Generate better code)
    - 如果类型不能在编译期绑定，那么，就必须在运行时的值当中保存type tag，进行runtime type checking，付出额外的时间效率和空间效率(保存type tag)
  - 类型检查(Type checking)
    - 编译器/运行时系统必须为表达式分配类型，并验证这些类型在上下文中是否合法
    - 实际上Type checking这个概念，处理包含检测类型错误的任务外，还包括进行类型推导(Type inference)
    - 常见语言的做法：
      - C/C++: 静态类型，弱类型，无运行时类型检查
      - Java/C#: 静态类型，强类型，运行时类型检查
      - Javascript: 动态类型，强类型，运行时类型检查
- 组件(Components of a type system)
  - 基本类型(Base types/Builtin types)
    - 数字(Numbers)
      - C、C#的整数反映了硬件实现，比如大小、有/无符号、短/长浮点数
      - C、Fortran用相对术语来描述类型大小, Java使用绝对位长来描述大小
      - Lisp将List作为Built-in类型
      - Scheme将类型长度保留给实现，但要求实现精确计算的API
    - 字符(Character)
      - ASCII，Unicode，同时提供字典序
    - 布尔(Boolean)
      - used to determine the flow of control
  - 组合类型(Compound and constructed types)(Aggregate types)
    - 数组(Arrays)
      - 有的语言将数组长度作为类型的一部分(如C/C++)，而其他则将长度作为运行时属性(如C#、Java)，前者能发现一些兼容错误
      - Fortran、PL/I、APL提供数组的的向量运算
    - 串(Strings)
      - 有位串和字符串等
      - 串不同于数组的地方在于，一般串要求高效的取子串、连接以及提供字典序等
    - 枚举(Enumerated types)
    - 结构和变体(Structures/Records and variants)
      - Structure是类型的连接, Variant是类型的并(一般实现为tagged union)，前者在IP中常见，后者在FP中作为ADT出现
    - 指针(Points)
      - 某些语言的指针创建，通过在指针地址上进行多态的new(polymorphism procedure)；java通过显示的new Class；而C是malloc过后显示的转换类型
      - 通过算术运算和强制转换来创建指针，弱化了编译器/运行时系统的类型检查能力
  - 类型等价性(Type equivalence)
    - 分类
      - 名称等价性(Name equivalence)
        
        一般名称等价性都可以将类型实现为一个整数，并提供经由整数查找类型信息的能力；判等时，直接进行整数的位模式比较
      - 结构等价性(Structural equivalence)
        
        将类型实现为树(因为允许循环引用，实际上是图)，Base types是叶节点，而Compound types是中间节点；判等时，需要进行树的递归比较
    - 名称等价性的缺点在于名冲突(可以引入名空间)，结构等价性缺点是结构相同的类型在逻辑上可能要求不同、不兼容，实践中，可能结合两者
  - 为表达式推导类型(Inferring types for expression)
    - 最简单的形式是，表达式树的每个叶子节点如Literal、Identifier都有类型，函数也没有多态性，此时可以通过一趟语法树的后续遍历得到类型
  - 过程间的类型推导(Interprocedure aspects of type inference)
    - 过程间类型分析，可能要求声明函数的原型(function prototype)，从而得到类型签名(type signature)，如C语言
    - 也可能通过其他手法将类型检查延迟到编译期、连接时、运行时，如Java
属性文法框架(The attribute grammar framework)
- 简介
  - 也叫做attributed context-free grammar，将一组属性关联到文法符号上，并定义计算属性的规则
  - 根据规则中计算属性的顺序，表现为语法树的top-down顺序计算的属性，称为inherited attribute，表现为bottom-up计算顺序的，称为synthesized attribute
  - 属性文法并不规定属性计算的严格次序
- 求值方法
  - 动态方法(Dynamic methods): Knuth提出，使用就绪队列，每个属性求值后，判断被依赖属性能否求值...另外的方案，可以建立属性依赖关系图，根据拓扑顺序求值
  - 无关方法(Oblivious methods): 不动点，反复多趟执行直到所有的属性都被求值
  - 基于规则的方法(Rule based methods): 通过离线的基于规则的静态分析，得到属性的求值顺序
- 环
  - 出现环将导致失败, 处理方法：
    - 为每个属性分配默认值，从而打破环的无穷递归
    - 避免出现环
      - 只使用综合属性和常量属性，可以完全消除有环依赖
        
        只有synthesized attribute的文法叫做S-attributed grammar
      - 使用强无环属性文法(strongly noncircular attribute grammar)
- 例子
  - 简单类型推导
  - 简单的执行时间估算
- 缺陷
  - 由于属性是纯函数式的，对于非局部信息，需要在所有的规则中传递(copy rules)，导致规则复杂化
  - 由于没有规定属性求值时机，一个规则的多个步骤的执行可能有很长的周期，导致内存不能高效回收
  - 需要实例化文法符号节点，以作为属性的容器
- 其实以上缺陷都可以用一个中央数据库来改进，但那将打破属性文法框架，演变成Ad-hoc syntac-directed translation...
Ad-hoc syntax-directed translation
- 简介
  - 为每个产生式关联代码片段，由Parser在归约产生式时执行
  - 相比属性文法的两个简化
    - 每个文法符号只关联1个值
    - 值的流动方向只有1个，即从叶节点到根节点。对应S-attributed grammar
- 实现
  - 值的管理: Table driven parser可以维护一个值的栈
  - 值的引用：Parser combiantor那样通过参数，后者yacc那样通过$$和$i
  - 其他位置的代码片段
    - 产生式中间的代码：增加新的文法符号，并插入；在归约该符号时执行代码
    - 移入时的代码：为Scanner识别每个token时绑定代码
- 例子
  - 估计执行时间
  - 简单类型推导
  - 建立抽象语法树
  - 生成目标码序列
高级主题
- 类型系统中更难的问题
  - 类型一致用法和固定函数类型: 函数没有多态性，因此，跑不动点算法，就能进行类型推导
  - 类型一致用法和未知函数类型：函数具有多态性(Ad-hoc多态和参数化多态)，这里的Ad-hoc多态意味着参数类型有几个备选值，参数化多态意味着引入类型方程；进行类型推导需要解方程，因此需要合一化算法(unification)
  - 类型的动态改变：可以通过在每个赋值点进行重命名，从而固定类型(尽管类型恐怕仍然需要运行时才能推导)；重命名后，涉及控制流的汇合点，需要面对类似SSA中的Phi函数的问题
    - 动态语言的类型推导(哪怕是运行时的)，使得check elimination和check motion成为可能

22. 杂项

ANF(Administrative normal form)变换
- 所有的操作符、调用，通过变换使得他们的实参都是原子表达式(atomic expression)，方法是利用let来绑定复合表达式。如((f x) (g x))被变换成(let ([v1 (f x)]) (let ([v2 (g x)]) (v1 v2)))
- 这里的操作符包括if、set等
- 变换算法类似CPS变换
- 变换结果，是一个let序列，实际上基本等价于汇编序列了，每个let相当于计算值并装在到寄存器，而ANF变换的目的是保证汇编运算的操作数是寄存器或立即数
CEK、CESK Interpter(Control、Environment、Store、Continuation)
- CESK分别表示表达式(或program counter)、名字到地址的表、地址到值的表、以及计算结果输出的目的地；这4个元素组成了解释器的一个状态，解释器主循环通过step状态得到最终结果
- CESK实际上是一个CPS解释器，相比递归CPS解释器而言，CESK是逐步推进状态的，这使得它不需要host语言支持尾递归，通过维护一个状态列表还能进行非确定性计算
- 优点
  - 支持First class closure，进而允许Exception、Generator、Coroutine等一系列Nonlocal control-flow
  - 解释器的当前状态被表示成一个函数式结构的4元素结构，允许逐步推进、允许并行维护多个状态来支持非确定性计算、不要求host language支持尾递归
  - 有利于制作Debugger支持逐步调试
  - 有利于静态分析
Closure conversion
- 通过将闭包实现为函数+环境链的方式，在不支持闭包的host语言中实现闭包
Lambda lifting
- 增加额外参数、并在compile time-binding的调用点显示传递参数，以这种方式改写lambda移除free variable，最后将lambda改写成普通全局函数，使得不需要创建真正的closure对象；对于会作为first class function传值的lambda，仍然只能创建闭包对象(如果host语言不支持闭包，那么得进行closure conversion)
- 函数内的nested function，如果不用做first class value的话，是非常好的lambda lifting对象，Scala就是这么做的
Tail-call optimization with trampolining
- 如果解释器的host语言或者虚拟机不支持尾调用优化，为了实现包含尾递归的语言，需要对语言进行trampolining的变换
函数式语言处理的一个可能步骤
- 词法分析、语法分析、语义分析得到Annotated AST
- desugaring去掉语言的各种语法糖得到core language AST
- 解释/编译
  - CESK模板解释器
  - G-Machine
  - Lambda lifting、Closure conversion编译到C
  - ANF变换/CPS变换后编译到汇编
解释器优化
1. I argue that first, you should try an interpreter for your language.
2. If that's not fast enough, try an SICP-style optimizing interpreter.
3. If that's not good enough, try compiling to Java.
4. If that's still not fast enough, try compiling to C.
5. If that's still too slow, try continuation-passing-style compilation to assembly.
6. If you need more speed, start doing basic compiler optimizations.
7. If you're still out of luck, start doing static-analysis-driven compiler optimizations.

28. 杂项

可以用C++模板实现编译期的Lisp，包括List相关操作Map、Filter、Reduce、Zip，以及解释器Eval
- 由于不涉及代码生成和优化，主要在进行类型特化的模式匹配，所以编译速度还是挺快的
- 一个限制是，模板元编程是纯函数的，无法表示副作用，比如Eval中难以实现set!，从而无法做到letrec(以及衍生物define)。可以考虑State monad？
一般语言是很难重载&&和||且保持短路求值的，因为这需要惰性求值设施，Scala中可以用call-by-name的第2参数来完美的做DSL短路求值

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

1.markdown

1.markdown

2. Engineering a compiler. 第3章，语法分析器

8. Design Patterns: Elements of Reusable Object-Oriented Software

20. Polymorphism

20. Parser的一点补充

20. Engineering a compiler. 第4章，上下文相关分析

22. 杂项

28. 杂项

Files

1.markdown

Latest commit

History

1.markdown

File metadata and controls

2. Engineering a compiler. 第3章，语法分析器

8. Design Patterns: Elements of Reusable Object-Oriented Software

20. Polymorphism

20. Parser的一点补充

20. Engineering a compiler. 第4章，上下文相关分析

22. 杂项

28. 杂项