Readme — com.fulcrologic/statecharts 1.0.0-alpha1

State Charts for Clojure(script)

An implementation of state charts that use the SCXML structure and semantics (as far as they are defined), without the need for XML.

A statechart is defined as a (nested) map. Some of this content’s behavior is configurable. The simplest setup is to use Clojure for the executable code and a simple data model that scopes data to states.

To make it easier to write the maps there are functions for each element type in the com.fulcrologic.statecharts.elements namespace, and it is recommended that you use these because some of them validate their parameters and children.

Once you have a machine definition you need to create a session, which is just a running instance of the machine.

Once you have a session, you can send events to it, and look at the content of the session (or store it, etc).

Here’s a traffic light example from the src/examples directory in this repository that leverages parallel and compound states to simulate traffic lights with pedestrian signals:

link:src/examples/traffic_light.cljc[role=include]

If you run the items in the comment block, you’ll see:

(:cross-ew/red :cross-ns/white :east-west/green :north-south/red)
(:cross-ew/red :cross-ns/flashing-white :east-west/green :north-south/red)
(:cross-ew/red :cross-ns/flashing-white :east-west/yellow :north-south/red)
(:cross-ew/white :cross-ns/red :east-west/red :north-south/green)
(:cross-ew/flashing-white :cross-ns/red :east-west/red :north-south/green)
(:cross-ew/flashing-white :cross-ns/red :east-west/red :north-south/yellow)
(:cross-ew/red :cross-ns/white :east-west/green :north-south/red)

History support includes both shallow and deep. Here’s a shallow example:

link:src/examples/history_sample.cljc[role=include]

See the SCXML spec for how to structure elements. The structure and naming are kept close to that spec for easy cross-referencing with its documentation.

2. Status

ALPHA.

The state chart definition (machine and elements) are API stable, as is the underlying base algorithm (though it may have bugs).

The API is 90+% stable, but may undergo minor changes to accomodate design of invoke and (expanded) send elements.

Implemented
- DataModel, ExecutionModel, and EventQueue abstractions, along with a simple implementation.
  - Late and early data model binding.
- Compound, parallel, atomic, initial, and final states
  - on-entry, on-exit
  - History (deep and shallow). Multiple nodes allowed, with default transitions (for when there is no history).
- Transitions
  - Eventless transitions
  - Guards
  - Executable content when taking a transition
- Executable content elements:
  - Script, raise, send, log, assign, and done-data.
  - Executable content elements are extensible (you can make your own kind)
- Simple dev-mode SCXML → CLJC conversion utility (see src/dev).
Not yet implemented
- Invoke external processes.
- Send events to arbitrary other sessions/services (easy add-on by user)
- Additional Executable content:
  - The other (e.g. if/else) SCXML flow control elements. (may not ever bother, but this is extensible, so you can easily do so)

See Conformance.adoc at the root of this repository for notes on decisions that might affect exact conformance to the standard.

2.1. Goals and Extensibility

This library supports a lot of flexibility, and has many long-term goals:

Compatible with distributed systems. For example a cluster might run long-lived state machine sessions that can be serviced by any node of the custer.
State machine definitions can be versioned.
Everything can be made to be serializable (including the code in the machine).

Thus you can define (via protocols):

How to interpret the executable code of the state machine (e.g. on-exit, cond, etc.). You could, for example, use strings for those, and Javascript or SCI to interpret them (making the machine completely serializable).
How the data model of the states work. You can, for example, hook the data model into Fulcro, Reagent, Datomic, Datascript, etc.
The implementation of the event queue. This allows you to generate state machines that know how to send events to each other, can be distributed, etc. It is necessary to make this part of the internals because the state charts support sending events from within state code, which as we mentioned above, could be interpreted by your own execution model and may not actually be Clojure(script).
The actual state chart processing semantics/algorithm. A version of the W3C 2015-09-01 recommendation for SCXML is provided as a default.

However, it would be a real hassle if you had to set up all of that stuff just to get what many people want: A statechart that can run in CLJC, using Clojure code, and a functional interface where you can manually send events to the machine. Thus, a reasonable default implementation is provided for the above, and it is simple to expand this to meet your needs.

3. Guide

First some very important notes:

Every node in a state chart has a UNIQUE ID. These IDs are autogenerated if you do not supply them.
Most of the "executable content" elements described in the SCXML standard (e.g. <if>) are simply collapsed into the script node.

3.1. Terminology

Atomic State: A state that does not have substates.
Compound State: A state that has child states, where at most one child is active at any given time.
Parallel State: A state that has more than one compound substate, all of which is active at the same time, and thus have a child state that is active.
Configuration: When used in the context of a state chart, the configuration is the list of all active states. A state is active if it or ANY of its children are active. Thus, a parallel machine with hierarchical states may have a rather large set of IDs in its current configuration.
Working Memory: A map of data that contains the current configuration of the state machine, and other information necessary to know its current full state (which states have had their data model initialized, possible data model tracking, etc.).
DataModel: An implementation of the data model protocol defines how the data model of your chart works. The simple implementation places the data in Working Memory, and treats lookups in a scoped fashion.
ExecutionModel: An implementation of this protocol is handed the expressions that are included on the state chart, and chooses how to run them. A default implementation requires that they be Clojure (fn [env data]), and simply calls them with the contextual data for their location.
External Event: An event that came from the external API, either by you calling process-event or some other actor code doing so (invocations, sends from external machines, etc.).
Internal Event: An event that came from the session that will process it. These come from the machine implementation itself (e.g. done evens) and from you using the raise element in an executable content position.
EventQueue: A FIFO queue for external event delivery. The event queue is responsible for holding onto pending External Events to "self", possibly other statechart sessions (instances of other machines), remote services (e.g. send an email), and for delayed delivery. The default implementation is a "manually polled" queue that does not support most of these features, and the delayed event delivery is manual (e.g. you have to poll it, or ask it when the next one should happen and start a timer/thread). Creating a system that runs the loop and does the timed delivery is typically how you would use these in a more serious/production environment.
Processor: An implementation of the statechart algorithm. This library comes with an implementation that follows (as closely as possible) the SCXML recommended standard from 2015. You may provide your own.
Session: The combination of the content of the DataModel and Working Memory. I.e. all of the data you’d need in order to resume working from where you last left off. Sessions typically have a unique ID, which could be used to store sessions into durable storage when they are "idle", and are used for cross-session events.
Conditional Element: In statecharts there is a node type (represented as a diamond) that represents a state in which the machine never "rests", but instead immediately transitions to another node based on predicate expressions. In this library (and SCXML) this is modelled with a state that has more than one transition, NONE of which have and :event qualifier (meaning they are exited as soon as they are entered, assuming there is a valid transition).

3.2. Data Models

The SCXML specification allows the implementation quite a bit of latitude in the interpretation of the chart’s data model. You could define scopes that nest, one global map of data that is visible everywhere, or hook your data model to an external database.

See the docstrings in the protocols namespace.

3.3. Transitions

A state can have any number of transition elements. These are tested in order of appearance, and the first transition that matches the current circumstance is taken. Transitions are enabled when:

Their cond (if present) evaluates to true AND
Their event (if present) matches the current event’s name (See event name matching)
OR neither are present.

An "eventless" transition without a :cond is always enabled. Condition states can be modelled using such transitions. For example, this is a conditional state that when entered will immediately transition to either state :X or :Y, depending on the result of the first transition’s condition expression:

(state {:id :Z}
  (transition {:cond positive-balance? :target :X})
  (transition {:target :Y}))

3.4. Event Processing

In a fully-fleshed system your event queue would have a corresponding runtime story, where process-event was automatically called on the correct machine/session/invocation/service when an event is available. As such, and event queue might be distributed and durable (e.g. using Kafka or the like), or might simply be something that runs in-core (a core.async go-loop).

The "simple" model that is provided with this library is an in-memory queue, with no automatic processing at all. If you want to support events that come from outside of the machine via the queue, then you have to create a loop that polls the queue and calls process-event!. If you do this, then event the delayed event delivery will work, as long as your code watches for the delayed events to appear on the queue.

3.4.1. Autonomous Execution

You can, of course, write your own "event loop". The library comes with a core.async event queue that works in conjunction with the simple model to provide an event loop that will automatically process events as they come in, and will allow the machine to send itself external events (usually done in order to get a delay). Note that the raise element does not use the external queue, but also does not provide delays.

Below is an example of using the core.async queue to run a traffic light that automatically changes over time:

link:src/examples/traffic_light_async.cljc[role=include]

The send element has a Send alias so you can avoid shadowing the Clojure function.

3.5. Execution

Most people will probably just use the CLJCExecutionModel, which lets you write executable content in CLJC as lambdas:

;; Use `data` to compute when this transition is "enabled"
(transition {:event :a :cond (fn [env data] (your-predicate data))}
  ;; Run some arbitrary code on this transition
  (script {:expr (fn [env data] ...)}))

There is a macro version of the script element called sfn that can be used as a shorthand for script elements:

;; Use `data` to compute when this transition is "enabled"
(transition {:event :a :cond (fn [env data] (your-predicate data))}
  ;; Run some arbitrary code on this transition
  (sfn [env data] ...)))

3.6. Working Memory and Identity

The working memory of the state machine is plain EDN and contains no code. It is serializable by nippy, transit, etc. Therefore, you can easily save an active state machine by value into any data store. The value is intended to be as small as possible so that storage can be efficient.

Every active state machine is assigned a ID on creation (which you can override via initialize). This is intended as part of the story to allow you to coordinate external event sources with working with instances of machines that are archived in durable storage while idle.

4. Relationship to SCXML

This library’s internal implementation follows (as closely as possible) the official State Chart XML Algorithm. In fact, much of the implementation uses internal volatiles in order to match the imperative style of that doc for easier comparison and avoidance of bugs.

The actual structure of the live CLJC data used to represent machines also closely mimics the structure described there, but with some differences for convenient use in CLJC.

Specifically, executable content is still treated as data, but the XML nodes that are described in the standard do not exist in this library, because a conformant XML reader (which would need to be aware of the target execution model) can easily translate such nodes into the target data representation (even if that target representation is script strings).

Some of the data model elements are also abbreviated in a similar manner. See the docstrings for details.

Thus, if you are trying to read SCXML documents you will need to write (or find) an XML reader that can do this interpretation.

For example, an XML reader that targets sci (the Clojure interpreter) might convert the XML (where a and do-something are implied values in the data and excution model):

<if cond="(= 1 a)">
  (let [b (inc a)]
    (do-something b))
</if>

into (scope and args still determined by the execution model selected):

;; String-based interpretation
(script {:expr
  "(if (= 1 a)
     (let [b (inc a)]
       (do-something b)))"})

;; OR eval-based
(script {:expr
  '(if (= 1 a)
     (let [b (inc a)]
       (do-something b)))})

;; OR functional
(script {:expr (fn [env {:keys [a]}]
                  (if (= 1 a)
                    (let [b (inc a)]
                      (do-something b))))})

If you’re using XML tools to generate you machines, though, it’s probably easiest to use script tags to begin with.

4.1. Related Work

The primary alternative to this library is clj-statecharts, which is a fine library modelled after xstate.

This library exists for the following reasons:

At the time this library was created, clj-statecharts was missing features. In particular history nodes, which we needed. I looked at clj-statecharts in order to try to add history, but some of the internal decisions made it more difficult to add (with correct semantics) and the Eclipse license made it less appealing for internal customization as a base in commercial software (see https://www.juxt.pro/blog/prefer-mit).
To create an SCXML-like implementation that uses the algorithm defined in the W3C Recommended document, and can (grow to) run (with minor transformations) SCXML docs that are targeted to Clojure with the semantics defined there (such as they are).
To define more refined abstract mechanisms such that the state charts can be associated to long-lived things (such as a monetary transaction that happens over time) and be customized to interface with things like durable queues for events (e.g. AWS SQS) and reliable timers.
MIT licensing instead of Eclipse.

Other related libraries and implementations:

XState : Javascript. Could be used from CLJS.
Apache SCXML : Stateful and imperative. Requires writing classes. Requires you use XML.
Fulcro UI State Machines : A finite state machine namespace (part of Fulcro) that is tightly coupled to Fulcro’s needs (full stack operation in the context of Fulcro UI and I/O).

4.2. Conformance

This library was written using the reference implementation described in the SCXML standard, but without the requirement that the machine be written in XML.

Any deviation from the standard (as far as general operation of state transitions, order of execution of entry/exit, etc.) should be considered a bug. Note that it is possible for a bugfix in this library to change the behavior of your code (if you wrote it in a way that depends on the misbehavior); therefore, even though this library does not intend to make breaking changes, it is possible that a bugfix could affect your code’s operation.

If future versions of the standard are released that cause incompatible changes, then this library will add a new namespace for that new standard (not break versioning).