Finite State Machine diagram courtesy of brilliant.org
Introduction
A Finite State Machine (FSM) is a theoretical model of computation based on a discrete, finite number of states. The machine can only be at one state at one ‘time’. Input data is provided to the machine along with a transition function for each state. The transition function may be the same for all states.
An initial state is specified for the machine. The machine then transitions into the next state, and continues to do so until stopped or all inputs have been exhausted. In some cases, reaching the acceptance state is considered a stopping criteria.
It is allowable for a FSM to remain in its current state after executing a transition.
The most common representation of an FSM is the Discrete Finite Automata (DFA). DFA’s obey the following conditions.
Transitions are uniquely determined by the source state and inputInput is required for each state transition
A Non-discrete Finite Automata (NFA) follows the same model of computation, but may violate one or both of the above conditions. A NFA can be translated into a DFA [1], so both models are considered to be under the umbrella of a FSM for this article.
So What???
While FSM’s are important in the foundation of computer science, it is hard to imagine what, if any, relevance they might have for Angular developers.
FSM’s can be used to model sequential logic or processes that might otherwise be cumbersome to represent in traditional functional languages. Everything from complex string or binary stream processing to client-specific routing can often be more compactly and cleanly represented by a FSM.
Behavior of an FSM can also be readily modified by altering one or more transition functions. Since JavaScript provides the ability to specify the body of a function as a string, this provides a mechanism to completely define an FSM in data. Complex change requests that may be frustrating for developers to ‘hack in’ and test can be completely isolated from the front-end code base.
FSM’s also allow real-time business logic to be executed on the front end without requiring the front-end development team to expend time creating, testing, and refining such processes. One example of my past use of FSM’s for such logic is in A|B testing. Logic that determines how the application behaves for a particular user and use case(s) is encapsulated into an FSM. The complete machine definition is provided by the back end. The front-end dev is only responsible for creating and exercising the machine to determine how to route or otherwise react to a user’s actions.
Types of FSM
FSM’s are often classified as being Mealy [2] or Moore [3] machines.
The output of a Mealy machine is determined by both the current state and its inputs. The output of a Moore machine is determined only by its current state.
Most machines I’ve constructed and used in practical applications tend to be Mealy-style.
TypeScript Library
Angular devs should be spared from the nuances of constructing FSM’s and their execution. FSM’s can be enormously helpful for encapsulating and quickly changing business logic. The latter can be easily facilitated by switching machines or changing transition functions inside an existing machine. Even so, Angular developers should have access to an FSM library for creating and executing a specific machine.
I’m glad to say that has already been done for you as part of the new AMYR Library,
The TypeScript FSM is in the libs/amyr-ts-lib/src/lib/libs/ai/ folder.
The FiniteStateMachine class is generic and requires a machine to be constructed with the type of input that is provided to the transition functions. It is acceptable to define a machine with unknown type, i.e.,
const fsm: FiniteStateMachine<unknown> = new FiniteStateMachine<unknown>();
The FiniteStateMachine class is governed by a number of models that are documented in the following gist.
https://medium.com/media/61644649b6dd015eda9264022bb5c800/href
Both the FSM and the data-driven Decision Tree (to be a subject of a future article) share a model to describe the result of an action,
interface DecisionTreeAction
{
// true if operation was successful
success: boolean; // reference to node in which an error was detected
node?: object; // action to take
action: string;
}
Any input to the machine or output from the machine is specified with the same generic type. This allows a much greater degree of type-checking at compile time and helps avoid mix-ups that lead to serious headaches during debugging. Trust this admonition from someone who first implemented a FSM in Basic 🙂
The FiniteStateMachine class exposes the following methods,
static create<T>(data: StateMachineDefinition, name?: string): FiniteStateMachine<T> | nullget numStates(): numberget numTransitions(): numberget currentState(): stringget states(): IterableIterator<string>get initialState(): stringget initialData(): object | nullget isAcceptance(): booleanfromJson(data: StateMachineDefinition): DecisionTreeActionaddState(stateName: string, acceptance: boolean=false): voidaddTransition(from: string, to: transFunction<T>): booleanaddSubscriber(observer: Observer <StateTransition<T>>): voidnext(input: T, initialState?: string): FSMStateOutput<T> | nullclear(): void
The machine is reactive in the sense that subscribers can be informed whenever the machine transitions into a new state.
This API is illustrated through a number of examples.
Binary Sequence With Even Number of Zeros
This is a common FSM example with two states, which are ‘S1’ and ‘S2’ for purposes of this article. State inputs are the numerical digits of the sequence, which are members of the alphabet, [0, 1]. The state diagram can be found almost anywhere on the internet, but most people new to FSM’s find a state transition table or textual description easier to understand.
State S1: digit = 1->transition to ‘S1’, digit = 0 -> transition to ‘S2’
State S2: digit = -> transition to ‘S2, digit = 0 -> transition to ‘S1’
State S1 is the acceptance state. If all digits are fed into the machine and it is in State S1, then we accept that the binary sequence has an even number of zeros.
This simple machine can be implemented and tested as follows:
// pre-defined transition functionsconst f1: transFunction<number> = (data: number) => {
return data == 1 ? {to: ‘S1’} : (data == 0 ? {to: ‘S2’} : {to: ‘S1’})
};
const f2: transFunction<number> = (data: number) => {
return data == 1 ? {to: ‘S2’} : (data == 0 ? {to: ‘S1’} : {to: ‘S2’})
};const fsm: FiniteStateMachine<number> = new FiniteStateMachine<number>();
fsm.addState(‘S1’, true);
fsm.addState(‘S2’);
fsm.addTransition(‘S1’, f1)
fsm.addTransition(‘S2’, f2);
let binary: Array<number> = [1, 0];
let n: number = binary.length;
let i: number;
let state: FSMStateOutput<number> | null = fsm.next(binary[0], ‘S1’);
for (i = 1; i < n; ++i) {
state = fsm.next(binary[i]);
}
// state.to is ‘S2’
// fsm.isAcceptance is false;
Since the machine is not in its acceptance state at the end of the input sequence, the binary sequence does not contain an even number of zeros.
Making Change
I chose this example as it is another case where I’ve used an FSM in an actual application. It also has personal historical appeal as I am largely a self-taught programmer. The first formal class I took in any language was FORTRAN and our first lab assignment was to write a program that computed change.
For brevity, the amount to be changed is less than one dollar and change is to be made in quarters, dimes, nickels, and pennies. This was the requirement for the Flash application I developed to help children with mental math exercises.
The algorithm is fairly simple. Start with the largest change denomination, or quarters in this example. Can a single unit of this denomination can be applied to reduce the remaining balance? If so, add one unit of that denomination to the change tally and reduce the outstanding balance by the value of that unit. If the unit of change can not be applied to the balance, drop down to the next-smallest unit, or dimes in this example. Continue until the balance is zero.
The output of this process is the number of quarters, dimes, nickels, and pennies to be given to a ‘customer’. The concept of moving to successively smaller monetary denominations can be modeled as a state transition.
A simple state machine consists of the alphabet, [‘q’, ‘d’, ’n’, ‘p’] and the states correspond directly to this alphabet.
‘q’ = number of quarters
‘d’ = number of dimes
’n’ = number of nickels
‘p’ = number of pennies
The value of each change denomination is normalized to pennies,
const COIN_VALUES: Record<string, number> = {
p: 1,
n: 5,
d: 10,
q: 25
};
A simple interface is used to model the change process
interface Change
{
p: number;
n: number;
d: number;
q: number;
amount: number;
change: number;
}
The amount property is the total amount to be changed and it remains constant through the change process. The change property is the running balance.
Example: Change due is 68 cents. amount = 68, change = 68.
Process: Apply one quarter. amount = 68, change = 43. Apply one quarter. amount = 68, change = 18. Apply one quarter. Change would be negative, so a quarter does not apply. Transition to dimes. Apply one dime. amount = 68, change = 8. Apply one dime. Change would be negative, so a dime does not apply. Transition to nickels. Apply one nickel. amount = 68, change = 3. Transition to pennies and repeat until balance is zero, at which point the change process is complete. This can be modeled as the acceptance state of a FSM.
Result: 2 quarters, 1 dime, 1 nickel, 3 pennies.
The same transition function can be used for each state. This function is written out in more detail to make the process easier to follow. It could be further compacted, and that is left as an exercise.
const makeChange: transFunction<Change> = (pmt: Change, state?: string): FSMStateOutput<Change> => {
if (pmt.change === 0) {
return {
to: ‘c’,
data: pmt
}
};
// sum current amounts
const coinage: string = state as string;
// can the current amount be applied to reduce the outstanding change due?
const value: number = COIN_VALUES[coinage];
const apply: boolean = value <= pmt.change;
let toState = ”;
if (apply)
{
(pmt as unknown as Record<string, number>)[coinage]++;
pmt.change -= value;
toState = pmt.change === 0 ? ‘c’: coinage;
}
else
{
if (coinage === QUARTERS) toState = DIMES;
else if (coinage === DIMES) toState = NICKELS;
else if (coinage === NICKELS) toState = PENNIES;
else toState = PENNIES;
}
return {
to: toState,
data: pmt
}
};
A change-making FSM can be created with a simple factory,
const PENNIES = ‘p’;
const NICKELS = ‘n’;
const QUARTERS = ‘q’;
const DIMES = ‘d’;
const PAYMENT_COMPLETE = ‘c’;.
.
.const changeMachineFactory = (): FiniteStateMachine<Change> =>
{
const fsm: FiniteStateMachine<Change> = new FiniteStateMachine<Change>();
// add states
fsm.addState(PENNIES);
fsm.addState(NICKELS);
fsm.addState(QUARTERS);
fsm.addState(DIMES);
fsm.addState(PAYMENT_COMPLETE, true); // ‘complete’ is the acceptance state
fsm.addTransition(PENNIES, makeChange);
fsm.addTransition(NICKELS, makeChange);
fsm.addTransition(DIMES, makeChange);
fsm.addTransition(QUARTERS, makeChange);
return fsm;
};
One more small function can be used to process the change with the algorithm described above.
const processChange = (fsm: FiniteStateMachine<Change>, change: Change): void => {
let state: FSMStateOutput<Change> | null = fsm.next(change, QUARTERS);
while (state?.to != COMPLETE) {
state = fsm.next(change, state?.to);
}
};
Let’s handle a small wrinkle in the process. The back-end service that provides the amount to be changed was written before user stories were complete. This service provides the amount to be changed in a fraction of a dollar, i.e. 15 cents is represented as 0.15. Of course, the back-end team refuses to change the service.
A simple adapter function can be used to handle this situation.
const createChange = (value: number): Change =>
{
const coinValue = value * 100;
const coinage: number = Math.max(0, Math.min(coinValue, 99));
return {
p: 0,
n: 0,
d: 0,
q: 0,
amount: coinage,
change: coinage
}
}
Change can now be processed with the following code. This examples uses 68 cents as in the above example.
const fsm: FiniteStateMachine<Change> = changeMachineFactory();
const change: Change = createChange(0.68);
processChange(fsm, change);
The number of quarters, dimes, nickels, and pennies can be easily read from the change variable. This is all the code I would ever expect a front-end developer to have to write. The FSM, transition function(s), and utility functions should all be provided by a specialist — which is the reason I’ve had a job for so many years 🙂
Stakeholder change requests can be isolated to the FSM and independently tested. For example, it may be later specified that the change process should be altered to maintain and consider the amount of available coin denominations. For example, the ‘drawer’ may be extremely low on dimes, so nickels are favored.
Data Description of a FSM
The ultimate flexibility of a FSM is realized when the entire machine (including transition functions) is represented entirely in data. The back end is responsible for maintaining the full definition of all machines and serves the data description for a particular machine to the front end. An example for the change machine is shown below. The function body script is shown in a separate variable to make the overall structure easier to deconstruct.
const PMT_FUNCTION_SCRIPT = `
if (data.change === 0) {
return {
to: ‘c’,
data: data
}
}
const COIN_VALUES = {p: 1, n: 5, d: 10, q: 25 };
const value = COIN_VALUES[state];
const apply = value <= data.change;
let toState = ”;
if (apply)
{
data[state]++;
data.change -= value;
toState = data.change === 0 ? ‘c’: state;
}
else
{
if (state === ‘q’) toState = ‘d’;
else if (state === ‘d’) toState = ‘n’;
else if (state === ‘n’) toState = ‘p’;
else toState = ‘p’;
}
return {
to: toState,
data: data
}`const TheChangeMachine: StateMachineDefinition = {
name: ‘ChangeMachine’,
alphabet: [
‘p’,
‘n’,
‘d’,
‘q’,
],
states: [
{
name: ‘p’, // pennies
isAcceptance: false,
transition: PMT_FUNCTION_SCRIPT
},
{
name: ‘n’, // nickels
isAcceptance: false,
transition: PMT_FUNCTION_SCRIPT
},
{
name: ‘d’, // dimes
isAcceptance: false,
transition: PMT_FUNCTION_SCRIPT
},
{
name: ‘q’, // quarters
isAcceptance: false,
transition: PMT_FUNCTION_SCRIPT
},
{
name: COMPLETE,
isAcceptance: true,
transition: NONE
},
],
initialData: {
p: 0,
n: 0,
d: 0,
q: 0,
amt: 68,
change: 68
}
};
This data description can be used as shown below.
const fsm: FiniteStateMachine<Change> = FiniteStateMachine.create(TheChangeMachine) as FiniteStateMachine<Change>;
const change: Change = fsm.initialData as Change;
processChange(fsm, change);
While making change is a fairly trivial FSM application, I’ve used FSM’s successfully for very complex routing and other real-time processes that would otherwise involve nasty, multi-level if-then-else statements. The latter are cumbersome to write and difficult to maintain. This difficulty is compounded by multiple change-requests during a product’s life cycle.
Making changes to a FSM proved to be much simpler in practice. Route selection or other process could be rigidly and independently tested in advance of applying the new machine to the application.
NOTE: There are two issues with providing transition functions via a string. When a new Function is constructed, the self-referential pointer (i.e. this) is assigned to the global context. When JavaScript creates the execution context for this function, the scope chain that may have been available for resolving outside variable references is likely to no longer be valid. It is best to use this process with pure transition functions.
It is also possible for a nefarious developer to inject harmful script into the string, so use this process with care.
FSM The Bad Parts
While FSM’s have many advantages, it is only natural to ask if there are drawbacks.
FSM’s can be difficult to create for those exposed to the concept for the first time. Like so many other aspects of software development, FSM’s take some element of time and experience in order to create and use effectively. Once a developer becomes familiar with the creation and usage of FSM’s, they can be a valuable tool to handle what might otherwise be cumbersome and time-consuming feature requests.
This leads to the other drawback of FSM’s, namely that when holding a hammer in hand, it’s tempting to look at everything else and see a nail 🙂 It’s quite easy for a FSM to become a solution looking for a problem.
Evolving Finite State Machines
Creating a state-machine diagram is often the most time-consuming part of using a FSM in an application. It is possible to use evolutionary techniques to create state machine definitions. While this can be beneficial, it can also be complex and time-consuming in and of itself. If there is any interest, I’ll write another article on this process. In the most extreme case, it is also possible to take substantial liberty with the definition of a state. A state may itself be an independent state machine.
Applying the techniques of evolutionary programming to FSM’s defined in such a manner leads (very roughly) to the process of programs that write other programs.
Yes, The Matrix has you 🙂
Summary
Finite State Machines can be a powerful new addition to your problem-solving arsenal. There is a very wide variety of material available online for those wishing to delve further into the topic. Fork the AMYR library and look through the specs for the FiniteStateMachine class. You will be exposed to a breadth of examples on how to create and use FSM’s.
Then, you will be ready for Fuzzy State Machines.
The Matrix will never let you go …
References
[1] Non-deterministic Finite Automata, Wikipedia, https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton
[2] Mealy, George H. (1955). A Method for Synthesizing Sequential Circuits. Bell System Technical Journal. pp. 1045–1079.
[3] Moore, Edward F “Gedanken-experiments on Sequential Machines”. Automata Studies, Annals of Mathematical Studies. Princeton University Press (34): 129–153 (1956).
Typescript Reactive, Data-Driven Finite State Machine was originally published in ngconf on Medium, where people are continuing the conversation by highlighting and responding to this story.