I tried the following letrec correctness test using your interpret.php, and unfortunately, the interpreter returned no answer. (let ((cont #f)) (letrec ((x (call-with-current-continuation (lambda (c) (set! cont c) 0))) (y (call-with-current-continuation (lambda (c) (set! cont c) 0)))) (if cont (let ((c cont)) (set! cont #f) (set! x 1) (set! y 1) (c 0)) (+ x y)))) Could you tell me what does this test return on your system? Now, why the exact implementation of letrec is important. Let us consider the following code that involves a non-deterministic choice. (define *k* #f) ; A rough-and-dirty ambient combinator. It's easier to write it ; than to look it up... (define (amb alt1 alt2) (call-with-current-continuation (lambda (k) (set! *k* (lambda () (set! *k* #f) (k alt2))) alt1))) (define (fail) (*k*)) (display (letrec ((val1 5) (proc (amb (lambda () (display "In first choice") (newline) (fail)) (lambda () (display "The second choice") (newline) 42))) (val2 7) ) (let ((old-vals (list val1 val2))) (set! val1 '*bad*) (set! val2 '*bad*) (list old-vals (proc))))) So, we bind val1 to 5, val2 to 7, and proc to the first choice. We proceed to evaluate the body of letrec with the first choice. We mutate val1 and val2, and evaluate our first choice, which didn't work out. So, we try the second choice. The correct implementation of letrec (e.g., Petite Chez Scheme, SCM) will *restore* the values of val1 and val2! That is, the changes made during the evaluation of the first choice will be backed out, and we start the second choice using the same original values of val1 and val2. Choices must indeed be evaluated in the same "environment", otherwise, they can't be called non-deterministic. So, if we evaluate the test on a conforming Scheme implementation, we get In first choice The second choice ((5 7) 42) Alas, many Scheme systems do not implement letrec correctly. Therefore, when we try the program on one of these systems (e.g., Gambit, Bigloo, Scheme48), we see In first choice The second choice ((*bad* 7) 42) A sad interaction between the choices.