LISP 语言是怎么来的–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 ，终于以回忆历史的方式写了一篇文章。 在这篇文章中，他们哲学般的把当时的这个范式概括为： 一个物理符号系统对于一般智能行为是既充分又必要的（ 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 研究上的优点。

（待续）