Схема летрека бесконечной среды

Question

В настоящее время я пишу метациркуляционный оценщик в Scheme, следуя инструкциям книги 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)))

Я что-то пропустил?

( Полный исходный код на GitHub).

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* который оценивает выражения для привязок переменных в порядке слева направо (сама схема не определяет порядок вычисления аргументов):

синтаксис: 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)