ITERATE, DEFINE and CELLs

[Bill Rozas <JINX%MIT-OZ@MIT-MC.ARPA>]

> Recursion subsumes iteration, so RECURSE is a good name even if used for
> simple iteration, but ITERATE isn't a good name when its use is not
> tail-recursive.  The *disadvantage* of named let is that its name *does* have
> connotation, namely local binding and *not* recursion.  Our desire to keep
> down the number of keywords should not be at the expense of such confusion.

I disagree.  Recursion for me (and most of the MIT-Scheme people) is a
property of a process, not a feature of the particular syntax with
which it was expressed.  If forms like DO loops are allowed, there is
no syntactic recursion and no real recursion.  One can easily imagine
some dual special form which avoids syntactic recursion while
developing a recursive process when evaluated (executed).  RECURSE
(recur) has too many such connotations for me since I view a procedure
as a way of encapsulating a process, and the only interesting thing is
the process, not its syntactic description.  This distinction between
procedure and process developed by it is very important, though
irrelevant in most programming languages (without a notion of
reduction vs. subproblem) but not in Scheme.  It is further expounded
in "Structure and Interpretation ..." section 1.2.1.

> With SET!, provided one assumes that all identifiers are initially bound in
> the global environment, or that SET!  can extend the global environment.
> With the exception of MIT's Scheme, this is what existing systems do.  If MIT
> is unwilling to change this, then we are reluctantly stuck with DEFINE.

SET! has too many connotations of side effects and I'm not willing
to acceptit as the primary definition mechanism.

I don't view definition as a side effect.  Its interactive
implementation involves one, in the same way that the interpreted
implementation of LETREC involve side effects, only because we don't
know how to do it any better.  The side effects do not exist for
internal definitions.  In the same way that the implementation of
LETREC is incomplete (it can only find a fixed point in some cases,
not all, and the others are disallowed or give an error), the
implementation of DEFINE is incomplete.  Its limitations are no worse
than the limitations of LETREC, yet they meet considerable opposition,
which I don't understand.

Purists in MIT-Scheme advocate for DEFINE to signal an error when
attempting to redefine an already existing identifier in a given
environment.  While conceptually this would be not only appropriate
but logical, it has problems in an interactive system when people want
to re-load some code after making some changes to it.  It would be
very cumbersome to have to change all DEFINEs into SET!s (though I
sometimes think this should be the case).  This is the only reason why
we allow "re-definition" of identifiers (again interactive
constraints).

In a given program there should be no redefinitions (I believe that
our "compiler" will complain, but I'm not sure since I never do it),
and definition should occur before assignment or use.  We even have a
stylistic convention (unfortunately not rigidly adhered to) to aid the
user in determining whether the definition is static (the value will
not change), or we are only introducing an identifier for further
assignment.  In the latter case no initial value is given, thus

(define foo)
(set! foo 3)			; Initial value for foo, which will change

Means something quite different from

(define foo 3)			; Foo is supposed to be 3

This corresponds to LSET and DEFINE in T, but not imposed by the
system.

As you can see, in neither case does the definition conceptually
involve a side-effect, since in the second it declares a constant, and
in the first it declares an identifier which can be used in
assignments.  DEFINE is thus purely declarative, as opposed to SET!
which is imperative.  I believe this distinction is very important,
and justifies the keeping of DEFINE (or some such declarative form).

> They take up half as much space as pairs, and have many fundamental uses.
> They aren't *absolutely* necessary, but then neither is most of
Scheme.

I'm willing to accept them in the standard as long as the CELL type
is not required to be disjoint from PAIR (in the same way that
CHARACTER is not required to be disjoint from STRING or INTEGER).
There is actually a reason for this, I can see a few proposed memory
(debugging) utility programs whose implementation depends on the fact
that all pointer objects have at least 2 words of storage, which would
not be the case for CELLS.

If they are addopted I suggest the following names:

(MAKE-CELL VALUE) returns a CELL object with initial content VALUE.

(CELL-CONTENT CELL) returns the content of cell CELL.

(SET-CELL-CONTENT! CELL NEW-VALUE) makes the new content of CELL be
NEW-VALUE.