[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

letrec and set!

Sorry folks, but my first message didn't seem to make it through. The test
message did -- and my mailbox now overflows... :-(

   Date: Thu, 19 Aug 93 08:14:04 +0200
   From: Christian Queinnec <Christian.Queinnec@inria.fr>
   Reply-To: Christian.Queinnec@inria.fr

   It is written in R4RS section 4.2.2 that "One restriction on letrec is very
   important: it must be possible to evaluate each <init> without ASSIGNING
   or referring to the value of any <variable>. Why assigning is forbidden ?
   It rules out some programs that are unambiguous such as:

   (letrec ((x (begin (set! y 1)
		      y ))
	    (y 3) )
     x )
		 ---> 1

   The value of y is not foreseeable but the result of x seems clear. 


I'd say that this restriction allows an implementation to defer the
allocation of the actual location of y until y is initialized.  While
it is known in advance where this location will be (to allow other
initializers to refer to that location) it can only be read or written
safely after all variables are initialized.

I think that the main use of the restriction comes from the introduction
of explicit value cells for writable variables.  Your program fragment
(after the transformation) would look like:

(letrec ((x (begin (assign-to-cell! y 1) (refer-to-cell y)))
         (y (make-cell 3)))

Obviously, the location (cell) assigned to by ``assign-to-cell!'' does not
exist until y is initialized.

Of course, a ``smart'' compiler could recognize that y is not used otherwise
and translate the fragment to:

(letrec ((x 1) (y <unknown>)) x) -> (letrec ((x 1)) x) -> 1

However, it seems difficult to formalize the rules under which a compiler
would be REQUIRED to do this kind of optimization, therefore the whole
think is simply said to be illegal.


PS: Indeed, I had some trouble with the correct implementation of
letrec in VSCM.  In fact, if the compiler is not able to detect
violations of the rule then it better allocates the location in
advance (otherwise an access to a non-existent location could cause
big trouble -- and we really don't want to see ``segmentation
violation - core dumped'' messages when running a Scheme program). The
trouble is that it is not possible to detect all violations of this
rule statically.