Finite state machine
A Finite state machine (FSM) is computational abstraction which maps a finite number of states to other states within the same set, via transitions. An FSM can only be in one state at any given moment. Transitions can either be explicit or implicit; explicit transitions are triggered by an input signal and implicit transitions by the internal state of the system (that is, the current state). Implicit transitions thus represent "automatic" or sequenced states that are generally processed between explicit transitions (although they can also be used to provide an optional path when no valid transition exists for a given input signal).
- Example
Consider the model of a simple vending machine. The machine is initially in the "ready" state, which maps to exactly two states in the following way:
- ready -> deposit -> waiting
- ready -> quit -> exit
The variables in bold-face represent transitions. Any input signal not corresponding to one of those transitions can either trigger an error or be ignored. Otherwise, the current state is updated and the process is repeated. If, for example, a deposit input signal is encountered, the FSM will move to the "waiting" state, which defines these transitions:
- waiting -> select -> dispense
- waiting -> refund -> refunding
The "dispense" state defines only one transition:
- dispense -> remove -> ready
Note, however, that in this example the "refunding" state doesn't actually require input in order to move to the "ready" state, so an implicit transition is defined as such:
- refunding -> ready
- Task
Implement a finite state machine which handles both explicit and implicit transitions. Then demonstrate an example which models some real-world process.
- See also
- Computers Without Memory (Finite State Automata), A Computerphile Video.
11l
<lang 11l>V states = [‘ready’ =
(‘Machine ready: (d)eposit, or (q)uit?’,
[String(‘d’), ‘q’]),
‘waiting’ =
(‘Machine waiting: (s)elect, or (r)efund?’,
[String(‘s’), ‘r’]),
‘dispense’ =
(‘Machine dispensing: please (r)emove product’,
[String(‘r’)]),
‘refunding’ =
(‘Refunding money’,
[String]())
]
V transitions = [‘ready’ =
[String(‘d’) = ‘waiting’,
String(‘q’) = ‘exit’],
‘waiting’ =
[String(‘s’) = ‘dispense’,
String(‘r’) = ‘refunding’],
‘dispense’ =
[String(‘r’) = ‘ready’],
‘refunding’ =
[‘’ = ‘ready’]]
F Acceptor(prompt, valids)
I valids.empty
print(prompt)
R ‘’
E
L
V resp = input(prompt)[0].lowercase()
I resp C valids
R String(resp)
F finite_state_machine(initial_state, exit_state)
V next_state = initial_state
V current_state = :states[next_state]
L
V response = Acceptor(current_state[0], current_state[1])
I response == exit_state
L.break
next_state = :transitions[next_state][response]
current_state = :states[next_state]
finite_state_machine(‘ready’, ‘q’)</lang>
- Output:
Machine ready: (d)eposit, or (q)uit?d Machine waiting: (s)elect, or (r)efund?s Machine dispensing: please (r)emove productr Machine ready: (d)eposit, or (q)uit?d Machine waiting: (s)elect, or (r)efund?r Refunding money Machine ready: (d)eposit, or (q)uit?q
BASIC
Commodore BASIC
<lang basic> 10 REM FINITE STATE MACHINE 20 LET MS=1: REM MACHINE STATE 30 REM 1=READY, 2=WAITING, 3=DISPENSE, 4=REFUND, 5=QUIT 40 : 50 REM MAIN LOOP 60 ON MS GOSUB 1000,2000,3000,4000,5000 70 GOTO 50 80: 1000 REM READY 1010 PRINT "MACHINE IS READY" 1020 PRINT "PRESS D-ISPENSE OR Q-UIT" 1030 INPUT KP$ 1040 IF KP$ = "D" THEN MS=2: GOTO 1070 1050 IF KP$ = "Q" THEN MS=5: GOTO 1070 1060 GOTO 1030 1070 RETURN 1080 : 2000 REM WAITING 2010 PRINT "MACHINE IS WAITING" 2020 PRINT "PRESS S-ELECT OR R-EFUND" 2030 INPUT KP$ 2040 IF KP$ = "S" THEN MS=3: GOTO 2070 2050 IF KP$ = "R" THEN MS=4: GOTO 2070 2060 GOTO 2030 2070 RETURN 2080 : 3000 REM DISPENSE 3010 PRINT "MACHINE DISPENSE" 3020 PRINT "PRESS C-OLLECTED PRODUCT." 3030 INPUT KP$ 3040 IF KP$ = "C" THEN MS=1: GOTO 3060 3050 GOTO 3030 3060 RETURN 3070 : 4000 REM REFUND 4010 PRINT "MACHINE IS REFUND" 4020 PRINT "PRESS C-OLLECTED REFUND." 4030 INPUT KP$ 4040 IF KP$ = "C" THEN MS=1: GOTO 4060 4050 GOTO 430 4060 RETURN 4070 : 5000 REM QUIT 5010 PRINT "MACHINE IS SHUTDOWN" 5020 END </lang>
Sinclair ZX81 BASIC
Works with 1k of RAM.
There doesn't seem much point, in BASIC, implementing a 'general' FSM that would accept a list of states and transition rules as parameters, because an unstructured BASIC program in essence already is that list.
Within each state, if the transition is implicit we just GOTO the next state. If it is explicit, we loop until the user presses a key corresponding to a valid transition. Invalid inputs are ignored.
The line 100 GOTO 110 is superfluous, because it would go there anyway; but it is worth including it in case we wanted to modify the program later and transition somewhere else out of the dispense state.
Note that the program uses no variables and makes no use of the return stack: all the state is expressed in the (so to speak) state.
<lang basic> 10 PRINT "PRESS D(EPOSIT) OR Q(UIT)"
20 IF INKEY$="D" THEN GOTO 50 30 IF INKEY$="Q" THEN STOP 40 GOTO 20 50 PRINT "PRESS S(ELECT) OR R(EFUND)" 60 IF INKEY$="S" THEN GOTO 90 70 IF INKEY$="R" THEN GOTO 140 80 GOTO 60 90 PRINT "DISPENSED"
100 GOTO 110 110 PRINT "PRESS R(EMOVE)" 120 IF INKEY$="R" THEN GOTO 10 130 GOTO 120 140 PRINT "REFUNDED" 150 GOTO 10</lang>
- Output:
It will be seen that the user has pressed, in order, D, R, D, S, R, and Q.
PRESS D(EPOSIT) OR Q(UIT) PRESS S(ELECT) OR R(EFUND) REFUNDED PRESS D(EPOSIT) OR Q(UIT) PRESS S(ELECT) OR R(EFUND) DISPENSED PRESS R(EMOVE) PRESS D(EPOSIT) OR Q(UIT)
C
Here is a manually-constructed table-driven finite state machine that is fairly general and could be adapted to different applications. <lang C>
- include <stdio.h>
- include <ctype.h>
- include <stdlib.h>
int main(int argc, char **argv) {
typedef enum State { READY, WAITING, REFUND, DISPENSE, COLLECT, QUIT } State;
typedef struct statechange {
const int in;
const State out;
} statechange;
- define MAXINPUTS 3
typedef struct FSM {
const State state;
void (*Action)(void);
const statechange table[MAXINPUTS]; // would be nice if could be [] ...
} FSM;
char str[10];
void Ready(void) { fprintf(stderr, "\nMachine is READY. (D)eposit or (Q)uit :"); scanf("%s", str); }
void Waiting(void) { fprintf(stderr, "(S)elect product or choose to (R)efund :"); scanf("%s", str); }
void Refund(void) { fprintf(stderr, "Please collect refund.\n"); }
void Dispense(void) { fprintf(stderr, "Dispensing product...\n"); }
void Collect(void) { fprintf(stderr, "Please (C)ollect product. :"); scanf("%s", str); }
void Quit(void) { fprintf(stderr, "Thank you, shutting down now.\n"); exit(0); }
const FSM fsm[] = {
{ READY, &Ready, {{'D', WAITING}, {'Q', QUIT }, {-1, READY} }},
{ WAITING, &Waiting, {{'S', DISPENSE}, {'R', REFUND}, {-1, WAITING} }},
{ REFUND, &Refund, {{ -1, READY} }},
{ DISPENSE, &Dispense, {{ -1, COLLECT} }},
{ COLLECT, &Collect, {{'C', READY}, { -1, COLLECT } }},
{ QUIT, &Quit, {{ -1, QUIT} }},
};
int each; State state = READY;
for (;;) {
fsm[state].Action();
each = 0;
while (!( ((fsm[state].table[each].in == -1)
// -1 comes last and is catchall: exit, or loop to self, on no valid input.
|| (isalpha(str[0]) && fsm[state].table[each].in == toupper(str[0]) )))) each++;
state = fsm[state].table[each].out;
}
return 0;
} </lang> Machine simulation :
C:\rosettaCode>fsm.exe Machine is READY. (D)eposit or (Q)uit :D (S)elect product or choose to (R)efund :S Dispensing product... Please (C)ollect product. :C Machine is READY. (D)eposit or (Q)uit :D (S)elect product or choose to (R)efund :R Please collect refund. Machine is READY. (D)eposit or (Q)uit :Q Thank you, shutting down now.
C++
<lang C>
- include <map>
template <typename State, typename Transition = State> class finite_state_machine { protected: State current; std::map<State, std::map<Transition, State>> database; public: finite_state_machine() { set(State()); } void set(State const& state) { current = state; } State get() const { return current; } void clear() { database.clear(); } void add(State const& state, Transition const& transition, State const& next) { database[state][transition] = next; } /* Add a state which is also it's own transition (and thus a link in a chain of sequences)
- /
void add(State const& state_and_transition, State const& next) { add(state_and_transition, state_and_transition, next); } bool process(Transition const& transition) { auto const& transitions = database[current], found = transitions.find(transition); if(found == transitions.end()) return false; auto const& next = found->second; set(next); return true; } /* Process so-called "automatic transitions" (ie: sequencing)
- /
bool process() { return process(get()); } /* A set of utility functions that may be helpful for displaying valid transitions to the user, etc...
- /
template <typename PushBackContainer> bool get_valid_transitions(State const& state, PushBackContainer& container) { container.clear(); auto const& found = database.find(state); if(found == database.end()) return false; auto const& transitions = found->second; if(transitions.size() == 0) return false; for(auto const& iterator : transitions) { auto const& transition = iterator.first; container.push_back(transition); } return true; } template <typename Container> bool get_valid_transitions(Container& container) { return get_valid_transitions(get(), container); } };
/* Example usage: a simple vending machine
- /
- include <string>
- include <vector>
- include <iostream>
using namespace std; void print(string const& message) { cout << message << endl; } int main() { finite_state_machine<string> machine; machine.add("ready", "quit", "exit"); machine.add("ready", "deposit", "waiting"); machine.add("waiting", "select", "dispense"); machine.add("waiting", "refund", "refunding"); machine.add("dispense", "remove", "ready"); machine.add("refunding", "ready"); machine.set("ready"); for(;;) { string state = machine.get(); if(state == "ready") print("Please deposit coins."); else if(state == "waiting") print("Please select a product."); else if(state == "dispense") print("Dispensed...please remove product from tray."); else if(state == "refunding") print("Refunding money..."); else if(state == "exit") break; else print("Internal error: unaccounted state '" + state + "'!"); /* Handle "automatic" transitions */ if(machine.process()) continue; vector<string> transitions; machine.get_valid_transitions(transitions); string options; for(auto const& transition : transitions) { if(!options.empty()) options += ", "; options += transition; } print("[" + state + "] Input the next transition (" + options + "): "); string transition; cout << " > "; cin >> transition; if(!machine.process(transition)) print( "Error: invalid transition!"); } } </lang>
- Output:
Please deposit coins. [ready] Enter the next transition (deposit, quit): > deposit Please select a product. [waiting] Enter the next transition (refund, select): > refund Refunding money... Please deposit coins. [ready] Enter the next transition (deposit, quit): > deposit Please select a product. [waiting] Enter the next transition (refund, select): > select Dispensed...please remove product from tray. [dispense] Enter the next transition (remove): > remove Please deposit coins. [ready] Enter the next transition (deposit, quit): > quit
D
<lang d>import std.conv; import std.range; import std.stdio; import std.string;
enum State {
READY, WAITING, EXIT, DISPENSE, REFUNDING,
}
void fsm() {
writeln("PLease enter your option when prompted");
writeln("(any characters after the first will be ignored)");
auto state = State.READY;
string trans;
while (true) {
final switch (state) {
case State.READY:
do {
write("(D)ispense or (Q)uit : ");
trans = readln().toLower.take(1).to!string;
} while (trans != "d" && trans != "q");
if (trans == "d") {
state = State.WAITING;
} else {
state = State.EXIT;
}
break;
case State.WAITING:
writeln("OK, put your money in the slot");
do {
write("(S)elect product or choose a (R)efund : ");
trans = readln().toLower.take(1).to!string;
} while (trans != "s" && trans != "r");
if (trans == "s") {
state = State.DISPENSE;
} else {
state = State.REFUNDING;
}
break;
case State.DISPENSE:
do {
write("(R)emove product : ");
trans = readln().toLower.take(1).to!string;
} while (trans != "r");
state = State.READY;
break;
case State.REFUNDING:
writeln("OK, refunding your money");
state = State.READY;
break;
case State.EXIT:
writeln("OK, quitting");
return;
}
}
}
void main() {
fsm();
}</lang>
Delphi
<lang Delphi> program Finite_state_machine;
{$APPTYPE CONSOLE}
type
TState = (stReady, stWaiting, stDispense, stRefunding, stExit);
var
state: TState = stReady;
procedure fsm(); var
line: string; option: char;
begin
Writeln('Please enter your option when prompted');
Writeln('(any characters after the first will be ignored)'#10);
state := stReady;
repeat
case state of
stReady:
begin
Writeln('(D)ispense or (Q)uit : ');
Readln(line);
if line = then
Continue;
option := UpCase(line[1]);
case option of
'D':
state := stWaiting;
'Q':
state := stExit;
end;
end;
stWaiting:
begin
Writeln('OK, put your money in the slot');
while state = stWaiting do
begin
Writeln('(S)elect product or choose a (R)efund : ');
Readln(line);
if line = then
Continue;
option := UpCase(line[1]);
case option of
'S':
state := stDispense;
'R':
state := stRefunding;
end;
end;
end;
stDispense:
begin
while state = stDispense do
begin
Writeln('(R)emove product : '#10);
Readln(line);
if line = then
Continue;
option := UpCase(line[1]);
case option of
'R':
state := stReady;
end;
end;
end;
stRefunding:
begin
Writeln('OK, refunding your money');
state := stReady;
end;
stExit:
begin
Writeln('OK, quitting');
state := stExit;
end;
end;
until state = stExit;
end;
begin
fsm;
end.</lang>
FreeBASIC
<lang freebasic>Enum states
READY WAITING DISPENSE REFUND QUIT
End Enum '-- (or just use strings if you prefer)
Dim As states state = READY Dim As String KBD = " " Do
Print KBD
Select Case state
Case READY
Print "Machine is READY. (D)eposit or (Q)uit : ";
Do
Do: KBD = Ucase(Inkey): Loop While KBD = ""
If KBD = "D" Then state = WAITING : Exit Do
If KBD = "Q" Then state = QUIT : Exit Do
Loop
Case WAITING
Print "(S)elect product or choose to (R)efund : ";
Do
Do: KBD = Ucase(Inkey): Loop While KBD = ""
If KBD = "S" Then state = DISPENSE : Exit Do
If KBD = "R" Then state = REFUND : Exit Do
Loop
Case DISPENSE
Print "Dispensing product... ";
Print "Please (C)ollect product. : ";
Do
Do: KBD = Ucase(Inkey): Loop While KBD = ""
If KBD = "C" Then state = READY : Exit Do
Loop
Case REFUND
Print "Please collect refund."
state = READY
KBD = " "
Case QUIT
Print !"Thank you, shuttingwn now.\n"
Exit Do
End Select
Loop Sleep</lang>
- Output:
Igual que la entrada de Phix.
Go
<lang go>package main
import (
"bufio" "fmt" "log" "os" "strings"
)
type state int
const (
ready state = iota waiting exit dispense refunding
)
func check(err error) {
if err != nil {
log.Fatal(err)
}
}
func fsm() {
fmt.Println("Please enter your option when prompted")
fmt.Println("(any characters after the first will be ignored)")
state := ready
var trans string
scanner := bufio.NewScanner(os.Stdin)
for {
switch state {
case ready:
for {
fmt.Print("\n(D)ispense or (Q)uit : ")
scanner.Scan()
trans = scanner.Text()
check(scanner.Err())
if len(trans) == 0 {
continue
}
option := strings.ToLower(trans)[0]
if option == 'd' {
state = waiting
break
} else if option == 'q' {
state = exit
break
}
}
case waiting:
fmt.Println("OK, put your money in the slot")
for {
fmt.Print("(S)elect product or choose a (R)efund : ")
scanner.Scan()
trans = scanner.Text()
check(scanner.Err())
if len(trans) == 0 {
continue
}
option := strings.ToLower(trans)[0]
if option == 's' {
state = dispense
break
} else if option == 'r' {
state = refunding
break
}
}
case dispense:
for {
fmt.Print("(R)emove product : ")
scanner.Scan()
trans = scanner.Text()
check(scanner.Err())
if len(trans) == 0 {
continue
}
option := strings.ToLower(trans)[0]
if option == 'r' {
state = ready
break
}
}
case refunding:
// no transitions defined
fmt.Println("OK, refunding your money")
state = ready
case exit:
fmt.Println("OK, quitting")
return
}
}
}
func main() {
fsm()
}</lang>
- Output:
Sample input/output:
Please enter your option when prompted (any characters after the first will be ignored) (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : s (R)emove product : r (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : r OK, refunding your money (D)ispense or (Q)uit : q OK, quitting
Groovy
<lang groovy>class FiniteStateMachine {
private enum State {
Ready(true, "Deposit", "Quit"),
Waiting(true, "Select", "Refund"),
Dispensing(true, "Remove"),
Refunding(false, "Refunding"),
Exiting(false, "Quiting");
State(boolean exp, String... input) {
inputs = Arrays.asList(input);
explicit = exp
}
State nextState(String input, State current) {
if (inputs.contains(input)) {
return map.getOrDefault(input, current)
}
return current
}
final List<String> inputs
final static Map<String, State> map = new HashMap<>()
final boolean explicit
static {
map.put("Deposit", Waiting)
map.put("Quit", Exiting)
map.put("Select", Dispensing)
map.put("Refund", Refunding)
map.put("Remove", Ready)
map.put("Refunding", Ready)
}
}
static void main(String[] args) {
Scanner sc = new Scanner(System.in)
State state = State.Ready
while (state != State.Exiting) {
println(state.inputs)
if (state.explicit){
print("> ")
state = state.nextState(sc.nextLine().trim(), state)
} else {
state = state.nextState(state.inputs.get(0), state)
}
}
}
}</lang>
Haskell
<lang haskell>import System.Exit import Data.Maybe import Control.Monad import Data.List import System.IO
type Name = String type Sequence = String type State = String
data Trigger = Trigger { name :: Name
, tseq :: Sequence } deriving (Eq)
instance Show Trigger where
show (Trigger name tseq) = name ++ "(" ++ tseq ++ ")"
data Transition = Implicit { start :: State
, end :: State }
| Explicit { start :: State
, trigger :: Trigger
, end :: State }
findEndState :: Sequence -> [(Trigger, State)] -> Maybe State findEndState sequence lst = if (isJust pair)
then snd <$> pair
else Nothing
where
pair = find (\t -> (tseq . fst) t == sequence) lst
findRelevantTransitions :: State -> [Transition] -> [Transition] findRelevantTransitions state transitions = filter (\t -> state == start t) transitions
findImplicitTransition :: [Transition] -> Maybe Transition findImplicitTransition [] = Nothing findImplicitTransition (transition@(Implicit _ _):xs) = Just transition findImplicitTransition (x:xs) = findImplicitTransition xs
runFSM :: State -> [Transition] -> [State] -> IO () runFSM state transitions finishStates = do
putStrLn $ "State: " ++ state
when (state `elem` finishStates) $ do
putStrLn "Exiting.."
exitWith ExitSuccess
let relTransitions = findRelevantTransitions state transitions
let implTransition = findImplicitTransition relTransitions
when (isJust implTransition) $ do
putStrLn "Implicit transition"
runFSM (end $ fromJust implTransition) transitions finishStates
let triggers = map (\t -> (trigger t, end t)) relTransitions
handleExplicitTransition triggers
where handleExplicitTransition triggers = do
let prompt = (intercalate " or " (map (show . fst) triggers)) ++ ":"
putStr prompt
resp <- getLine
let endState = findEndState resp triggers
case endState of
(Just e) -> runFSM e transitions finishStates
Nothing -> putStrLn "invalid input" >> handleExplicitTransition triggers
main = do
hSetBuffering stdout $ BlockBuffering $ Just 1 runFSM initialState transitions finishStates
initialState = "Ready" transitions = [ Explicit "Ready" (Trigger "Deposit" "d") "Waiting"
, Explicit "Ready" (Trigger "Quit" "q") "Exit"
, Explicit "Waiting" (Trigger "Select" "s") "Dispense"
, Explicit "Waiting" (Trigger "Refund" "r") "Refunding"
, Explicit "Dispense" (Trigger "Remove" "rm") "Ready"
, Implicit "Refunding" "Ready" ]
finishStates = ["Exit"] </lang>
J
This seems to be what the current draft task asks for:
<lang>NB. FSM builder: explicit=: {{
states=: ~. states,x;y
transitions=: ~. transitions,<m
FSM=: y S (<x S, m T)} (states ,&# transitions){.!._ FSM
EMPTY
}} implicit=: explicit start=: {{ implicit y [current=: 0 [transitions=: states=: <,FSM=: EMPTY }}
NB. FSM utilities S=: state=: {{ states i.<m }} T=: transition=: {{transitions i.<m }} N=: next=: {{
try. 1: current=: ([ {&states) current next y catch. 0 end.
(<x, y transition) { FSM
}} Snm=: statename=: {{ ;:inv m{states }} Tnm=: transitionname=: {{ ;:inv m{transitions }} implicits=: Template:R=.'' while. next '' do. r=.r, current end.</lang>
With the above implementation, the task example would look like:
<lang J>NB. task example FSM: start 'ready' 'ready' 'deposit'explicit 'waiting' 'ready' 'quit'explicit 'exit' 'waiting' 'select'explicit 'dispense' 'waiting' 'refund'explicit 'refunding' 'dispense' 'remove'explicit 'ready' 'refunding' implicit 'ready'
example=: {{
current=: 0 machine 'deposit' machine 'select' machine 'remove' machine 'deposit' machine 'refund' machine 'quit' echo 'final state: ',current statename
}}
machine=: {{
echo 'state: ',current statename echo 'transition: ',y next y i=. implicits if. #i do. echo 'implicit transition to: ',i statename end.
}}</lang>
Java
<lang java>import java.util.*;
public class FiniteStateMachine {
private enum State {
Ready(true, "Deposit", "Quit"),
Waiting(true, "Select", "Refund"),
Dispensing(true, "Remove"),
Refunding(false, "Refunding"),
Exiting(false, "Quiting");
State(boolean exp, String... in) {
inputs = Arrays.asList(in);
explicit = exp;
}
State nextState(String input, State current) {
if (inputs.contains(input)) {
return map.getOrDefault(input, current);
}
return current;
}
final List<String> inputs;
final static Map<String, State> map = new HashMap<>();
final boolean explicit;
static {
map.put("Deposit", State.Waiting);
map.put("Quit", State.Exiting);
map.put("Select", State.Dispensing);
map.put("Refund", State.Refunding);
map.put("Remove", State.Ready);
map.put("Refunding", State.Ready);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
State state = State.Ready;
while (state != State.Exiting) {
System.out.println(state.inputs);
if (state.explicit){
System.out.print("> ");
state = state.nextState(sc.nextLine().trim(), state);
} else {
state = state.nextState(state.inputs.get(0), state);
}
}
}
}</lang>
[Deposit, Quit] > Deposit [Select, Refund] > Refund [Refunding] [Deposit, Quit] > Deposit [Select, Refund] > Quit [Select, Refund] > Select [Remove] > Remove [Deposit, Quit] > Quit
JavaScript
On browser using blocking window methods
<lang JavaScript>//States var states = [{
'name': 'Ready',
'initial': true,
'events': {
'Deposit': 'Waiting',
'Quit': 'Exiting',
}
}, {
'name': 'Waiting',
'events': {
'Select': 'Dispensing',
'Refund': 'Refunding'
}
}, {
'name': 'Dispensing',
'events': {
'Remove': 'Ready'
}
}, {
'name': 'Refunding',
'events': {
getReady: 'Ready'
}
}, {
'name': 'Exiting',
'events': {}
}];
function StateMachine(states) {
this.states = states;
this.indexes = {};
for (var i = 0; i < this.states.length; i++) {
this.indexes[this.states[i].name] = i;
if (this.states[i].initial) {
this.currentState = this.states[i];
}
}
}; StateMachine.prototype.consumeEvent = function(e) {
if (this.currentState.events[e]) {
this.currentState = this.states[this.indexes[this.currentState.events[e]]];
}
} StateMachine.prototype.getStatus = function() {
return this.currentState.name;
} var fsm = new StateMachine(states); var s, currentButtons, answer; while ((s = fsm.getStatus()) !== "Exiting") {
switch (s) {
case "Refunding":
window.alert('Refunding');
fsm.consumeEvent("getReady")
break;
case "Dispensing":
case "Waiting":
case "Ready":
currentButtons = Object.keys(fsm.states[fsm.indexes[s]].events)
answer = window.prompt(currentButtons.join(' ') + '?');
answer = currentButtons.find(function(key) {
return key.match(new RegExp('^' + answer, 'i'))
});
if (answer) {
fsm.consumeEvent(answer);
}
}
} </lang>
Julia
<lang julia>abstract type State end
struct Ready <: State
transitiontable::Dict
implicit::Union{State, Nothing}
prompt::String
end
struct Waiting <: State
transitiontable::Dict
implicit::Union{State, Nothing}
prompt::String
end
struct Dispense <: State
transitiontable::Dict
implicit::Union{State, Nothing}
prompt::String
end
struct Refunding <: State
transitiontable::Dict
implicit::Union{State, Nothing}
prompt::String
end
struct Exit <: State
transitiontable::Dict
implicit::Union{State, Nothing}
prompt::String
end
Ready() = Ready(Dict("deposit" => Waiting, "quit" => Exit), nothing, "Vending machine is ready.") Waiting() = Waiting(Dict("select" => Dispense, "refund" => Refunding), nothing, "Waiting with funds.") Dispense() = Dispense(Dict("remove" => Ready), nothing, "Thank you! Product dispensed.") Refunding() = Refunding(Dict(), Ready(), "Please take refund.") Exit() = Exit(Dict(), nothing, "Halting.")
makeinstance(Ready) = Ready() makeinstance(Waiting) = Waiting() makeinstance(Dispense) = Dispense() makeinstance(Refunding) = Refunding() makeinstance(Exit) = Exit()
function queryprompt(query, typ)
print(query, ": ")
entry = uppercase(strip(readline(stdin)))
return (typ <: Integer) ? parse(Int, entry) :
(typ <: Vector) ? map(x -> parse(Int, x), split(entry, r"\s+")) :
entry
end
function promptinput(state)
choices = [(s[1], s[2:end]) for s in keys(state.transitiontable)]
print(state.prompt, join([" ($(w[1]))$(w[2])" for w in choices], ","), ": ")
while true
choice = readline()
if !isempty(choice) && (x = findfirst(s -> s[1] == choice[1], choices)) != nothing
return state.transitiontable[join(choices[x], "")]
end
end
end
quitting(s::State) = false quitting(s::Exit) = true
function runsim(state)
while true
if state.implicit != nothing
println(state.prompt)
state = state.implicit
elseif quitting(state)
println(state.prompt)
break
else
state = makeinstance(promptinput(state))
end
end
end
runsim(Ready())
</lang>
- Output:
Vending machine is ready. (q)uit, (d)eposit: d Waiting with funds. (s)elect, (r)efund: s Thank you! Product dispensed. (r)emove: r Vending machine is ready. (q)uit, (d)eposit: d Waiting with funds. (s)elect, (r)efund: r Please take refund. Vending machine is ready. (q)uit, (d)eposit: q Halting.
Kotlin
<lang scala>// version 1.1.51
enum class State { READY, WAITING, EXIT, DISPENSE, REFUNDING }
fun fsm() {
println("Please enter your option when prompted")
println("(any characters after the first will be ignored)")
var state = State.READY
var trans: String
while (true) {
when (state) {
State.READY -> {
do {
print("\n(D)ispense or (Q)uit : ")
trans = readLine()!!.toLowerCase().take(1)
}
while (trans != "d" && trans != "q")
state = if (trans == "d") State.WAITING else State.EXIT
}
State.WAITING -> {
println("OK, put your money in the slot")
do {
print("(S)elect product or choose a (R)efund : ")
trans = readLine()!!.toLowerCase().take(1)
}
while (trans != "s" && trans != "r")
state = if (trans == "s") State.DISPENSE else State.REFUNDING
}
State.DISPENSE -> {
do {
print("(R)emove product : ")
trans = readLine()!!.toLowerCase().take(1)
}
while (trans != "r")
state = State.READY
}
State.REFUNDING -> {
// no transitions defined
println("OK, refunding your money")
state = State.READY
}
State.EXIT -> {
println("OK, quitting")
return
}
}
}
}
fun main(args: Array<String>) {
fsm()
}</lang>
Sample input/output:
Please enter your option when prompted (any characters after the first will be ignored) (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : s (R)emove product : r (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : r OK, refunding your money (D)ispense or (Q)uit : q OK, quitting
Nim
Template:Trans Kotlin <lang Nim>import strutils
type State {.pure.} = enum Ready, Waiting, Exit, Dispense, Refunding
proc getAnswer(message: string; answers: set[char]): char =
while true: stdout.write message, ' ' stdout.flushFile result = (stdin.readLine().toLowerAscii & ' ')[0] if result in answers: return
proc fsm =
echo "Please enter your option when prompted" echo "(any characters after the first will be ignored)" var state = State.Ready
while true: case state
of State.Ready:
let trans = getAnswer("\n(D)ispense or (Q)uit :", {'d', 'q'})
state = if trans == 'd': State.Waiting else: State.Exit
of State.Waiting:
echo "OK, put your money in the slot"
let trans = getAnswer("(S)elect product or choose a (R)efund :", {'s', 'r'})
state = if trans == 's': State.Dispense else: State.Refunding
of State.Dispense:
discard getAnswer("(R)emove product :", {'r'})
state = State.Ready
of State.Refunding:
# No transitions defined.
echo "OK, refunding your money"
state = State.Ready
of State.Exit:
echo "OK, quitting"
break
fsm()</lang>
- Output:
Please enter your option when prompted (any characters after the first will be ignored) (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : s (R)emove product : r (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : r OK, refunding your money (D)ispense or (Q)uit : q OK, quitting
Ol
<lang scheme> (import (scheme read))
- finite state machine
(define (state-machine states initial-state)
(let loop ((state initial-state))
(let*((action ((states state) 'enter #f))
(process-enter (if (function? action) (action)))
(next-state (if (symbol? action) action
else
((states state) (string->symbol (symbol->string (read))) state))))
(loop next-state))))
- task states
(define states {
'ready {
'enter (lambda () (print "Write (d)eposit for deposit and (q)uit to exit."))
'd 'waiting
'deposit 'waiting
'q 'exit
'quit 'exit
}
'exit {
'enter (lambda () (halt 1))
}
'waiting {
'enter (lambda () (print "Write (s)elect for dispense or (r)efund for refund."))
's 'dispense
'select 'dispense
'r 'refunding
'refund 'refunding
}
'dispense {
'enter (lambda () (print "Write (r)emove to finish action."))
'r 'ready
'remove 'ready
}
'refunding {
'enter 'ready
}
})
- run
(state-machine states 'ready) </lang>
- Output:
Write (d)eposit for deposit and (q)uit to exit. d Write (s)elect for dispense or (r)efund for refund. f Write (s)elect for dispense or (r)efund for refund. f Write (s)elect for dispense or (r)efund for refund. s Write (r)emove to finish action. r Write (d)eposit for deposit and (q)uit to exit. d Write (s)elect for dispense or (r)efund for refund. s Write (r)emove to finish action. r Write (d)eposit for deposit and (q)uit to exit. q
Pascal
(Free Pascal 3.0.0)
This version uses fairly vanilla pascal to implement the task. I have added some confections to vend and some simple money handeling. It uses the table method to implement a FSM which is an explicit table with a dispatch loop.
<lang Pascal> {
fsm1.pas Copyright 2018 Trevor Pearson <trevor @ nb-LadyNada co uk > This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
Implementing a simulation of a vending machine using a finite state
machine. I have used the classic table based method and added a
* little extra stuff to give the routines something to do.
}
program fsm1.pas;
uses sysutils;
type
state = (Null,Ready,Waiting,Refund,Dispense,Stop); event = (Epsilon := 1,Deposit,Select,Cancel,Remove,Quit,Error);
Item = record Name : string[12]; Stock: shortint; price: currency; end;
var
amountPaid, itemPrice , changeDue: currency; I,J : integer;
machineState: state; newState: state; machineEvent: event; entry:string; vend : array[0..4,0..4] of Item; machine : array[1..7,1..7] of state;
{ The following routines implement the transitions }
procedure TOready();
var
i,j : integer;
begin
{ Always set the state of a state machine as the first thing you do
We also set the event to epsiion we can allways set it to error if there is a problem}
machineState := Ready; machineEvent := Epsilon;
{ Now do whatever we need to to transition into this state and check for errors}
Writeln(' Trevors vending machine');
Writeln();
WriteLn (' A B C D' );
for i:=1 to 2 do begin
write(i,' ');
for j:=1 to 4 do begin
write(vend[j,i].Name,' ':(12-length(vend[j,i].Name)));
end;
WriteLn(); Write(' '); for j:=1 to 4 do begin write('£',vend[j,i].price:4:2,' ');
end;
Writeln();
end;
{ We should have delt with money } if (amountPaid > 0) then machineEvent := Error; if (changeDue > 0) then machineEvent := Error;
end;
procedure TOwaiting(); begin machineState := Waiting; if ((machineEvent = Select) and (amountPaid >= itemPrice)) then machineEvent := Epsilon; if ((machineEvent = Deposit) and (amountPaid >= itemPrice)) then machineEvent := Epsilon;
end;
procedure TOrefund();
begin machineState := Refund;
machineEvent := Epsilon;
if (amountPaid > 0) then changeDue := amountPaid;
WriteLn('REFUNDING >> £' , changeDue:2:2);
changeDue := 0;
amountPaid := 0;
end;
procedure TOdispense(); begin
machineState := Dispense;
if (amountPaid >= vend[I,J].price) then begin
machineEvent := Remove;
changeDue := amountPaid - vend[I,J].price ;
amountPaid := 0;
vend[I,J].Stock := vend[I,J].Stock - 1;
WriteLn('Vending >>',vend[I,J].Name);
end
else machineState := Waiting;
end;
procedure TOstop(); begin machineState := Stop; machineEvent := Epsilon; { There should not be any transaction in process } if ((amountPaid >0) or (changeDue >0)) then machineEvent := Error;
end;
procedure Init; var k,l: integer; begin
{ Lets pretend we have some stuff in this machine }
vend[0,0].Name := 'Dummy';
vend[0,0].Stock := 0;
vend[0,0].price := 9999;
vend[1,1].Name := 'Snickers';
vend[1,1].Stock := 12; vend[1,1].price := 0.50;
vend[2,1].Name := 'Aero';
vend[2,1].Stock := 12; vend[2,1].price := 0.50;
vend[3,1].Name := 'Bounty'; vend[3,1].Stock := 10; vend[3,1].price := 0.75;
vend[4,1].Name := 'Creme egg'; vend[4,1].Stock := 15; vend[4,1].price := 0.60;
vend[1,2].Name := 'Coke-Cola'; vend[1,2].Stock := 6; vend[1,2].price := 1.10;
vend[2,2].Name := 'Pepsi'; vend[2,2].Stock := 6; vend[2,2].price := 1.25;
vend[3,2].Name := '7 up'; vend[3,2].Stock := 6; vend[3,2].price := 1.15;
vend[4,2].Name := 'Dr Pepper'; vend[4,2].Stock := 6; vend[4,2].price := 1.99;
{ Set up the state table }
for k :=1 to 7 do begin
for l :=1 to 6 do machine[k,l] := Null;
end;
machine[ord(Ready),ord(Deposit)] := Waiting; machine[ord(Waiting),ord(Deposit)] := Dispense; machine[ord(Waiting),ord(Select)] := Dispense; machine[ord(Waiting),ord(Cancel)] := Refund; machine[ord(Dispense),ord(Remove)] := Refund; machine[ord(Dispense),ord(Error)] := Refund; machine[ord(Refund),ord(epsilon)] := Ready; machine[ord(Ready),ord(Select)] := Waiting; machine[ord(Ready),ord(Quit)] := Stop;
{ There should be no money entered so no change is due
* set itemPrice to a huge dummy amount}
amountPaid := 0; changeDue := 0; itemPrice := 999; I:= 0; J:=0;
end;
begin
Init;
TOready;
{ Here comes the magic bit ... We check for events and if an event
* occurs we look up on the table to see if we need to transition to
* another state. If we do we call the TO_xxxxx procedure. BUT we do
* this in the other order to check for machine generated events like
* Error and Epsilon. }
repeat
newState := machine[ord(machineState),ord(machineEvent)];
case (newState) of Ready : TOready; Waiting : TOwaiting; Dispense : Todispense; Refund: Torefund; Stop: TOStop; end;
{ We get some user input and assign an event to it
- If the user enters a number we convert it to currency and set a
- deposit event If we have a letter we are making a selection }
if (machineState = Ready) or (machineState = Waiting) then begin
WriteLn;
Writeln('Enter Selectian A1..D4'); Writeln('or deposit amount e.g, 0.20 -- 20p piece.'); Write('Or X to cancel, Q to stop this machine :'); ReadLn (entry); if ((entry = 'q') or (entry = 'Q')) then machineEvent := Quit; if ((entry = 'x') or (entry = 'X')) then machineEvent := Cancel; if ((entry[1] in ['a'..'d']) or (entry[1] in ['A'..'D'])) then machineEvent:= Select; if (entry[1] in ['0'..'9']) then begin machineEvent := Deposit; amountPaid := StrToCurr(entry); end; if (machineEvent = Select) then begin I := ord(entry[1]) - 64; if (I > 5) then I := I - 32; J := ord(entry[2]) - ord('0'); end;
end; until machineEvent = Quit;
end.
</lang>
OUTPUT:
*** Selection First ****
Trevors vending machine
A B C D
1 Snickers Aero Bounty Creme egg
£0.50 £0.50 £0.75 £0.60
2 Coke-Cola Pepsi 7 up Dr Pepper
£1.10 £1.25 £1.15 £1.99
Enter Selectian A1..D4
or deposit amount e.g, 0.20 -- 20p piece.
Or X to cancel, Q to stop this machine :d1
Enter Selectian A1..D4
or deposit amount e.g, 0.20 -- 20p piece.
Or X to cancel, Q to stop this machine :0.99
Vending >>Creme egg
REFUNDING >> £0.39
Trevors vending machine
A B C D
1 Snickers Aero Bounty Creme egg
£0.50 £0.50 £0.75 £0.60
2 Coke-Cola Pepsi 7 up Dr Pepper
£1.10 £1.25 £1.15 £1.99
Enter Selectian A1..D4
or deposit amount e.g, 0.20 -- 20p piece.
Or X to cancel, Q to stop this machine :q
*** Deposit First ***
Trevors vending machine
A B C D
1 Snickers Aero Bounty Creme egg
£0.50 £0.50 £0.75 £0.60
2 Coke-Cola Pepsi 7 up Dr Pepper
£1.10 £1.25 £1.15 £1.99
Enter Selectian A1..D4
or deposit amount e.g, 0.20 -- 20p piece.
Or X to cancel, Q to stop this machine :2.00
Enter Selectian A1..D4
or deposit amount e.g, 0.20 -- 20p piece.
Or X to cancel, Q to stop this machine :b2
Vending >>Pepsi
REFUNDING >> £0.75
Trevors vending machine
A B C D
1 Snickers Aero Bounty Creme egg
£0.50 £0.50 £0.75 £0.60
2 Coke-Cola Pepsi 7 up Dr Pepper
£1.10 £1.25 £1.15 £1.99
Enter Selectian A1..D4
or deposit amount e.g, 0.20 -- 20p piece.
Or X to cancel, Q to stop this machine :q
Perl
Added a dummy input called "IMPLICIT" that does not actually require input but automatically transitions to next state. <lang perl>#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Finite_state_machine use warnings;
my ($state, $action, %fsm) = 'ready'; while( )
{
my ($start, $action, $end, $message) = split ' ', $_, 4;
$fsm{$start}{$action} = { next => $end, message => $message || "\n" };
}
while( $state ne 'exit' )
{
print "in state $state\n";
do
{
($action) = grep $_ eq 'IMPLICIT', my @actions = sort keys %{$fsm{$state}};
if( not $action )
{
print "Enter ", join(' or ', @actions), " : ";
chomp($action = uc <STDIN>);
}
}
until $fsm{$state}{$action};
print $fsm{$state}{$action}{message};
$state = $fsm{$state}{$action}{next};
}
- state input newstate displaytext
__DATA__ ready DEPOSIT waiting deposit coins ready QUIT exit waiting SELECT dispense remove item waiting REFUND refunding take the refund dispense REMOVE ready Thank You refunding IMPLICIT ready</lang>
- Output:
in state ready Enter DEPOSIT or QUIT : deposit deposit coins in state waiting Enter REFUND or SELECT : select remove item in state dispense Enter REMOVE : remove Thank You in state ready Enter DEPOSIT or QUIT : deposit deposit coins in state waiting Enter REFUND or SELECT : refund take the refund in state refunding in state ready Enter DEPOSIT or QUIT : quit
Phix
You can run this online here.
-- -- demo\rosetta\Finite_State_Machine.exw -- ===================================== -- with javascript_semantics -- First, let's define our state machine textually, why not: constant state_string = """ Ready,Deposit->Waiting,Quit Waiting,Select->Dispense,Refund Dispense,Remove->Ready:Remove product Refund->Ready:Refunding money Quit:Bye """ function decode(string state_string) sequence states = {}, messages = {}, valid_keys = {} for line in split(state_string,"\n") do sequence state = {} string keyable = "" integer m = find(':',line) messages = append(messages,iff(m?line[m+1..$]:"")) for phrase in split(line[1..m-1],",") do state = append(state,split(phrase,"->")) keyable &= phrase[1] end for states = append(states,state) valid_keys = append(valid_keys,keyable[2..$]) end for return {states, messages, valid_keys} end function constant {states, messages, valid_keys} = decode(state_string), valid_states = vslice(vslice(states,1),1) include pGUI.e Ihandle dlg, vbox, state, status, options procedure transition_to(integer sdx) IupSetAttribute(status,"TITLE",messages[sdx]) if length(states[sdx][1])=2 then -- (implicit) sdx = find(states[sdx][1][2],valid_states) end if IupSetAttribute(state,"TITLE",valid_states[sdx]) IupSetStrAttribute(options,"TITLE",join(vslice(states[sdx][2..$],1)," or ")) end procedure function finite_state_machine(atom c) integer sdx = find(IupGetAttribute(state,"TITLE"),valid_states), cdx = find(c,valid_keys[sdx]) if cdx then string newstate = states[sdx][cdx+1][$] sdx = find(newstate,valid_states) transition_to(sdx) end if return iff(valid_states[sdx]=`Quit`?IUP_CLOSE:IUP_CONTINUE) end function function key_cb(Ihandle /*dlg*/, atom c) if c=K_ESC then return IUP_CLOSE end if -- (standard practice for me) if c=K_F5 then return IUP_DEFAULT end if -- (let browser reload work) return finite_state_machine(upper(c)) end function IupOpen() state = IupLabel("","EXPAND=YES") status = IupLabel("","EXPAND=YES") options = IupLabel("","EXPAND=YES") vbox = IupVbox({state,status,options},`MARGIN=40x40`) dlg = IupDialog(vbox,`TITLE="Finite State Machine",SIZE=200x100`) IupSetCallback(dlg,"KEY_CB",Icallback("key_cb")) transition_to(1) -- Ready IupShow(dlg) if platform()!=JS then IupMainLoop() IupHide(dlg) end if
PicoLisp
Non-interactive random switch between states. <lang PicoLisp>(seed (in "/dev/urandom" (rd 8))) (de atm NIL
(state '(ready)
(ready (if (rand T) 'waiting 'quit)
(prin "ready->") )
(waiting (if (rand T) 'dispense 'refund)
(prin "wait->") )
(dispense 'ready
(prin "dispense->") )
(refund 'ready
(prin "refund->") )
(quit 'ready
(nil (prinl "quit")) ) ) )
(do 3
(while (atm)) )</lang>
- Output:
ready->wait->dispense->ready->wait->dispense->ready->quit ready->wait->refund->ready->quit ready->wait->dispense->ready->quit
Prolog
<lang Prolog>state(ready, deposit, waiting). state(ready, quit, exit). state(waiting, select, dispense). state(waiting, refund, refunding). state(dispense, remove, ready).
message(ready, 'Please deposit coins.~n'). message(waiting, 'Please select an item, or refund coins.~n'). message(dispense, 'Please remove your item.~n'). message(refunding, 'Coins have been refunded~n').
act :- act(ready).
act(exit). act(refunding) :- print_message(refunding), act(ready). act(State) :- dif(State, exit), print_message(State), read(Action), state(State, Action, NextState), act(NextState).
print_message(State) :- message(State, Message), format(Message).</lang>
- Output:
2 ?- act. Please deposit coins. |: deposit. Please select an item, or refund coins. |: select. Please remove your item. |: remove. Please deposit coins. |: deposit. Please select an item, or refund coins. |: refund. Coins have been refunded Please deposit coins. |: quit. true .
Python
<lang Python> Finite State Machine for Rosetta Code Actually two of them. The main FSM described in the task and a second one of the Acceptor variety described on the WP page to get the input from the user.
I handled the implicit transition by defining a null list as the valid inputs. and made my Acceptor return the null string () for the instance of no valid inputs. Then just defined the the transition for current state and null string for input.
I find it interesting that the rules for such a simple fsm took more lines of code than the actual code for the fsm which can be fed many different sets of rules. Storing the rules in a databse would reduce the lines required for storing the rules
states = { 'ready':{
'prompt' : 'Machine ready: (d)eposit, or (q)uit?',
'responses' : ['d','q']},
'waiting':{
'prompt' : 'Machine waiting: (s)elect, or (r)efund?',
'responses' : ['s','r']},
'dispense' : {
'prompt' : 'Machine dispensing: please (r)emove product',
'responses' : ['r']},
'refunding' : {
'prompt' : 'Refunding money',
'responses' : []},
'exit' :{}
}
transitions = { 'ready': {
'd': 'waiting',
'q': 'exit'},
'waiting' : {
's' : 'dispense',
'r' : 'refunding'},
'dispense' : {
'r' : 'ready'},
'refunding' : {
: 'ready'}}
def Acceptor(prompt, valids):
Acceptor style finite state machine to prompt for user input
if not valids:
print(prompt)
return
else:
while True:
resp = input(prompt)[0].lower()
if resp in valids:
return resp
def finite_state_machine(initial_state, exit_state):
response = True
next_state = initial_state
current_state = states[next_state]
while response != exit_state:
response = Acceptor(current_state['prompt'], current_state['responses'])
next_state = transitions[next_state][response]
current_state = states[next_state]
if __name__ == "__main__":
finite_state_machine('ready','q')
</lang>
- Output:
PS C:\alan\programming> & "C:/Program Files (x86)/Python38-32/python.exe" c:/alan/programming/fsm.py Machine ready: (d)eposit, or (q)uit?d Machine waiting: (s)elect, or (r)efund?s Machine dispensing: please (r)emove productr Machine ready: (d)eposit, or (q)uit?d Machine waiting: (s)elect, or (r)efund?r Refunding money Machine ready: (d)eposit, or (q)uit?q PS C:\alan\programming>
Racket
<lang racket>#lang racket
(define states
'((ready (deposit . waiting)
(quit . exit))
(waiting (select . dispense)
(refund . refunding))
(dispense (remove . ready))
(refunding . ready)))
(define (machine states prompt get-action quit)
(let recur ((state (caar states)))
(printf "CURRENT STATE: ~a~%" state)
(if (eq? state 'exit)
(quit)
(recur (match (cdr (assoc state states))
[(list (and transitions (cons actions _)) ...)
(prompt "next action (from: ~a): " actions)
(match (assoc (get-action) transitions)
[(cons action new-state)
(printf "~a -> ~a -> ~a~%" state action new-state)
new-state]
[#f (printf "invalid action for~%") state])]
[auto-state
(printf "~a -> ~a~%" state auto-state)
auto-state])))))
(module+ main
(let/ec quit
(with-input-from-string "deposit select remove deposit refund quit"
(λ () (machine states void read quit)))))</lang>
- Output:
CURRENT STATE: ready ready -> deposit -> waiting CURRENT STATE: waiting waiting -> select -> dispense CURRENT STATE: dispense dispense -> remove -> ready CURRENT STATE: ready ready -> deposit -> waiting CURRENT STATE: waiting waiting -> refund -> refunding CURRENT STATE: refunding refunding -> ready CURRENT STATE: ready ready -> quit -> exit CURRENT STATE: exit
Raku
(formerly Perl 6)
<lang perl6>#===== The state machine =====#
class StateMachine {
class State {...}
class Transition {...}
has State %!state; has &.choose-transition is rw;
method add-state(Str $id, &action)
{
%!state{$id} = State.new(:$id, :&action);
}
multi method add-transition(Str $from, Str $to)
{
%!state{$from}.implicit-next = %!state{$to};
}
multi method add-transition(Str $from, $id, Str $to)
{
%!state{$from}.explicit-next.push: Transition.new(:$id, to => %!state{$to});
}
method run(Str $initial-state)
{
my $state = %!state{$initial-state};
loop {
$state.action.();
if $state.implicit-next -> $_ { $state = $_; }
elsif $state.explicit-next -> $_ { $state = &.choose-transition.(|$_).to; }
else { last; }
}
}
class Transition {
has $.id;
has State $.to;
}
class State {
has $.id;
has &.action;
has State $.implicit-next is rw;
has Transition @.explicit-next;
}
}
- ===== Usage example: Console-based vending machine =====#
my StateMachine $machine .= new;
$machine.choose-transition = sub (*@transitions) {
say "[{.key + 1}] {.value.id}" for @transitions.pairs;
loop {
my $n = val get;
return @transitions[$n - 1] if $n ~~ Int && $n ~~ 1..@transitions;
say "Invalid input; try again.";
}
}
$machine.add-state("ready", { say "Please deposit coins."; }); $machine.add-state("waiting", { say "Please select a product."; }); $machine.add-state("dispense", { sleep 2; say "Please remove product from tray."; }); $machine.add-state("refunding", { sleep 1; say "Refunding money..."; }); $machine.add-state("exit", { say "Shutting down..."; });
$machine.add-transition("ready", "quit", "exit"); $machine.add-transition("ready", "deposit", "waiting"); $machine.add-transition("waiting", "select", "dispense"); $machine.add-transition("waiting", "refund", "refunding"); $machine.add-transition("dispense", "remove", "ready"); $machine.add-transition("refunding", "ready");
$machine.run("ready");</lang>
REXX
version 1
This version only works with:
- Personal REXX --or--
- PC/REXX
This is essentially a one-for-one translation of the BASIC program, with the following minor differences:
- the input allowed is either the uppercase or lowercase version of the letter(s)
- a mixture of uppercase and lowercase text is used for the output messages
- messages have extra blanks for readability (and options are spelled out)
<lang rexx>/*REXX pgm simulates a FSM (Finite State Machine), input is recognized by pressing keys.*/
10: say "Press D (deposit) or Q (quit)" /*display a prompt (message) to term. */
20: $=inkey(); upper $ /*since this a terminal, uppercase KEY.*/
if $=="D" then signal 50 /*Is response a "D" ? Process deposit.*/
if $=="Q" then exit /*Is response a "Q" ? Then exit pgm. */
signal 20 /*Response not recognized, re-issue msg*/
50: say "Press S (select) or R (refund)" /*display a prompt (message) to term. */
60: $=inkey(); upper $ /*since this a terminal, uppercase KEY.*/
if $=="S" then signal 90 /*Is response a "S" ? Then dispense it*/
if $=="R" then signal 140 /*Is response a "R" ? Then refund it. */
signal 60 /*Response not recognized? Re-issue msg*/
90: say "Dispensed" /*display what action just happened. */
signal 110 /*go and process another option. */
/* [↑] above statement isn't needed. */
110: say "Press R (remove)" /*display a prompt (message) to term. */ 120: $=inkey(); upper $ /*since this a terminal, uppercase KEY.*/
if $=="R" then signal 10 /*Is response a "R" ? Then remove it. */
signal 120 /*Response not recognized, re-issue msg*/
140: say "Refunded" /*display what action just happened. */
signal 10 /*go & re-start process (ready state). */</lang>
- output when using (pressing) the exact same input(s) as the BASIC entry: D R D S R Q
press D (deposit) or Q (quit) d ◄■■■■■■■■■■ user pressed this key. Press S (select) or R (refund) r ◄■■■■■■■■■■ user pressed this key. Refunded press D (deposit) or Q (quit) d ◄■■■■■■■■■■ user pressed this key. Press S (select) or R (refund) s ◄■■■■■■■■■■ user pressed this key. Dispensed Press R (remove) r ◄■■■■■■■■■■ user pressed this key. press D (deposit) or Q (quit) q ◄■■■■■■■■■■ user pressed this key.
version 2
works withooRexx (and any other REXX). key and Enter must be pressed- <lang rexx>/*REXX pgm simulates a FSM (Finite State Machine), input is recognized by pressing keys.*/
10: k=inkey('D (deposit) or Q (quit)','DQ')
if k=="D" then signal 50 /*Is response a "D" ? Process deposit.*/
if k=="Q" then exit /*Is response a "Q" ? Then exit pgm. */
50: k=inkey('S (select) or R (refund)','SR');
if k=="S" then signal 90 /*Is response a "S" ? Then dispense it*/
if k=="R" then signal 140 /*Is response a "R" ? Then refund it. */
90: say "Dispensed" /*display what action just happened. */
signal 110 /*go and process another option. */
110: k=inkey('R (remove)','R');
if k=="R" then signal 10 /*Is response a "R" ? Then remove it. */
140: say "Refunded" /*display what action just happened. */
signal 10 /*go & re-start process (ready state). */
inkey: Parse Arg prompt,valid Do Forever
Say 'Press' prompt 'and Enter' Parse Upper Pull key k=left(key,1) If pos(k,valid)>0 Then Leave Else Say 'Invalid key, try again.' End
Return k</lang>
- Output:
Press D (deposit) or Q (quit) and Enter c Invalid key, try again. Press D (deposit) or Q (quit) and Enter d Press S (select) or R (refund) and Enter g Invalid key, try again. Press S (select) or R (refund) and Enter r Refunded Press D (deposit) or Q (quit) and Enter
Rust
For abstraction, it is desirable to implement the transitions of the state machine through its methods.
Here it is done transparently using the method_enum::gen macro.
[dependencies]
methods-enum = "0.2.4"
<lang fsharp>enum State {
Ready, Waiting, Dispense, Refunding, Exit,
}
- [methods_enum::gen(Act: run)]
impl State {
pub fn set(&mut self); pub fn input_char(&mut self, ch: char);
fn run(&mut self, act: Act) {
match self {
State::Ready => match act {
Act::set() => println!("Ready: d - deposit / q - quit "),
Act::input_char('d') => self.set_state(State::Waiting),
Act::input_char('q') => self.set_state(State::Exit),
_ => self.set(),
},
State::Waiting => match act {
Act::set() => println!("Waiting: s - select / r - refund "),
Act::input_char('s') => self.set_state(State::Dispense),
Act::input_char('r') => self.set_state(State::Refunding),
_ => self.set(),
},
State::Dispense => match act {
Act::set() => println!("Dispense: r - remove "),
Act::input_char('r') => self.set_state(State::Ready),
_ => self.set(),
},
State::Refunding => match act {
Act::set() => {
println!("Refunding: refund of the deposit...");
self.set_state(State::Ready)
}
_ => (), // never - ignore
},
State::Exit => match act {
Act::set() => println!("Exit: goodbye! "),
_ => panic!("!! Invalid command for State::Exit: '{act:?}'"),
},
}
}
fn set_state(&mut self, new_state: State) {
*self = new_state;
self.set();
}
}
fn main() {
let mut machine = State::Ready; machine.set();
while !matches!(&machine, State::Exit) {
machine.input_char(char_entered());
}
}
fn char_entered() -> char {
let mut text = String::new();
std::io::stdin().read_line(&mut text).unwrap_or(0);
text.chars().next().unwrap_or('\x0d')
}</lang>
- Output:
Ready: d - deposit / q - quit d Waiting: s - select / r - refund r Refunding: refund of the deposit... Ready: d - deposit / q - quit d Waiting: s - select / r - refund s Dispense: r - remove r Ready: d - deposit / q - quit q Exit: goodbye!
Tcl
Using a nested dict where the leafs contain the output state corresponding to an action, and empty actions are implicit transitions. Would be marginally cleaner using a do..while proc. <lang tcl>set fsm [dict create \ ready {deposit waiting quit exit} \ waiting {select dispense refund refunding} \ dispense {remove ready} \ refunding {{} ready} \ ] set state ready
proc prompt {fsm state} { set choices [dict keys [dict get $fsm $state]] while {1} { puts -nonewline "state: $state, possible actions: $choices\n>" if {[gets stdin line] == -1} { exit } if {$line in $choices} { return $line } } }
while {$state ne "exit"} { set action [prompt $fsm $state] set state [dict get $fsm $state $action] while {[dict exists $fsm $state {}]} { set state [dict get $fsm $state {}] } }</lang>
- Output:
$ tclsh fsm.tcl state: ready, possible actions: deposit quit >deposit state: waiting, possible actions: select refund >select state: dispense, possible actions: remove >remove state: ready, possible actions: deposit quit >deposit state: waiting, possible actions: select refund >re state: waiting, possible actions: select refund >refund state: ready, possible actions: deposit quit >quit
VBA
<lang vb>Enum states
READY WAITING DISPENSE REFUND QU1T
End Enum '-- (or just use strings if you prefer) Public Sub finite_state_machine()
Dim state As Integer: state = READY: ch = " "
Do While True
Debug.Print ch
Select Case state
Case READY: Debug.Print "Machine is READY. (D)eposit or (Q)uit :"
Do While True
If ch = "D" Then
state = WAITING
Exit Do
End If
If ch = "Q" Then
state = QU1T
Exit Do
End If
ch = InputBox("Machine is READY. (D)eposit or (Q)uit :")
Loop
Case WAITING: Debug.Print "(S)elect product or choose to (R)efund :"
Do While True
If ch = "S" Then
state = DISPENSE
Exit Do
End If
If ch = "R" Then
state = REFUND
Exit Do
End If
ch = InputBox("(S)elect product or choose to (R)efund :")
Loop
Case DISPENSE: Debug.Print "Dispensing product..."
Do While True
If ch = "C" Then
state = READY
Exit Do
End If
ch = InputBox("Please (C)ollect product. :")
Loop
Case REFUND: Debug.Print "Please collect refund."
state = READY
ch = " "
Case QU1T: Debug.Print "Thank you, shutting down now."
Exit Sub
End Select
Loop
End Sub</lang>
- Output:
Machine is READY. (D)eposit or (Q)uit : D (S)elect product or choose to (R)efund : S Dispensing product... C Machine is READY. (D)eposit or (Q)uit : D (S)elect product or choose to (R)efund : R Please collect refund. Machine is READY. (D)eposit or (Q)uit : Q Thank you, shutting down now.
Wren
<lang ecmascript>import "/str" for Str import "io" for Stdin, Stdout
var READY = 0 var WAITING = 1 var EXIT = 2 var DISPENSE = 3 var REFUNDING = 4
var fsm = Fn.new {
System.print("Please enter your option when prompted")
System.print("(any characters after the first will be ignored)")
var state = READY
var trans = ""
while (true) {
if (state == READY) {
while (true) {
System.write("\n(D)ispense or (Q)uit : ")
Stdout.flush()
trans = Str.lower(Stdin.readLine())[0]
if (trans == "d" || trans == "q") break
}
state = (trans == "d") ? WAITING : EXIT
} else if (state == WAITING) {
System.print("OK, put your money in the slot")
while (true) {
System.write("(S)elect product or choose a (R)efund : ")
Stdout.flush()
trans = Str.lower(Stdin.readLine())[0]
if (trans == "s" || trans == "r") break
}
state = (trans == "s") ? DISPENSE : REFUNDING
} else if (state == DISPENSE) {
while (true) {
System.write("(R)emove product : ")
Stdout.flush()
trans = Str.lower(Stdin.readLine())[0]
if (trans == "r") break
}
state = READY
} else if (state == REFUNDING) {
// no transitions defined
System.print("OK, refunding your money")
state = READY
} else if (state == EXIT) {
System.print("OK, quitting")
return
}
}
}
fsm.call()</lang>
- Output:
Sample output:
Please enter your option when prompted (any characters after the first will be ignored) (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : s (R)emove product : r (D)ispense or (Q)uit : d OK, put your money in the slot (S)elect product or choose a (R)efund : r OK, refunding your money (D)ispense or (Q)uit : q OK, quitting
zkl
A lame FSM, we just convert text to a [hopefully valid] zkl program, compile and run it.
If we need true state to state hops, we could use tail recursion (another name for goto). <lang zkl>class FSM{ // our Finite State Machine
var bank=0, item=Void;
fcn deposit(coin){ bank=coin }
fcn select(item){
if(bank){ bank=0; self.item=item; }
else print("Depost coin, then select ")
}
fcn take { if(item) item=Void; else print("Select first "); }
fcn refund { coin:=bank; bank=0; return(coin) }
// couple of wrappers to state changes
fcn state{ println("Bank(%4d), Item(%s)".fmt(bank,item)) }
fcn act(f){ print("%-10s-->".fmt(f.name)); f(); state(); }
}
Vault.add(FSM); // put class FSM where I can find it</lang> <lang zkl>fcn run(program){ // convert text to FSM instructions and run them
program=program.replace("(",".fp("); // deposit(10)-->deposit.fp(10)
a,b,p := 0,0,Sink("class P(FSM){ state(); ");
while(Void!=(b=program.find(";",a)))
{ p.write("act(",program[a,b-a],");"); a=b + 1; }
program=p.write(program[a,*],"}").close();
// println(program); // WTH did I just do?
Compiler.Compiler.compileText(program)(); // compile and run our little FSM
}</lang> <lang zkl>run("select(); take(); deposit(10); select(\"snickers\"); take();");</lang> The above is converted to: <lang zkl>class P(FSM){
state();
act(select.fp());
act( take.fp());
act( deposit.fp(10));
act( select.fp("snickers"));
act( take.fp());
}</lang> The .fp() is function application (ie deferred execution) so I can extract the function name and print it.
- Output:
Bank( 0), Item(Void) select -->Depost coin, then select Bank( 0), Item(Void) take -->Select first Bank( 0), Item(Void) deposit -->Bank( 10), Item(Void) select -->Bank( 0), Item(snickers) take -->Bank( 0), Item(Void)