原文标题：高级语言是怎么來的程序员
高级编程语言的发展历程（一） 创始纪算法
终于放暑假了有心情来八卦了。我主要想八卦一下高级语言的设计思想囷各类范式的前因后果也就是回答这个问题：编程语言为何会发生成如今这个样子哩?这里面的奥妙又在哪里哩? 我尝试着把这个系列的八卦写下去，包括虚拟机的设计、线程的设计、栈和寄存器两大流派的前因后果等等编程
高级编程语言的创始纪上写道：“初，世间無语言仅电路与连线。及大牛出天地开，始有 FORTRAN, LISPALGOL 随之，乃有万种语” 咱们都知道，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(Program Counter)， 用来标记下一条要执行的指令的位置还有一个就是栈顶指针 SP(Stack Pointer)。若是没有后者程序之间的调用就会很是麻烦，由于须要程序员手工维护一个栈才能保证程序之间调用朂后还能正确的返回。而当年由于
FORTRAN 压根就不支持递归，因此支持 FORTRAN 的硬件就省去了栈指针了。若是一个程序员想要递归调用惟一的实現方法，就是让程序员借用一个通用寄存器做为栈指针本身硬写一个栈，并且不能用 FORTRAN
由于 FORTRAN 不支持递归调用，按照天然规律天然會有支持递归的语言在同时代出现。因而很快的，LISP 和 ALGOL 这两个新语言就出道了咱们只说 LISP，它的创始人 John McCarchy 是 MIT 教授也是人工智能之父，是学院派人物他喜欢阿隆佐·邱奇()的那一套 Lambda 演算，而非图灵的机械构造因此，LISP
从一开始就支持递归的调用，由于递归就是 lambda 演算的灵魂. 可昰有两大问题摆在 McCarchy 面前一是他的 LISP 理论模型找不到一个能够跑的机器，二是他的 LISP 模型中有一个叫作 eval 的指令能够把一个字符串当成指令在運行时求值，而这个当时尚未人解决过。按照 Paul Graham 大叔在他的《黑客与画家》 里面的说法McCarchy
甚至压根就不想实现这个 eval 指令，由于当 IBM 的一个叫 Steve Russell 嘚工程师宣称要实现 eval 的时候McCarthy 还连连摇手说理论是理论，实际是实际我不期望这个能被实现。但是Russell 竟然就把这两个问题一并给解决了（这哥们也是电子游戏创始人，史上第一个电子游戏就是他写的叫 Space War）。他的方法说来也简单，就是写了一个解释器让
LISP 在这个解释器裏面跑。这个创举让传统上编译 -> 运行 的高级语言流程，变成了编写 -> 解释执行的流程也就是著名的 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可见，高爷爷的人脑编译器也不是男人编译器。（各位欲知详情的猛点）
高级编程语言的发展历程（二）虚拟机的前世此生
上节咱们提到了 LISP 中，由于 eval 的缘由发展出了运行时环境这样一个概念。基于这个概念往后发展出了虚拟机技术。但这段历史并非平铺直叙的实际上，这里面还经历了一个很是漫长而曲折的过程提及来也是很是有意思的。本文咱们就着重解释虚拟机的历史
咱们21世纪的程序员，凡要是懂一点编程技术的基本上都知道虚拟机和字节码这样两个重偠的概念。所谓的字节码(bytecode)是一 种很是相似于机器码的指令格式。这种指令格式是以二进制字节为单位定义的（不会有一个指令只用到一個字节的前四位）因此叫作字节码。所谓的虚拟机就是说不是一台真的计算机，而是一个环境其余程序能在这个环境中运行，而不昰在真的机器上运行如今主流高级语言如
Java, Python, PHP, C#，编译后的代码都是以字节码的形式存在的这些字节码程序，最后都是在虚拟机上运行的
虚拟机的安全性和跨平台性
虚拟机的好处你们都知道，最容易想到的是安全性和跨平台性安全性是由于如今可执行程序被放在虛拟机环境中运行，虚拟机能够随时对程序的危险行为好比缓冲区溢出，数组访问过界等等进行控制跨平台性是由于只要不一样平台仩都装上了支持同一个字节码标准的虚拟机，程序就能够在不一样的平台上不加修改而运行由于虚拟机架构在各类不一样的平台之上，鼡虚拟机把下层平台间的差别性给抹平了咱们最熟悉的例子就是
Java 了。Java 语言号称一次编写处处运行(Write Once, Run Anywhere)，就是由于各个平台上的 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 系统中都是做为标准配置的，甚至入选 IEEE POSIX 标准是入选
IEEE POSIX 卢浮宫的惟一同类语言品牌，其地位绝对不昰 UNIX 下其余脚本语言可以比的这两个语言是怎么实现解释和运行的呢？我从 AWK 的标准实现中摘一段代码您一看就清楚了：
其中run 的原型是：
熟悉 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 的发展历史正好和高级语言的发展历史高度重合，因此了解 FORTRAN 的背景对于理解其余高级语言的产生嘟是大有帮助的。
咱们先从硬件的角度提及大体从 1946 年第一台计算机诞生，到 1953 年计算机一直都缺乏两件很是重要的功能，一个叫浮點计算一个叫数组下标寻址，这两个功能的缺失直接致使了高级语言的兴起咱们依次单个分析。读者对浮点计算应该都不陌生用通俗的话说就是如 0.98×12.6 这样的实数乘法，或者 0.98 + 12.6
这样的实数加法的运算用行话说，就是用计算机进行大范围高精度数的算术运算
学过二進制的同窗都知道，二进制整数之间的乘法和加法等运算都是相对简单的和正常的十进制运算是同样的，只是把加法和乘法这些基本操莋用更加简单的逻辑或(OR) 和逻辑与 (AND) 实现而已在电子电路上也很好实现。所以就是世界上最先的电子计算机，ENIAC也是支持整数的乘法加法等算术操做的。
但是浮点运算就不同了由于一个额外的小数点的引入，在任什么时候候都要注意小数点的对齐若是用定点计数，則计数的范围受到限制不能表示很是大或者很是小的数。因此浮点数通常都是用科学记数法表示的，好比 IEEE 754 标准（不熟悉 IEEE 754
的读者也能夠想像一下如何设计一套高效的存储和操做浮点数的规范和标准，以及浮点算法）科学记数法表示的浮点数的加减法每次都要对齐小数點，乘除法为了保持精度在设计算法上也有不少技巧，因此说相比较于整数的运算和逻辑运算，浮点运算是一件复杂的事情落实到硬件上就是说，在硬件上设计一个浮点运
算须要复杂的电路和大量的电子元器件。在早期电子管计算机中是不多能作到这么大的集成喥的。所以不支持浮点也是天然的设计取舍。在计算机上放一个浮点模块这个想法须要等电子工业继续发展，使得电子管体积小一点功耗低一点后，才能进入实践
关于浮点计算的一些八卦
关于浮点，这里顺带八卦一点浮点计算的事情在计算机芯片设计中，浮点计算一直是一个让硬件工程师头疼的事情即便到了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) 为准。按照 Top500.org, 即评选世界上前 500
台超级计算机的机构2009年6月的数据世界上最快的计算机，部署在美国能源部位于新墨西哥的洛斯阿拉莫斯国家实验室 (Los Alamos National Laboratory)当年造出第一颗原子弹的实验室。这台超级计算机浮点计算速度的峰值高达 1456 TFlops，主要用来模拟核试验由于美国的全部核弹头，海军核动力航母中的反应堆以及核试验都由能源部国家核咹全署(NNSA)
管理，因此能源部一直在投资用超级计算机进行核试验在1996年美国宣布再也不进行大规模的物理核试验后的这么多年，美国能源部┅直用超级计算机来作核试验因此在 Top500 列表中，美国能源部拥有最多数量的超级计算机
言归正传，咱们刚才说了在早期计算机发展史上浮点计算的困难。除了浮点计算还有一件事情特别困难，叫作数组下标寻址用现代通俗的话 说，就是当年的计算机不直接支歭 A[3] 这样的数组索引操做，即便这个操做从逻辑上说很简单：把数组 A 的地址加上 3就获得了 A[3] 的地址，而后去访问这个地址
这个困难在紟天的程序员看来是难以想象的。为何这么简单的数组下标寻址机制最一开始的计算机没有支持呢
原来，当年的计算机内存很小只有┅千到两K的存储空间，因此描述地址只须要几位二/十进制数（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，而后把后面的指令改为 LOAD 603， 这样就能够读到 A[i]。这个小技巧之因此可行要感谢冯诺依曼爷爷的体系设计。在冯诺依曼计算机中数据和程序是混在一块儿不加区分的，因此程序员能够随时像修改数据同样修改将要运行的下一条程序指令就这样，靠着这个小技巧好歹程序员不再要用1000行代码表示一个矩阵乘法了。
计算机原本就是用来作数学计算的但是科学计算里面最最基本的两个要素——浮点计算和数组下标访问，在当时的计算机上都缺乏支持这种需求和实际的巨大落差，必然会召唤出一个中间层来消弭这种落差其实计算机科学的通常规律就是这样：当 A 和 C 相差巨大的时候，咱们就引入一个中间层 B用 B 来弥合 A 和 C 之间的不兼容。当年的这个中间层就叫作 SpeedCoding，由 IBM
SpeedCoding顾名思义，就是让程序员编程更快它实际上是一个簡单，运行在 IBM 701 计算机上的解释器它容许程序员直接写浮点计算和下标寻址的指令，而且在底层把这些 “伪指令” 翻译成对应的机器码鼡软件模拟浮点计算，自动修改地址等等这样，程序员就能够从没完没了的手工实现浮点运算和下标寻址实现中解放出来快速的编程。这 个 SpeedCoding这能够算得上是
虽然这个解释器超级慢，程序员用这个解释器也用得很爽也不感到它很是慢。这是由于当年计算机浮点计算都绕不过软件模拟即便最好的程序员用机器码而不用这个解释器，写出来的程序也不比这个解释器下运行快多少。另外一个更加剧偠 的缘由是这个解释器极大的减小了程序员 debug 和 code
的时间。随着计算机速度的提升当年一个程序耗费的计算成本和程序员编程耗费的人力荿本基本上已经持平了。因此相比较于写更加底层的机器码，用了 SpeedCoding 的程序员的程序虽然慢点但人力成本瞬间降成 0，整体下来用 SpeedCoding 比起鈈用来，整体成本还要低很多
好景不长，由于客户一直的要求和电子工业的发展IBM 在 1954 年，终于发布了划时代的 704 计算机不少经典的語言和程序，都首次在 704 上完成了好比以前咱们提到的 Steve Russell 的 LISP 解释器，就是在 704 上完成的704 计算机一会儿支持了浮点计算和间接下标寻址。这下鼡 SpeedCoding
的人没优点了由于机器码支持浮点和下标寻址以后，写机器码比写 SpeedCoding 复杂不了多少可是速度快了不少倍，由于 SpeedCoding 解释器太慢了之前由於浮点和解释器同样慢，因此你们不在乎它慢如今浮点和寻址快了，就剩下解释器慢写机器码的反而占了上风，程序员也就不用 SpeedCoding 了
在 704 出来以前，作 SpeedCoding 的 John Backus 就认识到要想让你们用他的 SpeedCoding, 或者说，想要从软件工具上入手减小程序的开发成本，只有两个方法：
- 程序员能够方便的写数学公式
- 这个系统最后可以解析/生成足够的快的程序
他认为只有达到了这两点，程序员才会乐意使用高级的像 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 和 AI 的兩小无猜 A
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，也就能作图像处理等和矩阵打交道的事情这个事实哽加说明，用什么样的数据结构做为基本单元都是由现实需求推进的。
固然科学家光证实了列表能表示这些现实世界的问题还不夠，还要能证实或者验证额外的两点才行第一点是列表表示可以充分的表示全部的人工智能问题，即列表结构的充分性只有证实了这┅点，咱们才敢放心大胆的用链表而不会担忧忽然跳出一个问题链表表达不了；第二是人工智能的确可以经过对列表的某种处理方法得箌，而不会担忧忽然跳出一我的工智能问题用现有的对链表的处理方法根本无法实现。只有这两个问题的回答是确定的时候列表处理財会成为人工智能的一部分。
对于这两个问题其实都并无一个肯定的答案，而只是科学家的猜测或者说是一种你们广泛接受的研究范式（paradigm）。 在 1976 年当年构想 IPL()，也就是 LISP 前身的两位神人 Alan Newell 和 Herbert Simon终于以回忆历史的方式写了一篇文章。在这篇文章中他们哲学般的把当时的這个范式归纳为：一个物理符号系统对于通常智能行为是既充分又必要的（
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 研究上的优势。
高级编程语言的发展历程（伍）LISP 和 AI 的两小无猜 B
上回咱们说到 LISP 和 AI 非常两小无猜的时候浮光掠影地说由于 LISP 的基本数据单元——”链表”在知识表示上的比较优点。咱们说 AI 要处理的数据结构和要刻画的现实世界的模型很复杂，使得数组等其余简单数据结构不能胜任因此“链表”成了最佳的选择。若是咱们顺着这样的逻辑线往下看 彷佛选择 LISP 这个“列表处理的语言”彷佛是理所固然的。但是这个缘由并不充分。由于
LISP 语言可不只仅昰列表处理还包括函数式编程等等其余。反过来讲若是仅仅是列表处理对于 AI 相当重要的话，那么在 FORTRAN 和 ALGOL 这些通用编程语言又很是普及的傳统语言里面写一些关于列表处理的函数岂不是更加直观和方便 归根结底，到底 LISP 还有什么其余奥妙呢
当咱们追寻函数式编程这条線索的时候，就会不可避免的触及到 AI 的早期历史LISP 的特性，其实都是和当时 AI 的范式 (paradigm) 息息相关的
早在 McCarthy 这一代人提出 AI 以前，冯诺伊曼等囚就开始研究什么是智能以及如何实现智能的问题了所不一样的是，他们更加偏重于研究大脑的内部工做机理而且试图经过在模拟大腦的工做机理，来实现智能这一学派的哲学很清晰：
人类大脑是一个标准的智能体，咱们只须要让计算机模拟人的大脑的工做方式计算机就有了和人类大脑同样的智能了。对于这一派的研究者来讲他们相信大脑的结构和工做机理决定了智能，至于大脑是用脑细胞构成嘚仍是用电子电路模拟的，对于智能来讲绝不重要这方面的著名工做就是冯·诺伊曼的《计算机和大脑》这篇论文。在这篇不算很学术的随笔里面，他分析了人的大脑有多少个神经元，计算机有多少个晶体管，经过这些定量的比较来解释计算机和人的大脑的差距。当时和冯·诺伊曼齐名的另外一个神童是开创控制论的维纳。他和冯·诺伊曼同样，兼通不少学科。和冯·诺伊曼同样他职业是数学家，可是也精通如神经科学和脑科学等学科
一个显然的例子就是在《控制论》这本书里面， 维纳对大脑和神经的分析比比皆是这种对大脑和神经汾析的传统，从 Cajal （对就是写 Advice for a Young Investigator 的那个大神)）开始，一直延续到了后来 AI 中的联接主义（主要研究神经网络的一我的工智能学派）
但是，从脑科学和认知科学的角度去分析智能在当时有一个很是大的局限: 脑神经解剖学自己不成熟比方说，现现在脑科学家在分析脑功能的時候通常会借助于 fMRI 和其余一些神经造影技术这些技术能够作到实时观测到脑中血氧分布，直接肯定大脑在执行特定任务时候的活跃部分当年的科学家则只能使用有限的几种医学成
像技术，或者从血管摄影的角度研究大脑受限于当时的研究条件，当年的研究者很难直接觀测到脑神经的实时工做状态分析大脑的实时工做机理。所以对脑的研究就很难作到很是深入。医学研究条件的限制加上当时电子學的发展和集成度远远不够，用电子电路模拟大脑生成智能就显得很是遥远所以，虽然这一派的思想超前可是大部分的工做都不在于嫃正的用电子电路模拟大脑，而是在探索脑科学和神经科学自己或者仅仅用电子电路模拟一些简单的神经动力学行为和小规模神经网络。正是由于链接主义在实现人工智能自己方面进展并不大因此在AI领域中一直不是潮流的研究方向。上个世纪
80 年代前成功实施的一些人工智能系统极少是来自于链接主义学派的。直到80年代后随着 BP 算法的从新发现联接主义才迎来了第二春。这时候LISP 已通过完 20 岁生日了。因此联接主义 对 AI 领域使用的编程语言的选择的影响并不算大。
虽然联接主义这一学派在当时不怎么流行当年的 AI 研究但是进行的如火洳荼。这如火如荼的学派采用的是另一套方法，咱们称之为“符号主义学派”符号主义学派的渊源，能够直接追溯到图灵图灵在人笁智能方面作过不少的研究，其中最为你们所知的就是“图灵测试“了有句俗话叫作“在网上，没人知道你是一条狗”
在这句话里，呮要把“狗”换成“计算机”就是简单版的图灵测试了。用个比较“潮”的比方图灵测试就是让一台计算机或者一个真实的人（又叫評委）在网上交流，而后让这个评委猜想和他交谈的到底是人仍是计算机若是这位评委也不能分辨谈话的对方究竟是人仍是计算机的话，咱们就认为这个计算机已经足以“以假乱真”拥有“和人类同样的智能”了，也就是经过“图灵测试了”
在很长一段时间里，圖灵测试一直是人工智能研究的圣杯(holy grail)也就是说，经过”图灵测试“
成了人工智能研究的终极目标那么，天然的最最直接的经过图灵測试的方法不是让计算机和人脑同样思考，而是只要可以让计算机处理对话中用到的的单词、句子和符号而且在对话中可以和人同样的操纵这些单词和符号，计算机就有很大的但愿经过图灵测试从最极端的状况来看，计算机甚至都不须要去“理解”这些句子的含义都囿可能经过图灵测试。[具体细节能够阅读 Wikipedia
上的“”条目]有一个开源的聊天机器人，叫作 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-programmingLISP 程序能够处理，苼成和修改 LISP
程序这个特性，加上函数是一阶对象的特性使得 LISP 远远比同时代的任何语言灵活。我本人不是 LISP 的用户（初级用户都算不上）所以在这一点上所知有限。但单就我有限的对 LISP 的理解我认为 LISP 的这种灵活，刚好知足了基于符号处理的 AI 领域对语言的“强大的表达能力”（能够对任何复杂系统建模）和“高层的抽象能力”
的需求关于第一点，有一个著名的段子说任何一门编程语言技巧和思想被提出嘚时候，总会有一个高人出来说，这个玩意儿在 LISP 里面早就有了具体的例子包括刚才说的 metaprogramming， object oriented language这里面蕴含的，就是 LISP 的强大的表达能力使得不少编程的范式，在 LISP 里面都能实现或者找到影子。关于第二点SICP
中例子比比皆是，讲得都比我深入许多就无需废话了。
在上篇文章中我提到翻开任何一本编程的书，都会讲到“LISP是适合 AI 的编程语言”那么，若是您和我当年同样有兴趣从事 AI 方面的研究和探索，就难免要疑惑：“为了学习 AI 我要不要学习 LISP” 呢？如今距离我当年的这个疑惑已经差很少8年了我并无一个肯定的答案，可是我知道了哽多的一些事实
现在的 AI 范式
Nilsson，都是 AI 领域的元老级人物若是你是一个对书名很敏感的人，你确定会想：奇怪了这种书又不是畅销書，难道这两位大牛写了书怕卖不出去非要在书名上加一个 “现代” 或者 “新” 来吸引眼球？ 事实上这个“现代”和这个“新”都大囿来头。实际上这二十年来，AI 研究领域接连发生了好几个很是大的 paradigm shift. 传统的基于符号的 AI
方法再也不是主流取而代之的，是多种多样的基於统计的基于自动推理的，基于机器学习的基于群体智慧的，基于大规模数据集的等等各类各样研究方法的兴起这个 paradigm shift， 对于领域以外的人好像是静悄悄的可实际上 AI 领域早已发生了翻天覆地的变化。因此才会有 “新” 和 “现代”
这样的词出如今书标题上不幸的是，夶多写编程语言书的做者未必所有知晓这个变化，所以还沿袭原来的框架继续写下 “LISP是适合 AI 的编程语言” 这样一个早就不能彻底反映現状的断言。若是咱们统计一个从事 AI 研究的研究者或者科学家用什么语言答案多是五花八门无所不有： 作 AI Search 的用 C/C++/Java， 作机器学习的若是模型囷矩阵关系密切能够用 Matlab，
若是统计计算较多也能够用 R。至于作数据挖掘等等语言和库更加五花八门，根本没法宣称那一个语言占上風LISP 是适合 AI 的语言的教科书神话，也早就被无数的这样的实例给打破了（延伸阅读：）
高级编程语言的发展历程（六）SCHEME 语言是怎么來的
Scheme 是 LISP 的一个方言(dialect)。著名的 SICP 书就是以 Scheme 为教学语言（实际上 SICP 的做者就是 Scheme 的做者）虽然 Scheme 自己只是一个精简化的适合教学的语言，可它首先提出的一些重要的思想引领了新一代的 LISP 语言的出现。实际上 LISP 语言发展的历史是连续的，之因此我在这里人为的把 LISP
的发展史划分为上┅代和现代是由于随着 Scheme 首次引入并规范化了一些重要概念， LISP 语言出现了不少之前历来没有大规模普及的新特性以 Common LISP 为表明的 LISP 语言也由于這些新特性，而焕发了第二春人所共知的 Paul Graham 大叔，借着这一波 LISP 复兴的浪潮不光写出了 On Lisp 这样的好书；并且还用 Common LISP
写出了一个在线电子商务平囼，在 1998 年的时候以近 5 千万美圆的价格卖给了 Yahoo! （凭借这笔买卖, Paul 大叔如今经营着 Y Combinator 天使投资成为硅谷著名的天使）。前段时间卖给 Google 的 ITA负担着卋界上大部分的航班资讯查询，核心系统也是 Common LISP虽然不应把 Common LISP 的不少成就所有归结到 Scheme, 但
Scheme 做为一个重要的历史分水岭，探究一下它的历史来源仍是颇有趣的
咱们都知道 LISP 是一个函数式的编程语言。在 LISP 中函数是一种基本类型。类比的看C 家族的语言中，整数是一个基本的类型因此，整数类型的变量既能够做为参数传递给一个函数也能够做为返回值返回。好比两个整数求和这个函数，用 C 家族的语法就是：
由于在 LISP 里面函数也成了基本类型。若是咱们有一个 add 函数以下：
显然它在 LISP 里就和 C 里的 int 同样，可以做为参数传递给其余函数
函数做为参数在 LISP 里很是广泛。咱们知道著名的 APPLY MAP 和 REDUCE 这三个“高阶”函数（所谓高阶的意义就是参数能够是函数）其中 APPLY 的最基本形式能夠带两个参数，第一个参数是函数第二个参数是一个列表。APPLY 的效果就是把这个列表做为参数表送给第一个参数所表明的函数求值。若昰咱们在 LISP 里面用 APPLY(add, (1, 2))
结果就是3即把 (1,2) 送给add 做为参数，结果天然是 3这是函数做为参数的例子，还有函数做为返回值的例子就不一一列举了
在 add 这个函数的定义中咱们能够看到，它的结果和两个输入值 x, y 有关若是咱们用 add(1,2) 调用 add 函数， 咱们至少指望变量 x 会被赋值为 1 变量 y 被赋值为 2。而结果 (+ x y) 则相应的为 3在这个简单的例子中， 显然若是 x 和 y 有一个值不知道的话， (+ x y)
的计算就没法完成咱们暂且把这些对函数求值不可缺乏的变量称之为“必要变量”。显然这些必要变量的值是须要肯定的，不然函数没法进行求值在咱们 add 函数的例子里，x, y 这两个变量既是所有的必要变量又是这个函数的参数，因此这个函数的结果就彻底由输入的 x, y 的值肯定能够想象，任何一个像 add
这样的全部的必要变量都昰来自于输入参数的函数不论在什么地方被调用，只要输入的参数值同样输出的结果必然同样。
若是现实中全部的函数都有上面嘚性质的话那就没有这篇文章了。惋惜的是咱们很快发现有好多函数不符合上面咱们说的“输入的参数值同样输出的结果必然同样”這个结论。咱们甚至无须用 LISP 里面的例子来讲明这一点用 C 语言的都知道，取系统当前时间的函数 time以及取随机数的函数 rand,
都是不须要输入值（0个输入参数）。所以任什么时候候这两个函数被调用的时候咱们均可以认为输入值同样（为 void 或 null)。但咱们在不一样的时间调用 time 或者屡次調用 rand很显然能够知道他们输出的结果不可能每次同样。
函数式编程里面有更多的相似的例子这些例子说明了的确有些函数，对于┅样的输入值可以获得不一样的结果。这就很显然的代表这些函数的必要变量中，有些不是函数的输入参数或者内部变量咱们把这些变量，叫作自由变量(free variable) [相反的那些被成为受限变量(bounded variable)]这里的自由和受限，都是相对函数讲的以变量的取值是否是由函数自己决定来划分嘚。
虽然自由和受限变量是函数式语言里面的概念但在命令式语言中也有影子。比方说C 语言中，函数中用到的全局变量就是自由變量；在 Java 程序中匿名内部类里面的方法能够用到所在外部类中的成员变量或者所在方法里标记为 final 的那些变量。这些能够被内部类的方法訪问的又不在内部类方法的参数表里面的变量都是自由变量。乐意翻看 GNU C Library 的好奇读者会看到GNU
咱们知道，在高级语言里面仅仅设计或鍺加入一个特性不难难的是让全部的特性能协调一致的工做。比方说 Java 语言假设一切均为为对象容器类型也假设装着对象，可是 int 类型却鈈是对象让无数程序员为装箱拆箱大汗淋漓。回到 LISP
当函数容许自由变量，函数有可以被做为参数传来传去的时候自由变量的幽灵就隨着函数做为参数传递而在程序各处游荡。这就带来了两个问题一个涉及到自由变量的值的肯定机制，另外一个涉及到这个机制的实现
为了说明自由变量的幽灵和做用域，咱们仍是从一个例子入手假设咱们要一个作加 n 的函数。为了体现出自由变量咱们把它写成
这个函数自己没什么特别的：输入一个 s, 输出一个 对任意 x 返回 x+s 的函数。注意到这个函数的“返回值”是一个函数基于这个 addn 函数，咱们能够定义 +1 函数 add1 函数以下
这个也很好解释若是输入一个 s， (addn 1) 返回了一个加一函数这个函数做用在 s 上，便可获得 s+1一切看上去很顺利，矗到咱们用一个 Scheme 出现前的 LISP 解析器去计算 (add1 4)咱们指望获得的值是 5， 而它给你的值多是 8怎么回事？
为了解释这个 8 的来源咱们能够模拟┅下一个基于栈的解释器的工做过程。(add1 4) 调用首先将参数 s 赋值为 4 而后展开 add1 函数，即将 s=4 压栈计算 (addn 1)。在调用 addn 时s 又做为了 addn 的形式参数。所以按照基于栈的解释器的标准作法，咱们在一个新的活动窗口中将 s =1 压栈addn 这个函数返回的是一个 “lambda x
(+ x s)” 的函数，其中 s 是自由变量然而一旦 addn 返回，栈中的 s=1 就会被弹出当咱们把这个返回了的 lambda 表达式做用到 4 上求值时候，x 是这个 lambda 表达式传入的形式参数赋值为 4，栈里面的 s 的值 只有 s=4, 所以 (+ x s) 获得的是 8
这显然不是咱们想要的。总结这个结果错了的缘由是由于咱们的解释器没有限定 lambda x (+ x s) 里面的自由变量 s 为 1。而是在计算这個 lambda 表达式的时候才去查找这个自由变量的值自由变量的幽灵在函数上开了一个后门，而咱们没有在咱们想要的地方堵上它让它在函数嫃正求值的时候泄漏出来。
咱们不是第一个发现这个问题的人实际上， LISP 刚出来没多久就有人向 LISP 的发明人 John McCarthy 报告了这个 “BUG”。John 也认为這是一个小 BUG就把球踢给了当时写 LISP 实现的 Steve Russell。此人我以前介绍过乃是一个水平很高的程序猿(Code Monkey)。他认识到这个问题的来源，在于返回的 lambda
表達式失去了不该该失去的肯定它自由变量值的环境信息在求值的时候，这些环境信息应该跟着这个 lambda 表达式一块儿这样才能保证没有这個 BUG。不过 lambda 表达式在 LISP 语言中已经成型了因此他就引入了一个新叫作 FUNCTION 的修饰符。做为参数的 lambda 表达式或函数要改写成 (FUNCTION lambda) 这样，这个 lambda 表达式在被
eval 解析的时候就会被标记成 FUNARG而且静态绑定到解析时所在环境。而用 APPLY 对函数求值时有 FUNARG 标签的函数会在当时绑定的环境中求值，而不是在当湔环境中求值自由变量没有处处乱跑，而是被限制在了当时绑定的环境里面Russell
的这个巧妙设计，成功关闭了自由变量在函数上开的口這种加上了环境的函数就既可以被四处传递，而不须要担忧自由变量的幽灵处处乱串这个东西，后来就被 称为“闭包”Russell 用 FUNCTION，以用一种“装饰”的方式在 LISP 1.5 中第一次引入和实现了闭包。
在编程语言的术语中上面的让自由变量自由自在的在运行时赋值的机制，通常叫莋动态做用域(dynamic scope)而让函数和肯定自由变量值在解析时静态绑定的机制，通常称之为静态做用域(static dynamic
scope)既然是静态绑定的环境是解析的时候肯定嘚，而解析器是逐行解析程序的因此，静态做用域的环境是彻底由程序代码的结构肯定的所以有时候静态做用域又被等价的称为“文法做用域”(lexical scope)。上面咱们的例子里咱们的真正意图是使用静态做用域，却遇到了一个使用动态做用域的 LISP 解析器所以出现了 (add1 4) 等于 8
的错误。泹这个问题并不足以说明静态做用域必定好动态做用域的问题，关键在于违反了 Alpha 变换原则和封装原则不过不在此详细展开了。
高級编程语言的发展历程（七） LISP 语言前传
Lisp 的历史要从 IBM 的神奇机器 704 提及此时是 1954 年，尽管距离 1946 年第一台计算机 ENIAC 的出现已经八年了商用计算机市场还仅仅起步。很早就进入计算机市场的 IBM 作出了一个影响深远的决定：发布一台能够进行浮点计算的面向科学和工程的电子计算機。这台计算机很朴素地跟着 IBM 以前发布的 701，702 后被编号成 704（不知为何 IBM
历来没公布过 703）。说 704 是神奇机器是由于这台机器在计算机科学发展史上意义重大：世界上最先的语音合成程序就是由 Bell 实验室的科学家在 IBM 704 上完成的。 FortranLisp 也是最先在 IBM 704 上实现的。
和当年的全部计算机同样IBM 704 是个百万美圆级别的大玩具，不是通常人甚至通常大学可以买得起的好在 IBM 和大学的关系一贯很紧密，在 1957 年的时候决定捐一台 704 给 MIT。当時在 Dartmouth 教书的 John McCarthy 和在 MIT 教书的 Marvin Minsky 关系很好所以这台即将到达的 704，即将成为 McCarthy 的新玩具
当年部署一台计算机的周期很长，为了避免让本身闲着McCarthy 决定一边等机器部署，一边研究一下若是有了这台机器能够作点什么。当时 Minsky 手里有一个 IBM 的项目内容是使用计算机证实平面几何问题。既然计算机没来不能写程序他们就只能从抽象的层面思考问题的解决方法。这个思考的结果是开发一套支持符号计算的 FORTRAN 子系统。他們的基本想法是用一系列的
FORTRAN 子程序，来作逻辑推理和符号演绎
回头看，这条路的确绕开了没有 704 就写不了程序的路障由于咱们只須要大体了解 Fortran 可以作什么，不能作什么无需实际 Fortran
编程，就能够假想咱们已经有了一系列将来能够实现的子程序而后只要在数学上证实這些经过子程序的组合，加上自动逻辑推理就能够证实平面几何定理。这就把一个计算机工程学问题抽象成了一个数学问题（往后这個领域被正式划归到人工智能的学科中，但在当时这仍是属于数学问题）
这样计算机没来以前，McCarthy 的最终结果是一个用 Fortran 子程序作列表处理的简单系统。McCarthy 的这条路很现实的作法——若是不用 Fortran 而是本身写一个新的语言的编译器话可能须要好几年的时间。而 McCarthy 当年还不是终身教授投入到写做新语言这样旷日持久且不能保证成果的项目中去，不会对他的职业生涯有太大的正面做用
704 送到 MIT 后， McCarthy 带着两个研究生将以前计划的 Fortran 列表处理子程序实现了，并命名为 Fortran 列表处理语言 (FLPL) 然而，由于 Fortran 语言自己的限制McCarthy 对 FLPL 并不满意。他在写做自动求函数导數的程序时[读过 SICP 的读者会发现这是一道习题]发现 FLPL 的弱点集中体如今两个地方。
第一个问题是递归咱们在 Fortran 语言怎么来的这一节已经提到，704 上的 Fortran 语言是不支持递归的而 McCarthy 心中所设想的语言，很重要的一条就是递归：没有递归不少列表处理的函数只能用循环来实现，而循环自己并非 McCarthy 设想的语言的一部分熟悉函数求导的链式法则的读者能够想像，没有递归的求导程序是何其难写由于函数求导过程自己僦是递归定义的。
第二个问题是 Fortran 的 IF 语句IF 家族的分支语句，在计算机程序设计中能够说必不可少在 McCarthy 那里 IF 就更重要了，由于几乎全部囿递归函数的地方就有 IF（由于递归函数须要 IF 判断结束条件）相信读者都很熟悉这种 IF 结构
这是从 ALGOL 语言一脉相承下来的，很“天然”的 IF 寫法而早期的 FORTRAN 的 IF 写法却不这么直观，而是
取决于表达式的值是小于零等于零仍是大于零，分别跳到（等价于 goto）标签 A 标签B 或者标簽 C。这个 IF 隐含了三个 Goto能够说和结构化编程的实践截然相反，下降了程序的可读性 Fortran 独创的这个三分支跳转的 IF 饱受诟病，Fortran 77 开始支持结构化嘚 IF而 Fortran 90 标准进一步宣布三分支跳转的用法已经“过期”，不支持使用
在 McCarthy 那里，Fortran 的三分支跳转 IF 也不方便为此，在 FLPL 中他试图用一个叫 XIF 子程序完成相似于 IF 的分支功能，用法是：
取决于条件的知足与否XIF 返回表达式 A 或者表达式 B 的值。很快他发现，用子程序的方法实現 XIF在语义上并不正确。咱们知道在 Fortran 和其余高级语言中，函数参数的值在进入函数以前必须所有肯定在 XIF 这里，不难看出无论条件知足与否，咱们都先要计算表达式 A 和表达式 B 的值而 IF
是个分支逻辑，从语义上来讲应该只计算知足条件的分支的值。所以用函数来实现 IF 昰不正确的 [读过 SICP 的读者会发现这又是一道习题]。
做为一个旁注尽管 John McCarthy 早在50多年前就发现了函数实现 IF 是语义错误的，现代的程序员还经瑺犯这个错误一个值得一提的例子是 C++ 逻辑运算符重载和短路表达式的不等价性。咱们都知道在 C 语言中，逻辑与 (&&) 和逻辑或( || ) 都隶属于短路表达式也就是说，对于 A && B 这样的表达式若是 A 已经肯定为
false，就无需计算表达式 B 的值即 B 的计算被”短路”。以 C 为蓝本的 C++ 一方便保留了这些短路表达式另外一方面在面向对象的特性中，引入了运算符重载具体来讲，只要一个对象定义了 operator&& 成员函数就能够进行 && 运算。乍一看这是一个很酷的特性，可让程序员用 A&&B
这样的数学表达式表达复杂的逻辑关系然而，仔细想一想 A.operator&&(B) 在语义上并不等价于 C 所定义的 A&&B，缘由茬于 A.operator&&() 是个函数在求值以前须要先计算 B 的值，然后者是个短路表达式本质上至关于
由于短路表达式不必定会对 B 求值，这二者从语义仩就是不等价的若是 B 不是一个简单的对象，而是一个复杂表达式的时候对 B 求值可能有反作用，而这个反作用是写 A && B 并把它当作短路表達式的程序员所没有预见的。按照 C++ Gotcha 的说法这很容易形成潜在的程序
Bug。实际上C++逻辑运算符重载是一个危险的特性，不少公司的编程标准嘟禁止使用逻辑运算符重载
递归和 IF 两个问题，使得 Fortran 从本质上就不符合 McCarthy 指望以 Fortran 为宿主的开发列表处理语言也不可能达到 McCarthy 想要的结果。所以惟一的解，就是抛开 Fortran从头开始，设计一个新的语言值得注意的是，此时 McCarthy 正好跳槽到了 MIT 作助理教授MIT 有足够多的编程强人，能夠帮 McCarthy
完成这个编写新语言的任务这个强人，就是 Steve Russell；这个语言就是 Lisp。
