Lisp语言是怎么来的–LISP 和 AI 的青梅竹马

LISP 语言的历史和一些番外的八卦和有趣的逸事，其实值得花一本书讲。 我打算用三篇文章扼要的介绍一下 LISP 的早期历史。 讲 LISP， 躲不过要讲 AI (人工智能)的，所以干脆我就先八卦八卦他们的青梅竹马好了。

翻开任何一本介绍各种编程语言的书，都会毫无惊奇的发现，每每说到 LISP， 通常的话就是”LISP 是适合人工智能(AI)的语言”。我不知道读者读到这句话的时候是怎么理解的，但是我刚上大学的时候，自以为懂了一点 LISP 和一点人工智能的时候， 猛然看到这句话，打死我也不觉得”适合”。 即使后来我看了 SICP 很多遍， 也难以想象为什么它就 “适合” 了， 难道 LISP 真的能做 C不能做的事情么? 难道仅仅是因为 John McCarthy 这样的神人既是 AI 之父， 又是 LISP 之父， 所以 AI 和 LISP兄妹两个就一定是很般配? 计算机科学家又不是上帝，创造个亚当夏娃让他们没事很般配干啥? 既然本是同根生这样的说法是不能让人信服的，那么到底这句话的依据在哪里呢? 我也是后来看 AI 文献， 看当年的人工智能的研究情况，再结合当年人工智能研究的指导思想，当年的研究者可用的语言等历史背景，才完全理解“适合” 这两个自的。 所以，这篇既是八卦，也是我的心得笔记。我们一起穿越到 LISP 和 AI的童年时代。 虽然他们现在看上去没什么紧密联系， 他们小时候真的是青梅竹马的亲密玩伴呢!

让机器拥有智能， 是人长久的梦想， 因为这样机器就可以聪明的替代人类完成一些任务。二战中高速电子计算机的出现使得这个梦想更加近了一步。二战后，计算机也不被完全军用了，精英科学家也不要继续制造原子弹了，所以，一下子既有资源也有大脑来研究 “智能机器”这种神奇的东西了。 我们可以随便举出当年研究繁盛的例子： 维纳在 1948年发表了<控制论>, 副标题叫做 <动物和机器的控制和通信>, 其中讲了生物和机器的反馈，讲了脑的行为。创立信息论的大师香农在 1949 年提出了可以下棋的机器，也就是面向特定领域的智能机器。同时，1949年， 加拿大著名的神经科学家 DonaldHebb 发表了“行为的组织”，开创了神经网络的研究; 图灵在 1950年发表了著名的题为“计算的机器和智能”的文章，提出了著名的图灵测试。如此多的学科被创立，如此多的学科创始人在关心智能机器，可见当时的确是这方面研究的黄金时期。

二战结束十年后， 也就是 1956 年， 研究智能机器的这些研究者，都隐隐觉得自己研究的东西是一个新玩意，虽然和数学，生物，电子都有关系， 但和传统的数学，生物，电子或者脑科学都不一样，因此，另立一个新招牌成了一个必然的趋势。John McCarthy 同学就趁着 1956 年的这个暑假， 在 Dortmouth大学(当年也是美国计算机科学发展的圣地之一, 比如说， 它是 BASIC 语言发源地)， 和香农，Minsky等其他人(这帮人当年还都是年轻人)，一起开了个会， 提出了一个很酷的词， 叫做 Artificial Intelligence，算是人工智能这个学科正式成立。 因为 AI 是研究智能的机器， 学科一成立， 就必然有两个重要的问题要回答，一是你怎么表示这个世界，二是计算机怎么能基于这个世界的知识得出智能。 第一点用行话说就是”知识表示”的模型,第二点用行话说就是“智能的计算模型”。 别看这两个问题的不起眼， 就因为当时的研究者对两个看上去很细微的问题的回答， 直接造就了 LISP 和AI 的一段情缘。

我们各表一支。 先说怎么表示知识的问题。 AI 研究和普通的编程不一样的地方在于， AI 的输入数据通常非常多样化，而且没有固定格式。比如一道要求解的数学题，一段要翻译成中文的英文，一个待解的 sodoku 谜题，或者一个待识别的人脸图片。 所有的这些，都需要先通过一个叫做“知识表示”的学科，表达成计算机能够处理的数据格式。自然，计算机科学家想用一种统一的数据格式表示需要处理多种多样的现实对象，这样， 就自然的要求设计一个强大的，灵活的数据格式。 这个数据格式，就是链表。

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

所以，用链表而不是数组来作为人工智能的统一的数据结构，固然有天才的灵机一动，也有现实需求的影响。当然，值得一提的是，在 CommonLISP 这样一个更加面向实践而不是科学研究是 LISP 版本中，数组又作为链表的补充，成了基本的数据结构，而 CommonLISP，也就能做图像处理等和矩阵打交道的事情。这个事实更加说明，用什么样的数据结构作为基本单元，都是由现实需求推动的。

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

对于这两个问题，其实都并没有一个确定的答案，而只是科学家的猜想，或者说是一种大家普遍接受的研究范式(paradigm)。 在 1976年， 当年构想 IPL， 也就是 LISP 前身的两位神人 Alan Newell 和 Herbert Simon，终于以回忆历史的方式写了一篇文章。 在这篇文章中，他们哲学般的把当时的这个范式概括为： 一个物理符号系统对于一般智能行为是既充分又必要的( Aphysical symbol system has the necessary and sufficient means forgeneral intelligence action)。用大白话说就是，“智能必须依赖于某种符号演算系统，且基于符号演算系统也能够衍生出智能”。在实践中，如果你承认这个猜想，或者说这个范式，那你就承认了可以用符号演算来实现 AI。于是，这个猜想就让当时几乎所有的研究者，把宝押在了实现一个通用的符号演算系统上，因为假如我们制造出一个通用的基于符号演算的系统，我们就能用这个系统实现智能。

上面我们说过，链表的强大的表达能力对于这个符号演算系统来讲是绰绰有余的了，所以我们只要关心如何实现符号演算，因为假如上面的猜想是对的，且链表已经能够表示所有的符号， 那么我们的全部问题就变成了如何去构建这样的符号演算系统。后面我们可以看到， LISP 通过函数式编程来完成了这些演算规则的构建。

这里，需要提请读者注意的是， LISP 的全称是 LISt Processing， 即列表处理，但实际上 LISP 是由两种互相正交的哲学组合形成的， 一个是列表处理，另一个是函数式编程。 虽然在下面以后，我们会介绍 S-Expression这样美妙的把两者无缝结合在一起的形式，但是为了清晰我们的概念，我要强调一下列表处理和函数式编程是两个正交的部分。实际上，我们完全可以用其他的不是函数的方式构建一个列表处理语言。在历史上，早在 FORTRAN 出现之前，Alan Newell 和 Herbert Simon就用汇编实现了一个叫 IPL 的语言，而这个 IPL 语言就是面向过程的对列表处理的，而后，McCarthy 一开始也是用一系列的FORTRAN 子程序来做列表处理的。比如 LISP 里面的 CAR 操作，其全成实际上是 Content of the Addressportion of the Register，顾名思义，寄存器的地址单元内容，也即列表的第一个元素(和C表达数组的方式类似，这里寄存器中存着指向列表第一个元素的指针)。函数式的却不以列表为基本数据单元的语言也很多，比如 Scala ，就是以对象为基本数据单元。 因此，函数式和列表处理是不一定要互相耦合的。那么，到底是什么原因使得 LISP 选择函数式，这样的选择又为啥更加适合当时 AI 的研究呢， 我们下节将继续介绍当时 AI 的研究范式，强弱AI 之间的辩论和函数式编程在当年 AI 研究上的优点。

上回我们说到 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 上的“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: AModern Approach”(人工智能，一种现代方法) 和 “Artificial Intelligence: A NewSynthesis” (人工智能，一个新的综述)。 这两本书的作者分别是 Peter Norvig 和 Nils Nilsson，都是 AI领域的元老级人物。 如果你是一个对书名很敏感的人，你肯定会想：奇怪了，这种书又不是畅销书，难道这两位大牛写了书怕卖不出去，非要在书名上加一个“现代” 或者 “新” 来吸引眼球? 事实上，这个“现代”和这个“新”都大有来头。 实际上，这二十年来，AI 研究领域接连发生了好几个非常大的paradigm shift. 传统的基于符号的 AI方法不再是主流，取而代之的，是多种多样的基于统计的，基于自动推理的，基于机器学习的，基于群体智慧的，基于大规模数据集的等等各种各样研究方法的兴起。 这个 paradigm shift, 对于领域之外的人好像是静悄悄的，可实际上 AI 领域早已发生了翻天覆地的变化。所以才会有 “新” 和“现代” 这样的词出现在书标题上。 不幸的是，大多写编程语言书的作者，未必全部知晓这个变化，因此还沿袭原来的框架，继续写下 “LISP是适合AI 的编程语言” 这样一个早就不能完全反映现状的断言。 如果我们统计一个从事 AI研究的研究者或者科学家用什么语言，答案可能是五花八门无所不有： 做 AI Search 的用 C/C++/Java,做机器学习的如果模型和矩阵关系密切，可以用 Matlab, 如果统计计算较多，也可以用 R。至于做数据挖掘等等，语言和库更加五花八门，根本无法宣称那一个语言占上风。LISP 是适合 AI的语言的教科书神话，也早就被无数的这样的实例给打破了。