Reactive, Data-Driven Finite State Machine

TL;DR – This project is open source and the following description is rather long. It is also largely a repeat of information found in the Readme file on GitHub. So, if you are anxious for code, then fast-forward and check out the repo here!

This a follow-on article to the developments in my Angular Dev Toolkit regarding data-driven application logic. When discussing the expression-based decision tree, I mentioned that it would be possible to have a leaf node contain the name and initial state of a finite-state machine. For that approach, the FSM must be data-driven and to fit nicely into the general Angular idiom, I also wanted a machine that was reactive.

The Decision Tree and Sequencing Engine are general-purpose derivatives of work previously implemented for NDA clients (I had to rewrite everything pretty much from memory). As such, they will remain in the client-only Angular Dev Toolkit. Subsequent private and online discussions led me to believe that the Finite State Machine was of suitable general interest to open-source the baseline version.

If you are interested in some background material, then here is one of my favorite descriptions of a FSM, and is close to how I learned the topic ‘back in the day.’

The machine implementation in this repo is Mealy-style, although a state may be passed as data, so Moore-style machines can be used within this framework.

A FSM consists of a number of named states, and transitions from those states. One or more states may be defined as an acceptance state, meaning that after exercising the machine with a finite number of inputs, the machine may indicate acceptance of a certain criteria. This could be a valid string or that the number of zeros in a binary sequence is even. It is possible (and I’ve done this in C++) to define a rejection state with the convention that the machine may never transition out of this state. This is a way to catch and flag incorrect or other inputs.

The set of inputs to a FSM is called an alphabet.

The FiniteStateMachine class in this distribution has two possibly differentiating features from other implementations (particularly in Java, JS, and TS). One is that listening for specific state transitions is not performed by callback functions applied to those states. Instead, the machine is reactive. One or more (RxJs) Observers may subscribe to the machine and receive updates on all transitions that includes from and to states as well as relevant data.

API

The FiniteStateMachine class exposes the following models or interfaces,

export interface IDecisionTreeAction
{
  success: boolean;                 // true if operation was successful

  node?: Object;                    // reference to the data Object in which an error was detected

  action: string;                   // action to take
}


/**
 * A state transition must have a 'from' and 'to' (named) state and may contain optional Object data
 */
export interface IStateTransition
{
  from: string;

  to: string;

  data?: Object;
}


/**
 * Output from a state transition is the 'to' state and optional data obtained from the transition function
 */
export interface IStateOutput
{
  to: string;

  data?: any;
}


/**
 * The transition function is Mealy-style, that is a transition to a new state is based on prior state and
 * input data.  Since state is optional in this interface, pass the state name as data and a Moore-style
 * machine can be implemented.
 */
export interface transFunction
{ 
  (data: any, state?: string): IStateOutput;
}

(

The public API of the FiniteStateMachine class is as follows.

public static create(data: Object, name?: string): FiniteStateMachine | null
public get numStates(): number
public get numTransitions(): number
public get currentState(): string
public get states(): IterableIterator
public get initialState(): string
public get initialData(): Object | null
public get isAcceptance(): boolean
public get alphabet(): Array | null
public fromJson(data: Object): IDecisionTreeAction
public addState(stateName: string, acceptance: boolean=false): void
public addTransition(from: string, to: transFunction): boolean
public addSubscriber(observer: Observer ): void
public next(input: any, initialState?: string): IStateOutput | null
public clear(): void

Usage

The FSM in this distribution may be used by directly assigning states and transition functions. The machine may also be described with Object data. These cases are best illustrated by example.

First, consider one of the machines discussed in the above introductions to FSM’s. This machine is designed to test sequences consisting of the letters a, b, c, and d, which is the machine’s alphabet.

The states are S1, S2, S3, and S4, the latter of which is the acceptance state. The machine’s initial state is S1 and letters are input one at a time. The machine is tested for being in the acceptance state after the final transition (refer to the above link for the state diagram).

This machine can be implemented with the following code (which is provided in the specs located in the test folder) which presumes a string input Array, str, i.e.

const str: Array = [‘a’, ‘a’, ‘a’, ‘a’, ‘c’, ‘d’];

Note that the transition functions are defined statically in code, which allows them to use stronger typing than is described in the transFunction interface.

For compactness, testing the return value from adding a transition is not included in the example.

const f12: transFunction = (data: string) => {
  return data == 'a' ? {to: 'S2'} : {to: 'S1'}
};

const f22: transFunction = (data: string) => {
  return data == 'a' ? {to: 'S2'} : (data == 'b' ? {to: 'S1'} : (data == 'c' ? {to: 'S4'} : {to: 'S2'}))
};

const f32: transFunction = (data: string) => {
  return data == 'a' ? {to: 'S1'} : (data == 'b' ? {to: 'S4'} : {to: 'S3'})
};

const f42: transFunction = (data: string) => {
  return data == 'd' ? {to: 'S3'} : {to: 'S4'}
};
.
.
.
const __machine: FiniteStateMachine = new FiniteStateMachine();

__machine.addState('S1');
__machine.addState('S2');
__machine.addState('S3');
__machine.addState('S4', true);

__machine.addTransition('S1', f12);
__machine.addTransition('S2', f22);
__machine.addTransition('S3', f32);
__machine.addTransition('S4', f42);

const n: number = str.length;
let i: number;

let state: IStateOutput = __machine.next(str[0], 'S1');  // set the initial state and first input
for (i = 1; i < n; ++i) {
  state = __machine.next(str[i]);
}

Based on the machine’s construction, we would expect __machine.isAcceptance to be false. This is also the answer to the quiz question posed on the site from which the example was taken 

Many algorithms can be expressed as a FSM and Regex is equivalent to FSM (Kleene’s Theorem), for example. Whether or not one should implement an algorithm using a FSM is another topic. One example that often does not seem to fit a FSM architecture is the ‘change machine’ problem (this was a lab exercise in college).

Consider a machine that accepts coins (penny, nickel, dime, quarter) for an amount less than a dollar. After each coin is deposited, the machine updates the remaining balance, indicates if sufficient payment has been made, and computes any necessary change.

Alphabet and machine states may be considered equivalent in this machine, so we define states p, n, d, q, and c for the coin denominations and a ‘complete’ state. There is no transition out of the complete state, which is also the acceptance state for this machine.

Code to implement this machine is provided in the specs.

The most potentially useful feature of this FSM is the ability to describe a machine in data. This allows multiple machines to be defined in metadata and then dynamically applied based on real-time conditions in an application.

The string-test machine shown above can be described in the following data Object,

const machine1: Object = {
  name: 'StringTest',
  initialState: "S1",
  alphabet: [
    'a',
    'b',
    'c',
    'd'
  ],
  states: [
    {
      name: 'S1',
      isAcceptance: false,
      transition: "return data == 'a' ? {to: 'S2'} : {to: 'S1'}"
    },
    {
      name: 'S2',
      isAcceptance: false,
      transition: "return data == 'a' ? {to: 'S2'} : (data == 'b' ? {to: 'S1'} : (data == 'c' ? {to: 'S4'} : {to: 'S2'}))"
    },
    {
      name: 'S3',
      isAcceptance: false,
      transition: "return data == 'a' ? {to: 'S1'} : (data == 'b' ? {to: 'S4'} : {to: 'S3'})"
    },
    {
      name: 'S4',
      isAcceptance: true,
      transition: "return data == 'd' ? {to: 'S3'} : {to: 'S4'}"
    },
  ]

};

Transition functions defined in data will be called with arguments that strictly match the transFunction interface. They must adhere to the following conventions.

• Only the function body need be defined in a string.
• The variable names data and state are arguments. Use them as such.
• Transition functions must be pure.
• The self-referential pointer (this) is bound to the global context due to Function constructor invocation. Do not use this inside the function body.
• Do not reference any variables that are not defined in the function body as we can not be ‘loose’ regarding execution context of these functions.

In a typical application, the above Object description is input external to the application. Implementation of the machine reduces to

let result: IDecisionTreeAction = __machine.fromJson(machine1);

let str: Array = ['a', 'b', 'a', 'c', 'd', 'a', 'a', 'c'];
let n: number  = str.length;
let i: number;
let state: IStateOutput;

for (i = 0; i < n; ++i) {
  state = __machine.next(str[i]);
}

We would expect __machine.isAcceptance to be true.

Additional examples are provided in the specs in the GitHub repo. I hope you find something useful in this project!