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

shhgs shhgs.efhilt at gmail.com
Mon Dec 12 23:15:30 EST 2011


reindeers = dict( rudolf = defer.Deferred()
                , ....
                )
arrivedElvs = []
threeElvsArrived = defer.Deferred()

def onReindeerArrive(who):
    reindeer[who].callback(True)

def onElvArrive(elv):
    global arrivedElvs
    if len(arrivedElvs) <= 1:
        arrivedElvs.append(elv)
    elif len(arrivedElvs) == 2:
        arrivedElvs.append(elv)
        threeElvsArrived.callback(arrivedElvs)
    else:
        pass

defer.DeferredList(reindeers.values()).addCallback(lambda _ : True).addCallback(playWithReindeers)
elvsArrived.addCallback(playWithElvs)

Above is my pseudo code.  It's not clear if Santa will respond to only to one
of these two events. If so, you may block the other when one get fired.  I
think Twisted's approach is pretty elegant.



On Sun, Dec 11, 2011 at 07:05:54PM -0800, Andrew Francis wrote:
> 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

> _______________________________________________
> Twisted-Python mailing list
> Twisted-Python at twistedmatrix.com
> http://twistedmatrix.com/cgi-bin/mailman/listinfo/twisted-python




More information about the Twisted-Python mailing list