SETF madness

[JONL.PA@PARC-MAXC.ARPA]

Sometime during the 1930s or 1940s it was proven that general recursion
equtions were turing equivalent . . . 

But in my lifetime, they haven't been taken too seriously as a computation
model by anyone who actually has to get work done "in real time" (Yes, PROLOG
is an exception, but I'll comment on that later.  Maybe.)


What all the partially-facetious, somewhat-wishful, nearly-serious suggestions
about extending SETF are leading up to is a re-introduction of recursion
equations as a programming paradigm.  To be realistic, there must be some
limit on the paradigms used.  MacLisp's limit was simply that 
  1) variables would be bound, to
  2) values obtained from CAR/CDR sequences over the input [VAX/NIL, which
     I think still has some remnant of the destructing LET idea, also permits
     vector-referencing in addition to CAR/CDRing.]
This led to the very-compact description of how to "spread" the computed
values of a LET into a bunch of variables: namely, a data structure whose
form was to match that of an argument, and whose symbols were the variables
to be bound.  That's actually a very limited paradigm; but I stress that
those of us who used it found it most convenient.

Another serious proposal would have extended the limitation in point 1)
by including any LOCF'able place; this was coupled with a paradigm that
used a "program", rather than merely a data structure, to indicate how to
destructure the data.  Thus
   (LET ((`(,X ,Y) (MUMBLE))) ...)
instead of 
   (LET (((X Y) (MUMBLE))) ...)
That is, the "evaluable" places in the program would be places
were the destructured value would be "put".  Note that
   (LET (((GET 'X 'SOMEPROP) (MUMBLE))) ...)    ;"Program paradigm"
would bind the result of (MUMBLE) to a spot on the property list of the
symbol X; nothing at all in the "data paradigm" can express this.  In fact,
we just couldn't see how to do such binding efficiently in PDP10 MacLisp
(variables were easy -- they were built-in from antiquity), so that is one
reason we didn't try it out.  On the other hand, the LispMachine apparently
is capable of binding any random cell just as easily as binding a varialbe,
so it would have made more sense to attempt it there.  I believe it was
Rich Stallman's insight that this "program paradigm" was a super-set of
the "data paradigm", and could be implemented straight-forwardly; however,
I don't believe anyone ever did go to the trouble of building a prototype
and trying it out.


Now, back to the snipe at PROLOG.  It is true that PROLOG as a programming
language resembles recursion equations very much, and it is also true that
there are rumors of some PROLOG implementations running "in real time".
Furthermore, I admit that some problems are very succinctly stated in
PROLOG, and their re-formulation into one of the more classic programming
languages is a "hard" problem; so it's tempting to hope that some automating
of the conversion process will make programming a lot easier.  But I don't 
buy it, yet.  As you probe deeper into the use of PROLOG, you find that
you really can't do much without significant use of "cuts" and "directions",
which are in fact the serializers which tend to convert an apparently
descriptive program into a prescriptive one [i.e., rather than a program
which says "I would like such-and-such an efffect" into one that says
"First, do this, then do that, then do something else, then . . . "]

Except for all this madness about SETF, I'm fairly confident that the
Lisp community has it's head screwed on straight about avoiding paradigms
that trap the unwary into an exponentially-worse performance.  If - - - 
If Prolog really makes it big, it will have to make it possible to
express simple things like, say,
   (for I from 1 to 100 sum (AREF A I))
in such a way that the loop-overhead doesn't take an order of magnitude
more time than the array referencing.  SIgh, and again, if it "makes it
big", then the prolog manual will probably expand in size from a small
thin phamplet into something the size of the ZetaLisp or Interlisp tomes.