From: Ari Johnson
Subject: Implementation of LET with special variables
Date: 
Message-ID: <ZrKuc.38019$zN5.23872@fed1read01>
I'm understanding more and more how CL implementations work, but I am 
wondering if they handle the following more efficiently than I can come 
up with off-hand:

(defvar a)
(setq a 0)
(let ((a 1)) ...)

The best implementation I can come up with makes the LET look like this:
enter: 1. (push (symbol-value 'a))
        2. (setf (symbol-value 'a) 2)
        3. Let block forms
exit:  4. (setf (symbol-value 'a) (pop))

Thanks in advance.

From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-59E9B6.14184431052004@nntp1.jpl.nasa.gov>
In article <·····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

> I'm understanding more and more how CL implementations work, but I am 
> wondering if they handle the following more efficiently than I can come 
> up with off-hand:
> 
> (defvar a)
> (setq a 0)
> (let ((a 1)) ...)
> 
> The best implementation I can come up with makes the LET look like this:
> enter: 1. (push (symbol-value 'a))
>         2. (setf (symbol-value 'a) 2)
>         3. Let block forms
> exit:  4. (setf (symbol-value 'a) (pop))
> 
> Thanks in advance.

Read up on "deep" vs "shallow" binding.  Also note that your 
implementation is not thread safe.

E.
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <J1Ouc.39696$zN5.16321@fed1read01>
Erann Gat wrote:
> In article <·····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
> 
>>I'm understanding more and more how CL implementations work, but I am 
>>wondering if they handle the following more efficiently than I can come 
>>up with off-hand:
>>
>>(defvar a)
>>(setq a 0)
>>(let ((a 1)) ...)
>>
>>The best implementation I can come up with makes the LET look like this:
>>enter: 1. (push (symbol-value 'a))
>>        2. (setf (symbol-value 'a) 2)
>>        3. Let block forms
>>exit:  4. (setf (symbol-value 'a) (pop))
>>
>>Thanks in advance.
> 
> 
> Read up on "deep" vs "shallow" binding.  Also note that your 
> implementation is not thread safe.
> 
> E.

What's a good reference on binding possibilities?  I wasn't aiming for 
thread safety, but simplicity.  There are probably as many ways of 
making it thread safe as there are CL implementations out there.  What 
I'm looking for is whether or not there are clever tricks for 
implementing this. :)
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-2DFAF0.18580831052004@nntp1.jpl.nasa.gov>
In article <·····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

> Erann Gat wrote:
> > In article <·····················@fed1read01>,
> >  Ari Johnson <·····@hotmail.com> wrote:
> > 
> > 
> >>I'm understanding more and more how CL implementations work, but I am 
> >>wondering if they handle the following more efficiently than I can come 
> >>up with off-hand:
> >>
> >>(defvar a)
> >>(setq a 0)
> >>(let ((a 1)) ...)
> >>
> >>The best implementation I can come up with makes the LET look like this:
> >>enter: 1. (push (symbol-value 'a))
> >>        2. (setf (symbol-value 'a) 2)
> >>        3. Let block forms
> >>exit:  4. (setf (symbol-value 'a) (pop))
> >>
> >>Thanks in advance.
> > 
> > 
> > Read up on "deep" vs "shallow" binding.  Also note that your 
> > implementation is not thread safe.
> > 
> > E.
> 
> What's a good reference on binding possibilities?

Google for starters.

> I wasn't aiming for thread safety, but simplicity.

Then your original solution is fine.  But you should be aware that it's 
not strictly correct, and that this can lead to problems down the road.

> There are probably as many ways of 
> making it thread safe as there are CL implementations out there.

Actually, there aren't.  If you want a thread-safe Lisp, and especially 
if you want a thread-safe Lisp that uses OS-native threads and/or runs 
on a multiprocessor then you have to use a completely different approach 
to managing dynamic bindings.  (You have to actually use a *correct* 
approach, one that creates a *new* binding rather than one that mutates 
an existing binding.)

> What 
> I'm looking for is whether or not there are clever tricks for 
> implementing this. :)

It depends on what "this" is.  There are different clever tricks 
depending on whether you care about thread-safety, OS-native threads, or 
multiprocessing.

E.
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <%UTuc.41488$zN5.36165@fed1read01>
Erann Gat wrote:
> In article <·····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
> 
>>Erann Gat wrote:
>>
>>>In article <·····················@fed1read01>,
>>> Ari Johnson <·····@hotmail.com> wrote:
>>>
>>>
>>>
>>>>I'm understanding more and more how CL implementations work, but I am 
>>>>wondering if they handle the following more efficiently than I can come 
>>>>up with off-hand:
>>>>
>>>>(defvar a)
>>>>(setq a 0)
>>>>(let ((a 1)) ...)
>>>>
>>>>The best implementation I can come up with makes the LET look like this:
>>>>enter: 1. (push (symbol-value 'a))
>>>>       2. (setf (symbol-value 'a) 2)
>>>>       3. Let block forms
>>>>exit:  4. (setf (symbol-value 'a) (pop))
>>>>
>>>>Thanks in advance.
>>>
>>>
>>>Read up on "deep" vs "shallow" binding.  Also note that your 
>>>implementation is not thread safe.
>>>
>>>E.
>>
>>What's a good reference on binding possibilities?
> 
> 
> Google for starters.

I'm aware of Google and use it often.  I asked here because Google is 
unable to censor its results down to references that will talk to me on 
my level. :)

> 
>>I wasn't aiming for thread safety, but simplicity.
> 
> 
> Then your original solution is fine.  But you should be aware that it's 
> not strictly correct, and that this can lead to problems down the road.

Alright.  Since I have the conceptual details right, let's move on to 
the right way of doing it.

> 
> 
>>There are probably as many ways of 
>>making it thread safe as there are CL implementations out there.
> 
> 
> Actually, there aren't.  If you want a thread-safe Lisp, and especially 
> if you want a thread-safe Lisp that uses OS-native threads and/or runs 
> on a multiprocessor then you have to use a completely different approach 
> to managing dynamic bindings.  (You have to actually use a *correct* 
> approach, one that creates a *new* binding rather than one that mutates 
> an existing binding.)

I'm probably falling short of groking this due to an incomplete 
understanding of how bindings are implemented.

> 
> 
>>What 
>>I'm looking for is whether or not there are clever tricks for 
>>implementing this. :)
> 
> 
> It depends on what "this" is.  There are different clever tricks 
> depending on whether you care about thread-safety, OS-native threads, or 
> multiprocessing.

Assume we care about all of the above. :)
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-99F463.22364031052004@nntp1.jpl.nasa.gov>
In article <·····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

> >>I wasn't aiming for thread safety, but simplicity.

Then you wrote:

> > It depends on what "this" is.  There are different clever tricks 
> > depending on whether you care about thread-safety, OS-native threads, or 
> > multiprocessing.
> 
> Assume we care about all of the above. :)

Make up your mind.

If you don't care about thread safety then your original approach is 
fine.

If you do care about thread safety, but are willing to live with 
strictly time-sliced threads where you have control over what happens 
when you switch threads (these are sometimes called "Green threads") 
then you can still use your original approach, but you have to arrange 
that whenever you switch threads you "undo" all the dynamic bindings in 
the thread you're switching out of and "redo" all the dynamic bindings 
in the thread you're switching in to.  This can obviously slow things 
down quite a bit if you have a lot of dynamic bindings.  This is the 
approach that Barry was alluding to, the one implemented by most 
multi-threaded Lisps.

If you care about thread safety *and* you want to be able to use 
OS-native threads on an OS that does not provide a thread-switch hook, 
or if you want to avoid the performance hit, or if you want to run on 
multiprocessors where multiple threads can truly run simultaneously, 
then you need to fundamentally change your model of what symbol-value 
does.  You have to think about it the Right Way or you will lose.  
Symbol-value can no longer simply return the value of a static "slot" in 
a symbol data structure.  A symbol could truly have more than one value 
simultaneously.

The best way to understand how it's really supposed to work it so read 
the standard, especially section 3.1.1 and 3.1.2.1.1.  Note that there 
are three kinds of environments: global, lexical, and dynamic.  What you 
were doing in your original approach was not creating a new dynamic 
binding, but rather changing the value of the global binding, and 
storing the old value in the dynamic environment, which you were 
implementing using a stack.  This fails in a multi-threaded Lisp because 
you are making the global environment do double-duty, and thus the 
global environment becomes a shared resource for which there is 
contention across threads.  (Obviously that's a problem only if there is 
more than one thread.)

E.
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <NPWuc.42055$zN5.22205@fed1read01>
Erann Gat wrote:
> In article <·····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
> 
>>>>I wasn't aiming for thread safety, but simplicity.
> 
> 
> Then you wrote:
> 
> 
>>>It depends on what "this" is.  There are different clever tricks 
>>>depending on whether you care about thread-safety, OS-native threads, or 
>>>multiprocessing.
>>
>>Assume we care about all of the above. :)
> 
> 
> Make up your mind.
>
> If you don't care about thread safety then your original approach is 
> fine.

I wanted to start with a simple understanding of how it could be 
implemented, and then work toward a full understanding of how the Right 
Way to implement it works.  It'd be really silly of me to jump in trying 
to understand the complex implementation if I had a faulty understanding 
of the naive one.

> If you do care about thread safety, but are willing to live with 
> strictly time-sliced threads where you have control over what happens 
> when you switch threads (these are sometimes called "Green threads") 
> then you can still use your original approach, but you have to arrange 
> that whenever you switch threads you "undo" all the dynamic bindings in 
> the thread you're switching out of and "redo" all the dynamic bindings 
> in the thread you're switching in to.  This can obviously slow things 
> down quite a bit if you have a lot of dynamic bindings.  This is the 
> approach that Barry was alluding to, the one implemented by most 
> multi-threaded Lisps.
> 
> If you care about thread safety *and* you want to be able to use 
> OS-native threads on an OS that does not provide a thread-switch hook, 
> or if you want to avoid the performance hit, or if you want to run on 
> multiprocessors where multiple threads can truly run simultaneously, 
> then you need to fundamentally change your model of what symbol-value 
> does.  You have to think about it the Right Way or you will lose.  
> Symbol-value can no longer simply return the value of a static "slot" in 
> a symbol data structure.  A symbol could truly have more than one value 
> simultaneously.
> 
> The best way to understand how it's really supposed to work it so read 
> the standard, especially section 3.1.1 and 3.1.2.1.1.  Note that there 
> are three kinds of environments: global, lexical, and dynamic.  What you 
> were doing in your original approach was not creating a new dynamic 
> binding, but rather changing the value of the global binding, and 
> storing the old value in the dynamic environment, which you were 
> implementing using a stack.  This fails in a multi-threaded Lisp because 
> you are making the global environment do double-duty, and thus the 
> global environment becomes a shared resource for which there is 
> contention across threads.  (Obviously that's a problem only if there is 
> more than one thread.)
> 
> E.

I'll read those sections before asking any other questions (which I'm 
sure I'll have, just from a different subset of all possible questions 
than I have right now).  Thanks. :)
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-29CCE1.08182801062004@nntp1.jpl.nasa.gov>
In article <·····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

> Erann Gat wrote:
> > In article <·····················@fed1read01>,
> >  Ari Johnson <·····@hotmail.com> wrote:
> > 
> > 
> >>>>I wasn't aiming for thread safety, but simplicity.
> > 
> > 
> > Then you wrote:
> > 
> > 
> >>>It depends on what "this" is.  There are different clever tricks 
> >>>depending on whether you care about thread-safety, OS-native threads, or 
> >>>multiprocessing.
> >>
> >>Assume we care about all of the above. :)
> > 
> > 
> > Make up your mind.
> >
> > If you don't care about thread safety then your original approach is 
> > fine.
> 
> I wanted to start with a simple understanding of how it could be 
> implemented, and then work toward a full understanding of how the Right 
> Way to implement it works.

But that is also very different from what you originally asked about:

> I'm understanding more and more how CL implementations work, but I am 
> wondering if they handle the following more efficiently than I can come 
> up with off-hand:

You asked about efficiency, not correctness.

> It'd be really silly of me to jump in trying 
> to understand the complex implementation if I had a faulty understanding 
> of the naive one.

Yes, that would be the point I've been trying to make.

There are many things in computer science where if you start out with a 
simple model that works only in restricted cases it can be very hard to 
break away from that later.  Using a stack to implement function calls 
is the classic example.  You can do it that way, but it's very hard to 
go back and retrofit that model to provide lexical closures or 
first-class continuations.  This is the reason C programmers often have 
a hard time wrapping their brains around closures, and nearly everyone 
has a hard time understanding continuations even though neither one of 
these is an inherently difficult concept.  (In fact, I am coming to 
believe that there are no inherently difficult concepts in CS, there is 
only difficulty in understanding brought about by faulty models.)

E.
From: Cameron MacKinnon
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <NeOdndKxO5E_JCHdRVn-gg@golden.net>
Erann Gat wrote:
> In article <·····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
>>I'm understanding more and more how CL implementations work, but I am 
>>wondering if they handle the following more efficiently than I can come 
>>up with off-hand:
> 
> 
> You asked about efficiency, not correctness.

Well, if they're incorrect, then they're not really CL implementations, 
are they?  ;-)

> There are many things in computer science where if you start out with a 
> simple model that works only in restricted cases it can be very hard to 
> break away from that later.  Using a stack to implement function calls 
> is the classic example.  You can do it that way, but it's very hard to 
> go back and retrofit that model to provide lexical closures or 
> first-class continuations.  This is the reason C programmers often have 
> a hard time wrapping their brains around closures, and nearly everyone 
> has a hard time understanding continuations even though neither one of 
> these is an inherently difficult concept.  (In fact, I am coming to 
> believe that there are no inherently difficult concepts in CS, there is 
> only difficulty in understanding brought about by faulty models.)

Well said. I've been trying to smooth over the mental ruts which years 
of imperative programming in weaker languages have made. It's no 
exaggeration to say that these languages have artificially limited my 
view of the nature of computation. I think I'd be a very different coder 
today if I'd discovered SICP or similar before those ruts were made.

It may be that current teaching materials on Lisp are not the most 
effective way to teach Lisp to those with plenty of experience in lesser 
languages (a majority of newbies?). When learning Lisp "from the front" 
(i.e. looking at Lisp code and learning the language features) it is 
natural to try to map those features on to the features of already known 
languages, even when the fit is poor.

Some people might respond better if Lisp were taught "from the back": If 
a simple and concise variant, coded in C, was dissected and commented 
upon as to why certain implementation idioms are necessary, and the 
ramifications, in terms of expressive power, of the resulting language 
features. Only after a study of the implementation would the guide move 
on to using the  resulting language. I suspect that it would be much 
less likely that those taught this way would develop poor assumptions 
about the workings and capabilities of the language's features.

Thoughts, anyone? I've looked at a few small Lisps. Lisp500 isn't a 
candidate, unless there's a longer, better formatted source file 
somewhere which gets un-prettyprinted to create the 500 line version. 
SIOD would be more suitable, but it's a Scheme. PicoLisp is lexically 
scoped.

-- 
Cameron MacKinnon
Toronto, Canada
From: Cameron MacKinnon
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <M_udncRZ6oWEXSHdRVn-tw@golden.net>
Cameron MacKinnon wrote:
> PicoLisp is lexically scoped.

Wrong!

-- 
Cameron MacKinnon
Toronto, Canada
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <Ihcvc.44179$zN5.3804@fed1read01>
Cameron MacKinnon wrote:

> Erann Gat wrote:
> 
>> In article <·····················@fed1read01>,
>>  Ari Johnson <·····@hotmail.com> wrote:
>>
>>> I'm understanding more and more how CL implementations work, but I am 
>>> wondering if they handle the following more efficiently than I can 
>>> come up with off-hand:
>>
>>
>>
>> You asked about efficiency, not correctness.
> 
> 
> Well, if they're incorrect, then they're not really CL implementations, 
> are they?  ;-)

Exactly - at no point do I wish to stray from correctness; I wanted to 
start with the simplest correct implementation and build my 
understanding toward the most efficient, robust, and correct 
implementation.  The example I gave is neither efficient nor robust 
(i.e., it really breaks down when you have anything but a linear flow of 
control, such as a non-local exit or other thread, involved), but it is 
apparently correct.  Now I want to build from the understanding of the 
simplest possible correct implementation toward the most robust and 
possible efficient correct implementation.

I am taking the same approach as I did in learning calculus way back 
when: start simple but correct, build to robust and correct, and work on 
efficiency on the way.

>> There are many things in computer science where if you start out with 
>> a simple model that works only in restricted cases it can be very hard 
>> to break away from that later.  Using a stack to implement function 
>> calls is the classic example.  You can do it that way, but it's very 
>> hard to go back and retrofit that model to provide lexical closures or 
>> first-class continuations.  This is the reason C programmers often 
>> have a hard time wrapping their brains around closures, and nearly 
>> everyone has a hard time understanding continuations even though 
>> neither one of these is an inherently difficult concept.  (In fact, I 
>> am coming to believe that there are no inherently difficult concepts 
>> in CS, there is only difficulty in understanding brought about by 
>> faulty models.)
> 
> 
> Well said. I've been trying to smooth over the mental ruts which years 
> of imperative programming in weaker languages have made. It's no 
> exaggeration to say that these languages have artificially limited my 
> view of the nature of computation. I think I'd be a very different coder 
> today if I'd discovered SICP or similar before those ruts were made.

I wish I'd learned Lisp 11 years ago instead of C++.  A lot of it is 
starting to click for me now, but in some areas I still have a long way 
to go.

> It may be that current teaching materials on Lisp are not the most 
> effective way to teach Lisp to those with plenty of experience in lesser 
> languages (a majority of newbies?). When learning Lisp "from the front" 
> (i.e. looking at Lisp code and learning the language features) it is 
> natural to try to map those features on to the features of already known 
> languages, even when the fit is poor.
> 
> Some people might respond better if Lisp were taught "from the back": If 
> a simple and concise variant, coded in C, was dissected and commented 
> upon as to why certain implementation idioms are necessary, and the 
> ramifications, in terms of expressive power, of the resulting language 
> features. Only after a study of the implementation would the guide move 
> on to using the  resulting language. I suspect that it would be much 
> less likely that those taught this way would develop poor assumptions 
> about the workings and capabilities of the language's features.

That's what I'm trying to accomplish, sans the presence of any such 
implementation. ;)

> Thoughts, anyone? I've looked at a few small Lisps. Lisp500 isn't a 
> candidate, unless there's a longer, better formatted source file 
> somewhere which gets un-prettyprinted to create the 500 line version. 
> SIOD would be more suitable, but it's a Scheme. PicoLisp is lexically 
> scoped.

I've tried breaking down SBCL, starting with the runtime, but my 
schedule makes it difficult to dedicate time to tracing through others' 
code like that.  How does ECL stand up?
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-6237FF.22391001062004@nntp1.jpl.nasa.gov>
In article <····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

>   The example I gave is neither efficient nor robust 
> (i.e., it really breaks down when you have anything but a linear flow of 
> control, such as a non-local exit or other thread, involved), but it is 
> apparently correct.

You have that exactly backwards.  Your original example was efficient, 
it was an unwind-protect away from being robust, but it was *not* 
correct, notwithstanding that many CL's actually work that way.

E.
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <cPfvc.45142$zN5.44013@fed1read01>
Erann Gat wrote:
> In article <····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
> 
>>  The example I gave is neither efficient nor robust 
>>(i.e., it really breaks down when you have anything but a linear flow of 
>>control, such as a non-local exit or other thread, involved), but it is 
>>apparently correct.
> 
> 
> You have that exactly backwards.  Your original example was efficient, 
> it was an unwind-protect away from being robust, but it was *not* 
> correct, notwithstanding that many CL's actually work that way.

Please explain how it was incorrect, if you have the time.  Thanks. :)
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-625D3E.05581802062004@nntp1.jpl.nasa.gov>
In article <·····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

> Erann Gat wrote:
> > In article <····················@fed1read01>,
> >  Ari Johnson <·····@hotmail.com> wrote:
> > 
> > 
> >>  The example I gave is neither efficient nor robust 
> >>(i.e., it really breaks down when you have anything but a linear flow of 
> >>control, such as a non-local exit or other thread, involved), but it is 
> >>apparently correct.
> > 
> > 
> > You have that exactly backwards.  Your original example was efficient, 
> > it was an unwind-protect away from being robust, but it was *not* 
> > correct, notwithstanding that many CL's actually work that way.
> 
> Please explain how it was incorrect, if you have the time.  Thanks. :)

I already did.  The standard states that LET must create a new binding 
and arrange for the variable to refer to the new binding.  Your 
implementation does not do that.  It mutates the existing binding.  This 
emulates the correct behavior, but it is not in fact the correct 
behavior, and there are circumstances under which this incorrectness can 
be exposed.  Multithreading is one of them, but not the only one.

E.
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <YOmvc.46632$zN5.26543@fed1read01>
Erann Gat wrote:

> In article <·····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
> 
>>Erann Gat wrote:
>>
>>>In article <····················@fed1read01>,
>>> Ari Johnson <·····@hotmail.com> wrote:
>>>
>>>
>>>
>>>> The example I gave is neither efficient nor robust 
>>>>(i.e., it really breaks down when you have anything but a linear flow of 
>>>>control, such as a non-local exit or other thread, involved), but it is 
>>>>apparently correct.
>>>
>>>
>>>You have that exactly backwards.  Your original example was efficient, 
>>>it was an unwind-protect away from being robust, but it was *not* 
>>>correct, notwithstanding that many CL's actually work that way.
>>
>>Please explain how it was incorrect, if you have the time.  Thanks. :)
> 
> 
> I already did.  The standard states that LET must create a new binding 
> and arrange for the variable to refer to the new binding.  Your 
> implementation does not do that.  It mutates the existing binding.  This 
> emulates the correct behavior, but it is not in fact the correct 
> behavior, and there are circumstances under which this incorrectness can 
> be exposed.  Multithreading is one of them, but not the only one.

Alright, there we go.  I'm in the process of reading CLTL2, and although 
I'm not far into it, maybe someone can spoil the ending for me and 
explain exactly what entity a "binding" refers to and how this is 
implemented.  I'm too used to languages where a variable has a value and 
is either globally allocated or locally stack allocated, and I'm sure 
that's holding me back from grasping this.

CLTL2 seems a little vague on exactly what is meant by the word 
"binding", and the HyperSpec doesn't explain it any better.  I already 
know that a binding is an association between a name and a value - 
what's the difference between creating a new binding for X and changing 
the value of X?
From: rmagere
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <c9ku8l$8ae$1@news.ox.ac.uk>
Ari Johnson wrote:
>
> CLTL2 seems a little vague on exactly what is meant by the word
> "binding", and the HyperSpec doesn't explain it any better.  I already
> know that a binding is an association between a name and a value -
> what's the difference between creating a new binding for X and
> changing the value of X?

I don't know if this is what you are looking for, but you might trying
reading
http://www.flownet.com/gat/specials.pdf. The link is to "The Idiot's Guide
to Special Variables" written by Erann Gat, and obviously his homepage is
http://www.flownet.com/gat/.
From: Marco Baringer
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <m2pt8ind1k.fsf@convey.it>
Ari Johnson <·····@hotmail.com> writes:

> CLTL2 seems a little vague on exactly what is meant by the word
> "binding", and the HyperSpec doesn't explain it any better.  I already
> know that a binding is an association between a name and a value - 
> what's the difference between creating a new binding for X and
> changing the value of X?

i think you may be calling "variable" what is technically a "binding".

(let ((x 0))
  (let ((x 1)) ;; this is a new binding for the same variable
    (setf x 42)) ;; change the value of the binding
  ;; we have not changed the value of this binding, even though it's
  ;; still the variable x
  x)
==> 0

and then we have this;

(let ((x 0))
  (let ((x x)) ;; create a new binding for the variable x, the value
               ;; of the new binding is the value of the other binding.
    (setf x 42)) ;; change the new binding
  x)
==> 0

note though that there is no association between the symbol X and the
place in memore which holds those numbers. in fact this:

(let ((x 0))
  (voodoo-majick 'x)
  x)

will _always_ return 0 no matter what voodoo-majick tries to do.

-- 
-Marco
Ring the bells that still can ring.
Forget your perfect offering.
There is a crack in everything.
That's how the light gets in.
     -Leonard Cohen
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <Vsnvc.46758$zN5.23552@fed1read01>
Marco Baringer wrote:
> Ari Johnson <·····@hotmail.com> writes:
> 
> 
>>CLTL2 seems a little vague on exactly what is meant by the word
>>"binding", and the HyperSpec doesn't explain it any better.  I already
>>know that a binding is an association between a name and a value - 
>>what's the difference between creating a new binding for X and
>>changing the value of X?
> 
> 
> i think you may be calling "variable" what is technically a "binding".
> 
> (let ((x 0))
>   (let ((x 1)) ;; this is a new binding for the same variable
>     (setf x 42)) ;; change the value of the binding
>   ;; we have not changed the value of this binding, even though it's
>   ;; still the variable x
>   x)
> ==> 0
> 
> and then we have this;
> 
> (let ((x 0))
>   (let ((x x)) ;; create a new binding for the variable x, the value
>                ;; of the new binding is the value of the other binding.
>     (setf x 42)) ;; change the new binding
>   x)
> ==> 0
> 
> note though that there is no association between the symbol X and the
> place in memore which holds those numbers. in fact this:
> 
> (let ((x 0))
>   (voodoo-majick 'x)
>   x)
> 
> will _always_ return 0 no matter what voodoo-majick tries to do.

But how does that work with special variables, where there /is/ an 
association between the symbol and the place in memory which holds the 
bound value?  You're repeating what I know, so maybe I worded my 
question poorly, but it's the special variable case that is bothering me.

How do bindings 'work' in the following:

(setq x 0)
(defun f () x)
(f) => 0
(let ((x 1)) (f)) => 1
From: Edi Weitz
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87brk1aooa.fsf@bird.agharta.de>
On Wed, 02 Jun 2004 09:43:38 -0700, Ari Johnson <·····@hotmail.com> wrote:

> How do bindings 'work' in the following:
>
> (setq x 0)

Note that this is unportable. A top-level SETQ doesn't automatically
declare X to be special, you'll have to use DEFPARAMETER or DEFVAR.

> (defun f () x)
> (f) => 0
> (let ((x 1)) (f)) => 1

The compiler has to figure out that the X in the LET form is special
(either by a global declaration as above or by a local DECLARE) and
act accordingly.

It is easier to understand if you image that there are really two
operators, one is called LET (for lexical variables) and one is called
DYNAMIC-LET (for special variables). The compiler will insert the
right operator for you.

Check the ISLISP specification <http://www.islisp.info/> for a Lisp
dialect which requires you to use different operators for these two
kinds of bindings.

HTH,
Edi.
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <hzwvc.48737$zN5.35514@fed1read01>
Edi Weitz wrote:
> On Wed, 02 Jun 2004 09:43:38 -0700, Ari Johnson <·····@hotmail.com> wrote:
> 
> 
>>How do bindings 'work' in the following:
>>
>>(setq x 0)
> 
> 
> Note that this is unportable. A top-level SETQ doesn't automatically
> declare X to be special, you'll have to use DEFPARAMETER or DEFVAR.

Fair enough, but I think my intention was clear. ;)

>>(defun f () x)
>>(f) => 0
>>(let ((x 1)) (f)) => 1
> 
> 
> The compiler has to figure out that the X in the LET form is special
> (either by a global declaration as above or by a local DECLARE) and
> act accordingly.

I understand that, or else my question wouldn't make much sense as the 
compiler I'm imagining would have no way of knowing it's dealing with a 
dynamic variable.

> It is easier to understand if you image that there are really two
> operators, one is called LET (for lexical variables) and one is called
> DYNAMIC-LET (for special variables). The compiler will insert the
> right operator for you.

Right, I understand that LET and the conceptual DYNAMIC-LET are 
implemented differently.  Moreover, I have a pretty firm grasp (or think 
I do) on how LET works.  I'm asking specifically how DYNAMIC-LET would 
be implemented.
From: Joe Marshall
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <y8n5icto.fsf@comcast.net>
Marco Baringer <··@bese.it> writes:

> note though that there is no association between the symbol X and the
> place in memore which holds those numbers. in fact this:
>
> (let ((x 0))
>   (voodoo-majick 'x)
>   x)
>
> will _always_ return 0 no matter what voodoo-majick tries to do.

Too tempting!

(defun voodoo-majick (arg)
  (declare (ignore arg))
  (loop))

-- 
~jrm
From: Alexander Schmolck
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <yfspt8gtesg.fsf@black132.ex.ac.uk>
Joe Marshall <·············@comcast.net> writes:

>   (declare (ignore arg))

Surely a case of premature optimization? ;)

'as
From: Rahul Jain
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87oeny4yue.fsf@nyct.net>
Joe Marshall <·············@comcast.net> writes:

> Marco Baringer <··@bese.it> writes:
>
>> note though that there is no association between the symbol X and the
>> place in memore which holds those numbers. in fact this:
>>
>> (let ((x 0))
>>   (voodoo-majick 'x)
>>   x)
>>
>> will _always_ return 0 no matter what voodoo-majick tries to do.
>
> Too tempting!
>
> (defun voodoo-majick (arg)
>   (declare (ignore arg))
>   (loop))

(defun voodoo-majick (arg)
  (declare (ignore arg))
  (throw 'foo))

Is another possibility. :)

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: André Thieme
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <c9lvr7$edr$1@ulric.tng.de>
Marco Baringer wrote:

> (let ((x 0))
>   (voodoo-majick 'x)
>   x)
> 
> will _always_ return 0 no matter what voodoo-majick tries to do.
> 

What if voodoo-majick calls a routine which is written in assembler and 
has full access to physical ram (program is running as user root) and 
then searches for the contents of x and changes it inside the ram to 
another value?
I would see this as a possibility for the snippet to return something 
different from 0.


Andr�
--
From: Pascal Costanza
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <c9k1t3$2nk$2@newsreader2.netcologne.de>
Ari Johnson wrote:

> Erann Gat wrote:
> 
>> In article <····················@fed1read01>,
>>  Ari Johnson <·····@hotmail.com> wrote:
>>
>>>  The example I gave is neither efficient nor robust (i.e., it really 
>>> breaks down when you have anything but a linear flow of control, such 
>>> as a non-local exit or other thread, involved), but it is apparently 
>>> correct.
>>
>> You have that exactly backwards.  Your original example was efficient, 
>> it was an unwind-protect away from being robust, but it was *not* 
>> correct, notwithstanding that many CL's actually work that way.
> 
> Please explain how it was incorrect, if you have the time.  Thanks. :)

He already did. When you change the value of a global variable via setq, 
all threads will see the new value. However, the intuitively correct 
behavior of dynamic scoping is that only the current thread is affected.

This is only relevant for multi-threaded CL implementations.


Pascal


-- 
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
From: Rob Warnock
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <hLqdneHgU8jfMSDdRVn-jg@speakeasy.net>
Pascal Costanza  <········@web.de> wrote:
+---------------
| Ari Johnson wrote:
| > Please explain how it was incorrect, if you have the time.  Thanks. :)
| 
| He already did. When you change the value of a global variable via setq, 
| all threads will see the new value.
+---------------

Well, close, but... That's only correct if the global variable has not
yet been dynamically bound in the current thread. If the global variable
*has* been dynamically bound in the current thread, then a SETQ of the
global variable from within that thread will only change the value seen
within that thread.

Conversely, if the global variable *has* been dynamically bound in the
current thread, say, thread "X", then a SETQ of the global variable from
within some other thread when *not* bound will only change the value
seen within that and other threads in which it hasn't been bound, but
*not* the value seen within "X" and other threads in which *has* been
bound.

This is why (in threaded implementations) you'll often see functions
that start off with:

	(let ((*foo* *foo*)
	      (*bar* *bar*)
	      ...)
	  ;; *FOO* and *BAR* are now protected from SETQs in other
	  ;;  threads, and vice versa.
	  ...
	   ...
	    ...)


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Tim Bradshaw
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <fbc0f5d1.0406020529.3c0f8c91@posting.google.com>
····@rpw3.org (Rob Warnock) wrote in message news:<······················@speakeasy.net>...

> 
> This is why (in threaded implementations) you'll often see functions
> that start off with:
> 
> 	(let ((*foo* *foo*)
> 	      (*bar* *bar*)
> 	      ...)
> 	  ;; *FOO* and *BAR* are now protected from SETQs in other
> 	  ;;  threads, and vice versa.
> 	  ...
> 	   ...
> 	    ...)
> 
> 

There are a lot of other reasons for doing this!  In particular you
may want to protect the variable from assignments in the *same* thread
(or the only thread in a single-threaded implementation).

--tim
From: Rob Warnock
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <KqydnW2PYqSnZiPdRVn-jw@speakeasy.net>
Tim Bradshaw <··········@tfeb.org> wrote:
+---------------
| ····@rpw3.org (Rob Warnock) wrote:
| > This is why (in threaded implementations) you'll often see functions
| > that start off with:
| > 	(let ((*foo* *foo*)
| > 	      (*bar* *bar*)
| > 	      ...)
| > 	  ;; *FOO* and *BAR* are now protected from SETQs in other
| > 	  ;;  threads, and vice versa.
| > 	  ...)
| 
| There are a lot of other reasons for doing this!  In particular you
| may want to protect the variable from assignments in the *same* thread
| (or the only thread in a single-threaded implementation).
+---------------

Hunh? But it *won't* protect the variable from assignments in
the same thread! E.g.:

    > (defvar *foo* 13)

    *FOO*
    > (defun set-foo (n) 
	(setq *foo* n))

    SET-FOO
    > (defun show-foo ()
	(format t "foo = ~a~%" *foo*))

    SHOW-FOO
    > (let ((*foo* *foo*))
	(show-foo)
	(set-foo 52)
	(show-foo))
    foo = 13
    foo = 52
    NIL
    > 

I guess I don't understand your point...


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Jeremy Yallop
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <slrncbtv4a.uvq.jeremy@maka.cl.cam.ac.uk>
Rob Warnock wrote:
> Tim Bradshaw <··········@tfeb.org> wrote:
> +---------------
>| ····@rpw3.org (Rob Warnock) wrote:
>| > This is why (in threaded implementations) you'll often see functions
>| > that start off with:
>| > 	(let ((*foo* *foo*)
>| > 	      (*bar* *bar*)
>| > 	      ...)
>| > 	  ;; *FOO* and *BAR* are now protected from SETQs in other
>| > 	  ;;  threads, and vice versa.
>| > 	  ...)
>| 
>| There are a lot of other reasons for doing this!  In particular you
>| may want to protect the variable from assignments in the *same* thread
>| (or the only thread in a single-threaded implementation).
> +---------------
> 
> Hunh? But it *won't* protect the variable from assignments in
> the same thread!

I think Tim is referring to something like this:

   > (defparameter *foo* :initial)
   *FOO*

   > (defun set-foo () 
       (setf *foo* :changed))
   SET-FOO

   > (let ((*foo* *foo*)) 
       (set-foo))
   :CHANGED

   > *foo*
   :INITIAL

Jeremy.
From: Tim Bradshaw
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <fbc0f5d1.0406040306.62c0e6e5@posting.google.com>
····@rpw3.org (Rob Warnock) wrote in message news:<······················@speakeasy.net>...
>
> 
> Hunh? But it *won't* protect the variable from assignments in
> the same thread! E.g.:
> 

Sorry, I was being vague.  What I meant was that it protects the
variable from assignments outside the dynamic scope of the binding
(but in the same thread).  WITH-STANDARD-IO-SYNTAX is a good example
of this, also things tacitly done by LOAD &c like

   (let ((*package* *package*))
     ...)

--tim
From: Don Geddis
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87y8n5c1zj.fsf@sidious.geddis.org>
> | Ari Johnson wrote:
> | > Please explain how it was incorrect, if you have the time.  Thanks. :)

> Pascal Costanza  <········@web.de> wrote:
> | He already did. When you change the value of a global variable via setq, 
> | all threads will see the new value.

····@rpw3.org (Rob Warnock) wrote on Wed, 02 Jun 2004:
> Well, close, but... That's only correct if the global variable has not
> yet been dynamically bound in the current thread. If the global variable
> *has* been dynamically bound in the current thread, then a SETQ of the
> global variable from within that thread will only change the value seen
> within that thread.
> Conversely, if the global variable *has* been dynamically bound in the
> current thread, say, thread "X", then a SETQ of the global variable from
> within some other thread when *not* bound will only change the value
> seen within that and other threads in which it hasn't been bound, but
> *not* the value seen within "X" and other threads in which *has* been
> bound.

You've described what you would like to see from a Common Lisp implementation,
and in fact the behavior that you do get from most of the multi-threaded
implementations.  (Although you should note that threads are not part of the
ANSI CL standard, so a multi-threaded Common Lisp could be ANSI compliant
without functioning in the way you describe.)

But Pascal was responding to Ari's proposed code for implementing dynamic
variables.  Ari's code was broken in the presence of multiple threads, because
it did _not_ function the way you describe.

Which is exactly what Pascal explained.  He was answering Ari's question about
"how it [Ari's implementation] was incorrect".

        -- Don
_______________________________________________________________________________
Don Geddis                  http://don.geddis.org/               ···@geddis.org
I think that the team that wins game five will win the series.
Unless we lose game five.  -- Charles Barkley
From: Rob Warnock
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <KqydnWyPYqS9YCPdRVn-jw@speakeasy.net>
Don Geddis  <···@geddis.org> wrote:
+---------------
| > | Ari Johnson wrote:
| > | > Please explain how it was incorrect, if you have the time.  Thanks. :)
| 
| > Pascal Costanza  <········@web.de> wrote:
| > | He already did. When you change the value of a global variable via setq, 
| > | all threads will see the new value.
| 
| ····@rpw3.org (Rob Warnock) wrote on Wed, 02 Jun 2004:
| > Well, close, but... 
...
| But Pascal was responding to Ari's proposed code for implementing dynamic
| variables.  Ari's code was broken in the presence of multiple threads,
| because it did _not_ function the way you describe.
| 
| Which is exactly what Pascal explained.  He was answering Ari's question
| about "how it [Ari's implementation] was incorrect".
+---------------

Oops! You're right! Thanks for the catch.

And my apologies, Pascal...


-Rob

-----
Rob Warnock			<····@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607
From: Pascal Costanza
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <c9kd7n$rbu$1@f1node01.rhrz.uni-bonn.de>
Rob Warnock wrote:

> Pascal Costanza  <········@web.de> wrote:
> +---------------
> | Ari Johnson wrote:
> | > Please explain how it was incorrect, if you have the time.  Thanks. :)
> | 
> | He already did. When you change the value of a global variable via setq, 
> | all threads will see the new value.
> +---------------
> 
> Well, close, but...
[...]

Uhm, I meant something like "implementing dynamic scoping via setq", as in:

(defmacro dynamic-let ((var value) &body body)
   (with-gensyms (temp)
     `(let ((,temp ,var))
        (unwind-protect
            (progn
              (setq ,var ,value)
              ,@body)
          (setq ,var ,temp)))))

...which would be correct in single-threaded Lisps (except for omission 
of proper handling of unbound variables). In multi-threaded Lisps, the 
SETQs would have nasty side-effects in other threads.


Pascal

-- 
ECOOP 2004 Workshops - Oslo, Norway
*1st European Lisp and Scheme Workshop, June 13*
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
*2nd Post-Java Workshop, June 14*
http://prog.vub.ac.be/~wdmeuter/PostJava04/
From: Rahul Jain
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <877jupctvu.fsf@nyct.net>
····@rpw3.org (Rob Warnock) writes:

> Well, close, but... That's only correct if the global variable has not
> yet been dynamically bound in the current thread. If the global variable
> *has* been dynamically bound in the current thread, then a SETQ of the
> global variable from within that thread will only change the value seen
> within that thread.

Which is still not correct, actually, when you have dynamic closures. :)

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Ari Johnson
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <qGmvc.46612$zN5.32436@fed1read01>
Pascal Costanza wrote:
> 
> Ari Johnson wrote:
> 
>> Erann Gat wrote:
>>
>>> In article <····················@fed1read01>,
>>>  Ari Johnson <·····@hotmail.com> wrote:
>>>
>>>>  The example I gave is neither efficient nor robust (i.e., it really 
>>>> breaks down when you have anything but a linear flow of control, 
>>>> such as a non-local exit or other thread, involved), but it is 
>>>> apparently correct.
>>>
>>>
>>> You have that exactly backwards.  Your original example was 
>>> efficient, it was an unwind-protect away from being robust, but it 
>>> was *not* correct, notwithstanding that many CL's actually work that 
>>> way.
>>
>>
>> Please explain how it was incorrect, if you have the time.  Thanks. :)
> 
> 
> He already did. When you change the value of a global variable via setq, 
> all threads will see the new value. However, the intuitively correct 
> behavior of dynamic scoping is that only the current thread is affected.

That's what I meant by it not being robust.  It appears that I /am/ 
correct for the simple case, just not robust enough to remain correct in 
the complex case.
From: Rahul Jain
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <873c5dctrk.fsf@nyct.net>
Ari Johnson <·····@hotmail.com> writes:

> That's what I meant by it not being robust.  It appears that I /am/
> correct for the simple case, just not robust enough to remain correct in
> the complex case.

I'll repeat. :)

I have written a lisp implementation that is correct: it gives an out of
memory error on startup and provides no restarts other than exiting the
lisp implementation.

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Kenny Tilton
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <hvvvc.105045$Nn4.22488710@twister.nyc.rr.com>
Rahul Jain wrote:
> Ari Johnson <·····@hotmail.com> writes:
> 
> 
>>That's what I meant by it not being robust.  It appears that I /am/
>>correct for the simple case, just not robust enough to remain correct in
>>the complex case.
> 
> 
> I'll repeat. :)
> 
> I have written a lisp implementation that is correct: it gives an out of
> memory error on startup and provides no restarts other than exiting the
> lisp implementation.

Is it really out of memory?

:)

kenny

-- 
Home? http://tilton-technology.com
Cells? http://www.common-lisp.net/project/cells/
Cello? http://www.common-lisp.net/project/cello/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Your Project Here! http://alu.cliki.net/Industry%20Application
From: Rahul Jain
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87aczlbd9h.fsf@nyct.net>
Kenny Tilton <·······@nyc.rr.com> writes:

> Rahul Jain wrote:

>> I'll repeat. :) I have written a lisp implementation that is correct:
>> it gives an out of memory error on startup and provides no restarts
>> other than exiting the lisp implementation.
>
> Is it really out of memory?

Yep. It gave itself a 1 KB heap and just barely had enough memory to
cons the out of memory message.

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Pascal Costanza
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <c9k1on$2nk$1@newsreader2.netcologne.de>
Erann Gat wrote:

> In article <····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
>>  The example I gave is neither efficient nor robust 
>>(i.e., it really breaks down when you have anything but a linear flow of 
>>control, such as a non-local exit or other thread, involved), but it is 
>>apparently correct.
> 
> You have that exactly backwards.  Your original example was efficient, 
> it was an unwind-protect away from being robust, but it was *not* 
> correct, notwithstanding that many CL's actually work that way.

Hmpf, my impression was that most CL implementations get this right. 
Does anyone have any numbers in that regard?


Pascal

-- 
1st European Lisp and Scheme Workshop
June 13 - Oslo, Norway - co-located with ECOOP 2004
http://www.cs.uni-bonn.de/~costanza/lisp-ecoop/
From: Rahul Jain
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <878yf6o39m.fsf@nyct.net>
Ari Johnson <·····@hotmail.com> writes:

> I wanted to start with a simple understanding of how it could be
> implemented, and then work toward a full understanding of how the Right
> Way to implement it works.  It'd be really silly of me to jump in trying
> to understand the complex implementation if I had a faulty understanding
> of the naive one.

A Lisp environment could be implemented by always exiting with an out of
memory error the moment it starts.

:)

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: David Steuber
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87llj57kjn.fsf@david-steuber.com>
Rahul Jain <·····@nyct.net> writes:

> A Lisp environment could be implemented by always exiting with an out of
> memory error the moment it starts.

That would be too much like my mornings.

-- 
An ideal world is left as an excercise to the reader.
   --- Paul Graham, On Lisp 8.1
From: Rahul Jain
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87y8n5bf1v.fsf@nyct.net>
David Steuber <·····@david-steuber.com> writes:

> Rahul Jain <·····@nyct.net> writes:
>
>> A Lisp environment could be implemented by always exiting with an out of
>> memory error the moment it starts.
>
> That would be too much like my mornings.

Now all you need to do is work on robustness and you'll be a
commercially viable Lisp environment!

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Joe Marshall
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <llj7bdoo.fsf@ccs.neu.edu>
Ari Johnson <·····@hotmail.com> writes:

> What's a good reference on binding possibilities?  I wasn't aiming for
> thread safety, but simplicity.  There are probably as many ways of
> making it thread safe as there are CL implementations out there.  What
> I'm looking for is whether or not there are clever tricks for
> implementing this. :)

The binding has to be indexed by both the thread and the symbol being
bound.  This leads to two obvious implementations:  associate a table
with the symbol and index it by the thread, or associate a table with
the thread and index it by the symbol.  There is also the obvious
optimization of creating the tables and the entries lazily.

For actual examples, look at the docs for Corman Common Lisp and Franz
Allegro.  If I remember correctly, they each took a different
approach.
From: Barry Margolin
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <barmar-07CC94.17353431052004@comcast.dca.giganews.com>
In article <·····················@fed1read01>,
 Ari Johnson <·····@hotmail.com> wrote:

> I'm understanding more and more how CL implementations work, but I am 
> wondering if they handle the following more efficiently than I can come 
> up with off-hand:
> 
> (defvar a)
> (setq a 0)
> (let ((a 1)) ...)
> 
> The best implementation I can come up with makes the LET look like this:
> enter: 1. (push (symbol-value 'a))
>         2. (setf (symbol-value 'a) 2)
>         3. Let block forms
> exit:  4. (setf (symbol-value 'a) (pop))

That's essentially how they do it.  There are some complications that 
arise in implementations that support multi-threading, but you've got 
the basic principle right.

-- 
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-428808.15023731052004@nntp1.jpl.nasa.gov>
In article <····························@comcast.dca.giganews.com>,
 Barry Margolin <······@alum.mit.edu> wrote:

> In article <·····················@fed1read01>,
>  Ari Johnson <·····@hotmail.com> wrote:
> 
> > I'm understanding more and more how CL implementations work, but I am 
> > wondering if they handle the following more efficiently than I can come 
> > up with off-hand:
> > 
> > (defvar a)
> > (setq a 0)
> > (let ((a 1)) ...)
> > 
> > The best implementation I can come up with makes the LET look like this:
> > enter: 1. (push (symbol-value 'a))
> >         2. (setf (symbol-value 'a) 2)
> >         3. Let block forms
> > exit:  4. (setf (symbol-value 'a) (pop))
> 
> That's essentially how they do it.  There are some complications that 
> arise in implementations that support multi-threading, but you've got 
> the basic principle right.

I take issue with your characterization.  You give the impression that 
the naive algorithm is fundamentally correct, and that the difficulties 
that arise from multithreading are mere details.

I'd say that the naive implementation is fundamentally incorrect, but 
that its behavior is indistinguishable from a correct implementation in 
the special case of a single-threaded Lisp.  (Indeed, one could argue 
that the naive implementation is at odds with the standard, which 
requires references to a dynamically bound variable to refer to a *new* 
dynamic binding.  Multithreading is not the only extension that would 
unmask this incorrect behavior.  It just happens to be the most common.)

Also, the majority of Common Lisp implementations in use today are 
multithreaded.  (In fact, I believe CLisp is the only one that isn't.)  
So to say that "that's essentially how they do it" I think is doing the 
OP a disservice by potentially leading him into a single-threaded trap 
from which it can be very difficult to escape.

E.
From: Barry Margolin
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <barmar-F18375.21031731052004@comcast.dca.giganews.com>
In article <·······························@nntp1.jpl.nasa.gov>,
 Erann Gat <·········@flownet.com> wrote:

> In article <····························@comcast.dca.giganews.com>,
>  Barry Margolin <······@alum.mit.edu> wrote:
> 
> > In article <·····················@fed1read01>,
> >  Ari Johnson <·····@hotmail.com> wrote:
> > 
> > > I'm understanding more and more how CL implementations work, but I am 
> > > wondering if they handle the following more efficiently than I can come 
> > > up with off-hand:
> > > 
> > > (defvar a)
> > > (setq a 0)
> > > (let ((a 1)) ...)
> > > 
> > > The best implementation I can come up with makes the LET look like this:
> > > enter: 1. (push (symbol-value 'a))
> > >         2. (setf (symbol-value 'a) 2)
> > >         3. Let block forms
> > > exit:  4. (setf (symbol-value 'a) (pop))
> > 
> > That's essentially how they do it.  There are some complications that 
> > arise in implementations that support multi-threading, but you've got 
> > the basic principle right.
> 
> I take issue with your characterization.  You give the impression that 
> the naive algorithm is fundamentally correct, and that the difficulties 
> that arise from multithreading are mere details.

My understanding is that multi-threaded Lisps simply unwind the special 
PDL when performing a thread switch.  The specific details of how they 
do this is hardly necessary to understanding the basic idea of special 
bindings.

-- 
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-701B64.18520331052004@nntp1.jpl.nasa.gov>
In article <····························@comcast.dca.giganews.com>,
 Barry Margolin <······@alum.mit.edu> wrote:

> In article <·······························@nntp1.jpl.nasa.gov>,
>  Erann Gat <·········@flownet.com> wrote:
> 
> > In article <····························@comcast.dca.giganews.com>,
> >  Barry Margolin <······@alum.mit.edu> wrote:
> > 
> > > In article <·····················@fed1read01>,
> > >  Ari Johnson <·····@hotmail.com> wrote:
> > > 
> > > > I'm understanding more and more how CL implementations work, but I am 
> > > > wondering if they handle the following more efficiently than I can come 
> > > > up with off-hand:
> > > > 
> > > > (defvar a)
> > > > (setq a 0)
> > > > (let ((a 1)) ...)
> > > > 
> > > > The best implementation I can come up with makes the LET look like this:
> > > > enter: 1. (push (symbol-value 'a))
> > > >         2. (setf (symbol-value 'a) 2)
> > > >         3. Let block forms
> > > > exit:  4. (setf (symbol-value 'a) (pop))
> > > 
> > > That's essentially how they do it.  There are some complications that 
> > > arise in implementations that support multi-threading, but you've got 
> > > the basic principle right.
> > 
> > I take issue with your characterization.  You give the impression that 
> > the naive algorithm is fundamentally correct, and that the difficulties 
> > that arise from multithreading are mere details.
> 
> My understanding is that multi-threaded Lisps simply unwind the special 
> PDL when performing a thread switch.

I was not contesting the factual correctness of your assertion, only the 
spin you put on it.  The technique you describe is commonly used but 1) 
it is ineffecient, 2) it typically doesn't work with OS-native threads 
and 3) it fails utterly on multiprocessors.  I believe it does the OP a 
disservice to sweep these shortcomings under the rug as mere details.

> The specific details of how they 
> do this is hardly necessary to understanding the basic idea of special 
> bindings.

True, but the OP was asking specifically about implementation details.  
I got the impression that he already had a good grasp of the basic idea.

E.
From: Edi Weitz
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <878yf8tgmf.fsf@bird.agharta.de>
On Mon, 31 May 2004 11:03:58 -0700, Ari Johnson <·····@hotmail.com> wrote:

> I'm understanding more and more how CL implementations work, but I
> am wondering if they handle the following more efficiently than I
> can come up with off-hand:
>
> (defvar a)
> (setq a 0)
> (let ((a 1)) ...)
>
> The best implementation I can come up with makes the LET look like
> this:
> enter: 1. (push (symbol-value 'a))
>         2. (setf (symbol-value 'a) 2)
>         3. Let block forms
> exit:  4. (setf (symbol-value 'a) (pop))

This might be interesting:

  <http://www.franz.com/support/documentation/6.2/doc/multiprocessing.htm#wide-binding-1>

Edi.
From: szymon
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <87llj8w8me.fsf@darkstar.example.net>
Edi Weitz <···@agharta.de> writes:

> [.....]
> This might be interesting:
>
>   <http://www.franz.com/support/documentation/6.2/doc/multiprocessing.htm#wide-binding-1>

Which "free lisp" has similar multiprocessing features?

TIA, szymon.
From: Erann Gat
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <gNOSPAMat-988CDD.18592231052004@nntp1.jpl.nasa.gov>
In article <··············@darkstar.example.net>, szymon <···@wp.pl> 
wrote:

> Edi Weitz <···@agharta.de> writes:
> 
> > [.....]
> > This might be interesting:
> >
> >   <http://www.franz.com/support/documentation/6.2/doc/multiprocessing.htm#wi
> >   de-binding-1>
> 
> Which "free lisp" has similar multiprocessing features?

For bonus points: why is the answer to that question such a short list?

E.
From: Kaz Kylheku
Subject: Re: Implementation of LET with special variables
Date: 
Message-ID: <cf333042.0406020854.101bec23@posting.google.com>
Ari Johnson <·····@hotmail.com> wrote in message news:<·····················@fed1read01>...
> I'm understanding more and more how CL implementations work, but I am 
> wondering if they handle the following more efficiently than I can come 
> up with off-hand:
> 
> (defvar a)
> (setq a 0)
> (let ((a 1)) ...)
> 
> The best implementation I can come up with makes the LET look like this:
> enter: 1. (push (symbol-value 'a))
>         2. (setf (symbol-value 'a) 2)
>         3. Let block forms
> exit:  4. (setf (symbol-value 'a) (pop))

But even this implementation can be optimized.

Firstly, there doesn't have to be a simple push-down stack. Rather, an
entire frame is allocated in one operation. That frame contains
backing storage for non-closure lexical variables, and all of the
cells for saving and restoring dynamic variables, plus other material
related to the dynamic contour, like restarts, handlers, catch tags,
etc.

Secondly, in some cases a locally overridden dynamic variable behaves
exactly like a lexical variable. The difference is only apparent in
two ways: the variable has to be available to functions that are
called out of that dynamic contour, and its binding is not subject to
lexical capture. If the compiler can rule out these situations, a
dynamic variable can be subject to aggressive caching optimizations,
just like a lexical one:

Consider"

  (let ((*special-x* 3))
    ;; code that doesn't call anything that could store or retrieve
the
    ;; dynamic value of *special-x*, and makes no escaping closures
    )

In this code, *special-x* can be stack allocated, and in fact it could
even be optimized to a register. If it's never assigned to, it can
even be treated as effective manifest constant representing 3. There
is no need to save and restore anything.

Even if the variable needs to be saved and restored, the compiler can
still do flow analysis and over sections of code arrange for the
variable to be cached. It just has to be spilled back to its dynamic
location before a call is made to something which might retrieve the
value from that location, and has to be re-loaded back to a register
after such a call completes. The compiler can know about the semantics
of all of the standard CL functions, so it can know for instance that
if you call something like APPEND or CONS, these have no interaction
with a user-defined special variable, and consequently, the caching
can be carried across these calls.