Articles Feed

Chirb Statemachine Talk

by: micah | May 8th, 2007 | 1 comments »

Last night I presented the Ruby Statemachine Gem to the Chicago Ruby Users Group (Chirb) Below are links to download the slides and coding example used.

Finite State Machines and the Statemachine Ruby Gem (Slides):

• statemachines_chirb0407.pdf

Statemachine Exercises:

• statemachine_exercise.zip
• parser_spec.rb - Additional specs contributed by Michael Buselli

Understanding Statemachines, Part 4: Superstates

by: micah | April 7th, 2007 | 4 comments »

Superstates

Often in statemachines, duplication can arise. For example, the vending machine in our examples may need periodic repairs. It’s not certain which state the vending machine will be in when the repair man arrives. So all states should have a transition into the Repair Mode state.

In this diagram, both the Waiting and Paid states have a transition to the Repair Mode invoked by the repair event. Duplication! We can dry this up by using the Superstate construct. See below:

Here we introduce the Operational superstate. Both the Waiting and Paid states are contained within the superstate which implies that they inherit all of the superstate’s transitions. That means we only need one transition into the Repair Mode state from the Operational superstate to achieve the same behavior as the solution in diagram 1.

One statemachine may have multiple superstates. And every superstate may contain other superstates. ie. Superstates can be nested.

History State

The solution in diagram 2 has an advantage over diagram 1. In diagram 1, once the repair man is done he triggers the operate event and the vending machine transitions into the Waiting event. This is unfortunate. Even if the vending machine was in the Paid state before the repair man came along, it will be in the Waiting state after he leaves. Shouldn’t it go back into the Paid state?

Superstates come with the history state which solves this problem. Every superstate will remember which state it is in before the superstate is exited. This memory is stored in a pseudo state called the history state. Transitions that end in the history state will recall the last active state of the superstate and enter it.

You can see the history state being use in diagram 2. In this solution, the history state allows the vending machine to return from a repair session into the same state it was in before, as though nothing happened at all.

Code

The following code builds the statemachine in diagram 2. Watch out for the _H. This is how the history state is denoted. If you have a superstate named foo, then it’s history state will be named foo_H.

1. require 'rubygems'
2. require 'statemachine'
4. vending_machine = Statemachine.build do
5. superstate :operational do
6. trans :waiting, :dollar, :paid
7. trans :paid, :selection, :waiting
8. trans :waiting, :selection, :waiting
9. trans :paid, :dollar, :paid
11. event :repair, :repair_mode, Proc.new { puts "Entering Repair Mode" }
12. end
14. trans :repair_mode, :operate, :operational_H, Proc.new { puts "Exiting Repair Mode" }
16. on_entry_of :waiting, Proc.new { puts "Entering Waiting State" }
17. on_entry_of :paid, Proc.new { puts "Entering Paid State" }
18. end
20. vending_machine.repair
21. vending_machine.operate
22. vending_machine.dollar
23. vending_machine.repair
24. vending_machine.operate

Output:

Entering Repair Mode
Exiting Repair Mode
Entering Waiting State
Entering Paid State
Entering Repair Mode
Exiting Repair Mode
Entering Paid State

Next we should cover pseudo states.

Understanding Statemachines, Part 3: Conditional Logic

by: micah | February 12th, 2007 | 0 comments »

Conditions

If you’re doing any significant amount of work with statmachines, you will most certainly encounter some conditional logic in your statemachines. Take our vending machine. When ever a coin is inserted, the invoked event will depend on whether the total amount of money inserted is sufficient to buy something. If enough money has been tendered, the display should suggest that the customer make a selection. If insufficient money has been inserted, the customer should be prompted to insert more.

Conditional logic can be accomplished by using entry actions. See the diagram below.

Starting in the Accept Money state, when a coin is inserted, the coin event is fired and the statemachine transitions into the Coin Inserted state. This is where it gets fun. Upon entering of the Coin Inserted state its entry event is invoked: count_amount_tendered. This method will count the money and invoke the not_paid_yet or paid event accordingly. This will cause the statemachine to transition into the appropriate state.

The Coin Inserted state is unique. You wouldn’t expect to find the statemachine in the Coin Inserted state for any reason except to make this decision. Once the decision is made, the state changes. States like this are called Decision States.

Code

1. require 'rubygems'
2. require 'statemachine'
4. class VendingMachineContext
6. attr_accessor :statemachine
8. def initialize
9. @amount_tendered = 0
10. end
12. def add_coin
13. @amount_tendered = @amount_tendered + 25
14. end
16. def count_amount_tendered
17. if @amount_tendered >= 100
18. @statemachine.paid
19. else
20. @statemachine.not_paid_yet
21. end
22. end
24. def prompt_money
25. puts "$.#{@amount_tendered}: more money please"
26. end
28. def prompt_selection
29. puts "please make a selection"
30. end
31. end
33. vending_machine = Statemachine.build do
34. trans :accept_money, :coin, :coin_inserted, :add_coin
35. state :coin_inserted do
36. event :not_paid_yet, :accept_money, :prompt_money
37. event :paid, :await_selection, :prompt_selection
38. on_entry :count_amount_tendered
39. end
40. context VendingMachineContext.new
41. end
42. vending_machine.context.statemachine = vending_machine
44. vending_machine.coin
45. vending_machine.coin
46. vending_machine.coin
47. vending_machine.coin

Output:

$.25: more money please
$.50: more money please
$.75: more money please
please make a selection

Next lesson: Superstates
Understanding Statemachines, Part 4: Superstates

Understanding Statemachines, Part 2: Actions

by: micah | November 29th, 2006 | 2 comments »

Actions

Part 1 demonstrated how to build states and transitions. Add some actions to that and you’ve got a truly useful statemachine. Actions allow statemachines to perform operations at various point during execution. There are two models for incorporating actions into statemachines.

Mealy: A Mealy machine performs actions on transitions. Each transition in a statemachine may invoke a unique action.

Moore: A Moore machine performs actions when entering a state. Each state may have it’s own entry action.

Mealy and Moore machines each have advantages and disadvantages. But one great advantage of both it that they are not mutually exclusive. If we use both models, and toss in some exit actions, we’ve got it made!

Example:

Remember the vending machine statemachine. It had some problems. Adding some actions will solve many of them. Here’s the same statemachine with actions.

You can see I’ve added three transition actions (the Mealy type). Check out the transition from Waiting to Paid. When this transition is triggered the activate action will be called which will activate the hardware that dispenses goodies. Also, when a selection is made, transitioning from Paid to Waiting, the release action will cause the hardware to release the selected product. Finally, this version of the vending machine won’t steal your money any more. When an extra dollar is inserted, the refund event is invoked and the dollar is refunded.

Notice that the Waiting state has an entry action (Moore type) and an exit action. When ever the Waiting states is entered, the sales_mode action is invoked. The intent of this action is to make the vending machine blink or flash or scroll text; whatever it takes to attract customers. When the Waiting state is exited, the vending will go into operation_mode where all the blinking stops so the customer do business.

Implementation:

Here’s how the new vending machine can be implemented in Ruby:

1. vending_machine = Statemachine.build do
2. state :waiting do
3. event :dollar, :paid, :activate
4. event :selection, :waiting
5. on_entry :sales_mode
6. on_exit :operation_mode
7. end
8. trans :paid, :selection, :waiting, :release
9. trans :paid, :dollar, :paid, :refund
10. context VendingMachineContext.new
11. end

There are several new tricks to learn here. First is the state method. This is the formal syntax for declaring a state. The informal syntax is the trans method which we’ve already seen. The state method requires the state id and an option block. Every method invoked within the block is applied to the state being declared.

With a state block you may declare events, entry actions, and exit actions. The event method is used to declare transition out of the current state. Its parameters are the event, destination state, and an optional action. The on_entry and on_exit methods are straight forward. They take one parameter: an action. (See below for more on action syntax)

After the waiting state declaration we see the familiar calls to trans. The trans method takes an option 4th action parameter. You can see that the release and refund actions were added this way.

Context:

The final line sets the context of the statemachine. This is an interesting aspect. Every statemachine may have a context and if your statemachine has actions, you should definitely give it a context. Every action of a statemachine will be executed within its context object. We’ll discuss this more later.

Here is a simple context for the vending machine statemachine.

1. class VendingMachineContext
3. def activate
4. puts "activating"
5. end
7. def release(product)
8. puts "releasing product: #{product}"
9. end
11. def refund
12. puts "refuding dollar"
13. end
15. def sales_mode
16. puts "going into sales mode"
17. end
19. def operation_mode
20. puts "going into operation mode"
21. end
23. end

Action Declarations:

With the statemachine gem, actions can be declared in any of three forms: Symbols, String, or Block.

When the action is a Symbol, (on_entry :sales_mode) it is assumes that there is a method by the same name on the context class. This method will be invoked. Any parameters in with the event will be passed along to the invoked method.

String actions should contains ruby code (on_entry "puts 'entering sales mode'"). The string will use invoked with in the context object using instance_eval. Strings allow quick and dirty actions without the overhead of defining methods on your context class. The disadvantage of String actions is that they cannot accept parameters.

If the action is a Proc (on_entry Proc.new {puts 'entering sales mode'}), it will be called within the context of the context. Proc actions are also nice for quick and dirty actions. They can accept parameters and are preferred to String actions, unless you want to marshal your statemachine. Using one Proc actions will prevent the entire statemachine from being marhsal-able.

Execution

For kicks let’s put this statemachine thought a few events.

1. vending_machine.dollar
2. vending_machine.dollar
3. vending_machine.selection "Peanuts"

Here’s the output:

going into operation mode
activating
refuding dollar
releasing product: Peanuts
going into sales mode

That sums it up for actions. Next, we’ll talk about how do deal with conditional login in your statemachine.

Understanding Statemachines, Part 3: Conditional Logic

Understanding Statemachines, Part 1: States and Transitions

by: micah | November 17th, 2006 | 0 comments »

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:

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:

1. require 'rubygems'
2. require 'statemachine'
4. vending_machine = Statemachine.build do
5. trans :waiting, :dollar, :paid
6. trans :paid, :selection, :waiting
7. trans :waiting, :selection, :waiting
8. trans :paid, :dollar, :paid
9. 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.

1. puts vending_machine.state
2. vending_machine.dollar
3. puts vending_machine.state
4. vending_machine.selection
5. 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.

Understanding Statemachines, Part 2: Actions