lisp - 是否有使用正序求值的 Scheme 解释器？

Question

我一直在慢慢完成 Structure and Interpretation of Computer Programs 中的练习.科1.1.5谈到应用与正常顺序评估，这个话题后来在课文中多次出现。由于解释器使用应用顺序评估，因此只需在代码中插入 display 调试语句即可轻松查看其工作原理。能够对正常顺序评估做同样的事情将有助于我的理解。

有谁知道使用正常顺序求值而不是应用顺序来实现的 Scheme(或 Lisp)解释器？

更新:

这是一个从 SICP 中给出的例子修改而来的简短例子。我将定义自己的 add 过程来打印参数，并使用书中的 square 过程。

(define (add x y)
  (display x)
  (display y)
  (newline)
  (+ x y))

(define (square x) (* x x))

现在，如果我使用应用顺序求值运行短程序 (square (add 1 2))，则只会计算 (add 1 2) 的结果一旦传递给 square 过程。操作数 12 应该在最终结果之前打印一次。我们可以在解释器中运行它来验证是否发生了这种情况。

> (square (add 1 2))
12
9

不过，使用正常顺序求值，应该将单个操作数 (add 1 2) 复制到 square 过程中，它的求值为 (* (加 1 2)(加 1 2))。操作数 12 应该在最终结果之前打印两次。

我希望能够在执行正常顺序评估的解释器中运行它，以验证它确实是这样工作的。

Answer 1

事实证明，Scheme 实际上已经附带了一个本质上是正序求值器的东西。它们是您可能听过很多的传说中的宏，我们可以重写 1.1.4--1.1.5 节的示例，以使用宏扩展代替过程应用程序，相当容易:

(define (print . items)
  (for-each display items))

(define-macro (add x y)
  `(begin (print "[ADD " ',x " " ',y "]")
          (+ ,x ,y)))

(define-macro (mul x y)
  `(begin (print "[MUL " ',x " " ',y "]")
          (* ,x ,y)))

(define-macro (square x)
  `(begin (print "[SQUARE " ',x "]")
          (mul ,x ,x)))

(define-macro (sum-of-squares x y)
  `(begin (print "[SUM-OF-SQUARES " ',x " " ',y "]")
          (add (square ,x) (square ,y))))

(define-macro (f a)
  `(begin (print "[F " ',a "]")
          (sum-of-squares (add ,a 1) (mul ,a 2))))

忽略 PRINT，它们的逻辑有点超出您在文本中的位置，但它们只是许多 DISPLAY 的简写。实际上，您可能希望完全放弃逐印描摹，转而使用系统的宏扩展功能。但这因实现而异(例如，在 Ypsilon 中，您将使用 (macro-expand '(f 5)))。

如果你加载这些定义(需要注意的是 DEFINE-MACRO 是非标准的，但在实践中这应该不是问题，因为大多数方案都提供它)，然后评估 (f 5) 就像这本书一样会打印出来(当然我稍微美化了它):

[F 5]
[SUM-OF-SQUARES (add 5 1) (mul 5 2)]
[ADD (square (add 5 1))         (square (mul 5 2))]
     [SQUARE (add 5 1)]
     [MUL (add 5 1) (add 5 1)]
          [ADD 5 1]
                    [ADD 5 1]
                                [SQUARE (mul 5 2)]
                                [MUL (mul 5 2) (mul 5 2)]
                                     [MUL 5 2]
                                               [MUL 5 2]
136

这或多或少是书中说明的过程应该是什么。

---

写这些宏基本上就像写一个普通的过程，除了

• 使用 DEFINE-MACRO 代替 DEFINE。
• 正文中没有隐式 BEGIN，因此如果您有多个表达式，则需要提供自己的 BEGIN。
• 整个 body 表情都带有重音前缀。
• 参数的所有实例都以逗号为前缀。

这就是编写方案宏 101。

现在总而言之，仅仅在 SICP 的第一章就对某人使用宏有点愚蠢。但是如果你说你在修改 Racket 来做你想做的事情时遇到了过多的困难(然后有些人根本不使用 Racket)，那么这里有一个替代方案。