Hi Folks:
At the end of my Pycon 2011 talk, I mentioned that join patterns were another
concurrency construct I was interested in prototyping. I had also talked with
Christian about implementing select changed Stackless Python's internal
representation - and how it provided insights to how to make a more flexible
API. By the way, Join patterns allows a process to wait for a set of channels
to all complete before proceeding. A powerful feature of join patterns is when
one can wait for M out of N channels to complete. Turns out join patterns are
useful for solving a variety of problems.
I was unaware of join patterns until I read a post in GoLang Nuts. However
after reading the Microsoft Research paper "Jingle Bells: Solving the Santa
Claus Problem in Polyphonic C#," I decided to see if a version of join patterns
could be developed for Stackless Python. By the way, The Santa Claus Problem is
a notoriously difficult concurrency problem.
Again using the amazing PyPy module stackless.py alongside greenlets, and
again, with the help of my friends Kevin and Ted, we have come up with an
implementation. Turns out the select model can be extended to support a
synchronous version of join patterns (the original Jocaml and Microsoft papers
assume the model is asynchronous). So far the only thing that would break from
the new implementation would be anything that depended on a channel balance.
In the weeks to come, I want to clean up the code, fix the unit tests and write
documentation and a few more examples (i.e., Dining Philosophers) before
posting a new version in the Stackless repository.
Here is a taste of the new solution to the Santa Claus problem (I need to add
priority to reindeer by that. I am still working out the API but I think this
solution comes close in brevity with the Haskell solution in the book
"Beautiful Code"
def santa(reindeer, elves):
reindeerPattern =
stackless.joinPattern([stackless.JoinReceiveChanop(ch.receiveCase()) for _, ch,
_ in reindeer])
elfPattern =
stackless.joinPattern([stackless.JoinReceiveChanop(ch.receiveCase()) for _, ch,
_ in elves],3)
while True:
pattern = stackless.select([reindeerPattern, elfPattern])
if pattern is reindeerPattern:
harness(reindeerPattern)
deliveryToys(reindeerPattern)
unharness(reindeerPattern)
elif pattern is elfPattern:
consultWithSanta(elfPattern)
reindeerPattern.reset()
elfPattern.reset()
Cheers,
Andrew
_______________________________________________
Stackless mailing list
[email protected]
http://www.stackless.com/mailman/listinfo/stackless
