6.096 Fall '97
Introduction to Interactive Programming

Laboratory 4: Dispatch and Procedures

http://www-cs101.ai.mit.edu/courses/fall97/psets/Calculator/soln

Solutions

Pre-Lab

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:

• ARG1_STATE: This is where we start. In this state, we take numbers and use them to form the first numerical argument, whose value we will store in the field arg1. Once an operation button is pressed, we store the operation in the field op, and then go to the next state, AFTER_OP_STATE.
• AFTER_OP_STATE: This is the state right after an operation button is pressed. At this point, arg1 contains the value of the first argument, and the field op contains some operation that the user wants to perform. However, there is no second argument yet, so we should start waiting for the second numerical argument. Thus, if a numerical button is pressed, we start a new number, store its value in the field arg2, and move on to the next state, ARG2_STATE.
• ARG2_STATE: The FSM is in this state if the user has already started entering a numerical value for the second argument. At this point, arg1, op, and arg2 already contain valid values. Thus, at this point, if Equals is pressed, we can already compute arg1 op arg2 and print the result.
• AFTER_EQUAL_STATE: This is the state right after Equals has been pressed and a computation has been done. In the simplest implementation, we can just stay in this state until the user presses Clear to reset the calculator and go back to ARG1_STATE. However, as we shall see below, we can do more interesting things in with this state.

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.

Laboratory

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:

• State-Driven.

• Event-Driven.

We will give examples of both here.

State-Driven Implementation

Here is and example of state-driven code:

StateButtonHandler.java

Note the following:

• We keep track of the current state using an int field, curState. For readability, we also define private static final int constants for each state. At the beginning of the while(true) loop, curState indicates the current state. Somewhere within the loop, the value of curState is changed to the next state, which takes effect in the next iteration of the while(true) loop.
• Within the while(true) loop, we get an input, button, and then do a switch on curState. Depending on the current state, we call the appropriate "act" method. Note that the word "act" has no special meaning in Java. We just chose to use it here to emphasize that the FSM acts in different ways depending on the current state.
• Each act method then does a switch on the input button. Each of the cases within the switch correspond to an arrow in the state diagram. Thus, within each case we perform the actions specified in the diagram above, and perform the transition by changing the value of curState. Note that we can group cases with the same behavior, such as the digits, by taking advantage of the "fall through" feature of switch -- i.e., a case executes all code from the case until the break, even if there are other cases in the middle.
• Note that we have grouped together common code into internal (private or protected) "convenience methods". Examples of these are appendDigitOrDot(), and doOp().
• Aside from the explicit state represented by curState. The other fields also constitute implicit state variables that affect behavior. For example, the op field specifies what kind of operation is done. Also, arg1, arg2, and even the text field of the display are part of the state which determines the behavior.

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:

EventButtonHandler.java

Note the following in this implementation:

• The code is very similar except that the run() method is different. It now switches on the input button, and calls appropriate "event-handler" methods. Again, note that the word "handle" doesn't have a special meaning in Java. It's just a naming convention that we use.
• Each handler method then switches on the state. Each of the cases here still correspond to an arrow in the state diagram. In fact, the code is exactly the same is in the state-driven implementation. It has just been moved around. Can you see how the code moved?
• You may notice that in this particular example, the event-driven code exposes some commonality in behavior that allows us to combine cases and make the code shorter. For example, in handleOp(), all the cases for ARG1_STATE, AFTER_OP_STATE, and AFTER_EQUALS_STATE all set op to button and curState to AFTER_OP_STATE, and thus can be combined. We have provided an "optimized" version of the event-driven code for your interest: OptEventButtonHandler.java.

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:

• In some cases, you are forced to follow one or the other. For example, if you're working with the Java AWT package, you must generally use event-driven style.
• In some cases, one of the implementations would be more efficient than the other. For example, in the example above, the (optimized) event-driven implementation was ultimately more efficient.
• In some cases, you will move from one model to another. For example, as we did in these solutions, we started with a state-driven model because it was easily-derivable from a state-diagram. Then, we "translated" it to an event-driven version and discovered that we can still optimize the code.
• In general, however, efficiency is not as important as understandability and maintainability. The questions to ask are: which style can you understand better? Which style can other people reading your code several months or years from now understand better? For example, in this case, the state-driven implementation is easier understand and analyze because it mimicks the state diagram more explicitly. The optimized event-driven implementation may be more efficient, but it can also be harder to "decipher". Thus, it may be easier to make mistakes should you or someone else want to extend or modify the functionality of the code. (Note that it is also possible to have an event-driven implementation which is easier to understand than a state-driven one. It really depends on the situation.)

This course is a part of