anderson@ittvax.UUCP (Scott Anderson) (11/22/83)
There was recently a very long article in net.lang.lisp (almost 800 lines) on why many lisps distiguish between the value of a symbol in function position and in argument position (the EXPR property vs the VALUE property). In it, several people mention "shallow binding" and "deep binding." I'm not familliar with these terms. Can anyone tell me what they mean? Thanks, Scott D. Anderson decvax!ittvax!anderson OR yale-comix!ittvax!anderson
liz@umcp-cs.UUCP (11/24/83)
Shallow binding systems always keep the current value of atoms in each atom's value cell. When an atom is lambda bound (by entering a function) the old value of the atom is saved on a stack somewhere and the atom's value cell is set to the new value. When the lambda is exited, the old value of the atom is restored from the stack. The advantage of a shallow binding system is quick access to the value of an atom. In a deep binding system, there is something called an alist which saves all the current values of all the atoms. The alist is simply an assoc list of atoms and values. When you need the value of an atom, you have to assq down the list to the first occurrence of an atom and get its value. The disadvantage of deep binding is this slow access time. When an atom is lambda bound to a new value, the atom and value are simply pushed onto the alist. When the lambda exits, the alist is popped back to where it was before the lambda was entered. The big advantage to deep binding is that you can save the value of the alist and restore a context simply by setting the alist to the saved value. Closures and the like become quite simple. Most lisps these days use shallow binding. The old Maryland lisp that ran on our Univac used deep binding but with an interesting twist. Each atom also had a global binding cell which was always checked first for a value. The global cell could be set using "csetq" and always overode any lambda binding. That way you got the efficiency of shallow binding when you wanted and the context saving of deep binding when you needed... I don't know what other lisps may use deep binding, but the trend seems to be towards things like invisible pointers (as in Lisp Machine lisp) static binding (as in T) to get closures, etc, out of a shallow binding system. -Liz -- Liz Allen, Univ of Maryland, College Park MD Usenet: ...!seismo!umcp-cs!liz Arpanet: liz%umcp-cs@CSNet-Relay
rpk@mit-vax.UUCP (11/29/83)
I don't know if, when a variable is lambda-bound under a deep-binding
scheme, the ``current'' value is put in the value cell and old value is left
on the stack. If that is true, then a problem arises when the Lisp
environment supports multiprocessing. Suppose one executes in process A
(LET ((*BASE* 10.))
(DO-IT))
where *BASE* is 8 globally, and process B looks at *BASE*. Process B should
get the top level value of *BASE*, not the value that process A bound.
I would think that, instead, the new value would be pushed on the stack,
along with some bookeepping to find the previous value.
One way to speed up variable lookup that is used in MacLisp and ZetaLisp is
to tell the compiler that only ``special'' variables will really be
lambda-bound; all other local variables and arguments will be considered
``non-special'' This gives you efficiency in compiled code at the expense
of compatibility with the interpreter. ``Special'' variable references are
turned into routines that do lookup on the binding stack by symbols; all
other variable references are turned into stack references.
Most Lisps are dynamically scoped, but Common Lisp will be lexically scoped.
The special/non-special distinction described above is >>almost<< compatible
with lexical scoping, since the default is that bindings from ``superior''
stack frames will not be inherited into the current stack frame. Common
Lisp also allows ``fluid'' variable declaration, which is just the
``special'' declaration.
--
``Bob'' Robert P. Krajewski ARPA: RpK@MC
MIT Local: RpK@OZ
UUCP: ...!genradbo!mit-eddie!mitvax!rpktjt@kobold.UUCP (T.J.Teixeira) (11/29/83)
mit-vax!rpk appears to be confused about shallow-binding and
deep-binding. In deep-binding, the current value is *always* kept on
the binding-stack, *never* in the value cell. Some lisps that use
deep-binding do keep a value-cell for the "global" or "top-level" value
(e.g. Interlisp) and include a mechanism (often a hack) for accessing
this value (e.g. car of an atom is its top-level value in Interlisp).
Note that Interlisp does not require "special" declarations. The
binding stack for Interlisp (at least for pdp-10's) has a pointer
to the atom being bound in the high half word and the value in the low
half word. Compiled functions simply set up the high half word when
entered but are able to access locally defined variables as stack
offsets. Deeply-bound lisps do act as rpk suggests and push the
new value on the stack along with some bookkeeping information.
The bookkeeping information is the name of the variable that
this binding affects and not how to find the previous value. That
information is implicit in the order of the bindings on the stack.
A good way to characterize deep-binding and shallow-binding schemes is
that shallow-binding makes variable lookup fast, but binding (and
unbinding) expensive while deep-binding makes variable lookup slow, but
binding cheap. i.e. in shallow binding, all variables are evaluated in
constant time by looking at the value cell. To make a new binding, the
old value must be pushed on a stack, and the old value must be restored
when returning from that function (or past it using a non-local jump of
some type. e.g. after an error). In deep binding, evaluating a
variable takes time proportional to the depth of the binding stack.
Making a new binding may be slightly cheaper if there is a good way to
set up the "high half-word" in the binding stack (otherwise you use the
instruction/memory access that you save by not having to push the old
binding when setting up the name in the binding stack). However,
removing any number of local bindings can be done by simply resetting
the stack pointer.
There are two advantages of lexically scoped lisps in combination with
deep binding. Firstly, lexical scoping limits the depth of the binding
stack to the depth of lexical nesting. More importantly, the compiler
is able to efficiently access non-local variables as well as the local
ones since it knows the structure of all the lexically enclosing stack
frames as well as the structure of the local stack frame.
--
Tom Teixeira, Massachusetts Computer Corporation. Westford MA
...!{ihnp4,harpo,decvax,ucbcad,tektronix}!masscomp!tjt (617) 692-6200patcl@tekecs.UUCP (Pat Clancy) (11/29/83)
The definitions of the terms "shallowing binding" and "deep binding" which I learned are different from those given by umcp-cs!liz. Namely: deep binding requires a tree of saved environments, while shallow only requires a stack. The difference has to do with the binding of free variables, eg: (csetq foo(lambda(x) (lambda()(car x)) )) (csetq bar(lambda(x y) ((foo y)) )) (please excuse the probably weird usage, I learned Lisp on a Univac 1100!) Now the result of: (bar '(a b) '(c d)) has two possible values: deep binding: c shallow binding: a The free variable is the "x" inside the function returned by "foo". With deep binding, the alist branch created when foo is being evaluated is saved, including the entry for x, and this is the x which is found on evaluation of the inner (unnamed) function (ie, the inner function is passed a "funarg" including a pointer to the saved environment). With shallow binding, the x created during foo's evaluation is lost when foo exits (no alist tree, only a stack), so the x created during evaluation of bar is found. I have seen both this, and umcp-cs!liz's definitions in the literature, so I believe they are both correct but incompatible usages of these terms. Pat Clancy Tektronix