Interpreting LISP

Gary D. Knott Civilized Software Inc., Silver Spring, Maryland, USA ISBN-13 (pbk): 978-1-4842-2706-0 ISBN-13 (electronic): 978-1-4842-2707-7 DOI 10.1007/978-1-4842-2707-7 国会图书馆控制号: 2017944089 版权 © 2017 by Gary D. Knott 本书受版权保护. 出版商保留所有权利, 无论是涉及全部还是部分材料, 特别是翻译, 重印, 插图重用, 朗诵, 广播, 缩微胶片或其他任何物理方式的复制, 以及现在已知或将来开发的电子改编, 计算机软件, 或通过类似或不同方法进行传输或信息存储和检索的权利. 本书中可能出现商标名称, 徽标和图像. 我们使用这些名称, 徽标和图像仅为编辑目的, 并为了商标所有者的利益, 无意侵犯商标权, 而不是在每次出现商标名称, 徽标或图像时都使用商标符号. 本出版物中使用商号, 商标, 服务标志和类似术语, 即使未作标识, 也不应被视为对其是否受专有权约束的意见表达. 虽然本书中的建议和信息在出版之日被认为是真实和准确的, 但作者, 编辑或出版商均不对可能出现的任何错误或遗漏承担任何法律责任. 出版商对其中包含的材料不作任何明示或暗示的保证. 封面图片由 Freepik 设计 常务董事: Welmoed Spahr 编辑总监: Todd Green 采购编辑: Steve Anglin 开发编辑: Matthew Moodie 技术审阅: Daniel Holden 协调编辑: Mark Powers 文字编辑: Mary Bearden 由 Springer Science+Business Media New York, 233 Spring Street, 6th Floor, New York, NY 10013 在全球图书贸易中分销. 电话 1-800-SPRINGER, 传真 (201) 348-4505, 电子邮件 orders-ny@springer-sbm.com, 或访问 www.springeronline.com. Apress Media, LLC 是加利福尼亚州的 LLC, 其唯一成员 (所有者) 是 Springer Science + Business Media Finance Inc (SSBM Finance Inc). SSBM Finance Inc 是特拉华州的公司. 有关翻译信息, 请发送电子邮件至 rights@apress.com, 或访问 http://www.apress.com/rights-permissions. Apress 书籍可用于学术, 企业或促销用途的批量购买. 大多数书籍也提供电子书版本和许可证. 更多信息, 请参考我们的印刷和电子书批量销售网页 http://www.apress.com/bulk-sales. 本书中作者引用的任何源代码或其他补充材料均可通过该书的产品页面在 GitHub 上向读者提供, 网址为 www.apress.com/9781484227060. 更多详细信息, 请访问 http://www.apress.com/source-code. 使用无酸纸印刷

• 关于作者 …………………………………………………………. vii
• 关于技术审阅者 ………………………………………………….. ix
• 致谢 …………………………………………………………….. xi
• 引言 …………………………………………………………… xiii
• 第1章: LISP …………………………………………………………. 1
• 第2章: 原子表和数字表 …………………………………………….. 3
• 第3章: 求值 …………………………………………………………. 9
• 第4章: 一些函数和特殊形式 ………………………………………… 11
• 第5章: S-表达式 …………………………………………………… 17
• 第6章: 类型指针 …………………………………………………… 19
• 第7章: 图形表示法 …………………………………………………. 23
• 第8章: 更多函数 …………………………………………………… 27
• 第9章: 参数和结果是类型指针 ………………………………………. 31
• 第10章: 列表表示法 ……………………………………………….. 35
• 第11章: 更多特殊形式 ……………………………………………… 39
• 第12章: 定义函数: λ-表达式 ……………………………………….. 43
• 第13章: 更多函数 …………………………………………………. 47
• 第14章: 定义特殊形式 ……………………………………………… 53
• 第15章: Label 特殊形式 ……………………………………………. 57
• 第16章: Quote 宏 …………………………………………………… 59
• 第17章: 更多函数 …………………………………………………. 61
• 第18章: 关于类型指针的更多信息 …………………………………… 63
• 第19章: 将实际值绑定到形式参数 …………………………………… 67
• 第20章: 最小 LISP …………………………………………………. 75
• 第21章: 更多函数 …………………………………………………. 77
• 第22章: 输入和输出 ……………………………………………….. 83
• 第23章: 属性列表 …………………………………………………. 85
• 第24章: LISP 有什么用? ……………………………………………. 91
• 第25章: 符号微分 …………………………………………………. 93
• 第26章: 博弈 …………………………………………………….. 101
• 第27章: LISP 解释器程序 …………………………………………. 109
  • LISP in C ………………………………………………………. 110
• 第28章: 垃圾回收 …………………………………………………. 135
• 第29章: lispinit 文件, linuxenv.h 文件和 Makefile 文件 ………………… 139
• 参考文献 ………………………………………………………….. 145
• 索引 ……………………………………………………………… 147

Gary D. Knott, PhD, 是 Civilized Software Inc. 的创始人/CEO, 该公司是数学和统计建模软件 MLAB 的制造商.

Daniel Holden 是一位知名的 C 程序员, 对创意编程项目感兴趣, 也是 C 编程书籍 《Build Your Own Lisp》 的作者. 白天, 他作为研究员, 使用机器学习开发用于自动角色动画的工具; 晚上, 他喜欢写短篇小说, 创作数字艺术和开发游戏.

我感谢读者们在塑造和调试这份材料方面所提供的帮助, 此外, 还要感谢 Apress 的团队, Steve Anglin, Mark Powers, 和 Matthew Moodie, 以及 SPi Global 的团队, 包括 Baby Gopalakrishnan, Raagai Priya Chandrasekaran 等人.

我写这本小书是为了帮助数据结构课程的学生学习 LISP. 因此, 本书详细描述了 LISP 函数所操作的数据结构. LISP 的核心依赖于一种链表数据结构, 这是随着 LISP 的出现而普及 (如果不是首创) 的标志性特性之一. 这种数据结构以及其他一些结构, 特别是哈希表, 也被用于构建 LISP 解释器. 本书旨在实现几个目标. 首先, 它旨在作为对 LISP 语言温和而精确的介绍; 其次, 它旨在展示一个用 C 语言编写的非凡的 LISP 解释器, 该解释器提供了关于通用编程和解释器编写的几个“教训”; 第三, 它旨在介绍一些 LISP 编程的“风味”, 这在某些方面与 C 这样的过程式语言编程有很大不同, 在 C 语言中, 程序是逐条语句构建的. 所有这些都将在一个简短的篇幅内完成, 没有过多且可能冗长的阐述. 本书并非旨在让读者准备好使用某个特定的 LISP 系统, 而是侧重于 LISP 对编程学科所做的文化贡献. LISP 的学习, 再加上对一个用于展示的 LISP 解释器的学习, 对于编程语言和计算机体系结构以及数据结构领域的学生来说具有特殊的意义. 事实上, 这本书对于计算机科学所有领域的学生, 以及各种领域的自学者, 专业程序员和计算机爱好者都将非常有用. 尽管假定读者具有一定的“编程成熟度”, 但有毅力的读者可以通过并行的学习和实践来发展这样的基础. 通过并行的学习, 这本书旨在让从高中生到专业程序员的广泛兴趣读者都能理解. 我非常希望学生们能用这本书来帮助他们理解 LISP 以及 LISP 解释器是如何制作的, 从而理解为任何语言构建解释器所涉及的概念. 最好的方法是编译并运行 C LISP 解释器, 然后通过以各种方式修改它来进行实验. 我希望这本书能帮助所有使用它的人培养对这种优雅编程语言的审美欣赏. 最后, 由于本书中提供的 LISP 解释器 C 程序是一个需要仔细研究才能理解的非凡程序, 这本书, 连同一本关于 C 的书, 也应该有助于学习或重新学习 C 语言那奇妙的“瑞士军刀”般的编程.

LISP 是一种有趣的编程语言, 构建 LISP 解释器所涉及的思想也同样有趣 [McC79]. 本书包含了对 LISP 的介绍, 同时还包含了数据结构细节和一个可工作的 LISP 解释器的显式代码.

LISP 是一种具有独特功能的编程语言. 它在概念上是交互式的. 输入命令逐一给出, 相关结果值被打印出来. LISP 是一种应用式语言, 意味着它主要由函数应用命令组成. 除了函数应用, 还有赋值命令和条件命令, 它们以函数形式编写. 通常, 迭代由递归取代.

LISP 函数可以操作的数据值包括实数. 因此, 像 \(1.5 + 2\) 这样的表达式是一个 LISP 语句, 意思是: 打印出将 + 应用于参数 1.5 和 2 的结果. 在 LISP 中, 函数应用语句总是写成前缀形式, 例如, `+(1.5, 2)`. 此外, 我们不写 \(f(x, y)\) 来表示函数 \(f\) 应用于参数 \(x\) 和 \(y\) 的结果, 而是在 LISP 中写成 `(f x y)`, 所以 `(+ 1.5 2)` 是 \(1.5 + 2\) 的 LISP 形式. 最后, LISP 中的函数通常由标识符名称而不是特殊符号指定. 因此, 在 LISP 中计算 \(1.5 + 2\) 的正确方法是输入表达式 `(PLUS 1.5 2)`, 这确实会导致打印出 3.5. 像 `(PLUS 1.5 2)` 这样的表达式被称为函数调用表达式. LISP 函数还可以操作对象列表; 事实上, 首字母缩写 LISP 源于短语 LISt Processing.

LISP 通常通过一个名为 LISP 解释器的解释程序来实现. 这个程序读取作为输入输入的 LISP 表达式, 对它们进行求值, 并打印出结果. 一些表达式还指定了会改变状态的副作用. 我们将在下文中描述一个特定的 LISP 解释器是如何构建的, 同时也会描述 LISP 本身.

LISP 有多种方言, 包括扩展形式, 它们丰富了函数集合并增加了额外的数据类型. 我们将专注于 LISP 的共同核心, 但这里给出的一些定义并非普遍适用, 在少数情况下, 它们是本文介绍的 LISP 版本 (GOVOL)所特有的. 这里介绍的 GOVOL LISP 方言与原始的 LISP 1.5 [MIT62] 相似; 它不像当前最常用的 LISP 变体那样复杂, 但它包含了这些更复杂变体的所有基本特征, 因此你在这本书中学到的知识将立即适用于几乎每一种 LISP 方言. (查阅编程语言 Jovial 来了解 GOVOL 的含义.)

LISP 解释器程序维护几个通用数据结构. 第一个数据结构是一个符号表, 其中包含每个命名数据对象的条目. 这些命名数据对象被称为普通原子 (ordinary atoms), 普通原子的符号表被称为原子表 (atom table). (术语 atom 是历史性的; 这是 LISP 的设计者 John McCarthy [McC60][MIT62] 使用的术语.) 原子表在概念上具有以下形式:

原子表有 \(n\) 个条目, 其中 \(n\) 是某个相当大的值, 目前未指定. 原子表中的每个条目都有一个 name 字段, 用于存放原子名称, 例如: "PLUS" 或 "AXY". 每个条目还有一个 value 字段, 用于存放原子的当前值, 以及一个关联的 type 字段, 这是一个整数代码, 用于指定原子值的 datatype. 例如, 原子 "PLUS" 的值是一个内置函数, 由整数类型码 10 分类. 每个原子表条目还有一个 plist 字段和一个 bindlist 字段, 我将在后面讨论. (字段 (field) 只是一个术语, 指的是可以存储二进制值的一系列位; 通常这些位字段不是完整的计算机“字”. 当然, 二进制值包括计算机内部处理的所有内容.) 第二个数据结构是一个简单的表, 称为数字表 (number table), 其中存储浮点数. 每个输入的数字和每个计算出的数字都存储在数字表中, 至少在需要它存在的时间段内是这样. 数字表在概念上具有以下形式:

由于浮点数包含大量的整数, 因此除了可能为了速度之外, 没有 (直接的) 理由在 LISP 中将整数作为一种单独的数据类型提供.

从现在开始, 我们用 \(v[x]\) 来表示原子或函数调用表达式 x 的值. 这里定义的求值运算符 v, 基本上体现在 LISP 解释器程序中. 当 x 是一个普通原子时, \(v[x]\) 是 x 的原子表条目中 value 字段指定的数据对象. 这个数据对象的类型由原子 x 的 type 字段中的类型码给出. 当 x 是一个数字原子时, \(v[x] = x\).

我们现在可以陈述一些 LISP 的内置函数和特殊形式. 我们不描述当各种“非法”输入被求值时得到的结果. 这种行为根据 LISP 解释器的实现而变化. 以下是 LISP 中的特殊形式和函数的列表:

• SETQ: 带有副作用的特殊形式 \(v[(\text{SETQ } x y)] = v[x]\), 在 \(v[x]\) 作为初始副作用被赋值为 \(v[y]\) 之后. x 必须是一个普通原子, 必然带有一个非数字名称. x 的值的类型被改变为 \(v[y]\) 的类型, 但在 \(v[y]\) 是一个未命名函数或未命名特殊形式的情况下有特殊修改, 这将在后面讨论. 原子 x 的任何先前值都会丢失. 注意, 说 \(v[(\text{SETQ } x y)] = v[y]\), 并带有将 \(v[y]\) 赋值为原子 x 的值的副作用, 几乎总是同样正确的.
• QUOTE: 特殊形式 \(v[(\text{QUOTE } x)] = x\).
• PLUS: 函数 \(v[(\text{PLUS } n m)] = v[n] + v[m]\). \(v[n]\) 和 \(v[m]\) 必须是数字.
• DIFFERENCE: 函数 \(v[(\text{DIFFERENCE } n m)] = v[n] - v[m]\). \(v[n]\) 和 \(v[m]\) 必须是数字.
• MINUS: 函数 \(v[(\text{MINUS } n)] = -v[n]\). \(v[n]\) 必须是一个数字.
• TIMES: 函数 \(v[(\text{TIMES } n m)] = v[n] \cdot v[m]\). \(v[n]\) 和 \(v[m]\) 必须是数字.
• QUOTIENT: 函数 \(v[(\text{QUOTIENT } n m)] = v[n]/v[m]\). \(v[n]\) 和 \(v[m]\) 必须是数字且 \(v[m] \neq 0\).
• POWER: 函数 \(v[(\text{POWER } n m)] = v[n] \uparrow v[m]\) 其中 \(a \uparrow b\) 表示 ‘a 的 b 次方’, \(a^b\); \(v[n]\) 和 \(v[m]\) 必须是数字, 使得如果 \(v[n] < 0\) 则 \(v[m]\) 是一个整数.
• FLOOR: 函数 \(v[(\text{FLOOR } n)] = \lfloor v[n] \rfloor\), 小于或等于 \(v[n]\) 的最大整数. \(v[n]\) 必须是一个数字.
• EVAL: 函数 \(v[(\text{EVAL } x)] = v[v[x]]\).

LISP 有内置函数来处理由原子构成的某些复合数据对象. 这些数据对象被称为非原子 S-表达式 (nonatomic S-expressions). 它们是二叉树, 其终端节点是原子. 其中一些树可以被解释为列表, 这在 LISP 中是一种非常流行的形式. 事实上, 正如前面提到的, LISP 的名字来源于短语 “list processing”. 原子和非原子 S-表达式一起构成了数据对象的类, 其成员被称为 S-表达式. 术语 S-表达式是短语符号表达式 (symbolic expression) 的缩写. 非原子 S-表达式在其他编程语言中扮演着数组的角色. S-表达式的类别是按句法定义的. 每个原子都是一个 S-表达式, 并且, 如果 a 和 b 是 S-表达式, 那么点对 (dotted-pair) `(a . b)` 是一个 S-表达式. 从数学上讲, 一个点对仅仅是一个有序对. 注意点对必须用括号括起来. 术语非原子 S-表达式和点对是同义的. 因此, 例如, 以下所有表达式都是 S-表达式, 最后五个是非原子 S-表达式. (注意, 其中一些 S-表达式本身是合法的 LISP 输入, 而另一些则不是.)

T
NIL
3
(1 . T)
((0 . .1) . NIL)
(((1 . 2) . (3 . 4)) . 5)
(PLUS . A)
(PLUS . (1 . (2 . NIL)))

点不是运算符; 点和括号仅仅是用来给点对的抽象概念提供一种具体形式, 就像数字符号被用来为整数的抽象概念提供一种具体形式一样. 点和括号在 LISP 的说法中被用于点表示法 (dot notation) 内.

在内部, 也就是说, 在计算机内部, LISP 中的一个普通原子由一个到原子表的整数索引表示, 也就是说, 由一个指针表示. 我们根据情况交替使用术语索引 (index) 和指针 (pointer); 术语地址 (address) 有时也使用. 通过知道一个普通原子的指针, 我们可以访问该原子的名称和值. 一个数字原子由一个到数字表的整数索引表示, 其中存储着相应的浮点值. 类似地, 一个非原子 S-表达式在内部也由一个指针表示. 需要一些方法来区分指针指向哪种对象. 因此, 我们将携带一个整数类型码和一个指针, 并将这对组合称为类型指针 (typed-pointer). 一个类型码和一个指针, 它们共同构成一个类型指针, 将被打包到一个 32 位的计算机字中. 因此, 一个类型指针由两个相邻的位域组成, 形成一个 32 位的整数. 前 4 个最左边的位保存所指向数据对象的类型, 剩下的 28 个最右边的位保存指向所指向数据对象的指针或索引. 我们假设一种传统的二进制整数表示, 其中高位 (最左位) 决定了存储在 32 位计算机字中的组合数的符号, 0 表示非负整数, 1 表示负整数. 一个形成非正 32 位整数的类型指针将是指向原子表中普通原子, 数字表中数字原子的指针, 或者, 正如我们稍后将讨论的, 指向函数或特殊形式的指针. 一个形成正整数的类型指针将是指向点对的指针.

假设原子表和数字表加载如下:

这里我们介绍一些在 LISP 中操作非原子以及原子 S-表达式的基本函数.

• ATOM: 谓词 \(v[(\text{ATOM } x)] = \text{if } v[x] \text{ 是一个普通原子或数字 then T else NIL.}\)
• CONS: 函数 \(v[(\text{CONS } x y)] = (v[x] . v[y])\). x 和 y 是任意的 S-表达式. CONS 是点对构造运算符.
• CAR: 函数 \(v[(\text{CAR } x)] = a\) 其中 \(v[x] = (a . b)\), 对于某些 S-表达式 a 和 b. 如果 \(v[x]\) 不是非原子 S-表达式, 那么 (CAR x) 是未定义的, 任何结果都是错误的.
• CDR: 函数 \(v[(\text{CDR } x)] = b\) 其中 \(v[x] = (a . b)\), 对于某些 S-表达式 a 和 b. 如果 \(v[x]\) 不是非原子 S-表达式, 那么 (CDR x) 是未定义的, 任何结果都是错误的.

CONS, CAR 和 CDR 之间的基本关系是: \(v[(\text{CONS (CAR } x) (\text{CDR } x))] = v[x]\) 其中 \(v[x]\) 是一个非原子 S-表达式. CONS 函数构造一个点对, CAR 函数返回点对的第一个成员, CDR 函数返回点对的第二个成员.

在 LISP 解释器程序内部, 可调用的 LISP 函数和特殊形式将指向 S-表达式的类型指针作为输入, 并返回指向 S-表达式的类型指针作为输出. 唯一 (明显的) 例外是那些接受或返回函数或特殊形式的函数和特殊形式, 也就是概念上是有序对集合的那些. 实际上, 在这些情况下也会使用类型指针. 当一个结果被计算出来时, 会返回一个指向该结果 S-表达式或函数的类型指针. 当最终结果被计算出来时, 指向最终结果的类型指针被用来到达所指向的数据对象, 然后检查该对象以便打印出其完整的词法表示作为最终交付物. 我们现在可以描述之前定义的一些函数和特殊形式的工作原理. 对于 `(QUOTE x)`, \(v[\text{QUOTE}]\) 接收一个指向 S-表达式 x 的类型指针作为输入, 并返回相同的类型指针作为结果. 对于 `(PLUS x y)`, \(v[\text{PLUS}]\) 接收两个类型指针作为输入, 一个指向 \(v[x]\), 一个指向 \(v[y]\) (记住, 根据 LISP 的规则, \(v[\text{PLUS}]\) 是一个函数, 所以 x 和 y 在 \(v[\text{PLUS}]\) 被调用之前被求值). 如果 \(v[\text{PLUS}]\) 接收到的两个类型指针不都指向数字原子, PLUS 就被错误地使用了. 否则, 就会形成和值, 并形成一个具有相应浮点值的数字原子. 指向数字表中这个数字原子的类型指针就是结果. 对于 `(EQ x y)`, \(v[\text{EQ}]\) 接收两个类型指针作为输入: 一个指向 \(v[x]\), 一个指向 \(v[y]\). 如果这两个类型指针相同, 则返回一个指向原子 T 的类型指针, 否则返回一个指向原子 NIL 的类型指针. 因此 EQ 会正确报告两个原子是否相等, 因为原子是唯一存储的, 但它可能无法检测到两个点对是相等的 (即, 在相同的树形结构中由相同的原子组成). 当两个这样相等的点对存在于内存中不同的列表节点时, 就会发生这种失败. 另一方面, 如果我们希望测试相同的, 共享的点对, EQ 将服务于这个目的. 例如, `(EQ (CONS 1 2) (CONS 1 2))` 可能返回 NIL, 因为两个点对 `(1 . 2)` 和 `(1 . 2)` 可能存在于不同的列表区节点中, 然后由不同的类型指针表示. 对于 `(CAR x)`, \(v[\text{CAR}]\) 接收一个指向 \(v[x]\) 的类型指针 j 作为输入. 如果 \(v[x]\) 不是一个点对, CAR 就被错误地使用了. 否则返回类型指针 Pj.car. 对于 `(CDR x)`, \(v[\text{CDR}]\) 接收一个指向 \(v[x]\) 的类型指针 k 作为输入. 如果 \(v[x]\) 不是一个点对, CDR 就被错误地使用了. 否则返回类型指针 Pk.cdr. 对于 `(CONS x y)`, \(v[\text{CONS}]\) 接收两个类型指针作为输入: 一个指向 \(v[x]\) 的类型指针 j 和一个指向 \(v[y]\) 的类型指针 k. 获得一个未被占用的列表节点 Ph, 并将 Ph.car 设置为 j, Ph.cdr 设置为 k. 严格来说, 类型指针 j 和 k 的类型必须是 0 (点对), 8 (普通原子), 或 9 (数字原子). 然后返回类型指针 se(h). CONS 是少数消耗内存的 LISP 函数之一. CONS 要求每次调用都分配一个新的列表节点. 对于 `(SETQ x y)`, \(v[\text{SETQ}]\) 接收两个类型指针作为输入: 一个指向 x 的类型指针 j 和一个指向 y 的类型指针 k (记住 SETQ 是一个特殊形式). 如果 j 是正数, 或者由 j 指向的值 x 是一个数字原子, 函数或特殊形式, 就会出错, 因为 x 必须是一个普通原子. (记住, 类型指针的类型码字段包含它所封装的 32 位计算机字的符号位.) 如果 j 不是正数且由 j 指向的值 x 是一个普通原子, 那么通过将 EVAL 应用于类型指针为 k 的 S-表达式 y 来计算 \(v[y]\). 这会产生一个指向 \(v[y]\) 的类型指针 i. 然后, 原子表中由 j 确定的普通原子 x 所在的行, 其 value 字段被设置为与 i 对应的索引, 其类型码被设置为 \(v[y]\) 的类型, 该类型在类型指针 i 中给出, 除非 \(v[y]\) 是一个未命名函数或未命名特殊形式, 在这种情况下, \(v[y]\) 的类型码 14 或 15 的出现导致 x 新赋的值分别具有类型码 12 或 13.

某些形式的非原子 S-表达式出现得非常频繁, 以至于有专门的表示法来表示它们. 一个形式为 \((S_1 . (S_2 . (\dots . (S_k . \text{NIL})\dots)))\) 的点对, 其中 \(S_1, S_2, \dots, S_k\) 都是 S-表达式, 被称为一个列表 (list), 并写成 \((S_1 S_2 \dots S_k)\), 这是 S-表达式 \(S_1, S_2, \dots, S_k\) 的序列, 中间用空格隔开并用括号括起来. 这与点表示法没有混淆, 因为列表中 \(S_i\) 元素之间没有点. 当然, 在某些或所有元素 \(S_1, \dots, S_k\) 中可能有点, 但那时它们必须用括号括起来, 并且点出现在较低的层次. 任何符合条件的元素 \(S_i\) 本身都可以用列表表示法或点对表示法书写. 但是, 请记住, 并非每个非原子 S-表达式都可以表示为列表. 单个元素 \(S_1\) 的列表 \((S_1)\) 在点对表示法中写成 \((S_1 . \text{NIL})\). 以此类推, 原子 NIL 用于表示没有元素的列表. 符号模式 "()" 也用于表示空列表; 它应被理解为 NIL 的同义词.

• AND: 参数数量可变的特殊形式 \(v[(\text{AND } x_1 x_2 \dots x_k )] = \text{if } v[x_1] \neq \text{NIL and } v[x_2] \neq \text{NIL and } \dots v[x_k] \neq \text{NIL then T else NIL}\). 特殊形式 AND 使用惰性求值 (lazy evaluation) 进行求值; 这意味着参数从左到右被求值并与 NIL 进行测试, 第一个值为 NIL 的参数是最后一个被求值的参数.
• OR: 参数数量可变的特殊形式 \(v[(\text{OR } x_1 x_2 \dots x_k )] = \text{if } v[x_1] \neq \text{NIL or } v[x_2] \neq \text{NIL or } \dots \text{ or } v[x_k] \neq \text{NIL then T else NIL}\). 特殊形式 OR 使用惰性求值进行求值; 参数从左到右被求值并与 NIL 进行测试, 第一个非 NIL 值的参数是最后一个被求值的参数.

我们可以使用 LISP 解释器来计算内置函数和应用于参数的特殊形式的组合的值, 但是要将 LISP 作为一种编程语言而不是一种奇特的计算器来使用, 我们必须有一种方法来定义我们自己选择的函数并使用它们, 而不仅仅是使用预先存在的函数的未命名组合. 特殊形式 LAMBDA 在 LISP 中用于创建用户定义的函数. LAMBDA 接受两个参数, 它们都是 S-表达式. 第一个参数是一个普通原子列表, 表示正在定义的函数的形式参数, 第二个参数是一个 S-表达式, 表示正在定义的函数的定义. 这个第二个参数必须是合法的 LISP 输入, 所以它要么是一个原子, 要么是一个函数应用表达式. 这个第二个参数被称为函数定义的主体 (body). 一个表示特殊形式 LAMBDA 应用的列表被称为 LISP λ-表达式. 例如, λ-表达式 `(LAMBDA (X Y) (CONS Y X))` 表示一个函数. 这意味着, 在概念上, 它的值是一个有序对的集合. 它是这样一个函数, 给定两个 S-表达式, a 和 b, 作为输入, 返回点对 `(b . a)` 作为输出. 注意这个函数没有名字. 为了在 LISP 中使用这个函数, 我们可以向 LISP 解释器输入 `((LAMBDA (X Y) (CONS Y X)) 2 3)`, 并且会打印出 `(3 . 2)`. 在 λ-表达式 `(LAMBDA (X Y) (CONS Y X))` 中, S-表达式 `(CONS Y X)` 是主体, `(X Y)` 是形式参数的列表. 继续这个例子, `((LAMBDA (X Y) (CONS Y X)) 2 3)` 的求值过程是: 将第一个实际参数 2 的值绑定到第一个形式参数 X, 将第二个实际参数 3 的值绑定到第二个形式参数 Y, 然后通过计算 \(v[(\text{CONS Y X})]\) 来求值主体 `(CONS Y X)`, 此时主体中 X 的每次出现都求值为其关联的绑定值 2, Y 的每次出现都求值为其关联的绑定值 3. 这意味着在主体表达式 `(CONS Y X)` 中 \(v[\text{X}] = 2\) 且 \(v[\text{Y}] = 3\), 无论原子表中 X 和 Y 的全局值是什么. 设 a 是一个包含 k ≥ 0 个普通原子的列表, b 是一个可求值的 S-表达式. 通常, λ-表达式 `(LAMBDA a b)` 的值被定义为, 使得 \(v[(\text{LAMBDA } a b)]\) 等于在 k 个实际参数列表 r 上通过计算 \(e[b, a, r]\) 来计算的函数, 其中 \(e[b, a, r] = v[b]\) 在上下文中满足对于 \(1 \le i \le k\), \(v[a_i] = r_i\). 符号 e 代表环境求值. 这是一种依赖于由实际参数值到形式参数的绑定所指定的上下文的 v-运算符. 为每次使用都写一个 λ-表达式来指定函数是很笨拙的, 所以我们采用一种给函数命名的机制. λ-表达式的值可以使用 SETQ 来赋名. 因此, 例如, 求值 `(SETQ G (LAMBDA (X Y) (CONS Y X)))` 会导致普通原子 G 具有值 \(v[(\text{LAMBDA (X Y) (CONS Y X)})]\). 打印出的结果通常被理解为概念上赋给 G 的有序对集合, 即 \(v[(\text{LAMBDA (X Y) (CONS Y X)})]\), 这被表示为 "{user function: G}". 现在我们可以写 `(G 2 3)` 来得到 `(3 . 2)`. 如果你查看各种 LISP 方言, 你会发现一个通常称为 DEFINE 或 DEFUN (意为 define-function) 的特殊形式常用于将一个函数赋给一个普通原子的值, 但没有理由 SETQ 不能用于此目的, 所以我们在本书中避免使用 DEFUN. DEFUN 的使用通常与一种允许普通原子同时具有 S-表达式值和函数值的机制相结合. 正如我们定义的原子表, 这个选项是不可能的, 无论如何似乎也不是很有利. 注意, SETQ 的定义是其结果是赋值后其第一个参数的值. 这意味着第一个参数已经有一个用户定义的命名函数作为其值, 当 SETQ 用于给一个普通原子赋一个函数时, 这个值会作为结果出现. 定义和命名函数最有趣的情况是在使用递归时. 例如:

(SETQ FACT (LAMBDA (X)
               (COND ((EQ X 0) 1)
                     (T (TIMES X (FACT (DIFFERENCE X 1)))))))

这定义了阶乘函数 \(fact(n) = 1 \cdot 2 \cdot 3 \dots \cdot (n - 1) \cdot n\). 这是一个非断言性定义 (impredicative definition); 这意味着正在被赋值的名称 FACT, 本身被用于定义那个值. 这是一个令人不安的情况, 但在实用上完全可以理解. 特殊形式 LAMBDA 真正做的是将它的两个参数 CONS 在一起, 并返回一个指向结果点对的未命名函数类型的指针; 这是一个类型码为 14 的类型指针. 参数本身在函数实际应用之前不被检查. 如果这个表示为点对的未命名函数被赋给一个普通原子 b 的值, 那么 b 的值就只是指向这个点对的指针, 并且这个值的类型被设置为 12, 以表示一个用户定义的函数. 因此, 例如, 当上面赋值的 FACT 被使用时, 主体内的递归引用 FACT 被正确地解释, 因为在求值主体时 FACT 的值是一致定义的. 记住 \(v[(\text{SETQ } x y)]\) 被定义为在 \(v[x]\) 被赋为等于 \(v[y]\) 之后的值 \(v[x]\); 但是当 y 是一个 λ-表达式时, 这不成立. 在这种情况下, \(v[y]\) 是一个指向表示 λ-表达式 y 的值的 CONS 起来的点对的类型指针. 这个类型指针的类型码是 14. 然而, 在赋值以重新定义 \(v[x]\) 之后, \(v[x]\) 是一个指向同一点对的类型指针, 但是 \(v[x]\) 的类型码是 12 而不是 14. 因此, 在将一个 λ-表达式 y 的值赋给一个普通原子 x 的情况下, 赋值后 \(v[x]\) 的类型码*不是* \(v[y]\) 的类型码. 这个尴尬的例外之所以出现, 是因为 函数不必有名称. 如果总是需要名称, 这种编码在类型码值中的区别将是不必要的.

LISP 中有许多内置函数, 它们在逻辑上不是必须内置的. 它们的存在是为了方便, 在某些情况下是因为那样更快. 下面介绍的三个函数是内置函数, 它们可以用其他更基本的函数和特殊形式来定义.

• APPEND: 函数 定义为:

  (SETQ APPEND
        (LAMBDA (X Y)
                (COND ((EQ X NIL) Y)
                      ((ATOM X) (CONS X Y))
                      (T (CONS (CAR X) (APPEND (CDR X) Y))))))
  

  这个版本的 APPEND 比通常找到的定义稍微通用一些, 后者省略了 `((ATOM X) (CONS X Y))` 这对. 给定两个列表 \((a_1 a_2 \dots a_h)\) 和 \((b_1 b_2 \dots b_k)\) 作为输入, 列表 \((a_1 a_2 \dots a_h b_1 b_2 \dots b_k)\) 作为输出产生. 输入不会以任何方式被破坏. 在某种意义上, 这个函数体现了 LISP 的精髓. 当你在机器层面详细了解这个函数应用于参数时会发生什么, 你就会理解 LISP 的精髓. 例如, 若 \(v[\text{A}] = (1 \text{ A } 2)\), 则 \(v[(\text{APPEND A (LIST 7)})] = (1 \text{ A } 2 7)\), 而 \(v[(\text{APPEND A 7})] = (1 . (\text{A} . (2 . 7)))\); APPEND 连接两个列表; 它对原子的作用更随意. 注意 APPEND 在列表的末尾添加, 而 CONS 在列表的前面添加. 然而, 这些函数是不对称的; CONS 一次只能在列表的前面添加一个元素, 而 APPEND 可以在列表的末尾添加一整个元素列表. 此外, CONS 是高效的, 而 APPEND 是低效的; 这是因为一个带有指向第一个元素的指针的链表是一个不足以允许直接访问列表末尾的数据结构. (我们可以使用其他数据结构, 如双向链表 [双向链接] 二叉树或哈希表, 而不是单向链表 [Knu68, Knu73], 事实上, 在 LISP 的一些实现中已经这样做了.)

用户定义的特殊形式是通过应用特殊形式 SPECIAL 来创建的, 这与特殊形式 LAMBDA 完全类似, 只是返回一个指向输入参数点对的未命名特殊形式类型指针, 这样结果在以后使用时将被解释为一个特殊形式而不是一个函数. 一个未命名特殊形式类型指针的类型码是 15. 因此, 由 SPECIAL 创建的特殊形式的主体和形式参数列表通过将输入参数 CONS 在一起形成一个点对来表示, 并返回一个未命名特殊形式类型指针, 其指针部分索引这个点对. 就像 λ-表达式一样, 被赋给一个未命名特殊形式的普通原子的值的类型码被强制为 13 而不是 15. 值 13 是表示命名特殊形式的类型码. 新重置的值字段包含一个指向特殊形式的参数列表和主体的点对的指针. 设 a 是一个包含 k ≥ 0 个普通原子的列表, b 是一个可求值的 S-表达式. 一般来说, 特殊形式表达式 `(SPECIAL a b)` 的值被定义为 \(v[(\text{SPECIAL } a b)]\), 它等于在 k 个实际参数列表 r 上通过计算 \(e[b, a, r]\) 来计算的函数, 其中 \(e[b, a, r] = v[b]\) 在上下文中满足对于 \(1 \le i \le k\), \(v[a_i] = r_i\). 与 λ-表达式不同, 实际参数 r 是按原样给出的, 而不是通过求值给定的实际参数来计算的. 需要注意的是, LISP 特殊形式或函数的值 (即含义) 在上下文中的定义与在 Algol 中常用的替换规则所引出的含义是不同的, 在 Algol 中我们会说 \(v[(\text{SPECIAL } a b)]\) 是在 k 个实际参数列表 r 上计算的函数, 通过计算 b 的值, 其中对于 \(1 \le i \le k\), b 中 \(a_i\) 的每次出现都被 \(r_i\) 替换. 绑定会临时取代原子表中的符号含义, 正如在绑定生效期间完成的每个普通原子求值所看到的那样, 而替换并不会在所有地方都掩盖这些含义. 例如, `(SETQ EVALQUOTE (SPECIAL (X) (EVAL X)))` 定义了特殊形式 EVALQUOTE, 在下面的练习中使用.

递归函数或特殊形式可以在 LISP 中使用 SETQ 命名和定义. 这很方便, 我们几乎总是这样定义函数和特殊形式. 但这给 LAMBDA 运算符留下了一个理论上的困难, 即我们必须使用 SETQ 并赋一个名称才能定义一个递归函数. 因此, 理论上并非每个期望的函数都可以作为一个 λ-表达式就地编写. 为了解决这个困难, 引入了特殊形式 LABEL.

• LABEL: 特殊形式 \(v[(\text{LABEL } g h a_1 \dots a_k)] = e[(h v[a_1] \dots v[a_k]), g, h]\), 其中 g 是一个普通原子, h 是一个 λ-表达式, \(a_1, \dots, a_k\) 是 S-表达式. 其思想是 `(LABEL g h a<sub>1</sub> … a<sub>k</sub>)` = \(v[(h a_1 \dots a_k)]\) 在上下文中, 原子 g 在 λ-表达式 h 的主体中每次出现时都被求值为 λ-表达式 h. 因此, 在对提供的参数 \(a_1, \dots, a_k\) 求值 h 期间, g 实际上是 h 在 h 主体内的名称或标签.

将 LABEL 的定义扩展到应用于特殊形式留作练习, 因为 LABEL 主要需要提供一个令人愉快的理论闭包, 并且不常在实践中使用, 而且除了 QUOTE, 特殊形式在理论上可以通过使用 QUOTE 来保护相应 λ-表达式的参数来避免. 事实上, 下面给出的 LISP 解释器中不包含 LABEL.

特殊形式 QUOTE 使用得如此频繁, 以至于提供了一种特殊的表示法. 单引号或撇号符号用于表示一个一元前缀运算符, 定义为 'e = (QUOTE e). 因此, 例如, SET 函数可以通过输入定义:

(SETQ SET (LAMBDA (X Y)
                  (EVAL (CONS 'SETQ (CONS X (CONS 'Y NIL))))))

单引号符号作为一个宏 (macro) 起作用; 它在输入时被展开. 因此 ' 不能在 LISP 函数中作为一个原子来操作. 记住 ' 不表示单独的 QUOTE; 它必须带一个参数.

• NOT: 谓词 定义为: `(SETQ NOT (LAMBDA (X) (EQ X NIL)))`.
• NULL: 谓词 定义为: `(SETQ NULL (LAMBDA (X) (NOT X)))`. 注意 NULL 只是 NOT 的同义词. 我们可能更喜欢在测试 NIL 时使用 NULL, 在执行布尔逻辑非运算时使用 NOT.

为了在 LISP 解释器中高效地处理数字原子作为值, 我们使用了指向数字的指针来勾勒 v 运算符的工作方式. 这种指针的使用也需要允许函数被视为值. 指导思想是 LISP 解释器需要知道, 至少是潜在地, 与任何被操纵的值相关联的名称或词法表达式, 并且每个这样的值都由一个指向该值的完整表示的类型指针来表示. 特别是, 那么, 一个数字必须以一种方式表示, 这种方式允许在打印它, 将它用作计算中的参数或 CONS 参数, 以及在创建新数字作为中间结果时得到正确的结果. 考虑:

v[3.1],
v[A], where v[A] has been made equal to 3 via (SETQ A 3),
v[(PLUS 2 3)],
v[(PLUS 2 A)],
v[(CONS (PLUS 2 A) 1)].

每当通过计算 (例如, 求值 (PLUS 2 3)) 创建一个数字时, 该数字就会被输入到数字表中一个可用的行中, 当且仅当它尚未存在. 对于这种计算创建的数字, 可以通过不构造数字名称文本字符串来节省一些时间; 事实上, 为了统一性, 我们丢弃输入数字的文本字符串名称. 这种无名的数字原子被称为*懒惰数字原子* (lazy number atoms). 如果一个懒惰数字原子必须被打印出来, 只有那时我们才构造它的文本字符串名称. 此外, 不再需要的计算创建的数字原子应该不时地从数字表中移除. 类似地, 一个函数或特殊形式必须以一种方式表示, 这种方式允许在应用它, 打印它, 或将它用作计算中的参数时得到正确的结果. 考虑:

v[PLUS],
v[(PLUS 2 3)],
v[(EVAL (APPEND 'PLUS '(2 3)))],
v[(EVAL (APPEND PLUS '(2 3)))].

像 \(v[\text{PLUS}]\) 这样的函数的适当内部表示是作为一个指向原子 PLUS 的类型指针, 其中这个类型指针的类型码是 10, 而不是 8, 表明它引用的是一个内置函数, 也就是所指向的原子的值. 这样, 我们既知道函数又知道它的名字. 因此, 一个作为存储在原子表 j 条目中的普通原子 x 的值的内置函数, 由类型指针 bf(j) 表示. 这个原子表条目显示为 `[x, 10, t, −, −]`. 值字段条目 t 是一个指示特定内置函数的整数, 也就是 x 的值. 相比之下, 普通原子 x 由类型指针 oa(j) 表示. 同样, 一个作为存储在原子表 j 条目中的普通原子 x 的值的内置特殊形式, 由类型指针 bs(j) 表示. 这个原子表条目显示为 `[x, 11, t, −, −]`. 值字段条目 t 是一个指示特定内置特殊形式的整数, 也就是 x 的值. 一个用户定义的函数是由特殊形式 LAMBDA 通过将参数列表和主体 S-表达式 CONS 在一起并在列表区构造一个 S-表达式来构造的, 并返回一个指向这个构造的 S-表达式的类型指针. 这个类型指针的类型码是 14, 表示一个*未命名函数*. 类似地, 特殊形式 SPECIAL 构造一个点对, 并返回一个指向这个点对的类型指针, 类型码为 15, 表示一个*未命名特殊形式*. 当 SETQ 将一个未命名函数或特殊形式赋给一个普通原子时, 该原子的值从此由一个指向该原子的类型指针表示, 对于用户定义的函数其类型码为 12, 对于用户定义的特殊形式其类型码为 13. 假设普通原子 F 占据原子表的第 i 行, 并且我们求值 `(SETQ F (LAMBDA (X) 1))`. 那么普通原子 F 的行在原子表中是 `i : [F, 12, j, −, −]`, 其中

P_j = +---+---+
      | k | 1 |
      +---+---+
and
P_k = +---+-----+
      | X | NIL |
      +---+-----+

表示 \(v[\text{F}]\) 的类型指针然后以 12 作为其类型码, i 作为其指针部分. 这使我们既能知道函数的名称, 也能知道它的定义 S-表达式, 也就是 F 的值.

为了在 LISP 解释器中实现用于求值 λ-表达式主体的 e 运算符, 我们必须设计一种机械化的方式来将实际参数绑定到形式参数, 并在相关的 λ-表达式被求值期间遵守由此建立的上下文. 有几种方法可以做到这一点. 最早的方法, 在 IBM 704 和 709 的原始 LISP 解释器中使用, 是维护一个所谓的*关联列表* (association list). 描述这种方法然后用它作为一个模型来解释 LISP 解释器实际上是如何工作的, 如果不是事实上也是如此, 是很方便的. 关联列表是一个 LISP 列表, 它是内置普通原子 ALIST 的值. 关联列表的元素是点对 `(ni . vi)`, 其中 ni 是用作形式参数的普通原子, vi 是一个 S-表达式或函数, 它是绑定到 ni 的实际参数. 当一个函数调用表达式 `(g a1 … ak)` 要被求值时, 这样的点对被放到关联列表上. \(v[g]\) 的形式参数列表 `(f1, … , fk)` 被检索, 并且形式参数—实际参数的点对 `(fi . v[ai])` (当 \(v[g]\) 是一个函数时), 或 `(fi . ai)` (当 \(v[g]\) 是一个特殊形式时) 被形成, 并按从第一个到最后一个的顺序 CONS 到 \(v[\text{ALIST}]\) 上. 在 LISP 解释器内部做了一个例外, 使得像 \(v[\text{PLUS}]\) 这样的函数和特殊形式被允许作为关联列表点对中的元素. 这是必需的, 因为 LISP 函数和特殊形式可以接受函数和/或特殊形式作为参数. 现在获取 \(v[g]\) 的主体, LISP 解释器被递归调用来求值它. 在这个求值过程中, 每当遇到一个普通原子 d 时, 它都在当前上下文中被求值, 首先从前到后搜索关联列表以查找形式为 `(d . w)` 的第一个点对; 如果找到这样的对, d 的值就被认为是 w. 否则, 如果在 \(v[\text{ALIST}]\) 上找不到这样的对, 那么就在 d 的原子表条目中寻找 d 的值. 当 \(v[g]\) 的主体在当前关联列表给出的上下文中被求值后, 对应于 \(v[g]\) 形式参数绑定的初始 k 个点对从关联列表 \(v[\text{ALIST}]\) 中移除. 这种解析绑定到普通原子的值的模型被称为*动态作用域* (dynamic scoping), 与 Algol 等语言中的*词法*或*静态作用域* (lexical or static scoping) 相对. 在 Algol 中, 函数定义可以在定义文本中进行词法嵌套. 函数 p 主体中变量 x 的值被确定为在 p 嵌套于其中的最近的函数主体中绑定到 x 的值, 包括 p 本身的主体, 在 x 是局部定义变量或 p 的参数的情况下, 或者如果 p 没有 嵌套在任何其他函数中. 这种词法作用域搜索确定变量值的过程等价于在调用具有名为 x 的形式参数的函数 p 时, 将要绑定到 x 的实际值词法替换为 p 函数主体内 x 的名称, 除了那些嵌套在 p 内且具有名为 x 的形式参数的函数主体. 假设我们在同一词法级别有两个函数, f(a, b) 和 g(b, c), 其中 g 从 f 内部被调用. 使用 Algol 词法作用域, g 内部 a 的值是 a 的全局原子表值, 无论 g 是否从 f 运行调用. 使用 LISP 动态作用域, 如果 g 从顶层调用 g 运行, a 的值是全局原子表值, 如果 g 从 f 运行调用, a 的值是传递给 f 用于绑定到 a 的实际参数值. (Algol 有其自身的复杂性, 特别是, Algol 的词法静态作用域绑定规则有一些棘手的含义. 这只是在过程嵌套在过程中并混合形式参数和非局部变量名称时才是一个问题; C 通过禁止词法嵌套过程的声明来避免这些问题.) 注意, 如果同一个普通原子 x 在不同的 λ-表达式中多次用作形式参数, 并且相应的函数一个接一个地被调用, 那么同一个原子 x 将在某个时间段内在关联列表上的点对中多次出现. 每当必须求值 x 时, 都会使用最新的现有绑定. 这正是正确的做法, 但是当这个事实被遗忘时, 可能会出现明显的错误. 例如, 如果我们输入:

(SETQ G 3)                  followed by
(SETQ F (LAMBDA (X) (CONS X G)))  and
(SETQ B (LAMBDA (G X) (CONS G (F (PLUS X 1)))))

那么 \(v[(\text{B 2 0})] = (2 . (1 . 2))\), 但是 \(v[(\text{F 1})] = (1 . 3)\). 出现在函数 \(v[\text{F}]\) 主体中的普通原子 G 被称为函数 \(v[\text{F}]\) 的*自由变量* (free variable). 一般来说, 出现在函数或特殊形式主体中但未被列为该函数或特殊形式的形式参数的任何普通原子都是该函数或特殊形式的自由变量. 当一个函数或特殊形式的主体在关联列表的绑定对提供的上下文中被求值时, 遇到的自由变量的值由当前的关联列表确定 (如果可能). 因此, 你不能写一个像 \(v[\text{F}]\) 这样的函数, 并期望它的自由变量具有那些名称的原子表条目的值, 除非你小心不要在其他地方使用那些名称作为形式参数, 或者至少安排在函数被调用时它们永远不会在关联列表上被绑定. 这种情况并不那么糟糕. 我们只需要使用足够的纪律来避免在可能产生混淆时从同一候选者中选择形式参数名称和全局原子表名称. 简单的 LISP 参数绑定规则的一个抵消好处是, 我们可以利用关联列表上的最新绑定是普通原子的当前值这一事实, 来明确地跳过将参数传递给函数, 当我们知道所需的绑定已经生效时. 例如, 考虑:

(SETQ MAXF (LAMBDA (L F)
                   (COND ((NULL (CDR L)) (CAR L))
                         (T (MH (CAR L) (MAXF (CDR L) F))))))

和

(SETQ MH (LAMBDA (A B)
                 (COND ((GREATERP (F A) (F B)) A)
                       (T B)))).

这里 F 是 MH 中的一个自由变量, 当 MAXF 被调用时, 它将被正确地解释为绑定到 F 的函数, 因为 MH 只打算从 MAXF 内部使用. 这种设备被称为*跳跃绑定* (skip-binding). 然而, 在某些情况下, 通过遵循简单的关联列表模型进行上下文求值来对一个明显自由的变量进行求值是明显违反直觉的. 考虑这个例子:

(SETQ F (LAMBDA (A)
                (G (PLUS A 1)
                   (LAMBDA (X) (CONS X A))))).

这里我们有一个函数体, 它包含对某个函数 G 的调用, 该函数被传递一个由 LAMBDA 创建的函数作为其一个实际参数, 即 \(v[(\text{LAMBDA (X) (CONS X A)})]\). 普通原子 A 是这个参数函数的自由变量, 但 A 是包含函数 F 的形式参数, 而不是自由变量. 现在假设我们用 `(SETQ G (LAMBDA (A H) (H A)))` 定义 G. 那么 \(v[(\text{F 1})] = (2 . 2)\). 但是, 如果我们用 `(SETQ G (LAMBDA (O H) (H O)))` 定义 G, 那么 \(v[(\text{F 1})] = (2 . 1)\). 因此, 为了避免这样的意外, 我们不仅要避免全局名称和形式参数名称选择的冲突, 而且每当使用函数参数时, 我们还必须注意如果我们在不同的函数中使用相同的名称作为形式参数, 就会产生冲突. 这个困难被称为*函数参数问题* (functional argument problem) 或 “funarg” 问题.

让基本 S-表达式集合是普通原子 (非数字名称) 和由它们形成的非原子 S-表达式的集合. 以下九个函数和特殊形式构成了一组通用的函数和特殊形式, 意思是, 用它们可以表达任何基本 S-表达式参数的可计算函数: QUOTE, ATOM, EQ, CONS, CAR, CDR, COND, LAMBDA, LABEL. 记住, LABEL 实际上是一个符号设备, 允许陈述递归 λ-表达式, 所以我们可以 (弱) 说最小 LISP 只有八个功能组件. 我们为什么要考虑什么构成 LISP 运算符的最小集合? 我们永远不想使用这样一个傻瓜式的受限编程语言. 答案是 LISP 不仅仅是一种不寻常但实用的编程语言; 它深受数学计算理论精神的影响, 在那里我们问哪些函数可以被计算, 以及计算一个函数需要多少步 (以其输入为单位). 通常我们将自己限制在整数定义域和值域集合上. 为了定义什么是“一步”, 我们发现考虑像图灵机这样的简单计算模型是很有用的. 最小 LISP 是另一个这样的计算模型. 基本 S-表达式参数的可计算函数对应于非负整数的可计算函数, 因为我们可以规定一个有效的枚举映射, 将一个非负整数赋给每个基本 S-表达式. 证明非负整数的可计算函数被基本 S-表达式参数的可计算函数所包含要容易一些. 为此, 我们将整数 k 与原子 NIL 关联, 如果 k 是 0, 并与由 k 个 T 组成的列表 (T … T) 关联, 如果 k > 0. 因此, 非负整数, 并通过进一步的扩展, 有理数, 实际上被包含在各种最小 LISP 函数的定义域中.

本章讨论更多的函数和特殊形式.

• SUM: 参数数量可变的函数 \(v[(\text{SUM } n_1 n_2 \dots n_k)] = v[(\text{PLUS } n_1 (\text{PLUS } n_2 ( \dots (\text{PLUS } n_k 0)\dots)))]\).
• PRODUCT: 参数数量可变的函数 \(v[(\text{PRODUCT } n_1 n_2 \dots n_k)] = v[(\text{TIMES } n_1 (\text{TIMES } n_2 (\dots(\text{TIMES } n_k 1))\dots))]\).
• DO: 参数数量可变的函数 \(v[(\text{DO } x_1 x_2 \dots x_k)] = v[x_k]\). 由于 DO 是一个函数, 它的所有参数都从左到右被求值, 然后返回最后一个参数的值. 当它的参数在求值过程中有副作用时, 这个函数很有用. 基本上, DO 提供了一种像传统编程语言中那样执行一系列语句 (函数应用) 的方法.

• INTO: 函数 定义为:

  (SETQ INTO (LAMBDA (G L)
                     (COND ((NULL L) L)
                           (T (CONS (G (CAR L))
                                  (INTO G (CDR L))))))).
  

  给定列表 \(L = (L_1 L_2 \dots L_k)\), INTO 函数计算函数或特殊形式 G 对 L 的每个元素的应用, 以获得 \(((G L_1) (G L_2) \dots (G L_k))\).

• ONTO: 函数 定义为:

  (SETQ ONTO (LAMBDA (G L)
                     (COND ((NULL L) L)
                           (T (CONS (G L)
                                  (ONTO G (CDR L))))))).
  

  给定列表 \(L = (L_1 L_2 \dots L_k)\), ONTO 函数计算函数或特殊形式 G 对列表 L 的应用, 并递归地对 L 的每个尾部应用, 以获得 `((G L) (G ( CDR L)) … (G (CDR (CDR … (CDR L)))))`.

• APPLY: 特殊形式 定义为:

  (SETQ APPLY (SPECIAL (G X) (EVAL (CONS G X)))).
  

为了能够指定一个行为像交互式程序的 LISP 函数, 我们需要一种向用户打印消息和读取用户提供输入的机制. 函数 READ 和 PRINT 满足这些要求.

• READ: 伪函数 \(v[(\text{READ})]\) 等于响应提示感叹号符号 ! 向用户输入的 S-表达式.
• PRINT: 参数数量可变且副作用无害的函数 \(v[(\text{PRINT } x_1 x_2 \dots x_k )] = \text{NIL}\), 其中 \(v[x_1], v[x_2], \dots, v[x_k]\) 每个都在终端上作为副作用打印出来. 如果 k 是 0, 则打印一个空格.
• PRINTCR: 参数数量可变且副作用无害的函数 \(v[(\text{PRINTCR } x_1 x_2 \dots x_k )] = \text{NIL}\), 其中 \(v[x_1], v[x_2], \dots, v[x_k]\) 每个后面都跟一个回车符, 并在终端上作为副作用打印出来. 如果 k 是 0, 则打印一个回车符. (回车符 (carriage-return) 是换行 (newline) 的一种老式说法. 在 Linux 或 OS-X 上, 换行是 ASCII 换行符 (10); 在 Windows 上, 换行实际上是两个 ASCII 字符回车符 (13) 后跟一个换行符 (10)).

普通原子有值, 并且通常想象一个普通原子有多个值是很方便的. 这可以通过创建一个这些值的列表并将这个列表用作其元素是所需多个值的值来实现. 然而, 频繁地, 这些多个值被用来编码属性 (properties). 这很常见, 以至于 LISP 提供了特殊的功能来容纳属性. 抽象地说, 属性是一个函数. LISP 只提供适用于普通原子且其值为 S-表达式的属性, 它建立并使用一组特殊的列表来制表这种属性的输入-输出对. 假设 A 是一个普通原子, g 是一个抽象的属性函数. 那么 g 在 A 上的值被称为 A 的 g-属性值. LISP 不在需要时计算一个原子的特定属性值, 而是提供一种记录这些属性值以及相应的普通原子的方法, 这样属性值可以被检索而不是计算. 每个普通原子 A 都有一个与之关联的列表, 称为 A 的属性列表 (property list). 指向这个列表的类型指针存储在普通原子 A 的 plist 字段中. 这个列表可以被认为是 A 的一个备用值. 通常, 普通原子 A 的属性列表要么是 NIL, 要么是一个点对列表. 属性列表中每个这样的点对 `(p . w)` 被解释为意味着属性 p 在 A 上的值是 w. 因此属性和属性值由 S-表达式表示. 事实上, 通常属性由普通原子表示. 提供了以下函数来帮助处理属性列表.

• PUTPROP: 带有副作用的函数 \(v[(\text{PUTPROP } a p w)] = v[a]\), 并且属性, 属性-值点对 `(v[p] . v[w])` 被插入到原子 \(v[a]\) 的属性列表中. 如果存在另一个重复的属性, 属性-值点对, 对于属性 \(v[p]\) 和属性-值 \(v[w]\), 它将被移除. \(v[a]\) 必须是一个普通原子, \(v[p]\) 和 \(v[w]\) 是任意的 S-表达式.
• GETPROP: 函数 \(v[(\text{GETPROP } a p)]\) 等于当前属性值, 该值与属性 \(v[p]\) 在普通原子 \(v[a]\) 的属性列表上点对. 如果对于属性 \(v[p]\) 的点对不存在于 \(v[a]\) 的属性列表上, 则返回 NIL.
• REMPROP: 带有副作用的函数 \(v[(\text{REMPROP } a p w)] = v[a]\), 并且属性, 属性-值点对 `(v[p] . v[w])` 对于属性 \(v[p]\) 从普通原子 \(v[a]\) 的属性列表中移除, 如果这样的点对存在于 \(v[a]\) 的属性列表上.