Finitomata :: The Proper FSM for Elixir

I’m a big fan of Finite Automata. Always have been. Whenever we deal with a long-lived objects, they eventually have states and FSM does an enormously great job by attesting consistency, eliminating human errors and leaving the implementation with a business logic only. In a mediocre project, fifty if-then-else conditionals might perform as well as one FSM, but unless you are paid for the number of LoCs, FSM is drastically easier to carry on.

Cherrytree

Of course, I am not alone, and there are many implementations of FSM in different languages. During my Ruby journey, I loved workflow gem for its simplicity, clarity, and robustness. Nowadays I mostly do Elixir and I surely searched through available libraries to minimize FSM boilerplate.

The package that comes up first when doing an internet search would be fsm by Saša Jurić. But the author explicitly says on the very top of README

[…] I don’t advise using [this library]. Pure functional FSMs are still my preferred approach (as opposed to gen_statem), but you don’t need this library for that. Regular data structures, such as maps or structs, with pattern matching in multiclauses will serve you just fine.

That said, the proposed approach would be to have a GenServer with multiple clauses of, say, transition/2 function and messages containing events. Somewhat like

@impl GenServer
def handle_call(:event1, %{} = state), do: …
def handle_call(:event2, %{} = state), do: …
def handle_call(:event3, %{} = state), do: …

I admire Saša’s contribution in Elixir ecosystem, and he is definitely one of the smartest persons I ever met, so I used this approach for years. Until I found myself in a position of copy-pasting a boilerplate for that from one project to another. I surely felt it might be done better, but the actual implementation eluded me.

Last week I had been presenting the FSM concept to non-tech auditory during one of our internal tech talks, and it finally clicked. That’s how finitomata library was born.

The most important thing I wanted to automate would be the FSM pure description itself. I wanted something, that is fault-tolerant, not error-prone, and easy to grasp. I wanted the result to be drawable out of the box. That’s why I recalled PlantUML format. Instead of scrolling the editor window back and forth and memorizing all the transitions handled, the definition of the entire FSM would be in the very single place! That sounded as a great idea.

[*] --> s1 : to_s1
s1 --> s2 : to_s2
s1 --> s3 : to_s3
s2 --> [*] : ok
s3 --> [*] : ok

So I took NimbleParsec, the great parser combinators library by Dashbit and started with PlantUML parsing. I ensured the parsed FSM consistency as: one single state, no orphan states, at least one final state. Also I have plans to implement a mix task to generate a visual representation of FSM as a diagram (the respective issue is marked as Help Wanted FWIW :))

I already had the approximate architecture in my mind. I wanted FSM to leverage GenServer functionality under the hood, and several callbacks for the real consumer actions when the transaction gets performed. These callbacks were intended to allow the consumer to concentrate on business logic only, without a necessity to deal with processes, messages and supervision trees. It should have been absolutely imperative for the consumer yet fully OTP under the hood.

Draft implementation: the consumer initiates a transition by calling somewhat like transition(object, event), then the GenServer does its magic and the callback on_transition gets called. From inside this callback, the consumer implements the business logic and returns the result (the next state to move the FSM to.) Soon I figured out we need also on_failure and on_terminate callbacks to allow easy handling of errors and to perform a final cleanup respectively.

All the callbacks do have a default implementation, which would perfectly handle transitions having a single to state and not requiring any additional business logic attached.

Upon start, it moves to the next to initial state and sits there awaiting for the transition request. Then it would call an on_transition/4 callback and move to the next state, or remain in the current one, according to the response.

Upon reaching a final state, it would terminate itself, that’s where on_terminate/3 callback is called from. The process also keeps all the history of states it went through, and might have a payload in its state.

That’s how the whole implementation would look like

defmodule MyFSM do
  @fsm """
  [*] --> s1 : to_s1
  s1 --> s2 : to_s2
  s1 --> s3 : to_s3
  s2 --> [*] : ok
  s3 --> [*] : ok
  """

  use Finitomata, @fsm

  def on_transition(:s1, :to_s2, event_payload, state_payload),
    do: {:ok, :s2, state_payload}

  def on_transition(…), do: …

  def on_failure(…), do: …

  def on_terminate(…), do: …
end

The library includes a supervision tree with a DynamicSupervisor carrying all the FSM and the Registry instance to allow anything to be an FSM name with {:via, module, term}.

The snippet below demonstrates how one would use the FSM implementation above

# Starts an FSM supervised
#                    ⇓ IMPL  ⇓ NAME         ⇓ PAYLOAD
Finitomata.start_fsm MyFSM, "My first FSM", %{foo: :bar}

Finitomata.transition "My first FSM", {:to_s2, nil}
Finitomata.state "My first FSM"                    
#⇒ %Finitomata.State{current: :s2, history: [:s1], payload: %{foo: :bar}}

Finitomata.allowed? "My first FSM", :* # state
#⇒ true
Finitomata.responds? "My first FSM", :to_s2 # event
#⇒ false

Finitomata.transition "My first FSM", {:ok, nil} # to final state
#⇒ [info]  [◉ ⇄] [state: %Finitomata.State{current: :s2, history: [:s1], payload: %{foo: :bar}}]

Finitomata.alive? "My first FSM"
#⇒ false

That’s it for now, but the library is still in the kindergarten, it’s v0.1.0 so one might expect more sugar to come soon.

Happy finite automating!

Finitomata :: The Proper FSM for Elixir elixir 82

Finitomata :: The Proper FSM for Elixir

elixir 82