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

Question

我尝试设计一个非递归的Scheme解释器,使用堆栈和指针在AST上行走并进行评估.

如果我只需要处理纯过程调用,情况就好了.但是,一旦宏出现,不规则的语法就很难编写非递归例程.(因为不同语义的混合)更糟糕的是,当考虑内置宏(如if,conf let等)时,非递归方法似乎变得异常复杂.

关于实现非递归解释器的任何好建议？或者那些材料？我用Google搜索但没有发现任何东西.

而且,我想知道主流的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