1 Module behavior/fsm

1 Module behavior/fsm🔗ℹ

This module provides the ability to define, and then execute, state machines using a flexible yet capable model. The definition model provides a state machine that contains a set of discrete states, each state has a set of outbound transitions each of which may be associated with a trigger event. Note, wherever possible the terminology and relationships in the state machine model follow those of the Unified Modeling Language (UML).

State machine definition details:

All state names, and events, are represented as symbols.
Behaviors are represented as simple procedures that take the current machine-execution as a parameter and return void. As the execution instance is immutable the behavior cannot affect the current state.
Transition guards are represented as simple predicates that take the current machine-execution as a parameter and return a boolean which indicates whether the transition is enabled. As the execution instance is immutable the behavior cannot affect the current state.
Additional events may be passed into the model, these will be recorded if received and will be ignored without error. See execution details below for event and transition behavior.
The model supports internal transitions that transition from one state to itself without triggering exit or event behavior(s).
Model validation rules (resulting in exn:fail:contract errors from make-state-machine):
- The model must have one, and only one, start state.
- The model must have one, and only one, final state.
- Transitions marked as internal must have the same source and target state.
- A state may only have one outgoing, unguarded, transition.
Limitations (compared to UML for example):
- The model does not currently support nested, or hierarchical, states.
- The model does not currently support orthogonal regions.

Examples:

> (define simple-fsm (make-state-machine
                      'first-fsm
                      (list (make-state 'hello 'start)
                            (make-state 'goodbye 'final))
                      (list (make-transition 'hello 'goodbye #:on-event 'wake))
                      '(sleep)))
> (define log-string (open-output-string))
> (with-logging-to-port
      log-string
    (lambda ()
      (let* ([exec (make-machine-execution simple-fsm (make-logging-reporter))]
             [started (machine-execution-start exec)]
             [next1 (handle-event started 'sleep)]
             [next2 (handle-event next1 'wake)])
        (void)))
    'info)
> (for-each displayln
            (map (curryr list-tail 3)
                 (map (λ (line) (string-split line " " #:repeat? #t))
                      (string-split (get-output-string log-string) "\n" #:repeat? #t))))
(starting #<state> #f ()))
(enter-state #f #f ("#<procedure:no-behavior>")))
(execute-state #f #f ("#<procedure:no-behavior>")))
(handle-event #<state> #f ("sleep")))
(handle-event #<state> #<transition> ("wake")))
(exit-state #<state> #f ("#<procedure:no-behavior>")))
(transition #<state> #<transition> ("#<procedure:no-guard> => #t")))
(transition-effect #<state> #f ("#<procedure:no-behavior>")))
(enter-state #<state> #f ("#<procedure:no-behavior>")))
(execute-state #<state> #f ("#<procedure:no-behavior>")))
(completed #<state> #f ()))

A state machine is executed by constructing a machine-execution and then calling execution-start. This will transition to the start state and perform any behaviors associated with it. The state machine only transitiona from one state to another in response to an event (via handle-event) or by state completion (via complete-current-state). The state machine is completed when it transitions into either a 'final state, or a state with no outgoing transitions.

Additional execution details:

A new execution has a condition 'created, and will not accept handle-event or complete-current-state calls until in condition 'active.
The call to execution-start will alter the condition to 'active and set the current state to the start state.
Once the execution completes the condition is set to 'complete and the state machine will again reject calls to handle-event or complete-current-state.
When handling an event (if the event is valid for this machine) if no transition leaving the current state is triggered by the event it is logged and ignored. If more than one transition is triggered by the event and they are all enabled an error occurs and the execution condition is set to 'in-error.
Similarly, when calling complete-current-state if no transitions are enabled at this time, or if multiple transitions are enabled, an error occurs.
The last two situations are considered temporary, while the machine indicates an error the actions can be re-tried if a different event is used, or of guard conditions evaluate to different results. In the case where a single transition is enabled on retry the execution condition is reset to 'active.
Reporters are supported that receive events from the running execution for logging or other behavior.
Limitations (compared to UML for example):
- The procedure handle-event is synchronous, no queue is provided for incoming events.

1.1 Types and Predicates🔗ℹ

struct
(struct state-machine (name states events transitions))
  name : symbol?
  states : (hash/c 'symbol state?)
  events : (hash/c 'symbol (listof transition?))
  transitions : (hash/c 'symbol (listof transition?))

The state machine definition, returned by make-state-machine, and which defines the states and transitions and has been validated to be correct. The three hash values are constructed as optimization for the execution and comprise name to state, event to transition, and source state to transition respectively.

struct
(struct state (name kind entry execution exit))
  name : symbol?
  kind : (or/c 'start 'normal 'final)
  entry : (-> machine-execution? void?)
  execution : (-> machine-execution? void?)
  exit : (-> machine-execution? void?)

Represents a state within the state-machine, also included in certain machine-history-event instances.

struct
(struct transition ( source-name
target-name
internal
trigger-event
guard
effect))
  source-name : symbol?
  target-name : symbol?
  internal : boolean?
  trigger-event : symbol?
  guard : (-> machine-execution? symbol? boolean?)
  effect : (-> machine-execution? void?)

Represents a transition within the state-machine, also included in certain machine-history-event instances.

struct
(struct machine-execution (model condition current-state))
  model : state-machine?
  condition : (or/c 'created 'active 'in-error 'complete)
  current-state : state?

This represents the current state of a state machine execution, note that calls to handle-event and complete-current-state return new copies of this structure.

struct
(struct machine-history-event history-event ( current-execution
kind
source
transition
evaluations)
    #:transparent)
  current-execution : machine-execution?
  kind : symbol?
  source : (or/c #f state?)
  transition : (or/c #f transition?)
  evaluations : (listof string?)

These events are sent to the reporter associated with discrete actions taken as part of the state machine execution. For example, kind may be one of 'starting, 'enter-state, 'execute-state, 'exit-state, 'handle-event, 'transition, 'transition-effect, or 'completed.

1.2 Construction🔗ℹ

procedure
(make-state-machine name
states
transitions
[ additional-events]) → state-machine?
  name : symbol?
  states : (non-empty-listof state?)
  transitions : (non-empty-listof transition?)
  additional-events : (listof symbol?) = '()

Construct a new state-machine, all validation of the model is performed during construction and reported as exn:fail:contract exceptions.

procedure
(make-state name
kind
[ #:on-entry entry
#:execute execution
#:on-exit exit]) → state?
  name : symbol?
  kind : (or/c 'start 'normal 'final)
  entry : (-> machine-execution? void?) = no-behavior
  execution : (-> machine-execution? void?) = no-behavior
  exit : (-> machine-execution? void?) = no-behavior

Construct a new state.

procedure
(make-transition source-name
target-name
[ internal
#:on-event trigger-event
#:guard guard
#:execute effect]) → transition?
  source-name : symbol?
  target-name : symbol?
  internal : boolean? = #f
  trigger-event : (or/c #f symbol?) = #f
  guard : (-> machine-execution? symbol? boolean?) = no-guard
  effect : (-> machine-execution? void?) = no-behavior

Construct a new transition, note that by using symbols for the sourvce-name and target-name we do not need to reference state instances directly and the construction is considerably easier to read/understand.

Example:

> (make-state-machine
   'first-fsm
   (list (make-state 'hello 'start)
         (make-state 'goodbye 'final))
   (list (make-transition 'hello 'goodbye #:on-event 'wake)))
#<state-machine>

value
no-behavior : (-> machine-execution? void?)

A default behavior implementation that does nothing.

value
no-guard : (-> machine-execution? transition? boolean?)

A default guard implementation that simply returns #t.

1.3 Execution🔗ℹ

procedure
(make-machine-execution from-machine
[ reporter]) → machine-execution?
from-machine : state-machine?
reporter : (or/c #f (-> machine-history-event? void?)) = #f

Construct a new machine-execution using from-machine as the definition. The returned execution will be in the 'created condition.

procedure
(machine-execution-start exec) → machine-execution?
exec : machine-execution?

Transition to the start state of the machine. The returned execution will be in the 'active condition.

procedure
(machine-execution-complete? exec) → boolean?
exec : machine-execution?

Returns #t if the execution is in the 'completed condition.

procedure
(handle-event exec event) → machine-execution?
exec : machine-execution?
event : symbol?

Consume the event and determine the next action. The returned execution will be in either the 'active, 'in-error, or 'completed condition.

procedure
(complete-current-state exec) → machine-execution?
exec : machine-execution?

Complete the current state and determine the next action. The returned execution will be in either the 'active, 'in-error, or 'completed condition.

1	Module behavior/ fsm
2	Module behavior/ markov-chain
3	Module behavior/ petri-net
4	Module behavior/ reporter