scheme - 如何实现 let* in scheme？

Question

我正在尝试学习 scheme 并尝试在 scheme 中为 let* 实现解释器。这是语法:

<s6> -> <expr>                   
       | <define>
<expr> -> NUMBER | IDENT | <if> | <let> | <letstar> | <lambda> | <application>
<define> -> ( define IDENT <expr> )
<if> -> ( if <expr> <expr> <expr> )
<let> -> ( let ( <var_binding_list> ) <expr> )
<letstar> -> ( let* ( <var_binding_list> ) <expr> )
<lambda> -> ( lambda ( <formal_list> ) <expr> )
<application> -> ( <operator> <operand_list> )
<operator> -> <built_in_operator> | <lambda> | IDENT
<built_in_operator> -> + | * | - | /
<operand_list> -> <expr> <operand_list> | empty
<var_binding_list> -> ( IDENT <expr> ) <var_binding_list> | ( IDENT <expr> )
<formal_list> -> IDENT <formal_list> | IDENT

之前学习过let的实现，这里是:

(define let-stmt? (lambda (e)
(and (list? e) (equal? (car e) 'let) (= (length e) 3))))

(define get-value (lambda (var env)
(cond
    ((null? env) (error "s6-interpret: unbound variable -->" var))
    ((equal? (caar env) var) (cdar env))
    (else (get-value var (cdr env))))))

(define s6-interpret (lambda (e env)     //thanks to GoZooner
(cond
    ((number? e) e)
    ((symbol? e) (get-value e env))
    ((not (list? e)) (error "s6-interpret: cannot evaluate -->" e))

    ((let-stmt? e)
        (let ((names (map car  (cadr e)))
                (inits (map cadr (cadr e))))

        (let ((vals (map (lambda (init) (s6-interpret init env)) inits)))

        (let ((new-env (append (map cons names vals) env)))

        (s6-interpret (caddr e) new-env)))))

我如何修改 let 的解释器，以便我可以为 let* 编写解释器？谁能帮忙？

谢谢

Answer 1

这个问题最近被问过好几次了，在 Scheme 问题列表中向下滚动。这是它的要点:let* 是一个语法转换，在 SICP 中阅读更多关于这个主题的信息。 ，查找标题为“派生表达式”的部分。这种情况的关键思想是，每当你的评估者发现这样的表达式时:

(let* ((a 10)
       (b (+ 10 a)))
  (+ a b))

...您可以直接将其转换为等效的一系列嵌套 lambda 应用程序，可以像这样轻松评估:

((lambda (a)
   ((lambda (b)
      (+ a b))
    (+ 10 a)))
 10)

或者，您可以执行一个中间步骤，首先将 let* 转换为一系列嵌套的 let，然后对它们求值 - 如果您已经已经实现了 let 特殊形式。上面的相同示例如下所示:

(let ((a 10))
  (let ((b (+ 10 a)))
    (+ a b)))

当然，首先您必须知道如何计算lambda 形式。这里的重点是，let 和 let* 都是特殊形式(只不过是语法糖)，它们不遵循相同的评估模型，比如说，程序应用程序，并且需要在求值器级别进行特殊处理 - 在这种情况下，是一种语法转换，它会产生我们知道如何求值的不同表达式。