5.markdown

15. SICP，第3章，模块化、对象和状态

• 大纲
  • 引
    • 基本过程+组合+抽象，可能仍不足以克服大型系统的复杂性，有效的综合程序还需要一些组织原则，即将系统"自然的"划分为一些具有内聚力的部分，使这些部分可以分别的开发和维护
    • 组织程序的方式会受到我们对于被模拟系统的认知的支配
    • 两种特点鲜明的组织策略
      1. 将大型系统看成一大批对象，他们的行为可能随时间变化(行为受历史影响，即有状态)
         • 目标是，在需要扩充系统时，不需要做全面的修改，而只需要加入与这些对象获动作相对应的新符号对象。扩充和排错都只需要做一些局部性的工作
         • 在lisp中，需要抛弃代换模型(substitution model of computation)，改为机械、更不容易把握的环境模型(environment model of computation)
         • 在处理对象、变化和标志时，各种困难的根源是我们需要在这一模型中和时间搏斗。并发程序中，事情又会困难很多
      2. 类似电子工程师观察信号处理系统一样，将注意力集中在流过系统的信息流上
         • 能够解耦模拟真实时间时的各种计算顺序依赖
  • 赋值和局部状态
    • 局部状态变量
      • 所谓"有状态"，就是说，它的行为受历史的影响。在很多系统中，我们只维护当前值，而不是记住账户的全部历史
      • 如果一个系统中的状态变量可以分组，形成一些内部紧密结合的子系统，每个系统与其他系统之间仅存在松散联系，此时将这个系统看做由一些独立对象组成的观点就特别有用
    • 引进赋值带来的利益
      • 以复杂计算过程中的一部分的观点来看，其他部分都是在随时间不断变化的，而用局部状态模拟状态、用赋值模拟变化，可以让各个部分隐藏自己的变化，从而分解系统
      • 引进赋值和将状态隐藏在局部状态中的技术，避免了对所有状态进行显示的传递和返回，使得我们能更模块化的构造系统
        • 如果以纯FP的风格来组织这种复杂程序，恐怕所有的过程都必须传入和返回一个叫global的hashtable
    • 引进赋值的代价
      • 在代换模型中，一个ID，引用的是一个值；而在环境模型中，一个ID，引用的是一个存储位置
      • 关于别名(aliasing)：代换模型中，两个ID值相等和它们引用的是同一个对象，是一个概念，即不区分是否共享；在环境模型中，曾经相等的值的两个ID可能在之后不再相等，因为引用不同
        • 换句话说，在无赋值环境中，equal?为true，即可以认为是同一个对象；而在赋值环境中，eq?为true，才是同一对象
      • 引入赋值破坏了程序的引用透明性(referential transparency)
      • 不用任何赋值的程序语言称为函数式程序语言(functional programming)，而广泛采用赋值的程序设计被成为命令式程序设计(imperative programming)
      • 赋值顺序不同，程序的结果不同，因此带有赋值的语言强迫人们去思考赋值的相对顺序，确保修改作用在变量的正确版本上。这个问题在并发访问共享数据上尤为困难
  • 求值的环境模型
    • 求值规则
      • 引入副作用(赋值)后，一个S表达式中的子表达式的求值顺序变得重要，但我们不应该写出依赖于这种顺序的代码
      • 规则
        1. 求值一个lambda表达式，将会创建一个pair，它包括lambda的过程体和求值该lambda表达式的环境
           • lua中，出于优化考虑，function对象不会包含整个创建时环境，而只是捕获一系列的upvalue，具体的upvalue集合，是upvalues of this function + (upvalues of inner function - locals of this function)
        2. 调用一个过程，将创建一个新的环境，其中形参名字会规约到实参值上；这个新环境的外层环境是过程pair指向的环境，即创建该lambda时的环境
           • 该方案叫做lexical scoping；相对的，如果外层环境指向栈的外层，那么就是dynamic scoping
           • define这个spectial form，将会在当前过程的环境中添加一个新名字
  • 用变动数据做模拟
    • 变动的表结构
      • 如果能够通过FP或其他的方案实现组合数据的cons/car/cdr，那么，藉由set!，也能够实现set-car!/set-cdr!
      • 可以通过get-new-pair+set-car!+set-cdr!来实现cons
      • 注意append!，它将两个列表连接起来，避免了像append那样，创建length(list1)个新pair(特殊编译器的优化可能会导致append!更慢，因为要求mpair，但至少在racket目前的实现中，append!的确更快)
      • 创建循环链表，只能用mutable pair(或者stream)
      • 对一颗树调用count-pairs，如果没有赋值(immutable pair)，那么，一个pair绝不可能重复出现，因此简单的递归求和即可；但如果允许赋值，那么需要将mpair搜集到一个set中，最后求set的size
    • 队列的表示
      • 用一个pair保存list的头和尾，push即是对尾进行set-cdr!然后移动尾指针，pop即是移动头指针
    • 表格的表示
      • 使用(list key value item1 item2 ...)的方式，可以建立层次的多级hashtable。当然，这里的查询是O(n)的较慢
      • 在动态语言中，用memoization的手法将一个频繁调用且开销较大(大于查表)的过程给包装起来，配合一个hashtable做cache，是一种十分有效的优化纯函数调用的方法。是和DP对应的备忘录法的典型应用
    • 数字电路的模拟器
      • 连线是一个subject，当上面的信号变化后(0->1或1->0)，通过callback通知observer
      • 与或非门：监听输入连线，检测到变化后，注册一个时延的callback，在callback中计算并设置输出连线的信号
      • 连线和门->半加器->加法器->N位加法器
      • 这是第2章的图形语言外，又一次基本+组合+抽象的成功应用
    • 约束的传播(constraint propagation)
      • 一般来说，给定一个公式和一组变量，要求其中某个变量，必须先给出y=f(a,b,c)的数学公式，然后将公式转换为编程语言代码，这种方法要求工程师分别对每个变量都写一个求值过程。constraint propagation能根据提供的公式和任意一组变量，自动算出缺少的变量
      • 基本算子包括constant, adder, multipier等，他们会监听输入和输出的每个值，当n-1个值都被设置时，会自动计算出第n个值，进而通知其他运算子；当某个值被撤销导致已设置的值少于n-1时，它会撤销之前推导出的值
      • 通过connector连接各种运算子
      • 习题3.37，将运算子由过程风格改为表达式风格，即每个运算子以及运算子的复合都返回一个connector，代表一个表达式，这种方式可以足够精简、优雅的组合表达式。例如封装返回connector的运算子c+,c-,c*,c/,cv
  • 并发：时间是一个本质问题
    • 并发系统中时间的性质
      • 引入了赋值就引入了时间
      • 因为真实世界的对象一般是并发的活动的，所以我们将程序组织成具有相互分离的局部状态的对象，这样更加模块化也更合适
      • 并发的组织程序，可以利用多处理器的计算能力
      • 对并发的一种不太严格的限制是，要求并发系统产生出的结果和各个进程按某种顺序产生的结果完全一样
    • 控制并发的机制
      • 在lisp里通过parallel-execute提供并行执行的能力
      • 通过make-serializer创建一个serializer，它接收过程并返回一个新过程，该serializer返回的所有过程中，任意时刻只能有一个正在执行
      • 通过mutex实现make-serializer
      • 通过cas可以实现一个忙等待的mutex(除非再提供yield的能力)
        • 可以通过mutex实现semaphore
        • 可以通过cas实现semaphore
        • 在单核CPU上，cas只需要简单的实现为禁止线程调度(禁止clock interrupt)；而多核CPU中，cas必须是特殊指令
        • cas其实是在访问共享资源，当多个CPU核心通过cas访问同一个数时，缓存一致性的要求给硬件的实现带来了困难
      • 赋值->顺序->历史->时间->状态->并发时的共享->通信
      • 并发控制中，任何时间概念都必然与通信有内在的密切联系。时间和通信之间的联系也出现在相对论中，在处理时间和状态时所面临的计算模型领域的复杂性，事实上可能就是物理世界中的基本复杂性的反映
  • 流
    • 流作为延时的表
      • 如果着眼于函数在某个时间点的值，那么该值会随着时间变化；如果着眼于整条时间线，那么，它是不变的。流相对于赋值，就是从视角上，从关注当前状态转移到关注整个历史，至于完整历史引入的空间开销，流通过lazy evaluation来应对
        • 对于命名流，其空间复杂度是O(n)，这里的n，是最远访问距离
        • 对于临时流，优化解释器能够将其空间开销压倒O(1)
      • 赋值的问题在于变量的版本引用不一致，而流的解决方案，是给每个状态一个流，而每次迭代，会让所有的流同步更新版本，这就避免了版本不一致的问题
      • 流的优点
        • 流通过纯FP提供了一种递归更新整个程序所有状态(所有的流)的方案
        • 流通过lazy evaluation提供list的抽象，却只需要O(1)的空间(对于命名流是O(n))，因此可以高效的应用list最强大的map/filter/fold等操作
        • 利用lazy evaluation提供无限list的抽象
        • 流的模块性很好，根据现有流构造新流，无需修改已有代码
        • 流的lazy效应提供了通过define定义循环引用、引用晚定义变量的能力
        • 流提供了状态完整历史的访问能力，这是一般IP/FP不能直接使用的功能，因此可以用于实现特殊算法
      • 将lazy evaluation与副作用(赋值、IO)混用，是极其危险的编程风格
      • SICP中，stream-cons会将cdr部分封装成一个带cache的lambda，进行stream-cdr时才第一次求值
        • 如果这里的cdr不带cache，虽然也有lazy的能力，但在很多需要多次访问状态历史的算法中，可能开销很大
          • in-range流，有无cache无所谓
          • fibonacci流，有cache，复杂度是O(n)的；无cache退化成指数
          • primes流，无cache，由O(n^2)退化成指数
      • racket中stream-cons的car和cdr都是lazy的，这也是1976年friedman的论文中建议的：总是延迟求值cons的各个参数
    • 无穷流
      • 通过递归过程构造流
        • 例子：in-range，fib，primes(每个过程调用filter来过滤输入流，再递归)
      • 通过define变量来隐式定义流
        • 适用范围
          1. f(n)=p(g(n))：可以将f定义为g流的map/filter，这里的map/filter配合+-*/构成p
          2. f(n)=p(f(n-1), f(n-2)...)且f(0)=...：比如fib/integral流等，define成(stream-cons f(0) (stream-cons f(1), p(this)))，即先stream-cons结束条件，再在自身上做变换
          3. f(n)=p(g(n), f(n-1)...)：结合上面，利用stream-cons即map/filter等变换
        • 例子：ones, in-naturals, fib, primes(通过引用自身的过程prime?), integral
    • 流计算模式的使用
      • 普通的FP风格递归很容易写成无限流，再根据需要提取前n项或者第i项
      • 依赖于状态历史的特殊算法
        • 对于通过递归逼近来估值的算法，可以使用序列加速器来估值，很强大！
          1. euler-transform用于加速符号交错的级数，它应用于一个逼近流，得到一个收敛速度更快的流
          2. make-tableau递归的对输入运用transform，每一层将输入transform后传给下层make-tableau
          3. accelerated-sequence提取make-tableau返回的流数组的每个元素的首项，构成一个高速逼近的流，该流的第i个元素被应用了i次transform，需要basic流的i+k项已经计算(这里的k是transform依赖的项数)
      • join k个流，按一定顺序输出，相当于是以流的方式进行k层foreach
      • 将多个输入流join后，按权顺序输出(就SICP用到的算法而言，要求数对沿i方向和j方向都应该会权增大)
        • 例：将两个in-naturals流按(i+j)最小的顺序输出
        • 例：将两个in-naturals流按(i^3+j^3)最小的顺序输出，然后找相邻两项相等的值，即是ramanujan数
      • merge多个流时，至少应该保证交错输出，这样，如果其中一个流是无限的，也能保证另一个流完全输出
    • 流和延时求值
      • 通过define流具备lazy效果的能力，可以用来解决数学上就是交叉引用定义的问题。见p241~244
      • 关于lazy参数的讨论
        • 在lisp中，lazy参数只需要将调用时的实参给(stream xxx)起来即可
        • 过程的实参并不是在进入过程体时就立即求值，而是在执行过程的过程中按需求值，这样，可以实现特殊算法：调用过程时难以提供所有参数，随着过程的执行，附加参数被求出...(当然，没有lazy evaluation也能实现这种算法，只是lazy参数的方案给了一种自然的解法)
        • 虽然lisp是动态类型，但参数实际上可以是立即求值或者延迟求值，这样，每个形参都有两种选择，于是有k个参数的过程，其实就有2^k种选择，爆炸了，几乎呈现出静态类型generic的组合爆炸问题；一种选择是，在解释器层面让所有实参都lazy，但这就导致该语言的赋值/IO功能被限制
    • 函数式程序的模块化和对象的模块化
      • 虽然FP/流可以避免赋值中的顺序问题，但对输入的按真实序"归并"这一需求，势必强制性的引入时间概念，即使是在FP中
• 启发
  • 对于纯函数来说，相同的输入必然产生相同的输出，因此可以做cache、lazy evaluation、parallelism等
  • 蒙特卡罗法(mente carlo)：基于概率求值
    • 例，6/(pi^2)是随机选取两个整数之间没有公因子的概率
    • 例，用谓词P描述在一个函数内部(比如x^2+y^2<=1表示一个圆)，那么，用函数的包围矩形中随机的点通过P的概率，乘以矩形的面积，就可以得到函数在这个矩形区间中的定积分(integral)。这种方法叫蒙特卡罗积分
  • 引用透明性(referential transparency)：一个表达式用它的值替换过后，不会影响程序的结果。潜台词是，表达式没有副作用，即相同的输入总计算出相同的值
  • 别名(aliasing)：如果对一个名字的修改，可能由于副作用，影响到另外一个名字，那么，这两个名字实际上是同一个对象的别名。某些人建议说，程序设计语言中不应该允许副作用或别名。
  • racket中的mutable pair叫mpair，相应的有mcons/mcar/mcdr
  • 厄拉多塞素数筛选法，直到20世纪70年代，才被概率法的成果超过。另外它是公元前3世纪的希腊哲学家，由于第一个给出地球的圆周的精确估计而闻名于世
  • 练习3.59，幂级数可以用来算e/pi/sin/cos，通过他们的积分性质以及常数项，很容通过define引用自身的流来实现，经典！
  • p234, euler-transform用于加速交错级数，神技！
  • 所谓"随机"，即要求下一个输出和之前的输出无关，而random_update的恰好和这一个理念相反的，所以一定是伪随机的
  • 比较操作符，有数值序、字典序的分别，后者用于字符串顺序
  • 双向链表的典型实现：初始化一个dummy节点，首尾相连构成环；begin，即dummy->next，end即dummy。然后实现通用的insertBefore和removeAfter即可，无需做头指针的特殊判断
  • 单向链表能实现哪些ADT或算法？
    • 经典的单链表reverse法
    • stack：push: n->next=h, h=n；pop: h=h->next
    • queue
      • 法1: 用一个pair保存head,tail。push: tail->next=n; tail=n；pop: head=head->next
      • 法2: 保存tail，并且连接首尾成环。push: tail=insertAfter(tail)；pop:removeAfter(tail)
  • 在动态语言中(如lisp/lua/javascript/python)，memoize可以作为一种通用设施，透明的优化开销大、访问频繁的纯函数
  • partial application: 将过程f和将它的部分实参捕获成free variables后的那个closure
  • currying
    • currying最初是为了在只支持单参数的lambda calculation中模拟多参数过程
    • 原始定义: 对一个过程f进行curry，将返回一个新的过程(curried version of f)，它接收一个参数，返回f的绑定了第一个参数的partial application，这个partial application也可以是curried的。即，如果f有k个参数，curry返回cf后，可以cf(arg1)(arg2)..(argk)
    • 动态语言中，curry返回的curried procedure可以接收任意多个实参，只要累计的实参个数没有达到f的最小参数个数，那么curried procedure返回的仍然是curried procedure
      • 对于lisp/lua/javascript/python，可以这么用curry(sum4, 1)(2, 3)(4)
    • 静态语言中，由于过程的参数个数必须固定，因此curried procedure一次只能接受一个实参，k个参数需要调用k次
      • 对于c++/haskell，只能这么用curry(sum4)(1)(2)(3)(4)。由于在haskell中所有的过程都是curried，加上过程调用的syntax sugar，前面的调用和f(1, 2, 3, 4)等价
  • lisp中member, memq, memv是搜索value list；而assoc, assv, assq是搜索key-value pair list。就ADT而言，前者是list，后者是associative array
  • 对于在lisp中实现message-passing-style的OO，如果所有的调用点都直接传递message的symbol，那如果message签名不匹配，需要在运行时的dispatch时才能发现；如果每个message都wrap一个过程，那么，签名不匹配问题在调用点上就会发现。总结，将message-passing-style中的每个message包装上wrap过程后，更有利于静态分析
  • lisp中的stream是一种lazy evaluation的使用，曾经在algo 60上，也用call by name实现过lazy evaluation
  • haskell的表，lisp的stream，python的itertools，c#/c++的linq，都是一个东西：惰性求值的列表，即既提供list的抽象，又具有O(1)的空间效率
  • stream很适合用来表示数学上无限的定义
    • 如无穷级数，其值等于e/pi/sin/cos/tan等
    • 无限不循环的小数，即无理数。见练习3.58
  • 本章出现的几个非list的stream很难实现的算法
    • 练习3.56，汇合所有的只由2、3、5作为因子的数。用stream解及其经典！
    • 将输入join过后，按权序merge成输出
    • 逼近求值的加速器accelerated-sequence，其第k项是经过k次transform的结果。该解法严重依赖于历史，因此，连linq、itertools等其他lazy evaluation list都很难实现，只有stream实现得如此自然！
  • stream的lazy核心是stream-cons，因此，用递归过程构造流时，递归调用应该放在stream-cons中；如果一个子递归调用不在stream-cons中，那么它的递归深度应该有限
  • 流算法常用方案:
    • 法1, 生成无限流，每次take n。适合命名流，多次访问可以利用自带的cache避免重复计算。空间开销为n，但时间上避免了冗余
    • 法2, 每次生成长为n的有限流。适合临时流，避免了空间开销，但每次都需要重新计算
  • 截止目前SICP带来的新东西
    • 通过lambda实现message-passing-style的OO
    • 通过stream-cons实现lazy evaluation的list，比linq还多了历史状态的效果
  • 以流来组织程序，关键是给大部分的过程提供一个输入流作为参数。输入流可以是，用户事件流、随机数流、输入信号流等
  • partial application可以呈现两种抽象：
    1. 对象，输入可能改变对象的状态，从而相同的输入有不同的行为
    2. 纯函数，输入一定，输出相同。注意，如果是纯函数的抽象，那么过程体中一定不应该修改free variable！我之前实现的lua/python版本的curry就犯了这种低级错误，明明是要提供pure function的抽象，却修改了free variable，导致多次调用行为不同
       • memoize等特殊用法例外
  • curry因为每次调用时都需要concat实参和free variable，所以较慢；计算密集的大递归中尽量避免curry(比如qsort)

15. 杂项

• C++ project: 双向链表，只保存一个带环的dummy节点
• Lua project: memoize，用于加速dynamic programming对应问题
• Lisp/Lua/Python project: currying，curried procedure可以接收k个实参，如果达到f的参数个数要求，则调用
• C++ project: currying，每次绑定一个实参。variadic template起了大作用
• C++ project: MPL相关，typelist。variadic template起了大作用
• C++ project: bloom filter
  • 由于不存储key/value本身，因此无法提供map的抽象，只能用来表示集合，并且只支持insert/count，不支持遍历
  • 不存储key/value本身，每个元素只用k bit(这里的k是计算出的hash function个数，12已经是一个非常优化的数字了)，因此非常适合用来表示元素尺寸很大的集合，比如url、string
  • 总结，只需要支持insert/count的集合，并且集合元素尺寸很大，元素总数很多、空间占用很高时，考虑bloom filter
    • 典型引用: 网络爬虫算法中，表示visited urls的集合
• Lisp project: sort
  • 使用curry的quick-sort极慢
  • 比FP中经典的quick-sort快一倍的算法，同时能处理大量重复元素的特殊输入
  • 用mappend!连接两个串，果然比要求O(n)额外空间的append更快！(在racket中)
  • merge-sort很快。这里的关键是，怎样对无法随机访问的linked list进行按整数n分割
  • 我最快的sort只比c的qsort慢3倍，而qsort又比std::sort慢3倍以上...