从Lisp语言了解编程语言的解释与执行

唐诗

关键词：Lisp函数；过程；程序执行

1过程与数据抽象

对任何程序语言的学习，最终都主要集中在三个方面：基本元素，基本元素的组合功能，对组合后复合对象的抽象功能。

Lisp中的基本元素是表达式。其组成和现在流行的程序语言并没有太大差别，如数字运算符+／，判定谓词eq？等，Lisp作为一个语族，不同的方言（如rocket）会有不同的规定，但大体功能上和C或者Java等相比并没有什么本质的区别。在Lisp中表达式的组织形式是采用括号来构成各项求值表达式，且过程对于参数的调用采用的是前缀式。这在现在的程序语言中比较少见，但这合理有效且不会造成歧义。我们可以从离散数学中采用前缀式来标识二元关系的案例，以找到类似的痕迹。

在Lisp中，将基本元素组合构成复合对象或复合表达式。本质上，这要求语言提供一种类似于“胶水”的东西，能将两个或者更多的对象黏在一起。从最简单的开始，将两个对象组合在一起构成一个对象，可以通过某种操作，从这个对象中提取出原本的两个对象。用同样的方式，将这个组合后的对象和新的对象再用之前的组合方式构成一个新的对象，如此反复，就可以构成任意数量的元素，且我们可以有一定的方式将构成的元素从其中取出。这种愿望思维构成的合理推导，最终将问题规约为两个元素的组合，并能通过一定的方式将其从中取出。Lisp在这里提供的工具叫做序对（pair），具体的表现形式如下。

（ define x（cons 1 2））；定义出x

（ car x）；结果为1

（ cdr x）；结果为2

其中，cons就是这个语言中的胶水工具，我们放入其中的元素有顺序之分，且可以通过car与cdr的方式按照顺序取出。有了这个基本的工具，我们就可以在此基础上进一步构造复合对象。这就是上文中提到的语言的第三个重要部分——将复合对象作为一个整体，将其像基本元素一样，进一步进行组合操作。

cons体现了闭包（closure）的思想，可以说Lisp的数据在cons运算下是封闭的。从序对到闭包运算，这体现了Lisp的特性，也展现了和数学的联系——离散数学中的二元关系有序对，以及群论中的群对于封闭性的要求，都可以使我们找到其中的影子。

cons的实现，要求我们将过程作为第一级元素，能作为求值表达式的返回。下面是一些关于程序语言第一级元素的特点：（1）可被命名为变量；（2）可作为参数传递给程序；（3）可以作为程序的返回值；（4）可以被结合为数据结构。

过程可以像数据一样作为参数与返回，这是函数式编程语言的特点，我们可以在如今市面上常见的函数式语言如scala中找到类似的特性，如此一来，可以采用常规的分派方式实现cons。不过我们可以更进一步，采用纯粹过程的方式来实现cons，Lisp语言中提供了lambda表达式来作为过程的定义和返回，我们可以如下实现cons的功能。

实际代换结果表明没有问题。这被称作邱奇变换。

在面向对象语言中，我们习惯说，对于某个程序的调用，返回某种数据。例如，数字、字符串或者我们通过构造形成的某个数据对象，但是更进一步，我们去问一个数据是什么时，结果可能会语焉不详。当我们说数字1时，我们知道这并不是指我们打印文本中的“1”这个符号，它应该是一种象征，代表着某种高度的抽象，可以是一个鸡蛋，一个苹果，可以让打印文本中显示出1这个符号，也可以是别的什么东西。我们也知道，对它的操作得到的结果意味着什么，例如，1+1=2。而2也是某种抽象。

我们的程序代码，其本质其实是用程序语言对我们所理解的世界的一种模拟，我们对于现实的理解，包括对于抽象的理解，都会反映在我们程序中。邱奇的lambda演算，以及邱奇計数，可以启发我们对计数的纯粹函数的理解。邱奇计数采用的是如下方式来代表O和+1的操作的。

（define zero （lambda （f）

（lambda （x）x）））

（define （add_l n）（lambda （f） （lambda （x）（f（（n f）x）））））

其思想是通过函数调用次数来表示数字，0次调用来表示0，1次调用来表示1。结合上文，可以看到，数字0在这里事实上是一个lambda过程，该过程参数为一个过程，返回一个过程，作为返回结果的过程，接收过程作为参数，对该参数过程调用0次，其结果，体现为传人的参数直接返回——包括参数本身也是lambda过程的情况。相应的，（add_l n）过程以一个过程作为参数，返回结果是一个过程，该返回结果的过程，接收作为参数的过程，对该参数过程调用n+l次。以此为基础，对于0调用add_l得到1和2，就是如下形式。

这里并不是在Lisp中实现实际的数字技术，但是我们可以通过这种方式，来理解数据和过程在本质上的统一。实际上，我们已经能够看出，哪怕是作为最基本元素的数字，本质上也是可以理解为过程，和一般理解为纯粹过程“加法”没有本质的不同。

2分层次的抽象

Lisp方言众多，在不同的场景处理不同的问题时，由Lisp构造和提供一集对应的功能，这些功能可以由原始Lisp通过各类方式封装实现，抑或是考虑对应的功能对解释器进行适度的修改。最终，不必在最底层和一个个的基本元素打交道，而是在更高的层次上进行使用。这是控制大型系统的重要方法——理解复杂事物的关键，就是避免不必要的观察、计算和思考。

比如，在系统已经有了整数计算功能的情况下，我们若要使其能够完成有理数的计算。数学意义上有理数可以由分数表示，是分子和分母构成的一个整体，那么按照抽象的原则，对于具体的实现，我们可以通过构造函数和选择函数来完成。构造函数可以通过整数的分子和分母构造出有理数，选择函数可以针对一个有理数获取其分子或者分母。最简单的实现如下。

所有对于有理数的操作，如有理数的加减乘除，因为主要用到的是对于分子分母提取操作和生成新的有理数，所以可以直接用构造函数和选择函数进行如下处理。

其他诸如减法、乘法以及除法，也可以按照类似的方式实现。实际上，这是在底层的细节实现和上层的实际使用之间，构造了一个水平的抽象屏障。这种数据抽象的方法是一种广泛采用的控制复杂度的方法。因此，当底层有修改，可以只在底层进行，而不会影响上层的使用。

抽象屏障的构建，不只是在水平层面上，也可以在垂直角度上。例如，对于复数的构建，就有两种方式：直角坐标式的和极坐标式的。如此一来，当我们有一个复数的实部和虚部，或者模和偏转角时，实际上有两种不同的复数实现方式。这两种在处理不同的运算时各有优劣，在同一个运算包中保留两种实现，那就需要存在两种构造函数和选择函数，这两者在垂直方向上有一道屏障，而在水平层面上，两者共同在复数屏障之下。

目前，我们构建的有理数、复数，加上Lisp中原本就有的整数，对于他们的操作需要使用各自的运算符，这与我们在数学上的习惯不同。一般来讲，数学中使用+／等符号时，我们不会考虑这些符号作用的数字具体是什么类型，而在我们目前的实现中，目前这是做不到的。考虑到通用运算符的效果，要达成这个目标，就需要考虑数据“类”的问题。例如，给数据加上标签，另外，维护一张表，在表中根据不同的数据类型以及运算目标，放置对应的实际操作过程，在进行通用的运算时，先剥离数据类型的标签，根据类型和操作标签的提示，到表中找到过程处理对应的数据——这是一种比较典型的数据导向编程，本质上就是这些数据对象本身携带着如何操作他们的信息。除此之外，我们也可以在构造过程中直接加上过程，将数据和对应数据类型的操作结合，在调用通用运算符时提取使用，这是另一种组织系统的方式，叫做“消息传递”。

3状态和环境

赋值是一项在程序语言中很常见的功能。不过上文对于Lisp的讨论都没有涉及这一块，也就是没有状态（state）。这意味着在确定了一个对象的值后，在整个过程中它都不会改变。

Lisp具有赋值功能，一个对象在赋值前后其值可能不一样，这时这个对象是有状态的。在赋值前后，对于相同对象的同样操作，可能会产生不同的结果，这一般叫做副作用。如果在没有赋值的情况下，一个个的符号，其实就是对应它实际值的名字，因此在引入赋值后，一个个的变量就是一个个保存值的位置索引，而存储在那里的值是可以改变的。我们对它的引用，实际是通过它获取保存在其中的实际值。在这里，最本质的一点是我们引入了时间的概念。在符号无法直接由原本的值代换来解释执行的情况下，我们需要采用环境模型。

我们对于Lisp中过程的特殊地位已经有了一定的了解。对于Lisp中的list，本质是由一个个的cons不断调用完成的。我们已经知道cons本质是一个过程，因此这里可以说list也是一个过程。而我们所要说的环境模型中的环境，其实就是一张表，或者一个函数。

环境是一个结构化的对象，由一个个的框架构成，包含一些约束，这些约束包括管理变量名字与对应的值。每个框架包含一个指针，指向当前这个框架的外部环境。环境对于程序过程是非常重要的，其确定了表达式求值的上下文。在没有上下文的情况，程序语言的表达式没有任何意义。

Lisp的基础环境为我们提供各类基本操作。之后，每一次的过程调用，都会临日寸生产一个新的框架，框架中包含形式参数到被使用的实际参数的映射。一个变量对于某个特定环境的值，是在这一环境中包含着该变量的第一个框架里這个变量的约束值。过程构建的实质是lambda表达式相对于某个环境求值时，一个过程对象通过对原过程的代码文本和求值时的环境指针进行的重构。

赋值会带来状态和副作用，但它依旧有用且功能强大。它可以让我们将复杂的计算过程模块化，从其中任意一个模块看，其他模块像随着时间不断变化，他们隐藏起自己随时间变化的内部状态。这种策略将注意力集中在对象上，比较符合我们对于世界的认知。

4新语言构建

我们所要面对的问题复杂度是不断加深的。包含Lisp在内的任何一门确定的程序语言是不可能完全满足全部需要。为此，可以以上文提到的技术为基础，构建新的语言。具体而言，是通过构造解释器的方式实现这些语言。

对于某个程序语言的解释器，本质也是一个过程，在应用这个语言的一个表达式时，能够执行求值表达式所要求的动作。其中最基本的思想是：解释器决定了一个程序设计语言中各个表达式的意义，但其本身也不过是另一个程序。

实际上，任何程序都可以看作某个语言的解释器，如上面提到的对于有理数复数的算术规则，实际就可以看作在构造函数和选择函数过程上的新的语言规则的构建。

实现一个Lisp的解释器，使用的语言本身也是Lisp，看上去有些循环定义。不过实际上这种情况并不少见。对于没有显式的循环语法的Lisp，循环实现采用递归调用的方式。一个程序过程的定义在一定情况下可以包含对其自身的使用。使用与被解释语言同样的语言写出的解释器被称为元循环。因为篇幅原因，这里不再展开。

5结束语

编程语言是在对现实世界理解的基础上，对于世界的模拟，用以解决各类问题。从这个角度说，各个语言在其本质上有共通的地方。本文是以Lisp语言为线索讨论相关的执行，这是一种万物皆函数的观察理解世界的方式。另外，诸如面向对象，抑或是其他的方式，则是从其他的角度，用类似的底层工具，采取合适的模型，构筑起适合解决对应问题的方式。