no continuations

oleg at oleg at
Sun Jan 11 16:56:35 EST 2004

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)
    (lambda (k)
      (set! *k*
	(lambda ()
	  (set! *k* #f)
	  (k alt2)))

(define (fail) (*k*))

    ((val1 5)
      (proc (amb
	      (lambda ()
		(display "In first choice") (newline)
	      (lambda ()
		(display "The second choice") (newline)
      (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.

More information about the Haskell-Cafe mailing list