是否有使用常规顺序评估的Scheme解释器？

Question

通过计算机程序的结构和解释练习,我一直在慢慢地工作.第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))使用applicative-order评估运行短程序,结果(add 1 2)将只计算一次然后传递给square过程.操作数12应在最终结果之前打印一次.我们可以在解释器中运行它来验证这是发生了什么.

> (square (add 1 2))
12
9

但是,使用正常顺序评估时,(add 1 2)应将单个操作数复制到square过程中,该过程将评估为(* (add 1 2) (add 1 2)).操作数12应在最终结果之前打印两次.

我希望能够在一个执行正常顺序评估的解释器中运行它,以验证它确实是如何工作的.

Answer 1

Racket有一种懒惰的语言.它不仅仅是一个解释器,因为你可以编写由普通球拍模块和懒人组成的程序.

至于使用打印输出进行调试 - 您可以使用这种惰性语言进行调试,并在Haskell中获得类似于不安全IO的内容.尽管如此,这仍然会令人困惑.(如果你想要一个解释器堵塞打印到它,它会也引起混乱,因为它遵循了懒惰评估...)

Answer 2

事实证明,Scheme实际上已经是一个基本上是正常的评估者.它们是您可能已经听过的那些传说中的宏,我们可以重写1.1.4--1.5.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.
• 整个身体表情以重音为前缀.
• 参数的所有实例都以逗号为前缀.

那就是写作方案宏101.

现在总而言之,在SICP的第一章中,对某人来说,这是一个有点愚蠢的问题.但是如果你说你在修改Racket以实现你想要的东西(然后有些人根本没有使用Racket)时会遇到过多的困难,那么这里就是另一种选择.