Newsgroups: comp.lang.scheme
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!mintaka!mintaka.lcs.mit.edu!alan
From: alan@lcs.mit.edu (Alan Bawden)
Subject: Re: Letrecs and continuations
In-Reply-To: carlton@husc8.harvard.edu's message of 18 May 91 15:14:07 GMT
Message-ID: <ALAN.91May20014925@transit.lcs.mit.edu>
Sender: news@mintaka.lcs.mit.edu
Organization: ITS Preservation Society
References: <CARLTON.91May18111407@husc8.harvard.edu>
Distribution: comp
Date: 20 May 91 01:49:25
Lines: 99

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.