what's the difference,in a user point of view,between shallow and deep
binding ? are there cases in witch the result won't be the same ?
Pierre.
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
From: David D. Lowry
Subject: Re: shallow/deep binding question
Date:
Message-ID: <35E2B295.21A8@dbrc.com>
··········@spotimage.fr wrote:
>
> what's the difference,in a user point of view,between shallow and deep
> binding ? are there cases in witch the result won't be the same ?
>
> Pierre.
From the user's point of view, none. There should be no cases where the
result won't be the same.
Shallow and deep binding are simply implementation choices for binding
and looking up special (dynamic) variables. Deep binding stores the
variables on the run-time stack, which then may require extra time to
search up the stack to find the the variable binding. Shallow binding
rebinds the top-level (immediately accessible) variable binding, and
stores the old binding on a binding stack. Therefore variable lookup
time is quick, but extra time is needed for function calls and returns
because of the overhead of using the binding stack.
If the implementation is multi-threaded, then usually deep binding is
used, since switching threads is easy: just go to the run-time stack of
choice and start executing. With shallow binding you have to unwind the
binding stack, and then re-wind it with the new variable binding for
every thread switch.
DDL
[ David D. Lowry (remove "NOSPAM" to email)
[ Registered Patent Attorney ···@NOSPAMdbrc.com
[ Dike, Bronstein, Roberts & Cushman LLP www.dbrc.com
[ Boston, MA 02109 617 523-3400
[
[CLOS >= java*10 > C++ * 100
In article <·············@dbrc.com>, David D. Lowry <·········@dbrc.com> wrote:
>If the implementation is multi-threaded, then usually deep binding is
>used, since switching threads is easy: just go to the run-time stack of
>choice and start executing. With shallow binding you have to unwind the
>binding stack, and then re-wind it with the new variable binding for
>every thread switch.
While this is true, I think a number of multi-threaded implementations have
continued to use shallow binding. One reason is simply historical:
threading has usually been an add-on, and it would have been too much work
and binary-incompatible to change the binding mechanism. Second, variable
accesses are probably more common than thread switches, so it still makes
sense to optimize primarily for variable access.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
In article <····················@burlma1-snr1.gtei.net>,
Barry Margolin <······@bbnplanet.com> wrote:
>
> [the usual good stuff]
>
In CLtL2, there is an "implementation note (pg. 44)" which states: "Behind
the assertion that dynamic extents nest properly is the assumption that there
is only a single program or process.... Common Lisp has been carefully
designed to allow special variables to be implemented using either the 'deep
binding' technique or the 'shallow binding' technique, but the two techniques
have different semantic and performance implications for multiprocessing and
multiprogramming."
Mentioning there are "semantic implications" implies there, in fact, might be
differences to the user. What are the semantic implications, i
-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum
In article <············@nnrp1.dejanews.com>, <··········@neodesic.com> wrote:
>In article <····················@burlma1-snr1.gtei.net>,
> Barry Margolin <······@bbnplanet.com> wrote:
>>
>> [the usual good stuff]
Why was it necessary to include a quote section when nothing was actually
quoted?
>In CLtL2, there is an "implementation note (pg. 44)" which states: "Behind
>the assertion that dynamic extents nest properly is the assumption that there
>is only a single program or process.... Common Lisp has been carefully
>designed to allow special variables to be implemented using either the 'deep
>binding' technique or the 'shallow binding' technique, but the two techniques
>have different semantic and performance implications for multiprocessing and
>multiprogramming."
>
>Mentioning there are "semantic implications" implies there, in fact, might be
>differences to the user. What are the semantic implications, i
Suppose shallow bindings are used, and special bindings are implemented
using code that's equivalent to:
(let ((*variable* <value>))
...)
==>
(let ((saved-value *variable*))
(unwind-protect
(progn (setq *variable* <value>)
...)
(setq *variable* saved-value)))
Now you add multiple threads to the implementation. If a thread switch
occurs during the "..." body, *variable* will appear to have the new value
in the other thread, and assignments to *variable* from that thread will be
undone when this thread resumes and exits the LET. On the other hand, if
deep binding is used, variable evaluation simply searches the stack of the
current thread.
Lisp Machines use shallow binding, but threads have a separate stack for
dynamic bindings (threads on Lisp Machines are called "stack groups",
indicating that there are multiple stacks involved -- the "regular PDL" and
the "special PDL"), and thread switches undo all of the dynamic bindings of
the current thread and redo all the bindings of the new thread. Thus, they
were able to retain the normal semantics of dynamic bindings, but they had
a performance implication.
On a multi-processor, shared-memory machine, shallow bindings make it even
harder to maintain those semantics. If two threads are running
simultaneously on different processors, there's no thread switch during
which the bindings can be updated. You might be able to mark the memory
used for these bindings so that a trap occurs if it's referenced by a
thread other than the one that last bound it.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Cambridge, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
It depends on what you mean by shallow or deep binding. In Lisp, there is
some history behind using the terms to mean how you deal with the stack. In
other
systems papers, they mean what in lisp is termed the "funarg" problem, i.e. what
happens when you pass a function to another function. The closest approximation
to this issue with modern lisps is to play games with lexical vs. dynamic
binding of variables to a function. That is, try declaring the formal variables
to a function to all be dynamic and see what kind of trouble you can get into.
Now pass this function to another function (who also declares all of it's
formal arguments to be dynamic (special in CL parlance) and see what happens.
Anyway, I won't go into the details of the funarg problem here, most of us have
seen it before, it's in some sense "obsolete" since modern lisps don't work
that way anymore, and it's a traditional homework problem. As I recall,
_The
Anatomy of Lisp_ by John Allen is a good resource - the point to remember
is that the environment for creating the function and the environment for
evaluating it are different. Think PL/1 "THUNK"s, which is closest to a CL
lexical closure, but doesn't have the funarg problem...
In article <············@nnrp1.dejanews.com>, ··········@spotimage.fr wrote:
> what's the difference,in a user point of view,between shallow and deep
> binding ? are there cases in witch the result won't be the same ?
>
> Pierre.
>
> -----== Posted via Deja News, The Leader in Internet Discussion ==-----
> http://www.dejanews.com/rg_mkgrp.xp Create Your Own Free Member Forum