DOC HOME SITE MAP MAN PAGES GNU INFO SEARCH PRINT BOOK
 
Using Simple Finite State Machines - Fsm(C++)

A Simple Vending Machine

Suppose that the vending machine described in the section, Introduction, were controlled by an embedded microprocessor programmed in C++. What would the software look like if it used Fsm(C++)?

The programmer might start by writing action routines that produce the various outputs:

       int click(Fsm& f,unsigned input){
          set the bit in the hardware register that causes
          the machine to emit a single "click"    }
       int clickclick(Fsm& f,unsigned input){
           click(f,input);
           click(f,input);
       }
       int dispense_gum(Fsm& f,unsigned input){
           set the bit in the hardware register
           that causes the machine to dispense gum    }
       int dispense_candy(Fsm& f,unsigned input){
           set the bit in the hardware register that
           causes the machine to dispense candy    }
(You can ignore the parameters and result type of these action routines, since they are irrelevant to the vending machine example. We only sketch the implementation of the functions, which are highly machine-dependent.)

The state transition diagram of Figure 1 ignores the possibility of mistakes--intentional or otherwise--by the vending machine user. For example, what if a user were to insert five nickels in a row? There is no transition specified for a nickel input in the ``twenty'' state, yet clearly the machine must do something. For our simple vending machine, we define a default action routine to handle all such cases:

       int error(Fsm& f,unsigned input){
           set the bit in the hardware register
           that activates the coin release    }

For readability, we introduce names for the machine states and inputs:

       enum States{zero,five,ten,fifteen,twenty};
       enum Inputs{nickel,dime,select_gum,select_candy};

Now we can create an instance of the machine:

       Fsm v(5,zero,error);   // "v" for "vending machine"

The three constructor arguments have the following meaning: (1) the machine will have five states, implicitly numbered 0 through 4; (2) the initial machine state will be zero; (3) the default action routine for the machine will be the function error().

Clearly the machine instance defined above is not ready to control an actual vending machine; for this, we must `program' the desired state transitions. It is instructive, however, to examine the behavior of a ``default'' (i.e., unprogrammed) machine, which is defined as follows: For every possible input, a default machine would: (1) call its default action routine (2) go to state 0. Restated in vending machine terms, the default behavior would be: for every possible coin inserted or button pushed by the user, (1) activate the coin release and (2) go to state zero.

A simple Fsm is programmed by defining a set of transitions. For the vending machine Fsm, we need to define the nine transitions corresponding to the nine arcs in the transition diagram of Figure 1. We do this using function trans(). The four parameters of trans() are: (1) initial state (2) input (3) target state and (4) action routine. See Fsm(C++) for a detailed specification of trans() and all other Fsm functions used in the examples.

       v.trans(zero,nickel,five,click);
       v.trans(zero,dime,ten,clickclick);
       v.trans(five,nickel,ten,click);
       v.trans(five,dime,fifteen,clickclick);
       v.trans(ten,nickel,fifteen,click);
       v.trans(ten,dime,twenty,clickclick);
       v.trans(fifteen,nickel,twenty,click);
       v.trans(fifteen,select_gum,zero,dispense_gum);
       v.trans(twenty,select_candy,zero,dispense_candy);

All transitions not explicitly defined using function trans() continue to exhibit the default behavior. For example, a nickel input in the twenty state will continue to activate the coin release and return the machine to state zero).

The Fsm is now ready to control the vending machine. The control program itself is an infinite loop:

       #include <Fsm.h>
       main(){
           unsigned i;
           while(1){
               get the next value of i from the hardware
                    v.fire(i);
           }
       }

Each pass through the loop invokes v.fire(i), where i is the integer `input.' fire() invokes the action routine associated with this input in the current state and then puts the machine in the appropriate target state. When calling an action routine, fire() passes enough information for the routine to determine anything it might need to know about the context of the transition, and even to change the machine, if necessary. This explains the parameters in user-defined action routines like click(), which are not used in this example. The ability to alter a program inside an action routine leads to `unstructured' programs, and should be used sparingly, if at all. We illustrate this feature in ``A Simple Dynamically-Programmed Fsm''

Action routines are required to return an integer value; this value is returned to the client program as the result of function fire(). No use is made of the function result in this example.

For the program shown above, the input sequence:

       nickel
       nickel
       nickel
       nickel
       select_candy
       nickel
       dime
       select_gum
       dime
       nickel
       select_candy

produces the following output sequence:

       click
       click
       click
       click
       CANDY
       click
       clickclick
       GUM
       clickclick
       click
       RETURN 15 CENTS

From this example, it should be clear that an Fsm `program' falls at about the same level of abstraction as an assembly language program or, better yet, a microprogram. Transition-at-a-time programming produces code that becomes increasingly difficult to read and maintain as programs grow beyond a few dozen transitions. We call our machines simple to emphasize our intention that they used only for relatively simple machines. We may, in the future, provide an Fsm class with a lex-like input language that would raise the level of abstraction to one appropriate for programming more complex machines.


Next topic: A Simple Finite State Acceptor
Previous topic: Examples

© 2005 The SCO Group, Inc. All rights reserved.
SCO OpenServer Release 6.0.0 -- 02 June 2005