expansion of LETREC

[Jonathan A Rees <JAR@MC.LCS.MIT.EDU>]

I would like to put a little more detail in the report about the
distinction between the "syntactic sugar" special forms (COND etc.) and
the "primitive" or "core" ones (QUOTE IF LAMBDA BEGIN SET!).  The
distinction is a good one to make even in the absence of macros.  This
isn't hard to do for any of the special forms except for LETREC.  The
following almost works:

(letrec ((v1 x1) (v2 x2) ...) body)  ==>

(let ((v1 <unspecified>) (v2 <unspecified>) ...)
  (let ((temp1 x1) (temp2 x2) ...)    ;Note unspecified evaluation order
    (set! v1 temp1)    ;temp1 etc. are vars which don't occur free in body
    (set! v2 temp2)
    ...
    body))

But this ultimately doesn't foot the bill because it fails to say that
it is an error to reference the bound variables before they're
initialized.  This is very different from the variables having
unspecified values, since if the variable has an unspecified value it
cannot be an error to access that value, even though it may be an error
to do anything with it.

Let me describe the alternative solutions that have occurred to me:

1. Say that LETREC is "almost not primitive" except for this one quirk.
That's probably the status quo position.  This is bad because it
increases the number of primitives from 5 to 6, and because there are
now two variable binding constructs instead of one.  LETREC is so close
to being syntactic sugar that it would be a shame if it wasn't
first-class syntactic sugar.

2. Legitimize this actually quite useful feature of creating
uninitialized locations by introducing an explicit mechanism to create
them:
   2a. In MIT Scheme this is (define var).  This is unacceptable
   because it makes DEFINE primitive instead of syntactic sugar.
   2b. Another alternative would be to have a new binding construct
   [Andy, doesn't 1S have something like this?], say (LOCALS (var1 var2
   ...) body), which introduces uninitialized bindings.  This is also
   not good since it would be a shame to add a new special form, especially
   one which makes LAMBDA not be the only binding construct.

3. Similar to the #2, but with a new procedure instead of a special
form.  Let's call it CALL-WITH-UNINITIALIZED-PARAMETERS.  This is a
procedure of one argument, which calls its procedure argument in such a
way that the procedure's parameters are uninitialized:

(call-with-uninitialized-parameters
  (lambda (var1 var2 ...) body))

4. Have a procedure, say (UNINITIALIZED), which returns an object which
when stored in a variable's location causes it to be an error to access
the location.  This is similar to (3), but much more powerful, since
initializedness is no longer "monotonic" - a variable which had a value
can come to not have a value if it is SET! to (UNINITIALIZED).  I think
that kind of power could be dangerous although I can't say exactly why I
think so.  It's like MAKUNBOUND only worse.

5. Like 4 but don't document the procedure.  I don't like this because
it seems to hide something form the user -- it taunts, "I have this
feature but I won't let you use it".

6. Disallow anything besides LAMBDA-expressions on the right-hand sides.
This would mean that nothing would have to be said about it being an
error to reference the variables since there's no way that could happen
anyhow.  The problem with this is that even if it's a perfectly good
idea (true of the 1975 & 1978 Schemes) no one except Bill Rozas likes
it, not even me.

7. Change to normal order evaluation.  I don't think this is practical
or desirable at this point.

---

Let me know what y'all think about CALL-WITH-UNINITIALIZED-PARAMETERS.
If you like it (I kind of do) then try to think of a name for it.
Please overlook the question of what happens when you pass it CONS as an
argument.  We can just say that it's an error to pass it any primitive
procedure, since they all presumably reference their parameters.  If you
don't like it then please defend position number 1 so that I feel more
comfortable documenting it.

Jonathan.