高级编程语言的发展历程

高级编程语言的发展历程高级编程语言的发展历程（一）2010-07-20高级编程语言的创始纪上写道：“初，世间无语言，仅电路与连线。及大牛出，天地开，始有FORTRAN，LISP。ALGOL随之，乃有万种语。”我们都知道，LISP是基于递归函数的，FORTRAN是做科学计算的。现在的C等等，都比较像FORTRAN而不像LISP。可是很少有人知道，最初，FORTRAN是不支持函数递归调用的，而LISP是一生下来就支持的，所有高级语言里面的递归调用，都是逐渐从LISP那里学来的。这段尘封的历史非常有趣，值得八卦一番。一般人学编程，除了写HelloWorld之外，人生写的第二个程序，不是阶乘就是菲波拉契数列，要不就是汉洛塔。而这几个程序，基本上都是因为函数的递归调用才显得简单漂亮。没有递归的日子里，人民非常想念您。可是，第一版的FORTRAN就居然居然不支持递归。细心的读者要问了，不支持递归的语言能图灵完全么？当然可以，图灵机就是没递归的典型的例子。但是没递归调用的程序会很难写，尤其像汉诺塔这种。那么，FORTRAN他怎么就悍然不支持递归呢，让我们回到1960年。话说当年，IBM是计算机行业的领军者。那时候的计算机，都是比柜子还大的大家伙，至于计算能力嘛，却比你的手机还弱。那时候计

算机所做的最多的事情，不是发邮件打游戏，而是作计算。作计算嘛，自然需要一种和数学语言比较接近的编程语言。于是，1960年，IBM就捣鼓出了FORTRAN，用行话说，就是公式翻译系统。这个公式翻译系统，就成了世界上第一个编程语言。这个编程语言能做数学计算，能作条件判断，能GOTO。用现在的眼光看，这个语言能构模拟图灵机上的一切操作，所以是图灵完全的。学过数值计算的同学都知道，科学计算无非就是一大堆数学计算按照步骤进行而已。所以，一些控制判断语句，数学公式加上一个数组，基本上就能完成所IBM觉得这个语言够用了，有的科学计算了。就发布了FORTRAN语言规范，并且在自家的大型机上实现了这个语言。在实现这个语言的时候，IBM的工程师要写一个FORTRAN编译器（请注意那时候的大型机没有操作系统）。那时候的编译器都是用机器语言或者很低级的汇编语言写成的，所以编译器要越简单越好。这些工程师觉得，弄一个让用户运行时动态开辟内存的机制太麻烦了，所以干脆，强迫用户在写程序的时候，就要定好数组的大小，变量的类型和数目。这个要求并不过分，因为在科学计算中，数组的维度，用到的变量等，在计算之前，就是可以知道大小的。用现在的话说，就是不能动态开辟内存空间，也就相当于没有malloc的C，或者没有new的C++。这样的好处是，一个程序要多少内存，编译的时候就知道的一清二楚了。这个主意看上去很聪明，不过IBM的工程师比你想得更加聪明，他们想，既然一个程序或者子程序要多少内存在编译的时候都知道了，我们干脆就静态的把每个子程序在内存中的

位置，子程序中参数，返回值和局部变量放的位置，大小都定好，不久更加整齐高效么。是的，我们都知道，在没有操作系统管理的情况下，程序的内存策略越简单越好，如果内存放的整整齐齐的，计算机的管理员就能够很好的管理机器的内存，这样也是一件非常好的事情。（再次强调，当年还没有操作系统呢，操作系统要等到1964年发布的IBM360才有，具体开发一个操作系统之难度可参考《人月神话》）。可是，聪明的读者一下子就看出来了，这样静态的搞内存分配，就递不成归不了了。为啥呢？试想，我有个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.它的。创始人JohnMcCarchy是MIT教授，也是人工智能之父，是学院派人物。他喜欢丘齐的那一套Lambda演算，而非图灵的机械构造。所以，LISP从一开始，就支持递归的调用，因为递归就是，lambda演算的灵魂.但是有两大问题摆在McCarchy面前。一是他的LISP理论模型找不到一个可

以跑的机器，二是他的LISP模型中有一个叫做eval的指令，可以把一个字符串当成指令在运行时求值，而这个，当时还没有人解决过。按照PaulGraham大叔在他的HackersandPainters里面的说法，McCarchy甚至压根就不想实现这个eval指令，因为当IBM的一McCarthy还个叫SteveRussell的工程师宣称要实现eval的时候，连连摇手说理论是理论，实际是实际，我不指望这个能被实现。可是，Russell居然就把这两个问题一并给解决了（这哥们也是电子游戏创始人，史上第一个电子游戏就是他写的，叫SpaceWar）。他的方法，说来也简单，就是写了一个解释器，让LISP在这个解释器里面跑。这个创举，让传统上编译－>运行的高级语言流程，变成了编写->解释执行的流程，也就是著名的REPL流程。他做的事情，相当于在IBM的机器上用机器码写了一个通用图灵机，用来解释所有的LISP指令。这个创举，就让LISP从理论走到了实践。因为有了运行时的概念，LISP想怎么递归，就可以怎么递归，只要运行时支持一个软件实现的栈就可以了。上面我也说了，也就是写解释器的人麻烦一点而已，写LISP程序的人完全就可以不管下层怎么管理栈的了。同时，有了解释器，也解放了原来动态分配空间的麻烦，因为现在所有的空间分配都可以由解释器管理了，所以，运行时环境允许你动态的分配空间。对空间分配的动态支持，随之就带来了一项新技术：垃圾收集器。这个技术出现在LISP里面不是偶然的，是解释器的自然要求和归宿。在FORTRAN上本来被绕过的问题，就在LISP里面用全新的方法被解决了。LISP的划时代意义和解释器

技术，使得伴随的很多技术，比如抽象语法树，动态数据结构，垃圾收集，字节码等等，都很早的出现在了LISP中，加上LISP本身规则很少，使用起来非常灵活，所以，每当有一项新技术出现，特别是和解释器和运行时相关的一项新技术出现，我们就会听到有人说，“这玩意儿LISP里早就有了”，这话，是有一定道理的。除了上面的软件模拟之外，MIT还有一派在作硬件模拟，这一派，以后发展成了灿烂一时的LISPmachine，为日后所有虚拟机理论铺开了一条新路。这一派在70，80年代迅速崛起，然后随着PC的兴起又迅速的陨落，让人唏嘘不已.最后附送一个八卦:1960年的时候，高级语言编程领域也发生了一件大事，即ALGOL60的提出。ALGOL是划时代的标准，我们今天用的C/Java全是ALGOL家族的。ALGOL注意到了FORTRAN的不支持递归的问题，于是从一开始，就订立标准支持递归。但是，处理递归需要很小心的安排每个函数每次调用的地址和所谓的活动窗口(ActiveFrame)，而并不是每个编译器都是牛人写的，所以在处理递归这样一个新事物上，难免会出点小问题和小BUG。这时候，搞笑的高爷爷(Knuth)出场了，他提出了一个测试，叫做“是男人就得负67”。(Themanorboytest).恕我功底不深，不能给各位读者把这个男人测试的关窍讲清楚，但是，我知道，这个测试，乃是看ALGOL60编译器有没有正确的实现递归和外部引用的。照高爷爷的说法，真的男人要能得到正确答案，不是男人的就得不到正确答案。当然，高爷爷当时自己也没有男人编译器，所以自己猜了一个-121，后来，真

的男人编译器出来了，正确答案是-67。可见，高爷爷的人脑编译器，也不是男人编译器。高级编程语言的发展历程（二）2010-07-21虚拟机的前世今生我们提到了LISP中，因为eval的原因，发展出了运行时环境这样一个概念。基于这个概念，日后发展出了虚拟机技术。但这段历史并不是平铺直叙的，实际上，这里面还经历了一个非常漫长而曲折的过程，说起来也是非常有意思的。本文我们就着重解释虚拟机的历史。我们21世纪的程序员，凡要是懂一点编程技术的，基本上都知道虚拟机和字节码这样两个重要的概念。所谓的字节码(bytecode)，是一种非常类似于机器码的指令格式。这种指令格式是以二进制字节为单位定义的（不会有一个指令只用到一个字节的前四位），所以叫做字节码。所谓的虚拟机，就是说不是一台真的计算机，而是一个环境，其他程序能在这个环境中运行，而不是在真的机器上运行。现在主流高级语言如Java，Python，PHP，C#，编译后的代码都是以字节码的形式存在的，这些字节码程序，最后都是在虚拟机上运行的。虚拟机的安全性和跨平台性

虚拟机的好处大家都知道，最容易想到的是安全性和跨平台性。安全性是因为现在可执行程序被放在虚拟机环境中运行，虚拟机可以随时对程序的危险行为，比如缓冲区溢出，数组访问过界等等进行控制。跨平台性是因为只要不同平台上都装上了支持同一个字节码标准的虚拟机，程序就可以在不同的平台上不加修改而运行，因为虚拟机架构在各种不同的平台之上，用虚拟机把下层平台间的差异性给抹平了。我们最熟悉的例子就是Java了。Java语言号称一次编写，到处运行(WriteOnce，RunAnywhere)，就是因为各个平台上的Java虚拟机都统一支持Java字节码，所以用户感觉不到虚拟机下层平台的差异。虚拟机是个好东西，但是它的出现，不是完全由安全性和跨平台性驱使的。跨平台需求的出现我们知道，在计算机还是锁在机房里面的昂贵的庞然大物的时候，系统软件都是硬件厂商附送的东西（是比尔盖茨这一代人的出现，才有了和硬件产业分庭抗礼的软件产业），一个系统程序员可能一辈子只和一个产品线的计算机打交道，压根没有跨平台的需求。应用程序员更加不要说了，因为计算机很稀有，写程序都是为某一台计算机专门写的，所以一段时间可能只和一台庞然大物打交道，更加不要说什么跨平台了。真的有跨平台需求，是从微型计算机开始真的普及开始的。因为只有计算机普及了，各种平台都被广泛采用了，相互又

不互相兼容软件，才会有软件跨平台的需求。微机普及的历史，比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语言要做的事情，几行简单的脚本就能完成）解释和执行脚本语言美妙的地方在于，它们的源代码本身就是可执行程序，所以在两个层面上都是跨平台的。不难看出，脚本语言既要能被直接执行，又要跨平台的话，就必然要有一个“东西”，横亘在语言源代码和平台之间，往上，在源代码层面，分析源代码的语法，结构和逻辑，也就是所谓的“解释”；往下，要隐藏平台差异，使得源代码中的逻辑，能在具体的平台上以正确的方式执行，也就是所谓的“执行”。虽说我们知道一定要这么一个东西，能够对上“解释”，对下“执行”，但是“解释”和“执行”两个模块毕竟是相互独立的，因此就很自然的会出现两个流派：把解释和执行设计到一起和把解释和执行单独分开来这样两个设计思路，需要读者注意的是，现在这两个都是跨平台的，安全的设计，而在后者中字节码作为了解释和执行之间的沟通桥梁，前者并没有字节码作为桥梁。解释和执行在一起的方案我们先说前者，前者的优点是设计简单，不需要搞什么字节码规范，所以UNIX上早期的脚本语言，都是采用前者的设计方法。我们以UNIX上大名鼎鼎的AWK和Perl两个脚本语言的解释器为例说明。AWK和Perl都是UNIX上极为常用的，图灵完全的语言，其

中AWK，在任何UNIX系统中都是作为标准配置的，甚至入选IEEEPOSIX标准，是入选IEEEPOSIX卢浮宫的唯一同类语言品牌，其地位绝对不是UNIX下其他脚本语言能够比的。这两个语言是怎么实现解释和运行的呢？我从AWK的标准实现中摘一段代码您一看就清楚了：viewsourceprint?01intmain(intargc,char*argv[])02{}......syminit();compile_time=1;yyparse();...if(errorflag==0){compile_time=0;run(winner);

14}其中，run的原型是viewsourceprint?run(Node*a)1*/而winner的定义是：viewsourceprint?1Node*winner;/*rootofparsetree*//*executionofparsetreestartshere熟悉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等宿主语言上也都表现的淋漓尽致。像这样的小型语言，本来就是让运行时为了嵌入其他语言的，所以运行时越小越好，自然的，就走了和嵌入式系统一样的设计道路。结语其实第二种设计也不是铁板一块，里面也有很多流派，各派有很多优缺点，也有很多细致的考量，下一节，如果不出意外，我将介绍我最喜欢的一个内容：下一代虚拟机：寄存器还是栈。说了这么多，最后就是一句话，有时候我们看上去觉得一种设计好像是天外飞仙，横空出世，其实其后都有现实，需求等等的诸多考量。虚拟机技术就是这样，在各种需求的引导下，逐渐的演化成了现在的样子。

高级编程语言的发展历程（三）2010-07-22FORTRAN语言是怎么来的在高级语言是怎么来的子系列的第一篇中，我们结合当时硬件的特点，分析了FORTRAN为什么一开始不支持递归。但是FORTRAN本身是怎么来的这个问题其实还是没有得到正面回答，本节我们就谈谈FORTRAN语言本身是怎么来的。其实，FORTRAN语言也是现实驱动的。所以我们还是回到当时，看看当时程序员的需求和软硬件条件，看看FORTRAN是怎么来的。了解历史的另一个好处是，因为FORTRAN的发展历史正好和高级语言的发展历史高度重合，所以了解FORTRAN的背景，对于理解其他高级语言的产生都是大有帮助的。困难的浮点计算我们先从硬件的角度说起。大致从1946年第一台计算机诞生，到1953年，计算机一直都缺少两件非常重要的功能，一个叫浮点计算，一个叫数组下标寻址，这两个功能的缺失直接导致了高级语言的兴起。我们依次单个分析。读者对浮点计算应该都不陌生，用通俗的话说就是如0.98×12.6这样的实数乘法，或者0.98+12.6这

样的实数加法的运算。用行话说，就是用计算机进行大范围高精度数的算术运算。学过二进制的同学都知道，二进制整数之间的乘法和加法等运算都是相对简单的，和正常的十进制运算是一样的，只是把加法和乘法这些基本操作用更加简单的逻辑或(OR)和逻辑与(AND)实现而已，在电子电路上也很好实现。因此，就是世界上最早的电子计算机，ENIAC，也是支持整数的乘法加法等算术操作的。可是浮点运算就不一样了。因为一个额外的小数点的引入，在任何时候都要注意小数点的对齐。如果用定点计数，则计数的范围受到限制，不能表示非常大或者非常小的数。所以，浮点数一般都是用科学记数法表示的，比如IEEE754标准。（不熟悉IEEE754的读者也可以想像一下如何设计一套高效的存储和操作浮点数的规范和标准，以及浮点算法），科学记数法表示的浮点数的加减法每次都要对齐小数点，乘除法为了保持精度，在设计算法上也有很多技巧，所以说，相比较于整数的运算和逻辑运算，浮点运算是一件复杂的事情。落实到硬件上就是说，在硬件上设计一个浮点运算，需要复杂的电路和大量的电子元器件。在早期电子管计算机中，是很少能做到这么大的集成度的。因此，不支持浮点也是自然的设计取舍。在计算机上放一个浮点模块这个想法，需要等电子工业继续发展，使得电子管体积小一点，功耗低一点后，才能进入实践。关于浮点计算的一些八卦

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

言归正传，我们刚才说了在早期计算机发展史上，浮点计算的困难。除了浮点计算，还有一件事情特别困难，叫做数组下标寻址。用现代通俗的话说，就是当年的计算机，不直接支持A[3]这样的数组索引操作，即使这个操作从逻辑上说很简单：把数组A的地址加上3，就得到了A[3]的地址，然后去访问这个地址。这个困难在今天的程序员看来是不可思议的。为什么这么简单的数组下标寻址机制最一开始的计算机没有支持呢？原来，当年的计算机内存很小，只有一千到两千的存储空间，所以，描述地址只需要几位二/十进制数（BCD)。从而，在每条指令后面直接加一个物理地址是可行且高效的寻址方式。这种寻址方式，叫做直接寻址，当时所有的机器，都只支持直接寻址，因为在机器码中直接指出操作数的准确地址是最简单直接的方法，计算机不需要任何复杂的地址解码电路。但坏处是，这个设计太不灵活了，比如说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，然后，把后面的指令改成LOAD603，这样，就可以读到A[i]。这个小技巧之所以可行，要感谢冯诺依曼爷爷的体系设计。在冯诺依曼计算机中，数据和程序是混在一起不加区分的，所以程序员可以随时像修改数据一样修改将要运行的下一条程序指令。就这样，靠着这个小技巧，好歹程序员再也不要用1000行代码表示一个矩阵乘法了。SpeedCoding的出现计算机本来就是用来做数学计算的，可是科学计算里面最最基本的两个要素–浮点计算和数组下标访问，在当时的计算机上都缺少支持。这种需求和实际的巨大落差，必然会召唤出一个中间层来消弭这种落差。其实计算机科学的一般规律就是这样：当A和C相差巨大的时候，我们就引入一个中间层B，用B来弥合A和C之间的

不兼容。当年的这个中间层，就叫做SpeedCoding，由IBM的工程师JohnBackus开发。SpeedCoding，顾名思义，就是让程序员编程更快。它其实是一个简单，运行在IBM701计算机上的解释器。它允许程序员直接写浮点计算和下标寻址的指令，并且在底层把这些“伪指令”翻译成对应的机器码，用软件模拟浮点计算，自动修改地址等等。这样，程序员就可以从没完没了的手工实现浮点运算和下标寻址实现中解放出来，快速的编程。这个SpeedCoding，这可以算得上是FORTRAN的种子了。虽然这个解释器超级慢，程序员用这个解释器也用得很爽，也不感到它非常慢。这是因为当年计算机浮点计算都绕不过软件模拟，即使最好的程序员用机器码而不用这个解释器，写出来的程序，也不比这个解释器下运行快多少。另一个更加重要的原因是，这个解释器极大的减少了程序员debug和code的时间。随着计算机速度的提高，当年一个程序耗费的计算成本和程序员编程耗费的人力成本基本上已经持平了，所以，相比较于写更加底层的机器码，用了SpeedCoding的程序员的程序虽然慢点，但人力成本瞬间降成0，总体下来，用SpeedCoding比起不用来，总体成本还要低不少。好景不长，因为客户一直的要求和电子工业的发展，IBM在1954年，终于发布了划时代的704计算机，很多经典的语言和程序，都首次在704上完成了。比如之前我们在本系列的D篇中提到的

SteveRussell的LISP解释器，就是在704上完成的。704计算机一下子支持了浮点计算和间接下标寻址。这下用SpeedCoding的人没优势了，因为机器码支持浮点和下标寻址之后，写机器码比写SpeedCoding复杂不了多少，但是速度快了很多倍，因为SpeedCoding解释器太慢了，以前因为浮点和解释器一样慢，所以大家不在意它慢，现在浮点和寻址快了，就剩下解释器慢，写机器码的反而占了上风，程序员也就不用SpeedCoding了。FORTRAN创世纪在704出来之前，做SpeedCoding的JohnBackus就认识到，要想让大家用他的SpeedCoding,或者说，想要从软件工具上入手，减少程序的开发成本，只有两个方法：程序员可以方便的写数学公式这个系统最后能够解析/生成足够的快的程序他认为，只有达到了这两点，程序员才会乐意使用高级的像SpeedCoding这样的工具，而不是随着硬件的发展在机器码和SpeedCoding这样的工具之间跳来跳去。他本人通过实现SpeedCoding，也认识到如果有一个比机器码高级的语言，生产效率会高很多倍。那么，现在唯一的问题就是实现它，当然，这就不是一个小项目了，就需要IBM来支持他的开发了。所以，在1953年，他把他的想法写成了一个文档，送给了IBM的经理。项目在

1954年，704发布的当年，终于启动。JohnBackus领导的设计一个能达到上面两点的编程系统的项目的成果，就是日后的FORTRAN。和现在大多数编程语言不一样，FORTRAN语言的设计的主要问题不是语法和功能，而是编译器怎么写才能高性能。JohnBackus日后回忆说，当时谁也没把精力放在语言细节上，语言设计很潦草的就完成了（所以其后正式发布后又经过了N多修订），他们所有的功夫都是花在怎么写一个高性能的编译器上。这个高性能的编译器很难写，到1957年才写好，总共花了IBM216个人月。等到FORTRAN一推出，不到一年的时间，在IBM总共售出的60台704上，就部署了超过一半。现在没啥编程语言能够这么牛的攻城掠地了：）结语放到历史的上下文中看，FORTRAN的出现是很自然的。一方面，复杂的数学运算使得一个能够表述数学计算的高级语言成为必须，计算机的发展也为这个需求提供的硬件条件；另一方面，随着计算机的发展，程序员的时间成本一直不变，但是计算的成本一直在降低，用高级语言和用机器码在性能上的些许差异变得可以忽略。这样的历史现实，必然会召唤出以少量的增加计算机工作量为代价，但能大幅度降低程序员时间成本的新的工具和设计。这种新的工具，新的设计，

又对程序设计产生革命性的影响。在整个编程发展的历史上，FORTRAN和其他高级语言的出现可以说是第一波的革命；而后，UNIX和C语言的兴盛，使得系统编程的效率得到革命性提升，可以算是第二波革命；而面向对象方法，使得复杂的GUI等系统的编程效率得到提升，应该算得上是第三波革命。到如今，现在各种各样的方法论就更加多了，且看以后回看，哪种方法和工具能够大浪淘沙留下来。高级编程语言的发展历程（四）2010-07-24LISP语言的历史和一些番外的八卦和有趣的逸事，其实值得花一本书讲。我打算用三篇文章扼要的介绍一下LISP的早期历史。讲LISP，躲不过要讲AI（人工智能）的，所以干脆我就先八卦八卦他们的青梅竹马好了。翻开任何一本介绍各种编程语言的书，都会毫无惊奇的发现，每每说到LISP，通常的话就是“LISP是适合人工智能（AI）的语言”。我不知道读者读到这句话的时候是怎么理解的，但是我刚上大学的时候，自以为懂了一点LISP和一点人工智能的时候，猛然看到这句话，打死我也不觉得“适合”。即使后来我看了SICP很多遍，也难以想象为什么它就“适合”了，难道LISP真的能做C不能做的事情么？难道仅仅是因为JohnMcCarthy这样的神人既是AI之

父，又是LISP之父，所以AI和LISP兄妹两个就一定是很般配？计算机科学家又不是上帝，创造个亚当夏娃让他们没事很般配干啥？既然本是同根生这样的说法是不能让人信服的，那么到底这句话的依据在哪里呢？我也是后来看AI文献，看当年的人工智能的研究情况，再结合当年人工智能研究的指导思想，当年的研究者可用的语言等历史背景，才完全理解“适合”这两个自的。所以，这篇既是八卦，也是我的心得笔记。我们一起穿越到LISP和AI的童年时代。虽然他们现在看上去没什么紧密联系，他们小时候真的是青梅竹马的亲密玩伴呢！让机器拥有智能，是人长久的梦想，因为这样机器就可以聪明的替代人类完成一些任务。二战中高速电子计算机的出现使得这个梦想更加近了一步。二战后，计算机也不被完全军用了，精英科学家也不要继续制造原子弹了，所以，一下子既有资源也有大脑来研究“智能机器”这种神奇的东西了。我们可以随便举出当年研究繁盛的例子：维纳在1948年发表了《控制论》，副标题叫做《动物和机器的控制和通信》，其中讲了生物和机器的反馈，讲了脑的行为。创立信息论的大师香农在1949年提出了可以下棋的机器，也就是面向特定领域的智能机器。同时，1949年，加拿大著名的神经科学家DonaldHebb发表了“行为的组织”，开创了神经网络的研究；图灵在1950年发表了著名的题为“计算的机器和智能”的文章，提出了著名的图灵测试。如此多的学科被创立，如此多的学科创始人在关心智能机器，可见当时的确是这方面研究的黄金时期。

二战结束十年后，也就是1956年，研究智能机器的这些研究者，都隐隐觉得自己研究的东西是一个新玩意，虽然和数学，生物，电子都有关系，但和传统的数学，生物，电子或者脑科学都不一样，因此，另立一个新招牌成了一个必然的趋势。JohnMcCarthy同学就趁着1956年的这个暑假，在Dortmouth大学（当年也是美国计算机科学发展的圣地之一，比如说，它是BASIC语言发源地），和香农，Minsky等其他人（这帮人当年还都是年轻人），一起开了个会，提出了一个很酷的词，叫做ArtificialIntelligence，算是人工智能这个学科正式成立。因为AI是研究智能的机器，学科一成立，就必然有两个重要的问题要回答，一是你怎么表示这个世界，二是计算机怎么能基于这个世界的知识得出智能。第一点用行话说就是“知识表示”的模型，第二点用行话说就是“智能的计算模型”。别看这两个问题的不起眼，就因为当时的研究者对两个看上去很细微的问题的回答，直接造就了LISP和AI的一段情缘。我们各表一支。先说怎么表示知识的问题。AI研究和普通的编程不一样的地方在于，AI的输入数据通常非常多样化，而且没有固定格式。比如一道要求解的数学题，一段要翻译成中文的英文，一个待解的sodoku谜题，或者一个待识别的人脸图片。所有的这些，都需要先通过一个叫做“知识表示”的学科，表达成计算机能够处理的数据格式。自然，计算机科学家想用一种统一的数据格式表示需要处理多种多样的现实对象，这样，就自然的要求设计一个强大的，灵活的数据格式。这个数据格式，就是链表。

这里我就不自量力的凭我有限的学识，追寻一下为啥链表正好成为理想的数据结构的逻辑线。我想，读过SICP的读者应该对链表的灵活性深有感触。为了分析链表的长处，我们不妨把他和同时代的其他数据结构来做一比较。如我在前面的一个系列所说，当时的数据结构很有限，所以我们不妨比较一下链表和同时代的另一个最广泛使用的数据结构-数组-的优劣。我们都知道，数组和链表都是线性数据结构，两者各有千秋，而FORTRAN基本上是围绕数组建立的，LISP则是围绕链表实现的。通过研究下棋，几何题等AI问题的表示，我们的读者不难发现，AI研究关心于符号和逻辑计算远大于数值计算，比如下棋，就很难抽象成一个基于纯数字的计算问题。这样，只能存数字的数组就显得不适合。当然我们可以把数组扩展一下，让这些数组元素也可以存符号。不过即使这样，数组也不能做到存储不同结构的数据。比方说棋类中，车马炮各有各自的规则，存储这些规则需要的结构和单元大小都不一样，所以我们需要一个存储异构数据单元的模块，而不是让每个单元格的结构一样。加上在AI中，一些数据需要随时增加和修改的。比如国际象棋里，兵第一步能走两步，到底部又能变成皇后等等，这就需要兵的规则能够随时修改，增加，删除和改变。其他问题也有类似的要求，所有的这些，都需要放开数组维度大小一样的约束，允许动态增加和减少某一维度的大小，或者动态高效的增加删除数组元素。而一旦放开了单元格要同构和能随时增加和删除这样两个约束，数组其实就不再是数组了，因为随机

访问的特性基本上就丢失了，数组就自然的变成了链表，要用链表的实现。所以，用链表而不是数组来作为人工智能的统一的数据结构，固然有天才的灵机一动，也有现实需求的影响。当然，值得一提的是，在CommonLISP这样一个更加面向实践而不是科学研究是LISP版本中，数组又作为链表的补充，成了基本的数据结构，而CommonLISP，也就能做图像处理等和矩阵打交道的事情。这个事实更加说明，用什么样的数据结构作为基本单元，都是由现实需求推动的。当然，科学家光证明了列表能表示这些现实世界的问题还不够，还要能证明或者验证额外的两点才行，第一点是列表表示能够充分的表示所有的人工智能问题，即列表结构的充分性。只有证明了这一点，我们才敢放心大胆的用链表，而不会担心突然跳出一个问题链表表达不了；第二是人工智能的确能够通过对列表的某种处理方法获得，而不会担心突然跳出一个人工智能问题，用现有的对链表的处理方法根本没法实现。只有这两个问题的回答是肯定的时候，列表处理才会成为人工智能的一部分。对于这两个问题，其实都并没有一个确定的答案，而只是科学家的猜想，或者说是一种大家普遍接受的研究范式（paradigm）。在1976年，当年构想IPL，也就是LISP前身的两位神人AlanNewell和HerbertSimon，终于以回忆历史的方式写了一篇文章。在这篇文章中，他们哲学般的把当时的这个范式概括为：一个物理符号系统对

于一般智能行为是既充分又必要的（Aphysicalsymbolsystemhasthenecessaryandsufficientmeansforgeneralintelligenceaction）。用大白话说就是，“智能必须依赖于某种符号演算系统，且基于符号演算系统也能够衍生出智能”。在实践中，如果你承认这个猜想，或者说这个范式，那你就承认了可以用符号演算来实现AI。于是，这个猜想就让当时几乎所有的研究者，把宝押在了实现一个通用的符号演算系统上，因为假如我们制造出一个通用的基于符号演算的系统，我们就能用这个系统实现智能。上面我们说过，链表的强大的表达能力对于这个符号演算系统来讲是绰绰有余的了，所以我们只要关心如何实现符号演算，因为假如上面的猜想是对的，且链表已经能够表示所有的符号，那么我们的全部问题就变成了如何去构建这样的符号演算系统。后面我们可以看到，LISP通过函数式编程来完成了这些演算规则的构建。这里，需要提请读者注意的是，LISP的全称是LIStProcessing，即列表处理，但实际上LISP是由两种互相正交的哲学组合形成的，一个是列表处理，另一个是函数式编程。虽然在下面以后，我们会介绍S-Expression这样美妙的把两者无缝结合在一起的形式，但是为了清晰我们的概念，我要强调一下列表处理和函数式编程是两个正交的部分。实际上，我们完全可以用其他的不是函数的方式构建一个列表处理语言。在历史上，早在FORTRAN出现之前，AlanNewell和HerbertSimon就用汇编实现了一个叫IPL的语言，而这个IPL语言就是面向过程的对列表处理的，而后，McCarthy

一开始也是用一系列的FORTRAN子程序来做列表处理的。比如LISP里面的CAR操作，其全成实际上是ContentoftheAddressportionoftheRegister，顾名思义，寄存器的地址单元内容，也即列表的第一个元素（和C表达数组的方式类似，这里寄存器中存着指向列表第一个元素的指针）。函数式的却不以列表为基本数据单元的语言也很多，比如Scala，就是以对象为基本数据单元。因此，函数式和列表处理是不一定要互相耦合的。那么，到底是什么原因使得LISP选择函数式，这样的选择又为啥更加适合当时AI的研究呢，我们下节将继续介绍当时AI的研究范式，强弱AI之间的辩论和函数式编程在当年AI研究上的优点。高级编程语言的发展历程（五）2010-07-25上回我们说到LISP和AI很是青梅竹马的时候，浮光掠影地说因为LISP的基本数据单元–”链表”在知识表示上的比较优势。我们说，AI要处理的数据结构和要刻画的现实世界的模型很复杂，使得数组等其他简单数据结构不能胜任，所以“链表”成了最佳的选择。如果我们顺着这样的逻辑线往下看，似乎选择LISP这个“列表处理的语言”似乎是理所当然的。可是，这个原因并不充分。因为LISP语言可不仅仅是列表处理，还包括函数式编程等等其他。反过来说，如果仅仅是列表处理对于AI至关重要的话，那么在FORTRAN和

Algol这些通用编程语言又非常普及的传统语言里面写一些关于列表处理的函数岂不是更加直观和方便？归根结底，到底LISP还有什么其他奥妙呢？当我们追寻函数式编程这条线索的时候，就会不可避免的触及到AI的早期历史。LISP的特性，其实都是和当时AI的范式(paradigm)息息相关的。AI范式的演变早在McCarthy这一代人提出AI之前，冯诺伊曼等人就开始研究什么是智能以及如何实现智能的问题了。所不同的是，他们更加偏重于研究大脑的内部工作机理，并且试图通过在模拟大脑的工作机理，来实现智能。这一学派的哲学很清晰：人类大脑是一个标准的智能体，我们只需要让计算机模拟人的大脑的工作方式，计算机就有了和人类大脑一样的智能了。对于这一派的研究者来说，他们相信大脑的结构和工作机理决定了智能，至于大脑是用脑细胞构成的，还是用电子电路模拟的，对于智能来说毫不重要。这方面的著名工作就是冯诺伊曼的《计算机和大脑》这篇论文。在这篇不算很学术的随笔里面，他分析了人的大脑有多少个神经元，计算机有多少个晶体管，通过这些定量的比较来解释计算机和人的大脑的差距。当时和冯诺伊曼齐名的另一个神童是开创控制论的维纳。他和冯诺伊曼一样，兼通很多学科。和冯诺伊曼一样，他职业是数学家，但是也精通如神经科学和脑科学等学科。一个显然的例子就是在《控制论》这本书里面，维

纳对大脑和神经的分析比比皆是。这种对大脑和神经分析的传统，从Cajal(对，就是写AdviceforaYoungInvestigator的那个大神)开始，一直延续到了后来AI中的联接主义(主要研究神经网络的一个人工智能学派)。可是，从脑科学和认知科学的角度去分析智能在当时有一个非常大的局限:脑神经解剖学本身不成熟。比方说，现如今脑科学家在分析脑功能的时候一般会借助于fMRI和其他一些神经造影技术。这些技术可以做到实时观测到脑中血氧分布，直接确定大脑在执行特定任务时候的活跃部分。当年的科学家则只能使用有限的几种医学成像技术，或者从血管摄影的角度研究大脑。受限于当时的研究条件，当年的研究者很难直接观测到脑神经的实时工作状态，分析大脑的实时工作机理。因此，对脑的研究就很难做到非常深刻。医学研究条件的限制，加上当时电子学的发展和集成度远远不够，用电子电路模拟大脑生成智能就显得非常遥远。因此，虽然这一派的思想超前，但是大部分的工作都不在于真正的用电子电路模拟大脑，而是在探索脑科学和神经科学本身，或者仅仅用电子电路模拟一些简单的神经动力学行为和小规模神经网络。正是因为连接主义在实现人工智能本身方面进展并不大，所以在AI领域中一直不是潮流的研究方向。上个世纪80年代前成功实施的一些人工智能系统，极少是来自于连接主义学派的。直到80年代后随着BP算法的重新发现，联接主义才迎来了第二春。这时候，LISP已经过完20岁生日了。所以，联接主义对AI领域使用的编程语言的选择的影响并不算大。

符号主义虽然联接主义这一学派在当时不怎么流行，当年的AI研究可是进行的如火如荼。这如火如荼的学派，采用的是另外一套方法，我们称之为“符号主义学派”。符号主义学派的渊源，可以直接追溯到图灵。图灵在人工智能方面做过很多的研究，其中最为大家所知的就是“图灵测试“了。有句俗话叫做“在网上，没人知道你是一条狗”，在这句话里，只要把“狗”换成“计算机”，就是简单版的图灵测试了。用个比较“潮”的比方，图灵测试就是让一台计算机或者一个真实的人（又叫评委）在网上交流，然后让这个评委猜测和他交谈的究竟是人还是计算机。如果这位评委也不能分辨谈话的对方到底是人还是计算机的话，我们就认为这个计算机已经足以“以假乱真”，拥有“和人类一样的智能”了，也就是通过“图灵测试了”。在很长一段时间里，图灵测试一直是人工智能研究的圣杯(holygrail)。也就是说，通过”图灵测试“成了人工智能研究的终极目标。那么，自然的，最最直接的通过图灵测试的方法不是让计算机和人脑一样思考，而是只要能够让计算机处理对话中用到的的单词，句子和符号，并且在对话中能够和人一样的操纵这些单词和符号，计算机就有很大的希望通过图灵测试。从最极端的情况来看，计算机甚至都不需要去“理解”这些句子的含义，都有可能通过图灵测试。[具体细节可以阅读Wikipedia上的“ChineseRoom(中文房间)”条目]。有一个开源的聊天机器人，叫做A.L.I.C.E.，就把上面我们说的“只

要能够处理和操纵符号，就有可能通过图灵测试”发挥到了近乎极致。这个聊天机器人在图灵测试比赛中已经多次骗过人类评委，到了非常“智能”几乎能以假乱真的地步。可是，就是这样一个离通过图灵测试很近的机器人，其基本结构却简单到了我们都不能想像的地步：A.L.I.C.E.的数据库里面有一条一条的规则，这些规则规定了她看到你说什么的时候她说什么。唯一有点“智能”的地方，就是有些规则不光取决于你这句话，还取决于你的上一句话。[比如日常对话中我们先问“你喜欢看电影么？”，接着再问“什么类型的？”，这时候就需要前一句话推出这个问题是“（喜欢）什么类型的（电影)”]。“中文房间”的例子，和A.L.I.C.E.机器人如此简单的结构，都出人意料的显示出，即使计算机拥有了对符号的操作能力，通过了图灵测试，它也未必是是“有智能”的。可惜这句话只是我的马后炮而已，在AI发展的早期，因为图灵测试的拉动，联接主义的相对弱势和符号主义的繁盛，都把全世界的AI研究往一个方向拽，这个方向，很自然的，就是“符号处理”。符号处理和LISP补充其实上一篇我们已经提到了，AlanNewell和HerbertSimon认为对符号演算系统就可以衍生出智能，所以上面的文字，算是对符号主义这个paradigm做一个历史的小注解。当我们把LISP放到这段历史中，就会自然的想到，什么语言适合人工智能的问题，就变

成了“什么语言能做符号处理”。这个问题的答案，读者也都猜到了，就是LISP。符号处理在LISP里面的长处前文我已经介绍过一些了，这里我们可以再补充几点零碎的。LISP里有一个大家都知道的统一表示程序和数据的方法，叫做S-Expression。这个S，其实就是Symbolic的意思。把程序和数据都统一的当成符号，用现代编程语言的话说，就是LISP支持meta-programming。LISP程序可以处理，生成和修改LISP程序。这个特性，加上函数是一阶对象的特性，使得LISP远远比同时代的任何语言灵活。我本人不是LISP的用户（初级用户都算不上），因此在这一点上所知有限。但单就我有限的对LISP的理解，我认为LISP的这种灵活，恰好满足了基于符号处理的AI领域对语言的“强大的表达能力”（可以对任何复杂系统建模）和“高层的抽象能力”的需求。关于第一点，有一个著名的段子，说任何一门编程语言技巧和思想被提出的时候，总会有一个高人出来，说，这个玩意儿在LISP里面早就有了，具体的例子包括刚才说的metaprogramming，objectorientedlanguage。这里面蕴含的，就是LISP的强大的表达能力，使得很多编程的范式，在LISP里面都能实现，或者找到影子。关于第二点，SICP中例子比比皆是，讲得都比我深刻许多，就无需废话了。在上篇文章中我提到，翻开任何一本编程的书，都会讲到“LISP是适合AI的编程语言”。那么，如果您和我当年一样，有兴趣从事AI方面的研究和探索，就不免要疑惑：“为了学习AI，我要不要学习

LISP”呢？现在距离我当年的这个疑惑已经差不多8年了，我并没有一个确定的答案，但是我知道了更多的一些事实。如今的AI范式如果你让任何一个AI方向的研究者推荐几本适合初学者的书的话，十有八九他会提到“ArtificialIntelligence:AModernApproach”(人工智能，一种现代方法)和“ArtificialIntelligence:ANewSynthesis”(人工智能，一个新的综述)。这两本书的作者分别是PeterNorvig和NilsNilsson，都是AI领域的元老级人物。如果你是一个对书名很敏感的人，你肯定会想：奇怪了，这种书又不是畅销书，难道这两位大牛写了书怕卖不出去，非要在书名上加一个“现代”或者“新”来吸引眼球？事实上，这个“现代”和这个“新”都大有来头。实际上，这二十年来，AI研究领域接连发生了好几个非常大的paradigmshift.传统的基于符号的AI方法不再是主流，取而代之的，是多种多样的基于统计的，基于自动推理的，基于机器学习的，基于群体智慧的，基于大规模数据集的等等各种各样研究方法的兴起。这个paradigmshift，对于领域之外的人好像是静悄悄的，可实际上AI领域早已发生了翻天覆地的变化。所以才会有“新”和“现代”这样的词出现在书标题上。不幸的是，大多写编程语言书的作者，未必全部知晓这个变化，因此还沿袭原来的框架，继续写下“LISP是适合AI的编程语言”这样一个早就不能完全反映

现状的断言。如果我们统计一个从事AI研究的研究者或者科学家用什么语言，答案可能是五花八门无所不有：做AISearch的用C/C++/Java，做机器学习的如果模型和矩阵关系密切，可以用Matlab，如果统计计算较多，也可以用R。至于做数据挖掘等等，语言和库更加五花八门，根本无法宣称那一个语言占上风。LISP是适合AI的语言的教科书神话，也早就被无数的这样的实例给打破了。高级编程语言的发展历程（六）2010-07-27导言Scheme是LISP的一个方言(dialect)。著名的SICP书就是以Scheme为教学语言（实际上SICP的作者就是Scheme的作者）。虽然Scheme本身只是一个精简化的适合教学的语言，可它首先提出的一些重要的思想，引领了新一代的LISP语言的出现。实际上，LISP语言发展的历史是连续的，之所以我在这里人为的把LISP的发展史划分为上一代和现代，是因为随着Scheme首次引入并规范化了一些重要概念，LISP语言出现了很多以前从来没有大规模普及的新特性。以CommonLISP为代表的LISP语言也因为这些新特性，而焕发了第二春。人所共知的PaulGraham大

叔，借着这一波LISP复兴的浪潮，不光写出了OnLisp这样的好书；而且还用CommonLISP写出了一个在线电子商务平台，在1998年的时候以近5千万美元的价格卖给了Yahoo!(凭借这笔买卖,Paul大叔现在经营着YCombinator天使投资，成为硅谷著名的天使)。前段时间卖给Google的ITA，负担着世界上大部分的航班资讯查询，核心系统也是CommonLISP。虽然不该把CommonLISP的很多成就全部归结到Scheme,但Scheme作为一个重要的历史分水岭，探究一下它的历史来源还是很有趣的。函数作为一级对象我们都知道LISP是一个函数式的编程语言。在LISP中，函数是一种基本类型。类比的看，C家族的语言中，整数是一个基本的类型，所以，整数类型的变量既可以作为参数传递给一个函数，也可以作为返回值返回。比如，两个整数求和这个函数，用C家族的语法就是：viewsourceprint?1intadd(inta,intb);因为在LISP里面，函数也成了基本类型。如果我们有一个add函数如下：viewsourceprint?1(define(addxy)(+xy))

显然，它在LISP里就和C里的int一样，能够作为参数传递给其他函数。函数作为参数在LISP里非常普遍。我们知道著名的APPLYMAP和REDUCE这三个“高阶”函数（所谓高阶的意义就是参数可以是函数）。其中APPLY的最基本形式可以带两个参数，第一个参数是函数，第二个参数是一个列表。APPLY的效果就是把这个列表作为参数表，送给第一个参数所代表的函数求值。如果我们在LISP里面用APPLY(add,(1,2))结果就是3，即把(1,2)送给add作为参数，结果自然是3。这是函数作为参数的例子，还有函数作为返回值的例子就不一一列举了。自由变量的幽灵在add这个函数的定义中我们可以看到，它的结果和两个输入值x,y有关。如果我们用add(1,2)调用add函数，我们至少期望变量x会被赋值为1，变量y被赋值为2。而结果(+xy)则相应的为3。在这个简单的例子中，显然，如果x和y有一个值不知道的话，(+xy)的计算就无法完成。我们暂且把这些对函数求值不可缺少的变量称之为“必要变量”。显然，这些必要变量的值是需要确定的，否则函数无法进行求值。在我们add函数的例子里，x,y这两个变量既是全部的必要变量，又是这个函数的参数，所以这个函数的结果就完全由输入的x,y的值确定。可以想象，任何一个像

add这样的所有的必要变量都是来自于输入参数的函数，不论在什么地方被调用，只要输入的参数值一样，输出的结果必然一样。如果现实中所有的函数都有上面的性质的话，那就没有这篇文章了。可惜的是我们很快发现有好多函数不符合上面我们说的“输入的参数值一样，输出的结果必然一样”这个结论。我们甚至无须用LISP里面的例子来说明这一点。用C语言的都知道，取系统当前时间的函数time，以及取随机数的函数rand,都是不需要输入值（0个输入参数）。因此任何时候这两个函数被调用的时候，我们都可以认为输入值一样（为void或null)。但我们在不同的时间调用time或者多次调用rand，很显然可以知道他们输出的结果不可能每次一样。函数式编程里面有更多的类似的例子。这些例子说明了的确有些函数，对于同样的输入值，能够得到不同的结果。这就很显然的表明，这些函数的必要变量中，有些不是函数的输入参数或者内部变量。我们把这些变量，叫做自由变量(freevariable)[相反的那些被成为受限变量(boundedvariable)]。这里的自由和受限，都是相对函数讲的，以变量的取值是不是由函数本身决定来划分的。虽然自由和受限变量是函数式语言里面的概念，但在命令式语言中也有影子。比方说，C语言中，函数中用到的全局变量就是自由变量；在Java程序中，匿名内部类里面的方法可以用到所在外部类中的成员变量或者所在方法里标记为final的那些变量。这些可以被内部

类的方法访问的，又不在内部类方法的参数表里面的变量都是自由变量。乐意翻看GNUCLibrary的好奇读者会看到，GNUlibc中的rand函数就用到了一个random_data的变量作为自由变量(glibc/stdlib/random.c)。time也是一样，通过一个系统调用来设置时间，而这在原理上等价于用到一个叫做”当前时间”的自由变量(glibc/stdlib/time/time.c)。我们知道，在高级语言里面仅仅设计或者加入一个特性不难，难的是让所有的特性能协调一致的工作。比方说Java语言假设一切均为为对象，容器类型也假设装着对象，但是int类型却不是对象，让无数程序员为装箱拆箱大汗淋漓。回到LISP，当函数允许自由变量，函数有能够被作为参数传来传去的时候，自由变量的幽灵就随着函数作为参数传递而在程序各处游荡。这就带来了两个问题，一个涉及到自由变量的值的确定机制，另一个涉及到这个机制的实现。两种作用域为了说明自由变量的幽灵和作用域，我们还是从一个例子入手。假设我们要一个做加n的函数。为了体现出自由变量，我们把它写成viewsourceprint?1(define(addns)(lambdax(+xs)))

这个函数本身没什么特别的：输入一个s,输出一个对任意x返回x+s的函数。注意到这个函数的“返回值”是一个函数。基于这个addn函数，我们可以定义+1函数add1函数如下，viewsourceprint?1(define(add1s)((addn1)s))这个也很好解释，如果输入一个s，(addn1)返回了一个加一函数，这个函数作用在s上，即可得到s+1。一切看上去很顺利，直到我们用一个Scheme出现前的LISP解析器去计算(add14)。我们期望得到的值是5，而它给你的值可能是8。怎么回事？为了解释这个8的来源，我们可以模拟一下一个基于栈的解释器的工作过程。(add14)调用首先将参数s赋值为4然后，展开add1函数，即将s=4压栈，计算(addn1)。在调用addn时。s又作为了addn的形式参数。因此，按照基于栈的解释器的标准做法，我们在一个新的活动窗口中将s=1压栈。addn这个函数返回的是一个“lambdax(+xs)”的函数，其中s是自由变量。然而一旦addn返回，栈中的s=1就会被弹出。当我们把这个返回了的lambda表达式作用到4上求值时候，x是这个lambda表达式传入的形式参数，赋值为4，栈里面的s的值只有s=4,因此(+xs)得到的是8。这显然不是我们想要的。总结这个结果错了的原因，是因为我们的解释器没有限定lambdax(+xs)里面的自由变量s为1。而是

在计算这个lambda表达式的时候才去查找这个自由变量的值。自由变量的幽灵在函数上开了一个后门，而我们没有在我们想要的地方堵上它，让它在函数真正求值的时候泄漏出来。我们不是第一个发现这个问题的人。实际上，LISP刚出来没多久，就有人向LISP的发明人JohnMcCarthy报告了这个“BUG”。John也认为这是一个小BUG，就把球踢给了当时写LISP实现的SteveRussell。此人我之前的文章介绍过，乃是一个水平很高的程序猿(CodeMonkey)。他认识到，这个问题的来源，在于返回的lambda表达式失去了不应该失去的确定它自由变量值的环境信息，在求值的时候，这些环境信息应该跟着这个lambda表达式一起。这样才能保证没有这个BUG。不过lambda表达式在LISP语言中已经成型了，所以他就引入了一个新叫做FUNCTION的修饰符。作为参数的lambda表达式或函数要改写成(FUNCTIONlambda)。这样，这个lambda表达式在被eval解析的时候就会被标记成FUNARG，并且静态绑定到解析时所在环境。而用APPLY对函数求值时，有FUNARG标签的函数会在当时绑定的环境中求值，而不是在当前环境中求值。自由变量没有到处乱跑，而是被限制在了当时绑定的环境里面。Russell的这个巧妙设计，成功关闭了自由变量在函数上开的口。这种加上了环境的函数就既能够被四处传递，而不需要担心自由变量的幽灵到处乱串。这个东西，后来就被称为“闭包”。Russell用FUNCTION，以用一种“装饰”的方式，在LISP1.5中第一次引入和实现和闭包。

在编程语言的术语中，上面的让自由变量自由自在的在运行时赋值的机制，一般叫做动态作用域(dynamicscope)，而让函数和确定自由变量值在解析时静态绑定的机制，一般称之为静态作用域(staticdynamicscope)。既然是静态绑定的环境是解析的时候确定的，而解析器是逐行解析程序的，所以，静态作用域的环境是完全由程序代码的结构确定的。因此有时候静态作用域又被等价的称为“文法作用域”(lexicalscope)。上面我们的例子里。我们的真正意图是使用静态作用域，却遇到了一个使用动态作用域的LISP解析器，因此出现了(add14)等于8的错误。但这个问题并不足以说明静态作用域一定好。动态作用域的问题，关键在于违反了Alpha变换原则和封装原则，不过不在此详细展开了。