Developer

Set up Web applications as finite state machines

Modeling a Web application as a finite state machine provides applications with an easy way to deal with unexpected application events or user behavior. Follow this example to learn more about setting up such a conceptual machine.


While Web applications are among the hottest of topics these days, they employ a programming model that differs from that used by traditional, non-Web applications—one that presents new challenges for developers. Traditional applications have a largely deterministic flow of control, while Web applications perform actions and generate output as a response to external events (HTTP requests) that are beyond the control of the programmer.

There is no way to enforce that these events be made in a certain order or only in certain situations, so special care must be taken to ensure that the application doesn't break if the user does something unexpected. However, as a solution to the problems presented by the Web programming model, let's take a look at the concept of modeling Web applications as finite state machines. By modeling Web applications as finite state machines it is possible to create robust applications that present deterministic responses in any condition or situation.

What is a finite state machine?
The flow of control in a traditional application is basically sequential: The application executes from start to end following the coded logic. Few events can alter the normal flow of execution, and these events are mostly concerned with exceptional conditions. Command line utilities are classic examples of this traditional application.

Another class of applications is driven by externally generated events—that is, events generated outside the application and beyond the control of the application itself or the programmer. The code to be executed depends on the event received and when it arrives in relation to other events. So, the flow of control is neither sequential nor predetermined, because it depends on external events. Event-driven GUI applications are great examples of this latter class of application, because they are driven by commands and selections—events made by the user.

Web applications, which are driven by forms submitted and pages requested by the user, can also be placed in this category. However, GUI applications still have some degree of control over the events received, because they depend on the windows and controls presented to the user—and these things are controlled by the programmer. This isn't the case with Web applications, because the user can easily subvert the designed application logic by doing something unexpected, such as using the browser's history, manually typing links, or even simulating a form submission.

Obviously, a different technique is needed to handle these situations, one that can handle events in any order, and provide a meaningful response even if these events occur in an order different from what’s expected. Finite state machines were conceived exactly to meet this need.

A finite state machine is a conceptual machine that works by performing some action in response to an external event. The action performed can depend not only on the event received, but also on the order in which the event occurs in relation to other events. This is possible because the machine keeps track of an internal state, which is updated as events are received. The action to be performed in response to an event depends both on the event and on the internal state of the machine, and also determines and updates the state of the machine. This way, any logic can be modeled as a sequence of event/state combinations.

Learning by example: A sample application
To make it clear how a finite state machine works and how the concept can be used to build Web applications, let’s take a simple application, a Web-based bookmark manager, and model it as a finite state machine. First let's look at how the application works from a user's point of view:

Users must first log in or register with the application, as shown in Figures A.1 and A.2. If the username/password supplied at login isn't valid or if the username already exists when registering, an error page is displayed, shown as Figure A.4. Once logged in, the user is shown his or her list of favorite Web sites (Figure A.3). From here, the user has several options:
  • Create a new favorite (Figure A.5)
  • Edit or delete an existing favorite (Figure A.6)
  • Close the session (Figure A.7)

If the user doesn't use the links and buttons provided by the application, but tries to type a URL to go directly to a page or uses the browser's history, an error page is displayed (Figure A.8). This ensures that the user follows the path provided by the application instead of trying something that can break it, like clicking the browser's Back button instead of the Cancel link when editing a URL.
Figure A
The sample bookmark manager application

Next, let’s model the application as a finite state machine. One of the best ways to do that is to build a state table that captures all states of the finite state machine, all events that can happen, and the action to be performed for each state/event combination. A state table is represented as a table where each column represents a state, each row represents an event, and the cells represent a state/event combination and contain the action to be executed, which in turn determines the next state of the machine.

Rows or columns for events?
Whether to place events in rows or columns in your state table is really a matter of personal preference. I usually prefer to place events in state tables as rows, but that sometimes makes for wide tables that aren’t easily published on Builder.com. So, for the purposes of this article, I’ve rotated the table, placing states and events in rows and columns respectively.

Building the state table
Building a state table is a relatively simple process. The first thing to do is to identify all an application’s events. In the case of a Web application, it's straightforward, since the incoming requests are the events. Looking at the pages of the sample application, you can identify eleven requests, each corresponding to a unique link the user can click, or a form that he or she can submit. Table A lists all these requests with a detailed description for each one. Notice that I identified each request with a label that will appear in the finished state table.
Table A
Request Description
default Application's entry point; the application's home page URL
login Login page was requested; link to the login page clicked
login_form Login form was submitted; "Login" button clicked
register Registration page was requested; link to the register page clicked
register_form Registration form was submitted; "Register" button clicked
edit Favorite change was requested; "Edit" link clicked
edit_form Edit a favorite form was submitted; "Submit" button clicked
delete Favorite deletion was requested; "Delete" link clicked
add Add new favorite form was requested; "Add new" link clicked
add_form Add new favorite form was submitted; "Submit" button clicked
logout Logout was requested; "Logout" link clicked
favorites Favorites page was requested; "Cancel" link on edit or add forms clicked
Requests for the sample application

The next step is to define the actions. In order to do that, it is necessary to define what the application must do in response to an event and turn that into an action. Following this procedure for the sample application leads to Table B, which lists all actions, identified by a label and with a detailed description.
Table B
Action Description
showLoginPage Display the application's login page
login Handle the submission of the login form; if the username and password are valid, display the favorites page, otherwise display an error page
showRegPage Display the registration page
register Handle the submission of the registration form; if the username and password are valid, display the favorites page, otherwise display an error page
showEditPage Display the form to edit a favorite
update Handle the submission of the edit form; update the favorite and display the updated favorites page
delete Handle the deletion of a favorite; delete the favorite and display the updated favorites page
showAddPage Display the form to add a new favorite
add Handle the submission of the add form; add the new favorite and display the updated favorites page
logout Display the logout page and log the user out
showFavPage Display the favorites page
Restart Action executed on abnormal conditions, or when the user does not follow the links provided; display an error page and resets the application
Actions for the sample application

Finally, you need to define the states of the finite state machine and build the state table. This is an iterative process: Start with an empty table and put each event in a row. Put the finite state machine's initial state in the first column and, for each cell in that column, define the action to perform and the state the finite state machine must switch to. If a given state is previously undefined, you’ll need to create it and add it as a new column in the table. Continue this process until all the table’s cells are completed.

Table C is the final result for the sample application, each cell containing an action (top line) and new state (bottom line) for a given state and event combination.
Table C
  initial state logging in_favorites error

Default

ShowLoginPage
logging

Restart
initial state

Restart
initial state

Restart
initial state

Login

ShowLoginPage
logging

Restart
initial state

Restart
initial state

ShowLoginPage
logging

Login_form

Restart
initial state

Login
in_favorites
or error

Restart
initial state

Restart
initial state

Register

Restart
initial state

ShowRegPage
registering

Restart
initial state

ShowRegPage
registering

Reg_form

Restart
initial state

Restart
initial state

Restart
initial state

Restart
initial state

Edit

Restart
initial state

Restart
initial state

ShowEditPage
editing

Restart
initial state

Edit_form

Restart
initial state

Restart
initial state

Restart
initial state

Restart
initial state

Delete

Restart
initial state

Restart
initial state

Delete
in_favorites

Restart
initial state

Add

Restart
initial state

Restart
initial state

ShowAddPage
adding

Restart
initial state

Add_form

Restart
initial state

Restart
initial state

Restart
initial state

Restart
initial state

Logout

Restart
initial state

Restart
initial state

Logout
initial state

Restart
initial state

Favorites

Restart
initial state

Restart
initial state

Restart
initial state

Restart
initial state

 

registering

editing

adding

 

Default

Restart
initial state

Restart
initial state

Restart
initial state

 

Login

ShowLoginPage
logging

Restart
initial state

Restart
initial state

 

Login_form

Restart
initial state

Restart
initial state

Restart
initial state

 

Register

Restart
initial state

Restart
initial state

Restart
initial state

 

Reg_form

Register
in_favorites
or error

Restart
initial state

Restart
initial state

 

Edit

Restart
initial state

Restart
initial state

Restart
initial state

 

Edit_form

Restart
initial state

Update
in_favorites

Restart
initial state

Editor's Picks