This lecture introduces the concept of Finite State Machines via the construction of Graphical User Interface ("GUI") "Cheap Calculator" program which can do the four basic arithmetic operations: addition, subtraction, multiplication and division.
To see where we are going, download and run the demo (executable jar file--select "Open" when downloading): calc.jar As you can see this is a really cheap calculator: it misses a couple of digit buttons and does not support subtraction nor division. Nevertheless, it seems to calculate arithmetic expression in infix notation correctly. What do we mean by an "infix" expression? A binary operation is said to be in infix notation if the operator (e.g. +) is in between the two operands. There are also "postfix" and "prefix" expressions. The following table shows an example of each form of notation.
Adding two numbers x, y together
Infix Notation x + y Prefix Notation + x y Postfix Notation x y +
I am interested in writing a GUI application that simulates the behavior of a "cheap" infix calculator. As the user interface, this calculator has on the outside:
· 10 buttons labeled 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, respectively, to enter digit characters
· one button labeled . to enter the decimal point
· one button labeled +, to perform addition
· one button labeled *, to perform multiplication
· one button labeled =, to compute the result of the input so far
· one button labeled C, to clear all entries in the calculator and reset the calculator to its pristine initial state.
· and a display text field for me to view the input and the result of my desired computation.
Inside this calculator is perhaps some kind of electronic circuit board capable of carrying out the actual computations. The GUI provides the only way for me to interact with the internals of the calculator. How do I want the calculator to behave like? For a start, as I click on the digit buttons, I expect the calculator to accumulate the digits by concatenating them together and displaying the result on the display text field. But wait! What if I only click the digit '0' button? The calculator should not concatenate one '0' after another, should it? Run the demo and check it out yourself!
Now, try this: click '3', then click '+', then click '0' four times. This time around, clicking '0' results consistently in concatenating '0' to the existing display text. The calculator has changed its "click '0'" behavior after I click a digit button that is not a '0'. We say that the calculator has gone through a "state change" and behaves differently in each state.
Here is another of example.
First click C to reset the calculator. The display should show '0'.
Now, click '3', then '3' again, then '3' again.
What do you see? The first time you click '3', the calculator replaces '0' with '3'. Then for each subsequent click on '3', the calculator simply appends '3' to the current display text field and update it with the resulting string. You should see "333" at this point.
Next, click '+': "333" is still being display. But now click '3'. What happens? '3' is no longer appended to the existing display string, isn't it? You are sending the same message to the calculator by clicking the same '3', but the calculator responds differently this time, doesn't it? It has dynamically changed its behavior after you clicked on '+'! Again what we see here is another example of "state change". Clicking the '+' causes the calculator to transition to another state.
The behaviors of my calculator can be modeled as what is called a "finite state machine." What is a state? How many states are there? How do we go about describing the behavior of the calculator as it changes from state to state?
When you click on a button of the calculator, you are in effect making a request to the calculator to perform certain task. At any point in time, the internals of the calculator are in some specific conditions with specific values that would cause the calculator to respond in a very specific manner to such a request. The condition in which the calculator is in at any point in time is called the state of the calculator at that point in time. A state of a system is defined by the behaviors of the system. The user can interact with the calculator in only five ways:
To specify the behavior of the calculator, we must specify the calculator's response to each of the above five clicking events.
When you first turn on the calculator, imagine that it is in some initial condition called a start state. Suppose, from the start state, you...
Beginning with one state, the start state, by analyzing and specifying the behavior of the calculator in response to the five distinct click events, we have inferred the existence of four distinct other states: accumulate state, compute state, point state and error state. We can repeat the same analysis on each of these states for each of the click events. We will not discussed them in details here. Instead, we summarize the state behaviors and the state transition in the form of a diagram shown below.
Traditional procedural programming implements the behavior of finite state machines by using numbers, loops and conditional constructs such as if and switch statements. In OOP, each state is an object with behaviors. A finite state machine is an object that has states. The machine holds a reference to an abstract state and delegates all state-dependent behaviors to its current state. This is the gist of what is called the state design pattern. We will apply the state pattern to model the cheap calculator. Here is the UML diagram of the complete system that we will be building:
The documentation for the above classes can viewed here.
In this week's lab, you will be asked to complete the above GUI program. Here some code to help you get started.
package infixModel;
/**
* Represents the abstract state of the calculator (the context)
*/
abstract class ACalcState {
/**
* An error state object for general use
* A null object, does nothing.
*/
final static ACalcState ErrorState = new ACalcState() { // state 3 is error state: null-object pattern, does nothing!
public void enterDigit(InfixCalc calc, char c) {
}
public void enterOp(InfixCalc calc, IBinOp op) {
}
public void enterEqual(InfixCalc calc) {
}
public void enterPoint(InfixCalc calc) {
}
};
/**
* Appends c to the string of digit collected so far.
* @param calc The calculator model (context)
* @param c The digit being entered
*/
public abstract void enterDigit(InfixCalc calc, char c);
/**
* Performs the pending operation, and set op as the next pending operation
* on whatever is computed so far to the operand that will be entered next.
* @param calc The calculator model (context)
* @param op The new pendin operation
*/
public abstract void enterOp(InfixCalc calc, IBinOp op);
/**
* Computes the pending operation.
* @param calc The calculator model (context)
*/
public abstract void enterEqual(InfixCalc calc);
/**
* Enters a decimal point.
* @param calc The calculator model (context)
*/
public abstract void enterPoint(InfixCalc calc);
}
/**
* State at the start up or after the calculator has been cleared.
* No digits or operations input yet.
*/
class StartState extends ACalcState {
public static final StartState Singleton = new StartState();
private StartState() {
}
/**
* Appends c to the string of digit collected so far
* if c is not "0" which is ignored.
* Go to accumulating state.
* @param calc The calculator model (context)
* @param c The digit being entered
*/
public void enterDigit(InfixCalc calc, char c) {
calc.setDisplay("" + c);
if ('0' != c) {
calc.setCurState(AccumState.Singleton);
}
}
/**
* Performs the pending operation, and set op as the next pending operation
* on whatever is computed so far to the operand that will be entered next.
* Go to computation state.
* Go to error if the number in the display does not parse properly into a floating point number.
* Same as accumulating state.
* @param calc The calculator model (context)
* @param op
*/
public void enterOp(InfixCalc calc, IBinOp op) {
try {
calc.setAcc(calc.getPendingOp().compute(calc.getAcc(), Double.parseDouble(calc.getDisplay())));
calc.setDisplay("" + calc.getAcc());
calc.setPendingOp(op);
calc.setCurState(CompState.Singleton);
}
catch (Exception e) {
calc.setDisplay(e.getMessage());
calc.setCurState(ErrorState);
};
}
/**
* Performs the pending operation, which may be a no-op, displays the result
* and updates the pending op to no-op.
* @param calc The calculator model (context)
*/
public void enterEqual(InfixCalc calc) {
try {
calc.setAcc(calc.getPendingOp().compute(calc.getAcc(), Double.parseDouble(calc.getDisplay())));
calc.setDisplay("" + calc.getAcc());
calc.setNoOp();
}
catch (Exception e) {
calc.setDisplay(e.getMessage());
calc.setCurState(ErrorState);
};
}
/**
* Enters a "0." into the display string.
* Go to point state.
* @param calc The calculator model (context)
*/
public void enterPoint(InfixCalc calc) {
calc.setDisplay("0.");
calc.setCurState(PointState.Singleton);
}
}
/**
* State where a decimal point has been entered.
* Delegates to an accumulating state object for
* operations that are identical.
*/
class PointState extends ACalcState {
/**
* Reference to accumulating state for delegation purposes.
*/
static final AccumState AccState = AccumState.Singleton;
static final PointState Singleton = new PointState();
private PointState() {
}
/**
* Keeps on accumulating c. Same as accumlating state.
* @param calc The calculator model (context)
* @param c The digit being entered
*/
public void enterDigit(InfixCalc calc, char c) {
AccState.enterDigit(calc, c);
}
/**
* Performs the pending operation, and set op as the next pending operation
* on whatever is computed so far to the operand that will be entered next.
* Go to error if the number in the display does not parse properly into a floating point number.
* Same as accumulating state.
* @param calc The calculator model (context)
* @param op
*/
public void enterOp(InfixCalc calc, IBinOp op) {
AccState.enterOp(calc, op);
}
/**
* Computes the pending operation.
* Same as accumulating state.
* @param calc The calculator model (context)
*/
public void enterEqual(InfixCalc calc) {
AccState.enterEqual(calc);
}
/**
* Does nothing because a decimal point has already been entered.
* @param calc The calculator model (context)
*/
public void enterPoint(InfixCalc calc) {
// do nothing
}
}