Ann: Stackless Limbo Dancing Works Fine!

[Andrew Henshaw]

Christian Tismer wrote:

> Andrew Henshaw wrote:
>> Christian Tismer wrote:
>> ...snip...
>> 
> [snipped my description as well]
> 
>> Just so that I am clear -- in your concept of channels, can channels be
>> shared among multiple, parallel, sending processes?  What about multiple,
>> parallel, receiving processes?  In other words are your channels similar
>> to the Queue.Queue object?
> 
> a) yes, b) too, c) ...reading up Queue.Queue...
> you meant Java's Queue class?
> No, I don't implement almost any of the methods.

Actually, I meant the Python Queue class.

> And I'm not queueing data, but proclets.
> But yes, it is in fact a simple FIFO which
> triggers reschedules as needed.

Okay, that confirms my understanding.

> 
>> The reason that I ask is that this is different from Occam's behavior
>> (and
>> I believe CSP's).  In those systems, a channel should be assigned to at
>> most one concurrent sender and receiver.
> 
> At any time, there will be only one sender or receiver.
> After one is done, another one may show up through
> the queue.
> Do you say a channel is only conected to at most
> one sender and receiver in the sense of the whole
> program? I believe so, since in Occam, channels
> are denoted literally in the program text.

Well sort of.  A channel can be directly reused by different parallel 
senders/receivers; but, not while the first pair is still active.  For 
instance, let say you have defined 3 processes xmitA, xmitB, and recv, and 
the only parameter to each is a channel.  Then the following is fine:

CHAN c:
SEQ       -- do the following two PARs sequentially
  PAR     -- do the following two processes "in parallel"
    xmitA(c)
    recv(c)
  PAR
    xmitB(c)
    recv(c)

But, the following would be illegal:

CHAN c:
PAR     -- do all three processes "in parallel"
  xmitA(c)
  xmitB(c)
  recv(c)


In the first example, channel c is being reused; but it only connects 
between two processes at any one time.  Furthermore, the direction of the 
channel must not change within the scope of the parallel processes.

In the second example, two processes are trying to both transmit over the 
same channel.  They may not be actually doing it at the same time (for 
example, if you had a semaphore to control access to it); but, Occam does 
not permit such a construct.  That code would be done more correctly as:

CHAN c1, c2, c:
PAR
  xmitA(c1)
  xmitB(c2)
  multiplexer(c, c1, c2)
  recv(c)

and multiplexer would look something like:

PROC multiplexer(CHAN out, CHAN in1, CHAN in2):
  WHILE TRUE
    ALT     -- perform the communication that is first ready, and then the
            -- indented process
      in1 ? data       -- receive data on channel in1
        out ! data     -- transmit data on channel out
      in2 ? data
        out ! data

Well, actually you'd use an array of input channels and a replicated ALT; 
but, I thought this would be clearer.

Notice the use of colons as declaration terminators and indentation for 
block definition.  Very Pythonesque!
  


> 
> I didn't look at Occam in the first place, but
> by reading about the Limbo language. There, a channel
> is a first-class object, and it is explicitly
> shared between processes which might want to communicate.
> This is the reason that bade the implementation look
> this way.

I'd say that is also the case with Occam.

> 
> Anyway I'm not yet convinced if this was a good decision.
> I have no education in parallelism and just followed
> the hints of a couple of people at Bell Labs.
> 
>> If you need to merge the output
>> of multiple processes, then an ALT construct would be used to arbitrate
>> among the individual channels.  Under Occam, sending to the first
>> available receiver is more complex than in CSP, as it doesn't have ALT
>> output guards (difficult to implement on distributed processors, I
>> believe); so, I'd follow the CSP model here.
> 
> I'm trying hard to understand the CSP model at all,
> reading articles, books, ...
> 
>> I suspect you already know all of this, but I thought I would mention it
>> in case there is some advantage to you in (conceivably) simplifying your
>> channel design.  You can still get the more complex behavior, but it
>> would be done explicitly.
> 
> I just tried to do the simplest possible while effective
> thing. As said, I don't have the background to foresee
> if the concept can stand a higher level of communication.
> 
> Does my attempt contradict CSP, and how? Then please
> let me know. I also learned a few days ago that Occam
> systems don't seem to use simple queues, but instead
> pools of processes which are ready to send or receive
> ofver certain channels. Appears to be quite more
> complicated, using explicit scheduling decisions and so
> on. I believe this is also necessary, because Occam
> has to cope with real parallism, true channel I/O between
> multiple processors or even machines and such.
> My simple idea was based on the fact that I have one
> CPU only, and even easier, it is always shielded by
> the Python interpreter, the GIL, so I have complete
> control over this simplified "hardware".

Well, channels don't use queues at all (at least, not without the 
programmer building them).  You may be referring to the classic Occam 
example of using multiple parallel processes to create a pipeline or queue. 
 This is often given as an example because it's easy to visualize and 
demonstrates the simplicity of Occam's parallel model; but, it wouldn't be 
used to create a queue in real code.  A real queue would be done with an 
array and index pointers.  

An Occam channel is very simple and was implemented efficiently in the 
Transputer's microcode.  I suspect that having only a single transmitting 
process and a single receiving process simplifies that task.  As I said 
before, I believe that this holds for CSP also.  The main difference 
between CSP and Occam channels is the ability of an ALT-type construct to 
know whether a receiving process on the other end of a channel is ready to 
receive (called an output guard, IIRC).  In Occam, if you're a transmitting 
process, you can't simply check whether a receiver is ready to go; you have 
to commit to your send and then the communication either completes or you 
block.  As you say, with your complete control over the model, you could 
implement the output guards, if you desired.

> 
> Please let me know. I don't want to fight for my idea,
> but for the best solution in the context of Python.
> We're talking about two pages of code, and I'm happy
> to try out different approaches.
> 
> Thanks & cheers - chris
> 

You're welcome!  

Andy