[Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted

Andrew Francis andrewfr_ice at yahoo.com
Sun Dec 11 22:05:54 EST 2011


Hi Folks:

I don't know what to file this under but here goes:

Santa repeatedly sleeps until wakened by either all of his nine 
reindeer, back from their holidays, or by a group of three of his ten 
elves. If awakened by the reindeer, he harnesses each of them to his 
sleigh, delivers toys with them and finally unharnesses them (allowing 
them to go off on holiday). If awakened by a group of elves, he shows 
each of the group into his study, consults with them on toy R&D and 
finally shows them each out (allowing them to go back to work). Santa 
should give priority to the reindeer in the case that there is both a 
group of elves and a group of reindeer waiting 

I recently modified the stackless.py library to support yet another new concurrency feature: join patterns. Well I think of my version as a sawed-off version of join patterns. Join patterns are a synchronization and message passing construct. The closest thing to a join pattern in Twisted is a deferred list. Stackless has nothing of the sort.


The Santa Claus Problem is a notorious problem in concurrency (http://www.youtube.com/watch?v=pqO6tKN2lc4). I have come up with a relatively short solution.  I think one would be hard pressed to come up with a shorter solution in Python. My desire was to compete with Simon Peyton Jones Haskell version in "Beautiful Code." The full solution is here: http://andrewfr.wordpress.com/2011/11/30/the-santa-claus-problem-with-join-patterns. The nucleus is: 
def santa(reindeer, elves):
    joinObject = stackless.join().addPattern([ch for _, ch, _ in reindeer]).\
                                  addPattern([ch for _, ch, _ in elves],3)

    reindeerPattern, elfPattern = joinObject.patterns

    while True:
        pattern = joinObject.join()
        if reindeerPattern.ready():
            print "*** REINDEER GET PRIORITY ***"
            reindeerPattern.join()
            pattern = reindeerPattern
        if pattern is reindeerPattern:
            harness(reindeerPattern)
            deliveryToys(reindeerPattern)
            unharness(reindeerPattern)
        elif pattern is elfPattern:
            consultWithSanta(elfPattern)

    stopTwisted()

In this solution I use Twisted to control the timer (I use the blockOn technique that Christopher Armstrong first used). 

def tick(seconds):
    tickCh = stackless.channel()
    reactor.callLater(seconds, tickCh.send, None)
    tickCh.receive()

However I could just as easily make reindeer and elves web services or RestFull interfaces. I am still working on the  Join Pattern API. Also it has also been a goal of mine to write a stacklessreactor to better integrate Stackless with the Twisted Reactor.

Cheers,
Andrew
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://twistedmatrix.com/pipermail/twisted-python/attachments/20111211/5c526a94/attachment.htm 


More information about the Twisted-Python mailing list