方案letrec无限环境

Question

我目前正在计划中编写元级评估器，遵循SICP的步骤。

在练习中，我被要求实现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)))

我有错过什么吗？

(http://goo.gl/oW5j0z)。

Answer 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*，它按左、右、右顺序计算变量绑定的表达式(Scheme本身没有指定参数的计算顺序)：

语法: letrec*绑定主体 类似于‘letrec’，除了INIT表达式按顺序绑定到它们的变量之外。因此，‘letrec *’放宽了letrec限制，因为以后的INIT表达式可能引用以前绑定的变量的值。

更正确的代码是：

(let ((x1 *unassigned*) ... (xn *unassigned*))
  (let ((t1 ...) ... (tn ...))
    (set! x1 t1)
    ...
    (set! xn tn))
  body)