How to represent a simple finite state machine in Ocaml?

Question

I have written some state machine in C++ and Java but never in a functional language like Ocaml

Problem is I don't know if I can just adapt code from the object languages versions, since in Ocaml records and variants are more powerful than class;

So, I need an event-driven finite state machine (hierarchical like in UML), easily configurable

Could someone experienced in the field post a simple sample of that ? Just to avoid the most common traps

thanks :)

EDIT 16/03 : Is it possible to do it without mutable state ? And I'd like to encapsulate it properly under the name "FSM", should I choose a module or a class ?

Answer 1

It depends on how you have to operate the FSM, e.g., if you need to be able to store its state and continue later, or if you just want to execute it immediately. In the latter case, it's trivial to do it as a bunch of tail-recursive functions.

For example, assume the regexp C((A|B)*CD)* -- the following mutually recursive functions are a direct implementation of the respective FSM that recognises a list matching this regexp (if I didn't make any mistake :) ):

type alphabet = A | B | C | D

let rec s1 = function
  | C :: rest -> s2 rest
  | _ -> false

and s2 = function
  | [] -> true
  | (A | B) :: rest -> s2 rest
  | C :: rest -> s3 rest
  | _ -> false

and s3 = function
  | D :: rest -> s2 rest
  | _ -> false

Every function corresponds to exactly one state of the automaton and implements its transition function. Applying s1 : alphabet list -> bool will run the FSM on the argument.

PS: Note how this is an application demonstrating the benefit and elegance of tail call optimization...

Answer 2

Usually, you create a record corresponding to a state of the automata, and you have another type for the event triggering the transition to another state. In the state record, you have a map to find, for each event, the new state.

Let's suppose your transitions are triggered by strings:

type event = string

module EventMap = Map.Make(struct
    type t = event
    let compare = compare
  end)

type state = {
  state_info : ...; (* the content of that state, id, comment, etc. *)
  mutable state_transitions : state EventMap.t;
}

let next_state current_state event =
  try
    EventMap.find event current_state.state_transitions
  with Not_found -> current_state

Here, I supposed that unknown events stay on the same state, but you could have an error state in the record...