6.096 Fall '97
Introduction to Interactive Programming

Laboratory 4: Dispatch and Procedures




Lab Preparation

Designing the FSM controller(s)

In this part of the pre-lab, you were asked to design an FSM for the ButtonHandler. Designing an FSM involves doing the following:

  1. Identifying the inputs to the FSM.
  2. Identifying the different states of an FSM. In general, individual states are differentiated from one another by their behaviors -- an FSM behaves differently depending on what state it is in. Thus, one way to identify the states is to identify and separate the situations where an FSM would behave differently.
  3. Specifying the transition and action rules of the FSM. That is, answer the question: Suppose the FSM is in state S, and it gets input I, what does it do, and what state does it go to next?

Let's try to answer these questions in the case of the Calculator lab:

  1. The inputs to the FSM are pretty obvious. They are the different types of buttons. You may also notice that certain inputs are similar to each other in the sense that FSM reacts to them in similar ways. For example, the digits form one such group of inputs, and the operations form another. As we shall see below, this allows us to simplify the state diagram, and make it more compact.
  2. Identifying the state is a harder task. There are usually many possible answers to this part. How you choose to assign your states would depend on how easy it would be to define the transition and action rules. (Thus steps 2 and 3 are usually done together.) In these solutions, we chose identify 4 different states:
  1. We've already identified most of the basic transition and action rules above. Below is a state diagram that specifies these as well as other rules more completely. In this diagram, the states are depicted as circles, and the transitions and actions are depicted as arrows going from the current state to the next (or the same) state. Each arrow is labeled with the input (bold underlined) that causes the transition, and the actions that are performed with the transition (italics). For example, if we are in ARG2_STATE, and the user presses Equals, then we 1) perform arg1 = arg1 op arg2; 2) display the new arg1 on screen; and finally, 3) move to the AFTER_EQUAL_STATE.

    The FSM shown implements digit op digit eq as well as other features, such as digit op digit op digit op ..., digit op digit eq op digit eq..., etc.

It is important to note that when designing an FSM, one should generally take into account all possible combinations of states and inputs, and define reasonable behavior for them, even for (especially for?) combinations that are not expected. For example, in the diagram above, note that we specified what pressing Equals does in AFTER_OP_STATE and AFTER_EQ_STATE even though it is just nothing.


The general idea in writing code for this FSM is to have a while(true) loop that calls getButton() to get the input, and then depending on this input and the current state, change state and perform actions according to the FSM design.

There are two general ways to translate a state diagram into code:

Switch on the state first, and then switch on the input. Switch on input first, then switch on the state.

We will give examples of both here.

State-Driven Implementation

Here is and example of state-driven code:


Note the following:

Event-Driven Implementation

Another possible implementation has a similar idea but switches on the input first, then switches on the state. The polymorphic ButtonHandler from the Documentation project is actually an example of this. Here is another one:


Note the following in this implementation:

Design Decisions

So which implementation is better? State-driven or event-driven? Since the two implementations are equivalent and can be transformed into one another systematically, it really depends on the situation. Here are some mitigating factors:

This course is a part of

Lynn Andrea Stein'sRethinking CS101 project at theMIT AI Lab and theDepartment of Electrical Engineering and Computer Science at theMassachusetts Institute of Technology.

Questions or comments:

Last modified: Wed Oct 1 01:20:27 1997