Finite state machines in JavaScript, Part 1: Design a widget

Develop browser apps with JavaScript and finite state machines

Finite state machines have long been used as an organizing principle for designing and implementing complex behavior in event-driven programs, such as network adapters and compilers. Now, programmable Web browsers have opened a new event-driven environment to a new generation of applications. Browser-based applications, popularized by Ajax, are becoming more complex. Designers and implementers can benefit from the discipline and structure that finite state machines offer. In this article, you, learn how to use a finite state machine to design complex behavior for a simple Web widget -- an animated tooltip that fades into and out of view.

Part 2 in this series will describe how to implement that design in JavaScript, and take full advantage of its distinctive language features, including associative arrays and function closures. Part 3 will cover the practical issues of making the implementation work in all popular Web browsers. The resulting code is compact and concise, its logic is transparent, and its animation performs smoothly even on heavily loaded processors.

Edward J Pring, Senior Software Engineer, IBM

Photo of Edward PringEdward Pring holds an M.S. degree in Computer Science from New York University and a B.S. degree in Mathematics from Stanford University. As part of IBM Research, he has contributed to a wide range of IBM products and technologies, including operating systems, publishing applications, terminal emulators for mainframes, virus protection for personal computers, network automation for the Digital Immune System, and visualization and performance analysis for Web Services. His patent portfolio spans all of these fields.



09 January 2007

Also available in Russian Japanese

This article assumes you have some familiarity with JavaScript, and are interested in a deeper understanding of its more advanced features.

For years, Web designers have quietly exploited the JavaScript interpreters in popular Web browsers to enhance the appearance of their Web sites. They do this mainly by copying short snippets of code into their HTML pages. Now, with the recent popularity of Ajax, software engineers also use JavaScript to develop a new generation of applications that execute within browsers. As browser-based applications grow in size, they will increasingly require the same design patterns and development discipline that have evolved for other execution environments.

Browser-based applications execute in a real-time environment where mouse, keyboard, timer, network, and program events can occur at any time. When the behavior of an event-driven application depends upon the order in which events occur, its programming can become very tangled, and consequently difficult to debug and modify. Software engineers have long used finite state machines, sometimes called discrete or deterministic finite automata in academic circles, as an organizing principle for developing event-driven programs.

The discipline imposed by finite state machines adds rigor to the design by replacing tangled logic with straightforward tables, resulting in simpler implementation and easier testing. Traditionally, finite state machines have proven helpful in developing programs as diverse as network drivers and compilers. They will be equally helpful in developing browser-based applications.

In this series, you'll develop a sample finite state machine application as an exercise to explore some distinctive features of the JavaScript language:

  • Functions are first-class objects: they can be created, assigned to variables, and passed as arguments, just like any other object. Functions can be defined within another function and assigned to global variables or returned as results. Such functions will persist after the function that defines them has returned.
  • Functions can refer to any variable in their lexical scope (the nested braces surrounding the function's definition), such as the local variables of a function that defines them. These variables become part of the function closure (the function, its own variables, and any variables it uses that are defined elsewhere in its lexical scope), and they also persist after the function that defines them has returned.
  • Functions can be stored in associative arrays (arrays that are indexed by names rather than numbers).

These language features provide a compact and concise way to organize actions for events and transitions between states, and an elegant way to cope with differences between browser event models.

The sample application, FadingTooltip, is a more elaborate tooltip than the default built into most browsers. Tooltips created with the FadingTooltip widget use animation to fade into and out of view instead of popping up and abruptly vanishing, and they move with the cursor. The finite state machine pattern used to design this behavior makes its logic transparent. The JavaScript language features used to implement it make the source code compact and efficient.

This article shows how to design the behavior of an animated widget using the graph and table representations of a finite state machine. Subsequent articles will describe how to implement the table representation of a finite state machine in JavaScript, and how to handle the practical issues of testing the implementation in popular browsers.

Basic tooltips

Most modern graphical applications can temporarily display small text boxes containing helpful definitions, instructions, or suggestions when the cursor pauses over some visual control, such as a button, a selector, or an input field. These helpful text boxes were called "balloon help" in early Apple systems. They're called infopops in some IBM products, and ScreenTips in some Microsoft products. In this article, I use the more generic term tooltip.

Popular Web browsers such as Netscape Navigator, Microsoft Internet Explorer, Opera, and Mozilla Firefox will display tooltips for any HTML element that has a title attribute. For example, Listing 1 shows three HTML elements with title attributes.

Listing 1. HTML code for browser tooltips
 Here are some <span title='Move your
    cursor a bit to the right, please.'> fields with built-in tooltips </span>: <input
    type='text' title='Type your bank account and PIN numbers here, please ...' size=25>
    <input type='button' title='Go ahead. Press it. What's the harm? Trust me.' value='Press this
    button'>

The examples page shows how your browser renders HTML elements with the title attribute. Notice how the tooltips appear and disappear as you move your cursor over the elements. The text boxes contain simple text, without any formatting or styling. They pop into view after a short pause in cursor movement, and abruptly disappear after some arbitrary time elapses, or the cursor moves away from the HTML element, or a key is pressed. The browser never displays more than one text box at a time. The appearance and behavior of these tooltips are hard-wired into your browser; you cannot change them.

More elaborate tooltips

Built-in tooltips have much room for improvement, and recent versions of popular browsers provide all of the raw ingredients needed to build more elaborate tooltips. The HTML Division element creates a box that you can position anywhere in the browser's window. You can determine almost every aspect of the box's appearance with cascading style sheets (CSS). Cursor movements programmed in JavaScript can trigger particular actions for any visual element in the browser's window. You can program timers to sequence those actions.

If you use an older browser, you might not see some of this behavior. With the Opera browser prior to version 9, for example, the tooltips pop in and out, instead of fading in and out, because Opera was comparatively late in implementing the opacity style property. See Resources to download current versions of popular browsers.

The examples page also contains some HTML elements with more elaborate tooltips. If you are running a recent version of a popular browser, you can compare the more elaborate tooltips to the built-in tooltips:

  • They fade into view, and later fade from view, rather than popping in and out.
  • They contain images as well as text, and are formatted and styled.
  • While they are visible, they move with the cursor.
  • The fading reverses direction as the cursor moves away from, and then returns to, an HTML element.
  • More than one tooltip can be visible concurrently, some fading out while another fades in.

This enhanced behavior and appearance is not just cosmetic; it improves usability. Users who face busy pages with dozens or hundreds of elements might miss a tooltip that pops instantly into view. The human vision system, which is especially sensitive to motion, is more likely to notice a tooltip that fades into view and moves with the cursor, even when a distracted user's attention is focused elsewhere on the page. The images, formatting, and styling can convey information more effectively than unformatted text. And, all of the parameters of these more elaborate tooltips are configurable.

The rest of this article focuses on designing the FadingTooltip widget as a finite state machine. Subsequent articles will show how to implement and test the code. If you're in a hurry, though, Resources links to the JavaScript source, and an HTML Web page that uses it, to produce the examples above.

Finite state machines

Finite state machines model behavior where responses to future events depend upon previous events. There is a rich body of academic literature in this field (see Resources), but a useful working definition is straightforward. Finite state machines are computer programs that consist of:

  • Events that the program responds to
  • States where the program waits between events
  • Transitions between states in response to events
  • Actions taken during transitions
  • Variables that hold values needed by actions between events

Finite state machines are most useful in situations where behavior is driven by many different types of events, and the response to a particular event depends on the sequence of previous events. The events that drive finite state machines can be external to the computer, originating from a keyboard, mouse, timer, or network activity, or they can be internal to the computer, originating from other parts of the application program, or other applications.

States are a way to remember previous events, and transitions are a way to organize responses to future events. One of the states must be designated as the initial state. There may be a final state, but this is optional, and the FadingTooltip widget does not have one.

Two common representations of finite state machines are:

Directed graphs
Balloons represent states, and arrows between them represent transitions, which are labeled with events and actions.
Two-dimensional tables
Rows and columns represent events and states, and cells contain actions and transitions.

These representations are equivalent, but emphasize different aspects of design. Both are useful, and I use both later in this article.

Developing event-driven programs with finite state machines is a bit more complicated than ordinary procedural programming; it requires more discipline generally, and more design effort in particular. When done well, it can result in simpler code, faster testing, and easier maintenance. Even so, the complexity of finite state machines is not worthwhile for all event-driven programs. When the variety of events is small, for example, or the actions triggered by events are always the same, the extra development effort might not be justified.


Finite state machines and the runtime environment

Finite state machines are event-driven, and need a way to hook themselves to the events of interest in their runtime environment. These hooks, called event handlers, are very small fragments of code inserted into the runtime environment so they will execute whenever particular events occur. When they execute, event handlers need to obtain some basic information:

  • The type of event that has occurred (for example, the cursor has moved, or a timer has expired)
  • The context of the event (for example, which HTML element the cursor is over, or which network request has completed)
  • The location of the finite state machine's own variables and methods

JavaScript is well suited for building event-driven finite state machines. Indeed, JavaScript is perhaps too well suited -- it has three different ways to hook events. Each of these event models is straightforward, but programs must implement all three to ensure that they will run on all popular browsers. The context of an event is passed directly to event handlers in two of these event models; for the other one, JavaScript function closures allow an event's context to be enclosed with its event handler.

JavaScript provides an object model that might seem a bit peculiar to Java and C++ programmers, but is nonetheless entirely adequate for coding the variables and methods of finite state machines. And, JavaScript associative arrays allow you to code the two-dimensional table representation of a finite state machine directly.


Methodically designing behavior

The fundamental ingredients for a finite state machine are the events it responds to, and the states in which it waits between events. The design must consider each possible event for each possible state:

  • Whether the event can possibly happen in that state
  • What actions should be taken to handle the event
  • Which state to transition to after the event
  • What variables need to be remembered between events

I begin the design procedure with a graph, as seen in Figure 1, that shows states as balloons and transitions as arrows connecting the balloons. I end with a table, as shown in Figure 4, that lists events and states as row and column headings, respectively. Each cell in the table lists the actions to be performed when a particular event occurs in a particular state, or else indicates that the event cannot occur in that state.

You usually need several iterations of this design procedure to get the graph and table right. For finite state machines with many events and states, the procedure can be quite tedious, and some discipline is needed to work methodically through each cell in the table during each iteration. This forces you to consider what behavior you want in every possible situation. You might discover opportunities to further elaborate or refine the behavior, or discover you need more (or fewer) states than initially thought, or you might have to shuffle actions between cells to specify the right behavior in every situation.

This methodical procedure for designing finite state machines, though tedious, is well worthwhile. The completed table, as shown in Figure 4, reveals all of the logic for the behavior, and can be translated directly into code (see the actionTransitionFunctions source code).


About JavaScript capabilities

To design the FadingTooltip widget, you need to know some of JavaScript's capabilities. In the spirit of top-down design, I'll sketch the basic ideas here, and defer the details of implementation to the next article in this series.

All popular browsers can pass events to JavaScript code when the cursor passes over any HTML element on the page. These events are called mouseover, mousemove, and mouseout, indicating that the cursor has moved onto, is moving around above, and has moved away from the HTML element. The browser passes the current cursor position with these events. When the events occur, JavaScript can be programmed to dynamically create HTML Division elements, fill them with text, images, and markup, and position them near the cursor.

Browsers do not have native fade-in or fade-out functions, but you can simulate this by varying the transparency (well, actually the opacity, which is the opposite of transparency) of a Division element over time.

JavaScript has two types of timers: one-shot timers that generate a timeout event when they expire, and repeating tickers that generate timetick events periodically. You will need both for the FadingTooltip widget.


Sketching a state graph

Begin your design by reviewing the basic behavior that you want of the FadingTooltip widget. When the cursor passes over a particular HTML element, you want the widget to wait for the cursor to pause over that element. If it does, then you want the widget to fade the tooltip into view, display it for a while, and then fade it away.

Your finite state machine will need to respond to these events:

  • The browser can pass mouseover, mousemove, and mouseout events to JavaScript when the cursor passes over a particular HTML element, moves around within it, and eventually leaves the element, respectively.
  • JavaScript can program timeout events to indicate when the cursor has paused long enough or the tooltip has displayed long enough, and timetick events to animate increases or decreases in the opacity of the tooltip that simulate fade-in or fade-out, respectively.

You'll invent some states for the machine to wait in between events. Let's call the widget's initial state Inactive, which is where it will wait to be activated by a mouseover event. The widget will wait in Pause state until a timeout event indicates that the cursor has paused long enough over the HTML element. Then the widget will wait in FadeIn state while animating the fade-in with timetick events, and then wait in Display state for another timeout event. Eventually, the widget will wait in FadeOut state while animating the fade-out with more timetick events. The widget will return to Inactive state, where it will wait for another mouseover event.

Figure 1 sketches this progression as a graph, representing the states as balloons, the transitions as arrows connecting them, and the events as labels on the arrows. A double border indicates the balloon for the initial state.

Figure 1. Initial sketch of state graph
Initial sketch of state graph

The FadingTooltip widget will have to take some actions for each event it handles:

  • When a mouseover event occurs in Inactive state, it will have to start a one-shot timer before waiting in Pause state.
  • When that timeout event occurs, it will have to create the tooltip (with an initial opacity of zero) and start a repeating ticker before waiting in FadeIn state.
  • Each time a timetick event occurs, it will have to increase the tooltip's opacity slightly. When the tooltip's maximum opacity is reached, it will have to cancel the ticker and start another timer before waiting in Display state.
  • When that timeout event occurs, it will have to start another ticker before waiting in FadeOut state.
  • Each time a timetick event occurs in FadeOut state, it will have to decrease the tooltip's opacity slightly. When the tooltip's opacity reaches zero, the widget will cancel the ticker, delete the tooltip, and return to the Inactive state, where it will wait to be activated again by another mouseover event.

Figure 2 records these actions in the sketch by listing them beneath the event that triggers them.

Figure 2. Initial sketch of state graph with actions appended to events
Initial sketch of state graph with actions appended to events

Translating a state graph into a state table

The graph representations shown above are a good way to start the design of a finite state machine. But the table representation is better for completing the design because it exposes all of the combinations of events and states to consider.

To translate a state graph into a state table, label the rows with event names and the columns with state names. The order of the names is arbitrary; I put the initial state in the first column and the initiating event in the first row. Then, copy the actions and next state for each event into the appropriate cell of the table, as shown in Figure 3.

Figure 3. Initial state table corresponding to initial state graph
Initial state table corresponding to initial state graph

Completing the state table

To complete the design of your finite state machine, consider each empty cell in the table. You need to consider, for each cell, whether that event can occur in that state, and if so, what actions your widget should take in that situation, and what the next state should be. This is the tedious but very necessary part of the design process.

The order in which you consider the cells doesn't matter. It's common to iterate over this step during the design process many times, considering each cell repeatedly, revising their contents frequently, in different orders each time. It is also common to add (or remove) states as a design evolves, prompting further revisions. I'll skip the iterations and summarize this design step by reviewing the results for each state and event in turn.

Inactive state
During this state, only the initiating event that you already considered should occur, since mousemove and mouseout events should be preceded by a mouseover event, and no timers are running. So, you can mark all other cells in the first column "should not occur."

Before moving on, though, consider the mouseover event for this state a bit further. When you eventually create an HTML Division element for the tooltip, you need to position it near the cursor, so you want to save the current cursor position, which the browser passes with this event. And, it's good practice to cancel any running timer before starting a new timer. Add these actions to the mouseover cell.

Pause state

While waiting for its timer to expire, the cursor might move within the HTML element or move away from the HTML element. Decide what actions to take if these events occur, and what the next state should be. If a mouseout event occurs in this state, you want the FadingTooltip widget to return to Inactive state, as if the cursor had never passed over the HTML element at all, but you do need to cancel your timer. Record this action and transition in the mouseout cell .

On the other hand, for a mousemove event, you want the widget to continue waiting for the cursor to pause, which requires that you cancel and re-start the timer. Because you want the tooltip to appear near the cursor, you want to update your saved cursor position. On review, you might realize that the actions and transition for a mousemove event in Pause state are the same as for a mouseover event in Inactive state. Rather than repeat everything in both cells, indicate this duplication directly in the mousemove cell. Mark all other cells in this column "should not occur."

FadeIn state
During this state, while simulating fade-in with timetick events, the cursor can continue to move around. If a mousemove event occurs, move the tooltip to match, and remain in the current state. If a mouseout event occurs, transition to FadeOut state, with the ticker still running, so that subsequent timetick events will decrease the tooltip's opacity from its current value. Record these events and transitions in the appropriate cells, and mark all other cells in this column "should not occur."
Display state
The cursor can, of course, continue to move around. If it moves within the HTML element, you'll want to take the same action as for FadeIn state -- move the tooltip to match. If it moves away from the HTML element, take the same action and transition as for a timeout event in Display state. Indicate both of these duplications directly in the mousemove and mouseout cells, and mark all other cells as "should not occur."
FadeOut state
During this state, while simulating fade-out with timetick events, the cursor can still move around. If it moves within the HTML element, take the same action as for FadeIn and Display states. If the mouse moves away from the HTML element, you need not do anything -- the ticker will continue to run, so that subsequent timetick events will decrease the tooltip's opacity from its current value until it reaches zero.

Don't mark this cell "should not occur," but do indicate that no actions are needed. And, if the cursor moves back over the HTML element, move the tooltip back to the cursor and return to the FadeIn state.

Figure 4 shows all of these additional actions and transitions. The remaining empty cells are "should not occur" situations.

Figure 4. State table for FadingTooltip widget, as designed
State table for FadingTooltip widget, as designed

The table representation of a finite state machine can always be translated back into a graph, since the representations are equivalent. Figure 5 shows the graph representation of the completed table.

Figure 5. State graph for FadingTooltip widget, as designed
State graph for FadingTooltip widget, as designed

Gathering a list of state variables

After the state table and graph are complete, it is useful to review it one more time to gather a list of variables the machine will need to remember between events so that it can execute related actions in different cells. Your finite state machine will need state variables for the things in Listing 2.

Listing 2. Initial list of state variables
 currentState string value equal to one of the
    state names currentTimer pointer to timer object, obtained when set, used to cancel
    currentTicker pointer to ticker object, obtained when started, used to cancel currentOpacity
    float that varies from 0.0 (invisible) to 1.0 (fully visible) lastCursorPosition floats obtained
    from cursor events, used when an HTML Division element is created tooltipDivision pointer to
    HTML Division element, set when created, used when faded, moved, or deleted

Though JavaScript variables are untyped, the values they contain are typed (that is, values of any type can be assigned to any variable). In this spirit, I chose names for the state variables and, in the commentary, indicated the types I expect to assign to them.


Ready to implement

With the completed state table and a list of the state variables, you are ready to implement your finite state machine. Stay tuned, as that is the focus of the next article. Remember, though, that development is an iterative process; you might need to return to the design phase ...

Resources

Learn

  • Ajax: A New Approach to Web Applications: Read Jesse James Garrett's article that coined the term Ajax.
  • The book JavaScript: The Definitive Guide (David Flanagan, published repeatedly by O'Reilly Media between 1996 and 2006): Find exhaustive information on how JavaScript works in browsers.
  • The Standard ECMA-262: ECMAScript Language Specification (Ecma International, 1999) : Peruse the authoritative definition of the JavaScript language implemented by popular browsers.
  • Document Object Model (DOM) Level 2 Events Specification (W3C, 2000): Refer to this spec for the authoritative definition of the DOM Level 2 event model.
  • The Gecko DOM Reference (Mozilla): Get the authoritative definition of the object interfaces, including events, implemented by the Firefox browser.
  • HTML and DHTML Reference (Microsoft): Refer to the authoritative definition of the object interfaces, including events, implemented by the Internet Explorer browser.
  • Chapters 21 "Protocol Representation with Finite State Models" by Andre A. S. Danthine, and 25 "Executable Representation and Validation of SNA" by Gary D. Schultz, et. al. in Computer Network Architectures and Protocols (edited by Paul E. Green, Jr., Plenum Press, 1982): Read historic examples of finite state machines applied to computer network protocols.
  • Chapter 3.5 "Finite Automata" in Compilers: Principles, Techniques, ad Tools (Alfred V. Aho et. al., Addison-Welsley, 1986): Read a description of how finite state machines are applied to computer language compilers.
  • Chapter 5 "Behavioral Patterns" in Design Patterns: Elements of Reusable Object-Oriented Software (Erich Gamma et. al., Addison-Welsley, 1995): Read about the State pattern for a discussion of implementing finite state machines.
  • Chapter 13.25 "TCP State Machine" in Internetworking with TCP/IP (Douglas E. Comer, Simon and Schuster Company, 1995): Read to understand the finite state machine that underlies the Internet.
  • Chapter 15 "State Machines" in the Unified Modeling Language 2.0 Superstructure Specification (Object Management Group, 2004): Read for a complete graph representation of finite state machines.
  • State Chart XML (SCXML): State Machine Notation for Control Abstraction (RJ Auburn et. al., W3C): Read a proposed XML representation of finite state machines.
  • developerWorks Web development zone: Expand your site development skills with articles and tutorials that specialize in Web technologies.
  • The technology bookstore: Browse for books on these and other technical topics.
  • developerWorks technical events and webcasts: Stay current with jam-packed technical sessions that shorten your learning curve, and improve the quality and results of your most difficult software projects.

Get products and technologies

Discuss

More downloads

Comments

developerWorks: Sign in

Required fields are indicated with an asterisk (*).


Need an IBM ID?
Forgot your IBM ID?


Forgot your password?
Change your password

By clicking Submit, you agree to the developerWorks terms of use.

 


The first time you sign into developerWorks, a profile is created for you. Information in your profile (your name, country/region, and company name) is displayed to the public and will accompany any content you post, unless you opt to hide your company name. You may update your IBM account at any time.

All information submitted is secure.

Choose your display name



The first time you sign in to developerWorks, a profile is created for you, so you need to choose a display name. Your display name accompanies the content you post on developerWorks.

Please choose a display name between 3-31 characters. Your display name must be unique in the developerWorks community and should not be your email address for privacy reasons.

Required fields are indicated with an asterisk (*).

(Must be between 3 – 31 characters.)

By clicking Submit, you agree to the developerWorks terms of use.

 


All information submitted is secure.

Dig deeper into Web development on developerWorks


static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=1
Zone=Web development
ArticleID=187235
ArticleTitle=Finite state machines in JavaScript, Part 1: Design a widget
publish-date=01092007