Implementing state machine behaviour using F#

State Machine simulation is one of the most common practices. It is not a coding-oriented design pattern, but it is system-oriented, often used to model cases for the business use. Using F# and domain driven design, we can not only define different types to represent the state, but we can also define behaviour as functions for various state transition rules.

For example, given a current state X, a state machine will define what new state X can change to, and what events can cause the state changes to occur. i.e. Current State -> Event -> New State

In our scenario, we have various states and transition events of a process in an operating system viz.

Copy 
1module Process
2    module StateMachine
3        type ProcessState =
4            | New
5            | Ready
6            | Running
7            | Waiting
8            | Terminated
9        
10        type ProcessEvent
11            | Admit
12            | Interrupt
13            | SchedulerDispatch
14            | IOEventWait
15            | IOEventCompletion
16            | Exit

Let us create a state machine function that can provide the transition based on current state and event. It will be a simple pattern matching to identify the new state.

Copy 
1let stateMachine (state, event) =
2    match state, event with
3    | New, Admit
4        -> Ready
5    | Ready, SchedulerDispatch
6        -> Running
7    | Running, IOEventWait
8        -> Waiting
9    | Running, Exit
10        -> Terminated
11    | Running, Interrupt
12        -> Ready
13    | Waiting, IOEventCompletion
14        -> Ready
15    | _
16        -> failwith  "Invalid Transition"

The above function can provide the behaviour for transition, but it has an issue, it will allow us to raise an event which might not be permitted by the state such as ADMIT event when the current state is WAITING. This can lead to a run time exception “Invalid Transition”. Thus a better way to provide the implementation for the above code is to replace with the following code. First, we create two helper function, stateTransition that will take event as an input to return the future state and getEventForState that will take the current state as an input to return the collection of possible events it can raise.

Copy 
1let private stateTransition event =
2    match event with
3    | Admit
4        -> Ready
5    | SchedulerDispatch
6        -> Running
7    | IOEventWait
8        -> Waiting
9    | Exit
10        -> Terminated
11    | Interrupt
12        -> Ready
13    | IOEventCompletion
14        -> ready
15        
16let private getEventForState state =
17    match state with
18    | New
19        ->[|Admit|]
20    | Ready
21        -> [|SchedulerDispatch|]
22    | Running
23        -> [|IOEventWait, Interrupt, Exit|]
24    | Waiting
25        -> [|IOEventCompletion|]

Now we need a circular reference type that can be used to store the allowed event record with an identification property and a method function that takes a unit as an input to returns future allowed events with current state details.

Copy 
1type AllowedEvent = 
2        {
3                EventInfo : ProcessEvent
4                RaiseEvent : unit -> EventResult
5        }
6and EventResult
7        {
8                CurrentState : ProcessState
9                AllowedEvents : AllowedEvent array
10        }

In the above definition, AllowedEvent references EventResult in RaiseEvent and EventResult references AllowedEvent in AllowedEvents. Please note that both functions stateTransition and getEventForState are private to module.

Let us implement the final state machine function

Copy 
1let rec stateMachine event =
2    let newState = stateTransition event
3    let newEvents = getEventForState newState
4    {
5        CurrentState = newState
6        AllowedEvents = 
7            newEvents
8            |> Array.map (fun e ->
9                let f() = stateMachine e
10                {
11                    EventInfo = e
12                    RaiseEvent = f
13                })
14    }

This is recursive function as it is self referencing and it returns EventResult type. The stateMachine function takes the event as an input to calculate newState and newEvent using helper methods and then creates EventResult. The AllowedEvent array create a special map of functions, to be called at runtime for transitioning between states from outside the module. By implementing above code we can utilise the result from each RaiseEvent to traverse further.

To complete the the above implementation we would provide a method to be accessed publicly and it will give us initial result of the state machine.

Copy 
1let init() = stateMachine New

To test the implementation, we can now proceed as

Copy 
1let result = init()
2let result1 = result.AllowedEvents.[0].raiseEvent()

This methodology ensures that every time we raise an event, it is a valid event.