Efficient implementation of Finite State Machines (FSM)

On 06/03/2025 18:09, Anton Ertl wrote:

mhx@iae.nl (mhx) writes:

However, a state machine has well defined rules based on a
state's stored information and its inputs, causing it to go to
another well-defined state while generating outputs. In that
context a goto is harmless and merely serves as a crutch when
there are not enough computing nodes to serve all states in
parallel. How to make such an efficient crutch in Forth?

 You lost me.  Why would one "serve all states in parallel"?
 Anyway, if the question is how to implement a state machine
efficiently in Forth, one answer is to stay at a higher, more
structured level of abstraction or recreate it from the state machine.
E.g., don't transform a regular expression into a (indeterministic or
deterministic) finite state machine, but instead interpret it directly
(that's what Bernd Paysan's regexp.fs does).  Or instead of
transforming a grammar into a push-down automaton, transform it into a
structured Forth program (like Gray does).
 If you cannot do that, in standard Forth you don't really have good
options.  The best is probably to have the current state on the stack
(probably in the form of the address of an array indexed with the
input (or whatever causes a state change) and containing the potential
next states at the appropriate elements.
 In a particular implementation, you can do more, including goto-like
things.  What I would do then is have a colon definition per state,
and do the transition to the next state as tail call.  Have some
efficient forward-tail-call mechanism to allow calling states where
the definition comes later.  Gforth has a clever FORWARD, but for now
that does not do tail-calls.
 - anton

About a year ago I wanted a finite state machine and thought that the Julian Noble approach was rather slow, so I developed a different approach that I haven't seen elsewhere. This method defines a state of the FSM as a wordlist that contains an action including a test, (a :noname definition), and a VALUE that holds the execution token of the state's action/test.
A simple example that demonstrates the principle is given below, it implements the Michael Gassanenko example that selects integers that can be divided by 6. See https://groups.google.com/g/comp.lang.forth/c/iHCT2IaqxSA/m/85IUu0GSBwAJ for another implementation. An FSM for the /6 example is not the best solution for the example but is simply used to demonstrate the principle.
Use of a wordlist, whose wid is held in an immediate constant, enables easy linkage between states at compile time, eg a typical state action in outline is:
:noname <action>
    if state-x [ >order ] next-state [ previous ]
    else state-y [ >order ] next-state [ previous ]
; this-state >order to next-state previous
where
- next-state is the VALUE holding the states action xt. A common name is used for each state so that code can be factored out.
- state-x and state-y are the immediate constants holding the state's wordlist.
- the wordlist switching is factored out for readability
Advantages are:
- the FSM run time loop is simple
- wordlist switching only occurs at compile time
- forward reference is easy because state wordlists and a common name for the action-xt VALUEs are defined at the start.
- easily extendable for states that can goto to several other states e.g. use a CASE statement for the state action.
- I believe but haven't proved that the run time code could be automatically generated by defining a simple state transition table
Disadvantages are:
- the Forth code doesn't give much idea of the overall operation of the FSM (probably true for FSMs in general)
- the state wordlists are redundant at run time
\ The example
: fsm-state  ( "state-name" "action-name" -- )
    get-current
    wordlist dup constant immediate set-current 0 value
    set-current
;
\          state name    state action-xt
\          ~~~~~~~~~~    ~~~~~~~~~~~~~~~
fsm-state     inc-n        next-state
fsm-state     /2           next-state
fsm-state     /3           next-state
fsm-state     .n           next-state
: is-next-state  ( wid -- )
    >order s" next-state" evaluate previous
; immediate
0 constant stop-fsm
:noname  ( ad -- ad xt|0 )
   dup 1 over +! 2@ >=
   if /2 is-next-state else stop-fsm then
; inc-n >order to next-state previous
:noname  ( ad -- ad xt )
    dup @ 2 mod if inc-n is-next-state else /3 is-next-state then
\ No, the two IS-NEXT_STATEs can't be replaced by one after the THEN
; /2 >order to next-state previous
:noname  ( ad -- ad xt )
    dup @ 3 mod if inc-n is-next-state else .n is-next-state then
; /3 >order to next-state previous
:noname  ( ad -- ad xt )
    dup @ . ( drop ) inc-n is-next-state
; .n >order to next-state previous
: run-fsm  ( ad xt -- )  begin dup while execute repeat 2drop  ;
2variable counter
inc-n >order next-state constant start previous
: /6?  ( n -- )
    cr cr 0 counter 2!
    counter start run-fsm
;
78 /6?  \ displays 6 12 18 24 30 36 42 48 54 60 66 72 78
--
Gerry