Finite State Machines

FSMs are defined using a single declarative spec. Consider the audio player FSM in the example client:

(require '[reflet.fsm :as fsm])

(fsm/reg-fsm ::player-fsm
  (fn [self]
    {:ref  self
     :attr :player/state
     :fsm  {nil       {[::selected self] ::playing}
            ::playing {[::pause self] ::paused}
            ::paused  {[::play self]     ::playing
                       [::selected self] ::playing}}}))

Each FSM represents a computation that is run against a graph entity in the db. The entity is determined by the :ref attribute, here the self reference. The entity may already exist before the FSM is started, and the data can represent anything: component local state, domain data, it really doesn't matter. If the entity does not exist, then it will be created during the first transition.

The FSM state value is located at the attribute given by :attr. If no attribute is given, the default :reflet.fsm/state attribute is used. This means that more than one FSM instance can be started for any given :ref, by choosing different state attributes.

This is in fact how the audio player is implemented in the example client, where both ::selector-fsm and ::player-fsm use the same self reference but different attributes:

(fsm/reg-fsm ::selector-fsm
  (fn [self]
    {:ref  self                       ; <- Pass in the same ref
     :attr :player/selector-state     ; <- Different attribute
     :fsm  {nil    {[::toggle self] ::open}
            ::open {[::toggle self]   nil
                    [::selected self] nil}}}))

In the db, the component local state for the audo player might look like:

{:cmp/uuid              (second self)
 :player/state          ::playing     ; <- set by ::player-fsm
 :player/selector-state ::open        ; <- set by ::selector-fsm
 ... }

On start, the FSM may not always have a state value. This corresponds to the nil state, and you can always use nil as a state in your FSM definition, as seen above. But you can also set a default state to initialize the FSM:

{:ref  self
 :attr ::my-state-attr
 :or   ::start
 ... }

On creation, if and only if the FSM state value in the db is nil, this FSM will transition to the ::start state only once immediately after starting the FSM. This does not prevent the FSM from transitioning to the nil state some time later.

This touches on an important conceptual distinction: the DB is the source of truth, not the FSM definition. The FSM definition is just a computation. The current state of an FSM is always equal to the value of its state attribute in the db. But FSMs are ephemeral, and other external processes or computations can also affect state.

You can terminate an FSM by setting one or more :stop states:

{:ref  self
 :attr ::my-state-attr
 :or   ::start
 :stop #{::done ::error}
 ... }

Transitioning to a :stop state will halt the implementation, and leave the FSM in that state. The FSM implementation does not do any cleanup of app state. Cleanup depends on the :ref reference and the reactive context of its associated with-ref, as described in the References and Application Design document.

Lifecycles and Subscriptions

So far we have only seen how to define FSMs, not start and stop them.

There are two ways to manage FSM instances. The first is by subscribing to the FSM in your view code:

(fsm/reg-fsm ::player-fsm
  (fn [self]
    ...))

(f/with-ref {:cmp/uuid [player/self]
             :in       props}
  (let [state @(f/sub [::player-fsm self])]
     ...))

This is just a normal Re-frame subscription and all normal subscription semantics apply. However, in the background the FSM will have started and begin to advance during the next event phase. The considerations of this approach are:

The FSM lifecycle is managed for you
The FSM lifecycle is tied to the lifecycle of the subscription; when the subscription is disposed, the FSM is stopped
The state of the FSM is returned by the subscription
This approach cannot work in event handlers

The other way to manage FSMs is via the :reflet.fsm/start and :reflet.fsm/stop events:

(require '[reflet.fsm :as fsm])

(f/reg-event-fx ::component-config
  (fn [{db :db} [_ ref]]
    {:db       (db/assoc-inn db [ref ::component-flag] true)
     :dispatch [::fsm/start [::component-fsm ref]]}))

The considerations with this approach are:

You must manage the FSM lifecycle manually: if you forget to stop them, you will have FSM interceptors running needlessly on each event, and while the implementation is fast, this can add up over time
The FSM lifecycle is not tied to a subscription or component lifecycle
The state of the FSM must be manually queried like any other piece of app state
Only option in event handlers

In general the subscription approach is simpler, and you should always prefer it unless you know for a fact that your FSM lifecycle cannot be tied to a subscription or component.

States and Transitions

The behaviour of each FSM is defined by the :fsm spec. Each key in this spec is a state and each value is a map of allowed transitions for that state:

{:ref  self
 :attr :player/state
 :fsm  {nil       {[::selected self] ::playing}
        ::playing {[::pause self] ::paused}
        ::paused  {[::play self]     ::playing
                   [::selected self] ::playing}}}

A state with a nil transition map means that there are no transitions defined for that state:

{:fsm {::started {[::park self] ::parked
       ::parked  nil}}}

Here, if the ::parked state is reached then the FSM will continue to run but will never transition away, unless some external process intervenes.

All possible states for an FSM must be fully enumerated in the :fsm spec. An error will be raised if the FSM attempts a transition to or from a state that is not explicitly defined in the spec. Keep in mind that invalid states are nevertheless reachable if they are set by some process external to the FSM.

Two kinds of states are always implicitly enumerated to reduce boilerplate:

nil: every FSM has an implicit nil state defined with no transitions (effectively {nil nil}). nil is a common state for an FSM. In fact it is the starting state of any FSM whose entity in the db does not exist, or does not have a state value. You can of course always provide an explicit transition to override the default {nil nil}, as already seen:
```
{:ref self
 :fsm {nil {[::toggle self] ::open}  ; <- overrides {nil nil}
       ::open ...}}
```
:stop states: any state explicitly enumerated by the :stop option does not need to be enumerated in the :fsm spec.

So the following is valid:

{:ref  self
 :stop #{::done}
 :or   ::started
 :fsm  {::started {[::complete self]} ::done}}

Assume that there is no entity in the DB for the self reference when this FSM starts. Therefore, the initial state is nil, after which the :or dictates that it immediately transitions to the ::started state. Then, if it receives a [::complete self] event, it will transition to the ::done state and terminate. At no point is either the nil or the ::done state considered invalid even though they do not appear as a key in the :fsm spec.

Matching Input Events to Transitions

Each state in the :fsm spec is associated with zero or more allowable transitions. Each transition matches event prefixes to clauses:

{:ref  self
 :attr :player/state
 :fsm  {nil       {[::selected self] ::playing}
        ::playing {[::pause self] ::paused}
        ::paused  {[::play self]     ::playing
                   [::selected self] ::playing}}}
;;      event prefix ----^               ^---- transition clause

Only Re-frame events can trigger a transition. When an event is processed, Reflet matches the received event against the prefixes element by element. But a prefix can also match events with more elements. If more than one prefix would match a received event, then the longest successfully matching prefix is chosen (the matching is done using a longest matching prefix trie, so it is quite fast).

For example, given the received event:

[:voted self "literal" other-ref]

and the following set of prefixes:

{[:voted self]           :state-a
 [:voted self "literal"] :state-b}

Then the longest matching prefix would be:

[:voted self "literal"]

This match would then transition the FSM to :state-b. Matching events in this way allows us to use references like self to route input signals, and is one of two ways that different FSMs can be connected together (the other is the :pull conditional clause, described later).

There is also a special wildcard syntax, :*, that can match any event. Longest matching prefix semantics still apply:

{:*           :state-a
 [:vote self] :state-b}

Here, the event [:vote self "literal"] would be matched to :state-b, while the event [:tally self "literal"] would be matched to :state-a. In this way, the :* wildcard can be used to define a "default" transition if no other prefix matches.

Transitions, Entities and Conditional Clauses

So far we have only seen the simplified syntax for FSM transitions:

{::paused {[::play self]     ::playing
           [::selected self] ::playing}}

There is also an expanded form:

{::paused {[::play self]     ::playing
           [::selected self] {:to       ::playing
                              :when     ::clojure-spec
                              :pull     [other-process]
                              :dispatch [::other-event ...]}}}

Instead of a single keyword representing the next state, we have a clause map that allows more options:

:to: [required] The next state to transition to
:when: [optional] A conditional clause that by default takes the received event as its input. The conditional can be expressed in two forms:
- The id of a Clojure spec that must return (s/valid? spec-id input-event) true for the clause to match
- A function that must return a truthy value for the clause to match
If no :when is provided, then the clause always returns true.

:pull: [optional] A list of entity references. If this is provided, then the entity references are pulled from the db, and the resulting maps are passed to the :when conditional in place of the received event. In this way you can use the state of one FSM as input to another to determine its transitions. For example, the following clause will match if the number of entries in the pulled entity is greater than some number:

(defn- done=
  "The form is complete when a certain number of form attributes have
  been selected."
  [n]
  (fn [[self-entity]]
    (->> (keys self-entity)
         (filter form-attr?)
         (count)
         (<= n))))

(fsm/reg-fsm ::simplified-form
  ;; Keep processing ::select events until form is filled.
  (fn [self n]
    {:ref  self
     :stop #{::done}
     :fsm  {nil {[::select self] {:to   ::done
                                  :when (done= n)
                                  :pull [self]}}}}))

:dispatch: [optional] Dispatch one or more events iff this clause is matched. Same semantics as the Re-frame fx, except also supports cardinality many (a.k.a :dispatch-n)
:dispatch-later: [optional] Dispatch one or more events later, iff this clause is matched. Same semantics as the Re-frame fx, except also supports cardinality many

Besides these options, the expanded form allows you to declare a list of clauses:

{::paused {[::selected self] ::playing
           [::play self]     [{:to       ::playing
                               :when     ::cond1
                               :dispatch [::other-event ...]}
                              {:to       ::fast-forward
                               :when     (fn cond2 [event] ...)}]}}

When matching, the list of clauses is considered in order, like clojure.core/cond, and the one that has either no :when conditional, or a :when conditional that evaluates truthy triggers the transition. Note that while the rest of the FSM implementation has been written to be quite fast, the cost of the :when conditionals is obviously open ended. Try to keep them performant.

Transition Timeouts

An FSM can define a timeout for any state by including a special ::fsm/timeout prefix in that state's transition map:

(fsm/reg-fsm ::timeout-fsm
  (fn [self]
    {:ref  self
     :stop #{::done ::error}
     :fsm  {nil    {[::advance self] ::next}
            ::next {[::advance self]          ::done
                    [::fsm/timeout self 1000] ::error}}}))

This FSM defines a timeout transition for the ::next state. If the [::advance self] prefix is not matched in 1000 ms, then an ::fsm/timeout event is dispatched synchronously to transition the FSM to the ::error state.

Note: only one timeout prefix is allowed per state transition map.

A distinction is made between whether the timeout belongs to the FSM itself, or some other FSM. This is determined by the first positional argument of the ::fsm/timeout prefix, here self. Each FSM is responsible for dispatching its own timeouts, but not that of others.

In detail, given [::fsm/timeout arg1 arg2 & more]:

arg 1: [required] A reference. If this first arg of the prefix is the same as the FSM :ref, then the FSM will dispatch the timeout event at the right time:

 (fsm/reg-fsm ::self-timeout
   ;; Will timeout and reach ::done after 1000 ms in the nil state
   (fn [self]
     {:ref  self                                         ; self ref
      :fsm  {nil {[::fsm/timeout self 1000] ::done}}}))  ; self ref

If the first arg is a reference to some other FSM, then the prefix is matched regularly, and the other FSM would be in charge of dispatching the ::fsm/timeout event:

 (fsm/reg-fsm ::waits-for-other-fsm-timeout
   ;; Will reach ::done state when some other FSM has timed out
   (fn [self other]
     {:ref  self                                         ; self ref
      :fsm  {nil {[::fsm/timeout other 1000] ::done}}})) ; other ref

arg 2: [optional] The duration in milliseconds of the timeout. This can be omitted if you are matching a timeout from another FSM.

other args: [optional] You can provide any number of additional arguments, mostly useful for matching purposes. For example, if an FSM has multiple timeouts, you can differentiate between them in prefixes:

(fsm/reg-fsm ::fsm-a
  ;; ::fsm-a transitions on ::advance events. The :ref and the
  ;; first arg of ::fsm/timeout match, so the timeout will be
  ;; dispatched at the right time.
  (fn [fsm-a]
    {:ref  fsm-a                                                     ; <- Same ref
     :stop #{::done ::error}
     :fsm  {nil    {[::advance fsm-a]                 ::next
                    [::fsm/timeout fsm-a 1000 ::done] ::done}        ; <- Same ref
            ::next {[::advance fsm-a]                  ::done
                    [::fsm/timeout fsm-a 1000 ::error] ::error}}}))  ; <- Same ref

(fsm/reg-fsm ::fsm-b
  ;; Waits for a timeout from ::fsm-a, but the prefix must
  ;; match ::done. If ::fsm-a never fires a ::done timeout,
  ;; ::fsm-b will never transition out of the nil state.
  (fn [fsm-b fsm-a]
    {:ref  fsm-b                                                     ; <- Different ref
     :stop #{::done}
     :fsm  {nil {[::fsm/timeout fsm-a 1000 ::done]} ::done}})        ; <- Different ref

Recursive FSM definitions

Quite often you have a set of transitions that should be possible from multiple states. To reduce boilerplate, the FSM syntax has a recursive syntax that allows you to distribute a set of transitions across an entire FSM sub-spec.

For any key in your :fsm map where you would normally have a state key, you can instead have an FSM sub-spec:

{:fsm {;; regular
       ::s1                     {[:e1 self] ::s2}

       ;; recursive
       {::s3 {[:e2 self] ::s4}
        ::s4 {[:e3 self] ::s4}} {[:distribute self] ::s5}}}

The {[:distribute self] ::s5} transition map is then merged into the transition map of each state in the sub-spec, which is in turn merged into the parent spec, resulting in:

{:fsm {::s1 {[:e1 self] ::s2}

       ::s3 {[:e2 self]         ::s4
             [:distribute self] ::s5}    ; <- merged here

       ::s4 {[:e3 self]         ::s4
             [:distribute self] ::s5}}} ; <- and here

For example, you may want to be able to restart a process from more than one step in your pipeline:

(fsm/reg-fsm ::process
  (fn [self]
    {:ref  self
     :stop ::stop
     :fsm  {{nil  {[::advance self] ::s1}
             ::s1 {[::advance self] ::s2}
             ::s2 {[::advance self] ::s3}
             ::s3 {[::advance self] ::s4}
             ::s4 {[::advance self] ::s5}} {[::restart self] nil}

            ::s5 {[::advance self] ::stop}}}))

With the above definition, the process could be restarted from any of the states nil, ::s1, ::s2, ::s3, or ::s4, but not ::s5.

However, do not confuse this recursive formulation as a way to produce hierarchical behaviour. This recursive formulation is ultimately just about distributing transitions across states to reduce boilerplate.

Hierarchical FSMs

Hierarchical composition of FSMs is done by chaining together their event input signals or conditional clauses using references.

(fsm/reg-fsm ::workflow-a
  (fn [ref-a ref-b]
    {:ref ref-a
     :or  ::step-1
     :fsm {::step-1 {[::done ref-b] ::done}
           ::done   nil}}))

(fsm/reg-fsm ::workflow-b
  (fn [ref-b]
    {:ref ref-b
     :or  ::step-1
     :fsm {::step-1 {[::advance ref-b] ::step-2}
           ::step-2 {[::advance ref-b] ::step-3}
           ::step-3 {[::advance ref-b] ::step-4}
           ::step-4 {[::advance ref-b] {:to       ::done
                                        :dispatch [::done ref-b]}}
           ::done   nil}}))

Here we define two FSMs, each one a simple pipeline from one step to another. The FSMs are parameterized by their arguments, which are all references. These in turn specify the event prefixes, :dispatch events, :pull expressions, and the FSM :ref identities.

There are generally two ways to create hierarchical relationships between FSMs:

:dispatch an event in the clause of a child and match it against a prefix in the parent (as seen above)
Pass a child's reference to the :pull clause of the parent, and then test it's state in the :when conditional

The snippet above demonstrates the first approach. The full example in the reflet.client.ui.workflow.impl namespace uses both.

In either case, once you've defined the logic, all that is left is to pass the right refs to the right FSM subscriptions to connect things together in the view code.

For example, let's say you want ::workflow-b to be a sub processes of ::workflow-a. This could look something like:

(f/with-ref {:cmp/uuid [::a ::b]}
  (let [state-a @(f/sub [::workflow-a a b])
        state-b @(f/sub [::workflow-b b])]
    ...))

with-ref creates the references, and then the b ref is passed as the second argument to ::workflow-a. This way when ::workflow-b finally transitions from ::step-4 to ::done and dispatches the [::done b] event,::workflow-a will see this, and transition out of ::step-1 and into ::step-2.

These snippets describe a simple parent-child relationship. But the example client goes beyond that to demonstrate a multi step, multi-level (if somewhat contrived) hierarchical form workflow.

It also shows how you might implement a set of multimethods to render some views for each step in the workflow. At the end of the day, it's still just about getting the right refs to the right FSM subscriptions.

zalky

As always in Reflet, references are the glue that binds everything together.

More Examples

Besides what was covered in this document, there are more useful examples in the reflet.client.ui.player.impl and reflet.client.ui.workflow.impl namespaces. Also the unit tests in reflet.fsm-test cover much of the API usage in detail.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Finite State Machines