Finite state machine: Difference between revisions
Content added Content deleted
m (→{{header|Rust}}: syntaxhighlight lang="rust") |
|||
Line 1,102: | Line 1,102: | ||
} |
} |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
{{works with|jq}} |
|||
'''Also works with gojq and fq''' provided the line defining |
|||
keys_unsorted is uncommented. |
|||
In this entry, we adopt an approach which emphasizes |
|||
separating code from data: we define a format for |
|||
representing state-transition tables as JSON objects, |
|||
which can be stored for example in separate files; |
|||
and we illustrate one possible FSM engine for |
|||
animating such state-transition tables. |
|||
The format of the JSON object specifying a state-transition table is |
|||
as follows, it being assumed that each "state" has a distinct |
|||
description as a JSON string: |
|||
* each top-level key represents a state of the FSM, with "exit" meaning stop; |
|||
* the value of each top-level key is another JSON object, which we will refer to as the trigger dictionary; |
|||
* each trigger dictionary consists of one or more key-value pairs, in which the "key" is the name of a trigger and the value is the name of a state. |
|||
Triggers can be of three kinds: |
|||
1. external (corresponding to external inputs) |
|||
2. automatic (corresponding to determinate internal transitions) |
|||
3. indeterminate (corresponding to non-determinism) |
|||
For external transitions, the keys should be non-empty strings that do not match "^[0-9]+ ". |
|||
For automatic transitions, the trigger object should have "" as its only key. |
|||
For indeterminate transitions, the trigger object should have keys matching the regex "^[0-9]+ " |
|||
The FSM engine presented here is intended to allow a person to provide |
|||
the "external inputs" as well as to pace automatic transitions and |
|||
to simulate the indeterminate transitions. In general, a menu of valid |
|||
input choices is presented, and the first match of the response with |
|||
these options determines the state transition. In addition, "?" as a |
|||
user input is recognized as a request for help. |
|||
'''fsm.json''' |
|||
<syntaxhighlight lang=jq> |
|||
{ |
|||
"ready": { |
|||
"deposit": "waiting", |
|||
"quit": "exit" |
|||
}, |
|||
"waiting": { |
|||
"select": "dispense", |
|||
"refund": "refunding" |
|||
}, |
|||
"dispense": { |
|||
"confirm": "confirming", |
|||
"refund": "refunding" |
|||
}, |
|||
"refunding": { |
|||
"1 REFUND MONEY": "ready", |
|||
"2 SORRY": "ready" |
|||
}, |
|||
"confirming": { |
|||
"": "ready" |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
'''fsm.jq''' |
|||
<syntaxhighlight lang=jq> |
|||
# Uncomment the following line if using gojq or fq: |
|||
# def keys_unsorted: keys; |
|||
# next($action) determines the next state. |
|||
# Global: $fsm (the transition-table) |
|||
# $action specifies an action, which can be abbreviated: the first possible match is selected. |
|||
# Input: {state} |
|||
def next($action): |
|||
($fsm[.state] | keys_unsorted) as $keys |
|||
| if ($action|length) == 0 |
|||
then if $keys|index("") then fsm[.state][""] |
|||
else null |
|||
end |
|||
else (first($keys[] | select( startswith($action) )) // null) as $k |
|||
| if $k then fsm[.state][$k] else null end |
|||
end; |
|||
def start: {"state": "ready"}; |
|||
# The FSM engine - progress from state to state based on user input |
|||
def progress: |
|||
def options: fsm[.state]|keys_unsorted; |
|||
def prompt: |
|||
options |
|||
| if length == 1 and .[0]=="" then "Enter anything to proceed." |
|||
elif .[0]|test("^[0-9]+ ") then "options: \(.) (simulated non-deterministic transition)" |
|||
else "options: \(.)" |
|||
end; |
|||
def help: |
|||
options |
|||
| if length == 1 and .[0]=="" then "(internal state transition awaiting your input)" |
|||
elif .[0]|startswith("1 ") then "(simulated NDFSM awaiting your input in the form of an initial substring): \(.)" |
|||
else |
|||
"Make a selection by typing an initial substring of the option you wish to select: \(.)" |
|||
end; |
|||
start |
|||
| label $out |
|||
| "Initial state: \(.state)\nMake your selection (at least one letter) from these options: \(options))", |
|||
foreach inputs as $in (.; |
|||
.previous=.state |
|||
| .error = null |
|||
| if $in == "?" then .error = true # |
|||
else next($in) as $next |
|||
| if $next then .state=$next else .error = "try again or enter ? for help" end |
|||
end; |
|||
if .error == true then help |
|||
elif .error then .error |
|||
elif .state == "exit" then break $out |
|||
else |
|||
"\(.previous) + \($in) => \(.state)", |
|||
prompt |
|||
end |
|||
) ; |
|||
progress |
|||
</syntaxhighlight> |
|||
'''Illustrative Transcript''': |
|||
<pre> |
|||
$ jq -nRr --argfile fsm fsm.json -f fsm.jq |
|||
Initial state: ready |
|||
Make your selection (at least one letter) from these options: ["deposit","quit"]) |
|||
? |
|||
Make a selection by typing an initial substring of the option you wish to select: ["deposit","quit"] |
|||
d |
|||
ready + d => waiting |
|||
options: ["refund","select"] |
|||
s |
|||
waiting + s => dispense |
|||
options: ["confirm","refund"] |
|||
c |
|||
dispense + c => confirming |
|||
Enter anything to proceed. |
|||
confirming + => ready |
|||
options: ["deposit","quit"] |
|||
d |
|||
ready + d => waiting |
|||
options: ["refund","select"] |
|||
r |
|||
waiting + r => refunding |
|||
options: ["1 REFUND MONEY","2 SORRY"] (simulated non-deterministic transition) |
|||
1 |
|||
refunding + 1 => ready |
|||
options: ["deposit","quit"] |
|||
q |
|||
</pre> |
|||
=={{header|Julia}}== |
=={{header|Julia}}== |