2

我试图设计一个非递归的 Scheme 解释器，使用堆栈和指针在 AST 上行走和评估。

如果我只需要处理纯过程调用，一切都很好。然而，一旦出现宏，不规则的语法使得编写非递归例程变得困难。（因为混合了不同的语义）更糟糕的是，当考虑到内置宏（如 if、conf let 等）时，非递归方法似乎变得异常复杂。

关于实现非递归解释器有什么好的建议吗？或者有什么相关资料？我用谷歌搜索，但什么也没找到。

而且，我想知道主流的 Scheme 解释器是否使用这种方法。也许我可以只写递归，它不会受到指责。

4

2 回答 2

6

在 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
于 2013-07-29T13:56:38.553 回答
4

Whle researching for my Scheme compiler I have read lots of papers about all sorts of old problems related to compilation. Related to macros and @jozefg's nice illustration of separating actual interpreting and macro espansions that I found was Alexpander, written by Al Petrofsky. He has also written Eval in one define, which is a nice interpreter with syntax-rules.

I have previously written a Lisp1 interpreter that runs on Brainf*ck. It had a stack with alternating cell addresses to set-car! the result and the expression to be evaluated.

Eval is something like this:

(pop_stack register1) ; expression
(while-not-zero register1
   ... do computation
   (pop_stack register2) ; return address
   (open-cons register2) ; opens location
   (set-car register1)   ; sets value 
   (pop_stack register1)) ; next job

It supports standard McCharty LISP1 stuff, including macros (flambda).

A simple expression like (cons 'a 'b) used 6 rounds in the while loop, like this:

  1. (cons 'a 'b)
  2. cons => procedure:cons
  3. (pre-apply procedure:cons 'a 'b)
  4. 'a => a
  5. 'b => b
  6. (apply procedure:cons 'a 'b)

Because of this i could rename every keyword. Eg. this works:

(let ((mylambda lambda))
   (mylambda (x) (cons '1 x)))
于 2013-07-29T17:00:24.643 回答