[Stackless] Re: Stackless Python Logic Variables?

[andrew cooke]

Hi,

I'm replying to the stackless list because I think this probably belongs
there (and your mail, Christian, which was copied to the Oz list, doesn't
seem to have appeared, so I guess maybe it's subscription only).  Hope
this is OK, more below...

Christian Tismer said:
> I said:
[...]
>> (1) sounds like it might be better to get involved in a discussion on
>> that list about ways of making multi-threaded programming easier and
>> find out what people there actually want, seeing to what extent logic
>> variables can help.  that way you can get a solution that fits in with
>> the language and has consensus support.
>>
>> it may also be that some people on the list don't know that much about
>> declarative concurrency (in which case suggesting chapter 4 of the
>> book at http://www.info.ucl.ac.be/~pvr/ might be worthwhile).
>
> At least for me, the latter is true. Over the years (and they have
> piled up a little, meanwhile), I got a bit tired of reading interesting
> somethings that engaged people were trying me to read, finally.
> I'd like to beg your pardon about that. I consider this a weakness
> of age, although this fight is still open and will hopefully stay
> open for at least another 35 years.
> Having that said, I think this age is over, and I'm ready again
> to read and digest everything, after I have found, accepted,
> and overcome my personal limits.
[...]

Maybe I can introduce some of the ideas.  I know less about Oz and logic
variables than I do about Python, and I'm an expert in neither, so the
following probably contains errors.  Also, I haven't read the PEP that
James posted, so I may raise points that he's already covered.  Since this
will probably contain all I know on the subject I doubt I'll post again,
but maybe it will lead to discussion amongst others.


OK, logic variables are neat for a variety of reasons, but the one that's
most relevant to Stackless Python is probably the way in which they
simplify programming with several threads (note that the following doesn't
(as far as I can see) related to coroutines since the yield statement
itself manages the flow of information between the two
"psuedo-processes").

Rather than immediately explain how logic variables help inter-thread
communication it's probably worth first describing the CSP (Communicating
Sequential Processes - a famous book by Hoare, now available at
http://www.usingcsp.com/) approach to the same problem, because I believe
they are more or less equivalent, and you may find that the CSP part of
logic variables is all that is needed (logic variables simplify the CSP
approach and also allow other neat things, unrelated to threads).

The CSP approach, in brief, means that when one thread requires a value
from another thread it pauses.  The other thread will, at some point,
calculate the value and send it to the waiting thread.  This frees the
waiting thread, which can then continue.  The secondary thread does not
block after sending the message, but may itself block if it needs data
from some other thread, etc...

Clearly this can be implemented with the "usual" (ie C language like)
mutex constructions.  The advantage is that the approach is somewhat
cleaner and higher level.  Mutexes allow you to do many things (some of
them stupid!), while CSP really only has this simple idea of waiting for a
value from another thread.

This approach has been around for some time.  Occam used it (the language
used on transputer based parallel systems).  There was/is a (independent)
Java library that supports the approach.  There may well be a Python
library too.  I believe Ada uses it...

Now, returning to logic variables - how do they support CSP style
communication?  Very simply.  All logic variables are initially undefined.
 Any operation on an undefined logic variable (except assignment) pauses
the thread.  So variables work as a CSP channel.  If one thread is trying
to execute A+B and B is undefined then the thread will pause.  When
another thread assigns a value to B, the first thread will then continue
(assuming that A is bound).

So logic variables are a simple, language-level way of supporting CSP. 
However, they are much more - they allow a very elegant approach to
programming.

But at this point I have to stop and say that I don't know how relevant
this is to Python.  I am learning Oz, in which all variables are logic
variables, and it leads to very elegant programs, but I do not know how
well these ideas would carry across into Python.  This is why I explained
about CSP first - I wanted to separate the approach to communicating
between threads from the rest of logic variables so that you can
understand more clearly the different issues involved.

Back to logic variables.  Two more properties support the elegant
(declarative) style of programming that I admire in Oz.  First, once
values take a value they cannot change.  This is normal for functional
languages, but a big change to Python (indeed, I cannot see how objects
make sense without mutable values - Oz supports objects, but does so by
introducing a new kind of (mutable) variable).  Second, relations can be
defined between variables even when they are undefined.

This second detail means that if I declare that A=B when both are
undefined and then later declare A=3, then B automatically takes the value
3.  Another example is linked lists - normally in functional programming
it is only possible to extend a list efficiently at one end.  With logic
variables, however, you can make a list in which the variable at "the
other end" is undefined.  Later, if you want to extend at the "slow" end,
you assign to that variable (this is a very bad description of something
called "difference lists" in the literature) (this is clearly irrelevant
to Python lists, which are arrays).

Together these features allow you to write functions and generate data
structures in a way that makes their logical structure very clear.  You
are freed from worrying about the exact order of calculations because
undefined values can be "filled in later".

Now all this may sound very odd, and very un-Pythonic.  I agree!  I am not
criticising Python in saying this - Python is Python and Oz is Oz and
there is no reason why they should be the same language.  I expain all
this only because I think it is interesting (of course, if you can find
ways to add these things to Python, that owuld also be interesting...)


That's enough.  I hope that explains something about logic variables and
how they might help Python manage inter-thread communication.  I hope
people think that part, at least, of my explanation was very simple and
not very exciting.  That doesn't mean it's not useful - sometimes
simplicity is a good idea.

Whether the rest is any use to you, I am less sure, but I hope it makes
whatever James proposed easier to understand (or at least persuades
someone to read it! :o)

Cheers,
Andrew

-- 
http://www.acooke.org/andrew
_______________________________________________
Stackless mailing list
Stackless at www.tismer.com
http://www.tismer.com/mailman/listinfo/stackless