From: Marcin 'Qrczak' Kowalczyk
Subject: Threads and dynamic bindings
Date: 
Message-ID: <87zn25pile.fsf@qrnik.zagroda>
Browsing around ACL docs, I noticed that it gives newly created
threads null dynamic environment by default, i.e. toplevel values
of dynamic variables are in effect. I don't know what other
implementations which support threads do in this case, but I vaguely
remember that they do the same.

I would expect the environment to be inherited from the thread which
has created the new thread, and shared with it except areas where one
of the threads establishes a more local binding. I admit that I
haven't used that combination in practice. Why are they reset to
toplevel values?

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

From: Pascal Costanza
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <cm0jg2$4ao$1@newsreader2.netcologne.de>
Marcin 'Qrczak' Kowalczyk wrote:
> Browsing around ACL docs, I noticed that it gives newly created
> threads null dynamic environment by default, i.e. toplevel values
> of dynamic variables are in effect. I don't know what other
> implementations which support threads do in this case, but I vaguely
> remember that they do the same.
> 
> I would expect the environment to be inherited from the thread which
> has created the new thread, and shared with it except areas where one
> of the threads establishes a more local binding. I admit that I
> haven't used that combination in practice. Why are they reset to
> toplevel values?

There was a discussion about this here a few months ago, and IIRC it's 
because the originating threads may die after they have created the 
"inheriting" threads. However, it's possible to implement dynamic 
closures to get the behavior you want.


Pascal

-- 
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87sm7u4oxr.fsf@qrnik.zagroda>
Pascal Costanza <········@web.de> writes:

> There was a discussion about this here a few months ago,

I googled for it. There are lots of threads about the interaction
between threads and dynamic variables; only few of them talk
about bindings in newly created threads, especially on *why* CL
implementations do it this way. I haven't read them all yet.

> and IIRC it's because the originating threads may die after they
> have created the "inheriting" threads.

This is not a problem, just like a function closure which accesses
a lexical variable after the form which introduced it has finished
is not a problem. It just stays longer in threads which need it.

It seems there is no philosophical reason to reject either of the
semantics, it depends how we look at threads - whether they "extend"
the computation which started them or whether they are all born equal
no matter where started from. The question which should judge the
choice is: which is more useful, or less confusing. Unless there is
some philosophical reason I overlooked.

I'm asking because I want to know which behavior would be more "right"
for another language. Since most CL implementations do this differently
than my intuition tells, I'm suspicious.

> However, it's possible to implement dynamic closures to get the
> behavior you want.

What are they? I thought that in order to emulate the "inheriting"
behavior in terms of the "start always from globals" behavior one must
change constructs used for dynamic variables. Or be able to get all
dynamic variables with have been rebound in the current thread, which
is hard or impossible to do portably.

OTOH emulation in the other direction requires to change constructs
used to start new threads: make a "thread spawner" thread from the
toplevel, and let other threads ask it to create new threads instead
of creating them themselves. This is less intrusive, because dynamic
variables are hardwired in much more places than thread creation is.

In other words, if we take dynamic variables for granted, and think
how we might create threads with the semantics we want, then the
"inheriting" semantics is more expressive. It would be the other way
around if we took an existing implementation of threads for granted
and thought about ways to express dynamic variables.

The "inheriting" semantics allows to create a dynamic variable whose
initial binding belongs to a subset of threads (not all and not one),
yet it's possible to be dynamically rebound (if we don't need further
rebinding, a lexical variable is sufficient):
http://groups.google.com/groups?hl=pl&lr=&c2coff=1&selm=u11z90iy.fsf%40comcast.net

For now I'm convinced that inheriting is better, but I have no
experience with threads combined with dynamic variables, so I can't
tell how often the preference for each behavior comes in practice.

Unix processes inherit everything they can. One might argue that they
stay in parent-child relations, so they are different from threads in
this respect. OTOH threads just give more power: they allow for any
thread to wait for termination of another thread, so it's more like
removing an artificial limitation than changing the philosophy.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: Rahul Jain
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87y8hmjzp8.fsf@nyct.net>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:

> Pascal Costanza <········@web.de> writes:
>
>> There was a discussion about this here a few months ago,
> [...]
>> and IIRC it's because the originating threads may die after they
>> have created the "inheriting" threads.
>
> This is not a problem, just like a function closure which accesses
> a lexical variable after the form which introduced it has finished
> is not a problem. It just stays longer in threads which need it.

It is a problem because it needs to be implemented as such.

> It seems there is no philosophical reason to reject either of the
> semantics, it depends how we look at threads - whether they "extend"
> the computation which started them or whether they are all born equal
> no matter where started from. The question which should judge the
> choice is: which is more useful, or less confusing. Unless there is
> some philosophical reason I overlooked.

Ideally, the thread creation operator would allow you to specify the
behavior you want, possibly even with a list toplevel dynamic bindings
that should be established for that thread specifically.

>> However, it's possible to implement dynamic closures to get the
>> behavior you want.

I'm not sure this is really the case. You'd need to move the dynamic
bindings onto the heap instead of the stack so it can be shared by both
stacks. That is, if you want properly implemented dynamic closures where
modifying the value of the binding that was in effect when the new
thread was spawned will be visible in both threads.

> What are they?

They are what you're asking for.

[...]
> For now I'm convinced that inheriting is better, but I have no
> experience with threads combined with dynamic variables, so I can't
> tell how often the preference for each behavior comes in practice.

It can make dynamic variables rather expensive to lookup and requires a
decent amount of machinery in the implementation.

> Unix processes inherit everything they can.

No they don't and what they do inherit isn't the binding, but the value. 
This is completely different from dynamic binding and dynamic closure.

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87d5yy4h2b.fsf@qrnik.zagroda>
Rahul Jain <·····@nyct.net> writes:

>> This is not a problem, just like a function closure which accesses
>> a lexical variable after the form which introduced it has finished
>> is not a problem. It just stays longer in threads which need it.
>
> It is a problem because it needs to be implemented as such.

Ok, implementation difficulty is a reason I deliberately left off
for the moment.

This can be done (I've done it). Perhaps it gives the implementation
less freedom: I know how to do this with deep binding style, but I
don't know how to do this with shallow binding, or whether it can be
sensibly done with shallow binding at all.

I believe this reason doesn't matter in my case (I'm not constrained
to a tradition which prefers shallow binding in Lisp). Deep binding
and shallow binding are different, incomparable tradeoffs, you can't
say that either of them is superior. In my case not all global
variables are dynamic, and rebinding a dynamic variable is not too
common, so I'm not worried. Except extreme cases I value nice
semantics more than ease of implementation. Paul Graham should agree.

It was once said about lexical scoping that it's too expensive to
implement, and reality has shown that it is not.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: Svein Ove Aas
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <cm3mvp$qeb$1@services.kq.no>
Marcin 'Qrczak' Kowalczyk wrote:

> Pascal Costanza <········@web.de> writes:
> 
>> There was a discussion about this here a few months ago,
> 
> I googled for it. There are lots of threads about the interaction
> between threads and dynamic variables; only few of them talk
> about bindings in newly created threads, especially on *why* CL
> implementations do it this way. I haven't read them all yet.
> 
>> and IIRC it's because the originating threads may die after they
>> have created the "inheriting" threads.
> 
> This is not a problem, just like a function closure which accesses
> a lexical variable after the form which introduced it has finished
> is not a problem. It just stays longer in threads which need it.
> 
> It seems there is no philosophical reason to reject either of the
> semantics, it depends how we look at threads - whether they "extend"
> the computation which started them or whether they are all born equal
> no matter where started from. The question which should judge the
> choice is: which is more useful, or less confusing. Unless there is
> some philosophical reason I overlooked.
> 
> [snip lots of thought]

Is there some fundamental reason why we can't have both, with an option to
select behaviour at creation time?

That seems to me like the best option; both behaviours would be useful at
different times, and it's only the programmer who can really decide which
is best at the moment.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87hdoa4ivw.fsf@qrnik.zagroda>
Svein Ove Aas <·········@aas.no> writes:

> Is there some fundamental reason why we can't have both, with an
> option to select behaviour at creation time?

If it's decided at thread creation time, then having only the
inheriting semantics as primitive is enough, because the other can be
simulated by starting a "thread spawner" thread from the toplevel.

* * *

It's worse if this is to be decided per variable, rather than per
thread. Then the thread spawner technique doesn't work. This can be
probably done only by changing the implementation of *some* dynamic
variables, namely those whose behavior should be other than the
default. I think it's impossible to reuse existing dynamic variable
mechanism for emulation of the opposite behavior for some variables
only.

- If the default is to not inherit them, then inherited variables can
  be implemented by hand-implementing deep binding: a thread-local
  list of variable/value pairs, whose tail can be shared between
  threads, plus a default slot inside the variable.

- If the default is to inherit them, then non-inherited variables can
  be implemented by dictionaries indexed by weak references to threads,
  plus a default slot used when the thread has not bound it. Or by
  deep binding, except that the variable holding the list is always
  rebound to nil in new threads. Or in other ways - it's easier to
  implement this by hand, since it's always either "local to current
  thread only" or "shared", with no in-between possibility of being
  local to a group of threads.

Anyway, which state should be inherited and which should start with a
global default in new threads? Most variables that I can think of,
which make sense to be rebound at all, should be inherited.

A language can easily support two builtin kinds of dynamic variables,
but maybe it's not worth the effort.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: Pascal Costanza
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <cm47q2$8qv$1@newsreader2.netcologne.de>
Marcin 'Qrczak' Kowalczyk wrote:
> Pascal Costanza <········@web.de> writes:
> 
>>There was a discussion about this here a few months ago,
> 
> I googled for it. There are lots of threads about the interaction
> between threads and dynamic variables; only few of them talk
> about bindings in newly created threads, especially on *why* CL
> implementations do it this way. I haven't read them all yet.

Sorry, I could have been more helpful than this. The one thread I had in 
mind was the one that includes the following posting: 
http://groups.google.com/groups?selm=c0br80%24na1%241%40newsreader2.netcologne.de

>>However, it's possible to implement dynamic closures to get the
>>behavior you want.
> 
> What are they? I thought that in order to emulate the "inheriting"
> behavior in terms of the "start always from globals" behavior one must
> change constructs used for dynamic variables. Or be able to get all
> dynamic variables with have been rebound in the current thread, which
> is hard or impossible to do portably.

There is a middle ground that one can take: The dynamic closure 
construct can require you to name the special variables that you want to 
capture. I guess this should be useful enough in practice. The link 
above includes the code that does this.



Pascal

-- 
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87y8hm9fg6.fsf@qrnik.zagroda>
Pascal Costanza <········@web.de> writes:

> Sorry, I could have been more helpful than this.

No, it was interesting to read.

> http://groups.google.com/groups?selm=c0br80%24na1%241%40newsreader2.netcologne.de

Thanks. This is a different tradeoff: a simple implementation which
does something more general, doesn't need to use threading primitives
in order to work with threads; but we need to enumerate special
variables which we want to be shared when a closure is passed away
from its original dynamic environment.

I wonder what other uses the ability to capture a part of dynamic
environment has, not related to threads.

This is useful to implement partial sharing in CL, but not a
justification to not inherit bindings by default in another language.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: Rahul Jain
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87zn1y42lm.fsf@nyct.net>
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:

> This is useful to implement partial sharing in CL, but not a
> justification to not inherit bindings by default in another language.

Nothing in CL stops dynamic closures from being the default or an option
that captures _all_ bindings in a CL implementation.

-- 
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <871xfa56tq.fsf@qrnik.zagroda>
Rahul Jain <·····@nyct.net> writes:

>> This is useful to implement partial sharing in CL, but not a
>> justification to not inherit bindings by default in another language.
>
> Nothing in CL stops dynamic closures from being the default or an option
> that captures _all_ bindings in a CL implementation.

What do you mean? #'(lambda ...) is not allowed to make a dynamic
closure. Lambda body must be evaluated in the current, not captured
dynamic environment.

-- 
   __("<         Marcin Kowalczyk
   \__/       ······@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/
From: Bulent Murtezaoglu
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <871xfax9ck.fsf@p4.internal>
>>>>> "MK" == Marcin Kowalczyk <Marcin> writes:
[...]
    >> Nothing in CL stops dynamic closures from being the default or
    >> an option that captures _all_ bindings in a CL implementation.

    MK> What do you mean? #'(lambda ...) is not allowed to make a
    MK> dynamic closure. Lambda body must be evaluated in the current,
    MK> not captured dynamic environment.

Perhaps he had in mind the conversation starting with the posting below:

http://groups.google.com/groups?selm=c01aod%244me%241%40newsreader2.netcologne.de

(This, BTW, is a much more detailed version of the little conversation TimB, 
yourself and I had here a few days ago)

As for nothing stopping them from being an option (dafault?), I am
puzzled too, unless he means that they could be implemented without
breaking the rest of the language (dynamic-lambda ?).  In which case I
am not puzzled but I _could_ disagree using Tim Bradshaw's argument.

cheers,

BM
From: Tim Bradshaw
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <ey3sm7tiqlq.fsf@cley.com>
* Marcin Kowalczyk wrote:
> I would expect the environment to be inherited from the thread which
> has created the new thread, and shared with it except areas where one
> of the threads establishes a more local binding. I admit that I
> haven't used that combination in practice. Why are they reset to
> toplevel values?

One reason I'd prefer not to inherit dynamic bindings is that is
fouls up your expectation of what `dynamic' means.  Imagine a macro
which expands to something like this:

(let ((%secret% (make-secret ...)))
  (declare (special %secret%))
  (unwind-protect
    (multiple-value-progn
      ... user code ...)
    (clean-up-secret %secret%)))

But now, if the user code makes a thread, then it's caught %SECRET%'s
binding, and CLEAN-UP-SECRET is probably no longer safe.

I think that inheriting dynamic bindings would make sense in a
Unix-like `fork' based thread system, where threads are created by
branching the flow of control, so for something like this:

(let ((*print-base* 8))
  (if (zerop (fork))
      ... child process, *PRINT-BASE* is 8
      ... parent process, *PRINT-BASE* is also 8))

it should work like that.  But CL threading systems are not generally
fork based (are any?), instead they typically work by creating a
thread and then asking it to call some function, possibly in one step.
This is similar to how other threading systems work.  Unfortunately
not many other languages have special variables in the way CL does, so
we can't look to what they do.  I personally think inheriting specials
would be very weird in a normal CL threading system.

--tim
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <87pt2x4in7.fsf@qrnik.zagroda>
Tim Bradshaw <···@cley.com> writes:

> (let ((%secret% (make-secret ...)))
>   (declare (special %secret%))
>   (unwind-protect
>     (multiple-value-progn
>       ... user code ...)
>     (clean-up-secret %secret%)))
>
> But now, if the user code makes a thread, then it's caught %SECRET%'s
> binding, and CLEAN-UP-SECRET is probably no longer safe.

It's not specific to dynamic variables. If the secret was passed
through an ordinary lexical variable, the problem would be exactly
the same. It's inherent in explicit resource management combined
with threads accessing these resources.

Disallow referring to non-local lexical variables from thread
bodies? :-)

* * *

Here is an example that I made yesterday, which suggests that special
variables should be inherited. Unfortunately the example is quite
complex, but it's real:

I made a clone of Tetris game. When a piece is falling, a timeout is
computed which tells when it should go one line down.

The player can press the down arrow key, which switches between the
normal speed and 20 times faster speed of falling the current piece
(it's not an immediate drop, because he might want to almost drop it,
then slow it down again and move it left or right under a hanging
obstacle).

Pressing the down arrow should recompute the current timeout.
It should not cancel it immediately, nor start it again from the
beginning - while it would be hard to distinguish in practice anyway
(because the 20 times faster speed is really fast), I wanted the
timing to be perfect. This means that it should recompute the end of
the current timeout, starting from the same time as it was originally
started, but using a different speed in the formula.

The game loop is implemented like this. The main thread processes
the current piece, making it falling at some speed. It receives
asynchronous signals generated by another thread listening to the
keyboard (these signals are similar to CL conditions). Possible
signals are "left", "right", "rotate", "drop" and "quit". The first
three change the position or orientation of the piece (if possible),
and "drop" switches the speed between slow and fast. How to change
the timeout during waiting for the previous value of the timeout?

I implemented a function which I called DynamicSleep. It is similar
to Sleep, but takes a nullary function as its argument instead of the
timeout. The function computes a timeout (a point in time). Whenever
the thread which called DynamicSleep receives an asynchronous signal,
DynamicSleep recomputes the timeout after handling the signal (because
the signal might have changed some state which results in a different
timeout) and resumes waiting, or stops waiting when the new timeout
has already passed. This is a self-contained function, not specific
to Tetris.

How to implement this? In the first version it called Sleep in the
same thread, with an appropriate handler for asynchronous signals
which interrupts waiting after handling the signal using the old
handler.

Unfortunately it was misbehaving when I implemented handling SIGWINCH
and SIGTSTP (which are translated to the same mechanism of asynchronous
signals as used for communication between threads in my language). The
bad case was quite subtle - I will not go into boring details, but the
effect is that interruption of sleeping using a non-local exit caused
to abort of all pending signal handlers, if there were any stacked
above the sleep. I had to change it such that only the sleeping was
interrupted, but if it has already been interrupted by another signal
whose handler did not yet return, the handler should not be aborted.

So the solution was to sleep in a separate thread. DynamicSleep is now
implemented like this (omitting blocking & unblocking of signals):
* start a timer thread, which does:
  - in a loop:
  - compute the timeout using the provided function
  - set up a non-local exit point (escaping continuation)
  - set up a signal handler which performs the non-local exit
    on signal "interrupt"
  - sleep until the computed timeout passes (the sleep might be
    interrupted by the non-local exit from the signal handler)
  - the continuation mentioned above returns here
  - if we returned because of the non-local exit rather than
    because the sleep finished normally, restart the loop
* set up a signal handler which sends an "interrupt" signal to the
  timer thread after handling any signal
* wait for the timer thread to finish.

Now it works. But note that the timeout is computed in a different
thread that the caller might expect. The fact that it uses a second
thread at all is an implementation detail.

It happens that I don't use dynamic variables in the formula of the
timeout. But it would be natural to use it for representing some
of the state (now it's all in one big function with lexical local
variables, but if it was split into several functions, some of the
variables would be changed into dynamic variables to avoid manual
passing them around).

The DynamicSleep function could be implemented independently from
Tetris. Its caller should not care whether it computes the timeout in
the same thread or in a different thread. DynamicSleep itself should
not care which dynamic variables are needed in order to recompute the
timeout. It should just work.

Yes, I could also implement it slightly differently: compute the
timeout in the main thread and pass the updated timeout value along
with the "interrupt" signal. It doesn't invalidate the current way,
which is correct, but would break if dynamic variables were not
automatically inherited and if I actually used them at this place.

-- 
   __("< Marcin Kowalczyk \__/ ······@knm.org.pl ^^
   http://qrnik.knm.org.pl/~qrczak/
From: Tim Bradshaw
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <ey3ekjdidu4.fsf@cley.com>
* Marcin Kowalczyk wrote:

> It's not specific to dynamic variables. If the secret was passed
> through an ordinary lexical variable, the problem would be exactly
> the same. It's inherent in explicit resource management combined
> with threads accessing these resources.

Yes, it is. Special bindings have definite extent: when the form
establishing them is finished, then the binding is too.  Lexical
bindings have indefinite extent.  If you want to arrange life so that
you know that a lexical binding is not captured by something then you
have to conceal it.  I don't want a threading system to violate that
expectation.

--tim
From: Bulent Murtezaoglu
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <877jp55upn.fsf@p4.internal>
>>>>> "MK" == Marcin Kowalczyk <Marcin> writes:

    MK> Tim Bradshaw <···@cley.com> writes:
    >> (let ((%secret% (make-secret ...)))  
    >>    (declare (special %secret%)) 
    >>    (unwind-protect 
    >>       (multiple-value-progn ... user code ...)  
    >>      (clean-up-secret %secret%))) 
    >> 
    >> But now, if the user code makes a thread, then it's caught
    >> %SECRET%'s binding, and CLEAN-UP-SECRET is probably no longer
    >> safe.

    MK> It's not specific to dynamic variables. If the secret was
    MK> passed through an ordinary lexical variable, the problem would
    MK> be exactly the same. 

I vaguely see what you mean but I suspect (and my present intuition
is) that if you are passing secret down the dynamic contour like this,
your expectation is for the extent of the binding to end when you
finish executing the cleanup form.  With a lexical, you the programmer
see what binding is in scope as you write the code and if you'll spawn
threads you'll manage (locks?) whatever it is you want to do
accordingly.  So this is a principle of least surprise argument, I think.
But let's hear what Tim was thinking also.

But I probably argued the other way too (even here?), as you do in the 
example below.

    MK> It's inherent in explicit resource
    MK> management combined with threads accessing these resources.

I agree.  Expectations differ, though. 

[I liked the example enough to delete it!]

cheers,

BM
From: Tim Bradshaw
Subject: Re: Threads and dynamic bindings
Date: 
Message-ID: <ey37jp5idne.fsf@cley.com>
* Bulent Murtezaoglu wrote:

> I vaguely see what you mean but I suspect (and my present intuition
> is) that if you are passing secret down the dynamic contour like this,
> your expectation is for the extent of the binding to end when you
> finish executing the cleanup form.  With a lexical, you the programmer
> see what binding is in scope as you write the code and if you'll spawn
> threads you'll manage (locks?) whatever it is you want to do
> accordingly.  So this is a principle of least surprise argument, I think.
> But let's hear what Tim was thinking also.

I think this is pretty much right.  With a lexical binding you have
indefinite extent *but* you have lexicalness: if something captures
the binding then you can *see* it capture it.  With special bindings
then you can't tell who is looking at the binding, but you *can* know
that when you get to the end of the form the binding no longer exists
because of definite extent.  Bindings which anyone can see and which
*also* have indefinite extent are not a good idea, I think.

--tim