Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!samsung!think.com!hsdndev!husc6!carlton
From: carlton@husc8.harvard.edu (david carlton)
Newsgroups: comp.lang.scheme
Subject: Letrecs and continuations
Message-ID: <CARLTON.91May18111407@husc8.harvard.edu>
Date: 18 May 91 15:14:07 GMT
Sender: news@husc6.harvard.edu
Distribution: comp
Organization: Citizens for Boysenberry Jam
Lines: 86

Was playing around with some friends last night and we came up with
the following bit of code:

(letrec ((v 0)
         (k (call/cc (lambda (x) x))))
  (set! v (+ v 1))
  (k (lambda (x) v)))

(where call/cc = call-with-current-continuation.)

I think that it should return 1, and indeed when I perform the
standard-specified macro expansion (which I don't particularly like,
but that's another story), I get

(let ((v #f)
      (k #f))
   (let ((t1 0)
         (t2 (call/cc (lambda (x) x))))
      (set! v t1)
      (set! k t2))
   (set! v (+ v 1))
   (k (lambda (x) v)))

which does in fact return 1.  But the original returned 2 on all four
Scheme implementations I tried... (Gambit, MIT Scheme, Chez, and T's
Scheme mode.  Admittedly not the most recent versions of all of
those.)  Am I just being stupid, or is this really a pervasive bug?
The only thing that I could think of that might explain what is going
on is that the implementations were 'optimizing' my original
expression to

(let ((v 0))
  (letrec ((k (call/cc (lambda (x) x))))
    (set! v (+ v 1))
    (k (lambda (x) v))))

in an effort to produce as good code as possible in a letrec
expression by avoiding set!'s of local variables as much as possible.
And I would have claimed before last night that that transformation
was valid, but in light of the example above it doesn't seem to be.

Also, another interesting factoid that came out of this is that 

(letrec defns body)

and 

(let defns body)

aren't necessarily equivalent even if none of the RHS's of the defns
refer to the variables on the LHS's of the defns: consider the
following code:

(define count 0)

(letrec ((v 0)
         (k (call/cc (lambda (x) x))))
  (set! count (+ count 1))
  (set! v count)
  (k (lambda (x) v)))

It returns 2, but when you replace the 'letrec' by a 'let' it returns
1.  Interesting, eh?

In case you're curious, this whole thing arose when a friend showed me
that another optimization involving replacing let's by let*'s when
none of the RHS's of the definitions referred to the variables on the
LHS's didn't work:

(let[*] ((v 0)
         (k (call/cc (lambda (x) x))))
  (set! v (+ v 1))
  (k (lambda (x) v)))

returns 2 if it is a let*, 1 if it is a let.


So am I analyzing things properly, and is this a bug in all of those
implementations' treatment of letrec, or am I missing something here?
Continuations can certainly be weird enough that I can well believe
that I could be missing something...  At any rate, I thought that this
was a weird enough situation that people might not be familiar with it
and would be interested in it.

david carlton
carlton@husc9.harvard.edu