LISP作为软件的麦克斯韦方程(2012)

在我读物理研究生院的第一天，我们班的电磁学教授一开始就走到黑板前，一言不发地写下了四个方程式：

他退后一步，转过身，说了类似[1]的话：“这些是麦克斯韦方程。只有四个紧凑的方程式。只需做一点工作，就很容易理解方程式的基本元素-所有符号的含义，我们如何计算所有相关的量，等等。但是，虽然理解方程式的元素很容易，但理解它们的所有后果就是另一回事了。这些方程式里面都是电磁学--从天线到马达再到电路，应有尽有。如果你认为你明白了这四个方程式的后果，那你现在就可以离开房间了，学期末你就可以回来考A了。“。

艾伦·凯(Alan Kay)曾将Lisp描述为“软件的麦克斯韦方程式”，这是出了名的。他描述了当他还是一名研究生时所经历的启示，当时他正在学习LISP1.5程序员手册，并意识到“第13页…底部的半页代码。就是里斯普本身。这就是“麦克斯韦软件方程式！”这就是编程的整个世界，我可以用几行文字来完成。“。

在这篇文章中，我们要做的是理解这半页代码的含义，以及Lisp是软件的麦克斯韦方程式的含义。但是，我们不会逐字完成上面的半页代码。相反，我们将做一些信息量大得多的事情：我们将创建一个现代的、完全可执行的等价物，相当于上面的代码。此外，为了使这篇文章易于理解，我不会假设您了解Lisp。相反，我将教您Lisp的基本元素。

这听起来可能过于雄心勃勃，但好消息是学习Lisp的基本元素很容易。只要您精通计算机编程并熟悉数学，您就可以在短短几分钟内了解Lisp的工作原理。坦率地说，这比理解麦克斯韦方程式的元素容易得多！因此，我将从解释Lisp编程语言的子集开始，并让您编写一些Lisp代码。

但我不会仅仅向您展示如何编写一些Lisp。完成后，我们将为Lisp代码编写解释器。特别地，我们将基于Peter Norvig编写的漂亮的Lisp解释器创建解释器，该解释器只包含90行Python代码。我们的解释器会稍微复杂一些，主要是因为增加了Norvig的解释器所没有的一些便利。只要您愿意阅读Python代码，代码仍然简单易懂。正如我们将看到的，编写解释器的好处不仅仅是它为我们提供了一个运行的解释器(尽管这不是一件小事)。编写解释器也加深了我们对Lisp的理解。它采用了我们对Lisp的描述中的一些相当抽象的概念，并以Python代码和数据结构的形式给出了具体的、有形的表示，从而做到了这一点。通过将以前抽象的东西具体化，我们的Lisp解释器的代码为我们提供了一种理解Lisp工作方式的新方法。

当我们的Python Lisp解释器启动并运行后，我们将编写一个与LISP 1.5程序员手册第13页底部的代码相当的现代代码。但是，虽然我们的代码本质上与第13页中的代码相同，但它还有一个相当大的优势，那就是它也是可执行的。如果我们愿意，我们可以玩弄代码，修改它，改进它。换句话说，它是麦克斯韦软件方程式的活版！此外，随着我们的新理解，理解LISP手册第13页上的所有细节成为一项简单而有趣的练习。

这篇文章的第二部分主要基于两个来源：当然是LISP 1.5手册的第一章，也是Paul Graham(后记)的一篇文章，他在文章中解释了Lisp背后的一些早期思想。顺便说一句，“LISP”是LISP手册中使用的大写，否则我将使用现代的大写约定，并写成“Lisp”。

伟大的挪威数学家尼尔斯·亨里克·阿贝尔曾被问及他是如何变得如此擅长数学的。他回答说，这是“通过研究大师，而不是他们的学生”。目前这篇文章的动机是亚伯的训诫。作为一名程序员，我是一个初学者(并且几乎是Lisp的新手)，因此这篇文章是我通过Alan Kay、Peter Norvig和Paul Graham等大师的想法进行详细工作的一种方式。当然，如果你相信亚伯的话，那么你应该停止阅读这篇文章，而应该去学习凯、诺维格、格雷厄姆等人的作品！我当然建议花时间研究他们的作品，在文章的最后，我提出了一些进一步阅读的建议。然而，我希望这篇文章有一个足够清晰的观点，以使其本身具有趣味性。最重要的是，我希望这篇文章能让思考Lisp(和编程)变得有趣，并提出一些有趣的基本问题。当然，作为一个初学者，这篇文章可能包含一些误解或错误(可能是重要的)，我欢迎更正、指点和讨论。

在本节和下两节中，我们将学习Lisp的基本元素-足以为Alan Kay在LISP手册第13页上看到的内容开发我们自己的可执行版本。我们将我们开发的Lisp方言称为“titily Lisp”，或者简称为tiddlylisp。Tiddlylisp基于编程语言方案(Programming Language Scheme)的一个子集，该方案是Lisp最流行的现代方言之一。

虽然我可以向您展示一系列的Lisp示例，但是如果您自己键入这些示例，然后对它们进行修改并尝试您自己的想法，您将学到更多。所以我希望您将tiddlylisp.py文件下载到本地计算机。或者，如果您使用的是git，您可以只克隆与本文相关的整个代码库。文件tiddlylisp.py是Lisp解释器，我们将在本文后面介绍其设计和代码。在Linux和Mac上，您可以通过在命令行输入python tiddlylisp.py来启动tiddlylisp解释器。您应该会看到一个提示：

这就是您要输入示例中的代码的地方-它是一个交互式的Lisp解释器。您可以随时按Ctrl-C退出解释器。请注意，解释器不是非常完整-正如我们将看到的，它只有153行！-而且它不完整的一个原因是错误消息没有提供太多信息。不要花太多时间担心错误，只要再试一次就行了。

如果您使用的是Windows，并且还没有安装Python，那么在通过运行python tiddlylisp.py启动解释器之前，您需要下载它(对于这段代码，我建议使用Python2.7)。请注意，我只在Ubuntu Linux上测试了解释器，没有在Windows或Mac上测试。

在您键入的表达式中，+是一个内置过程，表示加法操作。它被应用于两个参数，在本例中是数字2和3。解释器计算将+应用于2和3的结果，即将2和3相加，返回值5，然后打印出来。

第一个示例非常简单，但它包含了我们理解Lisp所需的许多概念：表达式、过程、参数、计算、返回值和打印。我们将在下面看到更多关于这些想法的插图。

下面是第二个示例，说明另一个内置过程，这次是乘法过程*：

基本情况是一样的：*是一个内置过程，这次表示乘法，这里应用于数字3和4。解释器计算表达式，并打印返回的值，即12。

前两个示例有一个潜在的混淆之处，那就是我调用了+和*“过程”，然而在许多编程语言中，过程不返回值，只有函数返回值。我之所以使用这个术语，是因为它是编程语言方案(Programming Language Scheme)中的标准术语，也就是tiddlylisp所基于的Lisp方言。事实上，在Lisp的一些现代方言中-例如Common Lisp-像+和*这样的操作会被称为“函数”。但是我们将继续讨论Scheme的用法，并且只讨论过程。

这里，内置过程<；表示比较运算符。因此tiddlylisp打印比较常量10和20的表达式的求值结果。结果为True，因为10小于20。相比之下，我们有。

许多Lisp初学者最初对这种编写基本数值运算的方式感到困惑。我们对像2+3这样的表达式非常熟悉，以至于(+23)中改变的顺序显得奇怪和陌生。然而，相对于前缀符号(+23)，我们对中缀符号2+3的偏爱更多的是一种历史偶然，而不是任何关于算术的基本知识的结果。不幸的是，这造成了一些人放弃Lisp的后果，仅仅是因为他们不喜欢以这种不熟悉的方式思考。

在这篇文章中，我们不会深入到Lisp中，无法详细了解为什么前缀表示法是个好主意。但是，我们会得到一个提示：我们的tiddlylisp解释器将会简单得多，因为所有过程都使用相同的(前缀)样式。如果您真的非常不喜欢前缀表示法，那么我建议您重写tiddlylisp，以便它对某些操作使用中缀表示法，对其他操作使用前缀表示法。你会发现翻译器变得相当复杂。因此，有一种感觉是，在任何地方使用相同的前缀样式都会使Lisp变得更简单。

为了计算该表达式的值，tiddlylisp计算嵌套表达式，返回209 FROM(*11 19)和207 FROM(*9 23)。那么，外部表达式的输出就是求值的结果(<；207)，这当然是假的。

定义用于定义新变量；我们还可以为先前定义的变量赋值：

您在这里可能会有一个关于稍微不寻常的语法的问题：set！你可能想知道这个感叹号是不是有什么特别的意思--也许是设置好了！是某种混合手术之类的。事实上，没有这样的复杂性：集合！只是一个关键字，就像定义一样，没有什么特别之处。只是tiddlylisp允许在关键字名称中使用感叹号。所以感叹号表示没有什么特别的事情发生。

一个更深层次的问题是，为什么我们不简单地去掉定义，让它如此设定！检查是否已定义变量，如果没有，则执行此操作。稍后我会解释一下为什么我们不这么做；现在，你只需要注意区别就行了。

我们可以使用Define以类似于定义变量的方式定义新过程。下面是一个示例，说明如何定义一个名为Square的过程。我将解开下面发生的事情，但首先，这里是代码，

现在先忽略上面的第一行。从第二行可以看到过程Square的作用：它接受单个数字作为输入，并返回该数字的平方。

上面的第一行代码怎么样？我们已经知道了很多关于这行是如何工作的：正在定义一个名为Square的过程，并为其赋予表达式(lambda(X)(*x x))的值，无论该值是什么。我们需要理解的新东西是表达式(lambda(X)(*x x))的值是什么。为了理解这一点，让我们将表达式分为三部分：lambda、(X)和(*x x)。我们将把这三件分开理解，然后再把它们放在一起。

表达式的第一部分-lambda-只是告诉tiddlylisp解释器该表达式定义了一个过程。我必须承认，当我第一次遇到lambda表示法时，我发现这个非常令人困惑[2]-我认为lambda一定是一个变量，或者是一个参数，或者类似的东西。但事实并非如此，它只是给tiddlylisp解释器一个很大的危险信号，告诉他们，嘿，这是一个过程定义。这就是全部的Lambda。

表达式的第二部分-the(X)-告诉tiddlylisp这是一个只有一个参数的过程，为了定义该过程，我们将对该参数使用临时名称x。如果过程定义改为以(lambda(x，y).)开始。这将意味着该过程有两个参数，为了定义该过程，临时标记为x和y。

表达式的第三部分-(*x x)-是过程定义的核心。它是我们在调用过程时评估和返回的内容，用过程参数的实际值代替x。

综合来看，表达式的值(lambda(X)(*x x))只是一个只有一个输入的过程，然后返回该输入的平方。此过程是匿名的，即它没有名称。但是我们可以通过使用定义来给它命名，所以行

告诉tiddlylisp定义名为Square的东西，其值是具有单个参数(因为(X))的过程(因为lambda)，并且该过程返回的是其参数的平方(因为(*x x))。

关于定义过程中使用的变量，重要的一点是它们是虚拟变量。假设我们想定义一个过程区域，它将返回三角形的面积，参数为三角形的底数和高度。我们可以使用以下过程定义来完成此操作：

tiddlylisp；(定义面积(lambda(B H)(*0.5(*b h)tiddlylisp；(区域3 5)7.5。

tiddlylisp&>(定义h 11)tiddlylisp>；(定义面积(lambda(B H)(*0.5(*b h)。

如果您了解到在过程定义内，即紧跟在lambda(B H)之后，h被视为一个伪变量，并且与过程定义之外的h完全不同，您可能不会感到惊讶。它有一个所谓的不同范围。因此，我们可以用以下内容继续上面的内容。

也就是说，在过程定义之外，该面积仅为先前设置的h值的0.5倍3倍。在这一点上，h的值是11，因此(区域3h)返回16.5。

上面有一个变种，您可能会想知道，当您在过程定义中使用过程外部定义的变量时，会发生什么情况呢？例如，假设我们有：

如果我们评估foo，现在会发生什么？那么，tiddlylisp做了一件明智的事情，并将x解释为它是在过程定义之外定义的，所以我们有：

如果我们下一次更改x的值，我们的过程会发生什么？事实上，这改变了foo：

换句话说，在过程定义lambda(Y)(*x，y)中，x确实是指变量x，而不是指x在任何给定时间点可能具有的特定值。

让我们深入挖掘一下tiddlylisp是如何处理作用域和虚拟变量的。让我们来看看当我们定义一个变量时会发生什么：

解释器在内部处理这一问题的方式是维护所谓的环境：一个字典，其键是变量名，其值是相应的变量值。因此，当插入器看到上面的第一行时，它所做的是向环境添加一个值为5的新键"；x"；。当解释器看到第二行时，它会查询环境，查找键x，并返回相应的值。如果您愿意，可以将环境视为解释器的内存或数据存储，在其中存储到目前为止定义的变量的所有详细信息。

所有这些都很简单。我们可以继续定义和更改变量，而解释器只是在必要时不断咨询和修改环境。但是，当您使用lambda定义新过程时，解释器对定义中使用的变量的处理略有不同。让我们来看一个例子：

tiddlylisp；(定义h 5)tiddlylisp&>(定义面积(lambda(B)(*b h)tiddlylisp；>(区域2)10。

这里我想集中讨论的是过程定义(lambda(B)(*bh))。到目前为止，口译员一直在吃力地工作，适当地修改环境。然而，当它看到(lambda.)时所发生的是，解释器创建了一个新的环境，称为内部环境的环境，与外部环境不同，外部环境是解释器在到达(lambda.)之前一直在其中操作的环境。陈述。内部环境是一个新的字典，其键最初只是过程的参数-在本例中是单个键b-其值将在调用过程时提供。

简单地说，解释器在看到(lambda(B)(*bh))时所做的是创建一个新的内部环境，其中键b的值将在调用过程时设置。当计算表达式(*b h)(定义从过程返回的结果)时，解释器所做的是首先查询内部环境，在那里它找到关键字b，但没有找到关键字h。当它找不到h时，它会在外部环境中查找h，在外部环境中确实已经定义了关键字h，并检索适当的值。

我已经描述了一个简单的示例，展示了环境是如何工作的，但是tiddlylisp还允许我们将过程定义嵌套在过程定义中，嵌套在过程定义中(依此类推)。为了解决这个问题，顶级的tiddlylisp解释器在全局环境中运行，每个过程定义都会创建一个新的内部环境，如果合适的话，可能会嵌套在以前创建的内部环境中。

如果所有这些关于内部和外部环境的讨论让你感到困惑，不要害怕。在这个阶段，了解环境是如何工作的确实很重要，但是如果细节看起来仍然难以捉摸，您不应该担心。在我看来，理解这些细节的最好方法不是通过抽象的讨论，而是通过查看tiddlylisp的工作代码。我们很快就会谈到这一点，但现在我们可以带着对环境如何工作的总体印象继续前进。

到目前为止，我已经描述的过程定义仅从单个表达式计算和返回值。我们可以使用这样的表达式来完成令人惊讶的复杂事情，因为我们有嵌套表达式的能力。不过，如果有一种将不涉及嵌套的表达式链接在一起的方法会很方便。执行此操作的一种方法是使用BEGIN关键字。BEGIN在定义复杂过程时特别有用，因此我将在该上下文中给出一个示例：

此行定义一个名为Area的过程，只有一个参数r，其中(Area R)的值就是表达式的值。

用适当的r值替换。tiddlylisp对上面的BEGIN表达式求值的方式是，它按出现的顺序连续求值所有单独的子表达式，然后返回最后一个子表达式的值，在本例中是子表达式(*pi(*r r))。所以，举个例子，我们得到。

现在，在这样一个简单的示例中，您可能会认为避免定义pi更有意义，只需将3.14直接放到后面的表达式中即可。但是，这样做会使代码的意图变得不那么清晰，我相信您会发现很容易想象出更复杂的情况。

..