Software Design Spring 2008 For lab: 1) clean up your homework repository 2) read these notes For Thursday: 1) design proposal (actually, let's push this to Monday) 2) prepare for a quiz (exam practice question) Exam next Thursday 3 April. (See notes14 for gather/scatter). Processes --------- A process is a running program. It contains: 1) a copy of the program code (the Python interpreter plus the Python program) 2) program data (global variables, but not local variables) 3) initially, one thread of execution, which contains a) a program counter (where in the program are we?) b) a stack of frames (which contain local variables) Threads ------- Abstractly, a thread represents the flow of execution in a program. Usually, a program is executed in a single thread, meaning that at any given time, only one thing is happening. But many interactive programs run multiple threads. For example, at the same time a web browser might 1) download a file 2) render an image 3) play back a sound file 4) update an animated GIF 5) handle events from the user Each of these activities would happen in a separate thread. At a point in time, different threads are executing different parts of the program. Python Threads -------------- Download thread.py from the usual place and run it: from threading import Thread from time import sleep def counter(xs, delay=1): for x in xs: print x sleep(delay) # one thread counts backwards, fast t = Thread(target=counter, args=[range(100, 1, -1), 0.25]) t.start() # the other thread counts forward, slowly counter(range(1, 100), 1) What happens if you use Ctrl-C to try to stop? Q) How can you stop a running thread? A) In general, you can't. Methods that run in the background should check periodically to see if they should keep going. This is a pain. An alternative is the Watcher class in Gui.py. Check it out if you are curious. Q) Why is the Thread interface so horrible? A) I don't know, but you can improve it with something like this: class MyThread(threading.Thread): """this is a wrapper for threading.Thread that improves the syntax for creating and starting threads. See Appendix A of The Little Book of Semaphores, http://greenteapress.com/semaphores/ """ def __init__(self, target, *args): threading.Thread.__init__(self, target=target, args=args) self.start() Then you can create and start a thread the same way you make a Callable: MyThread(counter, range(100, 1, -1), 0.25) This definition of MyThread is in World.py. You can use it in Lab Exercise 10 if you want to, or use Thread directly. hw07 solutions -------------- wb/sd/solutions/PokerHand.py For each hand, I formed two histograms and a sorted list of rank frequencies: def make_histograms(self): """computer self.suits (a histogram of the suits in the hand), self.ranks (a histogram of the ranks), and self.sets, a sorted list of the rank sets in the hand """ self.suits = Hist() self.ranks = Hist() for c in self.cards: self.suits.count(c.suit) self.ranks.count(c.rank) self.sets = self.ranks.values() self.sets.sort(reverse=True) Most of the classification functions are variations on check_sets: def check_sets(self, *t): """check whether self.sets contains sets that are at least as big as the requirements in t """ for need, have in zip(t, self.sets): if need > have: return False return True def has_pair(self): return self.check_sets(2) def has_twopair(self): return self.check_sets(2, 2) # 4 kind is not 2 pair def has_threekind(self): return self.check_sets(3) def has_fourkind(self): return self.check_sets(4) def has_fullhouse(self): return self.check_sets(3, 2) has_straight is a little tricky: def has_straight(self): # make a copy of the rank histogram before we mess with it ranks = self.ranks.copy() ranks[14] = ranks.get(1, 0) # keep track of how many consecutive ranks we have seen. # if it gets to 5, we win! count = 0 for i in range(1, 15): if i in ranks: count += 1 if count == 5: return True else: count = 0 return False Checking for a straight flush was probably the hardest. Here are two solutions. The first is an adapation of the same technique has_straight uses. def has_straightflush(self): # make a set of (rank,suit) tuples s = set() for c in self.cards: s.add((c.rank, c.suit)) # why two parens? if c.rank == 1: s.add((14, c.suit)) # look for five in a row for suit in range(4): count = 0 for rank in range(1, 15): if (rank, suit) in s: count += 1 if count == 5: return True else: count = 0 return False The second solution partitions the hand into 4 subhands: def has_straightflush(self): # make a dictionary that maps from suit to Hand d = {} for c in self.cards: d.setdefault(c.suit, PokerHand()).add_card(c) # check each sub-hand for a straight for hand in d.values(): if len(hand.cards) < 5: continue hand.make_histograms() if hand.has_straight(): return True return False The second solution is shorter and more provably correct. Object invariants ----------------- Precondition: all of the classification methods require a valid histogram and sorted list of set cardinalities There are three ways to handle this kind of dependency: 1) document the precondition the burden is on the user to guarantee the precondition, where "the user" means other programmers that use these methods. + simple, no extra code required + acceptable for private functions/methods - complicates the interface - error-prone 2) guarantee that the precondition always holds a condition that must always be true is called an invariant. make sure that the __init__ method creates a valid histogram make sure that all modifiers update the histogram + least error-prone + requires no additional code in the classifier methods - possibly hard to implement - possibly inefficient 3) compromise: guarantee that the histogram is valid or None initially it's None the first classifier builds the histogram, the rest find it valid all modifiers set the histogram to None + histograms only computed when needed - have to add code to each classifier method