Organizing computation with Finite Schema Machines

When I was on my 𝑛th refactor of a thread macro with multiple embedded if expressions, I realized I was trying to handle lots of special cases without really thinking about them. But in the back of my mind, I knew I was trying to dispatch my function calls on the basis of whether the data I was passing through my function matched some predicate or other - another way of saying that the data was in a particular state.

After some sketches revealed that my understanding of the concepts was muddled and confused, I extensively googled "state machine" with some extra surrounding words, and it helped me discover that Leslie Lamport paper. The math is over my head, but the concept inspired me to figure out a better way of organizing what functions to call and when. A month and a half later, here it is.

State, Action, Function, Data

Before going through the code, it's worth going over the definitions outlined by Lamport early on in the paper.

I begin by considering what a computation is. There are several ways to define computation. For now, I take the simplest: a computation is a sequence of steps, which I call a behavior. There are three common choices for what a step is, leading to three different kinds of behavior:

Action Behavior

A step is an action, which is just an element of some set of actions. An action behavior is a sequence of actions.

State Behavior

A step is a pair〈s,t〉of states, where a state is an element of some set of states. A state behavior is a sequence s1 → s2 → s3 → ··· of states. The step〈si,si+1〉represents a transition from state si to state si+1.

State-Action Behavior

A step is a triple〈s,α,t〉, where s and t are states and α is an action. A state-action behavior is a sequence s1α1 → s2α2 → s3α3 → ···. The step〈si, αi,si+1〉represents a transition from state si to state si+1 that is performed by action αi.

This terminology clarified the shaky concept in my head and in my messy sketches. I was attempting to define a state-action behavior: I wanted to call a function (action) on the basis of some property of the data I was currently working with (state). That function would change the properties of that data - in other words, advance it to a new state.

How should those states be defined? Fabricate already extensively uses the malli schema library, so that was a natural choice. Its expressivity makes it easy to define states and incrementally refine them to match the data being processed by a program. It also meant that I would have to write my own implementation of a finite state machine, as the existing libraries in the Clojure ecosystem don't really work with Malli. The closest library to this concept that I currently know of is Dativity, which describes itself as a "stateless process engine." Fabricate's implementation, relying as it does on Malli, is different than Dativity's; it was a conceptual rather than implementational reference point.

A simple implementation

Let's take a tour through Fabricate's fsm namespace. The implementation is extremely simple right now, consisting of two functions:

(defn advance
  "Takes a value, matches it against the schema keys defined in the
   input state-action map, and calls the appropriate function to advance
   the value to the next state.

  Additional arguments to the function can be supplied via & args; they will be
  appended to the arguments passed to the matched function via apply.

  Errors in function execution will be printed and the input value will be returned."
  {:malli/schema [:=> [:cat state-action-map
                       [:or fsm-value-map :any]
                       [:* :any]] [:or fsm-value-map :any]]}
  [fsm-map value & args]
  (let [union-schema (schema/unify (keys fsm-map))
        fsm-v-map? (fsm-value-map? value)
        v (if fsm-v-map? (:state/value value) value)
        ;; value (if debug? (:fsm/value value) value)
        parsed (m/parse union-schema v)]
    (u/with-context
        (merge {:state/value v :log/level 300}
               (when fsm-v-map? (select-keys value [:state/name :state/description]))
               (select-keys (meta fsm-map) [:fsm/name :fsm/description]))
      (if (= :malli.core/invalid parsed)
        (do
          (u/log ::unmatched-value
                 :malli/error (me/humanize (m/explain union-schema v)))
          value)
        (let [matched-state (-> union-schema
                                m/children
                                (nth (first parsed))
                                last)
              op (get fsm-map matched-state
                      (get fsm-map (m/form matched-state)
                           (fn [vv]
                             (u/log ::unmatched-value
                                    :malli/error
                                    (me/humanize (m/explain union-schema vv)))
                             vv)))
              result (try (u/trace
                              ::advance
                            (->> (select-keys
                                  (m/properties matched-state)
                                  [:state/name :state/description])
                                 (apply concat)
                                 (into []))
                            (apply op v args))
                          (catch Exception e (Throwable->map e)))
              error-result? (schema/throwable-map? result)]
          (cond
            (and fsm-v-map? (not error-result?))
            (assoc
             {:state/value result
              :fsm/matched-state matched-state}
             :fsm/previous-state
             (or (:fsm/matched-state value) :fsm/initial))
            (and fsm-v-map? error-result?)
            (assoc
             {:state/error result
              :fsm/matched-state matched-state}
             :fsm/previous-state
             (or (:fsm/matched-state value) :fsm/initial))
            error-result? value
            (not (or error-result? fsm-v-map?)) result))))))

(defn complete
  "Completes the fsm by advancing through states until the same value is produced twice."
  {:malli/schema [:=> [:cat state-action-map :any [:* :any]] :any]}
  [fsm-map value & args]
  (let [fsm-states
        (iterate (fn [s] (apply advance fsm-map s args)) value)]
    (u/trace ::complete
      (apply concat (select-keys (meta fsm-map) [:fsm/name]))
      (reduce (fn [current-state next-state]
                (if (= current-state next-state)
                  (reduced current-state)
                  next-state))
              fsm-states))))

What do these do? They take a given piece of arbitrary Clojure data, and move it through a succession of states. This sequence is defined by a map mapping from malli schemas to functions. Malli schemas are just data, so they are easy to use as map keys. If a piece of data matches one of the states in the keys, it is transformed by calling the corresponding function. If it doesn't, it is returned as-is.

Termination is defined as the same successive value getting returned twice, which is a fairly naive way of representing the fact that there's no longer an action to take. While simple, this aspect mirrors one part of the much more formal and rigorous semantics that Lamport describes in that "that there is no fundamental difference between termination and deadlock."

In Lamport's schema, state t in〈s,α,t〉is derived from the output signature of the function, so it's implicit rather than explicit in the map representation.

There's nothing more to it than that. The challenge lies in precisely describing the succession of states required by the program.

Fabricate's use of Finite Schema Machines

The usage pattern followed by Fabricate is to successively add items to a closed map, such that the state advances when the computation producing that map entry is complete. Starting from a file path, it moves through a read step, a parse step, an evaluation step, and then a render step, after which it writes the file. Because this final function is run only for its side effects, it returns the same value as its input, thus terminating the computation in fsm/complete. This map-accumulation strategy is simple enough to test the implementation while still being extensible enough to dispatch on special cases.

One of the motivating concerns for this implementation was the ability to support multiple output types. Fabricate's README is a markdown file that is still generated by Fabricate, even though Fabricate doesn't include any Markdown parsers in its default dependencies; the library doesn't know anything about markdown, but it can still target it as an output format.

(def markdown-state "Fabricate markdown input evaluated as markdown string" (let [s1 [:map {:fsm/description "Fabricate contents evaluated after parsing" :closed true :fsm/name "Evaluated"} [:site.fabricate.file/input-file [:or [:fn fs/file?] :string]] [:site.fabricate.file/template-suffix [:orn [:default [:= ".fab"]] [:custom :string]]] [:site.fabricate.file/input-filename :string] [:site.fabricate.file/output-extension :string] [:site.fabricate.page/unparsed-content :string] [:site.fabricate.page/parsed-content [:fn vector?]] [:site.fabricate.page/title {:optional true} :string] [:site.fabricate.page/namespace {:optional true} :symbol] [:site.fabricate.file/output-file {:optional true} [:orn [:path :string] [:file [:fn fs/file?]]]] [:site.fabricate.page/evaluated-content [:fn (fn* [p1__34450#] (or (list? p1__34450#) (vector? p1__34450#)))]] [:site.fabricate.page/metadata {:optional true} [:map {:closed false}]]]] (mu/closed-schema (mu/merge s1 [:map {:fsm/description "Fabricate markdown input evaluated as markdown string" :closed true :fsm/name "Markdown"} [:site.fabricate.file/output-extension [:enum "md" "markdown"]]]))))

In the read step, data about the input file is appended to the map holding a page's state. This data allows us to dispatch functions on that map entry, running a function (after the evaluation step) that basically just renders the page as a markdown string for any pages that need to have Markdown as an output format. This allows for special cases in the rendering pipeline to be handled merely by progressively refining the schema to pick out the parts of data that identify them, and writing functions that are compatible with the remaining states.

Similar logic could be used to dispatch on the input filetype. Fabricate doesn't use any markup, but Finite Schema Machines give any users who desire to use Markdown an extensible method for adding it (or asciidoc) to their own rendering pipelines.

Other state machine implementations are possible; one could update an entry in place in the same map, as long as the possible values for that entry were appropriately constrained. Other applications might not need to hold to as many pieces of intermediate information, and so could choose a different representation of the sequence of states.

Limitations

This implementation, such as it currently is, will make no attempt to prevent users from doing silly things like an infinite succession of states:

(fsm/complete {[:enum :B] (fn [_] :A) [:enum :A] (fn [_] :B)})

Or from making a succession of states that only terminates when you reach an integer overflow:

(fsm/complete {:int inc} 1)

It will also advance on the first match, so you have to think carefully about making your states mutually exclusive. Luckily, the fact that map keys have to be distinct in Clojure already forces you to do that for obviously overlapping inputs, but there are many more subtle cases, especially when you're working with maps that may have overlapping keys:

(fsm/advance {[:map {:closed false} [:a :int]] (fn [m] (update m :a dec)) [:map {:closed true} [:a :int]] (fn [m] (update m :a inc))})

The value {:a 1} will just match against the first entry, even if that's not what you want. Map keys are unordered, so the best way to control this is to make the schemas as specific as possible. Fabricate deals with this by using closed maps and adding new keys to them as data advances through the states.

I have some design concepts for how the really obvious problems could be anticipated through a validation mechanism for the map defining the FSM, but that is a topic for a future expansion of this post.

Why Not Just Use cond/cond-> or Predicate Functions Mapped to Transforming Functions?

That certainly is a way to achieve a similarly lightweight implementation of a lot of this concept. I prefer the schema-based approach because it then becomes possible to unify the schema and identify matching schemas with malli.core/parse, which makes certain types of function dispatch much easier! Malli is also just a really great library, one that I think embodies the idea of declarative programming at its best.

Not Quite Fully Abstract - But Clearer

That said, gushing about how easy Malli and Clojure have made implementing this concept means I must admit that I'm not really following Lamport's main advice in that paper; I'm still fussing about with language details instead of using the formalism of pure mathematics (or TLA+) to achieve true rigor. But I didn't turn to Lamport's paper because I was interested in proving my static website generator correct; I think he might agree that personal experiments in generating static HTML are not a sufficiently complex and high-stakes problem to even warrant the use of proofs. I turned to the paper because I was struggling to think of a way to match states with functions. Thanks to the definitions provided in the second section of the paper, I eventually identified a simple and expressive way of doing so.

Malli isn't set theory, but it is simple and expressive enough that I am not as bogged down in implementation details, and I at least have become a bit more clear-eyed that I'm working with finite-state machines. Using it has forced me to think harder about just how I'm defining the data states I care about instead of just creating a true/false predicate that falls over on data of a slightly different shape than what it expects. It has forced me to think about how errors and exceptions fit into the state space of a program executing a series of functions on different sources of data. Lamport said the way to get better programs is to teach programmers to think better. For my part, I think implementing and using finite schema machines has done exactly that.