Understanding Statemachines, Part 1: States and Transitions 3
Introduction:
I consider State Machines to be a programming gem. An invaluable tool for the software craftsman’s toolkit. It’s not everyday that a statemachine comes in handly, but for some problems statemachines are the most elegant and robust solution you’ll find.
Perhaps you learned about Finite State Automata in school but could use a refresher. Or perhaps you’ve never heard of these crazy statemachines in your entire software career and your curiosity is piqued. This is a place to learn more.
I’ve found statemachines so valuable I’ve build a Ruby framework to build statemachines. I hope you find this tool valuable… but for that to happen you have to understand statemachines. To that end, this is the first installment of a complete statemachine lesson. Statemachines are simple. You’ll see.
States and Transitions:
The Vending Machine Statemachine Diagram
Above is a UML diagram of the statemachine the runs a simple vending machine. We can see that there are two rectangles with rounded corners. These are States. The vending machine has two possible states, Waiting and Paid. At any given time during execution, the vending machine will be in one of these states.
Note the arrows going from one state to another. These are called Transitions. Transitions are how statemachines change state. Also note that each transition is labeled with an Event. Events are the input to statemachines. They invoke transitions. For example, when the vending machine is in the Waiting state and the dollar event is received, the statemachine will transition into the Paid state. When in the paid state and the selection event is received, the statemachine will transition back into the Waiting state.
This should seem reasonable. Imagine a real vending machine. When you walk up to it it’s waiting for you to put money in. You pay by sticking a dollar in and then you make your selection. After this happy transaction, the vending machine waits for the next client.
This scenario is not the only possibility though. Statemachine are very helpful in examining all possible flows through the system. Take the Waiting state. We don’t normally expect users to make selections if they haven’t paid but it’s a possibility. As you can see this unexpected event is handled by our vending machine. It will simply continue to wait for your dollar. And it would be foolish for someone to put more money in the the vending machine if they’ve already paid. Foolish or not, you and I know it happens. Our vending machine handles this graciously by taking the money and allowing the user to make a selection for the fist dollar they supplied. Effectively the client loses the extra money they put in. (grin)
Implementing the Statemachine:
We have identified 3 fundamental components to a statemachine: States, Transitions, and Events. It turns out that the simplest way to define a statemachine is to define its transitions. Each transition can be defined by identifying the state where it begins, the event by which is invoked, and the state where it ends. Using this scheme we can define out vending machine like so…
| Origin State | Event | Destination State |
|---|---|---|
| Waiting | dollar | Paid |
| Paid | selection | Waiting |
| Waiting | selection | Waiting |
| Paid | dollar | Paid |
Defining it in ruby is not much harder:
require 'rubygems' require 'statemachine' vending_machine = Statemachine.build do trans :waiting, :dollar, :paid trans :paid, :selection, :waiting trans :waiting, :selection, :waiting trans :paid, :dollar, :paid end
The above snippet assumes you have the statemachine gem installed.
Mac users$ sudo gem install statmachine Windows users> gem install statemachine
The outcome of this code an instance of Statemachine stored in the variable named vending_machine. To use our statemachine we need to send events to it. This is done by calling methods that correspond to events.
puts vending_machine.state vending_machine.dollar puts vending_machine.state vending_machine.selection puts vending_machine.state
That’s it for the basics.
This concludes Part 1 of the lessing. Next we’ll learn how to make our statemachine more functional with by adding actions.
BOC 1
BOC is a testing pattern that Unclebob briefly mentioned on fitnesse.org shortly after it was published. It describes the typical steps taken in an automated test.
Experienced test writer use BOC whether they know it or not. For new-commers to automated testing, BOC is lesson #1.
If you think about it, BOC is very logical. Every test is testing something; some Operation that the system under test (SUT) performs. That’s where the Operate step comes from.
In almost all cases, you can’t just invoke the operation. The automated test Builds a testable environment first. Maybe data needs to be put in a database, or a service layer needs to be started. Either way, the Build step comes first.
After invoking the Operation, a test needs to Check that it behaved as expected. Clearly, the Check step has to come last.
Example:
Consider a test for the Withdraw feature of an ATM machine.
Build:
- You can’t withdraw money from an account unless there’s money in it. For the build step, add $500.00 to account 123.
Operate:
- Perform a withdraw of $250.00 from account 123.
Check:
- Check that the balance of account 123 is $250.00.
Next time you’re writing an automated test, think about it. More likely than not, you’re using BOC.
Got Real?
I heard about the Getting Real workshop from a good friend who is a web designer/developer. We used to talk some time ago about using the UI as a tool to drive the development and he told me I should go to the workshop if I could. I have to be honest, I didn’t know that much about 37signals and (you’re welcome to laugh) I didn’t know that one of the speakers was actually the creator of RubyOnRails.
A bit skeptic, I read a blog from somebody that participated in one of the workshops last year and my interest kept growing and growing. I told one of the company’s partners to give it a try and to my surprise he registered everybody for it. “The workshop better be good!” I said to myself.
So there we were, sitting down and waiting to see what these 37signals guys had to say. Right at the beginning of the presentation I learned that a businessman (Jason), a programmer (David) and a UI designer (Ryan) would be the speakers. It sounded like a success formula to me: it would not be about some nerds talking about adding the digit 2 in the 0-1 binary language; it would be about REAL-world professionals talking about REAL web/product development approached from diverse angles beyond the plain and traditional “bit-and-bytes” speech I am used to hear in that kind of activities.
What a way to start!
The speakers did a good job on keeping people interested while sharing without any hesitation the fruits of several years of pragmatic experience. Their advice was rich and wide: from how to integrate organically the layout and usability design with the programming endeavor using the application itself as a real “wireframe”; to business-oriented tips like how to hire the right people effectively. As an architect (on the traditional sense - building design!) it was refreshing to see Christopher Alexander “in-action” on some of their slides while talking about design patterns; and to hear about 37signals’ approach to Mies Van Der Rohe’s aphorism “less is more” applied to all aspects of the product development.
The workshop was great, definitely worth the time and investment and I have no hesitation recommending it to everyone that wants a more “holistic” and practical exposition to what software development should really be (if you want to Get Real!). A sincere “thank you” to the 37signals guys and to everyone there that helped to enrich the workshop with questions and comments.