第 6 章 函数作为表达方式

## 第 6 章 函数作为表达方式 通常说来，数据结构被用来描述事物。可以用数组描述坐标变换，用树结构表示命令的层次结构，而用图来表示铁路网。在 Lisp 里，我们常会使用闭包作为表现形式。在闭包里，变量绑定可以保存信息，也能扮演在复杂数据结构中指针的角色。如果让一组闭包之间共享绑定，或者让它们之间能相互引用，那么我们就可以创建混合型的对象类型，它同时继承了数据结构和程序逻辑两者的优点。 其实在表象之下，共享绑定就是指针。闭包只是让我们能在更高的抽象层面上操作指针。通过用闭包来表示我们以往用静态数据结构表示的对象，就往往可能得到更为优雅，效率更好的程序。 ### 6.1 网络 闭包有三个有用的特性：它是动态的，拥有局部状态，而且我们可以创建闭包的多个实例。那么带有局部状态的动态对象的多个拷贝能在什么地方一展身手呢？答案是：和网络有关的程序。许多情况下，我们可以把网络中的节点表示成闭包。闭包在拥有其局部状态的同时，它还能引用其它闭包。因而，一个表示网络中节点的闭包是能够知道作为它发送数据目的地的其他几个节点（闭包） 的。换句话说，我们有能力把网络结构直接翻译成代码。 在本节和下一节里，我们会分别了解两种遍历网络的方法。首先我们会按照传统的办法，即把节点定义成结构体，并用与之分离的代码来遍历网络。接着，在下一节我们将会用一个统一的抽象模型来构造通用功能的程序。 ~~~ ;; [示例代码6.1] ;; 一轮 twenty questions 游戏 > (run-node 'people) Is the person a man? >> yes Is he living? >> no Was he American? >> yes Is he on a coin? >> yes Is the coin a penny? >> yes LINCOLN ~~~ 我们将选择一个最简单的应用作为例子：一个能运行 twenty questions 的程序。我们的网络将会是一棵二叉树。每个非叶子节点都会含有一个是非题，并且根据对这个问题的回答，遍历过程会在左子树或者右子树两者中择一，继续往下进行。叶子节点将会含有所有的返回值。当遍历过程遇到叶子节点时，叶子节点的值会被作为遍历过程的返回值返回。如 [示例代码 6.1] 所示，是程序运行一轮 twenty questions 的样子。 从习惯的办法着手，可能就是先定义某种数据结构来表示节点。节点应该包含这几样信息：它是否是叶子节点；如果是的话，那返回值是什么，倘若不是，要问什么问题；还有与答案对应的下个节点是什么样的。 译者注：twenty questions 曾是一档国外很流行的电视智力节目，同时也是人工智能的重要题材。 ~~~ ;; [示例代码 6.2] ;; 节点的表示方法及其定义 (defstruct node contents yes no) (defvar *nodes* (make-hash-table)) (defun defnode (name conts &optional yes no) (setf (gethash name *nodes*) (make-node :contents conts :yes yes :no no))) ~~~ [示例代码 6.2] 里定义了一个信息足够详尽的数据结构。它的设计目标是让数据所占的空间最小化。contents 字段中要么是问题要么是返回值。如果该节点不是叶子节点，那么yes 和no 字段会告诉我们与问题的答案对应的去向；如果节点是个叶子节点，我们自然会知道这一点，因为这些字段会是空的。全局的*nodes* 是一个哈希表，在表中，我们会用节点的名字来索引节点。最后，defnode 会新建一个节点（两种节点都可以），并把它保存到*nodes* 中。有了这些原材料，我们就可以定义树的第一个节点了： ~~~ (defnode 'people "Is the person a man?" 'male 'female) ~~~ [示例代码 6.3] 中所示的网络正好足够我们运行6.1 中所示的一轮游戏。 ~~~ ;; [示例代码 6.3] ;; 作为样例的网络 (defnode 'people "Is the person a man?" 'male 'female) (defnode 'male "Is he living?" 'liveman 'deadman) (defnode 'deadman "Was he American?" 'us 'them) (defnode 'us "Is he on a coin?" 'coin 'cidence) (defnode 'coin "Is the coin a penny?" 'penny 'coins) (defnode 'penny 'lincoln) ;; [示例代码 6.4] ;; 用来遍历网络的函数 (defun run-node (name) (let ((n (gethash name *nodes*))) (cond ((node-yes n) (format t "~A~%>> " (node-contents n)) (case (read) (yes (run-node (node-yes n))) (t (run-node (node-no n))))) (t (node-contents n))))) ~~~ 现在，我们要做的就是写一个能遍历这个网络的函数了，这个函数应该打印出问题，并顺着答案所指示的路径走下去。函数的名字是 run-node ，如 [示例代码 6.4] 所示。给出一个名字，我们就根据名字找到对应的节点。如果该节点不是叶子节点，就把 contents 作为问题打印出来，按照答案不同，我们继续顺着两条可能的途径之一继续遍历。如果该节点是叶子节点，run-node 会径直返回 contents。使用 [示例代码 6.3] 中定义的网络，这个函数就能生成 [示例代码 6.1] 中的输出信息。 ### 6.2 编译后的网络 在上一节，我们编写了一个使用网络的程序，也许使用任何一种语言都能写出这样的程序。的确，这个程序太简单了，看上去似乎很难把它写成另一个模样。但是事实上，我们可以把程序打理得更简洁一些。 ~~~ ;; [示例代码 6.5] ;; 编译成闭包形式的网络 (defun *nodes* (make-hash-table)) (defun defnode (name conts &optional yes no) (setf (gethash name *nodes*) (if yes #'(lambda () (format t "~A~%>> " conts) (case (read) (yes (funcall (gethash yes *nodes*))) (t (funcall (gethash no *nodes*))))) #'(lambda () conts)))) ~~~ [示例代码 6.5] 就是明证。这是让我们的网络运行起来所需要的所有代码。在这里，不再把节点定义成一个结构， 也没有用一个单独的函数来遍历这些节点，而是把节点表示成闭包。原来保存在数据结构里的数据现在栖身于闭包里的变量绑定中。没有必要运行 run-node 了，它已经隐含在了节点自身里面。要启动遍历过程， 只消 funcall 一下起始的那个节点就行了： ~~~ (funcall (gethash 'people *nodes*)) Is the person a man >> ~~~ 自此，接下来的人机对话就和上个版本的实现一样了。 借助把节点都表示成闭包的方式，我们得以将 twenty questions 网络完全转化成代码（而非数据）。正如我们所看到的，程序代码必须在运行时按照名字来查找节点函数。然而，如果我们确信网络在运行的时候不会重新定义，那就可以更进一步：让节点函数直接调用它们的下一站目标函数，而不必再动用哈希表了。 如 [示例代码 6.6] 所示，是新版的程序代码。现在，*node* 从哈希表改成了一个列表。像以前一样，所有的节点还 是用defnode 定义的，不过定义时并不会生成闭包。在定义好所有的节点之后，我们就调用 compile-net 来一次性地编译整个网络。这个函数递归地进行处理，一直往下，直至树的叶子节点，在递归过程层层返回时，每一步都返回了两个目标函数对应的节点（或称函数），而不仅仅是给出它们的名字。 当最外面的 compile-net 调用返回时，它给出的函数将表示一个我们所需的那部分网络。 ~~~ > (setq n (compile-net 'people)) #<Compiled-Function BF3C06> > (funcall n) Is the person a man? >> ~~~ 注意到，compile-net 进行的编译有两层含义。按照通常编译的含义，它把网络的抽象表示翻译成了代码。 更进一层，如果compile-net 自身被编译的话，那它就会返回编译后的函数。（见第17页） 在编译好网络之后，由defnode 构造的列表就没用了。如果切断列表与程序的联系（例如将*nodes* 设为nil），垃圾收集器就会回收它。 这个版本的程序假定程序中的网络是一种树结构，这个前提对这个应用来说肯定是成立的。 ~~~ ;; [示例代码 6.6] ;; 使用静态引用的编译过程 (defvar *nodes* nil) (defun defnode (&rest args) (push args *nodes*) args) (defun compile-net (root) (let ((node (assoc root *nodes*))) (if (null node) nil (let ((conts (second node)) (yes (third node)) (no (fourth node))) (if yes (let ((yes-fn (compile-net yes)) (no-fn (compile-net no))) #'(lambda () (format t "~A~%>> " conts) (funcall (if (eq (read) 'yes) yes-fn no-fn)))) #'(lambda () conts)))))) ~~~ ### 6.3 展望 有许多涉及网络的程序都能通过把节点编译成闭包的形式来实现。闭包作为数据对象，和各种数据结构一样能用来表现事物的属性。这样做需要一些和习惯相左的思考方式，但是作为回报的是更为迅速，更为优雅的程序。 宏在相当程度上将有助于我们把闭包用作一种表达方式。"用闭包来表示" 是 "编译" 的另外一种说法。而且由于宏是在编译时完成它们的工作的，因而它们理所应当地就是这种技术的最佳载体。在介绍了宏技术之后，第 23 章和第 24 章里会呈上更大规模的程序，这些程序将会使用这里曾用过的方法写成。