4.markdown

1. 杂项

• 将C++/AlgoAndADT移植到windows下: 在windows下，我的quicksort超过了std::sort

2. 杂项

• 静态分析工具：cppcheck
  • cppcheck --enable=all --inconclusive --std=posix --std=c++11 --suppress=missingIncludeSystem .
    • 参数作用是：开启所有选项；包括不精确的猜测；不尝试分析以<>包含的系统头文件
• 静态分析工具：vs2013，编译选项/analyze
  • 只在vs2012+才有
• gcov，代码覆盖率分析
  1. 为g++增加编译选项：--coverage。等价于编译选项-fprofile-arcs+-ftest-coverage加上链接选项-lgcov
  2. 编译完成后，会生成*.gcno文件，里面记录了graph
  3. 运行程序，会生成包含每行运行次数的数据文件*.gcda
  4. 执行gcov main.cpp，可以逐文件的根据main.gcda生成main.gcov文件，后者是记载了每行执行次数的文本结果
• 函数memchr
• 注意RLE压缩（游程压缩）可以确保压缩率几乎总是小于1。即，除压缩块的标记字节外，其他字节总在重复4次以上时才压缩
• ANSI C中的标准类型（char/short/int/long）尺寸未定义，char甚至符号未定，皆因制定标准时，各编译器差异实在太大，如果强制统一标准，会破坏各平台下大量现存代码，故标准向现实妥协

2. Writing solid code，第1章，假象的编译程序

• Knuth号称在1985年11月27日其TEX就bugfree，并承诺给发现bug的人高额奖励...他凭什么对他的程序有那样的自信？？？bugfree的窍门在哪里？
• 开启编译器的所有警告
• 使用lint等静态分析工具，作为对编译器警告的补充
• 进行单元测试

2. Writing solid code，第2章，自己设计并使用断言

• 使用断言验证函数的precondition（形参）
• 给复杂的断言添加描述信息，不要浪费维护者的时间
  • 经典的例子：驶进森林的车看见路边立着一块牌子“危险”。是什么危险？怎样防备？
  • 程序员不能理解的断言会被忽视，或者他们可能会认为断言是错的，从而去掉以使程序继续运行
• 使用断言时，区分逻辑错误和运行时异常，后者应该是容错而非断言
• 不要使用行为未定义的语言特性，如果用了的话，使用断言来确保假设成立
• 对实现或运行时条件进行的假设，用断言来确保成立
• 用断言来保证不可能发生的情况
  • 如switch(enum)的default分支
• 运行时异常发生后，哪怕进行了容错，也应该再记日志，决不能默默的吞掉事件
• 为一个算法提供多个实现，用缓慢但简单正确的算法来验证复杂算法
• 编写程序状态一致性检查的程序，在问题暴露之前就检测到错误

2. Writing solid code，第3章，为子系统设防

• 在模块间接口处进行验证，可以最容易的发现各种错误
  • 一个经典的比喻：足球场可以容纳50000的球迷，而检票员只要站在入口处就够了。对于程序来说，这样的入口就是模块接口
• 消除随机性，使错误可见
  • 提供机制，使得随机数发生器总是返回固定的序列，于是问题可重现
  • 让栈、堆初始化成利于调试的默认值，更容易发现使用未初始化变量的问题
  • 释放堆后，将堆置为默认值，有助于发现dangling pointer（悬空指针）的使用
  • 在堆的最后增加一个guard字节，释放内存时检测guard字节值是否有变化，用来发现内存写越界的错误
  • 有可能发生的事件，试着让它总是发生。如realloc的内存移动或失败
• 为子系统提供内部状态一致性检查的函数，最好这样的检查是透明的，即使项目的新成员不知道，检查机制也在生效
• 在调试版程序中，用时间和空间来换取错误检查能力

2. Writing solid code，第4章，对程序进行单步跟踪

• 开发完毕后，一定用行覆盖工具确保程序都执行到
  • 一个缺乏覆盖的典型错误：程序员修改代码后，输入一组数据，查看输出正常，就commit代码；事后发现bug，原来新添加的代码根本没有被执行
• 行覆盖的方法
  • C++等语言可以用gcov扥工具
  • 脚本语言等工具链较弱的环境，用类似HERE(predicate)的宏或者函数来确保代码执行，执行过后再去掉
• 异常极少发生，因此异常处理代码很难被执行、测试到，必要的时候需要模拟异常
  • 比如让malloc总是返回NULL
• 一些常见错误:
  • 算数运算造成上溢下溢
  • 数据类型转换溢出
  • off-by-one
  • NULL指针
  • dangling pointer或多次free
  • 错把==写成=
  • 运算符优先级错误
  • 逻辑错误
• 单步跟踪的时候，密切观察上下文的数据流
• bug代码或性能关键代码，可能需要在汇编级进行单步

2. Writing solid code，第5章，糖果机的接口

• 单独返回错误码或者抛出异常，让用户不容易忽略错误情况
• 不用仅仅因为汇编或C语言不支持多值返回和异常，就心存侥幸的将错误码混入输出数据的空隙域：错误码做返回值，输出数据用out参数
• 不要编写包含多个功能的函数，将功能拆解成正交的多个函数后，才能正确的测试和断言输入
  • 多功能函数的参数太随意，它可能隐藏用户失误；而功能单一的函数会在用户失误的时候断言
  • realloc，包含了grow、shrink、malloc、free四个功能，是个万能函数，参数永远都合法，是典型的错误的设计
• 严格的输入比宽松的输入有更好的向后兼容性，如果将来发现过于严格可以进一步放宽限制，但反之不成立；因此，在最开始就最大限度的用断言限制输入
• 最理想的函数是总是成功的函数，因为错误处理总是困难的，因此，总是尽量尝试提供不出错的接口
  • 例子，tolower
• bool参数是不可读的，调用点处无法判断true/false对应的语义；因此bool参数往往说明设计者没有深思熟虑，要么拆分成两个函数，要么将0/1扩大成枚举域
• 总是提供易用的设计，如果实在没办法，那么在API文档中提供用例，避免误用
  • 如MSDN/man中的strtok

2. Writing solid code，第6章，风险事业

• 经常问自己，刚刚编写的这个表达式会上溢或者下溢吗？
• 在标准约束内编程
  • 曾经Microsoft的程序员，认为编译器团队不会破坏自家代码的向后兼容性，因为放心的假设int是16位，然后某一天因编译器团队迫于市场压力升级编译器，大量代码被毁掉了
• 需要查运算符优先级表的时候，直接使用括号
• 优先选择不会失败/报错的方案

2. Writing solid code，第7章，编码中的假象

• 只访问属于你的内存
  • 比如，memchr的实现者在end[0]处放置哨兵来加速循环，结果end[0]属于其他进程（实模式）/被多线程访问/被中断处理程序访问/是文件映射的末尾/是特殊的IO映射端口，结果程序crash得很惨
  • 上例是访问越界，类似的，还有非法访问权限，比如，在strchr中写输入的只读内存，以放置哨兵，而该段内存其实被多线程访问/是只读程序段，程序异常...
  • free过后的内存决不能读写。free过后的内存被怎样使用，取决于具体allocator的实现，比如被串入freelist，设置next指针
    • 典型错误如释放链表时，free(n)后再n = n->next
  • 一个错误案例:
    1. int i = 0, j = 0, k = 0;
    2. 想优化成：int i, j, k; memset(&k, 0, sizeof(int) * 3);
    3. 错误1：视编译器不同，i, j, k可能不连续；错误2，如果函数够简单，编译器甚至可能尝试将i, j放到寄存器中（由于&k，k肯定会放栈上）
• 分清接口语义和具体实现
  • 一个典型的错误案例
    1. copyFromHead: while (size-- > 0) *dest++ = *src++;
    2. fill: buf[0] = c; copyFromHead(buf, buf + 1, size - 1);
    3. 初衷是，copyFromHead用汇编实现，fill就可以用C实现
    4. 放在今天，这种写法会很慢，因为data dependency，写了马上要读；更重要的是，因为copyFromHead的实现可能一次拷贝多字节，故当size较大时，fill是错误的
• 为项目的维护者编写代码
  • 不要像律师写合同那样写代码

2. Writing solid code，第8章，态度问题

• bug从来不会主动消失
• 马上处理bug，不要推迟到最后
  • 把bug压倒最后来处理，会给产品部门一种项目进度异常顺利的错觉，从而高估进度
  • 最后的时间来处理囤积的bug往往士气不振，压力很大
  • 修复很久以前的代码造成的bug，更困难
  • bug修复得越早，重复出现的可能性就越小
  • 产品的时间不会被压缩，但是测试和debug的时间可能被压缩，因此，最后来处理bug可能导致产品测试不充分
• debug要治本，不要治表
  • 发现问题时，尝试找出本质原因
• 再简单的改动，也必须经过测试来验证
  • 一个案例：修改了局部变量名，结果导致全局变量被隐藏，程序错误
• 不要提供没有必要的自由度，灵活的设计并不总是好的，不必要的灵活性可能掩盖错误，是bug的温床
  • 如realloc
  • 记住，灵活不等于易用
• 试一试是个忌讳词，更应该花时间找到真正正确的方案
  • 不要靠巧合编程
  • 与其测试可能解，停下来，去查手册
• 尽可能编写和测试小块代码，让代码总是处在健康状态
• 测试代码的责任不在测试员身上，在程序员自己身上
  • 比起白盒测试和程序验证方法，黑盒测试不可能更好，前者更彻底
  • 不要依靠测试员来测试，这不是他们的工作
  • 程序员从里向外测试，测试员从外向里测试
  • 经典比喻：
    • 建房时，检查员只是检查，电气工程师虽然不会亲自去安装电线，但绝不敢在没有接通电源、没有经测试保险盒、没有用万用表检查每个出线口的情况下就交付线路。如果他这么做，他将找不到工作
• 测试员发现bug时，你第1反应应该是震惊，第2反应应该是感激
  • 永远不要抱怨测试员提交的bug"太愚蠢"，他们的责任只是报告所有错误，而不是判断严重性和推测错误之间的关联性
• 不要寄期望于靠测试员发现bug，这种软弱的想法和bugfree的目标是背道而驰的

2. Writing solid code，后记

• 决不允许同样的错误出现两次
• 如果你的小组中有人一再编写劣质代码，让他改正，或者让他离开；你没有必要让这样的代码给你、给你的产品带来麻烦

3. 读Writing solid code后对bugfree编程的总结

• 开发流程
  1. 编译器警告全开的情况下应该无warning
  2. 用lint和cppcheck等静态分析工具找问题
  3. 用gcov等行覆盖工具或者在无工具的情况下用HERE(predicate)函数来确保语句执行
     • 为测试错误处理代码，可能要想办法模拟失败情况
  4. 断言和程序验证技术
     • precondition、postcondition、class invariant:
       • 模块接口，用release版有效的r_assert，因为这里涉及沟通成本和闭源的情况
       • 普通接口，用assert即可
     • loop invariant: 用assert，因为性能方面的考虑
     • 假设验证:
       • 编译环境假设，如实现依赖或标准未定义行为，用assert或static_assert
       • 系统环境等运行时状态假设，用r_assert
     • 系统调用或输入校验失败: 用ENSURE，抛出RuntimeException
     • 复杂算法，编写内部状态一致性检查函数，用于第一时间发现错误
  5. valgrind等工具确保无内存泄露和非法内存访问
  6. 单元测试
     • 测试用例
       • 逻辑接口: 在Mock的帮助下，写测试代码
       • 算法接口
         • 可能需要从文件读取测试数据进行数据驱动的测试
         • 为一个算法提供多个实现，其中简单但缓慢的实现用来验证优化版算法的正确性
     • 清晰定义模块间的依赖关系，支持按照拓扑顺序逐个测试匹配pattern的模块
  7. 集成测试和系统测试
  8. 依赖于QA部门的黑盒测试
• 调试辅助
  • 消除随机性
    • malloc的内存初始化为默认值，用于发现访问未初始化的变量
    • free的内存置为默认值，用于发现引用dangling pointer
    • malloc的时候在块的尾部追加标记字节，free的时候检测标记是否变更，用于发现内存写越界
    • 让可能发生的事件总是发生，而不是随机发生
      • 如realloc移动指针或返回NULL
    • 随机数发生器能够生成固定的随机序列
    • 录制包括网络、用户操作在内的所有输入，支持重放以重现bug
  • 单步的时候，密切关注上下文中的数据流是否正确
• 接口设计
  • 要么单独返回错误码，要么抛出异常，让用户很难忽略错误
    • 不要投机的将错误码放入输出值的空隙域内
      • 比如malloc错误的时候返回NULL就是个设计错误
  • 最理想的函数是根本不报错
  • bool类型的参数是错误设计
  • 接口功能要单一，便于测试
    • 万金油接口很容易掩盖用户的过失，做与用户意图相悖的事
  • 严格限制输入，将来才有放宽的余地
    • 灵活不等于易用
  • 分清接口和实现，不要依赖于实现
• 态度
  • bug不会主动消失
  • 不要治表要治本
  • 立刻修复问题，不要囤积到最后；后者会磨掉士气以及给外界进度过于顺利的错觉
  • 比起尝试可能解，去查手册！
  • bugfree应该是程序员的目标，而不是QA的责任
    • 被QA发现bug，一是要吃惊，二是要感激

3. 杂项

• C Project: C99ADT, 本次添加的接口包括list, linkedList, BST, hashTable

4. 杂项

• C++ Project: Memory pool test。基于链表的快排序，想比较一下普通的malloc和基于内存池的链表节点性能差距
  • 32位下每个节点占内存8字节，因此32K的L1 cache能放4K个节点，因此，期望在2K~4K的时候，观测到内存池链表大大快于malloc链表，因为顺序访问所以池链表的cacheline是100%利用，而且因为没有分配器的fragmentation，所以只有池链表才能放入cache
  • 令人失望的是，没有观察到期待的差距。猜测原因：链表的n = n->next是高度data dependency的，会stalling掉pipeline，所以，此时L1和L2的差距不再突出
• 总结下链表比数组慢的原因：
  • 需要内存更多，cache的capacity miss更严重
  • access pattern不连续，访问相邻节点的时候可能在内存中乱飞，spatial locality差
  • 访问相邻元素依靠n = n->next，data dependency严重，ILP差，跟数组相比流水线利用率低

6. 杂项

• C语言中，x/y在结果为负数的时候，行为未定义，可能floor也可能ceil。
  • 想要对x减1同时对y取模，想避开负数，一种做法是(x - 1 + y) % y，但注意括号内容可能溢出
  • 标准定义的内容是：
    • x = (x/y) * y + (x%y)。因此，如果x/y是floor，x%y是正；如果x/y是ceil，x%y是负
    • 当x/y结果为正时，floor。此时x%y总为正
• C/C++中不要使用下划线开头的标识符，因为可能保留给标准或编译器
• main返回或exit的参数:
  • 成功：EXIT_SUCCESS或0
  • 失败：EXIT_FAILURE。像-1这样的值是不可移植的，部分系统可能把它当做成功
• C语言中的class-storage-specifier
  • auto(默认)，可能被放置内存或者寄存器中
  • register，应该被放置在寄存器中。编译器试具体寄存器分配策略，可以忽视，即实现层面可能等价auto
  • volatile，总是放在内存中，不在寄存器中缓存
• assert应该实现为void类型的表达式
  • 例: #define assert(b) (void)(b || fprintf(stderr, "%s(%d): assert failed: %s\n", __FILE__, __LINE__, #b))
• 编写RETURN宏注意应该允许后面接参数。可能的做法是宏的最后是一个真正的return
• callback+context常用来作为回调方案，这其实也就是closure
• 实现一个Allocator至少应该提供以下调试帮助
  • 未定义变量的使用：将malloc返回的内存初始化成固定值
  • Dangling pointer的使用：将free的内存内容置为固定值
  • 写越界：free时检测末尾字节有没被覆盖
  • 释放非堆内存：free时检测指针是否是Allocator分配的
  • Double free: free时将内存置为freed状态，如果发现free的参数是freed状态而非allocated状态，即为double free。当然，该法可能漏检查
  • Memory leaks：退出前检测是否有没释放的内存
  • 其中Dangling pointer相关的bug（包括double free）可以通过#define FREE(p) (free(p), p = 0)来避免
• 怎样保证迭代期间容器不被修改？
  • 所有写容器操作内部都会进行++c->version
  • 创建迭代器时(begin调用)进行it->version = c->version，迭代结束时(比如析构)进行assert(it->version == c->version);
• 求两个集合的交际，应该遍历较小的集合，然后搜集小集合中每个出现在大集合中的元素。换句话说，求交集的第一件事一定是找出小集合
• 集合的表示方法
  • std::set
  • Bitset: 在全集较小的情况下，通过在一个character map中进行binary search或者table lookup，将一个字符转换成[0, n)的整数索引
• 为何strcmp等cmp函数设计成(-1, 0, 1)三种状态，而不是(<0, 0, >0)？
  • 避免使用者简单的进行a - b，该方法会溢出
• 稀疏容器(如sparse matrix, sparse array)，往往在构造的时候要指定默认值。实现上，可以只将非默认值的(k, v)存储进hash表
• 在实现层面，c99的VLA其实就是指针，即int a[n]其实是int *a = alloca(sizeof(int) * n)。但是语义上却必须表现得和数组一致，包括sizeof(a) == n * sizeof(int)哪怕只能在运行时计算
• 计算一个int中有多少个bit 1，相比采用256的表查4次，用16的表查8次也不错，因为后者整个表都可以放在一个cacheline上
• 带参宏可以用(MACRO)来阻止替换。如
  1. 有两个定义static int ADD(int a, int b) { return a + b; }和#define ADD(a, b) ((a)*(b))
  2. (ADD)(2,3)结果是5，而ADD(2,3)结果是6
• GCC上的对齐规则有点特别：
  • sizeof(T) < 4以sizeof(T)对齐
  • sizeof(T) >= 4都以4对齐。VC没有这个特例，似乎CSAPP上提过GCC的这个曾经的设计错误
• 计算T的对齐:
  • int alignOf() { struct Help{ char c; T t;}; return (long)&((Help*)0)->t; }
• 一种简单hashing算法:
  • 生成256个[0~4G]的随机数，然后遍历输入的每个字节，以h = (h << 1) | ranBuf[input[i]]的方式组合起来
• 计算平台的最大alignment，可以作为实现malloc的对齐参考(因为linux最大对齐只是4，因此下面这个也满足)
  • union MaxSize { char c; long l; long long ll; double d; long double ld; void *p; void(*f)(); };再取sizeof(MaxSize)
• Skiplist除了提供map的接口外，也可以提供array的接口，优点是中间插入、删除无需memmove以及增大时无需realloc
• C++ project: 比较了基于链表的quicksort，比数组的只慢了50%不到，仍然快于ANSI C的qsort(后者还再慢50%)，看来访存影响没函数调用影响大
• VC对c99的支持很差，甚至在VS2013中将文件当C编译，仍然不支持VLA
• LLVM的字符串技巧：
  • StringPool: 用intern来减少大量字符串时的内存占用。每个PoolStringPtr是基于引用计数的，不用的时候会将自己从Pool中移除，当然，Ptr之间进行equal、hash也很快
  • StringRef: 不可变的字符串引用，含常指针和长度。大量字符串查找、取子串的算法都是基于它，substr、split等算法都返回StringRef
  • Twine: Rope的一种，栈上的临时对象，用于将const char*、string、StringRef等连接成表达式树（虽然只有+节点），供之后render到buffer中，从而达到高效的进行concat的目的。
    • C++11中因为有了右值引用，string(lit1) + lit2 + lit3 + lit4这样的表达式能够通过右值引用高效的append，无需Twine了
• #include "..."的查找规则：先查找当前目录，然后再按照-I的顺序查找

7. 杂项

• std::map只要求less，是因为，insert/find的时候，它利用loop invariant来进行< value: n = n->left; >= value: n = n->right的下降，道理和lower_bound有点类似

8. 杂项

• 字典
  • 静态字典：一旦创建不再修改。ordered_array+binary_search
  • 半动态字典：只支持insert和find，不支持remove。open addressing hashtable
  • 动态字典：chaining hashtable
  • 动态字典+min/max/to_ordered_array/kth_element: rbtree, skiplist
• 编写各种Allocator的时候，一定要考虑对齐问题！
  • NodePool: 一般N都是sizeof(T)，而Chunk又是PAGE_SIZE对齐的，因此一般不需要额外考虑对齐问题
  • StackPool: 考虑对齐问题后，分配不再是简单的p += size!
• C++ project: compaction with handle
  • 通过Handle来代替指针，从而具备compaction的能力，希望看到比raw pointer更好的性能表现。可惜只比raw pointer快一点点。另外为了追踪size/align信息和维护handle manager，每个alloc的overhead`都很大(16~20字节)
• C++ project: range，在C++11中提供类似python的用法，彻底避免手写循环
• C++ project: STLAllocator, 包括stack内存池和freelist内存池，分别用于临时对象和持久对象
  • freelist：当allocator要求元素个数大于1时，从::malloc分配
  • stack：当总申请大于PAGE_SIZE时，从::malloc分配

9. 杂项

• C++ project: findMaxPrime, 用来查找2^i下最大的素数，从而用于hash表rehash时的尺寸
  • 费尔马小定理: 素数p，[1, p)的数a，应该有(a^(p-1))%p==1
  • 这里判断p是否是素数，就是随机10~20个a，然后检测是否(a^(p-1))%p==1
• C++ project: StringIntering.OpenAddressingHashtable, 因为loadfactor控制在不超过0.5(此时clustering不严重; 如果为省内存，loadfactor接近1，可能就需要二次探测或double hash了)，而且不会有删除，因此用的线性探测法
• C++ project: Random, 线性同余随机数发生器
  • N(i+1)=(A * N(i)+C)%M: 常见的M是2^32
• C++ project: ADTAndAlgo.hash.h实现ChaningHashtable和OpenAddressingHashTable

11. 杂项

• CMake的使用

12. 杂项

• bitwise op: 按位操作
• false sharing: 又叫cache line ping-poinging，指多个线程访问同一个cache line，其中一个的写操作会导致另一个core的L1 cache失效
• bitfield的写操作是read+bitwise op+write的组合，是非原子的，因此存在race；这和int的写不一样，后者是原子的

13. 杂项

• Python project: UniqLineCounter，对一个目录下的所有文本文件的行，计算md5，然后统计独立的md5个数，由此得到源码的非重复数
• Polish notation, Reverse polish notation: 分别是前缀和后缀表示法
• Scoped hashtable: 考虑嵌套作用域的变量名查找，最简单的是沿着栈依次查找嵌套hash表; 优化的实现是，以pair<name, scopeIdx>作为key，只查一次表，当然，插入、查询的规则都需要定制
• C++ project: Channel, 两种实现方法。测试是流水线的primes gen
• C++ project: 只用O(n/2)临时空间的mergesort

14. 杂项

• C++ project: BigInteger

15. 杂项

• C++ project: BigInteger, 优化
  • 将乘法从O(N^2)优化到O(N^1.5)，运用高斯用3次乘法代替4次乘法的办法
  • 优化toString，每次处理(sizeof(T) * 8) / log(base)位
• C++ project: ADTAndAlgo, 用100多行实现了个最简的BigInteger，支持add/mul/tostring

16. 杂项

• std::string的c_str()无法提供可靠的writeable buffer（比如，COW的实现就不可写），但是&str[0]可以
• C++ project: bigInteger2, 完全重写。可惜性能没有提高。fromString采用了类似于toString的分块读取法，快了几倍

17. 杂项

• Python project: 重构UniqLineCounter, 参数列表可以是文件或文件夹; 如果参数列表为空，处理标准输入的行
• C++ project: base64, 高品质的实现

18. 杂项

• C++ project: Hashlib, 今天实现了Md5/Sha1/Sha256, 性能和md5sum/sha1sum/sha255sum相当
  • 注意，这三种hash算法，hash的内容是数据+sizeof(数据)，即它们会把数据的长度追加在内容后面一起hash，这样更有效的避免了碰撞
• 编译期交换变量的方法
  • 对于处理海量数据的算法，如果算法中需要交换几个变量的值(比如Md5等算法中的128位向量循环右移32位的操作)，可以仅仅是在算法的稍后部分交换源码中变量的名字，从而省掉拷贝的开销
  • 具体方法:
    • 原始算法:
      1. step1 = f1(a, b, c, d); swap(d, a, b, c);
      2. step2 = f2(a, b, c, d); swap(c, d, a, b);
      3. step3 = f3(a, b, c, d); swap(b, c, d, a);
    • 将f1/f2等操作改写为以变量引用做参数的inline函数或者宏，然后:
      1. step1 = F1(a, b, c, d);
      2. step2 = F2(d, a, b, c);
      3. step3 = F2(c, d, a, b);
  • 真实例子:
    • Md5/Sha1/Sha2中的多个变量循环右移(128/160位变量)，仅仅是交换变量名; 这几个hash算法中，循环展开，交换变量名的同时，还进行了表格内容的立即数嵌入等优化

19. 杂项

• C++ project: CRC32
• C++ project: RLE压缩

20. 杂项

• C++ project: Huffman压缩，其中有一对高效的InputBitStream/OutputBitStream类很好用

21. 杂项

• 字节顺序
  • 不管CPU内部字节序如何，它在ISA这一层提供的抽象一定是符合自然顺序的，因此，在各种CPU上，0xfa12的低16位都是0x12。换句话说，寄存器总是数学顺序的
  • C/C++中，所有整形的算数、位运算，都是自然顺序的，因此，i&0xff总是等于i%256。字节顺序问题只发生在寄存器和存储器之间传输的时候
  • 例子:
    • python实现longobject的时候，使用&MASK和>>SHIFT来进位，这是正确的，因为C语言保证在这些运算面前变量总是符合数学概念；当然，其中words数组的字节顺序则是可变的了
    • md5在最后添加数据length的时候，采用little endian，显然这里需要根据CPU适配顺序
    • 实现bitstream，平时用uint8_t存储，偶尔需要fetch<int32_t>，这里就需要确保按litten endian来操作，否则语义错了
• C++ project: lzw, lz77压缩，都很高效，压缩可以几十M/s，解压可以上百M每秒
  • 在hashtable的使用上一个确认影响到性能的地方: lzw在压缩的时候使用的是整串的hash，因此bucket size选择2^n-1没问题；但lz77使用的是头4个字节的hash，结果很多slot的链太长，使用素数作为bucket size后，有效的让分布更均匀，提高了效率！

23. CSAPP 第2版

• 并发和并行
  • 线程级并发(TLP): 从分时系统(time sharing)开始就出现并发，但是这种并发是由OS模拟出来的(进程、线程)；直到多核和超线程(hyperthreading)，才实现真正的并行
  • 指令级并发(ILP): 现代处理器可以同时执行多条指令的能力，即流水线。如果处理器可以通过多条流水线达到一个周期处理多条指令，就是超标量(superscalar)
    • 阻碍ILP的两个相关性: 数据相关性导致的data hazard和控制相关性导致的control hazard，前者通过forwarding和stalling来应对，后者通过branch predication应对
  • SIMD: 一条指令执行多个并行操作。如SSE和AVX
  • 超线程(hyperthreading)，允许一个CPU执行多个控制流，它涉及CPU的某些硬件单元有多个备份，比如program counter和register file，而其他硬件单元只有一份，比如执行浮点算数运算的execution unit。OS级的上下文切换可能需要20000个cycles，而hyperthreading只需要1个cycle，这样，当核心上的一个线程在等待数据从cache中load的时候，另一个线程可以执行。core i7有4核8线程
  • 模拟并发是需要的(thread和process)，即每核心超过一个任务是需要的，因为CPU比IO设备快，如果每个核心只有一个计算任务，那么一旦遇到IO，CPU将等待，这浪费了处理器的计算能力
• 为对抗缓冲区溢出攻击，编译器和OS做了一下措施(对用户程序透明)
  • 栈随机化：每次程序启动后，第1个栈帧的基址都在变。最新的版本的linux中, int main() {int i = 0; printf("%p\n", &i); }的输出每次都会变了
    • 更大的一类技术叫，地址空间布局随机化(address-space laytout randomization)，即所有程序段、代码段、数据段地址都会变，因此局部变量、全局变量的地址都会不同了，当然生成的代码也应该是PIC的
    • 执着的攻击者采用nop sled来攻击，即将很大范围的地址空间填成nop，一旦跳转到其中，即滑落到最后的攻击代码
  • 栈破坏侦测(stack protector)：最新的GCC会在栈上buffer与栈帧状态数据之间插入guard value，执行写buffer操作后，如果检测guard value有变，即被攻击。该值是程序每次运行时随机产生的，无法预测。对应的GCC选项是-fstack-protector
  • 限制可执行代码区域：新的处理器在虚拟存储器系统中的页表上提供了执行标记，一般来说，栈是不可执行的。JIT需要内存具有执行标记
• x86-64
  • GCC在生成32位程序的默认条件下，只会用i386指令集，而不会使用95年以后的更新指令，这是出于兼容性的需要(优化选项开得够高的话...)
  • x86-64诞生的动机、过程
    • 动机
      • 1985年i386出现以后，RAM增大了512倍，disk增大了10000倍，CPU快了1250倍，在硬件进步如此大的情况下，编译器生成的代码还是85年的i386兼容的，这不足以彻底发挥硬件性能
      • 32位寻址空间的4G内存已经不够用了
    • 过程
      • 2001年intel推出IA32的升级版IA64，它是从头开始设计的一套指令集，只能以兼容模式运行IA32的代码，很慢。市场反响不好
      • 2003年，amd抓住intel的在IA64上的失败，推出x86-64，意思是兼容x86的64位扩展。完全向后兼容，更强更快。后来将x86-64更名为amd64
      • 2004年，intel意识到不可能靠IA64替代IA32了，于是推出x86-64的变种，称为IA32-EM64T(enhanced memory 64-bit technology)。后更名intel64
      • linux和GCC统一将amd64和intel64称为x86-64，而将IA32叫做i386
  • x86-64的特点
    • 指针和长整数是64位
      • eax,ebx等通用寄存器扩展到64位，叫rax,rbx
      • C语言中的指针、long都是64位了
    • 通用目的寄存器从8个增加到16个
      • 8个新的寄存器叫r8~r15。它们的低32位、低16位、低8位分别交r8d, r8w, r8b
      • 更多寄存器减少了register spilling的可能，从而提高性能
    • 尽量将程序状态保存在寄存器中而不是栈上。函数调用从栈密集变为寄存器密集
      • 函数的前6个参数使用寄存器传递
      • 每个函数可以访问超过rsp的128字节空间，这样，临时变量有限的函数完全不需要移动栈指针了
      • rbp不再用作基址，没有特殊意义，局部变量访问改为基于rsp
    • 使用更优的指令
      • cmov的使用
      • 提供PIC的寻址方式: imm(%rip, idx, scale)
      • GCC在IA32下，默认对齐是小于4字节，按2对齐；大于等于4字节，按4对齐，在x86-64中，和MSVC一样，按sizeof(scalarType)对齐了
    • 浮点操作用SSE指令集替代x87指令
      • x87浮点指令集的一个明显缺点是，8个寄存器形成一个小栈，它们作为一个整体是caller save的，函数调用之前必须刷到栈上(尽管也可能是callee save，但总之必须作为整体将8个寄存器压栈，很浪费)
      • GCC下提供80位精度的long double，不再是硬件支持的了，因此，在x86-64中使用long double没有性能优势
• 第5章，优化程序性能
  • 编写高效程序的几类活动
    1. 选择一组合适的算法和数据结构
    2. 编写编译器能够有效优化的代码。需要理解编译器的能力和局限性，C语言的指针算数运算和强制类型转换都妨碍优化
    3. 当数据特别大时，划分任务，利用TLP优化
  • inline过后，procedural side effect的optimization blocking效应没了，从结果上过来说的达到了过程间分析的效果
  • 最小2次方拟合(least squares fit)
    • 对于O(n^k)复杂度的算法，尝试找到k阶系数的f，使得sum((yi - f(xi))^2)最小
  • loop-invariant code motion
    • 以函数调用作为循环截止，导致编译器无法进行code motion的一个理由是，loop body的写操作可能导致循环上界改变，因此如果上界函数过于复杂，编译器无法充分分析，则无法安全的做code motion
  • 由于branch prediction的存在，循环内的range check开销可能不大
  • 注意指针引入的memory aliasing导致优化困难。C中的关键字restrict可能有用
  • 超标量是out-of-order的，它有两个主要部分，指令控制单元(instruction control unit)和执行单元(execution unit)
    • ICU通过retirement unit和register renaming来处理分支预测，对于流水线前端的指令，他们的输出结果被renaming到其他临时寄存器，供后续指令引用，如果分支结果预测正确，那么这些临时结果生效，即retire，如果预测错误，则被扔掉(flush)。register renaming其实很像数据的版本号
    • 指令的两个指标，latency和throughput，其中throughput的倒数是issue time。对于issue time为1的指令，称为完全流水线化(fully pipelined)，比如整数、单精度浮点的+-*，ALU中往往有多组它们的EU，而除法需要大量的硬件单元，直到上一条除法指令几乎完成的时候，下一条才能开始，它的issue time很大(10~20个cycles)
    • latency和issue time分别定义了操作的下界和上界，对于data dependency重的算法，后续的指令可能需要stalling直到前面的操作完成，因此latency是主要指标，而如果数据相关性不强，操作几乎可以并行执行，那么由于ILP的关系，issue time会成为主要指标，即load/add/mul等只需要1个cycles，只有div由于issue time很大，需要10+个cycles
    • 除法的latency和throughput有一定浮动，具体情况因输入数据而异
  • reassociation transform: 重结合变换，利用运算的结合性，降低data dependency，提高ILP，效果类似loop spliting
    • 降低data dependency过后，能让操作时间由latency向issue time靠拢
  • loop spliting和reassociation transform都要求运算满足结合性，所以对于整数+- * ，编译器能自动进行，但是对于浮点数，由于精度的缘故不支持结合律，所以编译器不会自动进行这些优化。(可能开启-ffast-math或者-Ofast能行)
  • 现代CPU上一个load至少要1个cycle，因此，如果loop body中有两个访存操作，那么CPE(cycles per element)不可能低于2
  • 同样save操作的CPE也不可能低于1
  • write/read dependency: 下一条指令需要读取上一条指令写入存储器的值。这要求读操作检测save unit中是否有被cache住还没写入L1的数据，如果有，必须等到它们刷入L1才能去读，否则可以直接读L1，因此write/read dependency会导致更慢
  • 一些限制性能的因素
    • register spilling。x86-64相比IA32好了很多
    • miss penalty
      • 对于core i7来说，是44个cycles，即，对于无规律的分支，平均penalty是22个cycles
      • 不要关注可预测的分支
        • 比如迭代的结束条件，它总是成功直到最后退出的时刻才预测失败
        • 真正不可预测的是数据驱动的循环中的条件判断，它的命中率往往只有50%
      • 编写条件传输形式的代码代替条件判断
        • 比如用cond ? a : b，在GCC上它能生成cmov，从而避免了分支预测。并不是所有的程序都能改写成这种形式，因为它要求先计算出两个分支的值，这会增加计算量，而且语义也可能不允许
• 现代disk一般有多个zone，越往外，zone中每个track的sector越多；sector由disk driver管理，它将sector抽象成block暴露给上层，物理sector会有部分作为备份，因此block数少于sector总数
• 关于SSD(solid state disk)
  • 它是一种flash rom，长期以来被用于mp3播放器等，由于一直在降价提高容量，是disk的一种潜在替代者
  • 它的顺序读写极快，随机读也在同一量级(随机读的比disk快了数百上千倍)，随机写要慢一个量级
  • SSD的写较慢是因为：数据的读写单位是page，而每个几十个page组成block，写page的时候，要求先擦除block，才能写，如果block上已经有其他page了，必须拷贝到一个已擦除的新block后才能写，所以慢很多
  • 写SSD会消耗寿命，闪存翻译层的平均磨损(wear leveling)逻辑会尝试通过将擦除平均分布在所有块上来最大化寿命
  • 一个典型的SSD读写速率：
    • 顺序读: 250M/s 顺序写: 170M/s
    • 随机读: 140M/s 随机写: 14M/s
    • latency: 随机读: 30us 随机写: 300us
• 由于i-cache几乎是只读的，因此它的参数可能和d-cache不同，它可能更简单
• core i7的存储器系统
  • 每核
    • L1 d-cache 32K, L1 i-cache 32K
    • L2 unified cache, 256K
    • L1 d-TLB 64, L1 i-TLB 128
    • L2 unified TLB 512
  • 4核共享, L3 unified cache, 8M
  • quick path将4核连起来，让1个核和其他核以及外部IO bridge直接通信
  • cache的输入是物理地址, TLB的输入是VPN
  • 48位VAS和52位PAS
    • 可配置page size为4K或者4M(以下讨论限4K)
    • PTE是64位即8字节，因此4K的页只能放512个PTE
    • 4级页表, 48位被分为9,9,9,9,12, 即每级页表512个元素，每个页4K
    • 对于前3级PTE，64位里记录了读写标记、执行标记、内核模式标记、只写/写回策略、access标记、页大小(4K/4M)、40位的下级页表的PPN、是否在物理存储器中(linux上总为1，即页表常驻内存)
    • 对于最后1级PTE，还记录了dirty标记
    • 因为PTE中的PPN是40位，因此PAS是52位，如果这里的PPN是4*9的话，VAS才等于PAS
• 访问VA -> PTE-> 是否在物理存储器中? 如果是，则PA; 否则 -> linux, 是否是一个合法的段? 否的话，非法访问; 是的话，执行page fault处理程序

23. 杂项

• 比较整数x,y: x < y，而x - y < 0和-y < -x都是错的，它们都可能溢出，前者是减法溢出，后者是因为-INT_MIN==INT_MIN
• 用异或和减号编写的trick版的swap缺点：
  • 不具备generic programming的能力
  • 当x,y引用同一个对象的时候，会被清0
• C中无符号数>>规定是逻辑右移；有符号数的>>没有明确规定，编译器通常实现为算数右移
• C标准没有规定i >> w中的w如果超过sizeof(i) * 8的行为，一般的处理器上它的结果将是i >> (w % (1 << sizeof(i) * 8))
• C的union绕过了类型系统，要小心
• Java只有有符号数，而无符号数一般被用作纯粹的位序列，因此，丢掉无符号数过后，相应的必须提供逻辑右移的能力>>>
• 一些新的处理器可以配置成little-endian或者big-endian
• 群: 封闭性、结合律、单位元、逆元
• 阿贝尔群: 即交换群，在群的基础上满足交换律。int上的+法即是阿贝尔群
• gdb的几个命令:
  • break funcname: 在函数开始下断点
  • disassemble funcname: 反汇编该函数
  • info register: 查看寄存器
  • gdb -x file: 可以执行file中的多个命令，从而可以达到保存断点的效果
• 早期的RAM的每一位都是由一个铁氧体磁芯实现的，所以物理内存被称为core memory

25. SICP, 第1章, 构造过程抽象

• 大纲
  • 程序设计的基本元素
    • 表达式: 数字和运算符，以及组合式
      • +,-,*,/,remainder,not都是过程; 常用过程还有display/newline/random/current-milliseconds等
        • +,*都只有1个元素的时候，结果是元素本身(相当于和0,1结合)
        • -,/有>2的操作数时，相当于a[0] op a[1] op a[2]...
      • 1.0是浮点数，在此基础上进行的计算都是浮点数
      • 1是整数，在此基础上进行的计算都是有理数。racket支持任意精度的有理数，解释器可能通过gcd化简有理数成真分数
    • 命名和环境: 通过define将一个名字和值绑定到当前环境中
      • 本质上只有(define name exp)一种语法，(define (funcname args) body)是(define funcname (lambda (args) body))的语法糖
    • 求值过程
      • 当(...)以非关键字开头时，其中各个子表达式会逐个求值，最终的值列表中，第1个元素是一个过程(lambda或者builtin的+-*/等)，后面的值会作为实参来调用过程
        • 存在惰性求值的解释器实现，后面的实参不会在调用过程前就展开，但racket是立即求值的
          • 一个判断是立即求值还是惰性求值的方法: (define (p) (p))和(define (test z p) (if (= 0 z) z (p)))，然后call(test 0 p)，立即求值的话会死循环；类似的，把p定义成输出，看是否会输出也能检测是否惰性求值
      • 当(...)以关键字开头时，执行特殊的求值方式，即scheme本身的语法生效
        • cond: 逐个求值各个case，遇到真时，求值exp并返回。求值严格按照这个顺序，短路逻辑。case的语法是: (pred exp1 exp2 exp3 ...)，返回最后一个exp，其实这里得到了语句的效果
        • else: 用为#t的关键字。(在racket中，true和false是两个预先define的变量，分别为#t和#f)
        • if: cond的两分支特例，解释器会检查两个分支都存在。then和else的exp只能是单个exp
        • and: 返回#f或者最后1个exp本身，短路逻辑
        • or: 返回#f或者第1个非#f的exp本身，短路逻辑
        • define: 将一个名字-值对绑定到环境中
        • lambda: 定义一个用户过程。语法(lambda (args) [(statement1) (statement2)...] body)，其中的statement可以是(define ...)(newline)(print ...)(display...)等，太自由了
        • let: 求值为一个表达式，用于在任何允许是表达式的位置通过call一个lambda引入局部变量。语法(let ((var1 exp1)(var2 exp2)) body)，是((lambda (var1 var2) body) exp1 exp2)的语法糖
  • 过程与计算
    • 线性递归(linear recursive): 往往很容易通过将状态作为参数传给f(x(n+1))，从而形成尾递归，使得时间复杂度保持O(n)不变，但是栈空间复杂度从O(n)降到O(1)；IEEE标准要求scheme的实现支持尾递归，所以可以期待解释器将其优化成迭代
    • 树形递归
      • 作用在数列上时，开销可能是指数的；思路自然，但要写成尾递归优化可能很难或不可能。fibonacci数列是一个树递归成功迭代化的例子
      • 当递归作用于层次结构上时，可能是自然的。比如树结构的遍历
    • 几个logn的算法
      • 幂可以用logn的乘法得到
      • 乘法同样可以用logn的加法得到(最快的是FFT)
      • fibonacci可以用logn的2x2矩阵乘法得到
      • gcd的经典求法也是logn的
      • 大素数测试所用到的pow也是logn次mul&mod得到
  • 高阶函数用于抽象
    • 过程用做参数
      • 求和，比如定积分
      • 折半查找求根，不动点，牛顿迭代
      • map/filter/reduce
    • 过程作为返回值
      • double/compose/repeat等高阶函数
      • first class的概念
        • 可以赋予变量名
        • 可以作为过程参数
        • 可以作为过程返回值
        • 可以被装在结构中
• 启发价值的工具
  • 有过程f(x)，能够返回其导数，即(f(x + dx) - f(x)) / dx
  • 有过程f(x), 能够返回其定积分，即(f(a + dx/2) + f(a + dx/2 + 0*dx) + f(a + dx/2 + i*dx)...) * dx
  • 有过程f(x), 能够进行不动点迭代(fixed-point)，找到x使得x=f(x)
    • 对于特定的方程f(x)=0，可以精心构造g(x)来通过不动点求f(x)的根
    • 基本迭代方法: x(n)=f(x(n-1))，可能震荡甚至无法收敛
    • 平均阻尼(damping): x(n)=(x(n-1) + f(x(n-1)))/2，收敛性更好
  • 有过程f(x)，能够通过折半查找法求f(x)=0的根，要求同时提供a,b使得f(a)<0且f(b)>0
  • 有过程f(x)，可以进行newton-transform得到x - f(x)/f'(x)，对它进行标准不动点迭代(非平均阻尼)，即可求得f(x)=0的根
    • 通过x(n)=(x(n-1) + y/x(n-1))/2来求sqrt的做法，即是牛顿法的一个特例
  • 上面方法的应用:
    • 求平方根，3次方根甚至n次方根，都等价于求f(x)=0，于是可以用遮半查找或者牛顿法来求根
    • 黄金分割是f(x)=1+1/x的不动点
    • 求pi
      • 因为sin(pi)=0，所以求sin(x)=0的根能得到pi
      • 圆的面积等于pi*r^2，所以sqrt(1 - x*x)在[-1,1]的定积分是pi/2，所以求定积分能得到pi
      • 莱布尼茨发现pi/4=1-1/3+1/5-1/7+1/9...，所以求和可得pi
    • 求e: 见p47
    • 求tan(x): 见p48
  • fibonacci数列的第n项的log求法: 可以看做是对向量(1, 0)进行n次((1,1),(1,0))的矩阵变换，即v * pow(m, n)，其中pow是logn的，所以...
  • 对200位数进行因式分解在目前的计算机上是不可能的，但是进行素数测试确实可能的，由此催生了密码学、电子金融的应用。RSA也是基于大素数测试的可能性的
    • 基于费尔马小定理的测试: 对素数n，有小于n的数a，(a**n)%n==a
      • 存在骗过费尔马测试的数叫Carmichael数，很少，包括561,1105等，它们不是素数却能通fermat测试
    • Miller-Rabin检测，一种费尔马测试的变形，不会被欺骗: 如果n是素数，a小于n，(a**(n-1))%n==1
  • 几个神奇的高阶函数
    • 过程double，可以将f(x)应用两次，即f(f(x))。威力强大，比如((double (double double)) square)等价于将square应用16次!(注意不是2^3次, 8次的应该是(double (double (double square))))
    • 过程compose，效果是f(g(x))
    • 过程repeat，效果是将f(x)重复n次，即f(f(f(...f(x)...)))；它使用compose在logn的时间内构造
      • 一个repeat的应用: 有过程smooth等于(f(x-dx) + f(x) + f(x+dx)) / 3，要将smooth应用5次，则smooth-5=(repeat smooth 5)
• 编码风格
  • 谓词过程名以?结尾: prime?
  • 多参数过程每参数一行，参数列对齐
  • 需要迭代的过程，尽量写成尾递归，方法名以-iter结尾

27. 杂项

• C++ project: Y-combinator
• Lisp project: Y-combinator

29. SICP, 第2章, 构造数据抽象

• 大纲
  • 引
    • 本章的重点是将数据对象组合起来，形成复合数据。和复合过程一样，复合数据是为了提高我们在设计程序时所位于的概念层次，提高设计的模块性，增强语言表达能力。
    • 和复合过程一样，这里考虑的主要问题，是将抽象作为克服复杂性的一种技术，数据抽象将使我们能在程序的不同部分之间建立适当的抽象屏障(abstraction barriers)
    • 复合数据的关键思想是闭包，即，组合对象的粘合剂不但能用于组合基本的数据对象，也能用于复合数据对象
    • 过程的参数和局部变量，都是bound variable；而引用的外层过程参数和局部变量，以及全局变量，都是free variable，含有对它们的引用的高级函数被称为闭包。
  • 数据抽象导引
    • scheme的pair很简陋，使用很晦涩，但构造过程和字段访问过程的抽象有效的屏蔽了这种不便，同时它们作为抽象屏障也隐藏了数据表现的变化，提供了扩展能力
    • 在scheme的数据抽象中，cons/car/cdr位于最底层，出于性能考虑，它们被解释器实现为链表，但其实如果仅以实现语义为目的的话，能够捕获free variable的closure，已经可以作为复合数据的载体了，即，可以用包含free variables的closure作为复合数据本身，传入特定参数来返回不同的free variable，从而提供数据字段访问的能力
      • cons/car/cdr的实现1: cons返回闭包，car传入0选择第1个字段，cdr传入1返回第2个字段。这是将携带free variable的closure看做对象的message-passing style应用
      • cons/car/cdr的实现2: cons返回闭包，它接收一个过程作为参数，然后以所有的free variable调用这个过程并返回结果；car传入过程select_first_arg; cdr传入过程select_second_arg。这是将closure看做对象的message-passing style
      • cons/car/cdr的实现3: cons返回一个整数，它由两个素数的幂构成，比如2**n * 3**m; car从数中提取2的幂; cdr提取3的幂；当然，这种表示只能组合基本数据，不能再组合复合数据，不具备真正的闭包能力(这个闭包是"对操作封闭"的概念)
      • cons/car/cdr的实现4: 解释器实现，struct pair { void *car; void *cdr; };
    • 本节实现复数时，先提供数据抽象的接口，再基于接口实现算法，最后才用具体的表现填充数据抽象接口的做法，非常典型！可见即使语言本身简陋，但借助于数据抽象，仍然可以自由表达算法！数据抽象作为屏障，有效的隔离具体表现方式(无论具体的数据是用结构、链表甚至是closure来呈现，完全不影响算法实现本身！)
  • 层次性数据和闭包性质
    • 术语闭包来自抽象代数，指如果将运算用于这一集合中的元素，产生出的仍然是该集合里的元素。另外闭包在程序设计中被用于指代包含自由变量的过程。
    • cons具有闭包性，C和Pascal中的结构和数组不具备闭包性
      • Alan perlis在SICP前言中评论，在Pascal中，过多的可声明数据结构导致了过程的专用化，从而造成对合作的阻碍和惩罚
    • cons很容易表达链表，而基于链表可以实现大部分算法
    • 因为cons具有闭包性，很容易通过嵌套链表实现多分支树
    • 无论具体的数据结构是二叉树、kd树还是其他结构，都可以通过某种方式遍历，得到链表的方式，实现迭代器的抽象，进一步实现各种算法
    • Richard waters通过自动分析Fortran的程序，并用map/filter/fold的观点去观察，他发现Fortran的科学计算程序包里，90%的代码都可以纳入这一范畴
      • lisp成功的一个原因，就在于它用表作为一种标准接口，并提供高级函数来处理
      • 程序设计语言APL的威力来自类似的选择，它的所有数据都是数组，而各种类型的数组都提供了一组普遍的、使用方便的运算符
    • 通过嵌套map加上flatten的方式，提供list comprehension的能力
    • 描述一种语言时，注意力应该集中在语言的基本原语、组合手段以及抽象手段
    • 实例：通过beside/below/flip-vert/flip-horiz的方式组合painter，而painter又被定义为高阶过程，不同的painter绘制不同的图像(线条、位图)；通过这样很简单的方式，组合出递归绘制的漂亮版画！
      • 这其实是FP风格的多态，本例中相当于该多态只限于一个函数paint，因此painter被实现为函数子；如果该多态需要提供多组操作的话，如size/pos，那么可以用message-passing style，即传入操作选择子的symbol，这样就和常见的OO多态相同了；当然explicit dispatch和data-directed style也是可行方案
      • 程序设计的一个关键概念，分层设计
        • 一个复杂系统应该通过一系列层次构造出来，为了描述这些层次，可能需要使用一系列语言
        • 设法组合一个层次中部件的各种基本元素，而这样构造的部件又作为另一个层次的基本元素
        • 每个层次所用的语言都提供了一些基本元素、组合手段和对该层次中的适当细节做抽象的手段
          • 计算机工程里，电阻和晶体管被组合出来，产生与门、或门等部件
          • 门电路又被作为数字电路设计语言中的基本元素
          • 以上部件被组合起来，构成处理器、总线和存储器，进而构成计算机。这一层的语言是计算机体系结构
          • 计算机可以进一步组成分布式系统，采用的是适合描述网络互连的语言
  • 符号数据
    • 关于quote
      • 自然语言中，引号用于强调字面本身，而不进行语义解释，lisp中的quote也一样
      • lisp中最常见的元素是number、symbol、list，这三个元素递归构成的复合结构，其打印输出等于其源码文本本身，这是刻意设计的！
      • quote(')能被作用于符号和括号
        • (被用作数字，等于数字本身)
        • 被用作符号，返回symbol，它是一个interned的immutable string；即atom，能通过eq?高效的比较
        • 被用作括号，返回列表，其元素被递归的quote
      • quote的结果是atom或者atom的列表
        • 从用户程序的角度看，它返回的是数据树(dom)或者parsed ast(如果被quote的是lisp源码的话)
        • 从解释器的角度看，解释器parse整个源码后，得到大的ast，进一步将各个过程、表达式置入环境中解释执行，唯有quote节点的ast，解释器不访问，直接将这颗ast子树交给用户程序
      • 由于quote返回的ast/dom是解释器parse得到的，解释器同样用该结构解释执行，而s-expression的结构又及其简单，因此，quote源码后由lisp自己来模拟解释器，也是十分容易的
        • lisp很容易拿到ast，该ast结构简单，易于扩展和解释，因此lisp具备强大的元编程能力，是作为解释器/虚拟机的好选手
    • 集合的union和intersection，都可以通过在有序数组的基础上完成，因此，任何表示的集合，其union和intersection的复杂度都不应该超过O(n)
      • 直接的想，两个二叉树表示的集合，求交，是O(n*logn)的，但其实只要先中序迭代(O(n)的)，得到两个有序迭代器(数组)，就可以进一步O(n)的union或intersection了
      • 给一个有序数组，很容易构建一个平衡二叉树，其实如果给的是链表，一样也能构建平衡二叉树
      • 两个二叉树表示的集合求交:
        1. 中序遍历两个tree得到list1, list2
        2. 对有序list1，list2求交得到list3
        3. 根据有序list3构建平衡二叉树
    • huffman树的symbol不一定是8bit的字符，可以是任何单词
      • 实际上deflate中的huffman compression过程，就是以literal和lz77的输出codeword作为输入symbol的
  • 抽象数据的多重表示
    • 实例，复数的两种表示，分别是直角坐标系和极坐标系，前者适合做加减，后者适合乘除。同时支持两种表示，避免了不必要的转换开销，提高了性能(比如连乘或连加)
    • 多态的几种表示
      • explicit dispatch。每个操作根据类型tag显示分派，对类型封闭，对操作开放(增加新操作无需修改现有代码)
        • visitor pattern具备一样的特点，即对类型封闭对操作开放(需要新操作只需要派生一个visitor即可)
      • data-directed style，每个对象attach上类型tag，多态调用点上，根据"操作+类型1+类型2..."的组合查表得到实际的过程，然后再传入去掉类型tag的对象实体进行调用
        • 支持多分派
        • 对类型开放，对操作封闭
        • 闭包性：如果需要支持层次的多态，那么一个对象可能被前缀多个类型tag
      • message-passing style，用高阶过程表示对象，通过将方法symbol和参数传入这个过程，在过程体中进行分派和执行
        • 单分派
        • 对类型开放，对操作封闭
        • 等价于OO中的interface/base class，这里的高阶过程，过程体本身标记了类型(这个过程体/类型，决定了消息分派方式)，过程中的free variables相当于对象字段
        • 这里用free variable表示对象字段的方式，实际提供了一种聚合数据的方式，因此，它可以用来实现cons/car/cdr；也证明，支持closure的语言是turing complete的
        • 闭包性：因为高阶过程是first class的，因此可透明的复合
    • 要实现data-directed style中多分派过程的注册，需要支持mutable的associative array。scheme中提供了make-hash/hash-set!/hash-ref等一组函数
  • 带有通用型操作的系统
    • 虽然data-direcited style支持多分派，但当找不到完全匹配类型的过程时，可能需要提升类型(raise)，而因为自动提升机制的存在，自动化简的drop可能也需要，这是一个很复杂的机制
      • 像刚体碰撞这种多分派，一般要求强类型匹配，但当找不到完全匹配时，能够自动raise成sphere/bounding box等基类来完成碰撞，可能也是可接受的
      • 整数、有理数、实数、复数、多项式这样的算数系统，可能就需要提供自动类型raise/drop的机制以完成类型适配
      • raise除了可以在多分派中进行类型适配外，即使是单分派，自动raise也能让int/float这样的派生类支持复数/多项式的方法
• 启发价值
  • cons, car, cdr的由来
    • cons: construction
    • car: contents of address part of register
    • cdr: contents of decrement part of register
  • p62, 纯粹通过lambda来实现算数运算，即church计数
  • append, map, length都可以通过fold来实现
  • 向量的dot-product，矩阵的matrix-mul-vector、matrix-mul-matrix、transpose，都可以用map/fold/zip等高阶过程来实现(通常只需要1、2行代码)
  • 实现全排列(permutations)
    • 对S的每个元素x，调用permutations(remove S x)后，将x附加到每个结果的前面；再将所有x对应的排列flatten起来
  • 实现八皇后
  • 实现huffman编码
  • quote只被用于下一个元素，它只能是一个数字/符号或者括号，因此一个单引号足矣
  • eq?/eqv?equal?的比较
    • eq?，比较两个对象是否是同一个，实现依赖，具体为比较指针。symbol因为interned，所以适用；小整形因为是immediate的，所以适用；但float和big integer由于可能涉及内存分配，所以不适用
    • eqv?，适用于包括float/big integer在内的数值
    • equal?，各种类型的判等，包括string(mutable string)和list，其中list是递归比较
  • 符号求导
    • 和用高阶过程表示的导数比较
    • 仅仅通过4个规则即可包含所有加法乘法和幂: c->0, x->1, f1(x)+f2(x)->df1(x)+df2(x), f1(x)*f2(x)->...