Re: Binding terminology

[edsel!bhopal!jonl@navajo.stanford.edu (Jon L White)]

There is a sense in which it is easy to confuse the capabilities of the 
extant "shallow bound" implementations with the semantics implicit and 
explicit in Lisp 1.5.  MIT Professor Joel Moses wrote a paper in 1970
entitled "The Function of FUNCTION in Lisp" in which he exposed some of
the mis-conceptions then prevalent.  The most common one was that "deep 
binding" was Lisp 1.5, and "shallow binding" wasn't; in fact, neither of 
the then-extant models was correct in the Lisp 1.5 sense.  The problem 
lay in the ephemeral nature of the the objects used to hold bindings, 
rather than in the deep-versus-shallow question.

One may over-generalize this criticism to say that there is no functional
difference between deep and shallow binding, but only performance
consequences.  This generalization is incorrect, as the subsequent
discussion will show.

The terminology in use during the mid-1970's was that the name/value
pair in the environment "alist" (Lisp 1.5 model) was a "binding" rather
than the creation of a new variable such as Wilensky suggests.  It's
not entirely confusing to think of the entries in the alist as "value
cells".  So the alist model of binding permits you to think of having
simultaneously many value cells, whereas the shallow-binding model 
clearly has only one "value cell".  The difference is more apparent when
you talk about constructing environment objects; in the Lisp 1.5 model,
you are pointing at a (shared) alist, whereas the shallow-bound models
usually didn't implement this very well, if at all.

Not long after Moses' paper appeared, Dan Bobrow at BBN (and others also)
developed the "spaghetti stack" model, which was supposed to have exactly 
the same semantics as the Lisp 1.5 model; indeed, most "spaghetti" 
implementations seem to weave the alist of Lisp 1.5 into subparts of the 
stack-frames allocated to run the program.  The "deep bound" 
implementations which I am familiar with today are all variants of the 
"spaghetti stack" model; so I wouldn't be surprised to see people 
confusing "deep binding" questions with "environment retention" questions.

It is still the case that the extant "shallow bound" models are not as
rich at approximating the Lisp 1.5 model.  In particlar, there is no
way for them to create a "full" funarg -- that is, one that closes over
the entire dynamic environment at the time of creation.  When the Lisp
Machine project first started, I remember Greenblatt coming up with the
limited closure idea, whereby the user had to state explicitly which
dynamic variables would be "closed over".  (If someone else thinks they
invented that idea, then maybe they did -- I just remember RG stating it).
It was widely recognized then that this did not solve the so-called
FUNARG problem; but it was a somewhat useful device.  [Considering
how well entrenched the use of dynamic variables has been, I was 
moderately surprised that the Common Lisp community could agree as
early as 1983 to flush dynamic closuers of any kind; but Scheme's
influence showed how useful lexical-only closuers could be, and
they didn't require a "spaghetti stack" for implementation.]

In the late 1970's or early 1980's, Henry Baker wrote a paper dealing 
with shallow binding in MacLisp and "re-rooting", in which he showed 
how you could still model Lisp variables by storing their "current" 
value in a "shallow" cell, but have the same semantics as the 
"spaghetti-stack" implementations.  The important observation which 
he made was that there is an explicit, user-visible construct which 
must be invoked to change environments; at the time of switching 
contexts (read: environments), the processor could go around "patching 
up" all the relevant "shallow" value cells.

However, neither the Baker idea nor stack-group switching will work
for parallel processors.  There is no synchronizing event occuring
between two processors, running in two different "environments", which
would initiate the re-rooting of the shallow cells.  The obvious solution
is for each environment to have it's own unique "value cell" for
the dynamically-bound variables; this is what deep binding accomplishes.

I have heard of an idea about pairing a "process id" cell along with
a shallow value cell;  the idea being that each process (presumably
being run by an independent processor) would validate the "process id"
before using the shallow cell; and of course there would be appropriate
locks/semaphores to cover the critical periods of update.  But I don't
believe this works any better than the optimizations currently in use
by the deep-binding implementations.


-- JonL --