Forth 与 Lisp 的迁移之道

# 超越 Lambda 的 Let Over Lambda 来源：https://letoverlambda.com/textmode.cl/guest/chap8.html ## Let Over Lambda —— Lisp 50 年 ## 作者：Doug Hoyte ## Lisp 推动 Forth，Forth 推动 Lisp ### 刻意为之的怪异 本章是对本书迄今为止讨论的诸多宏技术的总结。我们将利用已开发的宏抽象，实现我最喜欢的编程语言之一：**Forth**。虽然这个实现体现了 Forth 的大多数重要思想，但它非常不同且充满 Lisp 风格。尽管本章代码有一些有趣的应用，但其主要目的是向 Lisp 受众传授 Forth 元编程的概念和基础，并作为本书核心主题——通过宏创建和利用语法二元性——的讨论平台。 Forth，除了 Lisp 之外，比其他任何语言都更拥有丰富而迷人的历史，我很庆幸发现了它。因此，也为了其他一切，本章献给我的父亲 Brian Hoyte，是他向我介绍了 Forth 和计算机编程。本章部分灵感来自 [THREADING-LISP] 以及 Henry Baker 的研究 [LINEAR-LISP] [LINEAR-LISP-AND-FORTH]。 Forth 是第一种在没有强大的政府、学术或企业赞助下创建和开发的编程语言——或者至少是第一种成功做到这一点的语言。Forth 并非受大型组织需求驱动，而是由 Chuck Moore 在 1968 年左右独立发明，用于解决他自己在天文学、硬件设计等方面的计算需求。此后，Forth 由热情的草根用户社区分发、实现和改进 [EVOLUTION-FORTH-HOPL2]。这与早期 Lisp 和 COMMON LISP 受到的 MIT（及后来的 DARPA）赞助、IBM 的 FORTRAN 以及 AT&T 的 Unix 语言 C 形成对比。由于这些根源，以及对于计算机软件和硬件角色的不同哲学，Forth 与众不同。甚至比 Lisp 更甚，Forth 看起来**怪异**。但和 Lisp 一样，Forth 的怪异是有原因的：它的设计考虑的不只是风格。Forth 刻意设计得怪异，而这种设计与宏相关。 如今，Forth 最常用于所谓的嵌入式平台——资源严重受限的计算机。Forth 的设计证明了它几乎可以在所有可编程计算机系统上完全实现。Forth 被设计为尽可能易于实现和试验。事实上，创建一个 Forth 克隆如此简单，以至于发明一个两种 Forth 风格的基于栈的语言几乎是编程语言设计爱好者的成人礼。一些可以追溯到 Forth 并做出有趣贡献的基于栈的语言有 PostScript 和 Joy。 通常，Forth 的重要实现决策取决于实现它的计算机的确切资源。Forth 程序员设计了一套**抽象寄存器**，需要映射到真实寄存器、映射到内存位置，或者以完全不同的方式实现。但如果我们是在 Lisp 上实现 Forth——一个潜力无限且限制很少的环境——该怎么办？我们不是简单地将 Forth 抽象寄存器任意映射到 Lisp 代码，而是尝试退一步思考。如果 Chuck 有一台 Lisp 机器，Forth 会是什么样子？我们探索一组最小的 Forth 抽象寄存器，针对在 Lisp 上实现时的简单性和能力进行了优化，而不是将 Forth 适配到任意机器（真实或虚拟）的能力上。 但事实上，Chuck 在创建 Forth 时，利用他在众多架构上实现数十种不同 Forth 的经验，正是为了寻找一组最佳的抽象概念。这就是 Forth 如此伟大的原因。和 Lisp 一样，Forth 代表了语言设计空间中的一个高局部最大值，而且也和 Lisp 一样，Forth 与其说是一种编程语言或一套标准，不如说是一种建筑材料，以及关于什么有效、什么无效的智慧集合。 ### Forth 寄存器 ```lisp (defvar forth-registers '(pstack rstack pc dict compiling dtable)) ``` **forth-registers** 变量是一个符号列表，代表我们 Forth 机器的抽象寄存器。当然，Lisp 并不以寄存器和定长数来思考，而是变量和符号。从一个仅包含变量名的列表开始开发 Forth 环境似乎很奇怪，但这实际上始终是实现 Forth 系统的第一步。创建 Forth 是一个巧妙的自举过程，其美丽和聪明仅次于 Lisp。以下是对此过程的简要描述。 Forth 的一个典型特征是其直接访问栈数据结构的能力，这些栈用于向子程序传递参数，以及在这些子程序中跟踪执行路径。Forth 尤其有趣，因为——与大多数编程语言不同——它将栈数据结构的这两种用途分离为两个你可以操作的栈¹（https://letoverlambda.com/textmode.cl/guest/chap8.html#）。在典型的 C 实现中，函数调用的参数及其所谓的**返回地址**存储在单个、可变大小的**栈帧**中，每个函数调用一个。在 Forth 中，它们是两个不同的栈：参数栈和返回栈，分别由我们的抽象寄存器 **pstack** 和 **rstack** 表示。我们使用 COMMON LISP 的 **push** 和 **pop** 宏，这意味着这些栈是用 cons 单元链表实现的，而不是大多数 Forth 中使用的数组数据结构。 抽象寄存器 **pc** 是**程序计数器**的缩写，一个指向我们当前正在执行的代码的指针。Forth 代码是什么以及我们如何指向它，将很快解释，我们的抽象寄存器 **compiling** 和 **dtable** 也是如此。 ### Forth 单词 ```lisp (defstruct forth-word name prev immediate thread) ``` Forth 的另一个构建块是其**字典**概念。Forth 字典是一个由 Forth **单词**组成的单向链表，类似于 Lisp 的函数²（https://letoverlambda.com/textmode.cl/guest/chap8.html#）。单词用 Lisp **结构体**表示。结构体是高效的基于槽的数据结构，通常实现为向量。**name** 槽用于在字典中查找单词的符号。注意，Forth 字典不是按字母顺序存储，而是按时间顺序。当我们添加新单词时，我们将其追加到字典末尾，这样遍历字典时最先检查最新定义的单词。字典的最后一个元素始终存储在抽象寄存器 **dict** 中。要遍历字典，我们从 **dict** 开始，沿着单词结构的 **prev** 指针，该指针指向之前定义的单词，或者如果我们在最后一个单词处，则指向 **nil**³（https://letoverlambda.com/textmode.cl/guest/chap8.html#）。 ### Forth 查找 ```lisp (defun forth-lookup (w last) (if last (if (eql (forth-word-name last) w) last (forth-lookup w (forth-word-prev last))))) ``` 给定要查找的单词 **w** 和要搜索的字典 **last**，**forth-lookup** 将返回一个 Forth 单词结构或 **nil**，取决于单词 **w** 是否在字典中找到。使用比较函数 **eql** 而不是 **eq**，因为——与 Lisp 不同——Forth 允许单词由数字和其他非符号命名。 我们 Forth 单词的 **immediate** 槽是一个标志，指示该单词是否为**立即**单词。立即性是 Forth 的元编程概念，我们将在后面深入探讨。现在先给出一个粗略的类比：立即单词类似于 Lisp 宏，因为它们是 Forth 中在编译时而非运行时执行的函数。什么？只有 Lisp 才应该有宏。虽然 COMMON LISP 的宏系统确实比任何其他宏系统都要强大——包括最好的 Forth 实现——但 Forth 的扩展能力超越了几乎所有其他语言。和 Lisp 一样，这种能力源于一种设计哲学：如果它对于语言实现者足够好，那么对于应用程序编程者也足够好。和 Lisp 一样，Forth 并不真正认可原语的概念。相反，它提供了一套**元原语**，可以组合起来构建你——程序员——所期望的语言。和 Lisp 一样，与大多数 Blub 语言不同，通过宏以新颖的方式扩展语言不仅是可能的，而且是受到鼓励的。和 Lisp 一样，Forth 关乎的不是风格，而是力量。 ### Cons 线程代码 在上一节中，我们专注于抽象寄存器。这些寄存器是重要的焦点，这就是为什么 Forth 哲学认为它们如此基础，但这些寄存器实际上只是一个更通用概念的一部分：**抽象机器**。不同 Forth 系统最显著的区别可能是它们对**线程代码**的实现。Forth 所说的线程代码与常规意义上抢占式调度的共享内存进程非常不同⁴（https://letoverlambda.com/textmode.cl/guest/chap8.html#）。Forth 线程与并发无关。它们是一个讨论代码编译和元编程的框架。 尽管 Lisp 提供了对符号的树数据结构⁵（https://letoverlambda.com/textmode.cl/guest/chap8.html#）的访问，你的程序从这些符号编译而来，在组装到内存之前以这些符号表示，而 Forth 不提供符号操作。相反，Forth 提供了对将代码组装（线程化）到内存这一过程的访问。虽然对外人来说，Forth 最明显的特征是它的栈和后缀表示法，但实际上使 Forth 成为 Forth 的是线程。Forth 关乎栈的方式与 Lisp 关乎列表的方式相同：它们恰好是解决元编程问题最适用的数据结构——而这正是 Forth 和 Lisp 真正关心的。 经典的线程样式被称为**间接线程**代码，但大多数现代 Forth 都是用**直接线程**代码实现的。区别在于一层间接性。这种间接性对底层效率的影响取决于底层处理器，我们在此不详细讨论。有许多关于 Forth 线程的优质教程 [STARTING-FORTH] [MOVING-FORTH]。在内存中，这些线程样式都由相邻的**单元**组成，这些单元是表示指针的定长机器字。一段紧凑的机器代码称为**内解释器**，通常针对所使用的处理器定制，因为它有重要的工作：跟随这些 Forth 线程的指针，沿途解释它们的含义。遇到一个单元时的默认行为是将当前程序计数器位置压入返回栈，然后将程序计数器指向单元中包含的内容。当内解释器到达线程末尾时，它弹出返回栈并在该位置恢复执行——它离开的地方⁶（https://letoverlambda.com/textmode.cl/guest/chap8.html#）。 可以想象，这种程序存储方式使得程序极其紧凑。一个编译后的 Forth 单词只是一个连续的定长数数组，其中大多数表示指向其他单词的指针。这一直是 Forth 的优势之一。由于将程序线程化到内存的透明性，Forth 允许对许多编程权衡进行精细控制，包括最重要的一个：执行速度与程序大小。线程代码让我们能够尽可能接近问题来优化抽象，从而产生极快、极小的程序。但正如 Lisp 宏不仅仅关乎效率，Forth 线程也是如此。和 Lisp 程序员一样，Forth 程序员更倾向于将自己视为实现者而非仅仅用户。Forth 和 Lisp 都关乎控制——制定你自己的规则。 至少还有其他两种常见的 Forth 线程技术：**标记线程**代码和**子程序线程**代码。它们在考虑速度与大小的权衡时代表了两个相反的方向。有时这些线程技术与间接和直接线程代码共存于同一个 Forth 中。标记线程涉及通过使用甚至比指针更小的定长数来表示线程中的单词，从而增加另一层间接性。在光谱的另一端是子程序线程。这种类型的线程代码正变得越来越流行，最好的现代 Forth 编译器部分使用子程序线程。与内解释器跟随的连续单词指针不同，子程序线程代码存储**内联**机器指令来调用这些指针。在子程序线程代码中，内解释器消失了——它实际上由硬件（或虚拟机）实现。子程序线程代码通常被认为是一个不透明的块，只能由特殊的、不可编程的编译器操作。特别是当对代码进行各种优化时，这些不透明块看起来完全不像统一的、基于单元的线程。几乎所有非 Forth 编译器只编译到子程序线程代码，并且不认为你会想要做其他任何事情，导致了这样一个特殊的定义： **Flub** 是一种只考虑子程序线程代码的语言，或者一种只提供子程序线程代码的语言实现。 例如，C 是一种 Flub，因为它只提供程序员创建函数的手段——子程序线程代码的不透明块。当然，我们可以在 C 中实现一个内解释器来处理间接线程代码⁷（https://letoverlambda.com/textmode.cl/guest/chap8.html#），并用此程序自举一个基于栈的语言，但那样我们就不再是用 C 编程了。几乎所有的 Blub 语言都是 Flub。 我们刚才描述的作为抽象机器的 Forth，不是 Flub。正如我们将看到的，Forth 赋予程序员/实现者对其程序如何编译的大量控制。 Lisp 是 Flub 吗？有趣的是，Lisp 很可能是第一种非 Flub 编程语言，但大部分已经变成了 Flub。尽管标准没有严格规定，但大多数 COMMON LISP 编译器只将函数编译为不透明的机器代码块，因此是 Flub。但在非常早期的 Lisp 版本中，函数存储为列表——一种奇怪的代码线程，并非完全不同于 Forth 线程。虽然这确实允许一些非常巧妙的运行时技巧，包括为循环代码赋予意义，但效率低得令人绝望。与 Forth 的多种线程类型不同——它们已在几乎所有架构上高效实现——Lisp 函数的这种内部表示是不可容忍的，因此 Lisp 被改变以允许（极其）高效的代码。对于元程序员来说，其结果是大多数 COMMON LISP 实现都是 Flub。但有些特性是语言无法添加的，而有些特性我们可以通过宏添加，这两者之间存在区别。通过宏，我们可以以任何方式扩展语言，它仍然是 Lisp。COMMON LISP 缺少线程代码，就像缺少延续和一等宏一样：它们是被有意从语言中省略的，留给宏编写者根据需要实现。本章及其代码最重要的成果之一是表明，即使它们是 Flub，Lisp 语言也可以通过宏转化为非 Flub 语言。非 Blub 意味着非 Flub，换句话说，如果你不能将一种语言变成非 Flub，那它一定是 Blub。