Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 5/3/83; site umcp-cs.UUCP
Path: utzoo!linus!security!genrad!grkermit!masscomp!clyde!akgua!psuvax!burdvax!presby!seismo!rlgvax!cvl!umcp-cs!liz
From: liz@umcp-cs.UUCP
Newsgroups: net.lang.lisp
Subject: Re: shallow binding and deep binding
Message-ID: <4055@umcp-cs.UUCP>
Date: Wed, 23-Nov-83 23:40:52 EST
Article-I.D.: umcp-cs.4055
Posted: Wed Nov 23 23:40:52 1983
Date-Received: Sat, 26-Nov-83 05:59:56 EST
References: <1126@ittvax.UUCP>
Organization: Univ. of Maryland, Computer Science Dept.
Lines: 37

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