Finite State Machines in Clojure with Jobim

When you are designing a distributed system, as in any other software system, you soon start noticing the same patterns happening again and again. Any software tool whose goal is to make easy the development of distributed systems should be capable of offering mechanisms of abstraction so this patterns can be factored in reusable components that can be reused.

One of these common patterns is the finite-state
machine. FSMs can be easily implemented using reactive actors, that store a
certain internal state that can be mutated as they receive incoming messages
following the rules described in a set of transition functions.

Erlang’s OTP platform offers an easy way of writing processes acting as FSMs
with the gen_fsm behaviour.

A similar mechanism that makes easy the creation of actors implementing FSMs has been implemented in the Jobim Clojure library and can be found in the jobim.behaviours.fsm namespace.

the FSM protocol

The abstraction of a FSM in jobim is defined in the jobim.behaviours.fsm.FSM protocol. To define a new FSM actor you will need to implement that protocol.

(defprotocol FSM
  (init [this initial-message]
    "Returns the initial state of the FSM")
  (next-transition [this current-state state-data  message]
    "Defines which transtion will be applied provided the
     current state and the incoming message")
  (handle-info [this current-state state-data message]
    "Handles messages distinct to events")
  (terminate [this state-name state-data]
    "Clean up code when the FSM is going to be terminated
     externally"))

The main function in the protocol are init and the next-transition functions.
The better way to understand this protocol is taking a look at a concrete example.

The lock automaton

The FSM we are going to describe is a simple lock mechanism. It will be initialized with a secret combination of numbers and the locked state.
Other agents can interact with the lock pushing numbers. The automaton will track the sequence of number and will switch its state to the open state if the correct sequence of numbers is introduced.

Each time a new number is pushed, the automaton will check if the sequence so far is a partial match of the whole combination. If that’s the case, it will maintain in its inner state the sequence so far. In other case, it will reset the sequence of pushed numbers.

The following sequence diagram gives an informal description of such a state machine.

The implementation of the automaton in Jobim requires the implementation of the FSM protocol.The jobim.behaviours.fsm/def-fsm can be used to ease the definition of the FSM.

(def-fsm Lock
  (init [this code] [:locked {:so-far [] :code code}])
  (next-transition [this state-name state-data message]
                   (let [[topic _] message]
                     (condp = [state-name topic]
                       [:locked :button] handle-button
                       [:open   :lock]  handle-lock
                       action-ignore)))
  (handle-info [this current-state current-data message]
               (do
                 (cond-match
                  [[?from :state] message] (send! from current-state))
                 (action-next-state current-state current-data)))
  (termiante [this current_state] :ignore))

The init function is invoked whenever the actor starts execution. It receives an initial message and must returns the initial state name and the initial state data for the FSM.

In the case of the lock FSM, it receives the initial code combination and returns the state :locked and the initial state {so-far [] :code code}.

The function next-transition describes the transition rules for the FSM.
It receives the current state name, the current state data and the received message and must return the function that will implement the next transition for the FSM. In this case we just look at the current state of the automaton and the topic of the incoming message:

 [:locked :button] handle-button
 [:open   :lock]  handle-lock
 action-ignore

If the current state is locked and a button is pushed, the handle-button function will be invoked. If the current state is open and a :lock message is received the handle-lock function will be invoked.
In any other case, the jobim.behaviours.fsm/action-ignore will be invoked that just returns the current state and state data as the next state and state data of the FSM effectively discarding the message.

The transitions of the FSM are encoded in the handle-button and handle-lock functions. State transition functions receive as arguments the current state name and data as well as the incoming message and must return the next state name and data. Sample implementations for the lock FSM can be seen in the following piece of code:

(defn- partial-match?
  ([combination so-far]
     (if (empty? so-far) true
         (if (= (first combination) (first so-far))
           (recur (rest combination) (rest so-far))
           false))))

(defn- handle-button
  ([current-state current-data message]
     (let [[_ code] message
           so-far (conj (:so-far current-data) code)]
       (if (= (:code current-data) so-far)
         (action-next-state :open (assoc current-data :so-far so-far))
         (if (partial-match? (:code current-data) so-far)
           (action-next-state :locked (assoc current-data :so-far so-far))
           (action-next-state :locked (assoc current-data :so-far [])))))))

(defn- handle-lock
  ([current-state current-data message]
     (action-next-state :locked (assoc current-data :so-far []))))

Utility function jobim.behaviours.fsm/action-next-state can be used to build the vector with name and data for the next state.

Sometimes the actor implementing the FSM must deal with messages not belonging to any transition. For instance, in the lock FSM it would be nice to be able to send a message to the FSM and retrieve the current state of the automaton, but
this message is not a regular event that can trigger a stat change in the automaton. The handle-info function can be implemented for the FSM actor to handle any kind of messages as any other actor.

Once the FSM protocol is implemented a new actor for the definition can be started using the jobim.behaviours.fsm/start and jobim.behaviours.fsm/start-evented functions. The first one will start a dedicated thread actor and the second one an evented actor.

The start function can receive a new object with the type of the defined FSM protocol or a string with the qualified package of the protocol implementation. This latter variant is useful to start the FSM actor in a remote node.

The start function can also receive a string as the first argument and will register the FSM actor globally with that name, so it can be retrieved from any node.

To send an event to the FSM actor, the jobim.behaviours.fsm/send-evented! function can be used instead of the regular jobim/send! function. This latter function can be used to send messages that will be handle by the handle-info function of the FSM protocol.

To make the use of the automaton easy for any client, some public interface for the FSM can be made up wrapping jobim.behaviours.fsm function calls:

;; public interface

(defn make-lock
  ([combination]
     (start (jobim.examples.fsm.Lock.) combination)))

(defn make-lock-evented
  ([combination]
     (start-evented (jobim.examples.fsm.Lock.) combination)))

(defn push-button
  ([fsm number]
     (send-event! fsm [:button number])))

(defn lock
  ([fsm]
     (send-event! fsm [:lock :ignore])))

(defn state
  ([fsm]
     (send! fsm [(self) :state])
     (receive)))

A client can use this interface to interact to with the FSM without even knowing the underlying implementation:

user> (use 'jobim)
nil
user> (bootstrap-node "node-config.clj")

 ** Jobim node started **


 - node-name: osx
 - id: 6bdcd512ab1a4df79d060692d008fe72
 - messaging-type :rabbitmq
 - messaging-args {:host "172.21.1.237"}
 - zookeeper-args ["172.21.1.237:2181" {:timeout 3000}]


:ok
user> (spawn-in-repl)
"6bdcd512ab1a4df79d060692d008fe72.1"
user> (use 'jobim.examples.fsm)
nil
user> (def *lock* (make-lock [1 2 3]))
#'user/*lock*
user> (state *lock*)
:locked
user> (push-button *lock* 1)
:ok
user> (push-button *lock* 2)
:ok
user> (push-button *lock* 3)
:ok
user> (state *lock*)
:open
user> (lock *lock*)
:ok
user> (state *lock*)
:locked
user> (push-button *lock* 2)
:ok
user> (push-button *lock* 4)
:ok
user> (state *lock*)
:locked

The implementation of the actor can be found in the jobim.examples.fsm.clj file of the Jobim source code. An alternative implementation of this very same actor can be found in the Erlang documentation.

Advertisement