MIT OpenCourseWarehttp://ocw.mit.edu 6.005 Elements of Software Construction Fall 2008 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.005elements ofsoftwareconstruction designing state machines Daniel Jackson Until now, we’ve been doing a crash course in Java. This is the first lecture of the course proper,starting with state machines --our first software paradigm. a lesson from failurefriendly !re in afghanistanAfghanistan, December 2001 ‣ US soldier uses plugger* to mark Taliban position for air-strike ‣ notices battery-low warning, so replaces battery and calls in coordinates ‣Photograph of PLGR removed due to copyright restrictions. resulting strike kills user and two comrades and wounds 20 others what happened? ‣ replacing battery reset to current position *PLGR: precision lightweight global-positioning satellite receiver Vernon Loeb. Friendly Fire Deaths Traced to Dead Battery; Taliban Targeted, but U.S. Forces Killed. Washington Post. March 24, 2002 3© Daniel Jackson 2008 A tragic story reported in the Washington Post. what can we learn from this? accidents are complex ‣ rarely one cause, so be wary of simple explanations‣ often human factors + technologylessons from this case ‣ design for robustness against all likely failure modes ‣ defaults are dangerous: user should be warned ‣ describe and analyze all usage scenarios 4© Daniel Jackson 2008 There are lots of problems here that could be analyzed. For example, there’s clearly a user interfaceproblem that the device didn’t clearly indicate when it was showing calculated coordinates versusthe coordinates of the user. Like many accidents, this one involved human factors issues in whichthe designers didn’t think through all the ways that user might interact with the machine. Butwhatever the problem was, it’s clear that we need some way to talk about the possible scenarios insimple but precise way. state machines what they are ‣ a simple notation for describing behaviors ‣ succinct and abstract --but not vague! ‣ basis for analysis and for implementation NOCOORDYOURCOORDMYCOORDlocateadjustresetNOCOORDYOURCOORDMYCOORDlocateadjustreset5© Daniel Jackson 2008 State machines give us this simple and precise way of talking about scenarios. Don’t confuseabstract with vague! They’re abstract in the sense that they allow you to express only the importantbits, but that isn’t the same as being vague. A state machine doesn’t tell you everything there is toknow about a system, but what it does tell you --namely what orders events can happen in --ittells you very precisely. our path general strategy ‣ design behavior --> design mechanism ‣ three paradigms covering different aspects of software design first paradigm: state machines ‣ today --state machines for designing behavior ‣ wednesday --design patterns for implementing state machines ‣ friday --analyzing state machines with invariants 6© Daniel Jackson 2008 This strategy is one we’ll follow throughout the course: first learning how to think about designingthe behavior of a system, and only then thinking about designing the mechanism --the system’s internal structure. This is a very important ‘separation of concerns’. It lets you focus on thebehavior without getting mixed up with mechanism issues. And there’s an important sequencinghere too: how can you figure out what mechanism you need to implement a behavior if you don’tknow what the behavior is? For small systems, many programmers just do the behavioral designcompletely in their heads, but that can lead you into real trouble --and many late nights ofrestructuring and debugging. For large systems, teams usually develop requirements andspecification documents. What we’re trying to teach you is the essential notions you need in thosedocuments. The models we’re teaching you in this course are much more succinct than informaldocumentation, can be analyzed automatically by tools (although that’s beyond this course) and canbe translated fairly directly into code, as we’ll see. So constructing these behavioral designs makesit easier to write the code, because they help bridge the gap --the code doesn’t come out of thinair. designing a midi pianoa midi-piano functionality required ‣ play notes on computer keyboard ‣ sustain by holding key down ‣ cycling through instruments ‣ record and playback context ‣ piano depends on keyboard, midi API ‣ this is a dependence diagram --more later need to start by understanding keyboard inputjavax.sound.midimy midi piano‣ keyboard input: press and release ‣ MIDI interface: commands 8© Daniel Jackson 2008 We’ll see more of these kinds of diagrams later. They’re called _dependency diagrams_. Note thatthe edges aren’t labelled: that’s a clue that they’re not state machines! Sometimes people try andmake these various notations look different from one another (eg, by making the boxes slightlydifferent shapes), but our experience is that it’s more trouble than it’s worth: easier just to useplain old boxes and arrows and label your diagrams so you know what they are. Note, btw, that there’s a big decision that’s already been made here: what the context actually is.We could have chosen to use a different API for making the musical sounds, and we could haveimplemented our own keyboard driver. Just defining where your system sits with respect to theoutside world and your assumptions about it is a big step. modeling the contexta single key the state machine ‣ two states, UP and DOWN ‣ UP is the initial state ‣ two input event classes, with these designationsUPDOWNrelprpr: pr: the keyboard driver reports a key pressrel: the keyboard driver reports a releasemeaning: a set of traces ‣ a trace is a sequence of events ‣ traces of this machine are <>...10© Daniel Jackson 2008 The designations are more important than you might think. The biggest mistake novices make withstate machine modeling is that the event classes aren’t right. Formulating a designation --trying tosay exactly what comprises the occurrence of an event --is a big help in checking whether yournotion of the event class is reasonable, and in conveying it to others. Here the crucial idea is thatpr, for example, doesn’t mean that the user actually pressed the key, which is an importantdistinction. Interestingly, not all keyboard drivers generate key repeats in this form. In Gnome, for example (asa student told me after class), the driver actually repeats release-press pairs --in the notation we’llsee next week, the repeat is (rel pr)* rather than pr*. That’s bad news, because it’s not at all clearhow the generated repeats can be distinguished from the real key presses. Note that the trace set is infinite if the machine has a loop in it, although each trace is itself finite --the history of events up to some point in time. This notion of traces was invented by Tony Hoare ina machine formalism called Communicating Sequential Processes. You may be a bit confused ifyou’ve seen the notion of languages and state machines in a computer science theory setting.There, the language usually consists of the set of all complete sequences, which are definedbecause there are some special states that are marked as final. Here we only have initial states. © Daniel Jackson 2008 the whole keyboard represent as parallel combination of state machines ‣ each key’s machine can take steps independently (general rule: shared events must be synchronized, but no sharing here) ‣ traces include <>, , , , 11 UPDOWNrel1pr1pr1...UPDOWNrel2pr2pr212The parallelism here is just conceptual. To implement this kind of parallelism, you could actuallyhave threads running concurrently, but usually you just have separate state components, one foreach of the submachines, and the whole machine runs sequentially with one of the submachinestaking a step at a time. When the ‘alphabets’ of events of the component submachines overlap, theshared events have to happen as one. In this case, there aren’t any shared events, but we’ll seeexamples of this below. © Daniel Jackson 2008 approximate models over-approximation ‣ this model is actually an over-approximation ‣ it allows more traces than can happen (eg ) --try it and see ‣ but this is OK: problem is handling fewer inputs than can occur 12 UPDOWNrel1pr1pr1...UPDOWNrel2pr2pr212This is an overapproximation because it includes traces that can’t happen in practice. In a realkeyboard driver, the keys are not independent. In many, for example, the key repeat on one key isterminated when another key is pressed, so the trace can’t occur, since thepressing of key 2 prevents repeats of key 1. Overapproximation is good because it allows us to use a simpler model. It doesn’t matter if wehandle more input scenarios than actually happen. [Note, not explained in lecture: There’s actually a form of overapproximation for output too, callednondeterminism, in which you show multiple possible outputs happening with the implication thateither they are all equally acceptable, or that some other part of the specification which is notcurrently being considered will say which should happen. This is useful because, again, it makes themodel simpler. But there’s a more subtle reason it helps: if I can show that my system has the righteffect whichever output behavior it chooses, then I’ve shown that any of the implementations youchoose will be OK. Sometimes we just want to make sure that everything will be OK withoutspecifying exactly what the behavior will be. An example of this is giving a caching algorithmwithout saying exactly what the rules are for choosing which line to evict. Sometimes we actuallycan’t control the behavior. In a distributed system, for example, it’s often impossible to get eventsat different hosts to execute in some given ordering, so it’s better to allow whatever ordering canhappen, and make sure the system will work whichever it is.] © Daniel Jackson 2008 modelling the midi API simple interface ‣ just turn each note on and off; need explicit initialization 13 OFFONOFFONendC#beginC#endCbeginCSTARTinitC#C...There’s nothing much going on here: just a simple state machine protocol, just like the kind manyAPIs present. File i/o, for example, has the same kind of protocol: you can’t read or write when thefile is closed, etc. first design draft© Daniel Jackson 2008 !rst design draft design strategy ‣ base structure on input and embed output events ‣ absorb superfluous presses 15 UPDOWNrelk/endnote(k)prk/beginnote(k)prk...kSTARTinitThis shows the result of starting with the basic keyboard and adding output events. I’ve written thisas a generic machine, with the understanding that there is one of these for each key. I’ve assumedsome function, note, that takes a key and returns a musical note associated with it. So begin_note(k) means the begin event for the note associated with key k. Note that there’s no output generatedfor the repeated press events. In lecture, I referred to the filtering of the superfluous presses as ‘debouncing’, but that’s an abuseof terminology. Debouncing means eliminating the spurious press and release events associatedwith the electrical contact of the key’s switch not closing cleanly. state machine semanticsthe i/o shorthand input/output shorthand ‣ i/o label is just a shorthand subtle consequence ‣ o need not follow i immediately ‣ another event can intervene ABi/oAiBoshort for:17© Daniel Jackson 2008 There are different ways that a state machine formalism can handle inputs and outputs. This isperhaps the simplest way. We just say that after the input occurs, the output can happen --and noother inputs until it’s happened. Note that we don’t actually distinguish inputs from outputs in anyformal way, although of course when you designate the events you’ll say which are which. And wedon’t have any notion of outputs following inputs immediately: if this was a component submachinein a parallel combination, another machine could take a step between the i and the o, so that the odoesn’t immediately follow the i. In most situations this is exactly what we want anyway. a state machine is ... ‣ a set of states State = { UP, DOWN, PRESSED, RELEASED } ‣ a set of initial states Init = { UP } ‣ a set of events Event = { pr, rel, begin, end } ‣ a transition relation UPDOWNrelbeginprPRESSEDRELEASEDprendtrans ⊆ State × Event × State = { (UP, pr, PRESSED), (PRESSED, begin, DOWN), (DOWN, pr, DOWN), (DOWN, rel, RELEASED), (RELEASED, end, UP) } ‣ trace set (derived from trans and Init)traces = { <>, , , , , ...}18 Here’s the mathematical definition of a state machine that we’re using. The diagram can betranslated easily into this structure: each box becomes a member of the set of states, each labelname becomes an event class, each edge becomes a tuple in the transition relation. In terms ofwhat the machine actually means though we only care about the traces: the states are just anartifact to help us define the order in which the events can occur. In general, there can be more than one initial state. This allows you to describe overapproximations--it’s another form of non-determinism, which I mentioned before --allowing an execution tostart in any of the initial states. But generally for the machines we’ll look at there’s just one initialstate. recordingexercise draw a state machine where ‣ pressing R key toggles between recording on and off ‣ and switches indicator light to red (on) and green (off) ‣ ignore actual recording for now !RECRECprPsetRedACTIVATEDDEACTIVATEDprPsetGreenINITsetGreen!RECRECprP/setGreenprP/setRedINITsetGreen20© Daniel Jackson 2008 In doing this exercise, some of you didn’t have explicit events for setting the indicator light greenand red, and just labeled the states. That’s not so good, because as we noted before, the statesdon’t really mean anything: it’s only the traces that are observable. adding recording design strategy ‣ add a parallel machine that maintains additional state new events and states ‣ events prR: keyboard driver reports press of R keypr(k): keyboard driver reports press of any key except for R‣ states !REC: recording o"!RECRECprRprRpr(k), rel(k)pr(k), rel(k)REC: recording ondesign question ‣ do we need to worry about key repeats? 21© Daniel Jackson 2008 You might think that this machine says nothing --and you’d be almost right. All it does is parse asequence of keyboard events, deciding whether we’re in the recording mode or not after a givensequence. As we noted before, only traces matter and not states. But we’ll actually use these statesto determine outputs, after elaborating them a bit. There’s no need to worry about key repeats in this case, as we don’t expect the user to hold the Rkey down. If we were worried about them, we could filter them out the way we filtered them out forother keys. textual notation state = (control-state, data-state) ‣ diagram only shows control state ‣ to show data state, use textual notation state //declare state and init List recording = <>; //state component and initial value boolean REC = false; //this component is a mode op pr-R //declare operation when true //precondition: when op can fire do //postcondition: e"ect of operation if (! REC) recording = <>; REC = !REC op pr (k) //any press except an R when true do //append key to recording if (REC) recording = recording ^ //.. and similar op for rel(k) 22© Daniel Jackson 2008 Here’s the elaboration. We want to say what actually gets recorded, and we can’t do that in adiagram. This is a textual state machine. It has exactly the same semantics as a diagram, but thestates and transitions are now implicit. The set of states is declared by giving state components,and each state is then a combination of values of the components. The transitions are declared bygiving operations, each of which defines a set of transitions. For example, the operation pr(k)defines the set of all key press events, where k is the key being pressed. Note that there’s a subtledifference in how I use the terms pr(k) and pr_k. The term pr(k) is a generic press event matchingany key k; the term pr_k is a press event for a particular key k. The operation is like a method: yousupply the argument k. The ! is boolean negation, so REC = !REC just flips the boolean value of REC. This would be bad Javastyle, btw, to name a variable in all caps. I’m doing it here so that it matches the name of the statein the diagram. When the state machine has one particular state component that takes one of asmall set of values, such as REC, it is often called a “mode”. You can think of all the states of themachine being partitioned into the modes: within the mode REC, there are different states corresponding to the different values of the state component recording. The statement “recording = recording ^ ” means that the event of key k being pressed isappended onto the sequence called recording. The ^ is concatenation of sequences, and is thesingleton sequence containing just e. This is standard mathematical notation which unfortunatelyyou can’t use in Java. Note that each operation has two parts, a precondition that says when the operation can occur, anda postcondition describing the way the state is updated. It’s important to understand that althoughthis seems much more complicated than the state machine diagram, the mathematical structureunderneath is the same. So the operation pr-R, for example implicitly defines transitions like (!REC, ), pr-R, (REC, <>)(REC, ), pr-R, (!REC, ) where each state has two components. There are just many more of these than for the diagram,because there’s a transition tuple (REC, s) for example for every recording sequence s. check your understanding what difference would this make? ‣ instead of test in postcondition op pr (k)when truedoif (REC)recording = recording ^ ‣ use precondition op pr (k)when RECdorecording = recording ^ 23© Daniel Jackson 2008 In our example, we didn’t actually use the precondition, because every operation was allowed inevery state. Here’s an example of using it, although it’s not what we want in this case. Suppose weput the test from the postcondition into the precondition. What this now says is not that we onlyupdate the recording sequence when in mode REC but that the pr-R event can only occur in modeREC, which is a very different thing! analyzing recording consider traces ‣ how about this trace? ‣ very strange behavior: recording starts with key release! two simple options ‣ filter out initial key releases ‣ or just allow it (which is what we’ll do) or perhaps ‣ regard as evidence of larger issue ‣ maybe recording should be of musicalstructure and not of user events?!RECRECprRprRpr(k), rel(k)pr(k), rel(k)24© Daniel Jackson 2008 Back to our simple machine. Note that something funny can happen: you can begin a recording witha key being released! There are many ways we could deal with this. We could filter out pr-R eventswhen any other key is depressed. We could do something more complicated and somehow handlethe unmatched release events, either by generating press events to match or by dropping them.What I actually did in my implementation, which you’ll see in the next lecture, is just to ignore thisissue because I wanted to keep things simple. But actually this little detail is a symptom of a much bigger problem. What’s really going on is thatwe shouldn’t be recording press and release events at all. We should be recording musical entities,such as notes of a particular duration and pitch. This little problem here is just the tip of theiceberg. If we go ahead and record only press and release events, we won’t be able to associatedifferent instruments with different notes: recording with one instrument and then playing back andmixing with notes played on another instrument. This is a typical occurrence in a softwaredevelopment: a small glitch reveals that actually the entire abstraction is suspect. It’s one reasonthat thinking carefully about the behavior before you start building is important, because it’s mucheasier to make big changes at this point than when we already have a pile of code written. playbackplayback let’s add a playback mode ‣ use P key for playing back prP: keyboard driver reports P key pressed ‣ add an event to signal end of playback done: output event to signal end of playback first design option ‣ playback only enabledwhen recording is off‣ no key presses during playback PLAYRECprRprRPLAYBKprPdonepr(k), rel(k)pr(k), rel(k)26© Daniel Jackson 2008 This is the most simple notion of playback -it occurs in a mode in which no recording or manualplaying is allowed. I’m ignoring for now the question of what exactly is played back; we’ll come tothat soon. record during playback can you record during playback? ‣ very useful, but much trickier what does playback involve? ‣ generated playback events mergedwith user keyboard events?PLAYBKRECPLAYBKPLAYRECprPdoneprRprRprRprRprPdoneHpr(k),rel(k)27© Daniel Jackson 2008 This is the more sophisticated and useful notion of playback, with recording and playbackinterleaved in any way we please. I’m using a statechart shorthand. The arc coming from the outerbox labeled “pr(k), rel(k)” says that you can have a transition on a press or release of any key fromany of the states inside the box, and the destination of the transition is whatever state you were inbefore. (H) means history and a transition to that special marker means a transition to the last statethat the machine was in inside the larger superstate box. This still doesn’t resolve the question of what is actually played back. Onto that next... © Daniel Jackson 2008 an asychronous solution 28 idea ‣ playback generates press and release events ‣ merge these events on a queue with incoming keyboard events ‣ midi piano sees just one stream of events keyboard inputjavax.sound.midimy midi pianoeventqueueplayback eventsHere’s perhaps the simplest way to handle playback. When the playback key is pressed, all theevents in the recording are added to an input queue, along with whatever events are beinggenerated by the keyboard driver. They can be interleaved in an arbitrary way so long as none ofthe events are delayed too long. As noted above, a better abstraction would be to record andplayback musical notes; in that case, we’d have to split the piano module into two parts, and putthe queue between the two. This isn’t really any more complicated conceptually, but it does requireinventing a whole new set of events, and I wanted to avoid that complication. There is, btw, a trickyissue to do with how the events are timed, which I’ve ignored. A simple solution is to timestampeach press or release with the delay since the last press or release, and have a process that delaysputting the next playback event into the queue by that amount. © Daniel Jackson 2008 the playback machine another over-approximation ‣ which enq events are generated will depend on what was recorded ‣ (that is, reads recording state component) 29 DONEPLAYBK!RECRECdoneprPprRprRpr(k), rel(k)pr(k), rel(k)enq (prk),enq (relk)This diagram describes the enqueuing of the events; it shows that during playback any sequence ofpress and release events can be enqueued. We’re abstracting away the details of which events getenqueued, but it’s pretty straightforward: it’s just the events in the recording sequence that wespecified textually. © Daniel Jackson 2008 more on recording state what would happen if ‣ playback is pressed during record ‣ generated events get played ‣ and added to recording ‣ so they get played back again... oops! ‣ keep two recordings current: holds events being recorded last: holds events being played back ‣ show how these are updated in textual syntax 30 revised recording with playbackstate List last, current = <>;boolean REC = false;op prR doif (REC) last = current else current = <>REC = ! RECop pr (k) //.. and similar op for rel(k) do if (REC) current = current ^ op prPdo //enq events in last31© Daniel Jackson 2008 Here’s the textual description showing how the two lists are handled. I omitted the preconditions,which means that they are by default true. This description doesn’t actually handle how the eventsare enqueued. © Daniel Jackson 2008 !nal state machine state List last, current = <>; boolean REC = false; op prR do if (REC) last = current else current = <>; REC = ! REC op pr (k) do if (REC) current = current ^ op rel (k) do if (REC) current = current ^ op prP do //enq events in last 32 DONEPLAYBK!RECRECdoneprPprRprRpr(k), rel(k)pr(k), rel(k)enq (prk),enq (relk)UPDOWNrelk/endnote(k)prk/beginnote(k)prkkThis is a summary of what we’ve arrived at in our state machine behavior design, and it will be thestarting point for our design of the mechanism. You can think of the textual part as describinganother component state machine that is in parallel with all the others. The first two diagrammaticcomponent machines just summarize this machine from the perspectives of the recording andplayback keys. summary© Daniel Jackson 2008 principles description before invention ‣ before you invent something, understand what’s there ‣ especially important for your design’s environment ‣ eg, keyboard driver and midi API behavior before mechanism, or ‘what before how’ ‣ design the behavior of a system first ‣ easier to design the mechanism when you know what the behavior is ‣ and easier to analyze the behavior when you can ignore mechanism ‣ eg, state machines before Java classes get the details right ‣ details matter for quality, and can hide major structural flaws ‣ eg, details of playback during record determine gross structure 34 addendum© Daniel Jackson 2008 modeling advice grounding in reality ‣ select events first and thoughtfully ‣ give explicit designations saying what they mean ‣ must be atomic and recognizable bad smells ‣ events not designated, event classes not really disjoint ‣ no initial state marked ‣ states or transitions without labels a state machine is not a control flow graph ‣ no behavior inside states ‣ no ‘decision edges’ 36