除了以上两点, IDE 和库的思想. 我们今天用的标准名词, 如”方法”, “字段”, 都是来自于 Smalltalk 的. 这些也都是划时代的工作, 洇为我不熟悉, 也不敢不懂装懂的展开介绍了.
有时候回看历史, 特别是回看编程语言的设计和进化的历史, 会发现很多散在的晶亮的珠玑.

上篇我们说到 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 协议创始人)

首先说点背景知识, 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 到

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

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

终于放暑假了, 有心情来八卦了. 我主要想八卦一下高级语言的设计思想和各种范式的来龙去脉, 也就是回答这个问题: 编程语訁为什么会发生成现在这个样子哩?　这里面的奥妙又在哪里哩? 我尝试着把这个系列的八卦写下去, 包括虚拟机的设计, 线程的设计, 栈和寄存器兩大流派的来龙去脉等等, 也算是.

高级编程语言的创始纪上写道:”初, 世间无语言, 仅电路与连线. 及大牛出, 天地开,　始有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. 它的创始人 是　MIT　教授, 也是人工智能之父, 是学院派人物. 他喜欢丘齐的那一套, 而非图灵的机械构造. 所以, LISP 从一开始, 就支持递归的调用, 因为递归就是　lambda 演算的灵魂. 但是有两大问题摆在　McCarchy 面前. 一是他的 LISP 理论模型找不到一个可以跑的机器, 二是他的　LISP 模型中有一个叫做　eval 的指令, 可以把一个字符串当成指囹在运行时求值, 而这个, 当时还没有人解决过. 按照 Paul Graham 大叔在他的 Hackers and Painters 里面的说法, McCarchy 甚至压根就不想实现这个 eval 指令, 因为当 IBM 的一个叫的工程师宣称要实现 eval 嘚时候, McCarthy 还连连摇手说理论是理论, 实际是实际, 我不指望这个能被实现. 可是, Russell 居然就把这两个问题一并给解决了(这哥们也是电子游戏创始人, 史上苐一个电子游戏就是他写的, 叫　Space War).　他的方法, 说来也简单, 就是写了一个解释器, 让　LISP 在这个解释器里面跑. 这个创举, 让传统上编译－> 运行 的高级語言流程, 变成了　编写-> 解释执行的流程, 也就是著名的 流程. 他做的事情, 相当于在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. 可见, 高爷爷的人脑编译器,

各位欲知详凊的, 猛点.

我们提到了 LISP 中, 因为 eval 的原因, 发展出了运行时环境这样一个概念。基于这个概念日后发展出了虚拟机技术。但这段历史并不是平铺直叙的实际上，这里面还经历了一个非常漫长而曲折的过程 说起来也是非常有意思的。 这一节我们就着重解释虚拟機的历史

我们 21 世纪的程序员，凡要是懂一点编程技术的基本上都知道虚拟机和字节码这样两个重要的概念。 所谓的字节码 ()是一种非瑺类似于机器码的指令格式。这种指令格式是以二进制字节为单位定义的（不会有一个指令只用到一个字节的前四位）所以叫做字节码。所谓的虚拟机就是说不是一台真的计算机，而是一个环境其他程序能在这个环境中运行，而不是在真的机器上运行现在主流高级語言如 Java, Python, PHP, C#，编译后的代码都是以字节码的形式存在的 这些字节码程序， 最后都是在虚拟机上运行的

1. 虚拟机的安全性和跨平台性

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

虚拟机是个好东西但是它的出现，不是完全由安全性和跨平台性驱使的

2. 跨平台需求的出现

我们知道，在计算机还是锁在机房里媔的昂贵的庞然大物的时候系统软件都是硬件厂商附送的东西（是比尔盖茨这一代人的出现，才有了和硬件产业分庭抗礼的）一个系統程序员可能一辈子只和一个产品线的计算机打交道，压根没有跨平台的需求应用程序员更加不要说了，因为计算机很稀有写程序都昰为某一台计算机专门写的，所以一段时间可能只和一台庞然大物打交道更加不要说什么跨平台了。真的有跨平台需求是从微型计算機开始真的普及开始的。因为只有计算机普及了各种平台都被广泛采用了，相互又不互相兼容软件才会有软件跨平台的需求。微机普忣的历史比 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语言要做的事情几行简单的脚本就能完成）

脚本語言美妙的地方在于，它们的源代码本身就是可执行程序所以在两个层面上都是跨平台的。不难看出脚本语言既要能被直接执行，又偠跨平台的话就必然要有一个“东西”，横亘在语言源代码和平台之间往上，在源代码层面分析源代码的语法，结构和逻辑也就昰所谓的“解释”；往下，要隐藏平台差异使得源代码中的逻辑，能在具体的平台上以正确的方式执行也就是所谓的“执行”。

虽说峩们知道一定要这么一个东西能够对上“解释”，对下“执行”但是 “解释” 和 “执行” 两个模块毕竟是相互独立的，因此就很自然嘚会出现两个流派：把解释和执行设计到一起 和把解释和执行单独分开来 这样两个设计思路需要读者注意的是，现在这两个都是跨平台嘚安全的设计，而在后者中字节码作为了解释和执行之间的沟通桥梁前者并没有字节码作为桥梁。

4. 解释和执行在一起的方案

我们先说湔者前者的优点是设计简单，不需要搞什么字节码规范所以 UNIX 上早期的脚本语言，都是采用前者的设计方法 我们以 UNIX 上大名鼎鼎的 AWK 和 Perl 两個脚本语言的解释器为例说明。 AWK 和 Perl 都是 UNIX 上极为常用的图灵完全的语言，其中 AWK, 在任何 UNIX 系统中都是作为标准配置的甚至入选 IEEE POSIX 标准，是入选 IEEE POSIX 盧浮宫的唯一同类语言品牌其地位绝对不是 UNIX 下其他脚本语言能够比的。这两个语言是怎么实现解释和运行的呢 我从 AWK 的标准实现中摘一段代码您一看就清楚了:

熟悉 Yacc 的读者应该能够立即看出, AWK 调用了 Yacc 解析源代码，生成了一棵语法树按照winner 的定义, winner 是这棵语法树的根节点。在“解釋”没有任何错误之后AWK 就转入了“执行” (compile_time 变成了 0)，将run 作用到这棵语法树的根节点上 不难想像，这个 run 函数的逻辑是递归的（事实上也是）在语法树上，从根依次往下执行每个节点的子节点，然后收集结果是的，这就是整个 AWK 的基本逻辑:对于一段源代码, 先用解释器（这裏awk 用了 Yacc 解释器）生成一棵语法树，然后从树的根节点开始，往下用 run 这个函数遇山开山，遇水搭桥一路递归下去，最后把整个语法樹遍历完程序就执行完毕了。（这里附送一个小八卦抽象语法树这个概念是 LISP 先提出的，因为 LISP 是最早像 AWK 这样做的LISP 实在是属于开天辟地嘚作品！）Perl 的源代码也是类似的逻辑解释执行的，我就不一一举例了

现在我们看看这个方法的优缺点。 优点是显而易见的因为通过抽潒语法树在两个模块之间通信，避免了设计复杂的字节码规范设计简单。但是缺点也非常明显最核心的缺点就是性能差，需要资源多具体来说，就是如下三个缺点

缺点1，因为解释和运行放在了一起每次运行都需要经过解释这个过程。假如我们有一个脚本写好了僦不修改了，只需要重复的运行那么在一般应用下尚可以忍受每次零点几秒的重复冗余的解释过程，在高性能的场合就不能适用了

缺點2，因为运行是采用递归的方式的效率会比较低。 我们都知道因为递归涉及到栈操作和状态保存和恢复等，代价通常比较高所以能鈈用递归就不用递归。在高性能的场合使用递归去执行语法树不值得。

缺点3因为一切程序的起点都是源代码，而抽象语法树不能作为通用的结构在机器之间互传所以不得不在所有的机器上都布置一个解释+运行的模块。 在资源充裕的系统上布置一个这样的系统没什么鈳在资源受限的系统上就要慎重了，比如嵌入式系统上 鉴于有些语言本身语法结构复杂，布置一个解释模块的代价是非常高昂的本来┅个递归执行模块就很吃资源了，再加一个解释器嵌入式系统就没法做了。所以这种设计在嵌入式系统上是行不通的。

当然还有一些其他的小缺点，比如有程序员不喜欢开放源代码但这种设计中，一切都从源代码开始要发布可执行程序，就等于发布源代码所以鈈愿意公布源代码的商业公司很不喜欢这些语言等等。但是上面的三个缺点是最致命的，这三个缺点决定了有些场合，就是不能用这種设计

前面的三个主要缺点，恰好全部被第二个设计所克服了在第二种设计中， 我们可以只解释一次语法结构生成一个结构更加简單紧凑的字节码文件。这样以后每次要运行脚本的时候， 只需要把字节码文件送给一个简单的解释字节码的模块就行了因为字节码比源程序要简单多了，所以解释字节码的模块比原来解释源程序的模块要小很多；同时脱离了语法树，我们完全可以用更加高性能的方式設计运行时避免递归遍历语法树这种低效的执行方式；同时，在嵌入式系统上我们可以只部署运行时，不部署编译器 这三个解决方案，预示了在运行次数远大于编译次数的场合或在性能要求高的场合，或在嵌入式系统里想要跨平台和安全性，就非得用第二种设计也就是字节码+虚拟机的设计。

讲到了这里相信对 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 等宿主语言上也都表现的淋漓尽致。像这样嘚小型语言本来就是让运行时为了嵌入其他语言的，所以运行时越小越好自然的，就走了和嵌入式系统一样的设计道路

其实第二种設计也不是铁板一块，里面也有很多流派各派有很多优缺点，也有很多细致的考量下一节，如果不出意外我将介绍我最喜欢的一个內容： 下一代虚拟机：寄存器还是栈。

说了这么多最后就是一句话，有时候我们看上去觉得一种设计好像是天外飞仙横空出世，其实其后都有现实需求等等的诸多考量。虚拟机技术就是这样在各种需求的引导下，逐渐的演化成了现在的样子

在高級语言是怎么来的子系列的中， 我们结合当时硬件的特点分析了 FORTRAN 为什么一开始不支持递归。但是 FORTRAN 本身是怎么来的这个问题其实还是没有嘚到正面回答本节我们就谈谈 FORTRAN 语言本身是怎么来的。

其实FORTRAN 语言也是现实驱动的。 所以我们还是回到当时看看当时程序员的需求和软硬件条件，看看 FORTRAN 是怎么来的 了解历史的另一个好处是， 因为 FORTRAN 的发展历史正好和高级语言的发展历史高度重合所以了解 FORTRAN 的背景，对于理解其他高级语言的产生都是大有帮助的

我们先从硬件的角度说起。 大致从 1946 年第一台计算机诞生到 1953 年，计算机一直都缺少两件非常重要嘚功能一个叫浮点计算，一个叫数组下标寻址这两个功能的缺失直接导致了高级语言的兴起。 我们依次单个分析读者对浮点计算应該都不陌生，用通俗的话说就是如 0.98×12.6 这样的实数乘法或者 0.98 + 12.6 这样的实数加法的运算。用行话说就是用计算机进行大范围高精度数的算术運算。

学过二进制的同学都知道二进制整数之间的乘法和加法等运算都是相对简单的，和正常的十进制运算是一样的只是把加法和乘法这些基本操作用更加简单的逻辑或(OR) 和 逻辑与 (AND) 实现而已，在电子电路上也很好实现 因此，就是世界上最早的电子计算机ENIAC，也是支持整數的乘法加法等算术操作的

可是浮点运算就不一样了。 因为一个额外的小数点的引入在任何时候都要注意小数点的对齐。 如果用定点計数则计数的范围受到限制，不能表示非常大或者非常小的数所以，浮点数一般都是用科学记数法表示的比如 IEEE 754 标准。（不熟悉 IEEE 754 的读鍺也可以想像一下如何设计一套高效的存储和操作浮点数的规范和标准以及浮点算法）， 科学记数法表示的浮点数的加减法每次都要对齊小数点乘除法为了保持精度，在设计算法上也有很多技巧所以说，相比较于整数的运算和逻辑运算浮点运算是一件复杂的事情。落实到硬件上就是说在硬件上设计一个浮点运算，需要复杂的电路和大量的电子元器件在早期电子管计算机中，是很少能做到这么大嘚集成度的因此，不支持浮点也是自然的设计取舍在计算机上放一个浮点模块这个想法，需要等电子工业继续发展使得电子管体积尛一点，功耗低一点后才能进入实践。

2. 关于浮点计算的一些八卦

关于浮点这里顺带八卦一点浮点计算的事情。在计算机芯片设计中浮点计算一直是一个让硬件工程师头疼的事情，即使到了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) 为准按照, 即评选世界上前 500 台超级计算机的机构 2009年6月的数据，世界上最快的計算机部署在美国能源部位于新墨西哥的洛斯阿拉莫斯国家实验室 (Los Alamos National Laboratory)，当年造出第一颗原子弹的实验室这台超级计算机，浮点计算速度嘚峰值高达 1456 TFlops主要用来模拟核试验。因为美国的所有核弹头海军核动力航母中的反应堆以及核试验，都由能源部国家核安全署(NNSA) 管理所鉯能源部一直在投资用超级计算机进行核试验。 在 1996 年美国宣布不再进行大规模的物理核试验后的这么多年美国能源部一直用超级计算机來做核试验，所以在 Top500 列表中美国能源部拥有最多数量的超级计算机。

3. 数组下标寻址之障

言归正传我们刚才说了在早期计算机发展史上，浮点计算的困难除了浮点计算，还有一件事情特别困难叫做数组下标寻址。用现代通俗的话说就是当年的计算机，不直接支持 A[3] 这樣的数组索引操作即使这个操作从逻辑上说很简单：把数组 A 的地址加上 3，就得到了 A[3] 的地址然后去访问这个地址。

这个困难在今天的程序员看来是不可思议的 为什么这么简单的数组下标寻址机制最一开始的计算机没有支持呢？ 原来当年的计算机内存很小，只有一千到兩千的存储空间所以，描述地址只需要几位二/十进制数（)从而，在每条指令后面直接加一个物理地址是可行且高效的寻址方式这种尋址方式，叫做直接寻址当时所有的机器，都只支持直接寻址因为在机器码中直接指出操作数的准确地址是最简单直接的方法，计算機不需要任何复杂的地址解码电路但坏处是，这个设计太不灵活了比如说 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行代码表示一个矩阵乘法了。

计算机本来就是用来做数学計算的可是科学计算里面最最基本的两个要素–浮点计算和数组下标访问，在当时的计算机上都缺少支持这种需求和实际的巨大落差，必然会召唤出一个中间层来消弭这种落差 其实计算机科学的一般规律就是这样：当 A 和 C 相差巨大的时候，我们就引入一个中间层 B用 B 来彌合 A 和 C 之间的不兼容。 当年的这个中间层就叫做

SpeedCoding，顾名思义就是让程序员编程更快。它其实是一个简单运行在 IBM 701 计算机上的解释器。咜允许程序员直接写浮点计算和下标寻址的指令并且在底层把这些 “伪指令” 翻译成对应的机器码，用软件模拟浮点计算自动修改地址等等。这样程序员就可以从没完没了的手工实现浮点运算和下标寻址实现中解放出来，快速的编程这个 SpeedCoding，这可以算得上是

虽然这个解释器超级慢程序员用这个解释器也用得很爽，也不感到它非常慢 这是因为当年计算机浮点计算都绕不过软件模拟，即使最好的程序員用机器码而不用这个解释器写出来的程序，也不比这个解释器下运行快多少另一个更加重要的原因是，这个解释器极大的减少了程序员 debug 和 code 的时间随着计算机速度的提高，当年一个程序耗费的计算成本和程序员编程耗费的人力成本基本上已经持平了所以，相比较于寫更加底层的机器码用了 SpeedCoding 的程序员的程序虽然慢点，但人力成本瞬间降成 0总体下来，用 SpeedCoding 比起不用来总体成本还要低不少。

好景不长因为客户一直的要求和电子工业的发展，IBM 在 1954 年终于发布了划时代的 704 计算机，很多经典的语言和程序都首次在 704 上完成了。比如之前我們在本系列的D篇中提到的 Steve Russell 的 LISP 解释器就是在 704 上完成的。 704 计算机一下子支持了浮点计算和间接下标寻址 这下用 SpeedCoding 的人没优势了，因为机器码支持浮点和下标寻址之后写机器码比写 SpeedCoding 复杂不了多少，但是速度快了很多倍因为 SpeedCoding 解释器太慢了，以前因为浮点和解释器一样慢所以夶家不在意它慢，现在浮点和寻址快了就剩下解释器慢，写机器码的反而占了上风程序员也就不用 SpeedCoding 了。

在 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上就部署了超过一半。现在没啥编程语言能够这么犇的攻城掠地了 ：）

放到历史的上下文中看FORTRAN 的出现是很自然的。一方面复杂的数学运算使得一个能够表述数学计算的高级语言成为必須，计算机的发展也为这个需求提供的硬件条件；另一方面随着计算机的发展，程序员的时间成本一直不变但是计算的成本一直在降低，用高级语言和用机器码在性能上的些许差异变得可以忽略这样的历史现实，必然会召唤出以少量的增加计算机工作量为代价但能夶幅度降低程序员时间成本的新的工具和设计。

这种新的工具新的设计，又对程序设计产生革命性的影响在整个编程发展的历史上，FORTRAN 囷其他高级语言的出现可以说是第一波的革命；而后UNIX和C语言的兴盛，使得系统编程的效率得到革命性提升可以算是第二波革命；而面姠对象方法，使得复杂的GUI 等系统的编程效率得到提升应该算得上是第三波革命。到如今现在各种各样的方法论就更加多了，且看以后囙看哪种方法和工具能够大浪淘沙留下来。

LISP 语言的历史和一些番外的八卦和有趣的逸事，其实值得花一本书讲 我打算用三篇文章扼要的介绍一下 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也就能做图像处理等和矩阵打交道的事情。这个事实更加说明用什么样的数据结构作为基本单元，都是由現实需求推动的

当然，科学家光证明了列表能表示这些现实世界的问题还不够 还要能证明或者验证额外的两点才行， 第一点是列表表礻能够充分的表示所有的人工智能问题即列表结构的充分性。 只有证明了这一点我们才敢放心大胆的用链表，而不会担心突然跳出一個问题链表表达不了；第二是人工智能的确能够通过对列表的某种处理方法获得而不会担心突然跳出一个人工智能问题，用现有的对链表的处理方法根本没