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.
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.
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.
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.