[comp.lang.scheme] Letrecs and continuations

carlton@husc8.harvard.edu (david carlton) (05/18/91)

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

alan@lcs.mit.edu (Alan Bawden) (05/20/91)

In article <CARLTON.91May18111407@husc8.harvard.edu>
carlton@husc8.harvard.edu (david carlton) writes:

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

   [...] the standard-specified macro expansion [...]

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

   [...]  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))))

I expect that you are right.  I note that the text accompanying the
macro expansion for LETREC in R3RS remarks:

  The second LET expression in the expansion is not strictly necessary, but
  it serves to preserve the property that the <init> expressions are
  evaluated in an arbitrary order.

This seems to imply that the writer believed that 

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

was also an acceptable implementation of LETREC, but this was unsuitable
for the standard because it specified the order of evaluation.  I don't
think the writer realized he had accidentally specified that all the
assignments must take place -after- all the initializers were evaluated.
(Probably he thought there was no way to detect that.)

A different expansion might have been:

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

which might result in either 1 or 2.  (But still overspecifies the
situation, since now evaluating initializers and performing assignments
must alternate.)

   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?

I think your analysis is correct.  I'm not sure it is a bug, since I am not
certain the standard really intended to specify the behavior in that case.

I can't resist bringing up the bizarre construction I discovered a couple
of years ago that combines LETREC and CALL-WITH-CURRENT-CONTINUATION to
create an object with state -- using nothing else except pure Lisp:

  (define (make-cell)
    (call-with-current-continuation
      (lambda (return-from-make-cell)
	(letrec ((state
		   (call-with-current-continuation
		     (lambda (return-new-state)
		       (return-from-make-cell
			 (lambda (op)
			   (case op
			     ((set)
			      (lambda (value)
				(call-with-current-continuation
				  (lambda (return-from-set)
				    (return-new-state
				      (list value return-from-set))))))
			     ((ref) (car state)))))))))
	  ((cadr state) 'done)))))

  (define (set-cell! cell value)
    ((cell 'set) value))

  (define (ref-cell cell)
    (cell 'ref))

This takes advantage of essentially the same peculiarities in the
specification of LETREC that you discovered.

Robert Hieb <hieb@heston.cs.indiana.edu> (05/20/91)

alan@lcs.mit.edu (Alan Bawden) writes:

>I expect that you are right.  I note that the text accompanying the
>macro expansion for LETREC in R3RS remarks:

>  The second LET expression in the expansion is not strictly necessary, but
>  it serves to preserve the property that the <init> expressions are
>  evaluated in an arbitrary order.

>This seems to imply that the writer believed that 

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

>was also an acceptable implementation of LETREC, but this was unsuitable
>for the standard because it specified the order of evaluation.  I don't
>think the writer realized he had accidentally specified that all the
>assignments must take place -after- all the initializers were evaluated.
>(Probably he thought there was no way to detect that.)

R^3.99, section 4.2.2, states that for a "letrec":

   Semantics:  The <variable>s are bound to fresh locations
   holding undefined values, the <init>s are evaluated in the
   resulting environment (in some unspecified order), each
   <variable> is assigned to the result of the corresponding
   <init>, the <body> is evaluated in the resulting environment,
   and the value of the last expression in <body> is returned.

This implies that the evaluation of all the initial values takes place
before any of the values are assigned to their respective variables.
That is what the rewrite rule for "letrec" in section 7.3 does, but the
above does not, so it may not be accidental after all.

One can still get away with optimizing the implementation of "letrec",
but only in special circumstances.  In particular one must watch out
for complex right-hand-sides and assigned variables.  Doing so would
seem to rule out treating "letrec" as a derived form (macro), since it
is not reasonable for the expander to do such complex analysis.

As a side point, the statement that the variable locations are
initialized with "undefined" values also makes expanding "letrec" as a
macro undesirable.  The original posting used "#f", which is rather
well defined.  I suppose that, since the meaning of "undefined" is not
specified, one could substitute "unspecified value," but that doesn't
seem to be the intent.

This is certainly an area that should be cleared up.

alan@lcs.mit.edu (Alan Bawden) (05/21/91)

In article <1991May20.092814.27355@news.cs.indiana.edu>
hieb@heston.cs.indiana.edu (Robert Hieb) writes:

   R^3.99, section 4.2.2, states that for a "letrec":

      Semantics:  The <variable>s are bound to fresh locations
      holding undefined values, the <init>s are evaluated in the
      resulting environment (in some unspecified order), each
      <variable> is assigned to the result of the corresponding
      <init>, the <body> is evaluated in the resulting environment,
      and the value of the last expression in <body> is returned.

   This implies that the evaluation of all the initial values takes place
   before any of the values are assigned to their respective variables.
   That is what the rewrite rule for "letrec" in section 7.3 does, but the
   above does not, so it may not be accidental after all.

Yup, I agree, that does say it.  I still wonder, though, if it might be
accidental overspecification.  Certainly several implementation have been
demonstrated to be unaware of this aspect of LETREC's behavior -- so I can
easily imagine this is an issue that was never discussed by the R^nRS
authors before.