Finite State Machine interpreter

1. Introduction

This script implements an interpreter for stack-based finite state machines. A FSM is defined by a simple dialect where each state is a REBOL block. The interpreter will process events and change state according to the dialect. It can be used in a wide range of cases where stateful processing of asynchronous events is desired.

2. Overview

3. The process-event function

Processes one event with the current state. The return value for this function is undefined (as you see, the current implementation will return true due to the until loop).

An event can be a value of types any-string! or word!, although it's easy to extend the code so that it works with other types, if you need it.

The until loop is needed for the continue and override directives. See 〈The interpreter's parse rules〉.

3.1 process-event's locals

3.2 The FSM prototype object

We need to store the current state. The state word is used to refer to the current state block. event and data are used to refer to the current event and its associated data (if any). initial-state is the initial state of the state machine, and is specified when calling make-fsm.

For debugging, it is possible to set tracing to true; you'll get a step-by-step trace of the state machine.

3.3 Process the event event

Processing one event works this way: we use find to search for event in the state block. (This is ok because we assume that events cannot be of type word! (word! events are converted to set-word!) or paren!, and the rest of the dialect only uses words and parens.) If the current state does not handle this event (event is not found), we search for default: which is the default handling for events for this state. If none of them is found, the event is just ignored; otherwise, the directives for the event are processed by the interpreter, using parse.

3.4 Example of state blocks

Let's first make an example, so that it will be easier to understand 〈The interpreter's parse rules〉. Each state is represented by a state block. This block defines how events are handled in that state. Event values are listed in the block, and each event (or group of events) is followed by directives. The list of directives for an event can be broken into two parts, both optional (but at least one of them must be specified - otherwise you shouldn't list the event in the block at all): an action (expressed as a paren, containing arbitrary REBOL code) and some state change directives.

In this example, state-one defines only an action for event1. For event2 we only define a state change (going to state-two). For event6 we define both an action and a state change.

State change directives can be broken into two parts too: an optional continue or override directive, followed by a state change. A state change can be: the return directive, which goes back to the previous state (in the initial state, nothing happens); the rewind? directive, which we'll discuss later; or a word referring to a state block, which means switching to that state. In this last case, the word can be followed by a paren!, that is similar to the action paren for the event, but is executed after the new state uses return to return to this state.

In this example, for event3 or event4, we define an action, and a state change with a return action. This means that if we receive event3 or event4 while in state-one, the action (print "Got event3 or event4") is executed, then the current state in changed to state-two. When state-two uses a return directive (for example it does so when receiving the event6 event), the current state is changed back to state-one and the action (print "Returned from state-two") is executed.

The continue and override directives are used to change what happens when switching to a new state. (They can be used with return and rewind? too.) Normally, a state change means that the next event will be processed by the new state; but if you use continue, then the current event is processed again by the new state (this is like "delegating" the processing of the event to another state). In this example, when event5 is encountered in state-one, the state is changed to state-two and event5 is processed again, which causes to print "Got event5 in state-two".

override is very similar, except that a new event is generated and then processed by the new state. override strange-event generates the event strange-event, so in the default case for state-one a strange-event is generated, the state is changed to state-two, and strange-event is processed (which causes to print "Unhandled event in state-one, now in state-two").

Please see 〈The interpreter's parse rules〉 for more details.

3.5 The interpreter's parse rules

These rules are used to parse the state block already positioned at the event to be processed (result of the find function). Since multiple events can share the same directives, we have one or more event specifications followed by an optional action paren, followed by optional state change directives.

Note that the return-state helper function is used to return to the previous state, and goto-state is used to go to a new state. Also note that you can specify an integer for return to return to the n-th previous state, i.e. 2 return calls the return-state function twice.

We need to add a couple words to the list of locals:

3.5.1 Rule for the rewind? directive

We're going to discuss the rewind? directive separately, because it's a little more complicated.

The rewind? directive attempts to rewind the state stack up to one of the specified states (it must be followed by one or more words referring to state blocks); each state is attempted in the given order; the directive is ignored (i.e. no state change happens) if none of the given states is on the stack (this is the reason for the question mark in the name).

So, this is a conditional state change directive, because the state is only changed if one of the listed states is found in the stack. The rewind-state helper function is called with the listed target states in order; it will return true if the state was found and the stack was successfully rewound back to it (i.e. the required number of returns were performed - return actions are evaluated normally too). In this case, we don't need to attempt with other states. You can think of rewind? as of a sort of conditional throw.

3.6 Helper functions

In the above code we used three helper functions goto-state, return-state and rewind-state.

goto-state changes the current state, pushing the old state and (if given) a return action into the stack.

return-state returns the state machine to the previous state; it gets the previous state and the return action from the stack, changes state to the previous state and does the return action. If the state stack is empty, it goes to the initial state.

rewind-state rewinds the stack up to a specified state, if it is on the stack; if the state is not on the stack, nothing is changed and the function returns false. Otherwise true is returned.

3.6.1 Additional variables for FSM objects

4. The make-fsm function

make-fsm creates a FSM object that can be used with process-event and reset-fsm.

The object is made from fsm-proto with the given spec. The current state is set to initial-state and state-stack is set to an empty block.

5. The reset-fsm function

Resets the state machine object. Gets the state machine back to the initial state gracefully (rewinding the stack); with the /only refinement, a "hard" reset is performed, that is, we only reset the state to initial-state, without performing a stack rewind.

6. The inherit function

inherit is just a handy shortcut that can be used when creating state blocks that are similar to each other. We make use of the fact that the order of rules in the state blocks is significant; we just append the rules of the "parent" state to the "child" state, so that any rule in child takes precedence, and otherwise the state behaves just like parent does. Please note that child is modified, as this is not a problem in the most common usage.

7. Example usage

To use the interpreter you just make a new FSM object with make-fsm, setting an initial-state, then call process-event for all your events, and when finished call reset-fsm.

In this example we could set my-fsm/tracing: yes to trace the state machine step-by-step for debugging.