6.markdown

6. SICP，第4章，元语言抽象

• 大纲
  • 引
    • 建立新语言是在工程设计中控制复杂度的一种威力强大的工作策略，因为新语言能使我们以一种完全不同的方式，利用不同的原语、组合以及抽象去描述和思考问题，这些要素都是为了处理专门问题而打造的——显然，通用语言不太可能内置这些解决方案
    • 本书中已经多次演示了定制语言：图形绘制语言、数字逻辑模拟器、约束传播系统(constraint propagation)
  • 元循环求值器(Meta circular evaluator)
    • 引
      • 用与被求值的语言同样的语言编写求值器，叫做元循环
      • 求值器的基本元素
        • 处理嵌套表达式。即组合
        • 定义复合过程。即抽象
        • 使用变量。即基本元素
        • 特殊形式(special forms)。特殊的求值规则，即语法。在lisp中，被叫做宏
    • 求值器的内核
      • eval需要针对不同的form进行dispatch
        • 对于boolean、string、number等self evaluation的值，返回本身
        • 对于变量(symbol)，从环境中找出对应的值。这里包括基本过程
        • quote，返回正文。
          • 当然，还有quasiquote、unquote、unquote-slicing
        • set!，修改变量所在的环境
          • define。正确的define实现，应该是以'undefined作为初始值来let要define的变量，然后以set!替换原来的define调用
        • if，先求职predicate，再求值then或者else
        • lambda，保存求值lambda时的环境；调用复合过程本身的时候，以形参约束(bound)实参、扩展环境，再用新环境求值过程体
        • begin，按顺序求值
        • library forms(derived forms)。在实际操作中，它们可以通过macro+fundamental form实现。common lisp的宏会有些问题，而scheme的hygienic macros则比较健全
          • cond, and可以用nested if实现
          • or可以用let + if实现
          • let/let*可以用lambda实现
          • named let可以用define+lambda+call实现
          • letrec可以用lambda+define实现
          • begin可以用嵌套的lambda实现
          • do可以用named let+if实现
      • 可以将复合过程(lambda)实现为结构或者host过程，有细微区别:
        • host过程：对caller来说无法区分host过程和lambda，因此无法实现特殊求值方式；但是实现上会简单点点
        • 结构：实现会稍微复杂一点。但在进行过程调用的时候，由于可以区分host过程和target过程，因此就可以利用caller的环境，从而实现call-by-name/call-by-need/call-by-reference等精确控制的argument passing mechanism，要实现cps interpreter等可能也会稍微饶一点
      • 在求值变量的时候，沿着环境中的frame链逐个查找的方式叫做deep binding(深约束)；一种优化策略是，在编译期，将每个变量的symbol翻译成词法地址(lexical address)，然后运行时可以直接以frame index+variable index进行lexical addressing
    • 将语法分析与执行分离
      • 这是一种partial evaluation的应用，将原来运行时的pattern analysis转到了编译期，减少运行时的工作，我将之看做一种编译
      • 这种partial evaluation的手法在各种场合都可以使用，比如pattern matching, 以及包括kmp在内的各种预处理算法
        • 关键思路：算法会多次运行，而多个运行实例间，有一部分公共参数，或者叫做静态参数、pattern；通过将这部分静态参数提取出来，进行一次原算法+静态参数的预处理，生成包含静态参数信息的新算法，最后作用于各组动态参数
        • 形式化的描述一下。有多次计算：A1(S + D1), A1(S + D2), ... A1(S + Dn)，通过将A1(S)编译成A2（这个过程即partial evaluation，而生成的A2是partial application；当然，相比之下，currying的输出是一种极简的parital application），最后将原来的计算替换成A2(D1), A2(D2), ...A2(Dn)，由于A1+S只计算了一次，从而提高了性能
  • Scheme的变形——惰性求值(Lazy evaluation)
    • 正则序和应用序(Normal order & Applicative order)
      • normal order和applicative order是用来描述一门语言的属性，前者指实参的求值会延迟到实际需要的时候(IO或者和其他系统的接合处)，后者指实参的求值会发生在调用过程前
      • 如果某个参数的求值发生在进入过程体之前，则成这个参数相对于这个过程是严格的(strict)；反之，如果还没求值就进入过程，则成为nonstrict
      • normal order一般是语义层面的概念，而lazy evaluation往往是指一种实现层面的手法
      • normal order是语言语义层面的概念，而nonstrict是某个参数相对于过程的属性
        • 一般的scheme都是applicative order的，但stream-cons的cdr参数、甚至包括car参数是nonstrict的
    • 一个采用惰性求值的解释器
      • 比起stream-cons这样通过special form来实现lazy evaluation，让整门语言变成normal order的好处是，具有nonstrict参数的过程可以被当做first-class值用于过程参数和返回
      • 在scheme社群中，以thunk称呼lazy得到的延迟对象，通过force来迫使thunk对象求值；如果thunk本身带有缓存，那么往往用于实现call-by-need，如果没有缓存，则被用于实现call-by-name
  • Scheme的变形——非确定性计算(nondeterministic computing)
    • amb和搜索
      • amb是John McCarthy在1961年第一次提出的
      • 本节的amb实现是基于历史的回溯(chronological backtracking)，或称为深度优先搜索
      • 自动搜索的历史
        • 1967年，Rebert Floyd第一次提出可能通过搜索和自动回溯，把非确定性算法很优雅的做紧程序设计语言里
        • 1969年，Carl Hewitt发明了Planner程序设计语言，它显示支持自动按历史回溯(automatic chronological backtracking)，采用depth first search
        • 1971年，Sussman、Winograd和Charniak实现了Planner的一个子集，叫做MicroPlanner，用于支持问题求解和机器人规划工作
        • 类似的想法也出现在逻辑和定理证明领域，导致Prolog语言在爱丁堡和马赛诞生
        • 1972年，由于自动搜索遇到极大障碍，McDermott和Sussman开发了一种名为Conniver的语言，包含程序员控制下的搜索策略安排机制，但这种方式被证实难以使用
        • 1975年，Sussman和Stallman在研究电子线路的符号分析过程中创建了一种更容易控制的方法，他们开发出一种基于相互关联的事实之间的依赖关系的非历史的回溯模式，被称为依赖导向的回溯(dependency-directed backtracking)。虽然方法比较复杂，但性能可接受了，因为工作中很少做多余的搜索
        • 1979、1980年，Doyle和McAllester推广并进一步澄清了Sussman和Stallman的方法，开发了一种新的构造搜索形式，被称为正确性保持(truth maintenance)。新型问题求解系统都用了某种形式的正确性保持技术
        • 1987年，Zabin、McAllester和Chapman描述了Scheme的一种基于amb的非确定性扩充，采用的是依赖导向的回溯
    • 非确定性程序的实例
      • 解逻辑题
      • 依赖于搜索的数值题
      • 一个例子，自然语言语法分析
    • 实现amb求值器
      • 原理：
        • cps解释器
        • 保存continuation后，可以在任何时候通过调用continuation来返回过去的某个程序状态(通过监听set!，在backtracking的时候进行undo)；因此，管理一系列的continuation后，就相当于拥有了一部时间机器，这就是amb的本质
        • 该amb解释器通过将每个amb form调用点上的continuation及一系列的备选值保存起来，链接到fail closure chain中，在计算失败的时候取出并执行顶上的fail closure就相当于取出最近的一个continuation和备选值进行回溯
        • fail closure chain其实就是continuation + value的chain，它们就是continuation的管理者，也就是时间机器的核心
      • 用call/cc辅以显示的continuation+value链，也能实现amb
  • 逻辑程序设计
    • 关键
      • pattern matching，模式匹配。输入一个模式和数据，将模式中的变量绑定到对应的数据
        • 在scheme中，linear pattern matcher，无论是运行时还是编译期的都很好写，注意运用partial evaluation去掉运行时的模式分析
      • unification，合一。pattern matching的推广，匹配的两边都是模式，因此，一次unification结束，可能两边都还有变量没约束到具体的数据，但只要没发生匹配失败，那合一仍然可以结束
• 启发
  • 一个简单的求值器有可能去模拟远比求值器本身复杂的各种程序，尽管这种结果可能会稍微违反直觉
  • 图灵提出的停机问题，是清晰给出的第一个不可计算问题：一个良好刻画的工作，却不能由一个计算过程完成

    • 不可能写出过程halts?，用于判断一个程序是能停止:

      (define (test f) (if (halts? f) (test f) 'halted) ) (test test)

  • 不借助define实现递归：Y combinator
    • 在C++这种无GC环境中，它还是一种存储上的解决方案（打破了lambda递归时的存储限制）

6. SICP，第5章，寄存器机器里的计算

• 大纲
  • 寄存器机器的设计
    • 相比标准x86过程的calling convention，手工调优的汇编的访存能够更精确，比如fibonacci的尾递归实现，能够只使用寄存器！(当然，本质上只是一个for循环的迭代)
    • 本节中的指令集
      • 数据传输
        • (assign (reg target) (reg source))
        • (assign (reg target) (constant c))
        • (assign (reg target) (label l))
      • 算数运算
        • (assign (reg target) (op +) inputs ...)
      • 跳转
        • (test (op =) inputs ....): 测试，影响状态寄存器
        • (branch (label l)) : 条件跳转
        • (goto (label l)), (goto (reg target)): 非条件跳转
      • 栈操作
        • save
        • restore
      • IO
        • (assign (reg target) (read)): 输入
        • (perform (op print) inputs ...): 输出
  • 一个寄存器机器的模拟器
    • 机器模型
    • 汇编程序
      • 这里的汇编，也是一个partial evaluation的过程，将上面的指令集文本(语法树datum)转化成可调用的过程，其中会将寄存器的位置、label的地址等都取出来
    • 监视机器执行
      • 一个比较有意义的统计是，统计栈的入栈和最大栈深，以衡量访存频率 ；如果是有内存寻址模式的指令集，也应该衡量访存次数
  • 存储分配和垃圾回收(Storage allocation & Garbage collection)
    • 将存储看做向量
      • 这里的list，其实是采用了cons的get-new-pair+set-car!+set-cdr!版本实现！
    • 维持一种无穷存储的假象
      • 这里用汇编(前文描述的指令集)实现了一个compacting gc
  • 显示控制的求值器
    • 显示控制求值器的内核
      • 这里用汇编实现了一个scheme解释器，入口是eval-dispatch
      • 必须区分基本过程(机器直接支持的运算如+-*/)和lambda建立的复合过程，后者需要递归
    • 序列的求值和尾递归
      • 注意这里用汇编实现的尾递归优化，避免了栈积累
  • 编译
    • 引
      • 编译大大提高了程序的效率，而解释则为开发和排错提供了更好的环境
      • 现实中的lisp系统往往是编译和解释的结合，对于库等稳定过程，直接将过程编译成native code(当然需要和运行时系统链接在一起)，而对于用户自定义代码，则可能是解释执行，但解释和编译的过程可以交换调用
      • 编译比解释快很多
        • 对源码的解释和错误诊断移到了编译期，没有运行时开销
        • 可以针对特殊情况进行特化，不需要考虑不同的可能。比如一个self-evaluating的值，可以直接返回本身，而无需走eval流程；也可以判断一个过程是内部过程，从而直接调用
        • 对于变量求值，由于可以在编译期进行分析，从而进行lexical adderssing而不是deep binding，加速变量查找
    • 编译器的结构
      • 类似解释器的eval，遍历语法树，不过不再是env+exp返回value，而是exp+symbol-table+next返回instruction-list。类似龙书里的语法制导的翻译(syntax directed translation)
      • 不知这是否算是一种abstraction interpreting
      • 要减少不必要的存储器访问。比如尽可能少的save/restore
    • 词法地址
      • 通过编译期的symbol-table，将所有的变量引用转换成词法地址(即frame index+variable index)
      • 由于所有的local definition都可以翻译成let，所以所有的bound variable和free variable都有词法地址
      • 对于全局变量，它没有词法地址，但是可以在编译期判断一个变量的全局/词法属性，因此，如果一个变量是全局变量，那么，可以在运行时直接在全局frame中查表，而非沿着frame list逐帧查找的deep binding
        • 全局变量无词法地址的这种限制，是由于top level definition存在导致的
        • 可以进行一个小小的优化，将全局变量访问也优化成lexical addressing。即引入一个数组，里面存放的是全局变量的地址，其中每个地址和global hash table中的地址相同，从而单个文件中的全局变量能够直接使用该数组的索引来访问
    • 编译代码与求值器的互连
      • 同一系统中同时提供编译和解释两种方案，供用户混合使用，用户可以将稳定和易变的部分分别编译和解释，从而运行效率和开发效率两不误。这就要求系统提供编译模块和解释模块的互相调用机制
• 启发
  • 关于编译(compiling)
    • 被硬件直接解释执行的语言称为native language或者machine language
    • 通用计算机的电路实现的是其指令集的解释器，是为解释器专门定制的
    • 如果不考虑通用计算机高度优化的事实的话，为每个程序生成专门的硬件电路并生产机器，专门用于执行该程序，才是最快的
    • 考虑到为每个程序都生成电路，成本太高，一种折中是，为每种语言的解释器(只不过是一个特殊的程序)生成电路并生产机器
    • 作为用于实现解释器的硬件代表:
      • 8086，实现的是寄存器语言的解释器(即x86)，包括数据传输、算数/逻辑运算、条件/非条件跳转等指令
        • native语言是x86，硬件是x86的解释器
        • x86由硬件直接解释执行
        • 对于高级语言A，如果A的解释器是用x86编写，而A语言的源码交给该解释器解释执行，那么机制叫做解释(如lua/bash)
        • 对于高级语言B，如果B的编译器是用x86编写，而B语言的源码交给该编译器翻译成x86执行，这种高级语言被翻译成native语言后再执行方式，叫做编译(如C/C++)
      • lisp machine，该硬件实现的是lisp解释器，硬件操作包括car、cdr等
        • native语言是lisp，硬件是lisp解释器
        • lisp由硬件直接解释执行
        • 对于高级语言A，如果A的解释器是用lisp编写，而A语言的源码交给该解释器解释执行，那么这是解释(比如lisp machine上的C解释器，当然，这种做法可能会比较少，静态编译型语言多半会直接编译)
        • 对于高级语言B，如果B的编译器是用lisp编写，而B语言的源码会被该编译器翻译成lisp后再执行，那么该过程叫做编译(如C->lisp的编译器)
  • 对于高级语言C和现有体系结构S1，如果将C移植到体系结构S2中呢？
    1. 直接用S2编写C的解释器，然后将该解释器放到S2机器上，于是S2机器上的C源码能被解释执行
    2. 用C编写C->S2的编译器，然后将这个用C语言编写的编译器在S1机器上编译成S1程序
       • 利用S1上的编译器，编译各种C语言程序到S2，然后将输出的S2程序拿到新机器上运行。这叫交叉编译(cross compiling)，Android/iOS开发环境中编译器就是运行在x86上的交叉编译器
       • 利用S1上的编译器，编译该编译器的C源码本身，得到一个工作在S2上的C->S2的编译器。这叫自举(bootstraping)。有了这个能在S2上运行的新编译器，于是可以在S2上写C代码并独立编译了
       • 利用S1上的编译器，编译C解释器的C源码，得到一个S2上的C语言解释器，从而能在S2上解释执行C语言。这个解释器的运行速度和1.中的手工解释器不同，区别是手工汇编和编译器输出的优化水平差距

6. 杂项

• Scheme
  • (arg1 . args)处理起来其实是高度统一的，无论是pattern matching，或者是用于其他什么目的
  • 宏系统其实是向用户开放library form的自定义。又叫语法扩展，因此定义宏叫defmacro或者define-syntax
  • 注意SICP中编译(partial evaluation)表达式序列时的组合方法
    • 它实际上在编译期分析了序列的结构，避免了运行时的map，对1元素、2元素的短序列效果尤其明显
    • SICP中使用的是非尾递归结合，但实测我用的尾递归结合在元素数>2时，在racket中更慢，不知为何。但能确定的是，我的尾递归结合在FP解释器中不会栈溢出
  • lexical addressing的frame index，在meta-circular evaluator中优化效果极为明显(比variable index效果更显著)
  • 选出无序数组的最小项
    • sort+min法，在applicative order的语言中，是O(n*log(n))的，但在normal order的语言中，是O(n)的
  • 如果cons的cdr是nonstrict的，那么，可以实现lazy list(即stream)；如果cons的car也nonstrict了，则可以实现lazy tree
    • racket的stream-cons参数是完全nonstrict的，因此racket的stream可以实现lazy tree
  • 单一状态的管理
    • 变量(引入赋值，side effect): 保存状态的最新版本。赋值的先后有区别，存在时序问题
    • 流：保存状态的完整历史。所有状态(所有流)版本一致，无时序问题，但随着状态的更新，空间复杂度是O(n)的。对应顺序模型？
    • amb: 只保存当前值，但同时提供备选值的搜索。对应分叉模型？
  • scheme中的宏相关：define-syntax, let-syntex, letrec-syntax, let*-syntax, syntax-rules, syntax-case, with-syntax
    • syntax-rules, with-syntax都是用syntax-case实现的
    • syntax-case也可用于一般的模式匹配
    • 和common lisp的宏(defmacro)不同，scheme的宏基本是一门DSL，它是hygienic macro
  • lisp是少有的解释/编译对用户不透明的语言，这主要表现在macro expansion time上
    • 对于边解释边执行的解释器而言，macro expansion time就是解释期。显然，宏体中能访问宏定义之前的所有过程
    • 对于先编译再求值的编译器而言，macro expansion time发生在编译期。显然，宏体中不能访问同一个编译单元(文件)定义在宏定义之前的用户过程，因为它们要到运行时才会产生
    • 基于上面的解释，有限制的在宏定义中访问用户自定义过程
  • hygienic macro
    • 包括两个要素，referential transparency和hygienic
      • 前者指，对于非模板引入变量以及pattern varaible，该identifier将绑定到macro expansion time时进行lexical addressing的结果上
      • 后者指，在宏模板中引入的局部identifier，绝不会和模板输入中的symbol发生名冲突
    • 它的模板中的每个identifier都在macro expansion time进行绑定，每个identifier的身份可能是三者之一：pattern variable、bound variable(hygienic相关)、free variable(referential transparency相关)
    • unhygienic macro(defmacro)展开的结果，是纯datum；而hygienic macro(define-syntax)展开的结果，是包含bound variable的datum，后者是由pattern varaible和bound variable代换后得到的
    • 在scheme中要使用unhygienic macro，需要使用with-syntax来引入绑定到固定值的新pattern varaible
      • 比如实现this、yield、await等关键字
  • 宏的特点和对策
    • 特点
      1. call-by-name: 有副作用时破坏正确性；非优化编译器中还有计算量上的额外开销
      2. dynamic scoping: 惊喜
      3. 在宏中引入局部变量时的名冲突：惊喜
      4. 另外，宏的实现可能应该让实参的求值顺序符合直觉
    • C宏:
      1. 无视副作用；或者，引入新名字来cache值，但会造成命名冲突
      2. 无解
      3. 无解
    • defmacro(unhygienic macro)
      1. 引入新名字cache值，用gensym避免名字冲突
      2. 无解
      3. gensym
    • define-syntax(hygienic macro)
      1. 引入新名字，hygienic属性避免了名冲突
      2. referential transparency的属性
      3. hygienic属性
  • 一般在lisp系统中，调试宏展开有expand和expand-1等过程
  • 由于S-expression的特点，函数调用和special form在语法上没有区别，唯一的区别是求值规则不同
  • 什么时候使用宏，什么时候使用过程？
    • 只在无法用过程实现时才使用宏！即，需要特殊的求值规则时才使用宏
  • quote、quasiquote、unquote、unquote-slicing是scheme内置的模板系统，进行语法变化和数据处理时非常方便
  • 在pure functional programming language中(比如haskell)，因为不能访问IO，所以无法用print来调试，故你的编写完备的单元测试
  • stream和amb都能实现无限的数据结构
  • S-expression作为前缀记法(polish notation，相对的是虚拟机字节码采用的reverse polish notation)的优点:
    • 无歧义，不需要优先级
    • 每个operator支持无限个operands
  • 注意写递归的hygienc macro时，其递归部分绝不该被多次引用，尤其注意这里宏参数的call-by-name陷阱。否则其时间复杂度会上升到指数级，类似fibonacci的递归算法
    • 对测试是，如果需要将递归部分作为参数来调用其他宏，先用let将递归部分绑定到一个变量
  • 实现scheme解释器的三要素分别对应于SICP中一再强调的DSL三要素
    1. 基本元素 —— 求值变量(进一步扩展的话，还能把self-evaluating包含进来)
    2. 组合 —— 求值调用，即先求值operator和operands，再将后者apply到前者
    3. 抽象 —— 求值lambda
       • 剥离抽象的方法，是用pattern matching(甚至unification)约束变量后，然后求值抽象本体
  • lisp的pattern matching非常适合用来写parser、assembler、macro等
• C/C++
  • 实参的求值顺序不定，因此f(read1(), read2())是很危险的，因为不知道用户的实际输入对应的是哪个参数。因此避免同一个表达式中出现多个副作用操作
  • 尽管C/C++编译器往往不支持尾递归优化，但可以将函数体写成for(;;)，再改写尾递归调用为修改参数+continue，就能手工完成尾递归优化。这在写FP解释器时尤为重要
• 比较mark & sweep和copy & compacting
  1. compacting后，碎片少，换页少，cache利用率高
  2. 前者是O(a)+O(n)的(这里的a是活跃块，n是所有块)，后者是O(a)的，如果活跃块:总块数的比值很小，即大部分都是垃圾，那么copy&compacting性能优势明显
• Continuation和CPS
  • Continuation的常见作用
    • 多值返回
    • 异步callback
    • 普通递归转化成尾递归(如果再进一步支持尾递归优化的话，就相当于将递归的栈完全转移到堆中)
    • 提供成功/失败两个continuation分支。比如运行时/编译期的linear pattern matcher中
  • 任何lisp系统都可以通过全文CPS变换来去掉call/cc调用
  • 和Continuation passing style对应的概念是传统的Direct style
  • logic programming和functional programming使用CPS作为intermediate representation，而imperative programming使用SSA作为IR
    • SSA等价于CPS去掉non-local control flow后的子集
  • CPS令catch/throw、coroutine、amb等non-local control flow易于实现
  • 在CPS中，所有的函数都有一个k参数；所有的call，其操作符要么是变量要么是lambda

    • 基本过程通过重命名op->op&来区分，比如DS表达式(* a (+ b c))的CPS版本是:

      (+& b c (lambda (v) (*& a v k)))

    • 像这样，将表达式转化CPS过后，基本过程op&可以进一步优化掉

  • CPS的内存模型
    • 将一个程序看做一颗调用树，main函数是根，main函数的各个调用语句对应各个子树，其他函数以及它函数体内的调用也看做父节点和子树的关系
    • 一个程序的运行，就是这颗调用树的部分遍历(忽略递归)，输入不同，遍历就不同
    • 一个程序的运行，可以看做程序状态的一个序列，程序历经整个序列后结束；其中每个程序状态，是对调用树遍历的一个静态快照
    • Directy style和程序状态的关系
      • directy style用栈来遍历调用树，随着遍历的进行，栈顶会push/pop(对应call/ret)
      • 一个程序状态(即遍历的某个瞬间)，对应于栈在某刻的snapshot，从栈顶到栈底的各帧，对应于沿调用树上某个节点沿父节点上溯形成的链
      • 一个程序状态和directy style中栈的snapshort一一对应，换句话说，一个程序历经各个栈的快照后结束
      • DS通过变化的栈来模拟遍历的过程，栈的深度表示调用树中当前节点的深度；整个过程中没有冗余，内存管理高效、实时，没有任何历史信息
      • 要保存某个程序状态，在DS中需要dump整个栈，开销很大(有可能实现用户态的copy on write吗？)
      • DS中仍然可以实现部分仅依赖于祖先节点而非历史状态的non-local control flow，比如exception(它只关心throw节点以及各个catch的祖先节点)
    • Continuation passing style和程序状态的关系
      • 一个过程体中有多个子调用，在CPS中，对第i颗子树的遍历，被表达为以K(i+1)为参数调用C(i)，其中C(i)是第i个子调用的过程，而K(i+1)是它的continuation；K(i+1)包含了i+1~n的子调用信息，它接收一个值，并继续执行以K(i+2)对C(i+1)的调用，该过程递归下去
      • 随着调用树的遍历，遍历过程会先后历经对父节点P的子树C0~Cn的遍历，都进行完毕过后，P节点遍历完毕，改为继续遍历P的父节点
        • 在DS中，这个先序遍历表现为，将P入栈，再将C0入栈、出栈，再将C1入栈、出栈，最后弹出P
        • 在CPS中，这个先序遍历表现为，以K(1)调用C(0)，K(1)在C(0)中被调用后，导致K(1)过程体中的以K(2)调用C(1)被触发，最后当C(n)执行完毕后，它会调用来自父节点的K(p)
      • 如果C(i)是复合过程的话(lambda)，以K(i+1)调用C(i)，会导致递归，C(i)的过程体中，又有一系列的子调用，它们也会被组织成一系列的CPS调用，在这个环境中K'(p)等于上一帧的K(i+1)
      • 一个程序状态，由一系列的调用节点组成，第i个节点有个状态s(i+1)表示下一步应该遍历其第i+1个节点；因此，一个程序状态可以用数组[s0(i0), s1(i1), s2(i2), ...]来表示，其中数组的前后两项互为父子调用, ik表示深度为k的子调用下一步应该遍历的子树，sk表示深度为k的子调用的过程，比如s0为main，而sk(ik)表示取sk这个过程的第ik个子调用
        • DS中，sk(ik)被存储在栈上，call的时候push，ret的时候pop，栈顶的帧将sn(in)存储在eip中
        • CPS中，用continuation chain来表示某个程序状态中的各个调用节点，该链上第k个节点的ck就表示sk(ik)，因为ck这个continuation在语义上就是接下来应该做的事
      • 因为continuation chain是FP风格的，程序运行的一系列状态被模拟为一系列的chain，相邻的两条chain只有顶上的节点不同，而前面的n-i个节点完全共享(是共享，而不只是相同，因为FP风格)
      • 在不考虑set!的情况下，CPS通过不停的创建新的continuation chain的方式来模拟遍历(创建方式是: old-chain => (cons (next (car old-chain)) (cdr old-chain)))，所有的历史都在内存中
        • 这就要求：高效的GC
        • 提供的能力：保存下任何时刻的一个continuation chain或者其前缀(一条continuation chain和它的任意前缀都是整个程序中的一个状态)，就能在将来的任意时刻利用该chain重新计算；这就提供了CPS以non-local control flow的能力，甚至像amb那样的时间机器的能力
      • CPS中，保存一个程序状态，只需要存储一个continuation chain(或者简单的说，就是continuation)，这是无成本的，唯一的影响是GC，以及副作用(set!)的干扰
    • DS使用系统栈来模拟程序状态，CPS使用continuation chain来模拟程序状态，前者在栈上，后者在堆中，故后者的递归深度只受堆容量影响而不受栈容量限制
    • CPS模型中，永远都在进行调用，或者是调用C(i)，或者是调用K(i+1)，而不会返回(直到遍历结束才返回)，故，必须要求解释器实现尾递归优化，这样才能实现chain的O(d)堆空间以及O(1)的栈空间需求
      • 如果没有尾递归优化，那么，CPS对系统栈的需求是O(n)，这里的n是调用树的一个遍历中所有节点的总数，而非DS的O(d)栈需求
    • DS的空间需求是O(max(d))
    • CPS的空间需求是O(n)。内存中共有n个chain，但n个chain的cdr都共享。其中有一个活跃的chain，k个由于call/cc而被引用的特殊chain，以及一系列没有引用可被GC的历史chain；另外还有O(1)的系统栈需求(如果没有尾递归优化，则是O(n)的栈需求)
  • 关于尾递归算法和非尾递归算法(这里指没有经过任何特殊变换的原始算法)
    • DS
      • 尾递归算法：O(1)的栈，O(n)的时间
      • 非尾递归算法：O(d)的栈，O(n)的时间
    • CPS
      • 尾递归算法：O(1)的栈，O(1)的堆，O(n)的时间
      • 非尾递归算法：O(1)的栈，O(d)的堆，O(n)的时间。当然，必须先将非尾递归算法转换为CPS，后者本身就是一种尾递归形式，但这个转换不影响空间复杂度
  • call/cc的参数f所接受的那个参数k，就是continuation，因此CPS解释器和CPS translation都很容易实现call/cc
  • 有一种CPS的变形，我将它叫做VCPS
    • CPS中，以k调用一个过程，会立即求出结果并调用k输出
    • VCPS中，以k调用一个过程，会返回一个pair(v1 k2)，调用(k2 v1)会进一步返回(v2 k3)，最终返回(vn k)，这时再调用一次，最初的输入k就会以最终结果vn被调用了
      • 相比CPS的自动求值，VCPS是由外部来驱动的，外部可以控制这个节奏
      • 由于需要创建n个pair，VCPS会稍微慢一点(lua/python等可以用tuple)
      • VCPS不要求尾递归优化的支持(注意，即使host语言不支持尾递归，也很容易用专门技巧实现尾递归优化的解释器的)
      • VCPS很适合用来生成递归数据结构的迭代器
        • Python/C#的yield只适合用来生成非递归容器的迭代器，对于递归容器，需要以其他方式线性化。当然你可以用yield模拟coroutine，但很丑陋
        • 可以用coroutine来生成递归ADT的迭代器，但有的语言没有协程，有的语言其协程性能差(比如在scheme中call/cc模拟的协程)
    • VCPS的实现
      1. 将树遍历(无论是ADT容器的遍历还是语法树的遍历)由DS改成CPS，所有的过程都有一个额外参数k
      2. 对于会产生值的递归节点，将k(value)改为(cons v k)
      3. 对于不会产生值的节点，直接调用(k nil)
      4. 注意该算法中的语义变化
         1. (proc arg1 ... argn k)，输出不再是以v调用k了，而是(cons v1 k2)(这里的k2可能不是k)；输出也可能是(k nil)的输出
         2. (k v)在CPS中不返回，而VCPS中它会立刻返回(cons vi ki+1)
    • 总之VCPS的特点是：不要求宿主支持尾递归；写迭代器很方便
• 编写递归数据结构的迭代器
  • 协程。coroutine，call/cc等
  • 在迭代器中携带手工维护的栈
  • VCPS。等价于携带栈的方法，但编码更容易
    • 在racket上，该方法实现的迭代器性能秒杀list、stream、call/cc等方案
    • 在lua中，性能不及coroutine
  • ADT专用算法，如二叉树的parent节点，线索二叉树
• Lua project
  • 实现简单的scheme解释器，最少语言元素：变量+lambda+过程调用。同时支持currying，因此多参过程的声明和调用都是syntax sugar
    • 由于解释器很简单，为了打印fibonacci数列，就在脚本中运用了Y-combinator、church numberal的手法
  • 用VCPS写二叉树的迭代器，比coroutine更慢；注意在lua中，VCPS可以用tuple代替pair
  • 用coroutine实现yield、async/await
• Python project
  • 用yield实现coroutine、async/await
• Scheme project
  • 用racket实现的amb解释器，居然比直接用racket的call/cc实现amb高效得多；另外自己实现的cps解释器中的call/cc也比racket的call/cc高效得多...
  • 尝试yin-yang-puzzle，将原题改写、去掉call/cc，然后再运用substitution model进行推导(deduction)
  • 用VCPS写多叉树迭代器，处理tree comparison问题，比用list、stream、call/cc写的迭代器都快！
  • 用宏写单元测试框架
  • 用call/cc实现yield、coroutine、async/await、exception、amb
  • 编写运行时的linear pattern matcher；提供运行时解释版本以及预编译版本(partial evaluation)
  • 编写编译期的linear pattern matcher宏
  • 用racket的match写一个简短但完备的meta-circular evaluator
  • 写一个cps解释器
    • 解释器本身用match宏来dispatch
    • 支持defmacro，基于运行时预编译的pattern matching；cond/and/or/let/let*/letrec/do等library form都是宏实现的
    • lexical addressing
    • call/cc。能够跑async/await、yin-yang-puzzle的示例
  • 写一个vcps的scheme解释器，比cps版本慢了点
  • 最简短的cps解释器，能够演示lambda calculus、yin-yang-puzzle的示例
  • list comprehension的宏
  • 比较啰嗦的parser combinator尝试
  • lisp 99 problems中的50余题
  • project euler的前50题

8. The little schemer

• 先正确，再简化/优化
• Use help function to abstract from representation
  • 要从多个实现中提取公共部分，方法是，将公共部分提取成函数(更高级的抽象)，然后将多个版本的变化以高阶函数的方法作为参数传入
• 需要将一组参数/动作打包的时候，用build过程
• car, cdr。cdr读作could-er
• 递归过程中，每次至少修改一个参数，这个改动将让递归逐渐趋向结束条件(不考虑通过副作用修改free varaible)
  • total function: 会返回的递归函数，其递归过程趋于收敛。
  • partial function: 递归条件是否收敛不可知，可能永远不结束。等价于while(true);的递归，是most partial function
    • 比如游戏；比如(even? recur(n/2); odd? recur(3*n+1))的经典算法
  • 要写出判断一个函数是total还是partial的过程halt?，是不可能的，这就是经典的停机问题
    • 和halting proof等价的一个问题是，无法写出一个函数，用于判断f1、f2对任意输入n都等价
• SICP中反复提到的三要素，primitive、combination、abstraction，正是lambda calculus原始定义的三要素(variable, application, lambda abstraction)
• 抽象和表现的分离。一个案例，数值zero, one, two, three是抽象(可以基于抽象运算符zero?,add1,sub1)，而表示可以是:
  • 符号(symbolic): 0, 1, 2, 3
  • church numeral: (lambda (f x) x), (lambda (f x) (f x)), (lambda (f x) (f (f x))), (lambda (f x) (f (f (f x))))
  • 列表: (), (()), ((())), (((())))
  • 列表: (), (()), (() ()), (() () ())
• scheme中的惯例，如果一个list的car也可以是list，那么这样复合的list就是S-expression了
• 写meta-circular解释器时，env-lookup实现中，frame-lookup的参数应该是frame, name, fail，如果一个frame找不到，则会以name为参数触发fail，env-lookup依赖这个机制递归的查找cdr frame-list
• 在scheme或者说lambda演算中，call form的术语是application
• 实参: actual arguments；形参: formal arguments，又叫formal parameters
• lazy evaluation的相反概念是eager evaluation
  • 描述参数的相关术语: nonstrict, strict
  • 描述语义的相关术语: normal order, applicative order
• 我熟悉的Y-combinator其实是applicative-order Y combinator

8. 黑客与画家

• static vs dynamic typing
  • 静态类型的优点：类型检查，更少的bug；compile time binding的优势，优化分析
  • 动态类型的优点：更自由的程序结构(想象Y-combinator、curry、memoize的函数签名会怎样)；作者称，静态语言无法实现用于语法变化的宏
• 软件的圣杯，可复用性(reusability)
• counter的例子中，python等语言需要各种手工hack来弥补语言缺陷，这其实就是在扮演人肉解释器的角色，是所谓"任何C程序复杂到一定程度后，都会内置一个lisp解释器，或者程序员自己充当人肉解释器"
• 如果在程序中发现了大量的模式，则这本身就是错误；程序只应该反应要解决的问题，重复的模式说明抽象不够深，在做着人肉解释器的工作，应该考虑用宏进行syntactic abstraction了

9. Peter novig: Design pattern in dynamic programming

• 16 of 23 patterns are either invisible or simpler
  • First-class types: Abstract-Factory, Flyweight, Factory-Method, State, Proxy, Chain-Of-Responsibility
  • First-class functions: Command, Strategy, Template-Method, Visitor
  • Macros: Interpreter, Iterator
  • Method Combination: Mediator, Observer
    • Combinator origned?
  • Multimethods: Builder
    • Multiple dispatch?
  • Modules: Facade
• First-Class Dynamic Types
  • First-Class: can be used and operated on where any other value or object can be used
  • Types or Classes are objects at run-time (not just at compile-time)
  • A variable can have a type as a value
  • A type or class can be created/modified at run-time
  • There are functions to manipulate types/classes (and expressions to create types without names)
  • No need to build extra dynamic objects just to hold types, because the type objects themselves will do
• First-Class Dynamic Functions
  • Functions are objects too
  • Functions are composed of methods
  • There are operations on functions (compose, conjoin)
  • Code is organized around functions as well as classes
  • Function closures capture local state variables (Objects are state data with attached behavior; Closures are behaviors with attached state data and without the overhead of classes.)
• Macros
  • Macros provide syntactic abstraction
    • You build the language you want to program in
  • Just as important as data or function abstraction
  • Languages for Macros
    • String substitution (cpp)
    • Expression substitution (Dylan, extend-syntax)
    • Expression computation (Lisp)
      • Provides the full power of the language while you are writing code
• Method Combination
  • Build a method from components in different classes
  • Primary methods: the “normal” methods; choose the most specific one
  • Before/After methods: guaranteed to run; No possibility of forgetting to call super ; Can be used to implement Active Value pattern
  • Around methods: wrap around everything; Used to add tracing information, etc.
  • Is added complexity worth it?
    • Common Lisp: Yes; Most languages: No
• Other Invisible Patterns:
  • The following patterns are invisible in dynamic languages, and usually implemented more efficiently
    • Smart Pointers: Pointers that manage copy constructors
    • Reference Counting: Automatic memory management
    • Closures: Functions with bound variables
    • Wrapper Objects: Objects with one data member, a primitive type such as a character or 32-bit integer
• New Dynamic Language Patterns:
• First-Class Patterns: make the design more explicit
  • Subroutine
    • Long ago, subroutine call was just a pattern
    • Involves two parts: call and definition
    • Nowadays, made formal by the language
    • Note there are still 2 parts in formal use of pattern
    • Many patterns are harder to define formally because their use is spread out over more than two places
  • Abstract class
  • Generic function
  • Macro
• Iterators: a study of C++, Dylan, Smalltalk and Sather
  • Iterator
    • C++ STL
  • Internal Iterator
    • C/C++
    • Smalltalk: Passing a block to the do method: employees do : [ :x | x print]
    • Inconventient for iteration over multiple collections
      • How dou you compare two collections?
      • How do you do element wise A:= B + C?
• Coroutine
  • Intent: separate out distinct kinds of processing; save state easily from one iteration to the next
  • Implementation: Most modern language implementations support an interface to the OS’s threads package. But that has drawbacks:
    • No convenient syntax (e.g. yield, quit)
    • May be too much overhead in switching
    • Problems with locking threads
  • Implementation: Controlled uses of coroutines can be compiled out (Sather iters, Scheme call/cc)
• Control abstraction
  • Most algorithms are characterized as one or more of:
    • Searching: (find, some, mismatch)
    • Sorting: (sort, merge, remove-duplicates)
    • Filtering: (remove, mapcan)
    • Mapping: (map, mapcar, mapc)
    • Combining: (reduce, mapcan, union, intersection)
    • Counting: (count)
  • Code that uses these higher-order functions instead of loops is concise, self-documenting, understandable, reusable, usually efficient (via inlining)
  • Inventing new control abstractions is a powerful idea
• Mixing compile time and run time: Memoization, Compiler, Run time loading, Partial Evaluation
• Memoization
  • Intent: Cache result after computing it, transparently
  • Complications: Know when to empty table, how many entries to cache, when they are invalid
• Compiler
  • Like the Interpreter pattern, but without the overhead
  • A problem-specific language is translated into the host programming language, and compiled as normal
  • Requires complex Macro capabilities May or may not require compiler at run time
  • A major factor when Lisp is faster than C++
  • In a sense, every macro definition is a use of the Compiler pattern (though most are trivial uses)
  • Examples: Decision trees; Window, menu layout; Definite Clause Grammar; Rule-Based Translator
• Run-Time Loading
  • Intent: Allow program to be updated while it is running by loading new classes/methods (either patches or extensions). Good for programs that cannot be brought down for upgrades.
  • Alternative Intent: Keep working set small, start-up time fast by only loading features as needed
  • Implementation: DLLs, dynamic shared libraries.
    • Language must allow redefinition or extension
• Partial Evaluation
  • Intent: Write literate code, compile to efficient code
  • Implementation: Mostly, at whim of compiler writer (Harlequin Dylan, CMU Lisp compilers good at it)
  • Alternative Implementation: Define a problem specific sublanguage, write a compiler for it with partial evaluation semantics
  • Example: Macro call horner(1 + 2 * x + 3 * x ^ 2) expands to 1 + x * (2 + 3 * x)
• Design Strategies
  • What to Build
    • Class Libraries / Toolkits: Generic (sets, lists, tables, matrices, I/O streams)
    • Frameworks: Specialized (graphics), “Inside-Out” (callbacks)
    • Languages: Generic or Specialized (Stratified Design)
    • Design Process: Source control, QA, Design rationale capture, ...
    • Metaphors: Agent-Oriented, Market-Oriented, Anytime Programming
  • How to Build
    • Programming In a language: The design is constrained by what the language offers
    • Programming Into a language: The design is done independently of language, then the design is implemented using features at hand
    • Programming On a language: The design and language meet half way. This is programming into the language you wish you had; a language you build on the base language. Sometimes called Stratified Design.
    • Abstraction
      • Data abstraction: encapsulation, first-class types
      • Functional abstraction: first-class functions, closures
      • Syntactic abstraction: macros, overloading
      • Control abstraction: macros and high-order functions
      • Design process abstraction: abstract away files, deal with phases of project, explicit development process
      • Resource abstraction: separate what it takes to do it from what is done (See Open Implementation)
      • Storage abstraction: garbage collection, no new, slot access and function calls have same syntax
  • How to Write
    • (Literate programming vs. class-oriented/obsessed)
  • Specific Design Strategies
    • (Open Implementation; English Translation)
  • Metaphors: The Agent Metaphor
    • (Is agent-oriented programming the next big thing?)
  • Combining Agent Components

9. 杂项

• Agent-oriented: 面向方法
• Iterator的一个分支是Internal iterator，它接收一个callback，用递归遍历每个元素触发这个callback；缺点是无法同时遍历多个容器
• 宏的比较
  • C/C++: 文本替换(String substitution)
  • Dylan: 表达式替换(Expression substitution)
  • Lisp: 表达式计算(Expression computation)、语法变换
• 三种境界：
  • Programming in a language: 用语言提供的特性编程
  • Programming into a language: 语言没有提供的特性，人工模拟
  • Programming on a language: 在host programming language之上做一门DSL，然后以DSL编程
• 抽象
  • Data abstraction: encapsulation, first-class types
  • Functional abstraction: first-class functions, closures
  • Syntactic abstraction: macros, overloading
  • Control abstraction: Searching, Sorting, Filtering, Mapping, Combining, Counting.. higher-order functions