scheme - 如何在没有递归的情况下实现Scheme解释器？

Question

我尝试设计一个非递归的Scheme解释器，使用堆栈和指针来遍历AST并进行评估。

如果我只需要处理纯过程调用，那就没问题了。然而，一旦宏出现，不规则的语法就很难编写非递归例程。 (由于不同语义的混合)更糟糕的是，当考虑到内置宏(如 if、conf let 等)时，非递归方法似乎变得异常复杂。

关于实现非递归解释器有什么好的建议吗？或者有这方面的 Material 吗？我用谷歌搜索了一番，但一无所获。

而且，我想知道主流的Scheme解释器是否使用这种方式。也许我可以直接写递归就不会被指责了。

Answer 1

在 vanilla r5rs 方案中，宏只是用于重新排列 AST 的 DSL。它们在纯粹的语法级别上运行，应该与解释器分开。

在 R6RS 或 CL 等中，宏实际上可以进行计算，这意味着它们需要运行 2 次解释器，一次用于扩展宏，一次用于评估生成的 AST。

例如给出这段代码

 (let ((x 5))
   (if (= x 5)
       (display "Woohoo")
       (error)))

您应该在离开 AST 的第一阶段对其运行宏扩展器

 ((lambda (x)
    (cond
      ((= x 5) (display "Woohoo"))
      (else (error)))) 5)

这样做应该评估无代码。只需重新排列 AST。然后，当你的解释器运行它时，它甚至不需要知道宏的存在。

所以你的最终方案解释器应该如下所示

Parse File
   |
   |
   |
Expand All Macros
   |
   |
   |
Optimize/Black Magic
   |
   |
   |
Optional ByteCode compilation or similar IL
   |
   |
Evaluate
   |
   |
Profit