数码鹭岛论坛

标题: 编程珠玑番外篇 [打印本页]

作者: 翔子 时间: 2010-5-24 15:12
标题: 编程珠玑番外篇
编程珠玑番外篇-1.Plan 9 的八卦
原文:http://blog.youxu.info/2008/10/06/about-plan/

在 Windows 下喜欢用 FTP 的同学抱怨 Linux 下面没有如 LeapFTP 那样的方便的工具. 在苹果下面用惯了 [url=http://cyberduck.ch/]Cyberduck 的同学可能也会抱怨 Linux 下面使用 FTP 和 SFTP 是一件麻烦的事情. 其实一点都不麻烦, 因为在 LINUX 系统上压根就不需要用 FTP. 为什么呢? 因为一行简单的配置之后, 你就可以像使用本机文件一样使用远程的任何文件. 无论是想编辑, 查看还是删除重命名, 都和本机文件一样的用. 这么神奇的功能到底如何使用呢, 待我一一道来.
首先, 如果你的内核版本是 2.6.14 或者更新(uname -r 可以查看你的内核版本), 你的机器上的已经有了这个支持了. 在这种情况下, 你可以使用:
sudo modprobe fuse
激活内核模块. 然后, 比如说, 你想SSH远程 remote.com 上的 /dir 目录, 作为本机的 ldir 目录, 你可以使用:
sshfs name@remote.com:/dir /ldir
然后, 您就可以完全在 ldir 目录下操作任何的远程机器上的文件了. 是不是很简单

如果要使用 ftp, 我们要使用一个叫做 curlftpfs 的开源软件. 幸运的是, 你可以直接使用 apt-get install curlftpfs 直接得到他.
安装结束后, 我们依然使用
curlftpfs ftp://user:pass@ftp.remote.com/dir ldir/
就可以把远程的目录当成本地的目录一样使用的. 拷贝啊重命名啊都可以. (当远程的内容直接能被你访问的时候, 谁拷贝啊

说到这里, 聪明的读者肯定要说: 靠, 远程的文件都能当成本机的用, 那太好了, 整个互联网就是我的磁盘嘛. 你还真说对了, 对于一个用户来说, 协议是不重要的, 重要的是数据. Gmail 不是有N个Gb的大小么, 让我们直接把 gmail 当磁盘好了. 于是有了 [url=http://richard.jones.name/google-hacks/gmail-filesystem/gmail-filesystem.html]Gmail FS. 这样, 你可以给你的邮件标题做支持正则表达式的查找噢

除此, 还有 [url=http://wikipediafs.sourceforge.net/]wikipediaFS, 可以用自己喜欢的编辑器直接编辑维基百科的文章. 还有 [url=http://manishrjain.googlepages.com/flickrfs]flickrFS. 直接用自己喜欢的编辑器可以编辑图像元信息, 还能 chmod 754 让图像只能被朋友访问噢 :)
以上的这些酷实现, 都是 [url=http://fuse.sourceforge.net/]FUSE 这个内核模块作为基础支持的. 那么, 这个牛逼的网络也是文件的点子是哪个牛逼的人想出来的呢? 答案是 UNIX 的发源地, 贝尔实验室. 确切的说, 是在设计 UNIX 的继承者– [url=http://en.wikipedia.org/wiki/Plan_9_from_Bell_Labs]Plan 9 的过程中提出来的. (小八卦: UTF-8, 就是世界上现在最通用的字符编码体系, 就是 Plan 9 操作系统的一个副产品).
一切都是文件这个点子倒不是什么新的点子, 在 The Unix Programming Environment 这本圣经里面就旗帜鲜明的打出 “UNIX下一切都是文件”的旗号. 但是毕竟旗号是旗号, 现实是现实. 关于文件的抽象在其后的发展中发现了这样那样的局限, 于是恶名远扬的 ioctl 函数被引进系统. 所以口号是口号, 实现是实现. 显然当初设计 UNIX 的几个哥们很不满意, 所以搞了一个 Plan 9 (搞 Plan 9 的人就是写 The Unix Programming Environment 的人). 在 Plan 9 系统中, 一切都是文件, 显卡是文件, 内存是文件, 进程是文件, 网络是文件…
等等, 熟悉 Linux 的用户要说了, 在 Linux 下面, 进程的确是文件啊. ls /proc 就能看到当前所有的进程, 不也是文件么. 是呀, Linux 这个就是和 Plan 9 学来的. 但是 Linux 学得不彻底, 因为这个文件系统的访问接口并不完整: 你不能通过 rm 一个文件杀死一个进程. 也不能通过 cp 拷贝出一个进程. 而在 Plan 9 上, 你不光能通过普通的文件操作命令去控制进程, 你还能 mv 一个进程. 我们刚才说了, 进程就是文件, 还能把其他机器上的文件当成本机一样用. 屏幕前聪明的你肯定一下子悟到了: 一定这居然是一个分布式的操作系统啊! 在这个系统里, 进程可以被其他计算机看到, 并且控制. 而管道可以横跨不同机器的不同进程, 这简直是把单机的概念都给抹杀了, 简直就是”网络就是计算机啊”.
熟悉互联网的读者都知道最近炒得很热的云计算啥的, 对用户无非就是互联网作为硬盘, 对公司无非就是分布式的操作系统协同工作, 在屏幕前的您肯定如我一样, 一拍大腿说: 靠, 贝尔实验室养得不是计算机科学家, 而是一大批未来学家啊. 30多年前人家搞互联网, 而今我们用互联网. 20年前人家用GUI, 如今我们用GUI. 10年前人家搞云计算, 而今我们炒概念闲扯淡. 差距啊.
说到这里就到了今天技术八卦的尾声了: 当年设计 Plan 9 的牛人 bwk 和 Rob Pike 等哪去了?
bwk (别查了, 就是那个写 C语言书的, 写AWK的) 年纪大了去普林教书了(人家本科生能不牛逼么). 而 Rob Pike 年轻, 风华正茂正当时. 您想,对于那些做云计算的大公司来讲, 这么牛逼的人哪能落入对手手中? 您这么想的, Google 也是这么想的. Rob 同学现在在 Google 研究院很爽的做着主力工程师呢. (小八卦, 他是Google 中唯一享有单字母邮箱的: r@google.com).

作者: 翔子 时间: 2010-5-24 15:15
标题: 编程珠玑番外篇-2.计算机图书排版的八卦
原文: [url=http://blog.youxu.info/2008/10/13/trivia-about-computer-typesetting/]http://blog.youxu.info/2008/10/13/trivia-about-computer-typesetting/

大家都知道, 计算机科学家超级爱动手自己开发工具, 而且对美有超乎常人的需求. Knuth 爷爷当年觉得自己辛辛苦苦的好书被排版成地摊上的厕纸一样, 一怒之下自己搞出了红遍大江南北的 TeX. 从此整个世界都清净了. 排版是计算机科学家研究的一个很好玩的领域, 这篇文章就谈谈我所知道的关于排版的八卦.

先说 Knuth 爷爷的吧. 首先, 是在设计 TeX 的过程中, 这位老爷爷研究了很多著名的字体, 成了名动一时的字体专家, 据说和乔布斯并称为加州最懂字体设计的两个搞IT的 (我瞎说的). 研究字体之余, 他就研究收集各大书法家的作品, 然后这位老爷爷又是一个基督教徒, 所以干脆用它的收藏出了一本书, 叫做 <3:16>. 这本书特别牛逼, 是一本用计算机科学研究上帝存在的. 而且发挥计算机科学的小幽默, 取圣经每章的第3节第16小句, 还证明了这个和随机一样好.

还是克爷爷, 写完TeX之后不过瘾, 要写本书来冲冲喜, 于是写出了极其牛B名字的 The TeXbook. 一语双关, 表现了牛人一贯的狂妄. 写完这个他又想写写自己的字体和绘图系统设计(metafont 系统) 所以干脆出了五卷书, 行话称作ABCDE, 也是用名字来表明: 看, 基本的入门书, 你非看不可.

跑题一下: Knuth 爷爷最喜欢让人家看到他提出的名字就腿发软. 比如他提出了一个叫做 Literate Programming 的东西, 并且很不怀好意的对 Dijkstra 说, 小样, 当年你说 structured programming 的时候我非要用 goto, 结果人家都说我是 unstructured programming (没结构的编程), 现在我要提出一个叫做 literate programming 的东西, 你要是不跟着我混, 人家就会叫你 illiterate programming (没文化的编程). 在这么邪恶的名字下, 全世界程序员只好个个听这个老头的话, 乖乖的使用文档和程序融为一体的”有文化的”编程习惯.

其实克爷爷属于斯坦福家族的. 在70-80年代, 世界上还有一个NB的研究机构: 贝尔实验室. 贝尔实验室自己也开发了自己的排版工具: Troff. 开发者是著名的K, 就是 K&R 里面的那个K. 这个 Troff 也是一个牛到极点的排版软件, 比如说, 当年那些科学家都对出版社的排版不满意, 所以都威胁出版社说: 我自己来排版, 你们只管印刷就行了. 就是因为这帮科学家开了这个传统, 所以后来出版商遇到想自己排版的, 都用巨崇拜的眼光打量着你.

说到 troff, 以下大名鼎鼎的书都是用 troff 排版的:

Advanced Programming in the UNIX Environment
The AWK Programming Language
The C Programming Language
Compilers: Principles, Techniques, and Tools
Computer Networks, 3rd Ed.
Computer Networks And Internets, 3rd Ed.
The Design and Implementation of the 4.4BSD Operating System
Effective TCP/IP Programming
The Elements of Programming Style, 2nd Ed.
Internetworking With TCP/IP Volume 123
More Programming Pearls
The Practice of Programming
Software Tools
Unix Network Programming
The UNIX Programming Environment
Programming in C++

所以说, troff 排版的无烂书. 当然, TeX 家族也不是吃素的, SICP, TAoCP, CLRS 都是用 TeX 搞出来的. 陶哲轩也说, 鉴别民科文章第一步就是看是不是用TeX排版的. 可见排版排得专业, 也是好文章的一个先决条件.

我觉得可以把以上的结论概括成徐氏排版定理, 如果一本书, 不是以上所说两个软件排版的, 又不是 O’Relly 出版的, 那是好书的概率也就不怎么大了. 作为一个作者来讲, 一定要记得用 troff 或者 latex 排版

troff 和 latex 都是一脉相承的, 理念也差不多, 所以牛B的开发人员两头都在玩, 比如一个叫做 Werner Lemberg 的牛人, 就是 troff 的开发人员, 同时还跑到 TeX 那里开发了支持中日韩的 CJK 包. (大家都知道, 软件的中文支持从来都不是中国人开发的)

史上最牛的程序员 Bill Joy 同学据说用了一个周末就写出了 vi, 所以大家都怀疑, 他用了半个小时的时间写了 BSD 上的 troff. 他写的这个程序, 被SUN用着, 一直用到今天.

最后强行插播一条广告: 我最近要写一本小册子, 叫做 Motifs in Computer Science (原名叫 Meta Ideas in Computer Science). 一定保证用 LaTeX+Troff+reStructuredText 排版, 按照我的 Troff/Latex 排版无烂书结论, 这本书也不是太烂. 欢迎捧场.

再补充一则八卦: 话说当年 PDP-11小型机特别贵, 但是贝尔实验室的科学家又想要用. 怎么办呢? 于是, 他们发挥了科学家爱忽悠的能力, 去和经理说: 你看, 我们文档的排版很烂吧(当年还是打字机时代), 你们投资一下搞一个小型机回来, 我们保证给你们开发一个在这个机器上用的文档排版系统. 经理一听, 大笔一挥说: 买之!. 科学家一听都乐了, 哈哈, 我们有新玩具了. 然后, 他们就开始在 PDP11 上开发 UNIX 了. 经理也不懂, 看他们搞的好玩, 就不时来问问: 老大们, 排版系统怎么样了? 贝尔的科学家一边敷衍敷衍, 一边继续搞 UNIX 和 C 语言. 等这两样都搞好了, 瞬间就写了一个排版软件, 就是 nroff. 经理可乐了, 说, 哎, 我们终于投资有回报了啊. 科学家也乐了, 因为若干年之后, C 和 UNIX 红遍大江南北, 因此两人拿下图灵奖. 所以说, 做研究这东西, 一定要先把基金忽悠过来, 然后想干啥干啥, 最后结果反而超出预料. (贝尔实验室的人居然研究宇宙背景辐射拿诺贝尔奖, 这种宽松宽容的基础研究在其他地方是很难遇到的).

作者: 翔子 时间: 2010-5-24 15:17
标题: 编程珠玑番外篇3 — 关于程序优化的八卦
原文: http://blog.youxu.info/2008/11/13/anecdotes-about-program-optimization/

(把八卦和文章重新分了一下类, 准备围绕自己的心得写个编程珠玑番外篇, 这个算第三篇吧)

<代码大全> (Code Complete) 是一本很好的书. 我建议像我这样写的程序总行数不超过50万的程序员应该买一本放在案头 (当然<代码大全> 不如 <Software Tools> 这本书好, 这个我以后有机会写文章细谈) 如果你天天编程序, 我建议你买一本. 如果你已经有了<代码大全>, 我诚心建议你赶快翻开此书, 撕去第26章. 因为代码大全的其他章节可以让你成为优秀的程序员, 唯独第26章, 读了之后立即从优秀程序员变成最差的程序员.

为啥? 因为第26章讲的, 都是怎么调节代码使得代码跑得更加快的技巧, 而这些技巧, 几乎都是让一个好程序变成差程序的技巧, 是教你不管三七二十一先对程序局部优化的技巧. 而局部优化是让程序变得糟糕的最主要的一个原因. 用高爷爷的话说, 提前优化是万恶之源 (Premature optimization is the root of all evil). 这些技巧, 就是带你去万恶之源的捷径.

代码优化究竟是什么洪水猛兽, 又究竟有多少伟大的程序员因为代码优化声名扫地, 请看本期关于代码优化的八卦.

话说当年在贝尔实验室. 一群工程师围着一个巨慢无比的小型机发呆. 为啥呢, 因为他们觉得这个机器太慢了. 什么超频, 液氮等技术都用了, 这个小型机还是比不上实验室新买的一台桌上计算机. 这些家伙很不爽, 于是准备去优化这个机器上的操作系统. 他们也不管三七二十一, 就去看究竟那个进程占用CPU时间最长, 然后就集中优化这个进程. 他们希望这样把每个程序都优化到特别高效, 机器就相对快了. 于是, 他们终于捕捉到一个平时居然占50% CPU 的进程, 而且这个进程只有大约20K的代码. 他们高兴死了, 立即挽起袖子敲键盘, 愣是把一个20K的C语言变成了快5倍的汇编. 这时候他们把此进程放到机器上这么一实验, 发现居然整体效率没变化. 百思不得其解的情况下他们去请教其他牛人. 那个牛人就说了一句话: 你们优化的进程, 叫做 System Idle.

所以说. 优化这东西, 一定要有一个全局的思路, 否则就是纯粹的无用功, 有时候还是负功. 在<编程珠玑 II> 第一章, Jon Bentley 就着重提醒了代码 profiling 的重要性. 说到 profiling 这个词, 就不能不再次提到万众敬仰的高爷爷. 高爷爷在1970年的暑假, 通过捡Stanford 大学机房扔出来的垃圾(其实是含有程序的磁带), 写出了一篇震古烁今的论文 “An empirical study of FORTRAN programs” (FORTRAN 程序的实证分析). 除了抱怨写程序的人不看他的 TAoCP 之外(因为一个程序用了被高爷爷定性为史上最差的随机数发生器算法, 有兴趣的可阅读 TAoCP vol2), 这篇论文主要说了三个划时代的东西:

1. 对程序进行 profile 是每个编程系统的居家旅行必备.

2. 在没 IO 操作的情况下, 一个程序中 4% 的代码占用了超过50% 的运行时间.

3. 97% 的情况下对程序进行提前优化是万恶之源.

这三个道理, 用大白话说, 就是: 1 程序都存在热点, 有优化的空间. 2. 但是97%的情况下程序员优化的都是错的地方, 反而把程序优化糟了. 3. 想要做优化, 第一步就要先知道程序在什么地方耗时间而不是靠猜.

说到热点, 顺带拐八卦一下Java的速度. Java 1.5 的虚拟机的关键技术, 就是叫做 Hotspot (热点). 传统上, 大家都认为 Java 比C 要慢. 其实不然. Jython 的作者 Jim Hugunin 就曾经说过, 其实两者差别不大 (http://hugunin.net/story_of_jython.html). 也有一些其他的测评说, Java 比 C 要快. 原因就在于, Java 虚拟机能够找到热点, 对热点专门做优化. 而C程序编译好了, 即使有热点, 也只能靠CPU去优化了. Java 的优化比 CPU 要深且更全局.

言归正传. 关于 FORTRAN 的 profile 的传统被继承了下来, 基本上现在任何的过程式主流编程语言都支持 profiling 工具. 关于 profile 怎么做的问题, 等我有空了好好写文章介绍. (因为我发现, 除了编程珠玑, 没有一本书提到过).

做程序优化的八卦就太多了, 说一个Beautiful Code 上的吧. 话说世界上做线性代数的库叫做BLAS, 基本上是工业标准. 因为线性代数运算太重要了, 所以各大处理器厂商都有 BLAS 的实现. Intel 的叫 MKL, AMD 的叫 ACML. 矩阵乘法实现的好坏, 直接决定了处理器的性能测试的分数(因为现代测处理器的速度的程序, 比如LAPACK指数, 基本上都是用 BLAS 里的矩阵乘法做基准). 去年 nVIDIA 高调宣传自己的 CUDA 系统比CPU厂商快10倍到100倍, 借此打开了GPU计算的大门(令人发指的达到500GFlops, Intel 最新的只有50GFlops). 其中 CUDA 可以理解为是 BLAS 在 nVIDIA 平台上的实现. 自从nVidia 推出 CUDA 以后, 俨然不把 intel 这些厂商放在眼里, 心想, 小样, 你们还是做通用处理器吧, 浮点乘法这些高级的东西, 还是放在显卡上比较好. nVidia 和 IBM/SONY 的阴谋很不小呢. 要是浮点计算比 Intel 快这么一两个数量级, 以后世界上前五百名超级计算机就全部变成什么用光纤网连起来的 PS3 机群, nVidia 显卡机群之类的. 人家外行见了计算机科学家肯定要问: 你们搞高性能计算机究竟是搞计算还是打网络游戏啊??

还是言归正传(我怎么老走题?), 简要的说一下 BLAS 优化. 单处理器上对 BLAS 的优化主要体现在对 cache 的高效使用. 矩阵乘法中, 如果矩阵都是按照行存储, 则在A*B中, 对B的访问是按列的. 假设B一行有N个元素, 那么在存储器中, 两个同列不同行的元素所在的存储单元相差N. 因此, 对B的访问并不是局部化的. 因为访问不局部化, 所以每次乘法, 都需要从内存中调一个 cache 单元到CPU. 这个极大的降低了处理器的执行速度. 因此, 矩阵乘法的优化的核心, 在于局部化B的访问. 反过来, 如果矩阵按照列存储, 则要局部化对A的访问. 关于怎样局部化访问还能获得正确的乘法, Beautiful Code 一书的第14章有非常好的讲解, 我就不废话了. 总之, 矩阵乘法局部化的好坏, 取决于一个机器的 cache 的大小.

多处理器和向量处理器就又不一样了. 要想利用好, 就要把计算任务平均的独立的分到不同的处理器上. 所以, 在这里, 优化就变成了分解成若干的小问题. 因此, 分治算法成了主流. 具体矩阵乘法怎么分块, 大学数学都讲了, 我就不废话了. 事实上, 之所以 nVidia 能和 Intel 干, 就是因为显卡上令人发指的有 64 个计算核心, 而 Intel 最牛X的才 4个. 那为啥 Intel 自己不多做几个核心呢? 因为 Intel 自己把自己带沟里去了 — Intel 处理器太复杂支持的功能太多了, 一块硅片上根本放不下很多核心. 而 nVidia 一直就是专用处理器, 每个核心功能简单, 可以做到很小.

Beautiful Code 第14章就是讲了随着计算机体系结构的变化, BLAS 是怎么进化的. Tanenbaum 曾经说过, 随着一个科技的出现, 某个 idea 可能就销声匿迹了. 但是说不定下一波科技再来的时候, 这个 idea 又复活了. BLAS 从串行, 到向量, 再到串行(带cache的RISC), 再到向量(Cell), 就是一个绝好的例子. 对这个进化史感兴趣的读者不可错过这一章妙文.

作者: 翔子 时间: 2010-5-24 15:19
标题: 编程珠玑番外篇-4. Linux 下的 Facade 程序
原文: [url=http://blog.youxu.info/2008/11/17/facade-commands-in-linux/]http://blog.youxu.info/2008/11/17/facade-commands-in-linux/

Linux 下的命令行工具大致有两个流派, 一是以小而精见长的, 只能提供一个简单的小功能. 比如 yes 这个命令, 除了输出一大串永不停止的 y 之外毫无用处. 这个工具看上去土, 很没用处的样子. 碰到要你一路回车法的时候, 这个工具就大大的有用. 所以我每次帮人使用一路回车法装 windows 的时候, 就怀恋 Linux 下的这个 yes. 过一个管道, 就省去了在电脑面前按下几百次 y 的繁复工作.

还有一种工具, 是我今天要说的重点. 这种工具一般是一个简单的命令行调用, 却有着几十种甚至上百种不同的参数的组合, 用这些参数能搭配出谁也没用过的功能. 以 gcc 为例, 居然有两百多个不同的命令行参数, 范围涉及到程序编译, 连接设置, 库设置, 优化, 报错信息, 调试信息等等, 任何一个正常的人想要穷尽学完这些参数都是不可能的. 同样的库还有 convert (图像转换的), ffmpeg (视频处理的), curl (内容抓取的). 看上去这些参数指示的功能乱七八糟的堆砌在一起的样子, 仔细一想这些功能的确是相互关联的, 所以被放到了一个工具之下. 这些工具和上面的工具的哲学是反其道而行之的: 集一大类功能于一个工具, 任何类似的操作都能通过这个一个命令+不同的参数来完成, 而非”do one thing, do it well”. 这些工具和传统意义上的 UNIX 工具哲学是不大像的. 为了区分他们, 我把它们叫做 Facade 工具, 因为这些工具的设计哲学很类似于 Design Pattern 里面的 [url=http://en.wikipedia.org/wiki/Facade_pattern]Facade Pattern (Facade 模式的核型是用一个统一的接口管理对一个系统的访问. 比如 gcc 就是对整个编译系统的接口, ffmpeg 就是对整个视频处理系统的接口, display 就是对整个 X 显示系统的接口等等.)

之所以区分这两者, 是我体会到: 在具体的学习过程中, 对付两者的学习方法是截然不一样的. 学习小工具, 基本上就是学一个简单的名字到功能的定义, 加一些简单的参数. 除了名字比较别扭外, 使用很方便, 学习曲线不陡峭. 学习的要点不在于这些小工具本身, 而在于利用管道和其他工具通信(小工具从来就不是单独使用的, 比如 yes, 比如 tr, 我几乎没见过不用管道的情况下用他们的); 和上面相反的是, 我几乎没见着 Facade 工具用在管道里面的.

原因是 Facade 工具基本上是一个自成体系的完整的操作方式, 就像一个新的领域的一种新的”语言”一样. 因此, 不掌握一点基本的编译知识, 就不可能把 gcc 玩转, 因为那些参数的含义的理解, 都是需要相应知识的. 我也常常看到不少做 Web 程序的哥们对 curl 的每个边边角角都很熟悉, 但是对 gcc 不太熟, 这也是很正常的, 因为 Facade 程序本来就是属于面向一个特定领域的工具.

我在学习这两种截然不同的工具的时候也曾感到过困惑: 怎么有的程序这么多参数, 全学会怎么可能. 在浪费了不少时间乱看这些 Facade 程序的 man 文件之后, 我认识到: 除非我写操作系统, 要让我的程序编译的时候有几百个参数, 否则, 简简单单的用 gcc 常用参数就能解决99%的问题了. 我觉得, Facade 程序的要点正是在于, 用一些简单的参数组合(更多情况下其实不要参数) 就可以完成 90% 的常用例子. 至于剩下的 10%, 遇到了再去查文档就行了. 同时, 对于不在自己”常用工具集”中的一些 Facade 工具, 认真学习他们的用法是一件非常耗时且几乎没有任何收获的事情, 而且学到的也不会被实际用到. 所以, 千万不要被”获取新知识的成就感” 给蒙蔽了, 去钻研那些琐碎的边边角角.
而对于小工具, 却要反过来. 我觉得在学习小工具 (尤其是 [url=http://en.wikipedia.org/wiki/GNU_Core_Utilities]coreutils 里面的所有命令) 的时候, 最好要做个有心人, 把大部分参数弄清楚记住 (本来参数也不多). Linux 下的小工具基本上是千锤百炼经过无数进化的, 应该说每个选项都是很常用的. 搞明白这些选项, 可以极大化发挥这些小工具的优势, 还能提高自己的生产率. 举个例子: 比如说 ssh 这个程序, 90% 的哥们就是用他来登录服务器, 然后运行服务器上的某个程序. 其实 ssh 的文档写得很清楚, 你可以把 ssh 后面接一个命令文件. 比如说

ssh name@server.com ls

就可以直接显示服务器上的目录了. 还可以拓展一下,

ssh name@server.com < script.py

就可以直接把本机上的 script.py 放在服务器上跑, 无需把文件先拷贝过去. (走题一下: 跨平台的脚本语言的好处就在这里. Apache 的 Hadoop 是 MapReduce 的一个开源实现, 他的任务控制器就是采用我说的这种方式来调用各个机器上的Mapper 或者 Reducer 工作的). 因此, 掌握 ssh 的加命令的用法, 在我看来, 是值得的.

很多小工具都有这样不太鲜为人知的用法, 熟稔这些用法, 我觉得是值得的, 况且这也不需要花多少时间, 只要打印一份文档每天睡前看半页就行了. 我以前还有整理了不少这类平时大多数人注意不到的小命令的一些”黑魔法”. 我觉得这些黑魔法一点都不是什么奇技淫巧, 而是实实在在能提高效率的魔法, 是居家旅行必备的工具套装.

PS: 最近有几个朋友看了我的博客, 发信让我推荐学习 Linux 的书. 我推荐 “鸟哥的Linux私房菜” 这本书. 我学 Linux 的过程中没看过这本书, 所以折腾的比较曲折. 直到我大四我才看到这本书, 这本书是一本非常深入浅出的好书.

PS2: GNU 的工具链有把小工具 Facade 化的倾向. 连 ls 这么简单的命令都有几十个参数. 在这种情况下, 还是挑选一些认为会常用的参数学习一下就行了, 没有必要去追求高大全. 一般说来, 这种两个字母的小工具, 如果后面加的参数超过6个字母, 就完全不对味了. 工具这东西, 强极则无用至极.

-EOF-

作者: 翔子 时间: 2010-5-24 15:21
标题: 编程珠玑番外篇-5.比代码大全好的两本书A
原文: [url=http://blog.youxu.info/2008/11/23/software-tool/]http://blog.youxu.info/2008/11/23/software-tool/

上次我说到”[url=http://blog.youxu.info/2008/11/13/anecdotes-about-program-optimization/]比代码大全好的书“, 第一本指的是 <Software Tools>. 为了说这本书的优点, 得先说这本书的缺点.

这么书基本上绝版了. 而且也没有中文版. Amazon 连旧书摊总共就不到50本. 可见这本书目前不是一本让广大程序员喜闻乐见的书. 其次, 这本书用的说明问题的语言叫做 Ratfor, 基本上是 FORTRAN 和 C 杂交的产物. 估计全世界用这个的程序员和现存的这本书的数量差不多多. 但是你要是认为这是一本古董书, 烂书或者非畅销书, 那你就错了. 因为是一本编程书籍, 生命周期本来就短, 因此单以现在的销量判断好坏, 并不科学. 江湖失传已久的如来神掌送给周星星的时候, 周星星也不以为然. 但最后威力无穷. 希望这篇书评, 能够让读者信服这是一本如来神掌的秘籍.

这本书的作者是 Brian W. Kernighan 和 P. J. Plauger . 关于这两个作者出书质量好的废话我就不多说了(不知道没听说第一个的回家用C写一个Hello, world 并面壁). 先说这本书讲的什么吧.

这本书主要两条线, 一条是怎样通过一个叫做 Ratfar 的语言, 一步一步构建 UNIX 系统下的 cat, wc, tr, sort, tar 等等这些工具; 另一条是怎样和低级繁琐且不顺手的 FORTRAN 语言做斗争, 克服语言的障碍, 写出功能和可读性俱佳的结构化程序. 第一条着重强调的是一个系统的功能分解(对UNIX哲学清楚的读者看一下目录就一目了然), 第二条实际上是叙述了一个一脉相承到”代码大全”的哲学: 如何构建”你的”编程语言, 而不是简单的使用”别人的”编程语言. 这一条, 道出了整个编程的真谛: 编程就是构建一个一个”自己的”小积木, 然后用自己的小积木搭建大系统.

为了说明小积木的道理, 我们从编程语言说起. 我以前的文章也提到过, C 并没有一个可以传递一行消息出来的 Assert 机制. 因此有经验的程序员会自己构造一个 Assert. 同样的道理, Java 虽然很高级, 却没有一个很好的单元测试框架, 所以全世界 java 程序员都在用 JUnit. 这些实践, 表明了一个现成编程语言总有一些特性不完美之处, 工具和使用者之间还有着不小的距离, 因此显得”不顺手”. 如果这个例子不够说明问题的话, 不妨问自己: 为什么人不能像写伪代码一样写程序呢? 因为我们使用了编程语言, 而编程语言有很多肮脏的细节要我们去处理, 比如下标从0开始, 浮点数不好作为数组下标等等. 语言的细节需要处理这个问题, 从 Fortran 到 Python, 只有程度的改变, 并没有本质的改变. 况且, 通用编程语言之所以通用并且简单, 就是因为支持的功能比较基本, 可扩展性强. 因此, 基本功能都有, 高级功能缺少成了通用编程语言的最大特点. 不管编程语言多么”高级”, 总是没有自己的思维高级. 因此, 编程的第一步就是把语言改造成自己的语言. 即使强大到直接能 [url=http://xkcd.com/353/]import antigravity 的 Python, 也有需要改造的地方(最好的例子就是 Python 3000 的推出).

小积木有了, 就要构建大系统了. 在这一点上, Software Tools 可以说是非常好的一本源代码导读. 自从 [url=http://en.wikipedia.org/wiki/Lions]Lion 分析 Unix 源代码以来, 源码剖析成了程序员修炼的一个捷径. 可是现在程序的源代码树都很繁杂, 能真的拿出来分析的很少很少了. Bell 实验室的两位作者从实作 UNIX 系统下的工具出发, 挑选出经过实践检验的优秀代码来讲解. 这样来自一线的题材是极其宝贵的, 就算在最新的 Beautiful Code 中, 大多代码也只是教科书代码而已. 至于代码大全, 完全就是玩具代码. 而 Software Tools 有几千行代码的大程序, 也有几行代码的小程序; 有算法程序, 也有文件IO程序, 基本覆盖日常所有用例, 对于内功修炼大有裨益.

除了道出”改造你的语言”的真谛之外, 这本书其他论点也可谓字字珠玑. 比如讲goto带给程序员的自由恰好是你不想要的自由, 因为这个自由会带来很多错误. (很多语言都有这种不想要的自由, 比如 C++, 到处都是). 比如说讲结构化编程不会自动带来清晰的程序, 因为机械的规则永远不能代替清晰的思考. 这个道理在面向对象/设计模式领域也一样. 比如本书还论证了为啥要详细设计, 因为设计和编码环节对于程序员讲是愉快的事情, 值得更多投入. 而 debug 和测试环节是比较痛苦的事情, 所以要少投入. 还比如人比机器时间贵, 所以程序员要越懒, 越快完成编程越好. 除非程序太慢, 否则从总成本看, 机器多用点时间没事, 人用的时间要越少越好, 等等等等. 类似于这样的深刻揭示编程的哲学理念的句子俯拾皆是, 比起相同内容但是篇幅冗长的代码大全, 这本书适合随身携带, 随时阅读, 随时提高.

老规矩, 结尾顺手说个八卦吧. 话说为了把 Ratfor 这个假想的语言翻译成当时最流行的两种语言, FORTRAN 和 PL/I, bwk 爷爷写了一个宏替换的工具, 能够把 Ratfor 替换成肮脏的 FORTRAN, 而他们写干净的 Ratfor. Dennis Ritchie 爷爷看到鸟, 很赞, 于是推广了一下这个宏替换工具, 起个诡异的名字叫做 m3 (macro for ap3). 然后 bwk 爷爷又看到了 dr 爷爷的工作, 回过来又和 dr 爷爷合作, 写出了金光闪闪的 m4. 如果你常常编译开源软件, 肯定会注意到一个叫做 configure 的生成 makefile 的程序. 这个 configure 的读入, 一般情况下是可配置的, 叫做 config.ac, 就是 m4 语言写的. 虽然因为版权问题, 现在 GNU m4 和两位爷爷没啥关系了, 但是基本的语法和用法都是一样的. 各位知道 K&R 的读者千万不要错过这个好用的工具(也是编程语言).

这个工具其实我也只懂皮毛, 也不常用, 只是用来自动编号一些行, 做一些稍微复杂一点的不能用正则的文本替换. 不过我似乎在某个地方听一个高手说, Linux 命令行下文本处理三剑客乃是 sed/awk/m4, sed 和 awk 的强大早就见识了, 相必m4与他们各有千秋. 故而略介绍一下.

另外, 本书也是 troff 排版的. 按照我的 [url=http://blog.youxu.info/2008/10/13/trivia-about-computer-typesetting/]troff 排版无烂书定理, 这本书也属一流好书.

作者: 翔子 时间: 2010-5-24 15:23
标题: 编程珠玑番外篇-6.高效能编程的七个好习惯
原文: [url=http://blog.youxu.info/2008/10/29/seven-habits-of-highly-effective-programmers/]http://blog.youxu.info/2008/10/29/seven-habits-of-highly-effective-programmers/

这七条都是我这个不怎么高效能编程的人悟到的. 不权威, 不一定全对.

1. 使用工具帮你找 Bug, 而不是人工找.
工具包括用单元测试, assert语句, 代码测试容器. 人工指用 print 和 debugger 一行一行跟踪. 我们知道, 编程中绝大部分时间是耗费在除 bug 上. 不同的人有不同的 debug 的方法. 我个人比较喜欢”极限编程(XP)” 学派的主义, 也就是说, 代码未动, 测试先行.
单元测试中的红棒绿棒(熟悉 JUnit 的读者知道我在说什么)一出现, 哪里出了问题就一目了然. 单元测试的另外一个好处在于增加写程序的自信. 以前没用单元测试之前, 每天晚上改代码改到很晚的时候脑子常常不灵活, 把代码改错, 然后第二天来还要重头弄. 有了单元测试之后每天晚上保证测试全部过掉, 这样心理踏实, 睡觉也香, 早晨也不忙, 吃饭也棒.
一般的语言都有 assert, 但是很少有人用. 其实 assert 是一个非常好的DEBUG 工具, C 的 assert 能够把哪一个文件哪一行出了错都告诉你. 不过我一般会自己写一个这样的 assert 宏:
#define ASSERT(value, msg) if (!(value)) {fprinft(stderr, "At file %s, line %d: \n message: %s\n", __FILE__, __LINE__, msg); exit(-1);}
这样的 ASSERT 可以带一个信息出来, 比起原来只告诉你哪个文件哪一行更加有价值.
第三个是用容器帮你找 Bug. 这一点以 C/C++ 程序最为突出, 因为编译之后直接就是可执行代码, 运行时的信息不像 Java 和 Python 这样有 VM 的语言容易得到. 这时候, 我推荐 [url=http://valgrind.org/]valgrind. 这个工具能够把 C/C++ 程序放到一个容器中执行, 记下每一个内存访问. 被这样的容器 debug 一下, 基本上指针指飞了 (Segmentation Fault) 的情况几乎就没有了. 想像一下是用 GDB 追踪非法指针和内存泄露方便, 还是用容器告诉你哪一个指针非法, 哪一个内存没释放方便

2. 选用自动化工具构建
用 gcc 或者简单的 IDE 来编译和运行程序在编程初期是很快速的, 可是越到后来, 会越臃肿. 在编译的时候, 不同的参数, 不同的目标, 在 IDE/gcc 里面每次都要设定. 而且一般的 IDE 也不能做到自动解决依赖等高级方法. 因此, 最好的方法是用 [url=http://ant.apache.org/]Ant 或者 Makefile 管理项目. 这方面教程很多, 而且我估计编程的个个都知道. 不管项目大小, 注意频繁使用就是了.
自动化测试也有很多工具, 特别是 GUI 和命令行测试的自动化, 工具链都很完整. 大公司里的程序员走这方面的流程都比较规范(我在西门子实习过), 但是小一点的公司中, 或者个人搞小项目的时候, 就不一定想得起来了(大部分我见到的程序员就手工来测试). 手工测试看上去快, 但是要是积累的次数多了就比较浪费时间了. 其实自动化测试工具的学习成本很低的, 事半功倍.

3. 买本小书做参考, 而不是用 Google.
这是大实话. 我大三开始学 Python 的时候, 语言特性并不熟悉, 手头也没有书, 因此常常连取个随机数都要上 Google 查一下库. 我发现, 不管网络多快, 自己搜索技术多牛, 还是没有手头一本书方便. 后来打印了一个7页的标准库的 cheatsheet, 编程立即行云流水. 我在实习的时候也观察到, 大部分时候程序员不可能记住一个框架所有的API, 所以他们要不等 IDE 几秒钟做代码补全, 要不一边翻文档一边做. 或许MSDN 这些本地文档系统比查书快吧, 但是用 Google 和网络搜索绝对比书慢. 现在因为工作原因, 常常要学一些新的语言, 我做的第一件事情, 就是把他的库接口的网页全部打印了下来.

4. 用脚本语言开发原型
人月神话的作者 Brooks 说: 准备把第一版扔掉, 因为第一版必然要被扔掉. 这是大实话和真理. 既然第一版要被扔掉, 咱们就让第一版扔掉得越早越好. 说白了就是, 原型要快速的被开发.
所谓的快速原型开发, 大致有两个捷径, 第一是只做核心的功能, 输入输出都是构造好的简单的例子. 第二是只做最简单的情况, 对于性能和健壮性什么的都不太考虑. 这两点, 恰好是脚本语言最擅长的. 脚本语言擅长于用精简的几行构造出复杂的功能, 并且语法很松散, 潜在假设程序是正确的.
即使在代码编写阶段, 一些功能的实现, 也是要先写个简单的, 再慢慢打磨成复杂的. 脚本语言此时依然有用. 比如我在用 Java 的时候, 常常不确定一个函数返回的对象究竟某个属性是什么样的值. 这时候我就会用 Java 的 bsh 脚本写一行打印, 而不会写一个复杂的 out.println 再编译再运行再把那行删除掉. 当然, 这几年很流行动态语言, 原型和产品之间的差距已经变得很小了.

5. 必要的时候, 程序要使用清晰的, 自我解释的文本文件作为日志输出.
不知道各位调试程序的时候是不是和我一样, 看到不确定的和要跟踪的变量就直接插入一行 print. 我以前一直这样做, 但是频繁的插入这样的打印会使得屏幕的输出很乱, 不知道哪行是什么意思. 一个更加好的办法是写一个日志函数, 可以分也可以不分优先级, 总之保证 Debug 的时候的输出以一种统一的, 可管理的方式出现. 这样, 在最后发布稳定版本的时候, 只需要简单的几行命令就可以从代码中剔除所有的日志打印行.
如果必然要输出日志, 最好要分配一个单独的命令行参数, 用来控制程序究竟输出不输出日志, 输出哪些日志. 一开始看上去这个是费时费力, 越到后来日志越多的时候, 就体会到方便之处: 有时候你只想要某一类日志, 可是其他的记录偏偏来捣乱. 多加一个参数可以使得程序更加灵活, 根本不需要去修改代码或者条件编译就能得到不同级别的程序日志.
日志和程序的输出结果一定要清晰且能自我解释, 否则不如没有日志. 我切身经历是这样的: 几个月前, 我一个程序跑了大约一天, 最后输出了很大的日志和结果. 但是很不幸的是, 结果里只有数字, 没有任何说明. 我自己都忘了每一行是什么意思. 而且更加麻烦的是程序的输出藏在重重判断和循环之内, 使得根本没有办法分析这一行输出对应的输入是什么. 于是, 最终只能再次浪费一天的时间让程序再跑一次. 经过这次教训, 我的程序日志和结果中插入了不少让人可读的内容. 这样, 即使程序丢失了, 结果还是能够被人解读的.
更多的关于数据和程序结果要能自我解释的精彩论述, 可参见 More Programming Pearls 第四章.

6. 使用命令行小工具操控分析你的结果和代码, 而不是用自己的眼睛和手.
我发现, 人有一个固有的习惯, 就是喜欢自己去”人工”, 而不喜欢用工具. 因为人工让人感觉工作更加刻苦, 更加快, 更加有控制感. 比如说吧, 上面我说的测试, 我就不只一次见到为了测一个交互式的命令行, 一个程序员宁愿老是每次打相同的三个命令, 而不愿意用一个简单的 expect. 再比如说, 面对长长的日志文件, 我见到很多人都是用文本编辑器直接打开, 用鼠标滚轮一行一行的往下翻, 而不是使用 grep. 包括看网页, 很多人从来不用查找功能, 而是一行一行的往下瞄. 包括打游戏也是, 好的UI脚本(不是外挂)一大把, 可是玩 WoW 的人很少用, 都喜欢自己重复点鼠标.
别看上面说的这些好像程序员没有, 其实我们常常陷入这个误区. 举个简单的例子, 一个 python 程序里面有十几个 print 函数, 我们想把这些打印全部灭掉, 一般人会打开文件慢慢瞄, 稍微高级一点的用查找, 找到了, 用快捷键删掉整行. 其实最好的方法根本都不要编辑器, 应该用 grep -v. 或者 sed, 但是这样的方法极少会有人用的. 我也是强迫自己无穷多次之后, 才渐渐的用这套快速的方法.

7. 程序能跑就是万岁. 除非万不得已, 尽量不要在性能上优化你的代码
Knuth 名言: Premature optimization is the root of all evil. (提前优化是万恶之源). 一般我们写代码的时候, 不知不觉的就会觉得, 哎呀, 这样写效率不高, 我要构造一个数据结构啥啥. 随机访问一定要哈希表, 排序一定上快排, 查找一定要二分, 强连通分量一定要用 Tarjan 算法, 动规一定比穷举好等等, 这些竞赛的时候极限情况下正确的论断其实在实际环境中并不重要, 因为做编程的一开始关键是能跑, 而不是跑得快. 往往这么以优化, 程序很难 debug, 倒是还要去翻算法导论和TAoCP 看人家的二分怎么写的等等.
在程序能跑的情况下, 优化也要特别小心. 我曾经有一个程序, 大约有 90% 的运算是查表, 只有 1% 的是乘法, 另外是一些判断和把插到的结果插入到一个集合中. 我的查表是用的最土的 list.index. 按照正常的想法, 应该把这个优化成哈希表. 而实际上我用 profile 工具一看, 才知道, 原来是插入到一个集合的操作费时间, 因为每次都需要 extend, 涉及到很多内存分配的操作. 我做过非常多的 profile 测试, 没有一次不出乎我预料的. 程序运行时间总是在自己不认为浪费的地方被浪费掉. 因此, 就算万不得已优化, 也务必要先做一下 profiling. 我喜欢 python 的地方就在于, 他的 profiling 只需要一行语句就完成了, 而且结果具体干净. 其他的语言, 至今没见到这么简单的 profiling 工具.

另外: 用两个或者大于两个显示器. 不要用或者少用鼠标.

作者: 翔子 时间: 2010-5-24 15:25
标题: 编程珠玑番外篇-7.比代码大全好的两本书B
原文: [url=http://blog.youxu.info/2008/11/23/the-elements-of-programming-styl/]http://blog.youxu.info/2008/11/23/the-elements-of-programming-styl/

各位读者老大中有不少都是大学生, 相信不少都参加过形形色色的英语写作培训班. 如果当年您参加培训班的时候, 老师没有介绍一本叫做 <[url=http://en.wikipedia.org/wiki/The_Elements_of_Style]The Elements of Style> (TEoS) 的书, 建议您现在立即冲过去找他们退钱. 为啥呢, 因为这本书是讲解英语写作绕不开的经典圣经(即使这本书已经被说烂了, 批评也不少, 但还是经典). 假如培训机构或者老师上课没推荐到这本书, 这个培训机构要不是太牛逼了, 要不是水货. 而大家都知道, 水货和牛逼的比例总是 1:epsilon.

作为[url=http://www.amazon.com/Elements-Style-Fourth-William-Strunk/dp/020530902X]Amazon 上 297 个5星的书, 书评我就不狗尾续貂了. Knuth 爷爷也是很喜欢这本书滴, 因此在 Stanford 开课的时候让学生人手一本 (我们系今年新生也强制人手一本). 这本书不光勾勒了英语的基本写作要素, 也刻画了一个时代: 从此, 任何需要”艺术和技艺”的领域, 都会时不时跳出一些牛人, 模仿这本书的题材和哲学, 用简洁的文笔勾勒出这个领域的基本要素. 以我熟悉的计算机领域为例, 就有 “The Elements of Programming Style”, “The Element of Programming Style with Perl”. “C Elements of Style”, “The Elements of Java Style”, “The Elements of UML Style” 等等书, 都是希望继承 TEoS 的衣钵, 勾勒出编程的一些风格要素. 今天我要说的比<代码大全>好的书的第二本, 就是叫做 <The Elements of Programming Style>的. 我以前在[url=http://blog.youxu.info/2008/04/09/classics-in-cs/]计算机科学必读经典中, 也提到了这本书.

这本书作者和上一本 Software Tools 一样, 属于一个家族哲学下的两本不同角度的书. 关于它的书评也很多, 我就不一一废话了. 只说几个体会较深的.

第一是写程序和写作一样, 要写的清楚. 这本书翻开第一条就是 Write clearly – don’t be too clever. 看上去说的和没说一样, 其实实践起来乃是金科玉律. 我曾自己写过三层嵌套的 “? :” 表达式, 写的时候自己被自己的聪明都感动了, 回来改的时候自己被自己当时的聪明给打击了: 死活看不懂当时啥意思, 只好写一个 printf 在后面测输出. 假如当时多花几分钟写的清楚一点明白一点, 就犯不着回头修改的时候花半小时破译了. 现实中的情况没这么极端, 但是也比比皆是. 相信任何正常的程序员, 每天都要为了理解以前写的不大清楚了程序浪费不少时间 (反正我是记不住一年前写的代码的每个小细节). 因此, 写的时候写的清楚比什么都重要.

在写得清楚上, Knuth 爷爷是榜样. 他提出的 [url=http://www.literateprogramming.com/]Literate Programming 的思想虽然太学术, 使得实践的人不多, 但是的确使得程序更加好读. Knuth 爷爷把他的用C语言作为基本语言的 Literate Programming 系统叫做 CWEB. 大名鼎鼎的 TeX 就是 CWEB 写成. 如果对 Knuth 爷爷比较粉的粉丝们恰好要做图算法,  Stanford Graphbase 是一本非常好的书, 里面贴得全是程序, 但是因为 Knuth 爷爷用 CWEB 写成, 文档和程序浑然一体, 读起来丝毫不觉得思维在程序和自然语言间做切换. Java 下有名的 XDoclet 和 Javadoc, 事实上也是 Literate Programming 的一种体现. [url=http://tex.loria.fr/historique/interviews/knuth-clb1993.html]据 Knuth 爷爷讲他写 CWEB 程序能笑出来, 这种境界不是一般人能有的. 而且 Knuth 爷爷在提出 Literate Programming 的时候, 就野心勃勃的说: 写文章也是写, 写程序也是写, 我们 Literature Programming 的口号就是: 没有蛀牙程序员也能拿普利策. (“I’m hoping someday that the Pulitzer Prize committee will agree.” Prizes would be handed out for “best-written program”.)

又八卦走题了. 言归正传, 我的第二个深刻的体会是”让计算机干脏活”. 什么叫脏活呢? 让你不爽的活叫脏活. 比如 Debug, 比如无穷多的复制粘帖, 比如替换一个大小写, 数数几个单词, 做做单元测试等等. 用眼睛瞄肯定会死人. 我以前在 “[url=http://blog.youxu.info/2008/10/29/seven-habits-of-highly-effective-programmers/]高效能编程的七个好习惯”  这篇文章中也说了, 就不多废话了.

当然, 现实的问题是, 理论是理论, 实践是实践. 事实上, 我们要不然就是不用或者想不起来用工具(理由是不习惯), 要不然就是成为工具的奴隶. 李笑来老师也观察到了第一点, 比如[url=http://www.xiaolai.net/index.php/archives/1491.html]这篇. 为什么明明别人告诉我有高效率工具和习惯存在的情况下, 我们还不去用不去改, 或者如何不成为工具的奴隶这两个话题都太大了, 我也写不好, 就不废话了. 然而, 不管最后实践用还是不用, 读一些被别人实践检验过的经验之谈还是很有用的. 这也是我推荐这本书的原因. 不知道大家有没有发现, 潜意识中如果有个正确的小声音不时在原则上提醒自己, 实践的时候潜移默化的就会越做越好.

最后依然附送两个八卦. 第一个是关于 TEoS 这本书的. 这本书列了很多的原则和规则, 都是具体的对某个词某个句型的建议, 因此英语写作的时候可以直接应用这些规则. 不过对着书查规则显然属于脏活的范围, 所以呢, 我们的”让计算机做脏活”的哲学就发挥作用了: 在 Linux 下有一个程序叫[url=http://www.gnu.org/software/diction/diction.html]diction, 用他可以检查英语写作的文章符不符合 TEoS 的标准, 我[url=http://blog.youxu.info/2007/07/11/some-useful-tools-for-you-to-write-english-articles-on-linux/]以前也专门介绍过. diction 会挑出那些不符合 TEoS 的句子, 告诉你让你修改. Knuth 爷爷也说, 虽然这个程序很笨, 但是至少可以强迫你重新审视你的文章, 挑出弱智的错误. 其实 GNU/Linux 下帮助英文写作的工具很多, 虽然不完美, 也称得上完整了. [url=http://blog.youxu.info/2007/07/11/some-useful-tools-for-you-to-write-english-articles-on-linux/]我以前的文章可供大家参考 . 和 diction 一起的另一个工具叫做 style, 可以做像长句分析, 被动语态分析, 平均单词和词汇量估计等统计, 以及语言学水平上的英语水平估计(等价于美国几年级学生水平的估计). 这些估计都是语言学家研究数年的标准指标. 大家都知道, GRE 作文是计算机批阅的, 虽然我们不知道算法, 但是可以想象, ETS 那么笨, 肯定是请语言学家帮忙设计的程序, 所以必然或多或少的用到很多标准的语言学指标. 所以呢, 你不用计算机程序分析分析自己的文章, 光听培训机构的一些老师忽悠, 怎么知道自己文章水平呐? 相比较一些培训机构的老师, 指不定 style 这个程序更像 ETS 的评价标准.

第二个八卦是关于写清晰的程序的. 或许大家都听说过史上最牛逼的注释的故事. 虽然各人有个人认为的最牛注释, 我个人喜欢的叫做 /* You are not supposed to understand this. */ (我不指望你懂这是啥意思). 这句话其实本来不该这么出名的, 恰好是因为出现在开源的第六版UNIX中, 恰好写的人是 Dennis M. Ritchie, 恰好澳大利亚出了一个叫 Lion 的人把 UNIX 源代码扒出来搞了个源码解析, 又恰好当年这本源码解析几乎每个黑客都人手一本. 所以, 这个极其挑战其他黑客智力的注释就变得流行起来鸟. [url=http://cm.bell-labs.com/who/dmr/odd.html]DMR 同学对此有技术上的详细解释,  不再废话. 就是友情含泪劝告读者: 您要是在你的程序里面搞这么一句然后又被你同事和老板看到鸟, 你就完蛋鸟. 世上只有一个牛逼的 DMR 敢这么写.

PS: 想要看看The Elements of Style 书的内容的老大们, 可以猛点[url=http://www.crockford.com/wrrrld/style.html]这个链接:

想要看 The Elements of Programming Style 说了哪些的老大们, 可以猛点[url=http://www.cnblogs.com/hitszxin/archive/2008/04/03/1136726.html]这个链接

-EOF-

作者: 翔子 时间: 2010-5-24 15:28
标题: 编程珠玑番外篇-8.Smalltalk 中的珠玑
原文: [url=http://blog.youxu.info/2008/11/30/pearl-in-smalltal/]http://blog.youxu.info/2008/11/30/pearl-in-smalltal/

如果我们能够重回1980年, 回望整个计算机编程语言领域, 特别是工业界编程, 打死也不会想到日后 Java 这种无名小卒, 以及 C++ 这个又面向对象又支持过程的双面间谍能够红得发紫. 当年最流行的语言, 当属 FORTRAN, C 和 Smalltalk. 前两个我们按住不表, 单说这个 Smalltalk. 我们现在的教科书基本都不介绍 Smalltalk, 或者就用一句: Smalltalk 是第一个纯面向对象的语言概括过去. 其实 Smalltalk 中有很多的好的思想, 一直在今天都发挥着魔力.

施乐当年的图形界面(来源: harding.edu)

为提起大家兴趣, 我先说血统和设计等八卦. Smalltalk 的血统是算得上高贵的, 来自当年超级牛逼的施乐 PARC 实验室. 施乐的 PARC 干过很多事情, 比较著名的一个故事是说乔布斯同学去参观, 看见那边科学家已经做出了 GUI (图形界面程序), 于是偷偷的回家搞 Macintosh, 搞好之后在1984年发布, 卖得大大的好, 赚得盆满钵盈. 西雅图当时有个大学没毕业做软件的小伙子, 看见乔老师赚了大钱, 想想觉得自己的人生挺没意思的, 只是和 IBM 做订购 DOS 的生意, 于是起了自立为王的念头; 加上看到乔老师的苹果机一个窗口一个窗口的很好玩, 于是一激动就自己搞了一个 Windows. (这个作软件的小伙子就是比尔盖茨啦). 这小伙子很牛, 把乔老师的苹果机逼到了角落里. 乔老师是最不能咽下恶气的人, 于是连在 Stanford 演讲了时候还不忘提一下微软抄苹果. 法律上就更不要说了, 两家公司之间旷日持久的 GUI 专利权官司从1988年打到1994年. 两家公司都一步不让. 最后施乐火了, 跳出来大喊一声: 靠, GUI 乃是我发明的. 于是把苹果给告了. 所谓螳螂捕蝉, 黄雀在后, 苹果被施乐这么一搞, 自己抄别人的老底就被挖出来了, 告微软就显得特别勉强, 所以官司最后也没赢, 以苹果无理取闹失败为结果.

施乐不光用 GUI 引领了我们现在计算机图形界面, 还发明了以太网, 鼠标, 所见即所得的编辑器等. 要不是这几样东西, 现在的计算机说不定是另一个样子呢. 言归正传, 前有施乐 PARC 出品了这么多伟大产品, 后加上 Alan Kay 这种牛人主导设计, Smalltalk 的血统之好, 和出自 AT&T Bell 实验室的 C 是有一拼的. C 还是两个人无聊敲打出来的, Smalltalk 是正儿八经作为一项研究弄出来的产品.

事实上 Smalltalk 的确也是划时代的产品. 我就说我知道的两个部分.

第一是现代程序员耳熟能详的 [url=http://en.wikipedia.org/wiki/Model-view-controller]MVC 结构以及整个 Design Pattern 的思想. MVC 出现在 Smalltalk 中并不是偶然的. 当年施乐开发 Smalltalk 主要是用来做图形界面编程的, 而图形界面的编程首先就是从施乐发明图形界面开始的. 试想一个程序员成天写命令行程序, 肯定是不会太在意 MVC 的分离. UNIX 世界中并没有MVC的对应物, 因为压根不需要. 而图形界面程序的复杂度比其他程序要高太多了, 因此自然的就产生了 MVC 这样解开功能模块耦合的自然的设计. MVC 的重要程度和流行程度可以从两个小事情看出来. 第一是著名的 [url=http://en.wikipedia.org/wiki/Design_Patterns]GoF 书, 翻开第一章第二节就开始讲 MVC, 用 MVC 作为整本书的纲领章节, 可见其重要程度. 第二是众多的 Java 框架, 比如Struts, JSF, 里面的对象就很直白的叫做 XXModel 或者 XXViewer. 这些传统都是从 Smalltalk 开始的, MVC 的影响一直到今天还到处都是. Smalltalk 不光催生了 MVC, 也催生了 Design Pattern. 细心阅读 GoF 的 DP 书我们就会发现, 里面所有的 Pattern 大多是在设计一个所见即所得的编辑器的背景下提出来的. 而上面我们已经说了, 施乐是第一家搞这个玩意的. 如果我们追溯 Smalltalk 早期很多的论文, 很明显可以看出, 虽然没有用 Design Pattern 这个词, 开发的时候要遵循一定的”对象结构”的思想是随处可见的.

第二是我认为非常重要的: 运行时类型信息支持, 或者叫反射. 简单的说, 就是一个对象在运行的时候能够知道自己的类型(类名称), 以及这个类有哪几个方法, 哪几个字段等等.

关于反射的基本概念在脚本语言里面是屡见不鲜的了. 大家都知道, LISP 里面的 eval 后面可以加任何的字符串, 构造出一个运行时对象. 脚本语言实现反射也很简单: 本来就是解释执行的语言, 多一个 eval 等价于多调用一次解释器而已. 而编译型语言就麻烦了, 因为解释器已经在编译期用过了, 运行的时候解释器是不存在的. 这样, 就造成了编译型语言没有运行时信息这个本质困难. Smalltalk 用了一个巧妙的方法解决了这个问题, 也就是 Java 和 Python 等现代语言用的方法: 虚拟机. 能编译的代码被先编译, 需要解释的代码在运行时可以被虚拟机自带的解析器再解析. 除了加入一个小的解释器到虚拟机外, Smalltalk 更进一步, 把对象的元信息也抽象成一个对象, 这样运行时需要的一个对象的所有元信息都能在面向对象的标准框架下表达. 我们用类 Java 的语言来举例: 一个叫 a 的 Foo 对象, 包含一个 a.hello() 的方法, 这个方法既可以通过 a.hello() 来调用, 也可以通过 a.class 先得到 a 的类, 再通过 a.Class.findMethod(“hello”) 找到这个方法. 最后再通过 .invoke() 调用这个方法. 这样的流程在没有虚拟机的 C++ 里面是没法完成的.

在1980年, 这个反射机制的划时代意义是怎么说都不为过的. 我以我熟悉的 [url=http://www.junit.org/]JUnit 的进化史为例说明这个议题.

现在做单元测试的框架, 一般都被称为 xUnit 家族. xUnit 家族最早的成员, 不是 JUnit, 而是 SUnit (Smalltalk Unit). SUnit 的历史比 Junit 悠久得多, 大约在1994年的时候, [url=http://en.wikipedia.org/wiki/Kent_Beck]Kent Beck, 也就是 Junit 的作者之一, [url=http://www.xprogramming.com/testfram.htm]写了 SUnit. 而后才有了 JUnit (1998). 所以, 在 [url=http://sunit.sourceforge.net/]SUnit 的网站上, 极其显摆的写着”一切单元测试框架之母” (The mother of all unit testing frameworks). 事实上这是大实话 — 所有单元测试框架里面的名词术语, 都从 Sunit 来的, 如 TestCase, Fixture 等等.

既然 SUnit 和 Junit 是同一个作者, 而早在1996年, Java 就已经成为工业界炙手可热的语言, 为什么要等到两年之后, JUnit 才横空出世呢. 这里面的原因说简单也简单: 自动单元测试需要反射支持. 1998 年前的 Java 没有反射, 直到1998年 Java 1.2 发布, 反射才完整的被支持. 所以, 只有1998年之后, Java 才有办法做自动单元测试.
我们回顾一下 Junit 的工作流程: 继承一个 TestCase, 加入很多以 test 开头的方法, 把自己的类加入 TestSuite 或者直接用 TestRunner, 让测试跑起来. Junit 能够自动覆盖所有 test 开头的方法, 输出红棒绿棒. 这地方的关键是自动覆盖. 假如每个测试都是靠程序员自己写 printf 比较, 那不叫自动. 假如每个 TestCase 里面的每个 test 开头的方法都要程序员自己写代码去调用, 那也不叫自动. 所谓的自动, 就是在机器和人之间形成一定的规约, 然后机器就去做繁琐的工作, 最小化人的工作(RoR就是很好的例子).

注意到我们的需求是 “让 Junit 自动调用以 test 开头的方法”, 而不需要自己很笨的一个一个自己去调用这些方法. 这意味着 Java 语言必须支持一个机制, 让 JUnit 知道一个测试类的所有方法名称, 然后还能挑出 test 开头的方法, 一一去调用. 这不就是反射么! 事实也证明了这一点: 目前互联网上找到的最早的 Junit 的源代码, 1.0 版的核心就只用了一个 Java 的标准库: reflect. 相反, 不支持反射的语言, 就得告诉单元测试的框架我要运行哪些. 比如说 C++ 的单元测试框架 CppUnit, 就很不方便–必须告诉框架我要测哪几个函数, 就算他们以 test 开头也不行. 还有一个好玩的例子是 J2ME 的测试框架. J2ME 是 Java 小型版, 不支持 reflect, 因此, JUnit 平移不上去. 如果细看所有的这些移植 JUnit 的尝试, 很容易发现, 移植出去的版本作用到有反射机制的语言上, 使用起来就很方便, 就比较成功, 比如NUnit; 没反射机制的就比较麻烦, 用的人也相对少, 比如 CppUnit 和 J2MEUnit. 反正任何对于 JUnit 的移植, 都绕不开”反射” 这个机制. 有反射者昌, 无反射者弱. NUnit 这个移植版本, 还曾经被 Kent Beck 夸设计好, 其原因, 与 C# 语言比 Java 更加良好的 attribute 和反射机制, 是息息相关的.
此外, 现代框架中流行的依赖注射 (Dependency injection), 反转控制 (Inversion of control), 都是基于反射的. 这也就是为啥用传统的不支持反射的语言很多年的人很少听过这些名词的原因.

有兴趣的读者可以继续阅读 wikipedia 关于[url=http://en.wikipedia.org/wiki/Reflection_(computer_science)]反射和 [url=http://en.wikipedia.org/wiki/Metaprogramming]元编程这两篇文章, 相信会得到更加多的启示.

Smalltalk IDE (arstechnica.com )

除了以上两点, IDE 和库的思想. 我们今天用的标准名词, 如”方法”, “字段”, 都是来自于 Smalltalk 的. 这些也都是划时代的工作, 因为我不熟悉, 也不敢不懂装懂的展开介绍了.

有时候回看历史, 特别是回看编程语言的设计和进化的历史, 会发现很多散在的晶亮的珠玑.

(完)

作者: 翔子 时间: 2010-5-24 15:29
标题: 编程珠玑番外篇-9.快工具, 新思想
原文: [url=http://blog.youxu.info/2008/12/04/wikiwik/]http://blog.youxu.info/2008/12/04/wikiwik/

和世界上大多数国际机场一样, 美国夏威夷国际机场非常大. 为了方便旅客在航站之间转运, 航站之间用巴士提供交通服务. 在夏威夷, 他们用本地人的语言把这种巴士命名为 wiki wiki, 意思是”很快”. 因为在本地人的语言里面, wiki 是”快”的意思.

1995 年的时候, “极限编程”方法论大牛, [url=http://en.wikipedia.org/wiki/Ward_Cunningham]Ward Cunningham, 觉得应该建立一个公共的网站, 让人能够输入一个 Pattern 的名字, 就能查阅到一个 Design Pattern 的用法, 而且这个网站还能被人编辑, 实现知识共享. 从此, 世界上第一个 wiki 网站就建立起来了, 他把它的东西叫做 [url=http://www.c2.com/cgi/wiki]WikiWikiWeb, 意思就是”快速查阅的网站”. 这时候 wiki 还只是在程序员之间流行, 直到 2001 年, 一个叫 Jimmy Wales 的, 创建了 Wikipedia, 从此, 才算是普及了. Wiki 和 Wikipedia 彻底改变了我们的生活. 试想, 人类协作创造了一本共享智慧的, 随时可访问(中国大陆和朝鲜除外)的百科全书, 是多么值得荣耀的伟大成就!

且慢, 以前人类难道没有百科全书么? 有, 几乎每个像样的图书馆都有大英百科全书, 为什么这些百科全书没有如此大的改变我们的信息获取方式呢? 沿着同样的逻辑链条, 我们可以问更多的问题: 在没有 Google 之前, 似乎搜索引擎也有, 但这个东西我们很少用, 也很少听说, 为什么就是 Google 一出现, 就彻底改变了我们的检索方式呢?

问题的答案很多, 我说我的答案: 很多事情, 只有在人能很快的完成的时候, 才有了做的可能. 这句话可能比较拗口, 反过来说可能更加好懂: 如果用某种方法做一件事情太耗时间了, 那么人就不可能用这个方法做事情. 只有一个方法能够让人足够快的做好事情的时候, 这个方法才会变得实用, 同时这个事情才有做的可能性.

为避免过于抽象, 我们仍然用例子说明. 美国宪法规定要10年做一次人口普查, 但是直到 1890 年, 美国才进行了历史上第一次完整的全国人口普查. 传统上, 人口普查的数据提取上来, 要花多于10年的时间才能处理完, 因此, 人口普查从来就做不完. 直到1890年左右, IBM 公司发明打孔卡片, 卖给了美国人口统计局, 美国人口统计局采用了打孔卡片作为报表, 从此才能在2年内做完一次人口普查统计. 打孔卡片比人填表统计快多少呢, 也就快5倍而已. 但是就这个5倍, 把原本不可能做到的全国人口普查变成了可能.

天气预报也是很好的例子. 天气预报的原理是解一个数值偏微分方程, 这个道理科学家在1922年就知道了. 但在计算机没出现前, 是没有天气预报员这个职业的. 直到1955年, 在电子计算机的帮助下, 天气预报才变成了现实. 那么, 1955 年的电子比1922年的机械式计算机快了多少倍呢? 也就1000倍. 另外有一个未经证实传说说, 以前预报24小时内的天气预报需要计算机计算25小时, 直到更快的计算机出现, 才使得2小时之内可以算出24小时的天气预报, 使得天气预报实用化. 这个, 也就是10倍的更新.

快工具和慢工具的差别, 带来了一件事情可做与不可做的差别. 其实不光是表面上速度的改变, 对应内里是整个方法体系的本质改变才是关键. 比如, 在 UNIX 下数一个文档有几个a开头的词是很简单的事情, 只需要知道正则表达式和管道就行了. 在没有正则表达式和管道的环境里, 这个事情就比较难 (或者有更加好的方法我不知道?). 当然, 这事也可以做, 只是慢了10倍而已. 同理, 从纽约到华盛顿步行也能到, 就是慢了一点而已. 而汽车让从纽约到华盛顿变成了一件很平常的事情, 其实小汽车也就比步行快了不到20倍而已. 到图书馆查百科全书也是一种获取资料方式, 在网上 Google 也是一种方式, 后者(一分钟)比起前者(一小时), 也就快了10倍到100倍而已. 可不同的仅仅是速度么? 正则表达式提供了新的描述角度; 汽车是一种新的不耗费体力的快速交通工具; Google 是一种新的获取信息的手段, 这些速度的表面差异, 对应的内里, 是本质差异. 虽然改变的是速度, 却不仅仅是速度. 甚至, 我们可以大胆的断定, 如果没有本质的内里的变化, 速度也不可能有10倍的提升.

我们都知道, 做事情要高效, 要 WikiWiki. WikiWiki, 是每一个想要管理好时间的人的圣杯, 是每一个想多做点事情的人的魔咒; 可是很显然, 平凡的工具, 至多越用越熟; 即使用到烂熟, 也不能带来本质的效率提升的; 一成不变的思想, 最多用到极致, 形成一个自我体系, 但跳出体系外, 是不能带来崭新的角度和本质的提升的. 特别的, 是在计算机科学以及计算机编程领域, 快工具和新思想层出不穷. 依我的观察, 在计算机科学的发展史中, 每一个时代都有很多新思想涌现, 带来的是革命性的思维方法和崭新的理论实践, 以及快好几个数量级的效率提升; 在在编程方面, 我们大多数人也见识了 UNIX 管道哲学, 和函数式编程的哲学对效率的提升. 这些新思想, 好工具, 是我们计算机科学领域最好的珠玑, 也是在大海边玩耍的孩子不可错过的晶亮的贝壳.

那么, 心急的读者要问了, 到底哪些是晶亮的贝壳和藏着的珠玑呢? 别急, 我会把我见到的认为是晶亮的贝壳和珠玑的好东西记录在这里, 所以, 请继续关注我这个系列的后续文章

最后附送几个不算八卦的八卦, 算是本文花絮:

1. 本文中间那句拗口的中文是翻译自 Software Tools 中的一句: < Many jobs will not get done at all unless they can be done quickly.> 里面还有 “We consider people cost a great deal more than machines, and the disparity will increase in the future” 以及 “The extra freedom permitted by got’s is just what you don’t want” 等道理深刻的话语. 有时候我真的怀疑, Software Tools 是一本讲哲学的书, 而不是一本编程书.

2. Wiki 最早的思想来自于苹果机上的 hypertalk. 这个软件相当于是个人多媒体 Wikipedia. 苹果的 Applescript 自然语言编程的语法, 也是借鉴的这个软件的语言, 叫做 hypertalk. 这个软件称得上是个人计算机的 killer app, 但是不幸被苹果收购之后就中断开发了. Steve Jobs 这家伙很没文化, 收购并扼杀了很多苹果上的经典软件, 这些故事等以后有空细说.

3. 关于汽车之比人快10倍, 但是本质上改变了人的生活的例子是借用的 Knuth 的, 具体可见 <Mathematics and Computer Science: Coping with Finiteness>, 文章发在 1976 年的 Science. 这是一篇好文章!

4. Ward Cunningham 的网站, http://c2.com/cgi/wiki 是历史上最早的 wiki 百科, 只是全是关于计算机和编程的而已.

作者: 翔子 时间: 2010-5-24 15:36
标题: 编程珠玑番外篇-A.P2P客户端的策略和奇妙的对策论-1
原文: [url=http://blog.youxu.info/2008/12/31/tit-for-tac-and-p2p-software/]http://blog.youxu.info/2008/12/31/tit-for-tac-and-p2p-software/

最近日本著名演员饭岛老师去世了. 在我这个年龄段的人中, 熟悉饭岛老师的相信十有八九都是通过奇妙的叫做 bt 或者电驴的软件认识的. 今天我们就来八卦一下程序设计人员是如何设计这些客户端的策略使得您既能下载欣赏到饭岛老师的片子, 又不会浪费您太多的上传带宽的. 简单的说, 就是 P2P 软件的客户端的策略该如何设计, 使得整个系统能够帮助每个用户获得相应的利益最大化.

要研究这个问题, 我们得从博弈论谈起. 但是因为这个是给程序员看的八卦, 不是数学专业课, 我们不在这里说太多的数学, 而是用例子和八卦引入.

大家都知道, 1994 年的诺贝尔经济学奖给了一个数学家, 约翰.纳什 (电影”美丽心灵”为证). 纳什的理论工作是推广了冯诺伊曼开创的极大极小定理(博弈论的基本定理). 而在通俗的对博弈论的介绍中, 提到纳什, 一般都是着重在纳什均衡和囚徒困境上. 我们不具体深究纳什均衡的数学意义, 而是以下面一个具体的极其简化的例子来说明囚徒困境:
假设 BT 网络中两个节点阿强(A) 和 B哥(B) 要交换文件. 文件很大, 我们假设需要非常多轮交换才能完成. 每一轮, 每个节点可以选择平衡上传/下载和几乎不上传/贪婪下载两组策略. 我们按照博弈论的一般用语, 把第一种策略称为 C(合作), 第二种称为 D(叛变). 同时, 假设A, B 都是使用 ADSL 网络, 所以上传成本比下载成本要高很多, 我们在计算回报的时候考虑这样的不对称. 现在, 假设 A 和 B 各自有对方需要的文件, 那么, 如果 A, B 同时选择策略 C, 即平衡的上传和下载, 他们得到的回报都是 3, 如果其中一个人偷鸡选择 D, 即几乎不上传, 光下载; 而另一个节点选择 C, 则选择 D 的能够下载到所要的文件且几乎不需要付出上传的代价, 我们记回报为 5, 而另一个人付出了上传的费用, 却得到了一点点的下载, 可以把回报看成是0. 如果两个人都选择贪婪下载, 几乎不上传, 那么两个人都得到了一点点下载, 现在这样的下载量没有3多, 但是因为本身付出的上传成本也少, 我们把这时候两者的回报都定为 1.

说了这么多, 只是为了让问题更加的真实. 这些交代的条件的数学本质, 可用表格表示, 博弈论中称之为支付矩阵:
C D
C (3,3) (0, 5)
D (5,0) (1, 1)

现在的问题是, 阿强和B哥都是理性的, 也是自私的, 因此, 他们都认为, “假如我选 C, 对方可能选 C 或者 D, 那么我这个策略最糟糕的情况下收益是 0, 而假如我选 D, 最糟糕的情况下收益是 1″ 那么, 因为 D 下最糟糕的收益比 C 最糟糕的情况下收益要大, 理智的人肯定选D. 我们看到, 两者选择 D 都是理性的, 但是实际上从对两者的收益分析看, 两者都选择 C 才是更加优的. 这个表面上看上去很理智但是最后没有到达对双方最好的结果的困境, 就是所谓的囚徒困境. (看过这篇八卦, 您也可以叫做饭岛老师困境)
关于囚徒/饭岛困境的简单介绍就到这里, 现在我们看我们的原始问题. 我们知道, BT 交换文件是分成一块一块的, 也就是说, 是一次一次的交换的. 我们把每次交换叫做一轮的话, 整个系统是一个多轮的博弈问题(或者叫做多阶段的博弈问题). 这个博弈问题, 就显得好玩起来了. 为什么呢, 因为多阶段博弈, 居然能够让自私的A和B两个节点为了自己的利益, 进化出合作来.

我们先简单的说明一下多阶段博弈不必然的能跳出囚徒困境. 比方说, 如果 A 和 B 知道一共有 N 轮博弈, 那么最后一轮, 理智的他们肯定都陷入了囚徒困境, 在第 N 轮的策略清楚之后, N 的问题就转化为 N-1 轮的问题. 所以, 必然的, A 和 B 在所有 N 轮上, 都会陷入囚徒困境 (好比奸商一辈子只和你做有限次买卖的话, 就会一直黑你, 不黑白不黑). 他们等到花儿也谢了, 也不能得到自己想要的内容. 但是, 问题的奥妙在于, 假如A 和 B 不知道一共多少轮, 或者有无限轮呢? 假如阿强在某轮选择平衡的上传和下载(C), 则可能正好碰上 B 哥也选择”友好合作”, 那么, 两个人都舒舒服服的交换了饭岛老师的片片. 所以, 对于一个设计良好的BT客户端, 问题的关键在于怎么选择自己的策略, 使得既能完成自己自私的下片目标, 又能注意和其他客户端良好的合作使得自己的收益最大, 而不在于在特定的一轮中自己的得失.

这里, 我们的目标是设计一个良好的策略. 通常, 在设计一个实践中性能良好的算法的时候, 数学家和计算机科学家在这里的方法就鲜明的分野了. 数学家, 会证明这样算法的存在性, 性能上下界, 和众多的必要条件, 以及算法之间在最理想的情况下的好坏比较. 而计算机科学家, 会像搭积木一样, 用不同的基本模块, 直接尝试不同的组合, 一一做实验, 看哪种方法最好. 在这里, 我仅介绍一种计算机科学家的方法: 通过让不同方法比赛, 取出赢家, 赢家的方法最好的方法. 其实准确的说, 这个就是达尔文的适者生存的方法. 而这个比赛本身又是一段非常有趣的八卦, 因此我着重花笔墨介绍一下.

在心理学和行为学领域, 有一本非常著名的书, 叫做<合作的进化>. 其作者, 记载了在80年代, 他组织的两次比赛, 叫做IPD (Iterative Prisoner’s Dilemma, 多轮囚徒困境). 竞赛的目的是在一个多轮的囚徒困境中找出最好的策略, 参赛者自己写好算法程序, 然后由组织者让这些程序两两对弈, 看谁在多轮囚徒困境中得到最多的分. 在所有的数学家计算机科学家等提交的很多程序中, 表现最好的一个策略, 超乎寻常的只有四行简单的 Basic 程序. 这四行 Basic 程序, 勾勒出了一个叫做 “针锋相对” 的算法(Tit for Tat). 这个算法策略很简单, 一开始采用合作, 假如对方上一轮合作, 则本轮合作. 如果对方上一轮对抗, 则本轮对抗. 用中国人熟悉的话说, 叫做”人不犯我, 我不犯人; 人若犯我, 我必犯人”. (四句话正好对应四行程序, 不是巧合). 其他的算法, 比如随机算法呀, 永远敌对的算法呀, 都比不过这个算法. 因此, 这个算法赢得了第一年的竞赛.

第二次, 各位吸取教训, 继续开发好算法. 猜猜第二次谁赢了? 居然还是那四行程序! 在合作的进化中, 作者从”宽容, 以牙还牙”等社会学的角度去解释为啥这四行程序会赢. 或许对人生有深刻思考的人会感叹, 这四行程序的确蕴含了深刻的智慧. 但是, 很不幸的是, 这个程序在现实中, 有一个非常大的漏洞, 而因为这个漏洞, 使得BT程序如果不修改策略, 先现实中会寸步难行. 这个看上去非常理智非常聪明的策略到底是怎样的大漏洞呢, 我先卖个关子, 下回分解.

(想看剧透的, 可以看 Wikipedia 的条目: Tit for Tat: [url=http://en.wikipedia.org/wiki/Tit_for_Tat]http://en.wikipedia.org/wiki/Tit_for_Tat )

作者: 翔子 时间: 2010-5-24 15:38
标题: 编程珠玑番外篇-B.P2P客户端的策略和奇妙的对策论-2
原文: [url=http://blog.youxu.info/2009/01/19/tit-for-tat-and-p2p-client/]http://blog.youxu.info/2009/01/19/tit-for-tat-and-p2p-client/

上篇我们说到 Tit for Tat 的策略有一个极大的漏洞, 是什么样的漏洞呢? 我们不妨先用通俗的例子理解一下.

假如现实生活中有两个人 A 和 B, 都是认为自己非常理智, 而且严格执行”以牙还牙”策略的人遇到了一起, 会发生什么样的事情呢? 我们按照他们初始的策略, 分三种情况讨论.

1. 假如 A 某次不小心招惹了一下 B (执行了被 B 解读为 D 的策略), 按照 B 的策略, 必然会在下一轮执行 D 策略 (报复). 而 A 对 B 初始是执行 C 策略 (合作) 的. 在 B 报复之后, A 下一轮就会采用报复. 而相反的, B 在本轮看到 A 合作之后, 下一轮就会报复. 如此往返. 不难看出, A 和 B 会陷入彼此报复的怪圈当中, 用大白话说, 就是所谓的冤冤相报何时了. 更加糟糕的是, 博弈的双方都认为自己是完全理智而且愿意合作的, 但是就是因为正好彼此差了一步, 因此从A的角度看B, A 会认为 B 是一个完全不懂得合作的蠢货 (A 提出合作的时候B正好报复). B 看 A 也一样. 现实生活中我们也能发现这种例子, 比如两个性格很强的人遇到了, 在某件事情上不投合, 结果成了一辈子的仇人, 还互相认为对方是傻X. 此时, 双方都得不到期望的最大受益.

2. 如果一开始双方都采用 D 策略, 则可以遇见, 这样的 D 策略将持续下去, 没有一方会主动的让步, 因为先让步的一方必然吃亏. 现实中, 我们也能观察到这样的事情, 即博弈双方仇怨越积越深, 最后到了不可化解的地步. 此时, 双方都陷入了囚徒困境.

3. 如果博弈的双方一开始都采取 C(合作)策略. 那么, 博弈双方则能够永远的友好合作下去, 获得最大的受益. 此时, 双方获取的受益都最大化了.

从上面的分析我们可以看到, 在多轮囚徒困境的情况下, 如果有多个 Tit-for-Tat 策略参与, 那么每个的受益, 极端的依赖于初始状态的设定. 在数学和计算机科学中, 这样的系统, 叫做”初值敏感系统”. 一般认为, “初值敏感系统”是非常不好的系统, 原因在于缺乏”鲁棒性”. 这里我走一下题, 解释一下初值敏感系统和鲁棒性这两个概念.

大家都知道有一个叫做”蝴蝶效应”的东西, 大体是说, 一只蝴蝶在巴西扇动翅膀，有可能会在美国的德克萨斯引起一场龙卷风. 原因在于, 这只蝴蝶翅膀扇动的气流, 引起的一个小小的搅动, 可能会在系统中被各种各样的因素放大, 最后演变成一个非常显著的效应. 中国也有一句古话, 叫做差之毫厘, 谬以千里, 说的都是, 初始的微小变化, 都能引起最后结果的显著不同. 我们这里的初值敏感系统, 和蝴蝶效应也是类似的, 能从小的摄动引发出显著的后果的. 比如大家都知道, 在”一只馒头引发的血案”中, A 在很不经意的情况下, 对B 采用了 D 策略(抢了馒头), B 由此产生了报复, 搞得 A 国破家亡.

显然, 面对这样的系统, 人类即使有模型, 也是很难预测未来的, 因为初值条件在测量上的一点点微小的误差, 都能造成预测的结果的巨大不同. 为了表征这个特性, 我们把”不对初值敏感”的特性成为鲁棒性 (Robustness). (这个鲁棒, 您可以直接理解为山东大棒, 结实, 抗得住外界的一些摄动).

聪明的读者要说了, 即使系统不鲁棒, 我们能不能设计好初值, 使得系统沿着最好的方向演化呢? 答案是不能. 因为任何一个客户端拥有的上传和下载的带宽都是有限的, 有限的资源必然会导致资源的竞争, 从而导致必然某些请求不能满足. 在这种情况下, D 策略是不可避免的. 况且, 网络情况复杂多变, 即使双方都有意采取 C 策略, 很可能因为网络的复杂性, 双发获得的受益不对等, 从而引发一方采取 D 策略. 所以, 如果 Tit for Tat 这种初值敏感策略放到 P2P 客户端中, 结果是不可想像的, 因为这时候每个客户端都是碰不得的刺猬, 一旦在某个时间点某个节点出现了差错, 很可能整个系统都陷入”冤冤相报”的死结, 让整个网络没法完成文件的传输, 反而忙着互相报复和自我保护.

从上面的分析我们看出, 靠精心设计初值来维护这个系统是不现实的, 我们需要设计的, 是一个好的策略, 使得不管初值怎么变, 系统中每个个体依然能够获得较大的收益. 那么, 怎样设计这个鲁棒的系统呢? 我们从极端的两个例子开始, 一种是不管别人怎么出牌, 永远合作的; 另一种是或者不管别人怎么策略, 永远背叛的. 这两个都很鲁棒, 都很”彪悍”. 但是毫无疑问, 效用不见得最大化.

从这两个极端的例子表现不怎么好来看, 我们的确应该要根据对手的策略选择自己的策略, 同时又不能非常的依赖于对手的策略(否则就初值敏感了). 那么, 最简单的方法就是: 我们以一定的概率去执行以牙还牙, 但是也允许以一定的概率不管上次选什么, 这次和对手选择合作(跳出怪圈). 这样, 因为随机性的引入, 对初值的依赖就随着时间的流逝越来越小了.

在多个人的环境中, 我们的确愿意和对手选择随机合作, 但是因为资源的限制, D 是不可避免的. 但是我们不会让 D 永远下去, 我们每轮和随机的对手选择一次随机的合作, 这样就不会被怪圈所左右. 这个就是 bt 协议跳出冤冤相报的精髓. 一旦知道了这个, 本文思想就差不多介绍完了. 下面就是程序员的编码工作了. 下面的内容完全是基于 Bram Cohen (bt 协议创始人) 的经典论文 “Incentives Build Robustness in BitTorrent” ( http://www.bittorrent.org/bittorrentecon.pdf ) 里面的内容展开的. 我只介绍和博弈论有关的部分. 读英文更加习惯的读者直接看原论文比读下面的文章更加好.

首先说点背景知识, bt 把文件看成一块一块的, 并且用一定的排序算法决定现在能够下载哪一块. 其次, bt 协议同时和多个机器之间建立 TCP 连接, 但是采用堵塞的方法控制传输. 因为建立连接代价比较大, 所以 bt 协议维持连接不变, 在其上采用 choking (堵塞) 的方法来执行 D 策略, 采用 un-choking 的方法来执行 C 策略, 而不是每次都重新建立和取消连接. IP 协议在这方面有天然的优势.

每次, BT 协议选择 k (通常为7, 限速的情况下为2, 3, 或 4) 个其他的客户端来执行 C 策略(即给上传). 在上一轮中给出最多下载的那些节点, 在本轮将被执行 C 策略(注意到有的节点上一轮并没有给上传, 即从C 到 D). 同时, 为了避免其他的更加好的节点被忽视, 每 m 轮, BT 客户端选择一个随机的 choke 了的节点执行 C 策略 (即从 D 到 C. 同时, 因为资源限制, 必然有一个被 choke 了, 即从 C 到 D).

那么, 什么时候执行 D 呢? 在 BT 协议中, 假如连续 n 轮, 都没有从一个节点收到任何下载, 在 bt 术语中, 这个叫做 snubbed. 这时候, 则该节点认为自己被那个结点执行D策略了. 作为报复, 自己也停止对该节点的上传(即以牙还牙, 从 C 到 D. ). 除非等到下次随机的选到了那个节点(再次到 C ).

这就是 bt 的协议关于博弈论的全部. 其中, 一轮持续时间在现在的实现中是 10 秒. m 为 3, n 为 6. 目前暂不清楚 Bram Cohen 是否通过实验得到这些参数, 有兴趣的读者可以自己查阅 bt 源代码, 改一下, 看看哪个更加好. 同时, 因为其他客户端采用的是 Tit for Tat, 想把自己的客户端改成吸血bt 是不可行的, 也占不到别人便宜.

PS: 有兴趣的读者可阅读 bt 源代码中的 Choker.py. BT 源代码用 Python 写成, 比较好懂.

作者: 翔子 时间: 2010-5-24 16:25
标题: 编程珠玑番外篇-C.正则表达式精义-1
很多天前和 zuola 聊天, 偶然提到正则表达式, zuola 说, 会正则表达式的都是牛人. 我说, 其实不难, 买本书看看就会了. 这几天, zuola 又在我博客上留言说会正则表达式才是真的程序员, 因此我想, 还是写篇比较浅显的教程, 让 zuola 同学快速成为牛人吧.

对于普通人来说, 正则表达式是比较难的. 从我个人的体验来看也是一样. 这个难, 主要在于两方面: 1. 接受正则表达式的思维方式; 2. 熟悉表达式里面各种各样的符号的用法. 第一点的难度在于这是个新东西, 和以前的知识结构不一样; 第二点的难度在于各种各样的环境下都对最基本的正则表达式做了很多扩展, 引入了各种各样的新的符号, 这样, 就使得学的时候一下子面对太多的复杂度不知所措. 举例来说, 大多数教程把 ^$*+-[](){}|.?\ 这些符号全部放到一起讲, 全然不分他们的层次关系, 导致学习者云里雾里. 同时, 不同的工具又定义了自己的特殊规则, 使得学习曲线更加陡峭. 因此, 我打算把正则表达式的知识点, 分几个不同的层次, 一一剖析. 在这一部分中, 我把正则表达式琐碎的细节一一剔除, 希望看到这篇文章的, 愿意学习正则表达式的读者, 能够迅速从这些繁琐的细节中解脱出来, 掌握其本质.

首先说正则表达式是什么. 正则表达式是一种描述性的语言, 用来概括一类字符串 (或者说一个字符串集合). 我们当然可以用自然语言来描述一类字符串, 比如我们说, 以 “010 开头的电话号码”, “夹在HTML 的 <b> 和 </b> 中间的内容”, “含有 hello 的字符串”, “负数”, “IP地址” “邮箱地址”, 等等. 其实在实际应用中, 我们也常常有这个需求, 比如说提取一篇邮件中所有的 email 地址 (查找), 或者把提取某类电话号码, 升个位, 加个区号什么的 (替换). 人当然可以做这个事情, 但是这个事情重复且单调, 又并不需要太多的智力, 因此, 计算机是最好的工具. 但是问题是, 我们怎么能够告诉计算机, 我们对哪类字符串感兴趣呢? 计算机科学家就帮我们设计了一种让人能够简单的写出来, 表达我们人类想表达的含义, 而计算机又恰好能够很容易的理解和处理的一种表达式, 这就是正则表达式了. 从人和计算机的角度说, 正则表达式是一种人和计算机都能轻松处理的约定, 用来描述一类具有某个性质的字符串.

正则表达式它既有倾向于人的思考方式的一面, 也有倾向于计算机工作原理 (有限自动机) 的一面. 因此, 传统意义上, 如果想真正理解正则表达式, 就要从理解计算机原理入手. 所幸的是, 我们普通用户, 在日常使用中, 并不需要了解计算机的原理, 因为这么多年技术的发展给了正则表达式很多新特性, 让正则表达式越来越脱离计算机的局限, 变得更加适合复杂的任务, 但这样的代价是正则表达式的细节越来越繁杂了, 对于初学者来说更加难学了. 因此我们在这里, 先讲本质, 后谈细节.

最基本的正则表达式, 只有三句话:

一个字符串是一个正则表达式, 比如 aaa, 就是一个正则表达式, 它描述了一个字符串集合, 这个字符串集合里面只有 aaa 这一个元素

两个正则表达式可以直接串起来, 比如 aaabbb 其实, 是由六个正则表达式 a a a b b b 接起来组成的. 我们先笼统的说, 接起来就等于把描述的内容接起来, 等一下再详细解释接起来的含义.

两个字符串, 比如 aaa 和 bbb, 用 | 连起来, 变成了 aaa|bbb, 也构成一个正则表达式, 它描述的字符串集合是原来分别的并集, 比如 aaa|bbb 描述了一个集合, 这个集合里面有 {aaa, bbb} 两个字符串.

好了, 就这两三话, 就可以解释正则表达式最基本的思维方式了: 用一个表达式, 去描述一类字符串(或者说, 一个集合).

光有这两个, 还不够强大, 因为上面的正则表达式, 我写几个, 就描述了几个字符串, 也就是说, 描述来, 描述去, 都是有限的集合, 不能描述无限的集合. 而我们想要描述的整数啊, 域名啊, 邮箱地址啊, 都是一切就有可能的, 因此, 我们有必要引入一个新的记号, 能够描述无限的集合,一个正则式 X 可以加上一个 *, 用来描述任意多个原来 X 描述的字符串拼起来的字符串.

这句话比较费解, 我们用例子来说明一下, 比如 a* 这个正则表达式, 我们知道 a 描述了一类字符, 这类字符里面只有一个 a, 所以, a* 描述了一个或者多个 a.

我们再看 a | b* , 按照定义, 这个正则表达式描述了 a 和 b, bb, bbb 等. 如果我们引入一个括号, 写成 (a|b)* , 那么 a|b 就变成一个整体, 描述了 a 或者 b, 这时候, (a|b)* 就是一切只由 a, b 组成的字符串. 这里的括号, 是为了避免歧义, 表示 * 是作用在 a|b 整体上的. 这时候, (a|b) 描述了 a 和 b, 整体加了一个 *, 意味者我们可以任意选 a 或者 b 一个接一个拼起来, 所以, aba, aab 都是在 (a|b)* 的那一类里面的. 注意, * 可以匹配 0 个, 就是说, 这里面包含了什么都没有. 比如说 ab*c 也描述了 ac, 因为中间可以有 0 个 b. 如果您想至少要一个b, 可以写成 abb*c.

为了帮助您理解接起来, 我们再看一个复杂的例子, o(n|ff). 我们知道, n|ff 描述了 n 或者 ff. 当我们直接把 o 接在前面的时候, 描述的是 on 或者 off. 就是说, 接起来的时候, 要把 o 和后面每种情况都组合一次. 我们再看 (a|o)(n|ff). 前面描述的是 a 或者 o, 后面描述的是 n 或者 ff, 接起来, 描述了 an, aff, on, off.

我们都知道, 正则表达式描述的是一类字符串, 所以, X 和 Y 在接起来变成 XY 以后, 自然的变成了描述每一种 X 里面的字符串和 Y里面字符串接起来的情况. 同样, * 好像把 X 和自己接起来多次一样 (可以是任意次), 每次只要接起来的是X里面的字符串, 就一定被 X* 所表述.

(熟悉集合的朋友立即知道正则表达式是用一个表达式代表了一个集合, X|Y 等价于两个集合的并集, 而 XY 拼起来等价于他们所有的元素 x, y 拼起来的集合).

好了, 恭喜您, 您已经学会正则表达式了. 真的, 你已经全部学会了正则表达式的知识. 不过不着急, 我们先回顾一下正则表达式的要点:

1. 正则表达式由普通的字符, 以及几个特殊的字符, 即括号 (), 或者 | 和星号 * 组成. 用来描述一类字符.

2. | 表示或者. 如果有两个正则表达式 X 和 Y, 那么 X|Y 就描述了原来 X 描述的和 Y 描述的.

3. 正则表达式可以接起来, 变成一个更长的, 描述了一个各个部分被那些被接起来的正则表达式描述的字符串.

4. () 是为了避免歧义.

我们上面说的这四个, 就是 100% 如假包换的正则表达式了. 以后的, 都是为了更加方便的使用正则表达式, 而又引入的一些扩展. 恰恰是这些扩展, 让初学者陷入了细节的泥潭. 我们在下一节, 一个一个的来对付诸如 +, [, -, ], ^, $, {m}, 等这些非基本的高级的功能. 需要强调的是, 这些高级的功能, 其实都只是为了人书写方便, 而且是完全可以用我们这里说的最基本的几个规则代替的. 这些高级功能, 我们下节再讲.

练习:

写出匹配以下性质字符串的正则表达式:
1. 字符串 2009
2. 周曙光同学有两个名字, 分别叫做 zola 和 zuola, 人们常常混淆. 请帮周曙光同学设计一个正则表达式, 可以帮他匹配自己的名字.
3. 二进制数字 (最少有一位, 但只含有 0 或者 1的)
4. 非零的十进制数字 (有至少一位数字, 但是不能以0开头)

练习软件:
有一些比较好的软件帮你学习正则表达式, 我推荐初学者用 egrep. 可以在 windows 下用, 具体用法是在命令行打入 egrep “正则表达式” 文件名
egrep 会把文件里面和正则表达式匹配的行 (该行含有一个字符串, 被正则表达式描述了) 打出来. egrep -o “正则表达式” 文件名的话就会只打出那个完全匹配的字符串, 而不是行. 另外, 在 Linux 下可以用 grep –color “表达式” 文件名, 这样, 匹配上的那个字符串, 会被高亮显示出来.

练习文件:
0108200920088964
zuola -d
zooooola
world hello -012012 2009
0909 zola zhou
0101001
zuola

(把这个文件存成文本文件, 用 windows 的朋友可以放在您的 “我的文档” 里面, 因为 cmd 就是从那里开始运行. 然后您[url=http://analyser.oli.tudelft.nl/regex/egrep.exe]下载一下 egrep 做实验)

答案:
1. 2009
2. z(|u)ola [或者您可以写成 zuola|zola]
3. (0|1)(0|1)*
4. (1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
你会看到第四题的答案很笨拙, 居然写了这么长. 后面的大部分细节, 就是为了诸如此类的写得更加简洁一点.

Update:
1. 按照 AW 的留言和他的博客上的读者留言, 这个在线网站可以在线测试正则表达式:
[url=http://gskinner.com/RegExr/]http://gskinner.com/RegExr/

2. 如果要论正则表达式方面的参考书的话, 我推荐 < 精通正则表达式>, 中文版余晟同学翻译的, 质量上乘. 这本书可能是正则表达式方面唯一的一本圣经了, 上次我也是直接推荐给 zuola. 本来我是想打算写完了所有的初级教程再推荐的, 所以在本文初稿中没有提到这本参考书.

3. 才和 zuola 聊天, 他说要讲点具体的 blogger 用到的例子. 其实我之所以没在这篇文章里面讲, 就是因为这样的例子, 都是和应用程序结合的, 需要 sed, htaccess, awk 或者 linux 管道的具体知识, 我就是想解开这些知识的耦合. 一下子看着天书一样的 sed 替换表达式, 是很难一下子学会的. 他的建议是非常有价值的, 可能在本系列最后, 我会补充一篇 blogger 常用的正则表达式用例.

作者: 翔子 时间: 2010-5-24 16:27
标题: 编程珠玑番外篇-D. 高级语言怎么来的-1
终于放暑假了, 有心情来八卦了. 我主要想八卦一下高级语言的设计思想和各种范式的来龙去脉, 也就是回答这个问题: 编程语言为什么会发生成现在这个样子哩?　这里面的奥妙又在哪里哩? 我尝试着把这个系列的八卦写下去, 包括虚拟机的设计, 线程的设计, 栈和寄存器两大流派的来龙去脉等等, 也算是[url=http://blog.youxu.info/2008/12/22/]完成年初给大家许下的诺言.

高级编程语言的创始纪上写道:”初, 世间无语言, 仅电路与连线. 及大牛出, 天地开,　始有FORTRAN,　LISP. ALGOL 随之, 乃有万种语.” 我们都知道, LISP 是基于递归函数的, FORTRAN 是做科学计算的. 现在的C 等等, 都比较像 FORTRAN 不像 LISP. 可是很少有人知道, 最初, FORTRAN 是不支持函数递归调用的, 而LISP是一生下来就支持的, 所有高级语言里面的递归调用, 都是逐渐从 LISP 那里学来的. 这段尘封的历史非常有趣, 值得八卦一番.

一般人学编程, 除了写 Hello World 之外, 人生写的第二个程序, 不是阶乘就是菲波拉契数列,　要不就是汉洛塔. 而这几个程序, 基本上都是因为函数的递归调用才显得简单漂亮. 没有递归的日子里, 人民非常想念您. 可是, 第一版的 FORTRAN 就居然居然不支持递归. 细心的读者要问了, 不支持递归的语言能图灵完全么?　当然可以, 图灵机就是没递归的典型的例子. 但是没递归调用的程序会很难写, 尤其像汉诺塔这种. 那么, FORTRAN 他怎么就悍然不支持递归呢, 让我们回到 1960 年.

话说当年,　IBM 是计算机行业的领军者.　那时候的计算机,　都是比柜子还大的大家伙, 至于计算能力嘛, 却比你的手机还弱.　那时候计算机所做的最多的事情,　不是发邮件打游戏,　而是作计算.　作计算嘛,　自然需要一种和数学语言比较接近的编程语言.　于是,　1960年, IBM　就捣鼓出了 FORTRAN, 用行话说,　就是公式翻译系统.　这个公式翻译系统,　就成了世界上第一个编程语言. 这个编程语言能做数学计算,　能作条件判断,　能 GOTO.　用现在的眼光看,　这个语言能构模拟图灵机上的一切操作,　所以是图灵完全的.　学过数值计算的同学都知道, 科学计算无非就是一大堆数学计算按照步骤进行而已. 所以, 一些控制判断语句, 数学公式加上一个数组, 基本上就能完成所有的科学计算了. IBM 觉得这个语言够用了, 就发布了 FORTRAN　语言规范, 并且在自家的大型机上实现了这个语言.　

在实现这个语言的时候, IBM　的工程师要写一个 FORTRAN 编译器 (请注意那时候的大型机没有操作系统). 那时候的编译器都是用机器语言或者很低级的汇编语言写成的, 所以编译器要越简单越好. 这些工程师觉得,　弄一个让用户运行时动态开辟内存的机制太麻烦了,　所以干脆,　强迫用户在写程序的时候,　就要定好数组的大小,　变量的类型和数目. 这个要求并不过分, 因为在科学计算中, 数组的维度, 用到的变量等, 在计算之前, 就是可以知道大小的. 用现在的话说,　就是不能动态开辟内存空间, 也就相当于没有 malloc 的 C, 或者没有 new 的 C＋＋. 这样的好处是, 一个程序要多少内存, 编译的时候就知道的一清二楚了. 这个主意看上去很聪明, 不过 IBM 的工程师比你想得更加聪明, 他们想, 既然一个程序或者子程序要多少内存在编译的时候都知道了, 我们干脆就静态的把每个子程序在内存中的位置, 子程序中参数, 返回值和局部变量放的位置, 大小都定好, 不久更加整齐高效么. 是的, 我们都知道, 在没有操作系统管理的情况下, 程序的内存策略越简单越好, 如果内存放的整整齐齐的, 计算机的管理员就能够很好的管理机器的内存, 这样也是一件非常好的事情. (再次强调, 当年还没有操作系统呢, 操作系统要等到 1964年发布的 IBM 360 才有, 具体开发一个操作系统之难度可参考< 人月神话>).

可是, 聪明的读者一下子就看出来了, 这样静态的搞内存分配, 就递不成归不了了. 为啥呢. 试想, 我有个 Fib 函数, 用来计算第 N 个菲波拉契数. 这个函数输入一个整数, 返回一个整数, FORTRAN 编译器帮我把这个函数给静态分配了. 好, 我运行 Fib(5) 起来, FORTRAN 帮我把 5 存在某个专门给输入参数的位置. 我在 Fib(5) 里面递归的调用了Fib(4), FORTRAN 一看, 哈, 不还是 Fib 么, 参数是 4, 我存. 这一存, 新的参数4, 就把原来的 5 给覆盖掉了, 新的返回值, 也把原来的返回值给覆盖掉了. 大事不好了, 这么一搞, 新的调用的状态居然覆盖了老的调用, 这下, 就没法返回原来的 Fib(5) 了, 这样一搞, 怎么递归啊?

IBM 这些写编译器的老前辈们, 不是不知道这个问题, 而是压根就鄙视提出这个问题的人: 你丫科学计算递归什么呀, 通通给我展开成循环, 展不开是你数学没学好, 想用递归, 你就不要用 FORTRAN 了. 那时候 IBM 乃是老大, 只有他们家才生产大型机, 老大发话, 下面的消费者只能听他的.

既然软件不支持, 硬件也就可以偷工减料嘛, 所以, 硬件上, 就压根没有任何栈支持. 我们都知道, 计算机发展史上, 软件和硬件是相互作用的. 我们现在也很难猜测, 是IBM 的软件工程师因为 IBM 的硬件工程师没有在硬件上设计出堆栈所以没有能在 FORTRAN 里面设计出递归调用呢, 还是 IBM 的硬件工程师觉得既然软件没要求, 我就不设计了呢? 不管怎么样, 我们看到的是, 1960 年前, 所有的机器的硬件都没有直接支持栈的机制. 熟悉CPU的都知道, 现代 CPU 里面, 都有两个至关重要的地址寄存器, 一个叫做 PC, 用来标记下一条要执行的指令的位置, 还有一个就是栈顶指针 SP. 如果没有后者, 程序之间的调用就会非常麻烦, 因为需要程序员手工维护一个栈, 才能保证程序之间调用最后还能正确的返回. 而当年, 因为 FORTRAN 压根就不支持递归, 所以支持 FORTRAN 的硬件, 就省去了栈指针了. 如果一个程序员想要递归调用, 唯一的实现方法, 就是让程序员借用一个通用寄存器作为栈指针, 自己硬写一个栈, 而且不能用 FORTRAN.

因为　FORTRAN 不支持递归调用, 按照自然规律, 自然会有支持递归的语言在同时代出现. 于是, 很快的, LISP 和 ALGOL 这两个新语言就出道了. 我们只说 LISP. 它的创始人 [url=http://en.wikipedia.org/wiki/John_McCarthy_(computer_scientist)]John McCarchy 是　MIT　教授, 也是人工智能之父, 是学院派人物. 他喜欢丘齐的那一套 [url=http://en.wikipedia.org/wiki/Lambda_calculus]Lambda 演算, 而非图灵的机械构造. 所以, LISP 从一开始, 就支持递归的调用, 因为递归就是　lambda 演算的灵魂. 但是有两大问题摆在　McCarchy 面前. 一是他的 LISP 理论模型找不到一个可以跑的机器, 二是他的　LISP 模型中有一个叫做　eval 的指令, 可以把一个字符串当成指令在运行时求值, 而这个, 当时还没有人解决过. 按照 Paul Graham 大叔在他的 Hackers and Painters 里面的说法, McCarchy 甚至压根就不想实现这个 eval 指令, 因为当 IBM 的一个叫 [url=http://en.wikipedia.org/wiki/Steve_Russell]Steve Russell的工程师宣称要实现 eval 的时候, McCarthy 还连连摇手说理论是理论, 实际是实际, 我不指望这个能被实现. 可是, Russell 居然就把这两个问题一并给解决了(这哥们也是电子游戏创始人, 史上第一个电子游戏就是他写的, 叫　Space War).　他的方法, 说来也简单, 就是写了一个解释器, 让　LISP 在这个解释器里面跑. 这个创举, 让传统上编译－> 运行的高级语言流程, 变成了　编写-> 解释执行的流程, 也就是著名的 [url=http://en.wikipedia.org/wiki/REPL]REPL 流程. 他做的事情, 相当于在IBM 的机器上用机器码写了一个通用图灵机, 用来解释所有的　LISP 指令. 这个创举, 就让 LISP 从理论走到了实践.

因为有了运行时的概念, LISP 想怎么递归, 就可以怎么递归, 只要运行时支持一个软件实现的栈就可以了. 上面我也说了, 也就是写解释器的人麻烦一点而已, 写LISP程序的人完全就可以不管下层怎么管理栈的了. 同时, 有了解释器, 也解放了原来动态分配空间的麻烦, 因为现在所有的空间分配都可以由解释器管理了, 所以, 运行时环境允许你动态的分配空间. 对空间分配的动态支持, 随之就带来了一项新技术: 垃圾收集器. 这个技术出现在　LISP 里面不是偶然的, 是解释器的自然要求和归宿. 在 FORTRAN 上本来被绕过的问题, 就在 LISP 里面用全新的方法被解决了. LISP 的划时代意义和解释器技术, 使得伴随的很多技术, 比如抽象语法树, 动态数据结构, 垃圾收集, 字节码等等, 都很早的出现在了 LISP 中, 加上 LISP 本身规则很少, 使用起来非常灵活, 所以, 每当有一项新技术出现, 特别是和解释器和运行时相关的一项新技术出现, 我们就会听到有人说, “这玩意儿 LISP 里早就有了”, 这话, 是有一定道理的.

除了上面的软件模拟之外, MIT 还有一派在作硬件模拟, 这一派, 以后发展成了灿烂一时的　LISP machine, 为日后所有虚拟机理论铺开了一条新路. 这一派在70, 80年代迅速崛起, 然后随着　PC 的兴起又迅速的陨落, 让人唏嘘不已.

最后附送一个八卦: 1960 年的时候, 高级语言编程领域也发生了一件大事, 即　ALGOL 60 的提出. ALGOL 是划时代的标准, 我们今天用的　C/Java 全是　ALGOL 家族的. ALGOL 注意到了　FORTRAN 的不支持递归的问题, 于是从一开始, 就订立标准支持递归. 但是, 处理递归需要很小心的安排每个函数每次调用的地址和所谓的活动窗口(Active Frame), 而并不是每个编译器都是牛人写的, 所以在处理递归这样一个新事物上, 难免会出点小问题和小 BUG. 这时候, 搞笑的高爷爷(Knuth) 出场了, 他提出了一个测试, 叫做 “是男人就得负67″. (The man or boy test). 恕我功底不深, 不能给各位读者把这个男人测试的关窍讲清楚, 但是, 我知道, 这个测试, 乃是看 ALGOL 60 编译器有没有正确的实现递归和外部引用的. 照高爷爷的说法, 真的男人要能得到正确答案, 不是男人的就得不到正确答案. 当然, 高爷爷当时自己也没有男人编译器, 所以自己猜了一个 -121, 后来, 真的男人编译器出来了, 正确答案是 -67. 可见, 高爷爷的人脑编译器, 也不是男人编译器…

各位欲知详情的, 猛点[url=http://en.wikipedia.org/wiki/Man_or_boy_test]这个.

作者: 翔子 时间: 2010-5-24 16:29
标题: 编程珠玑番外篇-E. 高级语言怎么来的-2
虚拟机的前世今生[url=http://blog.youxu.info/2009/05/13/hpl/]上节我们提到了 LISP 中, 因为 eval 的原因, 发展出了运行时环境这样一个概念。基于这个概念，日后发展出了虚拟机技术。但这段历史并不是平铺直叙的，实际上，这里面还经历了一个非常漫长而曲折的过程，说起来也是非常有意思的。这一节我们就着重解释虚拟机的历史。
我们 21 世纪的程序员，凡要是懂一点编程技术的，基本上都知道虚拟机和字节码这样两个重要的概念。所谓的字节码 ([url=http://en.wikipedia.org/wiki/Bytecode]bytecode)，是一种非常类似于机器码的指令格式。这种指令格式是以二进制字节为单位定义的（不会有一个指令只用到一个字节的前四位），所以叫做字节码。所谓的虚拟机，就是说不是一台真的计算机，而是一个环境，其他程序能在这个环境中运行，而不是在真的机器上运行。现在主流高级语言如 Java, Python, PHP, C#，编译后的代码都是以字节码的形式存在的，这些字节码程序，最后都是在虚拟机上运行的。

1. 虚拟机的安全性和跨平台性
虚拟机的好处大家都知道，最容易想到的是安全性和跨平台性。安全性是因为现在可执行程序被放在虚拟机环境中运行，虚拟机可以随时对程序的危险行为，比如缓冲区溢出，数组访问过界等等进行控制。跨平台性是因为只要不同平台上都装上了支持同一个字节码标准的虚拟机，程序就可以在不同的平台上不加修改而运行，因为虚拟机架构在各种不同的平台之上，用虚拟机把下层平台间的差异性给抹平了。我们最熟悉的例子就是 Java 了。Java 语言号称 一次编写，到处运行(Write Once, Run Anywhere)，就是因为各个平台上的 Java 虚拟机都统一支持 Java 字节码，所以用户感觉不到虚拟机下层平台的差异。
虚拟机是个好东西，但是它的出现，不是完全由安全性和跨平台性驱使的。

2. 跨平台需求的出现
我们知道，在计算机还是锁在机房里面的昂贵的庞然大物的时候，系统软件都是硬件厂商附送的东西（是比尔盖茨这一代人的出现，才有了和硬件产业分庭抗礼的[url=http://en.wikipedia.org/wiki/Software_company]软件产业），一个系统程序员可能一辈子只和一个产品线的计算机打交道，压根没有跨平台的需求。应用程序员更加不要说了，因为计算机很稀有，写程序都是为某一台计算机专门写的，所以一段时间可能只和一台庞然大物打交道，更加不要说什么跨平台了。真的有跨平台需求，是从微型计算机开始真的普及开始的。因为只有计算机普及了，各种平台都被广泛采用了，相互又不互相兼容软件，才会有软件跨平台的需求。微机普及的历史，比 PC 普及的历史要早10年，而这段历史，正好和 UNIX 发展史是并行重叠的。
熟悉 UNIX 发展史的读者都知道， UNIX 真正普及开来，是因为其全部都用 C，一个当时绝对能够称为跨平台的语言重写了一次。又因为美国大学和科研机构之间的开源共享文化，C 版本的 UNIX 出生没多久，就迅速从原始的 PDP-11 实现，移植到了 DEC，Intel 等平台上，产生了无数衍生版本。随着跨平台的 UNIX 的普及，微型计算机也更多的普及开来，因为只需要掌握基本的 UNIX 知识，就可以顺利操作微型计算机了。所以，微机和 UNIX 这两样东西都在 1970年到 1980 年在美国政府，大学，科研机构，公司，金融机构等各种信息化前沿部门间真正的普及开来了。这些历史都是人所共知耳熟能详的。
既然 UNIX 是跨平台的，那么，UNIX 上的语言也应当是跨平台的（注: 本节所有的故事都和 Windows 无关，因为 Windows 本身就不是一个跨平台的操作系统）。UNIX 上的主打语言 C 的跨平台性，一般是以各平台厂商提供编译器的方式实现的，而最终编译生成的可执行程序，其实不是跨平台的。所以，跨平台是源代码级别的跨平台，而不是可执行程序层面的。而除了标准了 C 语言外，UNIX 上有一派生机勃勃的跨平台语言，就是脚本语言。（注：脚本语言和普通的编程语言相比，在能完成的任务上并没有什么的巨大差异。脚本语言往往是针对特定类型的问题提出的，语法更加简单，功能更加高层，常常几百行C语言要做的事情，几行简单的脚本就能完成）

3. 解释和执行
脚本语言美妙的地方在于，它们的源代码本身就是可执行程序，所以在两个层面上都是跨平台的。不难看出，脚本语言既要能被直接执行，又要跨平台的话，就必然要有一个“东西”，横亘在语言源代码和平台之间，往上，在源代码层面，分析源代码的语法，结构和逻辑，也就是所谓的“解释”；往下，要隐藏平台差异，使得源代码中的逻辑，能在具体的平台上以正确的方式执行，也就是所谓的“执行”。
虽说我们知道一定要这么一个东西，能够对上“解释”，对下“执行”，但是 “解释” 和 “执行” 两个模块毕竟是相互独立的，因此就很自然的会出现两个流派：把解释和执行设计到一起 和 把解释和执行单独分开来 这样两个设计思路，需要读者注意的是，现在这两个都是跨平台的，安全的设计，而在后者中字节码作为了解释和执行之间的沟通桥梁，前者并没有字节码作为桥梁。

4. 解释和执行在一起的方案
我们先说前者，前者的优点是设计简单，不需要搞什么字节码规范，所以 UNIX 上早期的脚本语言，都是采用前者的设计方法。我们以 UNIX 上大名鼎鼎的 AWK 和 Perl 两个脚本语言的解释器为例说明。 AWK 和 Perl 都是 UNIX 上极为常用的，图灵完全的语言，其中 AWK, 在任何 UNIX 系统中都是作为标准配置的，甚至入选 IEEE POSIX 标准，是入选 IEEE POSIX 卢浮宫的唯一同类语言品牌，其地位绝对不是 UNIX 下其他脚本语言能够比的。这两个语言是怎么实现解释和运行的呢？我从 AWK 的标准实现中摘一段代码您一看就清楚了:
int main(int argc, char *argv[]) { ... syminit(); compile_time = 1; yyparse(); ... if (errorflag == 0) { compile_time = 0; run(winner); } ...}其中, run 的原型是
run(Node *a) /* execution of parse tree starts here */
而 winner 的定义是:
Node *winner ; /* root of parse tree */
熟悉 Yacc 的读者应该能够立即看出, AWK 调用了 Yacc 解析源代码，生成了一棵语法树。按照 winner 的定义, winner 是这棵语法树的根节点。在“解释”没有任何错误之后，AWK 就转入了“执行” (compile_time 变成了 0)，将 run 作用到这棵语法树的根节点上。不难想像，这个 run 函数的逻辑是递归的（事实上也是），在语法树上，从根依次往下，执行每个节点的子节点，然后收集结果。是的，这就是整个 AWK 的基本逻辑: 对于一段源代码, 先用解释器（这里awk 用了 Yacc 解释器），生成一棵语法树，然后，从树的根节点开始，往下用 run 这个函数，遇山开山，遇水搭桥，一路递归下去，最后把整个语法树遍历完，程序就执行完毕了。（这里附送一个小八卦，抽象语法树这个概念是 LISP 先提出的，因为 LISP 是最早像 AWK 这样做的，LISP 实在是属于开天辟地的作品！）Perl 的源代码也是类似的逻辑解释执行的，我就不一一举例了。

5. 三大缺点
现在我们看看这个方法的优缺点。优点是显而易见的，因为通过抽象语法树在两个模块之间通信，避免了设计复杂的字节码规范，设计简单。但是缺点也非常明显。最核心的缺点就是性能差，需要资源多，具体来说，就是如下三个缺点。
缺点1，因为解释和运行放在了一起，每次运行都需要经过解释这个过程。假如我们有一个脚本，写好了就不修改了，只需要重复的运行，那么在一般应用下尚可以忍受每次零点几秒的重复冗余的解释过程，在高性能的场合就不能适用了。
缺点2，因为运行是采用递归的方式的，效率会比较低。 我们都知道，因为递归涉及到栈操作和状态保存和恢复等，代价通常比较高，所以能不用递归就不用递归。在高性能的场合使用递归去执行语法树，不值得。
缺点3，因为一切程序的起点都是源代码，而抽象语法树不能作为通用的结构在机器之间互传，所以不得不在所有的机器上都布置一个解释+运行的模块。 在资源充裕的系统上布置一个这样的系统没什么，可在资源受限的系统上就要慎重了，比如嵌入式系统上。鉴于有些语言本身语法结构复杂，布置一个解释模块的代价是非常高昂的。本来一个递归执行模块就很吃资源了，再加一个解释器，嵌入式系统就没法做了。所以，这种设计在嵌入式系统上是行不通的。
当然，还有一些其他的小缺点，比如有程序员不喜欢开放源代码，但这种设计中，一切都从源代码开始，要发布可执行程序，就等于发布源代码，所以不愿意公布源代码的商业公司很不喜欢这些语言等等。但是上面的三个缺点，是最致命的，这三个缺点，决定了有些场合，就是不能用这种设计。

6. 分开解释和执行
前面的三个主要缺点，恰好全部被第二个设计所克服了。在第二种设计中，我们可以只解释一次语法结构，生成一个结构更加简单紧凑的字节码文件。这样，以后每次要运行脚本的时候，只需要把字节码文件送给一个简单的解释字节码的模块就行了。因为字节码比源程序要简单多了，所以解释字节码的模块比原来解释源程序的模块要小很多；同时，脱离了语法树，我们完全可以用更加高性能的方式设计运行时，避免递归遍历语法树这种低效的执行方式；同时，在嵌入式系统上，我们可以只部署运行时，不部署编译器。这三个解决方案，预示了在运行次数远大于编译次数的场合，或在性能要求高的场合，或在嵌入式系统里，想要跨平台和安全性，就非得用第二种设计，也就是字节码+虚拟机的设计。
讲到了这里，相信对 Java, 对 PHP 或者对 Tcl 历史稍微了解的读者都会一拍脑袋顿悟了: 原来这些牛逼的虚拟机都不是天才拍脑袋想出来的，而是被需求和现实给召唤出来的啊！
我们先以 Java 为例，说说在嵌入式场合的应用。Java 语言原本叫 Oak 语言，最初不是为桌面和服务器应用开发的，而是为机顶盒开发的。SUN 最初开发 Java 的唯一目的，就是为了参加机顶盒项目的竞标。嵌入式系统的资源受限程度不必细说了，自然不会允许上面放一个解释器和一个运行时。所以，不管Java 语言如何，Java 虚拟机设计得直白无比，简单无比，手机上，智能卡上都能放上一个 Java 运行时（当然是精简版本的）。这就是字节码和虚拟机的威力了。
SUN 无心插柳，等到互联网兴起的时候, Java 正好对绘图支持非常好，在 Flash 一统江湖之前，凭借跨平台性能，以 Applet 的名义一举走红。然后，又因为这种设计先天性的能克服性能问题，在性能上大作文章，凭借 JIT 技术，充分发挥上面说到的优点2，再加上安全性，一举拿下了企业服务器市场的半壁江山，这都是后话了。
再说 PHP。PHP 的历史就包含了从第一种设计转化到第二种设计以用来优化运行时性能的历史。 PHP 是一般用来生成服务器网页的脚本语言。一个大站点上的PHP脚本, 一旦写好了，每天能访问千百万次，所以，如果全靠每次都解释，每次都递归执行，性能上是必然要打折扣的。所以，从 1999年的 PHP4 开始， Zend 引擎就横空出世，专门管加速解释后的 PHP 脚本, 而对应的 PHP 解释引擎，就开始将 PHP 解释成字节码，以支持这种一次解释，多次运行的框架。在此之前， PHP 和 Perl, 还有 cgi, 还算平分秋色的样子，基本上服务器上三类网页的数量都差不多，三者语法也很类似，但是到了 PHP4 出现之后，其他两个基于第一种设计方案的页面就慢慢消逝了，全部让位给 PHP。你读的我的这个 Wordpress 博客，也是基于 PHP 技术的，底层也是 Zend 引擎的。著名的 LAMP 里面的那个 P，原始上也是 PHP，而这个词真的火起来，也是 99年 PHP4 出现之后的事情。
第二种设计的优点正好满足了实际需求的事情，其实不胜枚举。比如说在 Lua 和 Tcl 等宿主语言上也都表现的淋漓尽致。像这样的小型语言，本来就是让运行时为了嵌入其他语言的，所以运行时越小越好，自然的，就走了和嵌入式系统一样的设计道路。

7. 结语
其实第二种设计也不是铁板一块，里面也有很多流派，各派有很多优缺点，也有很多细致的考量，下一节，如果不出意外，我将介绍我最喜欢的一个内容：下一代虚拟机：寄存器还是栈。
说了这么多，最后就是一句话，有时候我们看上去觉得一种设计好像是天外飞仙，横空出世，其实其后都有现实，需求等等的诸多考量。虚拟机技术就是这样，在各种需求的引导下，逐渐的演化成了现在的样子。

作者: 翔子 时间: 2010-5-24 16:30
标题: 编程珠玑番外篇-F. 高级语言怎么来的-3
FORTRAN 语言是怎么来的在高级语言是怎么来的子系列的[url=http://blog.youxu.info/2009/05/13/hpl/][color=#0000ff]第一篇[/color]中，我们结合当时硬件的特点，分析了 FORTRAN 为什么一开始不支持递归。但是 FORTRAN 本身是怎么来的这个问题其实还是没有得到正面回答，本节我们就谈谈 FORTRAN 语言本身是怎么来的。
其实，FORTRAN 语言也是现实驱动的。所以我们还是回到当时，看看当时程序员的需求和软硬件条件，看看 FORTRAN 是怎么来的。了解历史的另一个好处是，因为 FORTRAN 的发展历史正好和高级语言的发展历史高度重合，所以了解 FORTRAN 的背景，对于理解其他高级语言的产生都是大有帮助的。

[b]1. 困难的浮点计算[/b]
我们先从硬件的角度说起。大致从 1946 年第一台计算机诞生，到 1953 年，计算机一直都缺少两件非常重要的功能，一个叫浮点计算，一个叫数组下标寻址，这两个功能的缺失直接导致了高级语言的兴起。我们依次单个分析。读者对浮点计算应该都不陌生，用通俗的话说就是如 0.98×12.6 这样的实数乘法，或者  0.98 + 12.6 这样的实数加法的运算。用行话说，就是用计算机进行大范围高精度数的算术运算。
学过二进制的同学都知道，二进制整数之间的乘法和加法等运算都是相对简单的，和正常的十进制运算是一样的，只是把加法和乘法这些基本操作用更加简单的逻辑或(OR) 和逻辑与 (AND) 实现而已，在电子电路上也很好实现。因此，就是世界上最早的电子计算机，ENIAC，也是支持整数的乘法加法等算术操作的。
可是浮点运算就不一样了。因为一个额外的小数点的引入，在任何时候都要注意小数点的对齐。如果用定点计数，则计数的范围受到限制，不能表示非常大或者非常小的数。所以，浮点数一般都是用科学记数法表示的，比如 IEEE 754 标准。（不熟悉 IEEE 754 的读者也可以想像一下如何设计一套高效的存储和操作浮点数的规范和标准，以及浮点算法），科学记数法表示的浮点数的加减法每次都要对齐小数点，乘除法为了保持精度，在设计算法上也有很多技巧，所以说，相比较于整数的运算和逻辑运算，浮点运算是一件复杂的事情。落实到硬件上就是说，在硬件上设计一个浮点运算，需要复杂的电路和大量的电子元器件。在早期电子管计算机中，是很少能做到这么大的集成度的。因此，不支持浮点也是自然的设计取舍。在计算机上放一个浮点模块这个想法，需要等电子工业继续发展，使得电子管体积小一点，功耗低一点后，才能进入实践。

[b]2. 关于浮点计算的一些八卦[/b]
关于浮点，这里顺带八卦一点浮点计算的事情。在计算机芯片设计中，浮点计算一直是一个让硬件工程师头疼的事情，即使到了386时代，386 处理器 (CPU)的浮点乘法也是用软件模拟的，如果想用硬件做浮点乘法，需要额外购买一块 80387 浮点协处理器 FPU，否则就在 386 上做软件的模拟。这样做的原因在一块硅片上刻蚀一个 CPU 和一个FPU 需要的集成度还是太高，当时的工艺根本没法实现。真的把 FPU 和 CPU 融在一起刻蚀到一块硅片上，已经是 1989 年的事情了。当时，Intel 把融合了 80386 和 80387 的芯片改了改，起了个名字叫 80486，推向了市场。带着浮点的处理器的普及，使得个人计算机能做的事情变多了。极度依赖于浮点计算的多媒体计算机（视频和声音等多媒体的压缩，转换和回放都是要依赖于浮点运算的），也正好随着 80486 的流行，逐渐普及开来。
在处理器上融合浮点运算依然是困难的。即使到今天，很多低端的处理器，都不带有浮点处理器。所以，号称能够上天入地的，被移植到很多低端设备比如手机上的 Linux 内核，必然是不能支持浮点运算的，因为这样会破坏内核的可移植性。我们都知道，在内核模式下，为了保证内核操作的原子性，一般在内核从事关键任务的时候所有中断是要被屏蔽的，用通俗的话说就是内核在做事情的时候，其他任何人不得打扰。如果内核支持浮点运算，不管是硬件实现也好，软件模拟也罢，如果允许在内核中进行像浮点计算这样复杂而耗时的操作，整个系统的性能和实时响应能力会急剧下降。  即使是在硬件上实现的浮点运算，也不是件容易的事情，会耗费CPU较多的时钟周期，比如 Pentium 上的浮点数除法，需要耗费 39 个时钟周期才行，在流水线设计的CPU中，这种占用多个时钟周期的浮点运算会让整个流水线暂停，让CPU的吞吐量下降。在现代 CPU 设计中，工程师们发明了超标量，乱序执行，SIMD 等多种方式来克服流水线被浮点运算这种长周期指令堵塞的问题，这都是后话了。
正因为对于计算机来说，浮点运算是一个挑战性的操作，但又是做科学计算所需要的基本操作，所以浮点计算能力就成了计算机能力的一个测试标准。我们常常听说有一个世界上前 500 台最快的超级计算机列表，这里所谓的“快”的衡量标准，就是以每秒钟进行多少次浮点计算(FLOPS) 为准。按照 [url=http://top500.org/][color=#0000ff]Top500.org[/color], 即评选世界上前 500 台超级计算机的机构 2009年6月的数据，世界上最快的计算机，部署在美国能源部位于新墨西哥的洛斯阿拉莫斯国家实验室 (Los Alamos National Laboratory)，当年造出第一颗原子弹的实验室。这台超级计算机，浮点计算速度的峰值高达 1456 TFlops，主要用来模拟核试验。因为美国的所有核弹头，海军核动力航母中的反应堆以及核试验，都由能源部国家核安全署(NNSA) 管理，所以能源部一直在投资用超级计算机进行核试验。在 1996 年美国宣布不再进行大规模的物理核试验后的这么多年，美国能源部一直用超级计算机来做核试验，所以在 Top500 列表中，美国能源部拥有最多数量的超级计算机。

[b]3. 数组下标寻址之障[/b]
言归正传，我们刚才说了在早期计算机发展史上，浮点计算的困难。除了浮点计算，还有一件事情特别困难，叫做数组下标寻址。用现代通俗的话说，就是当年的计算机，不直接支持 A[3] 这样的数组索引操作，即使这个操作从逻辑上说很简单：把数组 A 的地址加上 3，就得到了 A[3] 的地址，然后去访问这个地址。
这个困难在今天的程序员看来是不可思议的。为什么这么简单的数组下标寻址机制最一开始的计算机没有支持呢？原来，当年的计算机内存很小，只有一千到两千的存储空间，所以，描述地址只需要几位二/十进制数（[url=http://en.wikipedia.org/wiki/Binary-coded_decimal][color=#0000ff]BCD[/color])。从而，在每条指令后面直接加一个物理地址是可行且高效的寻址方式。这种寻址方式，叫做直接寻址，当时所有的机器，都只支持直接寻址，因为在机器码中直接指出操作数的准确地址是最简单直接的方法，计算机不需要任何复杂的地址解码电路。但坏处是，这个设计太不灵活了，比如说 A[3] 这个例子，就没法用直接寻址来表示。
一般情况下，如果知道数组A，对于 A[3] 这样的例子，用直接寻址问题去模拟间接寻址的困难还不是很大，只要程序员事先记住数组 A 的地址然后手工加上 3 就行了（A也是程序员分配的，因为当时没有操作系统，所以程序员手工管理内存的一切）。可是，也有一些情况这样直接寻址是不行的。比如说，当时计算机已经能支持跳转和判断指令了，也就是说，可以写循环语句了。我们可以很容易看到，以 i 为循环变量的循环体内，对 A[i] 的访问是不能写成一个静态的直接寻址的，因为 i 一直在变化，所以不可能事先一劳永逸的定好 A[i] 的所在位置，然后静态写在程序中。
这样，即使写一个简单的 10×10 矩阵的乘法，程序员就不得不死写 10的三次方即1000 行地址访问，而没办法用几行循环代替。当时的一些聪明人，也想了一些方法去克服这个问题，比如说，他们先取出 A 的地址，然后做一次加法，把结果，也就是当时 A[i] 的地址，注射到一个读内存的 LOAD 指令后面。然后执行那条 LOAD 指令。比如我要读 A[i]，我先看，A的地址是 600，再看看 i 是3，就加上 i，变成603，然后，把后面的指令改成 LOAD 603，这样，就可以读到 A[i]。这个小技巧之所以可行，要感谢冯诺依曼爷爷的体系设计。在冯诺依曼计算机中，数据和程序是混在一起不加区分的，所以程序员可以随时像修改数据一样修改将要运行的下一条程序指令。就这样，靠着这个小技巧, 好歹程序员再也不要用1000行代码表示一个矩阵乘法了。

[b]4. SpeedCoding 的出现[/b]
计算机本来就是用来做数学计算的，可是科学计算里面最最基本的两个要素–浮点计算和数组下标访问，在当时的计算机上都缺少支持。这种需求和实际的巨大落差，必然会召唤出一个中间层来消弭这种落差。其实计算机科学的一般规律就是这样：当 A 和 C 相差巨大的时候，我们就引入一个中间层 B，用 B 来弥合 A 和 C 之间的不兼容。当年的这个中间层，就叫做 SpeedCoding，由 IBM 的工程师 John Backus 开发。
SpeedCoding，顾名思义，就是让程序员编程更快。它其实是一个简单，运行在 IBM 701 计算机上的解释器。它允许程序员直接写浮点计算和下标寻址的指令，并且在底层把这些 “伪指令” 翻译成对应的机器码，用软件模拟浮点计算，自动修改地址等等。这样，程序员就可以从没完没了的手工实现浮点运算和下标寻址实现中解放出来，快速的编程。这个 SpeedCoding，这可以算得上是 FORTRAN 的种子了。
虽然这个解释器超级慢，程序员用这个解释器也用得很爽，也不感到它非常慢。这是因为当年计算机浮点计算都绕不过软件模拟，即使最好的程序员用机器码而不用这个解释器，写出来的程序，也不比这个解释器下运行快多少。另一个更加重要的原因是，这个解释器极大的减少了程序员 debug 和 code 的时间。随着计算机速度的提高，当年一个程序耗费的计算成本和程序员编程耗费的人力成本基本上已经持平了，所以，相比较于写更加底层的机器码，用了 SpeedCoding 的程序员的程序虽然慢点，但人力成本瞬间降成 0，总体下来，用 SpeedCoding 比起不用来，总体成本还要低不少。
好景不长，因为客户一直的要求和电子工业的发展，IBM 在 1954 年，终于发布了划时代的 704 计算机，很多经典的语言和程序，都首次在 704 上完成了。比如之前我们在本系列的D篇中提到的 Steve Russell 的 LISP 解释器，就是在 704 上完成的。 704 计算机一下子支持了浮点计算和间接下标寻址。这下用 SpeedCoding 的人没优势了，因为机器码支持浮点和下标寻址之后，写机器码比写 SpeedCoding 复杂不了多少，但是速度快了很多倍，因为 SpeedCoding 解释器太慢了，以前因为浮点和解释器一样慢，所以大家不在意它慢，现在浮点和寻址快了，就剩下解释器慢，写机器码的反而占了上风，程序员也就不用 SpeedCoding 了。

[b]5. FORTRAN 创世纪[/b]
在 704 出来之前，做 SpeedCoding 的 John Backus 就认识到，要想让大家用他的 SpeedCoding, 或者说，想要从软件工具上入手，减少程序的开发成本，只有两个方法： 1. 程序员可以方便的写数学公式  2. 这个系统最后能够解析/生成足够的快的程序。他认为，只有达到了这两点，程序员才会乐意使用高级的像 SpeedCoding 这样的工具，而不是随着硬件的发展在机器码和 SpeedCoding 这样的工具之间跳来跳去。他本人通过实现 SpeedCoding, 也认识到如果有一个比机器码高级的语言，生产效率会高很多倍。那么，现在唯一的问题就是实现它，当然，这就不是一个小项目了，就需要 IBM 来支持他的开发了。所以，在 1953年，他把他的想法写成了一个文档，送给了 IBM 的经理。项目在 1954 年， 704 发布的当年，终于启动。John Backus 领导的设计一个能达到上面两点的编程系统的项目的成果，就是日后的 FORTRAN。
和现在大多数编程语言不一样，FORTRAN 语言的设计的主要问题不是语法和功能，而是编译器怎么写才能高性能。John Backus 日后回忆说，当时谁也没把精力放在语言细节上，语言设计很潦草的就完成了（所以其后正式发布后又经过了N多修订），他们所有的功夫都是花在怎么写一个高性能的编译器上。这个高性能的编译器很难写，到 1957 年才写好，总共花了 IBM 216 个人月。等到 FORTRAN 一推出，不到一年的时间，在 IBM 总共售出的 60 台 704上，就部署了超过一半。现在没啥编程语言能够这么牛的攻城掠地了：）

[b]6. 结语[/b]
放到历史的上下文中看，FORTRAN 的出现是很自然的。一方面，复杂的数学运算使得一个能够表述数学计算的高级语言成为必须，计算机的发展也为这个需求提供的硬件条件；另一方面，随着计算机的发展，程序员的时间成本一直不变，但是计算的成本一直在降低，用高级语言和用机器码在性能上的些许差异变得可以忽略。这样的历史现实，必然会召唤出以少量的增加计算机工作量为代价，但能大幅度降低程序员时间成本的新的工具和设计。这种新的工具，新的设计，又对程序设计产生革命性的影响。在整个编程发展的历史上，FORTRAN 和其他高级语言的出现可以说是第一波的革命；而后， UNIX和C语言的兴盛，使得系统编程的效率得到革命性提升，可以算是第二波革命；而面向对象方法，使得复杂的 GUI 等系统的编程效率得到提升，应该算得上是第三波革命。到如今，现在各种各样的方法论就更加多了，且看以后回看，哪种方法和工具能够大浪淘沙留下来。

作者: 翔子 时间: 2010-5-24 17:02
标题: 编程珠玑番外篇-H. 高级语言怎么来的-4
LISP 语言是怎么来的–LISP 和 AI 的青梅竹马 ALISP 语言的历史和一些番外的八卦和有趣的逸事，其实值得花一本书讲。我打算用三篇文章扼要的介绍一下 LISP 的早期历史。讲 LISP，躲不过要讲 AI （人工智能）的，所以干脆我就先八卦八卦他们的青梅竹马好了。
翻开任何一本介绍各种编程语言的书，都会毫无惊奇的发现，每每说到 LISP，通常的话就是”LISP 是适合人工智能（AI）的语言”。我不知道读者读到这句话的时候是怎么理解的，但是我刚上大学的时候，自以为懂了一点 LISP 和一点人工智能的时候，猛然看到这句话，打死我也不觉得”适合”。即使后来我看了 SICP 很多遍，也难以想象为什么它就 “适合” 了，难道 LISP 真的能做 C 不能做的事情么？难道仅仅是因为 John McCarthy 这样的神人既是 AI 之父，又是 LISP 之父，所以 AI 和 LISP 兄妹两个就一定是很般配？计算机科学家又不是上帝，创造个亚当夏娃让他们没事很般配干啥？既然本是同根生这样的说法是不能让人信服的，那么到底这句话的依据在哪里呢？我也是后来看 AI 文献，看当年的人工智能的研究情况，再结合当年人工智能研究的指导思想，当年的研究者可用的语言等历史背景，才完全理解“适合” 这两个自的。所以，这篇既是八卦，也是我的心得笔记。我们一起穿越到 LISP 和 AI 的童年时代。虽然他们现在看上去没什么紧密联系，他们小时候真的是青梅竹马的亲密玩伴呢！
让机器拥有智能，是人长久的梦想，因为这样机器就可以聪明的替代人类完成一些任务。二战中高速电子计算机的出现使得这个梦想更加近了一步。二战后，计算机也不被完全军用了，精英科学家也不要继续制造原子弹了，所以，一下子既有资源也有大脑来研究 “智能机器”这种神奇的东西了。我们可以随便举出当年研究繁盛的例子：维纳在 1948 年发表了<控制论>, 副标题叫做 <动物和机器的控制和通信>, 其中讲了生物和机器的反馈，讲了脑的行为。创立信息论的大师香农在 1949 年提出了可以下棋的机器，也就是面向特定领域的智能机器。同时，1949年，加拿大著名的神经科学家 Donald Hebb 发表了“行为的组织”，开创了神经网络的研究；图灵在 1950 年发表了著名的题为“计算的机器和智能”的文章，提出了著名的图灵测试。如此多的学科被创立，如此多的学科创始人在关心智能机器，可见当时的确是这方面研究的黄金时期。
二战结束十年后，也就是 1956 年，研究智能机器的这些研究者，都隐隐觉得自己研究的东西是一个新玩意，虽然和数学，生物，电子都有关系，但和传统的数学，生物，电子或者脑科学都不一样，因此，另立一个新招牌成了一个必然的趋势。John McCarthy 同学就趁着 1956 年的这个暑假，在 Dortmouth 大学（当年也是美国计算机科学发展的圣地之一, 比如说，它是 BASIC 语言发源地），和香农，Minsky 等其他人(这帮人当年还都是年轻人)，一起开了个会，提出了一个很酷的词，叫做 Artificial Intelligence，算是人工智能这个学科正式成立。因为 AI 是研究智能的机器，学科一成立，就必然有两个重要的问题要回答，一是你怎么表示这个世界，二是计算机怎么能基于这个世界的知识得出智能。第一点用行话说就是”知识表示”的模型, 第二点用行话说就是“智能的计算模型”。别看这两个问题的不起眼，就因为当时的研究者对两个看上去很细微的问题的回答，直接造就了 LISP 和 AI 的一段情缘。
我们各表一支。先说怎么表示知识的问题。 AI 研究和普通的编程不一样的地方在于， AI 的输入数据通常非常多样化，而且没有固定格式。比如一道要求解的数学题，一段要翻译成中文的英文，一个待解的 sodoku 谜题，或者一个待识别的人脸图片。所有的这些，都需要先通过一个叫做“知识表示”的学科，表达成计算机能够处理的数据格式。自然，计算机科学家想用一种统一的数据格式表示需要处理多种多样的现实对象，这样，就自然的要求设计一个强大的，灵活的数据格式。这个数据格式，就是链表。
这里我就不自量力的凭我有限的学识，追寻一下为啥链表正好成为理想的数据结构的逻辑线。我想，读过 SICP 的读者应该对链表的灵活性深有感触。为了分析链表的长处，我们不妨把他和同时代的其他数据结构来做一比较。如我在前面的一个系列所说，当时的数据结构很有限，所以我们不妨比较一下链表和同时代的另一个最广泛使用的数据结构-数组-的优劣。我们都知道，数组和链表都是线性数据结构，两者各有千秋，而 FORTRAN 基本上是围绕数组建立的，LISP 则是围绕链表实现的。通过研究下棋，几何题等 AI 问题的表示，我们的读者不难发现， AI 研究关心于符号和逻辑计算远大于数值计算，比如下棋，就很难抽象成一个基于纯数字的计算问题。这样，只能存数字的数组就显得不适合。当然我们可以把数组扩展一下，让这些数组元素也可以存符号。不过即使这样，数组也不能做到存储不同结构的数据。比方说棋类中，车马炮各有各自的规则，存储这些规则需要的结构和单元大小都不一样，所以我们需要一个存储异构数据单元的模块，而不是让每个单元格的结构一样。加上在AI 中，一些数据需要随时增加和修改的。比如国际象棋里，兵第一步能走两步，到底部又能变成皇后等等，这就需要兵的规则能够随时修改，增加，删除和改变。其他问题也有类似的要求，所有的这些，都需要放开数组维度大小一样的约束，允许动态增加和减少某一维度的大小，或者动态高效的增加删除数组元素。而一旦放开了单元格要同构和能随时增加和删除这样两个约束，数组其实就不再是数组了，因为随机访问的特性基本上就丢失了，数组就自然的变成了链表，要用链表的实现。
所以，用链表而不是数组来作为人工智能的统一的数据结构，固然有天才的灵机一动，也有现实需求的影响。当然，值得一提的是，在 Common LISP 这样一个更加面向实践而不是科学研究是 LISP 版本中，数组又作为链表的补充，成了基本的数据结构，而 Common LISP，也就能做图像处理等和矩阵打交道的事情。这个事实更加说明，用什么样的数据结构作为基本单元，都是由现实需求推动的。
当然，科学家光证明了列表能表示这些现实世界的问题还不够，还要能证明或者验证额外的两点才行，第一点是列表表示能够充分的表示所有的人工智能问题，即列表结构的充分性。只有证明了这一点，我们才敢放心大胆的用链表，而不会担心突然跳出一个问题链表表达不了；第二是人工智能的确能够通过对列表的某种处理方法获得，而不会担心突然跳出一个人工智能问题，用现有的对链表的处理方法根本没法实现。只有这两个问题的回答是肯定的时候，列表处理才会成为人工智能的一部分。
对于这两个问题，其实都并没有一个确定的答案，而只是科学家的猜想，或者说是一种大家普遍接受的研究范式（paradigm）。在 1976 年，当年构想 IPL，也就是 LISP 前身的两位神人 Alan Newell 和 Herbert Simon ，终于以回忆历史的方式写了一篇文章。在这篇文章中，他们哲学般的把当时的这个范式概括为：一个物理符号系统对于一般智能行为是既充分又必要的（ A physical symbol system has the necessary and sufficient means for general intelligence action）。用大白话说就是，“智能必须依赖于某种符号演算系统，且基于符号演算系统也能够衍生出智能”。在实践中，如果你承认这个猜想，或者说这个范式，那你就承认了可以用符号演算来实现 AI。于是，这个猜想就让当时几乎所有的研究者，把宝押在了实现一个通用的符号演算系统上，因为假如我们制造出一个通用的基于符号演算的系统，我们就能用这个系统实现智能。
上面我们说过，链表的强大的表达能力对于这个符号演算系统来讲是绰绰有余的了，所以我们只要关心如何实现符号演算，因为假如上面的猜想是对的，且链表已经能够表示所有的符号，那么我们的全部问题就变成了如何去构建这样的符号演算系统。后面我们可以看到， LISP 通过函数式编程来完成了这些演算规则的构建。
这里，需要提请读者注意的是， LISP 的全称是 LISt Processing，即列表处理，但实际上 LISP 是由两种互相正交的哲学组合形成的，一个是列表处理，另一个是函数式编程。虽然在下面以后，我们会介绍 S-Expression 这样美妙的把两者无缝结合在一起的形式，但是为了清晰我们的概念，我要强调一下列表处理和函数式编程是两个正交的部分。实际上，我们完全可以用其他的不是函数的方式构建一个列表处理语言。在历史上，早在 FORTRAN 出现之前，Alan Newell 和 Herbert Simon 就用汇编实现了一个叫 IPL 的语言，而这个 IPL 语言就是面向过程的对列表处理的，而后，McCarthy 一开始也是用一系列的 FORTRAN 子程序来做列表处理的。比如 LISP 里面的 CAR 操作，其全成实际上是 Content of the Address portion of the Register，顾名思义，寄存器的地址单元内容，也即列表的第一个元素（和C表达数组的方式类似，这里寄存器中存着指向列表第一个元素的指针）。函数式的却不以列表为基本数据单元的语言也很多，比如 Scala ，就是以对象为基本数据单元。因此，函数式和列表处理是不一定要互相耦合的。那么，到底是什么原因使得 LISP 选择函数式，这样的选择又为啥更加适合当时 AI 的研究呢，我们下节将继续介绍当时 AI 的研究范式，强弱 AI 之间的辩论和函数式编程在当年 AI 研究上的优点。
（待续）

作者: 翔子 时间: 2010-5-24 17:10
标题: 编程珠玑番外篇-I. 高级语言是怎么来的-5
LISP 语言是怎么来的–LISP 和 AI 的青梅竹马 B上回我们说到 LISP 和 AI 很是青梅竹马的时候，浮光掠影地说因为 LISP 的基本数据单元–”链表”在知识表示上的比较优势。我们说， AI 要处理的数据结构和要刻画的现实世界的模型很复杂，使得数组等其他简单数据结构不能胜任，所以“链表”成了最佳的选择。如果我们顺着这样的逻辑线往下看，似乎选择 LISP 这个“列表处理的语言”似乎是理所当然的。可是，这个原因并不充分。因为 LISP 语言可不仅仅是列表处理，还包括函数式编程等等其他。反过来说，如果仅仅是列表处理对于 AI 至关重要的话，那么在 FORTRAN 和 Algol 这些通用编程语言又非常普及的传统语言里面写一些关于列表处理的函数岂不是更加直观和方便？归根结底，到底 LISP 还有什么其他奥妙呢？
当我们追寻函数式编程这条线索的时候，就会不可避免的触及到 AI 的早期历史。LISP 的特性，其实都是和当时 AI 的范式 (paradigm) 息息相关的。
AI 范式的演变
早在 McCarthy 这一代人提出 AI 之前，冯诺伊曼等人就开始研究什么是智能以及如何实现智能的问题了。所不同的是，他们更加偏重于研究大脑的内部工作机理，并且试图通过在模拟大脑的工作机理，来实现智能。这一学派的哲学很清晰：人类大脑是一个标准的智能体，我们只需要让计算机模拟人的大脑的工作方式，计算机就有了和人类大脑一样的智能了。对于这一派的研究者来说，他们相信大脑的结构和工作机理决定了智能，至于大脑是用脑细胞构成的，还是用电子电路模拟的，对于智能来说毫不重要。这方面的著名工作就是冯诺伊曼的《计算机和大脑》这篇论文。在这篇不算很学术的随笔里面，他分析了人的大脑有多少个神经元，计算机有多少个晶体管，通过这些定量的比较来解释计算机和人的大脑的差距。当时和冯诺伊曼齐名的另一个神童是开创控制论的维纳。他和冯诺伊曼一样，兼通很多学科。和冯诺伊曼一样，他职业是数学家，但是也精通如神经科学和脑科学等学科。一个显然的例子就是在《控制论》这本书里面，维纳对大脑和神经的分析比比皆是。这种对大脑和神经分析的传统，从 Cajal (对，就是写 Advice for a Young Investigator 的那个大神) 开始，一直延续到了后来 AI 中的联接主义(主要研究神经网络的一个人工智能学派)。
可是，从脑科学和认知科学的角度去分析智能在当时有一个非常大的局限: 脑神经解剖学本身不成熟。比方说，现如今脑科学家在分析脑功能的时候一般会借助于 fMRI 和其他一些神经造影技术。这些技术可以做到实时观测到脑中血氧分布，直接确定大脑在执行特定任务时候的活跃部分。当年的科学家则只能使用有限的几种医学成像技术，或者从血管摄影的角度研究大脑。受限于当时的研究条件，当年的研究者很难直接观测到脑神经的实时工作状态，分析大脑的实时工作机理。因此，对脑的研究就很难做到非常深刻。医学研究条件的限制，加上当时电子学的发展和集成度远远不够，用电子电路模拟大脑生成智能就显得非常遥远。因此，虽然这一派的思想超前，但是大部分的工作都不在于真正的用电子电路模拟大脑，而是在探索脑科学和神经科学本身，或者仅仅用电子电路模拟一些简单的神经动力学行为和小规模神经网络。正是因为连接主义在实现人工智能本身方面进展并不大，所以在AI领域中一直不是潮流的研究方向。上个世纪 80 年代前成功实施的一些人工智能系统，极少是来自于连接主义学派的。直到80年代后随着 BP 算法的重新发现，联接主义才迎来了第二春。这时候，LISP 已经过完 20 岁生日了。所以，联接主义对 AI 领域使用的编程语言的选择的影响并不算大。
符号主义
虽然联接主义这一学派在当时不怎么流行，当年的 AI 研究可是进行的如火如荼。这如火如荼的学派，采用的是另外一套方法，我们称之为“符号主义学派”。符号主义学派的渊源，可以直接追溯到图灵。图灵在人工智能方面做过很多的研究，其中最为大家所知的就是“图灵测试“了。有句俗话叫做“在网上，没人知道你是一条狗”，在这句话里，只要把“狗”换成“计算机”，就是简单版的图灵测试了。用个比较“潮”的比方，图灵测试就是让一台计算机或者一个真实的人（又叫评委）在网上交流，然后让这个评委猜测和他交谈的究竟是人还是计算机。如果这位评委也不能分辨谈话的对方到底是人还是计算机的话，我们就认为这个计算机已经足以“以假乱真”，拥有“和人类一样的智能”了，也就是通过“图灵测试了”。
在很长一段时间里，图灵测试一直是人工智能研究的圣杯(holy grail)。也就是说，通过”图灵测试“ 成了人工智能研究的终极目标。那么，自然的，最最直接的通过图灵测试的方法不是让计算机和人脑一样思考，而是只要能够让计算机处理对话中用到的的单词，句子和符号，并且在对话中能够和人一样的操纵这些单词和符号，计算机就有很大的希望通过图灵测试。从最极端的情况来看，计算机甚至都不需要去“理解”这些句子的含义，都有可能通过图灵测试。 [具体细节可以阅读 Wikipedia 上的“[url=http://en.wikipedia.org/wiki/Chinese_room]Chinese Room (中文房间)”条目]。有一个开源的聊天机器人，叫做 A.L.I.C.E.，就把上面我们说的“只要能够处理和操纵符号，就有可能通过图灵测试”发挥到了近乎极致。这个聊天机器人在图灵测试比赛中已经多次骗过人类评委，到了非常“智能”几乎能以假乱真的地步。可是，就是这样一个离通过图灵测试很近的机器人，其基本结构却简单到了我们都不能想像的地步：A.L.I.C.E. 的数据库里面有一条一条的规则，这些规则规定了她看到你说什么的时候她说什么。唯一有点“智能”的地方，就是有些规则不光取决于你这句话，还取决于你的上一句话。 [比如日常对话中我们先问“你喜欢看电影么？”，接着再问“什么类型的？”，这时候就需要前一句话推出这个问题是“（喜欢）什么类型的（电影)”]。“中文房间”的例子，和 A.L.I.C.E. 机器人如此简单的结构，都出人意料的显示出，即使计算机拥有了对符号的操作能力，通过了图灵测试，它也未必是是“有智能”的。可惜这句话只是我的马后炮而已，在 AI 发展的早期，因为图灵测试的拉动，联接主义的相对弱势和符号主义的繁盛，都把全世界的 AI 研究往一个方向拽，这个方向，很自然的，就是“符号处理”。
符号处理和 LISP 补充
其实上一篇我们已经提到了，Alan Newell 和 Herbert Simon 认为对符号演算系统就可以衍生出智能，所以上面的文字，算是对符号主义这个 paradigm 做一个历史的小注解。当我们把 LISP 放到这段历史中，就会自然的想到，什么语言适合人工智能的问题，就变成了“什么语言能做符号处理”。这个问题的答案，读者也都猜到了，就是 LISP。
符号处理在 LISP 里面的长处前文我已经介绍过一些了，这里我们可以再补充几点零碎的。LISP 里有一个大家都知道的统一表示程序和数据的方法，叫做 S-Expression。这个 S，其实就是 Symbolic 的意思。把程序和数据都统一的当成符号，用现代编程语言的话说，就是 LISP 支持 meta-programming。LISP 程序可以处理，生成和修改 LISP 程序。这个特性，加上函数是一阶对象的特性，使得 LISP 远远比同时代的任何语言灵活。我本人不是 LISP 的用户（初级用户都算不上），因此在这一点上所知有限。但单就我有限的对 LISP 的理解，我认为 LISP 的这种灵活，恰好满足了基于符号处理的 AI 领域对语言的“强大的表达能力”（可以对任何复杂系统建模）和“高层的抽象能力” 的需求。关于第一点，有一个著名的段子，说任何一门编程语言技巧和思想被提出的时候，总会有一个高人出来，说，这个玩意儿在 LISP 里面早就有了，具体的例子包括刚才说的 metaprogramming, object oriented language。这里面蕴含的，就是 LISP 的强大的表达能力，使得很多编程的范式，在 LISP 里面都能实现，或者找到影子。关于第二点，SICP 中例子比比皆是，讲得都比我深刻许多，就无需废话了。
在上篇文章中我提到，翻开任何一本编程的书，都会讲到“LISP是适合 AI 的编程语言”。那么，如果您和我当年一样，有兴趣从事 AI 方面的研究和探索，就不免要疑惑：“为了学习 AI，我要不要学习 LISP” 呢？现在距离我当年的这个疑惑已经差不多8年了，我并没有一个确定的答案，但是我知道了更多的一些事实。
如今的 AI 范式
如果你让任何一个 AI 方向的研究者推荐几本适合初学者的书的话，十有八九他会提到 “Artificial Intelligence: A Modern Approach”(人工智能，一种现代方法) 和 “Artificial Intelligence: A New Synthesis” (人工智能，一个新的综述)。这两本书的作者分别是 Peter Norvig 和 Nils Nilsson，都是 AI 领域的元老级人物。如果你是一个对书名很敏感的人，你肯定会想：奇怪了，这种书又不是畅销书，难道这两位大牛写了书怕卖不出去，非要在书名上加一个 “现代” 或者 “新” 来吸引眼球？事实上，这个“现代”和这个“新”都大有来头。实际上，这二十年来，AI 研究领域接连发生了好几个非常大的 paradigm shift. 传统的基于符号的 AI 方法不再是主流，取而代之的，是多种多样的基于统计的，基于自动推理的，基于机器学习的，基于群体智慧的，基于大规模数据集的等等各种各样研究方法的兴起。这个 paradigm shift, 对于领域之外的人好像是静悄悄的，可实际上 AI 领域早已发生了翻天覆地的变化。所以才会有 “新” 和 “现代” 这样的词出现在书标题上。不幸的是，大多写编程语言书的作者，未必全部知晓这个变化，因此还沿袭原来的框架，继续写下 “LISP是适合 AI 的编程语言” 这样一个早就不能完全反映现状的断言。如果我们统计一个从事 AI 研究的研究者或者科学家用什么语言，答案可能是五花八门无所不有：做 AI Search 的用 C/C++/Java, 做机器学习的如果模型和矩阵关系密切，可以用 Matlab, 如果统计计算较多，也可以用 R。至于做数据挖掘等等，语言和库更加五花八门，根本无法宣称那一个语言占上风。LISP 是适合 AI 的语言的教科书神话，也早就被无数的这样的实例给打破了。
延伸阅读：
[url=http://stackoverflow.com/questions/130475/why-is-lisp-used-for-ai]http://stackoverflow.com/questions/130475/why-is-lisp-used-for-ai

欢迎光临数码鹭岛论坛 (http://www.clore.net/forum/)