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

[Andrew Francis]

From: shhgs <shhgs.efhilt at gmail.com>
To: Andrew Francis <andrewfr_ice at yahoo.com>; Twisted general discussion <twisted-python at twistedmatrix.com> 
Sent: Monday, December 12, 2011 11:15 PM
Subject: Re: [Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted

Hi Shhgs:

>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.


Cool!

Okay, I understand your approach: you count the elves and then the right number arrive, you wake Santa.

Twisted does have one important ingredient for solving Santa Claus: a join mechanism in the form of a deferred list. Also the non-preemptive nature of the reactor guards against a lot of the problems in another solution. In this regard, I think a Twisted solution may be more efficient than most Python mechanisms out there.

The main problem I see with a pure Twisted solution is that it really can't impose the priority rule. Perhaps the  way the reactor works makes priority somewhat moot.  Let's assume we could put timestamps on elves and reindeer arrival times (or force reindeer and elves to arrival at specific times).

Now at time T, there are eight reindeer and two elves ready. At T+1, an additional  reindeer and elf are ready (their timestamps are the same, timer resolution notwithstanding). However the Twisted reactor will serialise the events and trigger the callback. For argument, let us pretend the elvesArrive callback is activated and that wakes Santa. Santa consults with the elves. The problem is that all nine reindeer were ready and the priority rule is broken. I am not sure, from inside the callback, one could check to see if nine reindeer were indeed ready.

Also I suspect once you actually coded out the solution, the ancillary things (looping, callLater) would make the code more difficult to read. However that is minor compared to aforementioned problem. 

Cheers,
Andrew


________________________________
From: shhgs <shhgs.efhilt at gmail.com>
To: Andrew Francis <andrewfr_ice at yahoo.com>; Twisted general discussion <twisted-python at twistedmatrix.com> 
Sent: Monday, December 12, 2011 11:15 PM
Subject: Re: [Twisted-Python] How to Solve a Problem Like Santa with Stackless and Twisted

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