Scheme letrec infinite environment

Question

I'm currently writing metacircular evaluator in Scheme, following the SICP book's steps.

In the exercise I am asked to implement letrec, which I do in the following way:

(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))))))

However, when I evaluate the expression as follows, it goes into infinite loop:

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

Do I miss anything?

(Full Source Code at GitHub).

did your code ever worked for the simplest cases like (let ((x 1)) x)? — Will Ness
this question is misleading. the problem in that code is at much deeper (earlier) level and has nothing to do specifically with letrec. — Will Ness

Victor Fedotov Victor Fedotov · Accepted Answer · 2014-03-16T13:04:29

I checked result transformation result of (let ((x 1)) x) and got:

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

instead of:

((lambda (x) x) 1)

obviously problem is in let body processing. If I were you, I would use utility function:

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

By the way: I would say, that your letrec implementation is not very correct. Your transformation returns:

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

It much more resembles letrec* which evaluates expressions for variable bindings in left-ro-right order (Scheme itself doesn't specify arguments evaluation order):

syntax: letrec* bindings body

 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.

The more correct code would be:

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

Scheme letrec infinite environment

1 Answers