EP 003 - Finite State Machines

Status: Placeholder. Don't bother reading yet.

Abstract

Colloquial: I'd like re-frame to have a better story for programming in FSMs. I want to represent "Higher Order Behaviour" which currently gets "smeared" across multiple event handlers.

Introduction

Many high level aspects of SPAs are best modelled explicitly as an FSM. First, an app must gather X from the user, but if they press cancel, then return to showing Y, but otherwise move on to do activity Z. It is quite natural to model such overall decisions and the UIs involved as an FSM.

Many low level aspects of SPAs are best modelled explicitly as FSM too. The simple act of GETing from a server involves various states, including waiting, and failed, and timed-out, and retrying and succeeded.

BUT you need the power of a fully expressive state machine. You need orthogonal state, guards, hierarchical state, history, etc. Back in 1987, Harel identified the set of features required - anything less and your tool will not be expressive enough to do the job.
Harel also insisted that statecharts was a visual formalism, so tooling is also important.

Why?

Beware of the Turing tar-pit in which everything is possible but nothing of interest is easy.
-- Alan Perlis

State machines are appealing because:

• they constrain you (vs the full Turing tar-pit). Just because you can wield immense power doesn't mean you should.
• they force you to think through and structure a problem. This process helps to flush out the corner cases.
• they make explicit certain important assumptions which are otherwise hidden in a thicket of conditionals.

Also, Why Developers Never Use State Machines https://www.skorks.com/2011/09/why-developers-never-use-state-machines/

How?

Technical elements:

• a way to register:
  • a state machine specification against a machine-id
  • the specification will be a data structure, listing states, transitions, etc
• a way to create an instance of a registered state machine
  • args: machine-id, id for this particular instance
  • data for machine instance will be stored in app-db (at :machines or a configurable place?)
• a way to trigger
  • the id of the state machine targeted
  • the trigger
  • the trigger args
• trigger causes:
  • state transition
  • an action fn to be called which produces :effects
• UI changes. See EP on reg-view which will make it much easier to describe UI in machine data structure
• a way to destroy an instance

Misc Notes

Events model user intent, not implementation details.

So, we DO NOT want events that talk about FSM or triggers etc because that's an implementation detail.

Instead, we want

But event handlers should know about XXX

Triggers

Types of triggers:

1. External (from the user, websocket)
2. Data - something about app-db has changed

Implementation

What if we didn't even use FSM and used Behaviour Trees instead?
Behaviour trees are more composable. A better match for a data-oriented design.

Links And Notes:

• statecharts
• THE PRECISE SEMANTICS OF UML STATE MACHINES
• David Khourshid - Infinitely Better UIs with Finite Automata also written
• Statecharts: Updating UI state
• https://statecharts.github.io/
• Harel Paper
• setState Machine Speaker Deck by Michele Bertoli

Previously CLJS :

• https://github.com/jebberjeb/reframe-fsm
• https://github.com/protocol55/re-state
• http://blog.cognitect.com/blog/2017/8/14/restate-your-ui-creating-a-user-interface-with-re-frame-and-state-machines

Other Attempts:

• Fractal UI components using snabbdom, Harel statecharts, and event emitters

• BT 101 – Behavior Trees grammar basics

• Understanding Behavior Trees

• behavior3js github repo

• Understanding the Second Generation of Behavior Trees (video)

• 10 Reasons the Age of Finite State Machines is Over

• Parameterizing Behavior Trees

• Behavior Trees in Robotics and AI

TLA+

• ** Three Approximations - includes SAM
• State Machines and Computing
• SAM – the State-Action-Model pattern
• TLA Intro
• Computation and State Machines - Leslie Lamport
• SAM Pattern in JS