metosin / tilakone

Minimalistic finite state machine (FSM) in Clojure

tilakone

Minimalistic finite state machine (FSM) in Clojure.

Status: Deprecated.

Tilakone (eng. State machine)

Noun

state machine (plural state machines)

 (computing theory) A formalism for describing computation, consisting of a set of 
 states and a transition function describing when to move from one state to another.

source: wiktionary.org

Usage

Tested with Clojure 1.10.0

All bundled:

[metosin/tilakone "0.0.4"]

Optionally, the modules can be required separately:

[metosin/tilakone.core "0.0.4"]
[metosin/tilakone.schema "0.0.4"]

Intro

The excellent cdorrat/reduce-fsm library has a nice FSM example:

; from https://github.com/cdorrat/reduce-fsm#basic-fsm

(defn inc-val [val & _] (inc val))

(fsm/defsm count-ab
  [[:start
    \a -> :found-a]
   [:found-a
    \a ->  :found-a
    \b -> {:action inc-val} :start
    _ -> :start]])

;; We can use the generated fsm like any function
(map (partial count-ab 0) ["abaaabc" "aaacb" "bbbcab"])
;; returns => (2 0 1)

This is very nice and works for many cases. The reduce-fsm library uses macros to define the FSM and actions are functions. This makes the reduce-fsm less suitable if you need to serialize your FSMs.

Tilakone is a similar FSM library, but it uses pure data to define the FSM states (no macros needed) and the action functions can be defined separately.

Here's the same example with tilakone:

(ns example.count-ab-example
  (:require [tilakone.core :as tk :refer [_]]))

; State definitions, pure data here:

(def count-ab-states
  [{::tk/name        :start
    ::tk/transitions [{::tk/on \a, ::tk/to :found-a}
                      {::tk/on _}]}
   {::tk/name        :found-a
    ::tk/transitions [{::tk/on \a}
                      {::tk/on \b, ::tk/to :start, ::tk/actions [:inc-val]}
                      {::tk/on _, ::tk/to :start}]}])

; FSM has states, a function to execute actions, and current state and value:

(def count-ab
  {::tk/states  count-ab-states
   ::tk/action! (fn [{::tk/keys [action] :as fsm}]
                  (case action
                    :inc-val (update fsm :count inc)))
   ::tk/state   :start
   :count       0})

; Lets apply same inputs to our FSM:

(->> ["abaaabc" "aaacb" "bbbcab"]
     (map (partial reduce tk/apply-signal count-ab))
     (map :count))
;=> (2 0 1)

Note that the state definitions in count-ab-states are pure data.

Also, there is one extra state transfer defined in tilakone example from state :start. In reduce_fsm the default behaviour for signal (that is, if no transition is found for signal) is to stay at the current state, but tilakone treats all undeclared state transfers as errors. For this purpose the above example declares an explicit rule to allow any unmatched signal (_) in state :start to be handled as transition to state :start.

The count-ab is the actual FSM. It contains the state declarations, optional actions function (more of actions later), current state and current value. Note that the state and value can be any clojure value.

The tilakone.core/apply-signal function accepts an FSM and a signal. It returns the FSM with possibly updated state and value.

Documentation

• TODO

Comparing reduce-fsm and Tilakone

• reduce-fsm is older project with far more users
• reduce-fsm is faster (at least at the moment)
• reduce-fsm is more feature complete
• tilakone FSMs are pure data™
• tilakone code is quite a bit simpler with no macros and less code (reduce-fsm 592 lines, tilakone 145 lines)

TODO

• proper documentation
• examples on :enter/:leave actions, state guards, etc
• add tilakone visualization
• add perf tests

License

Copyright © 2019 Metosin Oy

Distributed under the Eclipse Public License, the same as Clojure.

tilakone's Issues

Examples don't work with given version

Cool little library.

The examples in the readme and examples directory don't work with version 0.0.4 which is the dependency given in the readme. The readme and simple.clj examples throw null pointer exceptions.

It took me a bit to discover that there's a 0.0.5-SNAPSHOT on clojars that is needed for the examples to work.

Push latest to clojars

Hello!

I've added this as a dependency but it is compiling with errors on a cljs project.

------ WARNING #1 - :undeclared-var --------------------------------------------
 Resource: tilakone/util.cljc:104:20
 Use of undeclared Var tilakone.util/format
--------------------------------------------------------------------------------

------ WARNING #2 - :undeclared-var --------------------------------------------
 Resource: tilakone/util.cljc:114:20
 Use of undeclared Var tilakone.util/format
--------------------------------------------------------------------------------

Apparently 616410a solves this. Can you push it to clojars, please?
I have no clue how to add remote repos as dependencies.

Thanks for the library!

Turn ::tk/states into map?

Hi,

thanks for this neat little library! While exploring it, I was wondering why ::tk/states is a sequence of maps with ::tk/name rather than a map with ::tk/name as keys. The latter would take care of preventing duplicate state definitions (which AFAICT don't serve a purpose and aren't detected by the validation function right now) as well as improve performance for large state machines because currently, each state lookup requires a linear search. I'm happy to provide a patch if you're interested. If so, let me know if you would like to retain backwards compatibility with the current API.