Gentoo中文社区

http://oneindex.gentoo.site/%E8%A7%86%E … kv?preview

http://oneindex.gentoo.site/%E6%B1%87%E … source.zip

yum -y install make zlib zlib-devel gcc-c++ libtool  openssl openssl-devel wget vim

apt install -y zlib1g-dev build-essential libpcre3 libpcre3-dev openssl libssl-dev wget vim

wget http://downloads.sourceforge.net/projec … .35.tar.gz
tar zxvf pcre-8.35.tar.gz
mv pcre-8.35 /usr/local/pcre
cd /usr/local/pcre
./configure
make && make install

wget http://nginx.org/download/nginx-1.22.0.tar.gz
tar zxvf nginx-1.22.0.tar.gz
cd nginx-1.22.0/
./configure --prefix=/usr/local/nginx --with-http_stub_status_module --with-http_ssl_module --with-pcre=/usr/local/pcre
make && make install

vim /etc/init.d/nginx

chmod a+x /etc/init.d/nginx
chkconfig --add nginx
chkconfig nginx on

debian
vim /lib/systemd/system/nginx.service
[Unit]
Description=nginx
After=network.target

[Service]
Type=forking
ExecStart=/usr/local/nginx/sbin/nginx
ExecReload=/usr/local/nginx/sbin/nginx -s reload
ExecStop=/usr/local/nginx/sbin/nginx -s quit
PrivateTmp=true

[Install]
WantedBy=multi-user.target

#!/bin/bash
# nginx Startup script for the Nginx HTTP Server
# it is v.0.0.2 version.
# chkconfig: - 85 15
# description: Nginx is a high-performance web and proxy server.
#              It has a lot of features, but it's not for everyone.
# processname: nginx
# pidfile: /var/run/nginx.pid
# config: /usr/local/nginx/conf/nginx.conf
nginxd=/usr/local/nginx/sbin/nginx
nginx_config=/usr/local/nginx/conf/nginx.conf
nginx_pid=/var/run/nginx.pid
RETVAL=0
prog="nginx"
# Source function library.
. /etc/rc.d/init.d/functions
# Source networking configuration.
. /etc/sysconfig/network
# Check that networking is up.
[ ${NETWORKING} = "no" ] && exit 0
[ -x $nginxd ] || exit 0
# Start nginx daemons functions.
start() {
if [ -e $nginx_pid ];then
   echo "nginx already running...."
   exit 1
fi
   echo -n $"Starting $prog: "
   daemon $nginxd -c ${nginx_config}
   RETVAL=$?
   echo
   [ $RETVAL = 0 ] && touch /var/lock/subsys/nginx
   return $RETVAL
}
# Stop nginx daemons functions.
stop() {
        echo -n $"Stopping $prog: "
        killproc $nginxd
        RETVAL=$?
        echo
        [ $RETVAL = 0 ] && rm -f /var/lock/subsys/nginx /var/run/nginx.pid
}
# reload nginx service functions.
reload() {
    echo -n $"Reloading $prog: "
    #kill -HUP `cat ${nginx_pid}`
    killproc $nginxd -HUP
    RETVAL=$?
    echo
}
# See how we were called.
case "$1" in
start)
        start
        ;;
stop)
        stop
        ;;
reload)
        reload
        ;;
restart)
        stop
        start
        ;;
status)
        status $prog
        RETVAL=$?
        ;;
*)
        echo $"Usage: $prog {start|stop|restart|reload|status|help}"
        exit 1
esac
exit $RETVAL

摘取自骏马金龙的第4章ext文件系统机制原理剖析

在写文件(Linux中一切皆文件)时需要为其分配一个inode号。

其实，在格式化创建文件系统后，所有的inode号都已计算好（创建文件系统时会为每个块组计算好该块组拥有哪些inode号），因此产生了问题：要为文件分配哪一个inode号呢？又如何知道某一个inode号是否已经被分配了呢？

既然是"是否被占用"的问题，使用位图是最佳方案，像bmap记录block的占用情况一样。标识inode号是否被分配的位图称为inodemap简称为imap。这时要为一个文件分配inode号只需扫描imap即可知道哪一个inode号是空闲的。

这样理解更容易些，类似bmap块位图一样，inode号是预先规划好的。inode号分配后，文件删除也会释放inode号。分配和释放的inode号，像是在一个地图上挖掉一块，用完再补回来一样。

imap存在着和bmap和inode table一样需要解决的问题：如果文件系统比较大，imap本身就会很大，每次存储文件都要进行扫描，会导致效率不够高。同样，优化的方式是将文件系统占用的block划分成块组，每个块组有自己的imap范围。

目录

如果没有文件系统

         如何读写文件

         提炼上述过程中我们需要知道的信息

文件系统的实现

         需要在硬盘上保存的信息

         代码上实现的逻辑

                  设备号

                  分区信息

                  file结构体

                  inode保存的信息

如果有文件系统

         读写接口

         读写流程

         TASK_FS
如果没有文件系统

  如果我们不在硬盘本身建立文件系统，我们直接面对硬盘的扇区。
如何读写文件 

先看看对于操作普通文件来说，意味着什么。

  我们要拿着一个小本本，上面记着，文件名，文件所在扇区以及文件大小。每次要读写文件，我们要人工查询这个账本，知道我们要的文件在哪里。如果文件A所在的扇区M已经写满了，随后的一个扇区M+1被文件B占用了，我们还想接着写文件A，怎么办呢？只能从其他地方找一个空闲扇区N，然后在账本上把N记录到文件A占用的扇区项中。

  我们如何知道硬盘上还有哪些空间可以用呢？难道每次都从前往后把扇区使用情况计算一遍吗吗？可能还需要另起一个账本记录扇区使用情况，删除文件，我们把对应的扇区标记为空闲，如果创建文件，把对应的扇区标记为不能使用。

对于操作系统而言呢？我觉得，没有文件系统就不会有操作系统，这样的操作系统充其量就是一个硬盘驱动。为什么？可以设想一下创建文件的过程:

    用户告诉这样的操作系统，说要创建一个文件A
    计算机输出，请你自己记录好文件名，并告诉我要在哪个扇区创建。并且记录好这个文件你占用了哪些扇区

我不能忍受。。。
提炼上述过程中我们需要的信息

将变化的放在一起，将不变的放在一起。统一才有美感。
dir_entry

  对于文件使用情况的账本而言，看起来要表述一个文件在硬盘上的信息，我们需要知道它占用了哪些扇区，它的名字，文件大小这样的信息。那么这些信息应该放在哪里呢？当然可以随机存放，但是存放完了，计算机如何在下次使用的时候找到这个文件呢？还是需要一份记录来索引这些信息，还不如把这些文件信息按照统一格式存放在一起，这就是目录结构(dir_entry)的由来。按照树状目录能得到任何文件信息。
sector_map

对于硬盘使用情况的账本而言，要记录好哪些扇区空闲，哪些已经被使用了。这就是sector_map的由来。
super_block

那么这些账本本身是存在于硬盘的某些地方，还需要一个总账本来记录这些管理块的信息，这个总账本就是super_block。
inode

那么inode的由来呢？为什么文件名和inode分开存放呢？

  试想一下，如果文件名和文件的属性信息一起存放的话，一个文件目录项会占用很大的空间，一个扇区也许只能存几个文件的信息，而系统在查找文件的时候，可能要读很多次扇区才能找到需要的文件，这样大大影响系统的效率。毕竟我们在找文件的时候，不需要文件的信息，不需要知道文件大小、所在扇区等等信息全部与查找无关，为什么要这些信息来影响我们的速度呢？我们只要文件名来判断这是不是我们要找的文件。所以将文件的其余信息剥离出来概括为inode结构体。
inode_array

  inode单独列出来了，存放在哪里呢？如何通过dir_entry找到inode呢？当然可以存放于任何扇区上，只不过dir_entry可能要加上inode所在扇区和在扇区中的偏移两个字段了，随之而来问题就是存放inode的扇区只能用来存放其他inode而不能用来存放文件数据了，因为我们给文件分配空间是按照扇区为单位的，难道一个扇区分给文件时候，还要记上一笔在偏移offset处是inode占用的，读写的时候请跳过，这样的逻辑恐怕没人会去用代码实现它吧。另外，由于“存放inode的扇区只能用来存放其他inode而不能用来存放文件数据”这样的原因，设计者就折中了一下，把indoe占用的扇区都提到一个单独空间，以后所有的inode都放到这个空间里，这个空间就是inode_array。

  当然也会出现问题，可能inode_array满了，而硬盘空间还要很大剩余；或者硬盘空间嘛呢，inode_array还有很多剩余。这是很极端的情况，总要有不尽人意的地方，那就把这个不足最小化吧。

  在存放inode的时候，怎么知道inode_array中哪个下标可以用呢？这就是又需要一份记录，来记录inode_array中哪些是空闲的，哪些是已经使用，这个记录就是inode_map。而inode在inode_array中的下标就是inode_num。dir_entry中记录了这个inode_num就可以在inode_array中找到对应的文件信息了。这个过程衔接的太美妙了。
文件系统的实现

文件系统需要的结构体大概都知道了，剩下的仅仅是需要规划处具体的结构体了。我们来看看。
需要在硬盘上保存的信息

    超级块

    Inode-map

    Sector-map

    Inode-array

    上面几个结构体作者在书中都列举出来了，都是很好理解的。我不啰嗦再搬运过来了。
代码上实现的逻辑
设备号

  正是在作者的讲解下，我算是真正的了解到设备号的意义。以前总是看书上说主设备号代表设备归属于哪个驱动，子设备号真正表明是哪个具体的设备。我虽然能顺着设备号找到驱动，能从驱动中看到子设备号对流程的分用作用，但是感觉总是欠缺点什么。我就好奇为什么linux 0.12中将0x300就能代表第一块硬盘，难道不能是0x400吗？为什么0代表整个硬盘，1代表第一个分区？分区编号要按照物理分区顺序吗？如果是0x400会产生什么影响呢？

  跟着作者一起学着规划硬盘空间，才渐渐明白，这些编号可以随意编，跟硬盘上的分区顺序不存在某种必然的联系，只是最后落实到保存硬盘信息的结构体上的时候，不会出现偏差就可以了。

  对于操作系统而言，每个分区都被当做一个独立的设备对待。看看书中所描述的硬盘信息结构体。
复制代码

struct part_info {
    u32    base;    /* # of start sector (NOT byte offset, but SECTOR) */
    u32    size;    /* how many sectors in this partition */
};

/* main drive struct, one entry per drive */
struct hd_info
{
    int            open_cnt;
    struct part_info    primary[NR_PRIM_PER_DRIVE];//计算后NR_PRIM_PER_DRIVE = 5
    struct part_info    logical[NR_SUB_PER_DRIVE];// 计算后NR_SUB_PER_DRIVE = 64
};

复制代码

  由结构体可以看出来，硬盘上存在的每个分区都会被记录下来。

  书中根设备编号是0x322，可以知道子设备号是0x22，一开始很困惑，这么大的子设备号，难道要分0x22个分区？或者说系统怎么就知道0x22表示的是根分区呢？

  还得再看一段代码：

logidx = (p->DEVICE - MINOR_hd1a) % NR_SUB_PER_DRIVE;
sect_nr += p->DEVICE < MAX_PRIM ?
        hd_info[drive].primary[p->DEVICE].base :
        hd_info[drive].logical[logidx].base;

  先将设备号减去第一个逻辑设备的编号得到设备号在logical数组的下标。当然，可能这个设备号不是逻辑设备，而是主分区。没关系，下一步判断p->DEVICE 是不是小于MAX_PRIM，如果小于，说明是主分区，直接用p->DEVICE在primary数组中取值就可以了。

  原来是这样，你想怎么样编号就怎么样编号，只要你自己能找到映射关系就可以了。
分区信息

  硬盘的管理结构体已经设计好了，那么如何获取硬盘的分区信息呢？见硬盘驱动那篇总结。
文件描述符

  内存中的文件如何和硬盘中的文件联系起来？当我们打开一个文件后，后续的操作，如何来标示我们操作的是一个文件而不是一段莫名其妙的内存呢？

  首先，我们会想到将inode读到内存就好了，我们就知道文件的所有信息了。那文件名呢？好像文件名除了查找匹配能贡献一份力量，其它地方用不着啊，难道也一些读进来吗？仅仅是做个标识而已，用一个数不是更好、更简单吗？这就是文件描述符的作用。那文件描述符放在哪里呢？由于每个进程打开的文件不同，打开同一个文件的次序不同，那么文件描述符一般情况下也就不能作为进程共享的资源了(当然，域套接字是可以的，内核社区的人员一次又一次地刷新人们的理解力)。既然如此，文件描述符最好是进程私有的了，就只能放在进程表(也就是进程控制块)里面了。此外，机器资源有限，总不能让一个进程无限制的打开文件，最好大家都没内存了，只能歇菜了。所以，一个进程打开的文件数是有限制的，目前我们只给20个就好了。
file结构体

  好像有了文件描述符就可以直接和inode关联起来了，没必要中间再加一层file结构体啊。我想是因为要以比较节约的方式共享文件吧，节约什么呢，除了内存还能有谁能让那些设计师精益求精呢？ 

    我们当然可以在每个进程控制块里面分配20个存放文件信息的结构体，存放读写偏移指针、打开的权限、inode指针等等信息。但是能保证进程会长时间打开20个文件吗？如果不能保证，那不就浪费了。如果以后允许打开100个文件呢？难道进程控制块也要随之而增大吗？
    关于共享文件，父子进程通过一个放在描述符数组里面的指针共享一个file结构体，而不用在单独维护一个file时候还要考虑同步。设想这样一个情形：父子进程都对一个文件进行写操作，父进程写了10个字符，按照需求该子进程接着写10个字符了，如果是父子进程单独维护file结构体，那么实际上只有子进程写了10个字符，父进程写的10个字符被覆盖了。如果共享呢？file中的pos每次操作对于两个进程而言都是同步的(当然这个例子不太严谨，它本身就存在同步问题，但是仅仅用来说明一点问题还是可以的)。

inode保存的信息

  为什么不用inode本身当做系统或者进程操作文件的接口呢？这个问题比较好考虑。多个进程操作同一个文件，那读写指针的值肯定不一样，读写方式也不一样，其实这些不一样的地方提炼出来就是file结构体啦，file结构体的内容也不是随意产生的。

  将变化的放在一起，将不变的放在一起。
如果有文件系统

再接下来考虑一下如果有文件系统能给我们带来什么好处呢？
读写接口

不过，首先还是要实现读写接口的，就套用linux惯用的读写接口就好了。

int read(int fd, void *buf, int count);

只不过linux是通过中断调用来和内核交互，咱们是通过给TASK_FS发送消息并同步等待来实现的。
读写流程

    那么如果一个用户进程A请求读写一个文件X，那么A会向TASK_FS进程发送消息，告诉FS文件名和读写模式。
    功能完备的文件系统还要考虑很多因素，诸如做下判断，看看文件路径是相对于当前目录还是根目录。我们比较简单，全部按照根目录实现，而且不支持多级目录，所有文件都放在根目录中。
    TASK_FS会给TASK_HD发消息，把目录区读给我。然后逐一比较有没有相同的文件名，假设有同名的，根据dir_entry中记录的inode_num算一下文件indoe所在的扇区是多少，然后再给TASK_HD发消息，把inode所在扇区读进来，文件具体的信息就有了。
    后续操作这个文件，TASK_HD根据进程控制块中的信息来计算和决定该怎么操作文件数据。比如说根据文件描述找到file结构体，里面有读写指针知道下一步要操作的位置是哪里，通过file结构体找到inode，这样就知道文件数据在哪个扇区了。

通过上面简单的叙述，也可以窥见现代文件系统问什么加入了dentry这个成员，目录项在查找的时候也是经常用到的，还不如缓存在内存中，加快读写速度。
TASK_FS

  TASK_FS在微内核的设计中，被设计为一个进程了，它不断地循环读取其它进程发给它的读写请求，但是一次只能处理一个请求，如果这个请求没有完成，那么其它进程只能挂接在TASK_FS的等待队列上等待了。不过没关系，过早的优化是万恶之源。

section .data
         hello:        db 'Hello World!/n',10     ;’Hello World!’，加换行符
         helloLen:  equ $-hello                   ;’Hello World!’字符串长度
section .text
         global _start
_start:
         move ax,4                  ;4:sys_write系统调用号
         mov ebx,1                  ;1:标准输出文件描述符
         mov ecx,hello              ;放hello字符串的首地址
         mov edx,helloLen           ;hello字符串长度
         int 80h                    ;软中断，陷入内核
         move ax,1                  ;sys_exit系统调用号
         mov ebx,0                  ;返回值，0表示没有错误.exit(0)
         int 80h                    ;这里有必要解释下，int 80h实际上是执行一个中断，叫做软中断，int 80h执行之后，中断会返回到原来发生中断的那条指令的下一条指令的地址开始取指，可以阅读我的另一篇关于ARM流水线的文章， 所以，mov ax,1这条指令之后的又需要再次产生一个软中断陷入内核来执行exit操作。即需要再调用一次int 80h,你只需要记住，每执行一个系统调用，都需要跟一条int 80h 来陷入内核执行。

首先介绍一下我自己:本人是一个极客,爱好研究OS底层技术！觉得只有掌握OS底层技术才算真正掌握IT技术！

当初在网上看到Gentoo方面的介绍，兴致勃勃安装,结果以失败告终!后面在某年国庆终于编译到图形界面,卡在火狐安装上,后来一直没有整了!
进了几个Gentoo群，发现都不活跃,后来去了电报上，才发现电报才是最活跃！

个人觉得技术是慢慢积累的，感觉新手没有好的交流平台，相信很多英文很多人都比较吃力！

所以我就开了这个中文社区,当然不代表本人精通Gentoo,只是为了方便新手入门和学习,也方便有相同爱好的朋友加入!

网站至少会开放十年！

同时对以下网友特别鸣谢:
TMD 免费吧管理团队成员(网站:http://bbs.mn)
Viper 中国黑客第一军团负责人(公司网站:http://www.cnini.com)
齐雷鸣 益友和同事(工作室:https://www.iegum.com/)
Batsum SQL爱好者(个人博客:u.batsum.com)
雾雨凝霜  一个只会吹水的Linux爱好者
杰克 跨境自由职业者(个人网站:https://qhjack.gitee.io)

semes

本节既是备注亦作为参考文献。所有列于此的书籍与论文皆值得阅读。

译注: 备注后面跟随的数字即书中的页码
备注 viii (Notes viii)

Steele, Guy L., Jr., Scott E. Fahlman, Richard P. Gabriel, David A. Moon, Daniel L. Weinreb , Daniel G. Bobrow, Linda G. DeMichiel, Sonya E. Keene, Gregor Kiczales, Crispin Perdue, Kent M. Pitman, Richard C. Waters, 以及 John L White。Common Lisp: the Language, 2nd Edition. Digital Press, Bedford (MA), 1990.
备注 1 (Notes 1)

McCarthy, John.Recursive Functions of Symbolic Expressions and their Computation by Machine, Part I. CACM, 3:4 (April 1960), pp. 184-195.

McCarthy, John.History of Lisp. In Wexelblat, Richard L. (Ed.) Histroy of Programming Languages. Academic Press, New York, 1981, pp. 173-197.
备注 3 (Notes 3)

Brooks, Frederick P. The Mythical Man-Month. Addison-Wesley, Reading (MA), 1975, p. 16.

Rapid prototyping is not just a way to write programs faster or better. It is a way to write programs that otherwise might not get written at all. Even the most ambitious people shrink from big undertakings. It’s easier to start something if one can convince oneself (however speciously) that it won’t be too much work. That’s why so many big things have begun as small things. Rapid prototyping lets us start small.
备注 4 (Notes 4)

同上， 第 i 页。
备注 5 (Notes 5)

Murray, Peter and Linda. The Art of the Renaissance. Thames and Hudson, London, 1963, p.85.
备注 5-2 (Notes 5-2)

Janson, W.J. History of Art, 3rd Edition. Abrams, New York, 1986, p. 374.

The analogy applies, of course, only to paintings done on panels and later on canvases. Well-paintings continued to be done in fresco. Nor do I mean to suggest that painting styles were driven by technological change; the opposite seems more nearly true.
备注 12 (Notes 12)

car 与 cdr 的名字来自最早的 Lisp 实现里，列表内部的表示法：car 代表“寄存器位址部分的内容”、cdr 代表“寄存器递减部分的内容”。
备注 17 (Notes 17)

对递归概念有困扰的读者，可以查阅下列的书籍：

Touretzky, David S. Common Lisp: A Gentle Introduction to Symbolic Computation. Benjamin/Cummings, Redwood City (CA), 1990, Chapter 8.

Friedman, Daniel P., and Matthias Felleisen. The Little Lisper. MIT Press, Cambridge, 1987.

譯註：這本書有再版，可在這裡找到。
备注 26 (Notes 26)

In ANSI Common Lisp there is also a lambda macro that allows you to write (lambda (x) x) for #'(lambda (x) x) . Since the use of this macro obscures the symmetry between lambda expressions and symbolic function names (where you still have to use sharp-quote), it yields a specious sort of elegance at best.
备注 28 (Notes 28)

Gabriel, Richard P. Lisp Good News, Bad News, How to Win BigAI Expert, June 1991, p.34.
备注 46 (Notes 46)

Another thing to be aware of when using sort: it does not guarantee to preserve the order of elements judged equal by the comparison function. For example, if you sort (2 1 1.0) by < , a valid Common Lisp implementation could return either (1 1.0 2) or (1.0 1 2) . To preserve as much as possible of the original order, use instead the slower stable-sort (also destructive), which could only return the first value.
备注 61 (Notes 61)

A lot has been said about the benefits of comments, and little or nothing about their cost. But they do have a cost. Good code, like good prose, comes from constant rewriting. To evolve, code must be malleable and compact. Interlinear comments make programs stiff and diffuse, and so inhibit the evolution of what they describe.
备注 62 (Notes 62)

Though most implementations use the ASCII character set, the only ordering that Common Lisp guarantees for characters is as follows: the 26 lowercase letters are in alphabetically ascending order, as are the uppercase letters, and the digits from 0 to 9.
备注 76 (Notes 76)

The standard way to implement a priority queue is to use a structure called a heap. See: Sedgewick, Robert. Algorithms. Addison-Wesley, Reading (MA), 1988.
备注 81 (Notes 81)

The definition of progn sounds a lot like the evaluation rule for Common Lisp function calls (page 9). Though progn is a special operator, we could define a similar function:

(defun our-progn (ftrest args)
  (car (last args)))

This would be horribly inefficient, but functionally equivalent to the real progn if the last argument returned exactly one value.
备注 84 (Notes 84)

The analogy to a lambda expression breaks down if the variable names are symbols that have special meanings in a parameter list. For example,

(let ((&key 1) (&optional 2)))

is correct, but the corresponding lambda expression

((lambda (ftkey ftoptional)) 1 2)

is not. The same problem arises if you try to define do in terms of labels . Thanks to David Kuznick for pointing this out.
备注 89 (Notes 89)

Steele, Guy L., Jr., and Richard P. Gabriel. The Evolution of Lisp. ACM SIGPLANNotices 28:3 (March 1993). The example in the quoted passage was translated from Scheme into Common Lisp.
备注 91 (Notes 91)

To make the time look the way people expect, you would want to ensure that minutes and seconds are represented with two digits, as in:

(defun get-time-string ()
  (multiple-value-bind (s m h) (get-decoded-time)
    (format nil "~A:~2,,,'0@A:~2,,,'O@A" h m s)))

备注 94 (Notes 94)

In a letter of March 18 (old style) 1751, Chesterfield writes:

“It was notorious, that the Julian Calendar was erroneous, and had overcharged the solar year with eleven days. Pope Gregory the Thirteenth corrected this error [in 1582]; his reformed calendar was immediately received by all the Catholic powers of Europe, and afterwards adopted by all the Protestant ones, except Russia, Sweden, and England. It was not, in my opinion, very honourable for England to remain in a gross and avowed error, especially in such company; the inconveniency of it was likewise felt by all those who had foreign correspondences, whether political or mercantile. I determined, therefore, to attempt the reformation; I consulted the best lawyers, and the most skillful astronomers, and we cooked up a bill for that purpose. But then my difficulty began; I was to bring in this bill, which was necessarily composed of law jargon and astronomical calculations, to both of which I am an utter stranger. However, it was absolutely necessary to make the House of Lords think that I knew something of the matter; and also to make them believe that they knew something of it themselves, which they do not. For my own part, I could just as soon have talked Celtic or Sclavonian to them, as astronomy, and they would have understood me full as well; so I resolved to do better than speak to the purpose, and to please instead of informing them. I gave them, therefore, only an historical account of calendars, from the Egyptian down to the Gregorian, amusing them now and then with little episodes; but I was particularly attentive to the choice of my words, to the harmony and roundness of my periods, to my elocution, to my action. This succeeded, and ever will succeed; they thought I informed them, because I pleased them; and many of them said I had made the whole very clear to them; when, God knows, I had not even attempted it.”

See: Roberts, David (Ed.) Lord Chesterfield’s Letters. Oxford University Press, Oxford, 1992.
备注 95 (Notes 95)

In Common Lisp, a universal time is an integer representing the number of seconds since the beginning of 1900. The functions encode-universal-time and decode-universal-time translate dates into and out of this format. So for dates after 1900, there is a simpler way to do date arithmetic in Common Lisp:

(defun num->date (n)
  (multiple-value-bind (ig no re d m y)
                       (decode-universal-time n)
    (values d m y)))

(defun date->num (d m y)
  (encode-universal-time 1 0 0 d m y))

(defun date+ (d m y n)
  (num->date (+ (date->num d m y)
                (* 60 60 24 n))))

Besides the range limit, this approach has the disadvantage that dates tend not to be fixnums.
备注 100 (Notes 100)

Although a call to setf can usually be understood as a reference to a particular place, the underlying machinery is more general. Suppose that a marble is a structure with a single field called color:

(defstruct marble
  color)

The following function takes a list of marbles and returns their color, if they all have the same color, or n i l if they have different colors:

(defun uniform-color (1st)
  (let ((c (marble-color (car 1st))))
    (dolist (m (cdr 1st))
      (unless (eql (marble-color m) c)
        (return nil)))
    c))

Although uniform-color does not refer to a particular place, it is both reasonable and possible to have a call to it as the first argument to setf . Having defined

(defun (setf uniform-color) (val 1st)
  (dolist (m 1st)
    (setf (marble-color m) val)))

we can say

(setf (uniform-color *marbles*) 'red)

to make the color of each element of *marbles* be red.
备注 100-2 (Notes 100-2)

In older Common Lisp implementations, you have to use defsetf to define how a call should be treated when it appears as the first argument to setf. Be careful when translating, because the parameter representing the new value comes last in the definition of a function whose name is given as the second argument to defsetf . That is, the call

(defun (setf primo) (val 1st) (setf (car 1st) val))

is equivalent to

(defsetf primo set-primo)

(defun set-primo (1st val) (setf (car 1st) val))

备注 106 (Notes 106)

C, for example, lets you pass a pointer to a function, but there’s less you can pass in a function (because C doesn’t have closures) and less the recipient can do with it (because C has no equivalent of apply). What’s more, you are in principle supposed to declare the type of the return value of the function you pass a pointer to. How, then, could you write map-int or filter , which work for functions that return anything? You couldn’t, really. You would have to suppress the type-checking of arguments and return values, which is dangerous, and even so would probably only be practical for 32-bit values.
备注 109 (Notes 109)

For many examples of the versatility of closures, see: Abelson, Harold, and Gerald Jay Sussman, with Julie Sussman.Structure and Interpretation of Computer Programs. MIT Press, Cambridge, 1985.
备注 109-2 (Notes 109-2)

For more information about Dylan, see: Shalit, Andrew, with Kim Barrett, David Moon, Orca Starbuck, and Steve Strassmann. Dylan Interim Reference Manual. Apple Computer, 1994.

At the time of printing this document was accessible from several sites, including http://www.harlequin.com andhttp://www.apple.com. Scheme is a very small, clean dialect of Lisp. It was invented by Guy L. Steele Jr. and Gerald J. Sussman in 1975, and is currently defined by: Clinger, William, and Jonathan A. Rees (Eds.) Revised4 Report on the Algorithmic Language Scheme. 1991.

This report, and various implementations of Scheme, were at the time of printing available by anonymous FTP from swiss-ftp.ai.mit.edu:pub.

There are two especially good textbooks that use Scheme—Structure and Interpretation (see preceding note) and: Springer, George and Daniel P. Friedman. Scheme and the Art of Programming. MIT Press, Cambridge, 1989.
备注 112 (Notes 112)

The most horrible Lisp bugs may be those involving dynamic scope. Such errors almost never occur in Common Lisp, which has lexical scope by default. But since so many of the Lisps used as extension languages still have dynamic scope, practicing Lisp programmers should be aware of its perils.

One bug that can arise with dynamic scope is similar in spirit to variable capture (page 166). You pass one function as an argument to another. The function passed as an argument refers to some variable. But within the function that calls it, the variable has a new and unexpected value.

Suppose, for example, that we wrote a restricted version of mapcar as follows:

(defun our-mapcar (fn x)
  (if (null x)
      nil (cons (funcall fn (car x))
                (our-mapcar fn (cdr x)))))

Then suppose that we used this function in another function, add-to-all , that would take a number and add it to every element of a list:

(defun add-to-all (1st x)
  (our-mapcar #'(lambda (num) (+ num x))
              1st))

In Common Lisp this code works fine, but in a Lisp with dynamic scope it would generate an error. The function passed as an argument to our-mapcar refers to x . At the point where we send this function to our-mapcar , x would be the number given as the second argument to add-to-all . But where the function will be called, within our-mapcar , x would be something else: the list passed as the second argument to our-mapcar . We would get an error when this list was passed as the second argument to + .
备注 123 (Notes 123)

Newer implementations of Common Lisp include avariable *read-eval* that can be used to turn off the # . read-macro. When calling read-from-string on user input, it is wise to bind *read-eval* to nil . Otherwise the user could cause side-effects by using # . in the input.
备注 125 (Notes 125)

There are a number of ingenious algorithms for fast string-matching, but string-matching in text files is one of the cases where the brute-force approach is still reasonably fast. For more on string-matching algorithms, see: Sedgewick, Robert. Algorithms. Addison-Wesley, Reading (MA), 1988.
备注 141 (Notes 141)

In 1984 CommonLisp, reduce did not take a :key argument, so random-next would be defined:

(defun random-next (prev)
  (let* ((choices (gethash prev *words*))
         (i (random (let ((x 0))
                      (dolist (c choices)
                        (incf x (cdr c)))
                      x))))
    (dolist (pair choices)
      (if (minusp (decf i (cdr pair)))
        (return (car pair))))))

备注 141-2 (Notes 141-2)

In 1989, a program like Henley was used to simulate netnews postings by well-known flamers. The fake postings fooled a significant number of readers. Like all good hoaxes, this one had an underlying point. What did it say about the content of the original flames, or the attention with which they were read, that randomly generated postings could be mistaken for the real thing?

One of the most valuable contributions of artificial intelligence research has been to teach us which tasks are really difficult. Some tasks turn out to be trivial, and some almost impossible. If artificial intelligence is concerned with the latter, the study of the former might be called artificial stupidity. A silly name, perhaps, but this field has real promise—it promises to yield programs that play a role like that of control experiments.

Speaking with the appearance of meaning is one of the tasks that turn out to be surprisingly easy. People’s predisposition to find meaning is so strong that they tend to overshoot the mark. So if a speaker takes care to give his sentences a certain kind of superficial coherence, and his audience are sufficiently credulous, they will make sense of what he says.

This fact is probably as old as human history. But now we can give examples of genuinely random text for comparison. And if our randomly generated productions are difficult to distinguish from the real thing, might that not set people to thinking?

The program shown in Chapter 8 is about as simple as such a program could be, and that is already enough to generate “poetry” that many people (try it on your friends) will believe was written by a human being. With programs that work on the same principle as this one, but which model text as more than a simple stream of words, it will be possible to generate random text that has even more of the trappings of meaning.

For a discussion of randomly generated poetry as a legitimate literary form, see: Low, Jackson M. Poetry, Chance, Silence, Etc. In Hall, Donald (Ed.) Claims for Poetry. University of Michigan Press, Ann Arbor, 1982. You bet.

Thanks to the Online Book Initiative, ASCII versions of many classics are available online. At the time of printing, they could be obtained by anonymous FTP from ftp.std.com:obi.

See also the Emacs Dissociated Press feature, which uses an equivalent algorithm to scramble a buffer.
备注 150 (Notes 150)

下面这个函数会显示在一个给定实现中，16 个用来标示浮点表示法的限制的全局常量：

(defun float-limits ()
  (dolist (m '(most least))
    (dolist (s '(positive negative))
      (dolist (f '(short single double long))
        (let ((n (intern (string-upcase
                            (format nil "~A-~A-~A-float"
                                          m  s  f)))))
          (format t "~30A ~A ~%" n (symbol-value n)))))))

备注 164 (Notes 164)

快速排序演算法由霍尔于 1962 年发表，并被描述在 Knuth, D. E. Sorting and Searching. Addison-Wesley, Reading (MA), 1973.一书中。
备注 173 (Notes 173)

Foderaro, John K. Introduction to the Special Lisp Section. CACM 34:9 (Setember 1991), p.27
备注 176 (Notes 176)

关于 CLOS 更详细的信息，参考下列书目：

Keene, Sonya E. Object Oriented Programming in Common Lisp , Addison-Wesley, Reading (MA), 1989

Kiczales, Gregor, Jim des Rivieres, and Daniel G. Bobrow. The Art of the Metaobject Protocol MIT Press, Cambridge, 1991
备注 178 (Notes 178)

让我们再回放刚刚的句子一次：*我们甚至不需要看程序中其他的代码一眼，就可以完成种种的改动。*这个想法或许对某些读者听起来担忧地熟悉。这是写出面条式代码的食谱。

面向对象模型使得通过一点一点的来构造程序变得简单。但这通常意味著，在实践上它提供了一种有结构的方法来写出面条式代码。这不一定是坏事，但也不会是好事。

很多现实世界中的代码是面条式代码，这也许不能很快改变。针对那些终将成为面条式代码的程序来说，面向对象模型是好的：它们最起码会是有结构的面条。但针对那些也许可以避免误入崎途的程序来说，面向对象抽象只是更加危险的，而不是有用的。
备注 183 (Notes 183)

When an instance would inherit a slot with the same name from several of its superclasses, the instance inherits a single slot that combines the properties of the slots in the superclasses. The way combination is done varies from property to property:

    The :allocation , :initform (if any), and :documentation (if any), will be those of the most specific classes.
    The :initargs will be the union of the :initargs of all the superclasses. So will the :accessors , :readers , and:writers , effectively.
    The :type will be the intersection of the :types of all the superclasses.

备注 191 (Notes 191)

You can avoid explicitly uninterning the names of slots that you want to be encapsulated by using uninterned symbols as the names to start with:

(progn
  (defclass counter () ((#1=#:state :initform 0)))

  (defmethod increment ((c counter))
    (incf (slot-value c '#1#)))

  (defmethod clear ((c counter))
    (setf (slot-value c '#1#) 0)))

The progn here is a no-op; it is used to ensure that all the references to the uninterned symbol occur within the same expression. If this were inconvenient, you could use the following read-macro instead:

(defvar *symtab* (make-hash-table :test #'equal))

(defun pseudo-intern (name)
  (or (gethash name *symtab*)
      (setf (gethash name *symtab*) (gensym))))

(set-dispatch-macro-character #\# #\[
  #'(lambda (stream char1 char2)
      (do ((acc nil (cons char acc))
           (char (read-char stream) (read-char stream)))
          ((eql char #\]) (pseudo-intern acc)))))

Then it would be possible to say just:

(defclass counter () ((#[state] :initform 0)))

(defmethod increment ((c counter))
  (incf (slot-value c '#[state])))

(defmethod clear ((c counter))
  (setf (slot-value c '#[state]) 0))

备注 204 (Notes 204)

下面这个宏将新元素推入二叉搜索树：

(defmacro bst-push (obj bst <)
  (multiple-value-bind (vars forms var set access)
                       (get-setf-expansion bst)
    (let ((g (gensym)))
      `(let* ((,g ,obj)
              ,@(mapcar #'list vars forms)
              (,(car var) (bst-insert! ,g ,access ,<)))
         ,set))))

备注 213 (Notes 213)

Knuth, Donald E. Structured Programming with goto Statements.Computing Surveys , 6:4 (December 1974), pp. 261-301
备注 214 (Notes 214)

Knuth, Donald E. Computer Programming as an ArtIn ACM Turing Award Lectures: The First Twenty Years. ACM Press, 1987

This paper and the preceding one are reprinted in: Knuth, Donald E. Literate Programming. CSLI Lecture Notes #27, Stanford University Center for the Study of Language and Information, Palo Alto, 1992.
备注 216 (Notes 216)

Steele, Guy L., Jr. Debunking the “Expensive Procedure Call” Myth or, Procedural Call Implementations Considered Harmful or, LAMBDA: The Ultimate GOTO. Proceedings of the National Conference of the ACM, 1977, p. 157.

Tail-recursion optimization should mean that the compiler will generate the same code for a tail-recursive function as it would for the equivalent do. The unfortunate reality, at least at the time of printing, is that many compilers generate slightly faster code for dos.
备注 217 (Notes 217)

For some examples of calls to disassemble on various processors, see: Norvig, Peter. Paradigms ofArtificial Intelligence Programming: Case Studies in Common Lisp. Morgan Kaufmann, San Mateo (CA), 1992.
备注 218 (Notes 218)

A lot of the increased popularity of object-oriented programming is more specifically the increased popularity of C++, and this in turn has a lot to do with typing. C++ gives you something that seems like a miracle in the conceptual world of C: the ability to define operators that work for different types of arguments. But you don’t need an object-oriented language to do this—all you need is run-time typing. And indeed, if you look at the way people use C++, the class hierarchies tend to be flat. C++ has become so popular not because people need to write programs in terms of classes and methods, but because people need a way around the restrictions imposed by C’s approach to typing.
备注 219 (Notes 219)

Macros can make declarations easier. The following macro expects a type name and an expression (probably numeric), and expands the expression so that all arguments, and all intermediate results, are declared to be of that type. If you wanted to ensure that an expression e was evaluated using only fixnum arithmetic, you could say (with-type fixnum e).

(defmacro with-type (type expr)
  `(the ,type ,(if (atom expr)
                   expr
                 (expand-call type (binarize expr)))))

(defun expand-call (type expr)
  `(,(car expr) ,@(mapcar #'(lambda (a)
                              `(with-type ,type ,a))
                          (cdr expr))))

(defun binarize (expr)
  (if (and (nthcdr 3 expr)
           (member (car expr) '(+ - * /)))
      (destructuring-bind (op a1 a2 . rest) expr
        (binarize `(,op (,op ,a1 ,a2) ,@rest)))
    expr))

The call to binarize ensures that no arithmetic operator is called with more than two arguments. As the Lucid reference manual points out, a call like

(the fixnum (+ (the fixnum a)
               (the fixnum b)
               (the fixnum c)))

still cannot be compiled into fixnum additions, because the intermediate results (e.g. a + b) might not be fixnums.

Using with-type , we could duplicate the fully declared version of poly on page 219 with:

(defun poly (a b x)
  (with-type fixnum (+ (* a (expt x 2)) (* b x))))

If you wanted to do a lot of fixnum arithmetic, you might even want to define a read-macro that would expand into a(with-type fixnum ...) .
备注 224 (Notes 224)

在许多 Unix 系统里， /usr/dict/words 是个合适的单词文件。
备注 226 (Notes 229)

T is a dialect of Scheme with many useful additions, including support for pools. For more on T, see: Rees, Jonathan A., Norman I. Adams, and James R. Meehan. The T Manual, 5th Edition. Yale University Computer Science Department, New Haven, 1988.

The T manual, and T itself, were at the time of printing available by anonymous FTP from hing.lcs.mit.edu:pub/t3.1 .
备注 229 (Notes 229)

The difference between specifications and programs is a difference in degree, not a difference in kind. Once we realize this, it seems strange to require that one write specifications for a program before beginning to implement it. If the program has to be written in a low-level language, then it would be reasonable to require that it be described in high-level terms first. But as the programming language becomes more abstract, the need for specifications begins to evaporate. Or rather, the implementation and the specifications can become the same thing.

If the high-level program is going to be re-implemented in a lower-level language, it starts to look even more like specifications. What Section 13.7 is saying, in other words, is that the specifications for C programs could be written in Lisp.
备注 230 (Notes 230)

Benvenuto Cellini’s story of the casting of his Perseus is probably the most famous (and the funniest) account of traditional bronze-casting: Cellini, Benvenuto. Autobiography. Translated by George Bull, Penguin Books, Harmondsworth, 1956.
备注 239 (Notes 239)

Even experienced Lisp hackers find packages confusing. Is it because packages are gross, or because we are not used to thinking about what happens at read-time?

There is a similar kind of uncertainty about def macro, and there it does seem that the difficulty is in the mind of the beholder. A good deal of work has gone into finding a more abstract alternative to def macro. But def macro is only gross if you approach it with the preconception (common enough) that defining a macro is like defining a function. Then it seems shocking that you suddenly have to worry about variable capture. When you think of macros as what they are, transformations on source code, then dealing with variable capture is no more of a problem than dealing with division by zero at run-time.

So perhaps packages will turn out to be a reasonable way of providing modularity. It is prima facie evidence on their side that they resemble the techniques that programmers naturally use in the absence of a formal module system.
备注 242 (Notes 242)

It might be argued that loop is more general, and that we should not define many operators to do what we can do with one. But it’s only in a very legalistic sense that loop is one operator. In that sense, eval is one operator too. Judged by the conceptual burden it places on the user, loop is at least as many operators as it has clauses. What’s more, these operators are not available separately, like real Lisp operators: you can’t break off a piece of loop and pass it as an argument to another function, as you could map-int .
备注 248 (Notes 248)

关于更深入讲述逻辑推论的资料，参见：Stuart Russell 及 Peter Norvig 所著的 Artificial Intelligence: A Modern Approach。
备注 273 (Notes 273)

Because the program in Chapter 17 takes advantage of the possibility of having a setf form as the first argument todefun , it will only work in more recent Common Lisp implementations. If you want to use it in an older implementation, substitute the following code in the final version:

(proclaim '(inline lookup set-lookup))

(defsetf lookup set-lookup)

(defun set-lookup (prop obj val)
  (let ((off (position prop (layout obj) :test #'eq)))
    (if off
        (setf (svref obj (+ off 3)) val)
        (error "Can't set ~A of ~A." val obj))))

(defmacro defprop (name &optioanl meth?)
  `(progn
     (defun ,name (obj &rest args)
       ,(if meth?
          `(run-methods obj ',name args)
          `(rget ',name obj nil)))
     (defsetf ,name (obj) (val)
       `(setf (lookip ',',name ,obj) ,val))))

备注 276 (Notes 276)

If defmeth were defined as

(defmacro defmeth (name obj parms &rest body)
  (let ((gobj (gensym)))
    `(let ((,gobj ,obj))
       (setf (gethash ',name ,gobj)
             #'(lambda ,parms
                 (labels ((next ()
                            (funcall (get-next ,gobj ',name)
                                     ,@parms)))
                   ,@body))))))

then it would be possible to invoke the next method simply by calling next :

(defmeth area grumpy-circle (c)
  (format t "How dare you stereotype me!""/,")
  (next))

备注 284 (Notes 284)

For really fast access to slots we would use the following macro:

(defmacro with-slotref ((name prop class) &rest body)
  (let ((g (gensym)))
    `(let ((,g (+ 3 (position ,prop (layout ,class)
                              :test #'eq))))
       (macrolet ((,name (obj) `(svref ,obj ,',g)))
         ,@body))))

It defines a local macro that refers directly to the vector element corresponding to a slot. If in some segment of code you wanted to refer to the same slot in many instances of the same class, with this macro the slot references would be straight svrefs.

For example, if the balloon class is defined as follows,

(setf balloon-class (class nil size))

then this function pops (in the old sense) a list of ballons:

(defun popem (ballons)
  (with-slotref (bsize 'size balloon-class)
    (dolist (b ballons)
      (setf (bsize b) 0))))

备注 284-2 (Notes 284-2)

Gabriel, Richard P. Lisp Good News, Bad News, How to Win BigAI Expert, June 1991, p.35.

早在 1973 年， Richard Fateman 已经能证明在 PDP-10 主机上， MacLisp 编译器比制造商的 FORTRAN 编译器，产生出更快速的代码。

译注:该篇 MacLisp 编译器在 PDP-10 可产生比 Fortran 快的代码的论文在这可以找到
备注 399 (Notes 399)

It’s easiest to understand backquote if we suppose that backquote and comma are like quote, and that ```,x`` simply expands into (bq (comma x)) . If this were so, we could handle backquote by augmenting eval as in this sketch:

(defun eval2 (expr)
  (case (and (consp expr) (car expr))
    (comma (error "unmatched comma"))
    (bq (eval-bq (second expr) 1))
    (t  (eval expr))))

(defun eval-bq (expr n)
  (cond ((atom expr)
         expr)
        ((eql (car expr) 'comma)
         (if (= n 1)
             (eval2 (second expr))
             (list 'comma (eval-bq (second expr)
                                   (1- n)))))
        ((eql (car expr) 'bq)
         (list 'bq (eval-bq (second expr) (1+ n))))
        (t
         (cons (eval-bq (car expr) n)
               (eval-bq (cdr expr) n)))))

In eval-bq , the parameter n is used to determine which commas match the current backquote. Each backquote increments it, and each comma decrements it. A comma encountered when n = 1 is a matching comma. Here is the example from page 400:

> (setf x 'a a 1 y 'b b 2)
2
> (eval2 '(bq (bq (w (comma x) (comma (comma y))))))
(BQ (W (COMMA X) (COMMA B)))
> (eval2 *)
(W A 2)

At some point a particularly remarkable molecule was formed by accident. We will call it the Replicator. It may not necessarily have been the biggest or the most complex molecule around, but it had the extraordinary property of being able to create copies of itself.

Richard Dawkins

The Selfish Gene

We shall first define a class of symbolic expressions in terms of ordered pairs and lists. Then we shall define five elementary functions and predicates, and build from them by composition, conditional expressions, and recursive definitions an extensive class of functions of which we shall give a number of examples. We shall then show how these functions themselves can be expressed as symbolic expressions, and we shall define a universal function apply that allows us to compute from the expression for a given function its value for given arguments.

John McCarthy

Recursive Functions of Symbolic Expressions and their Computation by Machine, Part I

这个附录包含了 58 个最常用的 Common Lisp 操作符。因为如此多的 Lisp 是（或可以）用 Lisp 所写成，而由于 Lisp 程序（或可以）相当精简，这是一种方便解释语言的方式。

这个练习也证明了，概念上 Common Lisp 不像看起来那样庞大。许多 Common Lisp 操作符是有用的函式库；要写出所有其它的东西，你所需要的操作符相当少。在这个附录的这些定义只需要:

applyarefbackquoteblockcarcdrceilingchar=consdefmacrodocumentationeqerrorexptfdefinitionfunction``floorgensymget-setf-expansionifimagpartlabelslengthmultiple-value-bindnth-valuequoterealpartsymbol-functiontagbodytype-oftypep=+-/<>

这里给出的代码作为一种解释 Common Lisp 的方式，而不是实现它的方式。在实际的实现上，这些操作符可以更高效，也会做更多的错误检查。为了方便参找，这些操作符本身按字母顺序排列。如果你真的想要这样定义 Lisp，每个宏的定义需要在任何调用它们的代码之前。

(defun -abs (n)
  (if (typep n 'complex)
      (sqrt (+ (expt (realpart n) 2) (expt (imagpart n) 2)))
      (if (< n 0) (- n) n)))

(defun -adjoin (obj lst &rest args)
  (if (apply #'member obj lst args) lst (cons obj lst)))

(defmacro -and (&rest args)
  (cond ((null args) t)
        ((cdr args)  `(if ,(car args) (-and ,@(cdr args))))
        (t           (car args))))

(defun -append (&optional first &rest rest)
  (if (null rest)
      first
      (nconc (copy-list first) (apply #'-append rest))))

(defun -atom (x) (not (consp x)))

(defun -butlast (lst &optional (n 1))
  (nreverse (nthcdr n (reverse lst))))

(defun -cadr (x) (car (cdr x)))

(defmacro -case (arg &rest clauses)
  (let ((g (gensym)))
    `(let ((,g ,arg))
       (cond ,@(mapcar #'(lambda (cl)
                           (let ((k (car cl)))
                             `(,(cond ((member k '(t otherwise))
                                       t)
                                      ((consp k)
                                       `(member ,g ',k))
                                      (t `(eql ,g ',k)))
                               (progn ,@(cdr cl)))))
                       clauses)))))

(defun -cddr (x) (cdr (cdr x)))

(defun -complement (fn)
  #'(lambda (&rest args) (not (apply fn args))))

(defmacro -cond (&rest args)
  (if (null args)
      nil
      (let ((clause (car args)))
        (if (cdr clause)
            `(if ,(car clause)
                 (progn ,@(cdr clause))
                 (-cond ,@(cdr args)))
            `(or ,(car clause)
                 (-cond ,@(cdr args)))))))

(defun -consp (x) (typep x 'cons))

(defun -constantly (x) #'(lambda (&rest args) x))

(defun -copy-list (lst)
  (labels ((cl (x)
             (if (atom x)
                 x
                 (cons (car x)
                       (cl (cdr x))))))
    (cons (car lst)
          (cl (cdr lst)))))

(defun -copy-tree (tr)
  (if (atom tr)
      tr
      (cons (-copy-tree (car tr))
            (-copy-tree (cdr tr)))))

(defmacro -defun (name parms &rest body)
  (multiple-value-bind (dec doc bod) (analyze-body body)
    `(progn
       (setf (fdefinition ',name)
             #'(lambda ,parms
                 ,@dec
                 (block ,(if (atom name) name (second name))
                   ,@bod))
             (documentation ',name 'function)
             ,doc)
       ',name)))

(defun analyze-body (body &optional dec doc)
  (let ((expr (car body)))
    (cond ((and (consp expr) (eq (car expr) 'declare))
           (analyze-body (cdr body) (cons expr dec) doc))
          ((and (stringp expr) (not doc) (cdr body))
           (if dec
               (values dec expr (cdr body))
               (analyze-body (cdr body) dec expr)))
          (t (values dec doc body)))))

这个定义不完全正确，参见 let

(defmacro -do (binds (test &rest result) &rest body)
  (let ((fn (gensym)))
    `(block nil
       (labels ((,fn ,(mapcar #'car binds)
                   (cond (,test ,@result)
                         (t (tagbody ,@body)
                            (,fn ,@(mapcar #'third binds))))))
         (,fn ,@(mapcar #'second binds))))))

(defmacro -dolist ((var lst &optional result) &rest body)
  (let ((g (gensym)))
    `(do ((,g ,lst (cdr ,g)))
         ((atom ,g) (let ((,var nil)) ,result))
       (let ((,var (car ,g)))
         ,@body))))

(defun -eql (x y)
  (typecase x
    (character (and (typep y 'character) (char= x y)))
    (number    (and (eq (type-of x) (type-of y))
                    (= x y)))
    (t         (eq x y))))

(defun -evenp (x)
  (typecase x
    (integer (= 0 (mod x 2)))
    (t       (error "non-integer argument"))))

(defun -funcall (fn &rest args) (apply fn args))

(defun -identity (x) x)

这个定义不完全正确：表达式 (let ((&key 1) (&optional 2))) 是合法的，但它产生的表达式不合法。

(defmacro -let (parms &rest body)
  `((lambda ,(mapcar #'(lambda (x)
                         (if (atom x) x (car x)))
                     parms)
      ,@body)
    ,@(mapcar #'(lambda (x)
                  (if (atom x) nil (cadr x)))
              parms)))

(defun -list (&rest elts) (copy-list elts))

(defun -listp (x) (or (consp x) (null x)))

(defun -mapcan (fn &rest lsts)
  (apply #'nconc (apply #'mapcar fn lsts)))

(defun -mapcar (fn &rest lsts)
  (cond ((member nil lsts) nil)
        ((null (cdr lsts))
         (let ((lst (car lsts)))
           (cons (funcall fn (car lst))
                 (-mapcar fn (cdr lst)))))
        (t
         (cons (apply fn (-mapcar #'car lsts))
               (apply #'-mapcar fn
                      (-mapcar #'cdr lsts))))))

(defun -member (x lst &key test test-not key)
  (let ((fn (or test
                (if test-not
                    (complement test-not))
                    #'eql)))
    (member-if #'(lambda (y)
                   (funcall fn x y))
               lst
               :key key)))

(defun -member-if (fn lst &key (key #'identity))
  (cond ((atom lst) nil)
        ((funcall fn (funcall key (car lst))) lst)
        (t (-member-if fn (cdr lst) :key key))))

(defun -mod (n m)
  (nth-value 1 (floor n m)))

(defun -nconc (&optional lst &rest rest)
  (if rest
      (let ((rest-conc (apply #'-nconc rest)))
        (if (consp lst)
            (progn (setf (cdr (last lst)) rest-conc)
                   lst)
            rest-conc))
      lst))

(defun -not (x) (eq x nil))
(defun -nreverse (seq)
  (labels ((nrl (lst)
             (let ((prev nil))
               (do ()
                   ((null lst) prev)
                 (psetf (cdr lst) prev
                        prev      lst
                        lst       (cdr lst)))))
           (nrv (vec)
             (let* ((len (length vec))
                    (ilimit (truncate (/ len 2))))
               (do ((i 0 (1+ i))
                    (j (1- len) (1- j)))
                   ((>= i ilimit) vec)
                 (rotatef (aref vec i) (aref vec j))))))
    (if (typep seq 'vector)
        (nrv seq)
        (nrl seq))))

(defun -null (x) (eq x nil))

(defmacro -or (&optional first &rest rest)
  (if (null rest)
      first
      (let ((g (gensym)))
        `(let ((,g ,first))
           (if ,g
               ,g
               (-or ,@rest))))))

这两个 Common Lisp 没有，但这里有几的定义会需要用到。

(defun pair (lst)
  (if (null lst)
      nil
      (cons (cons (car lst) (cadr lst))
            (pair (cddr lst)))))

(defun -pairlis (keys vals &optional alist)
  (unless (= (length keys) (length vals))
    (error "mismatched lengths"))
  (nconc (mapcar #'cons keys vals) alist))

(defmacro -pop (place)
  (multiple-value-bind (vars forms var set access)
                       (get-setf-expansion place)
    (let ((g (gensym)))
      `(let* (,@(mapcar #'list vars forms)
              (,g ,access)
              (,(car var) (cdr ,g)))
         (prog1 (car ,g)
                ,set)))))

(defmacro -prog1 (arg1 &rest args)
  (let ((g (gensym)))
    `(let ((,g ,arg1))
       ,@args
       ,g)))

(defmacro -prog2 (arg1 arg2 &rest args)
  (let ((g (gensym)))
    `(let ((,g (progn ,arg1 ,arg2)))
       ,@args
       ,g)))

(defmacro -progn (&rest args) `(let nil ,@args))

(defmacro -psetf (&rest args)
  (unless (evenp (length args))
    (error "odd number of arguments"))
  (let* ((pairs (pair args))
         (syms (mapcar #'(lambda (x) (gensym))
                       pairs)))
    `(let ,(mapcar #'list
                   syms
                   (mapcar #'cdr pairs))
       (setf ,@(mapcan #'list
                       (mapcar #'car pairs)
                       syms)))))

(defmacro -push (obj place)
  (multiple-value-bind (vars forms var set access)
                       (get-setf-expansion place)
    (let ((g (gensym)))
      `(let* ((,g ,obj)
              ,@(mapcar #'list vars forms)
              (,(car var) (cons ,g ,access)))
         ,set))))

(defun -rem (n m)
  (nth-value 1 (truncate n m)))

(defmacro -rotatef (&rest args)
  `(psetf ,@(mapcan #'list
                    args
                    (append (cdr args)
                            (list (car args))))))

(defun -second (x) (cadr x))

(defmacro -setf (&rest args)
  (if (null args)
      nil
      `(setf2 ,@args)))

(defmacro setf2 (place val &rest args)
  (multiple-value-bind (vars forms var set)
                       (get-setf-expansion place)
    `(progn
       (let* (,@(mapcar #'list vars forms)
              (,(car var) ,val))
         ,set)
       ,@(if args `((setf2 ,@args)) nil))))

(defun -signum (n)
  (if (zerop n) 0 (/ n (abs n))))

(defun -stringp (x) (typep x 'string))

(defun -tailp (x y)
  (or (eql x y)
      (and (consp y) (-tailp x (cdr y)))))

(defun -third (x) (car (cdr (cdr x))))

(defun -truncate (n &optional (d 1))
  (if (> n 0) (floor n d) (ceiling n d)))

(defmacro -typecase (arg &rest clauses)
  (let ((g (gensym)))
    `(let ((,g ,arg))
       (cond ,@(mapcar #'(lambda (cl)
                           `((typep ,g ',(car cl))
                             (progn ,@(cdr cl))))
                       clauses)))))

(defmacro -unless (arg &rest body)
  `(if (not ,arg)
       (progn ,@body)))

(defmacro -when (arg &rest body)
  `(if ,arg (progn ,@body)))

(defun -1+ (x) (+ x 1))

(defun -1- (x) (- x 1))

(defun ->= (first &rest rest)
  (or (null rest)
      (and (or (> first (car rest)) (= first (car rest)))
           (apply #'->= rest))))

在本章里，我们将使用 Lisp 来自己实现面向对象语言。这样子的程序称为嵌入式语言 (embedded language)。嵌入一个面向对象语言到 Lisp 里是一个绝佳的例子。同時作为一个 Lisp 的典型用途，並演示了面向对象的抽象是如何多自然地在 Lisp 基本的抽象上构建出来。

        17.1 继承 (Inheritance)
        17.2 多重继承 (Multiple Inheritance)
        17.3 定义对象 (Defining Objects)
        17.4 函数式语法 (Functional Syntax)
        17.5 定义方法 (Defining Methods)
        17.6 实例 (Instances)
        17.7 新的实现 (New Implementation)
        17.8 分析 (Analysis)

17.1 继承 (Inheritance)

11.10 小节解释过通用函数与消息传递的差别。

在消息传递模型里，

    对象有属性，
    并回应消息，
    并从其父类继承属性与方法。

当然了，我们知道 CLOS 使用的是通用函数模型。但本章我们只对于写一个迷你的对象系统 (minimal object system)感兴趣，而不是一个可与 CLOS 匹敌的系统，所以我们将使用消息传递模型。

我们已经在 Lisp 里看过许多保存属性集合的方法。一种可能的方法是使用哈希表来代表对象，并将属性作为哈希表的条目保存。接著可以通过 gethash 来存取每个属性：

(gethash 'color obj)

由于函数是数据对象，我们也可以将函数作为属性保存起来。这表示我们也可以有方法；要调用一个对象特定的方法，可以通过funcall 一下哈希表里的同名属性：

(funcall (gethash 'move obj) obj 10)

我们可以在这个概念上，定义一个 Smalltalk 风格的消息传递语法，

(defun tell (obj message &rest args)
  (apply (gethash message obj) obj args))

所以想要一个对象 obj 移动 10 单位，我们可以说：

(tell obj 'move 10)

事实上，纯 Lisp 唯一缺少的原料是继承。我们可以通过定义一个递归版本的 gethash 来实现一个简单版，如图 17.1 。现在仅用共 8 行代码，便实现了面向对象编程的 3 个基本元素。

(defun rget (prop obj)
  (multiple-value-bind (val in) (gethash prop obj)
    (if in
        (values val in)
        (let ((par (gethash :parent obj)))
          (and par (rget prop par))))))

(defun tell (obj message &rest args)
  (apply (rget message obj) obj args))

图 17.1：继承

让我们用这段代码，来试试本来的例子。我们创建两个对象，其中一个对象是另一个的子类：

> (setf circle-class (make-hash-table)
        our-circle   (make-hash-table)
        (gethash :parent our-circle) circle-class
        (gethash 'radius our-circle) 2)
2

circle-class 对象会持有给所有圆形使用的 area 方法。它是接受一个参数的函数，该参数为传来原始消息的对象：

> (setf (gethash 'area circle-class)
        #'(lambda (x)
            (* pi (expt (rget 'radius x) 2))))
#<Interpreted-Function BF1EF6>

现在当我们询问 our-circle 的面积时，会根据此类所定义的方法来计算。我们使用 rget 来读取一个属性，用 tell 来调用一个方法：

> (rget 'radius our-circle)
2
T
> (tell our-circle 'area)
12.566370614359173

在开始改善这个程序之前，值得停下来想想我们到底做了什么。仅使用 8 行代码，我们使纯的、旧的、无 CLOS 的 Lisp ，转变成一个面向对象语言。我们是怎么完成这项壮举的？应该用了某种秘诀，才会仅用了 8 行代码，就实现了面向对象编程。

的确有一个秘诀存在，但不是编程的奇技淫巧。这个秘诀是，Lisp 本来就是一个面向对象的语言了，甚至说，是种更通用的语言。我们需要做的事情，不过就是把本来就存在的抽象，再重新包装一下。
17.2 多重继承 (Multiple Inheritance)

到目前为止我们只有单继承 ── 一个对象只可以有一个父类。但可以通过使 parent 属性变成一个列表来获得多重继承，并重新定义 rget ，如图 17.2 所示。

在只有单继承的情况下，当我们想要从对象取出某些属性，只需要递归地延著祖先的方向往上找。如果对象本身没有我们想要属性的有关信息，可以检视其父类，以此类推。有了多重继承后，我们仍想要执行同样的搜索，但这件简单的事，却被对象的祖先可形成一个图，而不再是简单的树给复杂化了。不能只使用深度优先来搜索这个图。有多个父类时，可以有如图 17.3 所示的层级存在： a 起源于 b 及 c ，而他们都是 d 的子孙。一个深度优先（或说高度优先）的遍历结果会是 a , b , d, c , d 。而如果我们想要的属性在 d与 c 都有的话，我们会获得存在 d 的值，而不是存在 c 的值。这违反了子类可覆写父类提供缺省值的原则。

如果我们想要实现普遍的继承概念，就不应该在检查其子孙前，先检查该对象。在这个情况下，适当的搜索顺序会是 a , b , c , d 。那如何保证搜索总是先搜子孙呢？最简单的方法是用一个对象，以及按正确优先顺序排序的，由祖先所构成的列表。通过调用traverse 开始，建构一个列表，表示深度优先遍历所遇到的对象。如果任一个对象有共享的父类，则列表中会有重复元素。如果仅保存最后出现的复本，会获得一般由 CLOS 定义的优先级列表。（删除所有除了最后一个之外的复本，根据 183 页所描述的算法，规则三。）Common Lisp 函数 delete-duplicates 定义成如此作用的，所以我们只要在深度优先的基础上调用它，我们就会得到正确的优先级列表。一旦优先级列表创建完成， rget 根据需要的属性搜索第一个符合的对象。

我们可以通过利用优先级列表的优点，举例来说，一个爱国的无赖先是一个无赖，然后才是爱国者：

> (setf scoundrel           (make-hash-table)
        patriot             (make-hash-table)
        patriotic-scoundrel (make-hash-table)
        (gethash 'serves scoundrel) 'self
        (gethash 'serves patriot) 'country
        (gethash :parents patriotic-scoundrel)
                 (list scoundrel patriot))
(#<Hash-Table C41C7E> #<Hash-Table C41F0E>)
> (rget 'serves patriotic-scoundrel)
SELF
T

到目前为止，我们有一个强大的程序，但极其丑陋且低效。在一个 Lisp 程序生命周期的第二阶段，我们将这个初步框架提炼成有用的东西。
17.3 定义对象 (Defining Objects)

第一个我们需要改善的是，写一个用来创建对象的函数。我们程序表示对象以及其父类的方式，不需要给用户知道。如果我们定义一个函数来创建对象，用户将能够一个步骤就创建出一个对象，并指定其父类。我们可以在创建一个对象的同时，顺道构造优先级列表，而不是在每次当我们需要找一个属性或方法时，才花费庞大代价来重新构造。

如果我们要维护优先级列表，而不是在要用的时候再构造它们，我们需要处理列表会过时的可能性。我们的策略会是用一个列表来保存所有存在的对象，而无论何时当某些父类被改动时，重新给所有受影响的对象生成优先级列表。这代价是相当昂贵的，但由于查询比重定义父类的可能性来得高许多，我们会省下许多时间。这个改变对我们的程序的灵活性没有任何影响；我们只是将花费从频繁的操作转到不频繁的操作。

图 17.4 包含了新的代码。 λ 全局的 *objs* 会是一个包含所有当前对象的列表。函数 parents 取出一个对象的父类；相反的 (setfparents) 不仅配置一个对象的父类，也调用 make-precedence 来重新构造任何需要变动的优先级列表。这些列表与之前一样，由precedence 来构造。

用户现在不用调用 make-hash-table 来创建对象，调用 obj 来取代， obj 一步完成创建一个新对象及定义其父类。我们也重定义了rget 来利用保存优先级列表的好处。

(defvar *objs* nil)

(defun parents (obj) (gethash :parents obj))

(defun (setf parents) (val obj)
  (prog1 (setf (gethash :parents obj) val)
         (make-precedence obj)))

(defun make-precedence (obj)
  (setf (gethash :preclist obj) (precedence obj))
  (dolist (x *objs*)
    (if (member obj (gethash :preclist x))
        (setf (gethash :preclist x) (precedence x)))))

(defun obj (&rest parents)
  (let ((obj (make-hash-table)))
    (push obj *objs*)
    (setf (parents obj) parents)
    obj))

(defun rget (prop obj)
  (dolist (c (gethash :preclist obj))
    (multiple-value-bind (val in) (gethash prop c)
      (if in (return (values val in))))))

图 17.4：创建对象
17.4 函数式语法 (Functional Syntax)

另一个可以改善的空间是消息调用的语法。 tell 本身是无谓的杂乱不堪，这也使得动词在第三顺位才出现，同时代表著我们的程序不再可以像一般 Lisp 前序表达式那样阅读:

(tell (tell obj 'find-owner) 'find-owner)

我们可以使用图 17.5 所定义的 defprop 宏，通过定义作为函数的属性名称来摆脱这种 tell 语法。若选择性参数 meth? 为真的话，会将此属性视为方法。不然会将属性视为槽，而由 rget 所取回的值会直接返回。一旦我们定义了属性作为槽或方法的名字，

(defmacro defprop (name &optional meth?)
  `(progn
     (defun ,name (obj &rest args)
       ,(if meth?
          `(run-methods obj ',name args)
          `(rget ',name obj)))
     (defun (setf ,name) (val obj)
       (setf (gethash ',name obj) val))))

(defun run-methods (obj name args)
  (let ((meth (rget name obj)))
    (if meth
        (apply meth obj args)
        (error "No ~A method for ~A." name obj))))

图 17.5: 函数式语法

(defprop find-owner t)

我们就可以在函数调用里引用它，则我们的代码读起来将会再次回到 Lisp 本来那样：

(find-owner (find-owner obj))

我们的前一个例子在某种程度上可读性变得更高了：

> (progn
    (setf scoundrel           (obj)
          patriot             (obj)
          patriotic-scoundrel (obj scoundrel patriot))
    (defprop serves)
    (setf (serves scoundrel) 'self
          (serves patriot) 'country)
    (serves patriotic-scoundrel))
SELF
T

17.5 定义方法 (Defining Methods)

到目前为止，我们借由叙述如下的东西来定义一个方法：

(defprop area t)

(setf circle-class (obj))

(setf (area circle-class)
      #'(lambda (c) (* pi (expt (radius c) 2))))

(defmacro defmeth (name obj parms &rest body)
  (let ((gobj (gensym)))
    `(let ((,gobj ,obj))
       (setf (gethash ',name ,gobj)
             (labels ((next () (get-next ,gobj ',name)))
               #'(lambda ,parms ,@body))))))

(defun get-next (obj name)
  (some #'(lambda (x) (gethash name x))
        (cdr (gethash :preclist obj))))

图 17.6 定义方法。

在一个方法里，我们可以通过给对象的 :preclist 的 cdr 获得如内置 call-next-method 方法的效果。所以举例来说，若我们想要定义一个特殊的圆形，这个圆形在返回面积的过程中印出某个东西，我们可以说：

(setf grumpt-circle (obj circle-class))

(setf (area grumpt-circle)
      #'(lambda (c)
          (format t "How dare you stereotype me!~%")
          (funcall (some #'(lambda (x) (gethash 'area x))
                         (cdr (gethash :preclist c)))
                   c)))

这里 funcall 等同于一个 call-next-method 调用，但他..

图 17.6 的 defmeth 宏提供了一个便捷方式来定义方法，并使得调用下个方法变得简单。一个 defmeth 的调用会展开成一个 setf 表达式，但 setf 在一個 labels 表达式里定义了 next 作为取出下个方法的函数。这个函数与 next-method-p 类似（第 188 页「譯註: 11.7 節」），但返回的是我们可以调用的东西，同時作為 call-next-method 。 λ 前述两个方法可以被定义成：

(defmeth area circle-class (c)
  (* pi (expt (radius c) 2)))

(defmeth area grumpy-circle (c)
  (format t "How dare you stereotype me!~%")
  (funcall (next) c))

顺道一提，注意 defmeth 的定义也利用到了符号捕捉。方法的主体被插入至函数 next 是局部定义的一个上下文里。
17.6 实例 (Instances)

到目前为止，我们还没有将类别与实例做区别。我们使用了一个术语来表示两者，对象(object)。将所有的对象视为一体是优雅且灵活的，但这非常没效率。在许多面向对象应用里，继承图的底部会是复杂的。举例来说，模拟一个交通情况，我们可能有少于十个对象来表示车子的种类，但会有上百个对象来表示特定的车子。由于后者会全部共享少数的优先级列表，创建它们是浪费时间的，并且浪费空间来保存它们。

图 17.7 定义一个宏 inst ，用来创建实例。实例就像其他对象一样（现在也可称为类别），有区别的是只有一个父类且不需维护优先级列表。它们也没有包含在列表 *objs** 里。在前述例子里，我们可以说：

(setf grumpy-circle (inst circle-class))

由于某些对象不再有优先级列表，函数 rget 以及 get-next 现在被重新定义，检查这些对象的父类来取代。获得的效率不用拿灵活性交换。我们可以对一个实例做任何我们可以给其它种对象做的事，包括创建一个实例以及重定义其父类。在后面的情况里， (setfparents) 会有效地将对象转换成一个“类别”。
17.7 新的实现 (New Implementation)

我们到目前为止所做的改善都是牺牲灵活性交换而来。在这个系统的开发后期，一个 Lisp 程序通常可以牺牲些许灵活性来获得好处，这里也不例外。目前为止我们使用哈希表来表示所有的对象。这给我们带来了超乎我们所需的灵活性，以及超乎我们所想的花费。在这个小节里，我们会重写我们的程序，用简单向量来表示对象。

(defun inst (parent)
  (let ((obj (make-hash-table)))
    (setf (gethash :parents obj) parent)
    obj))

(defun rget (prop obj)
  (let ((prec (gethash :preclist obj)))
    (if prec
        (dolist (c prec)
          (multiple-value-bind (val in) (gethash prop c)
            (if in (return (values val in)))))
      (multiple-value-bind (val in) (gethash prop obj)
        (if in
            (values val in)
            (rget prop (gethash :parents obj)))))))

(defun get-next (obj name)
  (let ((prec (gethash :preclist obj)))
    (if prec
        (some #'(lambda (x) (gethash name x))
              (cdr prec))
      (get-next (gethash obj :parents) name))))

图 17.7: 定义实例

这个改变意味著放弃动态定义新属性的可能性。目前我们可通过引用任何对象，给它定义一个属性。现在当一个类别被创建时，我们会需要给出一个列表，列出该类有的新属性，而当实例被创建时，他们会恰好有他们所继承的属性。

在先前的实现里，类别与实例没有实际区别。一个实例只是一个恰好有一个父类的类别。如果我们改动一个实例的父类，它就变成了一个类别。在新的实现里，类别与实例有实际区别；它使得将实例转成类别不再可能。

在图 17.8-17.10 的代码是一个完整的新实现。图片 17.8 给创建类别与实例定义了新的操作符。类别与实例用向量来表示。表示类别与实例的向量的前三个元素包含程序自身要用到的信息，而图 17.8 的前三个宏是用来引用这些元素的：

(defmacro parents (v) `(svref ,v 0))
(defmacro layout (v) `(the simple-vector (svref ,v 1)))
(defmacro preclist (v) `(svref ,v 2))

(defmacro class (&optional parents &rest props)
  `(class-fn (list ,@parents) ',props))

(defun class-fn (parents props)
  (let* ((all (union (inherit-props parents) props))
         (obj (make-array (+ (length all) 3)
                          :initial-element :nil)))
    (setf (parents obj)  parents
          (layout obj)   (coerce all 'simple-vector)
          (preclist obj) (precedence obj))
    obj))

(defun inherit-props (classes)
  (delete-duplicates
    (mapcan #'(lambda (c)
                (nconc (coerce (layout c) 'list)
                       (inherit-props (parents c))))
            classes)))

(defun precedence (obj)
  (labels ((traverse (x)
             (cons x
                   (mapcan #'traverse (parents x)))))
    (delete-duplicates (traverse obj))))

(defun inst (parent)
  (let ((obj (copy-seq parent)))
    (setf (parents obj)  parent
          (preclist obj) nil)
    (fill obj :nil :start 3)
    obj))

图 17.8: 向量实现：创建

    parents 字段取代旧实现中，哈希表条目里 :parents 的位置。在一个类别里， parents 会是一个列出父类的列表。在一个实例里， parents 会是一个单一的父类。
    layout 字段是一个包含属性名字的向量，指出类别或实例的从第四个元素开始的设计 (layout)。
    preclist 字段取代旧实现中，哈希表条目里 :preclist 的位置。它会是一个类别的优先级列表，实例的话就是一个空表。

因为这些操作符是宏，他们全都可以被 setf 的第一个参数使用（参考 10.6 节）。

class 宏用来创建类别。它接受一个含有其基类的选择性列表，伴随著零个或多个属性名称。它返回一个代表类别的对象。新的类别会同时有自己本身的属性名，以及从所有基类继承而来的属性。

> (setf *print-array* nil
        gemo-class (class nil area)
        circle-class (class (geom-class) radius))
#<Simple-Vector T 5 C6205E>

这里我们创建了两个类别： geom-class 没有基类，且只有一个属性， area ； circle-class 是 gemo-class 的子类，并添加了一个属性， radius 。 [1]circle-class 类的设计

> (coerce (layout circle-class) 'list)
(AREA RADIUS)

显示了五个字段里，最后两个的名称。 [2]

class 宏只是一个 class-fn 的介面，而 class-fn 做了实际的工作。它调用 inherit-props 来汇整所有新对象的父类，汇整成一个列表，创建一个正确长度的向量，并适当地配置前三个字段。（ preclist 由 precedence 创建，本质上 precedence 没什么改变。）类别余下的字段设置为 :nil 来指出它们尚未初始化。要检视 circle-class 的 area 属性，我们可以：

> (svref circle-class
         (+ (position 'area (layout circle-class)) 3))
:NIL

稍后我们会定义存取函数来自动办到这件事。

最后，函数 inst 用来创建实例。它不需要是一个宏，因为它仅接受一个参数：

> (setf our-circle (inst circle-class))
#<Simple-Vector T 5 C6464E>

比较 inst 与 class-fn 是有益学习的，它们做了差不多的事。因为实例仅有一个父类，不需要决定它继承什么属性。实例可以仅拷贝其父类的设计。它也不需要构造一个优先级列表，因为实例没有优先级列表。创建实例因此与创建类别比起来来得快许多，因为创建实例在多数应用里比创建类别更常见。

(declaim (inline lookup (setf lookup)))

(defun rget (prop obj next?)
  (let ((prec (preclist obj)))
    (if prec
        (dolist (c (if next? (cdr prec) prec) :nil)
          (let ((val (lookup prop c)))
            (unless (eq val :nil) (return val))))
        (let ((val (lookup prop obj)))
          (if (eq val :nil)
              (rget prop (parents obj) nil)
              val)))))

(defun lookup (prop obj)
  (let ((off (position prop (layout obj) :test #'eq)))
    (if off (svref obj (+ off 3)) :nil)))

(defun (setf lookup) (val prop obj)
  (let ((off (position prop (layout obj) :test #'eq)))
    (if off
        (setf (svref obj (+ off 3)) val)
        (error "Can't set ~A of ~A." val obj))))

图 17.9: 向量实现：存取

现在我们可以创建所需的类别层级及实例，以及需要的函数来读写它们的属性。图 17.9 的第一个函数是 rget 的新定义。它的形状与图 17.7 的 rget 相似。条件式的两个分支，分别处理类别与实例。

    若对象是一个类别，我们遍历其优先级列表，直到我们找到一个对象，其中欲找的属性不是 :nil 。如果没有找到，返回 :nil。
    若对象是一个实例，我们直接查找属性，并在没找到时递回地调用 rget 。

rget 与 next? 新的第三个参数稍后解释。现在只要了解如果是 nil ， rget 会像平常那样工作。

函数 lookup 及其反相扮演著先前 rget 函数里 gethash 的角色。它们使用一个对象的 layout ，来取出或设置一个给定名称的属性。这条查询是先前的一个复本：

> (lookup 'area circle-class)
:NIL

由于 lookup 的 setf 也定义了，我们可以给 circle-class 定义一个 area 方法，通过：

(setf (lookup 'area circle-class)
      #'(lambda (c)
          (* pi (expt (rget 'radius c nil) 2))))

在这个程序里，和先前的版本一样，没有特别区别出方法与槽。一个“方法”只是一个字段，里面有着一个函数。这将很快会被一个更方便的前端所隐藏起来。

(declaim (inline run-methods))

(defmacro defprop (name &optional meth?)
  `(progn
     (defun ,name (obj &rest args)
       ,(if meth?
            `(run-methods obj ',name args)
            `(rget ',name obj nil)))
     (defun (setf ,name) (val obj)
       (setf (lookup ',name obj) val))))

(defun run-methods (obj name args)
  (let ((meth (rget name obj nil)))
    (if (not (eq meth :nil))
        (apply meth obj args)
        (error "No ~A method for ~A." name obj))))

(defmacro defmeth (name obj parms &rest body)
  (let ((gobj (gensym)))
    `(let ((,gobj ,obj))
       (defprop ,name t)
       (setf (lookup ',name ,gobj)
             (labels ((next () (rget ,gobj ',name t)))
               #'(lambda ,parms ,@body))))))

图 17.10: 向量实现：宏介面

图 17.10 包含了新的实现的最后部分。这个代码没有给程序加入任何威力，但使程序更容易使用。宏 defprop 本质上没有改变；现在仅调用 lookup 而不是 gethash 。与先前相同，它允许我们用函数式的语法来引用属性：

> (defprop radius)
(SETF RADIUS)
> (radius our-circle)
:NIL
> (setf (radius our-circle) 2)
2

如果 defprop 的第二个选择性参数为真的话，它展开成一个 run-methods 调用，基本上也没什么改变。

最后，函数 defmeth 提供了一个便捷方式来定义方法。这个版本有三件新的事情：它隐含了 defprop ，它调用 lookup 而不是gethash ，且它调用 regt 而不是 278 页的 get-next (译注: 图 17.7 的 get-next )来获得下个方法。现在我们理解给 rget 添加额外参数的理由。它与 get-next 非常相似，我们同样通过添加一个额外参数，在一个函数里实现。若这额外参数为真时， rget 取代get-next 的位置。

现在我们可以达到先前方法定义所有的效果，但更加清晰：

(defmeth area circle-class (c)
  (* pi (expt (radius c) 2)))

注意我们可以直接调用 radius 而无须调用 rget ，因为我们使用 defprop 将它定义成一个函数。因为隐含的 defprop 由 defmeth实现，我们也可以调用 area 来获得 our-circle 的面积：

> (area our-circle)
12.566370614359173

17.8 分析 (Analysis)

我们现在有了一个适合撰写实际面向对象程序的嵌入式语言。它很简单，但就大小来说相当强大。而在典型应用里，它也会是快速的。在一个典型的应用里，操作实例应比操作类别更常见。我们重新设计的重点在于如何使得操作实例的花费降低。

在我们的程序里，创建类别既慢且产生了许多垃圾。如果类别不是在速度为关键考量时创建，这还是可以接受的。会需要速度的是存取函数以及创建实例。这个程序里的没有做编译优化的存取函数大约与我们预期的一样快。 λ 而创建实例也是如此。且两个操作都没有用到构造 (consing)。除了用来表达实例的向量例外。会自然的以为这应该是动态地配置才对。但我们甚至可以避免动态配置实例，如果我们使用像是 13.4 节所提出的策略。

我们的嵌入式语言是 Lisp 编程的一个典型例子。只不过是一个嵌入式语言就可以是一个例子了。但 Lisp 的特性是它如何从一个小的、受限版本的程序，进化成一个强大但低效的版本，最终演化成快速但稍微受限的版本。

Lisp 恶名昭彰的缓慢不是 Lisp 本身导致（Lisp 编译器早在 1980 年代就可以产生出与 C 编译器一样快的代码），而是由于许多程序员在第二个阶段就放弃的事实。如同 Richard Gabriel 所写的，

    要在 Lisp 撰写出性能极差的程序相当简单；而在 C 这几乎是不可能的。 λ

这完全是一个真的论述，但也可以解读为赞扬或贬低 Lisp 的论点：

    通过牺牲灵活性换取速度，你可以在 Lisp 里轻松地写出程序；在 C 语言里，你没有这个选择。
    除非你优化你的 Lisp 代码，不然要写出缓慢的软件根本易如反掌。

你的程序属于哪一种解读完全取决于你。但至少在开发初期，Lisp 使你有牺牲执行速度来换取时间的选择。

有一件我们示例程序没有做的很好的事是，它不是一个称职的 CLOS 模型（除了可能没有说明难以理解的 call-next-method 如何工作是件好事例外）。如大象般庞大的 CLOS 与这个如蚊子般微小的 70 行程序之间，存在多少的相似性呢？当然，这两者的差别是出自于教育性，而不是探讨有多相似。首先，这使我们理解到“面向对象”的广度。我们的程序比任何被称为是面向对象的都来得强大，而这只不过是 CLOS 的一小部分威力。

我们程序与 CLOS 不同的地方是，方法是属于某个对象的。这个方法的概念使它们与对第一个参数做派发的函数相同。而当我们使用函数式语法来调用方法时，这看起来就跟 Lisp 的函数一样。相反地，一个 CLOS 的通用函数，可以派发它的任何参数。一个通用函数的组件称为方法，而若你将它们定义成只对第一个参数特化，你可以制造出它们是某个类或实例的方法的错觉。但用面向对象编程的消息传递模型来思考 CLOS 最终只会使你困惑，因为 CLOS 凌驾在面向对象编程之上。

CLOS 的缺点之一是它太庞大了，并且 CLOS 费煞苦心的隐藏了面向对象编程，其实只不过是改写 Lisp 的这个事实。本章的例子至少阐明了这一点。如果我们满足于旧的消息传递模型，我们可以用一页多一点的代码来实现。面向对象编程不过是 Lisp 可以做的小事之一而已。更发人深省的问题是，Lisp 除此之外还能做些什么？

脚注

[1] | 当类别被显示时， *print-array* 应当是 nil 。 任何类别的 preclist 的第一个元素都是类别本身，所以试图显示类别的内部结构会导致一个无限循环。

[2] | 这个向量被 coerced 成一个列表，只是为了看看里面有什么。有了 *print-array* 被设成 nil ，一个向量的内容应该不会显示出来。

接下来三章提供了大量的 Lisp 程序例子。选择这些例子来说明那些较长的程序所采取的形式，和 Lisp 所擅长解决的问题类型。

在这一章中我们将要写一个基于一组 if-then 规则的推论程序。这是一个经典的例子 —— 不仅在于其经常出现在教科书上，还因为它反映了 Lisp 作为一个“符号计算”语言的本意。这个例子散发着很多早期 Lisp 程序的气息。

        15.1 目标 (The Aim)
        15.2 匹配 (Matching)
        15.3 回答查询 (Answering Queries)
        15.4 分析 (Analysis)

15.1 目标 (The Aim)

在这个程序中，我们将用一种熟悉的形式来表示信息：包含单个判断式，以及跟在之后的零个或多个参数所组成的列表。要表示 Donald 是 Nancy 的家长，我们可以这样写：

(parent donald nancy)

事实上，我们的程序是要表示一些从已有的事实作出推断的规则。我们可以这样来表示规则：

(<- head body)

其中， head 是 那么...部分 (then-part)， body 是 如果...部分 (if-part)。在 head 和 body 中我们使用以问号为前缀的符号来表示变量。所以下面这个规则：

(<- (child ?x ?y) (parent ?y ?x))

表示：如果 y 是 x 的家长，那么 x 是 y 的孩子；更恰当地说，我们可以通过证明 (parent y x) 来证明 (child x y) 的所表示的事实。

可以把规则中的 body 部分(if-part) 写成一个复杂的表达式，其中包含 and , or 和 not 等逻辑操作。所以当我们想要表达 “如果 x 是 y 的家长，并且 x 是男性，那么 x 是 y 的父亲” 这样的规则，我们可以写：

(<- (father ?x ?y) (and (parent ?x ?y) (male ?x)))

一些规则可能依赖另一些规则所产生的事实。比如，我们写的第一个规则是为了证明 (child x y) 的事实。如果我们定义如下规则：

(<- (daughter ?x ?y) (and (child ?x ?y) (female ?x)))

然后使用它来证明 (daughter x y) 可能导致程序使用第一个规则去证明 (child x y) 。

表达式的证明可以回溯任意数量的规则，只要它最终结束于给出的已知事实。这个过程有时候被称为反向链接 (backward-chaining)。之所以说 反向 (backward) 是因为这一类推论先考虑 head 部分，这是为了在继续证明 body 部分之前检查规则是否有效。链接 (chaining) 来源于规则之间的依赖关系，从我们想要证明的内容到我们的已知条件组成一个链接 (尽管事实上它更像一棵树)。 λ
15.2 匹配 (Matching)

我们需要有一个函数来做模式匹配以完成我们的反向链接 (back-chaining) 程序，这个函数能够比较两个包含变量的列表，它会检查在给变量赋值后是否可以使两个列表相等。举例，如果 ?x 和 ?y 是变量，那么下面两个列表：

(p ?x ?y c ?x)
(p  a  b c  a)

当 ?x = a 且 ?y = b 时匹配，而下面两个列表：

(p ?x b ?y a)
(p ?y b  c a)

当 ?x = ?y = c 时匹配。

我们有一个 match 函数，它接受两棵树，如果这两棵树能匹配，则返回一个关联列表（assoc-list）来显示他们是如何匹配的：

(defun match (x y &optional binds)
  (cond
   ((eql x y) (values binds t))
   ((assoc x binds) (match (binding x binds) y binds))
   ((assoc y binds) (match x (binding y binds) binds))
   ((var? x) (values (cons (cons x y) binds) t))
   ((var? y) (values (cons (cons y x) binds) t))
   (t
    (when (and (consp x) (consp y))
      (multiple-value-bind (b2 yes)
                           (match (car x) (car y) binds)
        (and yes (match (cdr x) (cdr y) b2)))))))

(defun var? (x)
  (and (symbolp x)
       (eql (char (symbol-name x) 0) #\?)))

(defun binding (x binds)
  (let ((b (assoc x binds)))
    (if b
        (or (binding (cdr b) binds)
            (cdr b)))))

图 15.1: 匹配函数。

> (match '(p a b c a) '(p ?x ?y c ?x))
((?Y . B) (?X . A))
T
> (match '(p ?x b ?y a) '(p ?y b c a))
((?Y . C) (?X . ?Y))
T
> (match '(a b c) '(a a a))
NIL

当 match 函数逐个元素地比较它的参数时候，它把 binds 参数中的值分配给变量，这被称为绑定 (bindings)。如果成功匹配，match 函数返回生成的绑定；否则，返回 nil 。当然并不是所有成功的匹配都会产生绑定，我们的 match 函数就像 gethash 函数那样返回第二个值来表明匹配成功：

> (match '(p ?x) '(p ?x))
NIL
T

如果 match 函数像上面那样返回 nil 和 t ，表明这是一个没有产生绑定的成功匹配。下面用中文来描述 match 算法是如何工作的：

    如果 x 和 y 在 eql 上相等那么它们匹配；否则，
    如果 x 是一个已绑定的变量，并且绑定匹配 y ，那么它们匹配；否则，
    如果 y 是一个已绑定的变量，并且绑定匹配 x ，那么它们匹配；否则，
    如果 x 是一个未绑定的变量，那么它们匹配，并且为 x 建立一个绑定；否则，
    如果 y 是一个未绑定的变量，那么它们匹配，并且为 y 建立一个绑定；否则，
    如果 x 和 y 都是 cons ，并且它们的 car 匹配，由此产生的绑定又让 cdr 匹配，那么它们匹配。

下面是一个例子，按顺序来说明以上六种情况：

> (match '(p ?v  b ?x  d (?z ?z))
         '(p  a ?w  c ?y ( e  e))
         '((?v . a) (?w . b)))
((?Z . E) (?Y . D) (?X . C) (?V . A) (?W . B))
T

match 函数通过调用 binding 函数在一个绑定列表中寻找变量（如果有的话）所关联的值。这个函数必须是递归的，因为有这样的情况 “匹配建立一个绑定列表，而列表中变量只是间接关联到它的值： ?x 可能被绑定到一个包含 (?x . ?y) 和 (?y . a) 的列表”：

> (match '(?x a) '(?y ?y))
((?Y . A) (?X . ?Y))
T

先匹配 ?x 和 ?y ，然后匹配 ?y 和 a ，我们间接确定 ?x 是 a 。
15.3 回答查询 (Answering Queries)

在介绍了绑定的概念之后，我们可以更准确的说一下我们的程序将要做什么：它得到一个可能包含变量的表达式，根据我们给定的事实和规则返回使它正确的所有绑定。比如，我们只有下面这个事实：

(parent donald nancy)

然后我们想让程序证明：

(parent ?x ?y)

它会返回像下面这样的表达：

(((?x . donald) (?y . nancy)))

它告诉我们只有一个可以让这个表达式为真的方法： ?x 是 donald 并且 ?y 是 nancy 。

在通往目标的路上，我们已经有了一个的重要部分：一个匹配函数。 下面是用来定义规则的一段代码：

(defvar *rules* (make-hash-table))

(defmacro <- (con &optional ant)
  `(length (push (cons (cdr ',con) ',ant)
                 (gethash (car ',con) *rules*))))

图 15.2 定义规则

规则将被包含于一个叫做 *rules* 的哈希表，通过头部 (head) 的判断式构建这个哈系表。这样做加强了我们无法使用判断式中的变量的限制。虽然我们可以通过把所有这样的规则放在分离的列表中来消除限制，但是如果这样做，当我们需要证明某件事的时侯不得不和每一个列表进行匹配。

我们将要使用同一个宏 <- 去定义事实 (facts)和规则 (rules)。一个事实将被表示成一个没有 body 部分的规则。这和我们对规则的定义保持一致。一个规则告诉我们你可以通过证明 body 部分来证明 head 部分，所以没有 body 部分的规则意味着你不需要通过证明任何东西来证明 head 部分。这里有两个对应的例子：

> (<- (parent donald nancy))
1
> (<- (child ?x ?y) (parent ?y ?x))
1

调用 <- 返回的是给定判断式下存储的规则数量；用 length 函数来包装 push 能使我们免于看到顶层中的一大堆返回值。

下面是我们的推论程序所需的大多数代码：

(defun prove (expr &optional binds)
  (case (car expr)
    (and (prove-and (reverse (cdr expr)) binds))
    (or  (prove-or (cdr expr) binds))
    (not (prove-not (cadr expr) binds))
    (t   (prove-simple (car expr) (cdr expr) binds))))

(defun prove-simple (pred args binds)
  (mapcan #'(lambda (r)
              (multiple-value-bind (b2 yes)
                                   (match args (car r)
                                          binds)
                (when yes
                  (if (cdr r)
                      (prove (cdr r) b2)
                      (list b2)))))
          (mapcar #'change-vars
                  (gethash pred *rules*))))

(defun change-vars (r)
  (sublis (mapcar #'(lambda (v) (cons v (gensym "?")))
                  (vars-in r))
          r))

(defun vars-in (expr)
  (if (atom expr)
      (if (var? expr) (list expr))
    (union (vars-in (car expr))
           (vars-in (cdr expr)))))

图 15.3: 推论。

上面代码中的 prove 函数是推论进行的枢纽。它接受一个表达式和一个可选的绑定列表作为参数。如果表达式不包含逻辑操作，它调用 prove-simple 函数，前面所说的链接 (chaining)正是在这个函数里产生的。这个函数查看所有拥有正确判断式的规则，并尝试对每一个规则的 head 部分和它想要证明的事实做匹配。对于每一个匹配的 head ，使用匹配所产生的新的绑定在 body 上调用 prove。对 prove 的调用所产生的绑定列表被 mapcan 收集并返回：

> (prove-simple 'parent '(donald nancy) nil)
(NIL)
> (prove-simple 'child '(?x ?y) nil)
(((#:?6 . NANCY) (#:?5 . DONALD) (?Y . #:?5) (?X . #:?6)))

以上两个返回值指出有一种方法可以证明我们的问题。（一个失败的证明将返回 nil。）第一个例子产生了一组空的绑定，第二个例子产生了这样的绑定： ?x 和 ?y 被（间接）绑定到 nancy 和 donald 。

顺便说一句，这是一个很好的例子来实践 2.13 节提出的观点。因为我们用函数式的风格来写这个程序，所以可以交互式地测试每一个函数。

第二个例子返回的值里那些 gensyms 是怎么回事？如果我们打算使用含有变量的规则，我们需要避免两个规则恰好包含相同的变量。如果我们定义如下两条规则：

(<- (child ?x ?y) (parent ?y ?x))

(<- (daughter ?y ?x) (and (child ?y ?x) (female ?y)))

第一条规则要表达的意思是：对于任何的 x 和 y ， 如果 y 是 x 的家长，则 x 是 y 的孩子。第二条则是：对于任何的 x 和 y ， 如果 y 是 x 的孩子并且 y 是女性，则 y 是 x 的女儿。在每一条规则内部，变量之间的关系是显著的，但是两条规则使用了相同的变量并非我们刻意为之。

如果我们使用上面所写的规则，它们将不会按预期的方式工作。如果我们尝试证明“ a 是 b 的女儿”，匹配到第二条规则的 head 部分时会将 a 绑定到 ?y ，将 b 绑定到 ?x。我们无法用这样的绑定匹配第一条规则的 head 部分：

> (match '(child ?y ?x)
         '(child ?x ?y)
         '((?y . a) (?x . b)))
NIL

为了保证一条规则中的变量只表示规则中各参数之间的关系，我们用 gensyms 来代替规则中的所有变量。这就是 change-vars 函数的目的。一个 gensym 不可能在另一个规则中作为变量出现。但是因为规则可以是递归的，我们必须防止出现一个规则和自身冲突的可能性，所以在定义和使用一个规则时都要调用 chabge-vars 函数。

现在只剩下定义用以证明复杂表达式的函数了。下面就是需要的函数：

(defun prove-and (clauses binds)
  (if (null clauses)
      (list binds)
      (mapcan #'(lambda (b)
                  (prove (car clauses) b))
              (prove-and (cdr clauses) binds))))

(defun prove-or (clauses binds)
  (mapcan #'(lambda (c) (prove c binds))
          clauses))

(defun prove-not (clause binds)
  (unless (prove clause binds)
    (list binds)))

图 15.4 逻辑操作符 (Logical operators)

操作一个 or 或者 not 表达式是非常简单的。操作 or 时，我们提取在 or 之间的每一个表达式返回的绑定。操作 not 时，当且仅当在 not 里的表达式产生 none 时，返回当前的绑定。

prove-and 函数稍微复杂一点。它像一个过滤器，它用之后的表达式所建立的每一个绑定来证明第一个表达式。这将导致 and 里的表达式以相反的顺序被求值。除非调用 prove 中的 prove-and 函数则会先逆转它们。

现在我们有了一个可以工作的程序，但它不是很友好。必须要解析 prove-and 返回的绑定列表是令人厌烦的，它们会变得更长随着规则变得更加复杂。下面有一个宏来帮助我们更愉快地使用这个程序：

(defmacro with-answer (query &body body)
  (let ((binds (gensym)))
    `(dolist (,binds (prove ',query))
       (let ,(mapcar #'(lambda (v)
                         `(,v (binding ',v ,binds)))
                     (vars-in query))
         ,@body))))

图 15.5 介面宏 (Interface macro)

它接受一个 query （不被求值）和若干表达式构成的 body 作为参数，把 query 所生成的每一组绑定的值赋给 query 中对应的模式变量，并计算 body 。

> (with-answer (parent ?x ?y)
    (format t "~A is the parent of ~A.~%" ?x ?y))
DONALD is the parent of NANCY.
NIL

这个宏帮我们做了解析绑定的工作，同时为我们在程序中使用 prove 提供了一个便捷的方法。下面是这个宏展开的情况：

(with-answer (p ?x ?y)
  (f ?x ?y))

;;将被展开成下面的代码

(dolist (#:g1 (prove '(p ?x ?y)))
  (let ((?x (binding '?x #:g1))
        (?y (binding '?y #:g1)))
    (f ?x ?y)))

图 15.6: with-answer 调用的展开式

下面是使用它的一个例子：

(<- (parent donald nancy))
(<- (parent donald debbie))
(<- (male donald))
(<- (father ?x ?y) (and (parent ?x ?y) (male ?x)))
(<- (= ?x ?y))
(<- (sibling ?x ?y) (and (parent ?z ?x)
                         (parent ?z ?y)
                         (not (= ?x ?y))))

;;我们可以像下面这样做出推论

> (with-answer (father ?x ?y)
    (format t "~A is the father of ~A.~%" ?x ?y))
DONALD is the father of DEBBIE.
DONALD is the father of NANCY.
NIL
> (with-answer (sibling ?x ?y))
    (format t "~A is the sibling of ~A.~%" ?x ?y))
DEBBLE is the sibling of NANCY.
NANCY is the  sibling of DEBBIE.
NIL

图 15.7: 使用中的程序
15.4 分析 (Analysis)

看上去，我们在这一章中写的代码，是用简单自然的方式去实现这样一个程序。事实上，它的效率非常差。我们在这里是其实是做了一个解释器。我们能够把这个程序做得像一个编译器。

这里做一个简单的描述。基本的思想是把整个程序打包到两个宏 <- 和 with-answer ，把已有程序中在运行期做的多数工作搬到宏展开期（在 10.7 节的 avg 可以看到这种构思的雏形) 用函数取代列表来表示规则，我们不在运行时用 prove 和 prove-and 这样的函数来解释表达式，而是用相应的函数把表达式转化成代码。当一个规则被定义的时候就有表达式可用。为什么要等到使用的时候才去分析它呢？这同样适用于和 <- 调用了相同的函数来进行宏展开的 with-answer 。

听上去好像比我们已经写的这个程序复杂很多，但其实可能只是长了两三倍。想要学习这种技术的读者可以看 On Lisp 或者Paradigms of Artificial Intelligence Programming ，这两本书有一些使用这种风格写的示例程序。