Programmable state machines in rust

project homepage ipynb

Rust has several finite state machine packages such as rust-fsm. However, all of them are meant for state machines who's state network is known at compile time. I needed a programmable state machine, so wrote my own, with the help of the petgraph library.

Motivation

Programmable finite statemachines and or finite automata are best known for their use in the evaluation of regular expressions. Every regular expression can be converted into a parser wich is represented by a finite state machine *. They also have many many other uses. For example, the keymap of a configurable modal text editor such as vim is a programable FSM.

* Actually, this is no longer true. Modern PERL style regex is too powerful to represent all regular expressions as FSMs.

A "real" finite state machine does nothing but define:

  1. A set of valid sequences of inputs
  2. A mapping from each elemenent in each sequence to a state

Here is an FSM which describes the behavior of my toaster oven.

Given this state machine, and a sequence of inputs, we can determine the state of the toaster.

This basic information is quite usefull in and of itself, and we can actually make a toaster controll circuit based on a state machine like this. If the state is "heat on" we make sure that the heat is turned on, otherwise we make sure the heat is turned off.

A modified programmable state machine which associates Actions with each edge in the state graph, is rather more powerfull, however. Systems such as the aformentioned keymap of a modal editor are best expressed using such a modifidied state machine:

Obviously, the full keymap is far more messy than this, but you can already see how the state machine works.