Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site kobold.UUCP
Path: utzoo!linus!security!genrad!grkermit!masscomp!kobold!tjt
From: tjt@kobold.UUCP (T.J.Teixeira)
Newsgroups: net.lang.lisp
Subject: Re: Shallow binding and deep binding
Message-ID: <205@kobold.UUCP>
Date: Tue, 29-Nov-83 10:54:22 EST
Article-I.D.: kobold.205
Posted: Tue Nov 29 10:54:22 1983
Date-Received: Thu, 1-Dec-83 02:11:37 EST
References: <4055@umcp-cs.UUCP> <511@mit-vax.UUCP>
Organization: Masscomp, Westford, MA
Lines: 43

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-6200