6.005 Elements of Software Construction | Fall 2009
Problem Set 1a: The State Machine Paradigm
Due: Monday, Sept 28, 2009 at 5:00pm

The purpose of this problem set is to give you practice in the basic techniques of the state machine paradigm. You'll construct state transition diagrams for a variety of small problems. In the next problem set, you'll practice implementation patterns.

State Diagram Modeling

Simple models

For these models, we give you the designations of the events, so your task is just to construct a diagram. The focus is on learning the form and meaning of state machine diagrams.

Alarm clock. Draw a state machine for an alarm clock with these input event classes:

and a single output event class:

Energy saver. Draw a state machine for a laptop's energy saving facility that dims the screen after one timeout and turns it off after another, returning to full brightness whenever the user presses a key, and which has the following input event classes:

and these output event classes:

Shopping cart. Draw a state machine for an online store, which allows a user to add and remove items from a shopping cart. Additions only occur when the user is shopping; removals can occur when the user is editing the cart. When done with shopping, the user can save the cart for future use or checkout. If no item has been added, or the last item has been removed, the cart is not accessible. For this problem, we shall model only the inputs and the states they result in; outputs could be added later. The input classes are:

Harder models

For these models, we only give you informal descriptions, and you have to figure out the abstraction: what events to model. The focus is on learning how to model real things with state machines.

Star rating. Many websites (and some applications) let users rate items by selecting some number of stars. On the web, this is usually implemented with a small Javascript program that runs in the browser. In any state, a sequence of stars is displayed, with a (possibly empty) prefix in a distinct color, representing the current selection. The user can extend and contract the prefix simply by hovering over the displayed stars. When the user clicks on a star, the current selection is submitted, and the browser issues an HTTP POST request to the server. The selection may start showing no stars (that is, the empty prefix), or it may already show one star or more. To allow the user to reset to no stars, a click on the final star in the previous submission is treated as a reset.

Model this mechanism as a state machine. You should start by designating event classes; you may need to refine your designations as you think more carefully about the problem. You should include, in addition to the user inputs, the outputs needed both to update the display and to send the final value to the server.

MP3 player. An MP3 player, such as Apple's iPod, contains a hierarchical menu of items, with the internal nodes corresponding to albums and playlists, and the leaf nodes corresponding to songs. The user can navigate around the hierarchy, and select a song to play. When the song is showing, it can be paused and restarted. What makes this design tricky is that the user can navigate the hierarchy while a song is playing; a song is only stopped either when it completes, or when the user starts another song.

Model this mechanism with a textual state machine. The state should include both the position in the navigation (where the user is in the hierarchy), and which song is playing, paused, etc. If you're not familiar with this kind of mechanism, you can read Apple's overview of the classic iPod at http://www.apple.com/support/ipod101/anatomy/. You'll need some way to model the hierarchy. Here's one simple way to do it. Assume each song, album or playlist etc is of some type Node, and you have predefined functions up, down and next which map from node to node in the hierarchy, corresponding to moving up, moving down, and moving through a list. If the current selection state is a node n, then up(n), for example, would give you the node reached by going up one level in the hierarchy. As before, remember to designate your event classes very carefully!

Online registration. Most websites require email validation prior to accepting new members. Here's how the protocol works. The user requests a registration by entering some information including an email address and password. The site sends an email to the user asking for confirmation of the request. The user then clicks on a link in the email message, which completes the registration, and automatically logs the user in. Subsequent visits to the website require explicit login. If the user does not respond to the confirmation within some time period, the request information is dropped, and a subsequent confirmation will fail.

Model this mechanism as a state machine. Again, pay careful attention to event designations.

State Machine Reasoning

Radiation therapy. In radiation therapy, it's important to log the dose delivered accurately. Unfortunately, both the disk on which the log is written and the beam that delivers the dose may fail. Here's a simple protocol designed to mitigate this problem.

The dose is broken into small increments of size epsilon, say. Before each increment is delivered, the computer logs a message to the disk recording the incremental dose. Then the computer instructs the beam to deliver the incremental dose. After each of these steps, the computer expects an acknowledgment that it was executed successfully; if not, the entire process is aborted immediately. The beam is mostly reliable; it always either delivers the exact incremental dose requested, or delivers no dose at all; if it sends an acknowledgment, it succeeded in delivering the requested dose. The disk likewise either writes the message faithfully or writes nothing; if it sends an acknowledgment, the write was completed successfully. The disk always remains readable and is never corrupted.

This protocol ensures that when the incremental doses recorded on disk are summed, they are close to the dose actually delivered. Make this statement precise, and prove it by constructing a state machine for the problem and using invariant reasoning.

Construct a state machine modelling this system.

Infrastructure

No code is provided for this problem set. An empty Eclipse project called pset1a will be available for you to pull on the 6.005 svn admin page. Submit your solutions to the exercises as a single PDF file called pset1a-username.pdf (where username is your Athena login name) in the base pset1a directory.

Hints

The power of state machines comes from their simplicity. Don't confuse state machine diagrams with control flow diagrams, and resist the urge to extend the notation in an ad hoc way. Remember to make sure that: