前天看到 pongba 说好书太多 以致于没时间写博客, 深有同感. 架子上目前放着 Dreaming in Code 和 TAoCP 第四卷第三册, 手不释卷, 以至于三上时间都不放过. 细想自己读过的好书不少(至于烂书, 只能用无数这个词来衡量了), 勉强回忆了一些让自己印象深刻的, 写一两句话的点评, 算是我眼中的必读经典吧.

A类. 基础

Structure and Interpretation of Computer Programs (SICP)

计算机程序的构造和解释 (SICP) 堪称是MIT计算机系的镇山之宝之一, 书中通过展示 LISP 语言和程序设计两条主线, 向读者展示了程序设计的几乎所有重要概念. 数十年来各种语言层出不穷, MIT 依然故我给入学本科生教 LISP. LISP 这种函数式的语言, 和过程语言相比, 理论更加优美(lambda 演算), 描述更加简洁. 现代的动态语言如 Javascript, Python 和 Ruby 都或多或少被 LISP 影响. 任何想写具有清晰结构, 或者正确思路的程序的人, 都应当阅读这本书. 好消息是, 这本书是可以在线免费看的.

The Art of Computer Programming (TAOCP)

计算机程序设计艺术 (TAOCP) 是计算机领域的一部未完成的里程碑. 如果之前没有听过它的大名, 那就不算学过计算机科学. Knuth (中文名高德纳) 阅读文献无数, 博古通今, 文风幽默. 书中讲解细致深入, 大开大阖. 如果说 SICP 是练童子功的话, 这本书就是属于名门正派的顶极内功. TAoCP上往往一个普通的习题, 就是一个很经典的结论; 往往不经意的一句话, 就是一个巧妙的算法. Knuth 常常把貌似不相关的结论深刻的联系在一起, 比如我现在读的第四卷第二册上九连环问题和Gray码是深刻联系的, 易经和生物遗传密码子也是有对应关系的(当然不是民科说的那种).

如此的打通任督二脉的例子和习题俯拾皆是, 真的是穷人进了皇宫的感觉. 即使对于面试工作, 这套书也是值得一翻的: 在Google面试的时候, 面试官问一道题目, 我很快给了一个答案, 其中用到了一个不太显然的结论. 面试官问, 这个结论怎么来的? 我说, TAOCP 第二卷讲了这道题目的一个推广情形. 面试官说, 这道题目就是看面试的有没有看过 TAOCP. 我看很多人面试之前都在网上疯狂做题, 尚不能穷其一隅. 其实读过 TAoCP 的人极少会害怕面试的时候那些技巧性的问题. 万变都极少超出TAOCP划出的框架.

Introduction to Algorithm (CLRS)

算法导论 (Introduction to Algorithm), 在圈子里常常按四个作者的首字母写成 CLRS, 算是对不愿意看或者看不懂 TAOCP 的人送上了半个梯子(还有半个当属具体数学 Concrete Mathematics). 这本书在美国大部分大学中被列为算法类教材, 在国内也是 ACM 竞赛集训必看的教材之一. 虽然名字里面带一个导论, 内容却一点不含糊. 在我个人看来, 其内容基本覆盖绝大多数常用的算法, 在 NP 复杂性理论以及近似算法方面也有所涉及. 这本书最好的地方是习题详细且全部没有答案, 非常适合作为大学课本和ACM讨论班阅读材料, 最坏的地方也在于没有答案, 对于自学者来说, 可能会觉得枯燥无味且困难重重.

另: 如果有淘老书的习惯, 不妨选择 The Design and Analysis of Computer Algorithms (计算机算法设计与分析) 这本书在 CLRS 出现之前绝对是算法教材一哥. 可惜这本书一直没有更新, CLRS 才以算法多而全取胜.

Compilers: Principles, Techniques, and Tools

这就是著名的龙书 (Dragon Book) 啦. 和上面的 The Design 一样, 都是 Stanford 教授 Jeffrey D. Ullman 的巨著. 计算机的历史很大程度上是编译器发展的历史. 当年 Knuth 就是因为写了Alogo 60 编译器后, Addison-Wesley 过来找高爷爷约稿, 1962年的时候就让他写本编译器的书. Knuth 写啊写啊, 发现写了很久还没写到主题. 那边编辑急了, 说你都写了3000页手稿了, 你还不交稿. 高爷爷说, 这个, 我还没写到正题呢. 书商说, 算了, 你出多卷本吧. 于是才有了 TAoCP. 这个小故事也就说明计算机编程的发展史和编译器的发展史是平行的. 龙书基本上框出了一个编译器的架子, 从词法句法分析到类型分析 代码生成. 新版加入了JIT, 垃圾收集等现代特性. 这部巨作的作者阵容也是强大的: Alfred Vaino Aho 是 grep 和 awk 的作者. Ravi Sethi 以前在 Bell 实验室, 现在好像是朗讯的首席技术官. Avaya 实验室的头. 至于 Jeffrey Ullman 这个老头, 好玩的趣事就更加多了, 比如他是 Sergey Brin的导师, 他有两大不回信原则: 陶瓷信不回, 问书后习题信不回.

[under construction, more later…]

Modern OS

(Artificial Intelligence: A Modern Approach(AIMA)

Structured Compter Architecture

Computer Architecture: A Quantitative Approach

Computer Networks

B类, 编程

K&R C

Programming Pearls and More Programming Pearls
The Practice of Programming
Code Complete or The Elements of Programming Style
MMM(Mythical Man Month)
GoF’s Design Pattern
The Art of Unix Programming

C类, Geek

H2G2
GEB
How to Solve It
Elements of Style
The Cathedral and the Bazaar

通常, C 程序员使用如下代码对 a 数组的每个元素进行操作:

for (i = 0; i < n; i++) func(a[i]);

这行代码有三个独立的逻辑, for 循环控制了对 a 的访问顺序, a[i] 控制了对 a 数组的元素访问方式, func() 函数控制了对 a 元素的操作. 这个三个逻辑是彼此独立的. 然而, 问题逐渐浮出水面. 首先是 for 循环的次序. 对于随机存取的数组 a, 访问顺序应当是没有关系的. for( i=n-1; i>=0; i–) 也是可以的. 一个简洁的语言应当突出逻辑, 丢掉不必要的代码. 因此, 最好能写成

foreach (k in a)  func(k);

这个解一石二鸟, 第一是把访问顺序逻辑彻底抛弃, 第二是改变了访问方式, 从此没有烦人的 ArrayIndexOutOfBoundException, 不需要担心访问越界. 在函数式编程语言中, 类似的形式是:

map(func, a)

我们希望 foreach 能够遍历一个数据结构的每个元素一次. 可是这个终究是一个语法糖, 因为它只能胜任特定的数据结构. 对于用户自己设计的一些数据结构, 比如树, 想同时拥有先序和后序遍历, foreach 就无能为力了. 与此同时, 我们也不想用 for 那样简单粗暴的方式去控制访问顺序 (因为很容易导致内存越界, 而且很多数据结构不支持随机存取). 这时候, 就需要迭代器的帮助了. 因为不同的数据结构要求不同的访问顺序, 我们希望数据结构本身能够提供一些访问顺序. 这种对于数据结构上元素访问顺序的抽象, 被称为迭代器. 一般来说, 迭代器通过 getIterator() 被数据结构构造, 具有一个 hasNext() 的判断和一个 next() 的函数. 对一个数据结构的访问可以四海一家的写成:

for (i = a.getIterater(User’s_Order); i.hasNext(); i.next() ) func(i.current());

迭代器把访问逻辑从数据结构上分离出来, 是一个常用的设计方法. Design Pattern 也把它作为23个Pattern之一.在 STL 中也到处都是了它的身影. 但对一个完美主义者来说, 这个代码还是太冗长, 既然对数据结构的访问能够四海一家的写成如此, 为何不直接规定一个简洁的语法访问呢? 是的, 我们希望返朴归真, 回到原来的形式:

for i in a.SomeIterator(): func(i)

好消息是现代语言都支持这样的方法. [注: 在C/C++ 语言中, 还不能支持上面的写法. C#有类似的写法. 在 Ruby 和 Python 中很常见. ] 可是能不能再简化呢, 能不能连 i 这个中间变量都不要呢? 我们简直希望写成:

a.SomeIterator(func)

是呀, 这样的世界多美好啊. 可是, 别忘了在面向对象的语言中间, 一切都是对象. 在 C 的时代, 我们可以通过函数指针把 func 参数传递进去. 可是这里是对象, 怎么办呢. 很简单, 只要构造一个只有一个方法的对象, 传进去就行了. 这样的构造方法, 居然也是一个设计模式, 叫做函数对象(Function Object), 或者叫函数子 (Functor). 被 Java 的匿名内部类这个概念折腾到崩溃的读到这里, 应该知道所谓的匿名内部类, 就是为了在面向对象的环境中做函数传递这个事情而想出来的小花招. Java 的写法就是

a.SomeIterator( new FunctionObject()
{ public func(a)
{return something;}
});

［为了引用这样一个函数, 使用了天书一般的不必要代码, 可想有多少人真的喜欢这个方法］

逃离了Java 的世界, 我们来到 Python 或者 Ruby 或者其他函数式语言的世界, 激动的发现原来函数也是一种对象, 和其他对象一样在 Python 中坐上头等舱. 如此好事怎么能错过呢. 于是, 大摇大摆写上:

a.SomeIterator(func)

没有类型检查, 也没有复杂代码, 连一个辅助变量都不多谢, 真舒服. 在 Python 中间, 这样的模式比比皆是, 比如 os.path.walk(path, visit, arg) 可以对path目录下所有的文件遍历, 并且调用 visit 函数处理, 还可以夹带一个私货 arg 进去, 非常方便. [注: os.walk() 则反其道行之, 提供一个 generator, 外部用 for 访问]

从外面夹带私货不算特别困难, 毕竟可以通过修改函数的定义方式来实现. 可是假如想从迭代器里面夹带一些私货出来给函数用, 就有点困难了. 比如说, func 函数需要访问迭代器的一个私有的变量. 显然把迭代器作为参数传给函数是不行的. 只能反其道行之, 让迭代器把函数当成自己人, 以迭代器为主, 把函数包含到迭代器的作用域内才能玩转. 这个就是所谓的闭包. 也就是说, 一个函数被包入另一个更大的作用域, 并且可以访问大的作用域里面的变量. C/C++ 是不允许在函数里面定义函数的, 所以只好望着闭包干羡慕. Java 算不错了, 用内部类解决了这个问题.

我们说个具体的例子: 函数 func(x) 需要另一个值 y, 返回 x*y, 另一个值 y 在外部作用域定义了. 写成 Python 代码

a= [1, 2, 3]
def func(x):
return x*y

for y in a:
print func(2)

会出现 2,4,6

我们可以看到, 函数func 的定义和使用是独立的. 而静态语言是不能随便在什么位置都能定义函数闭包的, 原因不难解释: 编译器会跳出来告诉你 y 这个变量没有定义. 因为动态语言在运行时才能得到 y 的值, 从而使用 func, 所以不存在这个问题. 动态语言的灵活性在此充分展现. 最后, 既然我们知道迭代器后面必然要加一个闭包, 还要括号干啥? 不如直接写成 (实际上, Groovy 语言就是这样的):

a.each func

从简单的循环, 到迭代器, 到生成器, 到内部类, 到函数作为一级对象, 再到闭包, 过程式编程语言, 对象编程语言和函数编程语言越来越呈现融合的趋势.

文章名：

Ultimate Physical Limits to Computation [计算的终极物理极限]

作者: MIT 的 Seth Lloyd,  量子计算领域顶尖科学家.

概要:  计算机是一种物理系统，因此肯定服从物理系统的规律。文章研究了一千克的计算机最多一秒能执行多少次逻辑运算，最大存储容量是多少，并且给出了定量的结果。所以, 摩尔定律不能永续。

这些问题和我以前提到的比特每焦耳问题是很相似，但是我物理基础有限，不能全部理解。
本文发在 2000 年 Nature.地址: 

http://puhep1.princeton.edu/~mcdonald/examples/QM/lloyd_nature_406_1047_00.pdf

有兴趣的直接给我发邮件或者gtalk: xu.mathena [A@T] gmail.com

某午夜, 灵感泉涌, 找灯开关, 找笔, 找纸, 找合适的词, 试图再现思维的火花. 提笔, 乱七八糟的中文, 潦草的数学符号、记号, 几行伪代码, 夹杂英文单词. 我常常想, 假如我从来不曾学过数学, 从来不会英语, 我记下的思维状态, 是否会和现在一样； 我在思考的时候, 会不会自觉的使用数学语言, 会不会用英语? 咿呀学语的婴孩, 不会使用人类语言的聋哑人, 又该如何记下他们的思维? 语言符号到底是构建了人类的思维, 还是限制了思维的表达?

谱曲要入五音, 写词要从平仄; 语言要有语法, 文章要有结构; 这些, 包括编程, 计算, 证明, 都是在使用思维而赋之于符号规则系统(语言). 符号系统有其规则和用法. 守其规则, 才能有交流. 如果放弃了语言的交流功能, 则可以解放思维, 自由表达. 如果我们观察乡村里的”土哑巴”(不会正规的手语，手语是自创), 则只有周围的少数人能理解其含义. 从他的思维层到自创的手语层也许是透明的一一对应的, 无碍的. 但出了他的手语层而要求和他人交流时, 其自创的手语又成了交流的障碍. 因此, 规则是用以交流用的语言必须内涵的. “即使狮子会说话，我们也不懂得它”.

语言能力不是与生俱来的. 即使完全通过逻辑, 从原始的事实构建到高层的抽象, 也需要时间. 以数学为例, 从最简单的集合论和代数系统到费马大定理, 完全通透的走过也需要比较长的时间. 而构建这个大厦的砖块只是几条公理, 建造的方法又只有逻辑一种. Wittgenstein (维特根斯坦) 在逻辑哲学论中讲语言是思维逻辑结构的几何投影. 思维逻辑结构建立后, 可以借助于语言, 通过一个人传递到另一个人. 如果语言的几何投影能够被简单还原, 思维就通过语言完成了一次传递. 在A(创造者)脑中, 语言是被构建的. 在B(学习者) 脑中, 语言是被解构并还原为事实的逻辑图像(思想)的. 在学习者那里, 思维是要需要借助语言进行的.

一个人认识到的世界不是完备的, 因此使用的语言集合也只是一个子集. 对语言的理解程度决定于对世界的构建. 仍以数学为例, 研究微分方程的数学家与研究代数数论的数学家如果遇到了, 可能彼此都不懂对方在讲什么. 微分方程世界的语言, 对于代数数论世界的数学家, 是难以解构的, 因为他的世界里缺少语言反向解构的对应物. 回到自然语言, 英语对于很多中国人, 是无法解构的, 因为我们无法分辨这个语素到底对应了什么. 但是假使我有一本字典, 这个问题也就解决了. 抽象的层次, 表达的符号, 描述的世界等所有的一切不同, 都让语言这个逻辑图像呈现出了不同的样子, 而让不熟悉这个语言系统, 或者缺乏逻辑世界对应物的人, 云里雾里.

我们来研究一个设计精巧而简单的语言: 程序设计语言. 程序设计语言是也是表达思维的工具.

程序设计语言有语法, 有规则. 语法和规则是为了让底层的语言理解机制消歧义, 获得一致性的解释. 符号在程序设计语言中发挥了原子的作用. 几乎所有的编程语言都是基于封闭世界假设, 也就是说, 没有声明(被计算机感知)的原子符号, 不能使用, 每个事物都有其本体论含义. 编程语言把真实世界的逻辑关系映射到了计算机世界. 因此受制于计算机世界. 在语言和思维关系当中, 语言的限制造成思维表达能力相对受制, 而相反的, 交流能力却大大提高 (居然能和一台机器打交道了).

图灵完全性从一定程度上解决了语言能力的问题. 一般来说, 编程语言被计算机解构后, 描述计算机世界的能力是相同的. 但是这不代表编程语言的表达真实世界的能力是一样的. 事实上, 不同的编程语言的描述世界的能力是不一样的.

程序设计语言是真实世界的逻辑图像, 这个图像对应了一种逻辑(算法), 一个设计哲学(模式, API)或者一个世界模型(框架). 而这个图像可能位于世界的不同层次. 以Java, C 和 SQL 为例. Java 是对象世界的逻辑图像. C 是过程世界的逻辑抽象. SQL 是关系(数据库)世界的逻辑抽象. 因为世界难以”一言以蔽之”, 因此不同的语言出现是必然的. 三个语言在解题能力上是等价的, 然而, 之所以没有人用 Java 用做关系数据库的语言, 是因为 Java 的逻辑抽象, 不是关系数据库的一个直接几何投影. 因此, 用 Java 这个逻辑图像去重现施加于关系数据库世界的逻辑, 是不够直接简明的, 至少说, 不是最贴切的.

从程序设计语言的使用上, 我们可以清楚的看到, 语言的错误选择限制了思维. 语言的错误选择不在于语言本身, 而在于语言和表达世界的不契合. 以 Java 编程为例, 一开始的 public static void main 封装在一个 public class 中, 不知道吓退了多少从来没有接触过面向对象的语言学习者. 推而广之, 即使一个框架设计再好, 不了解其设计哲学, 仍然觉得难学难用. 不契合来自于四方面, 1. 对世界模型的不熟稔, 造成语言无法使用. 比如, 对MVC的不熟悉造成Struts难学难用. 对IR不熟悉造成 Lucene 难学难用. 2. 太复杂的抽象造成语言难以入门, 比如 Java 模型造成一行Hello, world 都要至少构造一个 class, 一个 main 和一个 system.out (在Java 6.0中已经无须这么复杂). 一个简单的逻辑映射出不属于这个世界的很多抽象. 不必要的复杂性吓退了初学者. 3. 太高层的抽象造成语言难以理解, 比如 LISP, 抽象于 lambda 演算, 至今仍有不少人对于 Y-Combinator 的高层抽象表现出费解; 而对于精通函数式语言的人来说, Google 的 MapReduce 又显得那么自然. 不了解高度抽象的世界模型, 必然是如同看到满屏幕的乱码一样, 无法下手. 4. 太低的抽象造成语言难以使用, 如C, 在没有library 情况下, 链表都要手工构造. 即使想描述一个简单的思维, 都需要映射出很多不必要的底层抽象. 这样让语言的使用者主观上不倾向于用这套语言体系.

［我最近在学习法语, 其名词的性限制了我的表达, 继而限制了沟通. 因为假如我用错了, 别人会不懂. 因此触发了语言和思维的思考. 同时这几天, 我在考虑到底选择什么样的程序设计语言才是好的选择, 因此有抽象层次和语言表达能力的思考. 正巧有一本维特根斯坦的哲学逻辑在手边, 偶翻一下, 触发了思考, 故写下这篇随笔. 在语言选择方面, 我推荐 Python, 我认为它达到了抽象层次和表达能力的契合, 无论你是初学者, 还是高手］.

晚上和同学讨论了一个问题, 觉得很有意思, 贴出来.

假设一个带权有向图, 找 A 到 B 的最短路径显然是简单的, 如果权重没有负数的话, Dijstra’s Algorithm 瞬间就做完了. 现在问题略有变化了. 假设这个带权有向图已知, 但是边的权值不知道. 因为计算权值的代价太大, 所以如果有些边必然不在从 A 到 B 的最短路径上, 就没有必要计算这条边的权值. 那么, 问题是:

给定一个有向图和 A B 两点, 找出原来图的一个子图, 使得对于任意的边的权值赋值, 所有可能的最短路径都包含在这个子图中. (等价的说, 把所有不可能在最短路径上的边全部给移除掉)

大家想想办法, 我后天贴我们的算法 :)

[先说一下, 上次的语言识别程序的思路来自 Python Cookbook, 我只是略作修改, 并没有什么太大的贡献, 这个系列可能包含三到四篇文章. 底下我可能会用朴素贝页斯分类器再写一个然后比较两者效果]

以前我在翻译怎样写一个拼写检查器中, 就提到了(概率)语言模型这个东西. 什么是语言模型呢, 简单的说, 就是这个语言当中, 每个词出现的概率分布是有一定规律的, 与其他因素无关的. 如果我们要写一个汉语到英文的翻译器, 那么, 理论上说, 我们翻译器输出来的结果当中每个单词出现的概率, 应该和英文当中每个词出现的概率一样. 试想一下, the 这个单词在英文中常常出现, 而如果我们的翻译器对于任意汉语的翻译结果中, 故意调低或者错误设置 the 出现的概率, 造成翻译出来的结果几乎不出现 the, 或者出现的概率出奇的奇怪, 那么, 这段翻译出来的话, 它怎么看也不会像英语. 同样的道理, 一个拼写检查器可以把任意拼错的单词纠正过来, 在纠正过程中必须照顾到语言模型. 如果 teh 可以被改正为 the 和 tek, 那么我们应该优先考虑 the 才对, 因为 the 被使用的概率比 tek 大. (统计语言模型整体是很大的一块, 大家可以去读 Google 黑板报数学之美系列得到一个大致的感觉. 我这里只用到语言模型, 用不到条件概率)

基于这个假设, 我们自然的得到一个主意: 好呀, 假如两个文本的语言模型类似, 我们就认为他们是同种语言写成的. 对的, 怎么衡量这个类似呢, 我们可以用数学的方法: 统计任何两个语言模型之间的”距离”, 然后选取最小的. 这个地方距离随便怎么定义, 可以用向量夹角, 可以用欧式距离. 但是, 现实的问题不是这么简单. 首先, 如果每个词都对应一个词频的话, 得到的向量是高维的. 除非有一个包含各种语言单词的全集, 否则很难说这个向量一共要有多少个维度. 而且高维的随机向量还往往以很大的概率正交. 为了控制维度灾难, 一个简单的方法是使用每一个字节作为一个词统计. 这个模型虽然看上去很没道理, 而且还很”面向机器”, 但是考虑到计算机处理语言的时候本来也就是根据字节来处理, 这样做一下也未尝不可.

我并没有亲自实践比较字节频率然后计算向量距离的方法, 不过我可以想像, 这样的方法在UTF-8字符集上是有很好表现的. 有人可能会担心, 加入某个汉字编码成了两个字节, 这两个字节正好分别等于西文字母的编码的话, 汉字就可以在计算机中等价的写成一串字母了, 这样, 就很难保证一段汉字是不是和一段希腊文正好有同样的字节分布了, 因为我们可以作弊一下, 搞出一段汉字, 正好和希腊文对应分布一样. 但是, 巧妙之处在于UTF-8 字符集本身通过若干前缀区分了不同的变长编码, 不同的编码区段没有任何交集. 反过来说就是, 从UTF-8 编码的字节序列中任意取一个字节出来, 一定能够区分这个字节是某个变长编码的一部分. 任何一个多字节符号编出来的编码的一部分, 绝对不可能正好是其他单字节符号的编码. 这样, 单字节多字节变成字节编码后各自为政, 映射到的字节码的概率分布不会出现“作弊”现象. 用严格的数学语言来说就是, 一个字符对应的字节在叠加到向量中的时候, 绝对不会叠加到属于另一个字符的所有字节上, 也就是说, 他们总有独立分布的部分存在. 这个是字节模型能正确反映语言模型的一个必要要求.

[To be continued…]

ASPN Python Cookbook 提到了一个使用 zlib 库识别文本用哪种语言写成的程序. 其核心代码不超过20行, 据我观察, 识别精度不低于95％. 我略做了一下修改, 把联合国联合国人权宣言作为语料库，目前从 wikipedia 上随便抓一篇爪哇文的文章下来, 都能识别得九不离十。

class Entropy:
    def __init__(self):
		self.entro = []

    def register(self, name, corpus):
        “”"
        register a text as corpus for a language or author.
        <name> may also be a function or whatever you need
        to handle the result.
        “”"
        corpus = str(corpus)
        ziplen = len(zlib.compress(corpus))
        print name, ziplen
	self.entro.append((name, corpus, ziplen))

    def guess(self, part):
        “”"
        <part> is a text that will be compared with the registered
        corpora and the function will return what you defined as
        <name> in the registration process.
        “”"
        what = None
        diff = 0
        part = str(part)

        for name, corpus, ziplen in self.entro:
		nz = len(zlib.compress(corpus+part)) - ziplen
		if diff==0 or nz<diff:
                	what = name
        		diff = nz
        return what

先贴代码, 有时间细讲一下语言模型和信息论的妙用. 简单而小巧的模型解决看上去不可解决的问题， 这就是人工智能的精华.

[所有文件打包下载(包含语料源文件10Mb). 代码本身其实只有50行]

看到师弟蔡白银写的文章, 有所感, 写下几句不成文的心得体会.

大学读经典书, 能缩小自己和发达国家学生的差距. 我们国家的大学和发达国家相比, 差距大家也都能看到. 在理工科上, 或许中国大学唯一能和外国大学在同一起跑线的, 就是图书馆里面躺着的经典英文原版书了. 科学发展到今天, 每个领域都是枝丫茂盛, 都有经典的著作. 作为大学生, 如果没有读过(哪怕看看前言也行呀), 在我看来, 不算合格. 修身第一条, 就是读读经典.

要是上大学的时候只是全是靠课堂而不主动阅读, 这大学也和幼儿园没两样.

好书能帮你打通筋脉, 读了之后立即高屋建瓴, 建立起对一个领域的全盘认识. 我常常觉得, 好书大气磅礴, 就像武林名门正道功夫一样, 大开大阖, 读完以后人的气象都不一样. 读烂书, 或者上用烂教材的课, 会降低你的智商.不相信我这句话的人可以选择 TAoCP 读一下第一小节,再比较一下其他(本校)写数据结构和算法的书.

好的教材好比是心法, 提纲挈领. 先看心法是磨刀不误砍柴功的. 而可惜的是无论是市场还是实际, 砍柴的书都很受欢迎, 磨刀的书没人喜欢看. 很多做技术的都容易做到头, 就是因为没心法, 练不好72绝技的. 就计算机方面而言, 数据结构算法 (Intro. to Algorithm/TAoCP)看一本, 编程工具(TIJ/TIC++/SICP+Python)看一本, 离散数学(Concrete M/Discrete M)看一本, 足以秒杀大多数公司面试题了.

要善于利用中英对照, 好坏对照的比武看书法. 我并非崇洋媚外, 国内很多大学的教材, 存在很强的门户之见, 其教材主要内容囿于本校擅长的某些领域, 往往不能使人窥得一个体系的全貌. 因此最好的办法是找本英文的, 找本中文的. 英文书往往文字冗长, 实例繁多; 中文书往往讲空泛理论, 几乎无例子, 两者结合, 能够取长补短. 更有效的是想像两个作者在吵架, 并且将自己置于审稿人的地位, 跳出书本, 评点某处某书写得如何, 如果自己写该如何写等等. 如此一比武, 好书烂书高下立判, 而且能从一个更高的层次审视一本书. 一招一式学高手, 未必能成高手; 常看高手过招, 华山论剑, 你很快会变成高手.

书是要往厚处读的. 一本书, 哪怕只读一章, 也要保证从头读到尾. 如果没这个自信, 还是不要读了. 弱水三千, 只取一瓢, 与其说是走捷径, 不如说是纵容自己的浮躁和浅尝辄止. 这样读书, 基础不牢. 好比光看别人拳法打的好看, 自己不下功夫从头到尾把拳法演练几遍, 很快就会忘掉的. 我认识不少人, 书往往看得很多, 但考试面试或者实际运用的时候, 和没读过没两样. 结果如此, 那当年读了干啥?

–推而广之, 书上的程序和习题是要一条一条做的. 我认识一个高中朋友, 他说物理不好. 我给他出了个主意: 只做一本书上的习题, 而且一丝不苟, 从格式到步骤都要完美, 假想自己是写本能出版的习题解. 他尝试了几个星期, 单科成绩已经是年级第一了. 往往看上去最笨的方法, 实际上是最聪明的. 就我个人而言, 高年级小学生一笔一划写完初中平面几何只要一年半, 老师讲要三年; 完全不懂OO的大一新生一键一键敲完 Thinking in Java 上的所有程序只要半学期, 就能独步于10万行代码的中型项目. 而很多人学 4 年 Java 也不知道架构到底是什么样子的.

如果我没记错的话, 侯捷在 STL 源码剖析的序言中, 引用了老子的一句话: “天下大事，必作于细”. 我觉得, 能将这句心法读到, 又有什么不能剖析的源码呢. 纵使若干年后, STL 丢在历史某处, 你仍然能够在新的技术中”游刃有余”.

补充: 有很多辅助手段能帮人选书. 我的选法是: 互联网. 判断一本书(我特指数学或计算机方面的教材)是不是好书太简单了, 看看这本书作者如何, 这本书反馈如何. 如果有网页的话, 看看 Google 给这本书的 PageRank 是多少. 尽量选择国外一流大学的教材. 一般情况下, 国内出版的教材, 如果不是清华北大中科院或者这方面的杰出专家出的, 可直接略过. 少买几本庸书, 是为抵制全球变暖和保护森林做贡献.

当然, 说的这些, 都是一己之见. 我知道大家都很”快餐阅读”. 但愿看这篇文章的, 和能认真做到的比例, 能到10:1, 也就行了.

I take Computer Architecture course this semester and study basic VHDL for digital design. The instructor recommends ModelSim with both Windows and Linux versions. But unfortunately, ModelSim for Linux can only be installed on RH Linux. I tried to install it on Ubuntu but obviously it didn’t work. It turned out that the only solution would be using ModelSim for Windows in our computer lab. But as a dead-head Linux fan, I simply want to find alternative software to get things done on Linux platform. After some googling and asking help from friends, I found two handy software packages that form a tool chain to do VHDL simulation on Linux: GHDL and GTKWave.

What

GHDL is an amazing package that it employ gcc and compile VHDL code to objective code. It can’t translate your design into a netlist but it’s sufficient for us to do the simulation.
GTKwave is another tool which can help you view the wave form dumped by GHDL simulation. There two, in principle, can help you handle all the VHDL simulation tasks involved in a one-semester-course like computer architecture.

How

Build the tool chain

If you are using a Debian family (Debian/Ubuntu, etc) Linux, an apt-get will save your life. Try:
apt-get install ghdl
and
apt-get install gtkwave.
[You might need sudo or run it as root.]

If you not, try to download the package and read the README. It’s easy. If you want to install it on Mac as what I’ve done, remember to install X11. The whole procedure should take you less than five minutes.

How to use it

It’s very simple. GHDL will compile the VHDL code for you to object code and convert it to executable. For example, if I have CPU.vhdl which is a simple computer description. Try to type:

ghdl -a cpu.vhdl

to compile it, and

ghdl -e cpu

to make executable file (do linking).

Finally you can use

./cpu --help

to see how to run it.

Some tips:
If you include ieee package, add this option: –ieee=synopsys
If you want to let the simulation run certain amount of time, use something like

./cpu --stop-time=100ns

If you want to dump a signal wave format for gtkwave, just add –vcd=vcd.file

After that, you can use

gtkwave vcd.file to see the wave. You might need to add all the signals to the wave window via “Search->Signal Search Tree”.

Why

You might ask why it’s handy than ModelSim. It’s obvious. For example, if you write a shell script that can issue all the compiling/dumping/viewing command in the right order, you only need two keyboard stoke to run a test, in comparing with in ModelSim, where you need to do at least 10 mouse click and maybe type these commands:

view wave
add wave -r /*
"set format, etc"

Finally, you can use GHDL as your VHDL code formatter and get a very nice HTML format for your neat code. You can now make it even neater, why not :)

Some really missing features for these small tools.

1. Non-standard signal watch.

If you have a signal which is an array, it’s not handy to view the wave as ghdl doesn’t actually output the signal changing information for this signal.

2. Automatic dependency solving.

Currently GHDL will complain about the dependency, but it doesn’t actually handle this like GNU make. Therefore, you have to either write your own makefile to use make to manage your code dependency, or recompile all the code every time.

My example code of a silly CPU:

    1 – CSE 560 Homework, a simple CPU
    2 – Eric You XU
    3 — version 0.05
    4
    5 library ieee;
    6 use ieee.std_logic_arith.all;
    7 use ieee.std_logic_signed.all;
    8 use ieee.std_logic_1164.all;
    9
   10 entity CPU is
   11         port (  IR      :       in std_logic_vector (31 downto 0);
   12                 READY   :       in bit;
   13                 CLK     :       in bit
   14                 );
   15 end entity CPU;
   16
   17 architecture behav of CPU is
   18     type reg_type is array(0 to 255) of std_logic_vector(31 downto 0);
   19     signal storage: reg_type;
   20
   21     signal d1, d2: std_logic_vector(31 downto 0);
   22     signal raw1, raw2: std_logic_vector(31 downto 0);
   23     signal s1_int, s2_int: integer;
   24     signal prod: std_logic_vector(63 downto 0);
   25     signal status:      std_logic_vector(1 downto 0);
   26     signal phase:       bit;
   27     signal index:       integer;
   28     signal opcode:      std_logic_vector(2 downto 0);
   29     signal needd2:      bit;
   30
   31 begin
   32
   33
   34
   35 process(clk)
   36    begin
   37     if (ready=‘0′) then
   38         phase <= ‘0′;
   39 – For test
40 storage(0) <= X”00000004″;
   41 storage(1) <= X”FFFFFFFD”;
   42 storage(2) <= X”01010103″;
   43 storage(3) <= X”0F0F0F08″;
   44 storage(4) <= X”F0F0F0F0″;
   45 storage(5) <= X”FFFFFFFF”;
   46 storage(6) <= X”00000000″;
   47 storage(7) <= X”0000000E”;
   48 storage(8) <= X”00000004″;
   49 storage(9) <= X”DEADBEEF”;
   50
   51      else
   52        if(clk’event) then
   53           if(clk = ‘1′) then                    – CLK _| 
   54               if(phase = ‘0′) then              – state 1, read instructions
   55
   56                   opcode        <=      IR(26 downto 24);
   57                   – 31 30 29 28 27 26 25 24: Lower 3 bit
   58                   raw1 <= storage(ieee.std_logic_unsigned.conv_integer( IR(23 downto 16) ));
   59                   raw2 <= storage(ieee.std_logic_unsigned.conv_integer( IR(15 downto 8) ));
   60                   – RAW Hazard 
   61                   –avoid to use s1_int = con_int(raw1)
   62                   s1_int        <=      ieee.std_logic_signed.conv_integer(storage(ieee.std_logic_unsigned.conv_integer( IR(23 downto 16) )));
   63                   s2_int        <=      ieee.std_logic_signed.conv_integer(storage(ieee.std_logic_unsigned.conv_integer( IR(15 downto 8) )));
   64                   index <= ieee.std_logic_unsigned.conv_integer(IR(7 downto 0));
   65
   66               else                              – state 3, write register files
   67                 case opcode is
   68                         when “000″ => – ADD
   69                                 storage(index) <= d1;
   70                         when “001″ => – SUB
   71                                 storage(index) <= d1;
   72                         when “011″ =>
   73                                 storage(index) <= d1;
   74                         when “100″ => – INC
   75                                 storage(index) <= d1;
   76                         when “101″ => – DEC	
   77                                 storage(index) <= d1;
   78                         when “010″ => – MULT
   79                                 storage(index) <= prod(31 downto 0);
   80                                 d2 <= prod(63 downto 32);
   81                                 d1 <= prod(31 downto 0);
   82                                 if (index = 255) then
   83                                          storage(0) <= prod(63 downto 32);
   84                                 else
   85                                          storage(index+1) <= prod(63 downto 32);
   86                                 end if;
   87                         when “110″ => – DIV
   88                                 storage(index) <= d1;
   89                                 if (index = 255) then
   90                                          storage(0) <= d2;
   91                                 else
   92                                          storage(index+1) <= d2;
   93                                 end if;
   94                         when others =>
   95                                 report “Invalid OpCode.” severity FAILURE;
   96                   end case;
   97              end if;
   98
   99            else                                 – CLK |_		
  100               if(phase = ‘0′) then              – state 2, ALU step
  101
  102                   case opcode is
  103                      when “000″ =>  – ADD
  104                                 d1 <= conv_std_logic_vector((s1_int + s2_int), 32);
  105                                 needd2 <= ‘0′;
  106                      when “001″ => – SUB
  107                                 d1 <= conv_std_logic_vector((s1_int - s2_int), 32);
  108                                 needd2 <= ‘0′;
  109                      when “011″ => – COMP
  110                                 d1 <= conv_std_logic_vector((-s1_int - 1), 32);
  111                                 needd2 <= ‘0′;
  112                      when “100″ => – INC
  113                                 d1 <=  conv_std_logic_vector((s1_int + 1), 32);
  114                                 needd2 <= ‘0′;
  115                      when “101″ => – DEC
  116                                 d1 <=  conv_std_logic_vector((s1_int - 1), 32);
  117                                 needd2 <= ‘0′;
  118                      when “010″ => – MULT
  119                                 – If I assign the prod value to d1 and d2 here, a RAW hazard will occur.			
  120                                 prod <= raw1 * raw2;
  121                                 needd2 <= ‘1′;
  122                      when “110″ => – DIV
  123                                 d1 <= conv_std_logic_vector((s1_int/s2_int), 32);
  124                                 d2 <= conv_std_logic_vector((s1_int rem s2_int), 32);
  125                                 needd2 <= ‘1′;
  126                      when others =>
  127                              report “Invalid OpCode.” severity FAILURE;
  128                   end case;
  129
  130
  131                   phase <= ‘1′;
  132                else                             – state 4: NOP, Increase PC, etc.
  133
  134                   – Set STATUS —
  135                   status <= “00″;
  136                   if(needd2 = ‘0′) then – only look at d1
  137                       if d1 = X”00000000″ then
  138                           status <= “01″;
  139                       end if;
  140                       if d1(31) = ‘1′ then
  141                           status <= “10″;
  142                       end if;
  143                       if d1 = X”FFFFFFFF” then
  144                           status <= “11″;
  145                       end if;
  146                   else – needd2 = 1
  147                      if d1 = X”00000000″ and d2 = X”00000000″ then
  148                          status <= “01″;
  149                      end if;
  150                      if d2(31) = ‘1′ and opcode = “010″ then            – high order bit of mult is 1
  151                         status <= “10″;
  152                      else
  153                         if d1(31) = ‘1′ and opcode = “110″ then         – high order bit of div is 1
  154                            status <= “10″;
  155                         end if;
  156                      end if;
  157                      if d1 = X”FFFFFFFF” and d2 = X”FFFFFFFF” then
  158                          status <= “11″;
  159                      end if;
  160                   end if;
  161                   ——————
  162
  163                   phase <= ‘0′;
  164               end if;
  165           end if;
  166        end if;
  167     end if;
  168
  169 end process;
  170 end architecture behav;

Continued with the last post

Some readers reported that if using graph_search to solve the NQueensProblem provided in search.py, python will complain that:

TypeError: list objects are unhashable

Yes, you are doing perfectly right and the code itself is imperfect. As this point, you might want to make the List objective hashable. Inspired by the idea of Set and FrozenSet in Python, you would expect a frozen(x) function to make any mutable object immutable (and therefore hashable) [Or you can try to use tuple from beginning, but in the NQueensProblem code, it uses .index method, which is only suitable for List]. Unfortunately, this proposal (PEP-351) was rejected by Guido. Hence, we don’t have a unified way to convert any “state” to an immutable object and insert it in to “closed table”. One possible way to do this is to write your own State class and implement the __hashcode__ function. The other handy but awkward way is to convert the list to a tuple when insterting to the “closed table, i.e. edit Line 144 of search.py as:

if tuple(node.state) not in closed:
closed[tuple(node.state)] = True

Here is a toy forzen function.

“”"Toy function frozen which can convert mutable objects to immutable
	Author: Eric You XU.
	GPLv2
“”"

def frozen(x):
	“”"Return the immutable version of an object.
	“”"
	if type(x) == type([]):
		return tuple(x)
	elif type(x) == type([]):
		raise “I can’t froze dictionary object as they are very hot.”
	# fill your type here
	else:
		return x

You can put it in to search.py and edit the Line 144 as:

if frozen(node.state) not in closed:
colsed[frozen(node.state)] = True

Now the code looks much better.