2

我目前正在按照 SICP 书的步骤在 Scheme 中编写元循环评估器。

在练习中，我被要求实施letrec，我按照以下方式进行：

(define (letrec->let exp)
  (define (make-unassigned var)
    (list var '*unassigned*))
  (define (make-assign binding)
    (list 'set! (letrec-binding-var binding)
          (letrec-binding-val binding)))
  (let ((orig-bindings (letrec-bindings exp)))
    (make-let
     (map make-unassigned
          (map letrec-binding-var orig-bindings))
     (sequence->exp
      (append
       (map make-assign orig-bindings)
       (letrec-body exp))))))

但是，当我按如下方式评估表达式时，它会进入无限循环：

(letrec
  ((a (lambda () 1)))
  (+ 1 (a)))

我想念什么吗？

（GitHub 上的完整源代码）。

4

1 回答 1

1

我检查了结果转换结果(let ((x 1)) x)并得到：

((lambda (x) (x)) 1)

代替：

((lambda (x) x) 1)

显然问题在于let身体处理。如果我是你，我会使用效用函数：

(define (implicit-begin exps)
  (if (= 1 (length x))
      (car x)
      (cons 'begin x)))

顺便说一句：我想说，你的letrec实现不是很正确。您的转换返回：

(let ((x1 *unassigned*>) ... (xn *unassigned*))
  (set! x1 ...)
  ...
  (set! xn ...)
  body)

它更类似于letrec*以左右顺序评估变量绑定的表达式（方案本身没有指定参数评估顺序）：

语法：letrec* 绑定体

 Similar to ‘letrec’, except the INIT expressions are bound to their
 variables in order.

 ‘letrec*’ thus relaxes the letrec restriction, in that later INIT
 expressions may refer to the values of previously bound variables.

更正确的代码是：

(let ((x1 *unassigned*) ... (xn *unassigned*))
  (let ((t1 ...) ... (tn ...))
    (set! x1 t1)
    ...
    (set! xn tn))
  body)
于 2014-03-16T13:04:29.260 回答