Re: Efficient implementation of Finite State Machines (FSM)

On 09/03/2025 16:29, Anton Ertl wrote:

Gerry Jackson <do-not-use@swldwa.uk> writes:

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

 It means that Gforth will have to improve its SEE in order to point
out the differences between the different NEXT-STATEs.  Currently I get:
 /2 >order  ok
next-state xt-see
noname :
   dup @ #1 and
   IF     next-state
   ELSE   next-state
   THEN ; ok

:) Well if you've never encountered this in (how many years has GForth been going - 25/30?) it's haardly worth bothering. At least it make someone think something strange is going on.

 

Disadvantages are:
- the Forth code doesn't give much idea of the overall operation of the
FSM (probably true for FSMs in general)

 That's definitely the case here.

THe same applies to your example. Most FSM implementations have a transition table and/or a state diagram.

IIRC for Michael Gassanenko it was a
demonstration of filtering and backtracking,

That's correct. I said it was a simple example of an FSM to demonstrate the principle the FSM

but it's unclear to me
how that transfers to FSMs.

The transition table for my example is:
                   Next State
State    If test true  If test false
-----    ------------  -------------
inc-n      /2             exit FSM
/2         inc-n          /3
/3         inc-n          .n
.n         inc-n          inc-n
As posts are text only it's not suitable for a state diagram.

 Anyway, let's look at the core:
 

: run-fsm  ( ad xt -- )  begin dup while execute repeat 2drop  ;

 This means that every state has to return to this loop to dispatch the
next one.  Now Gforth (development) has EXECUTE-EXIT, which allows
tail-calling the next state for better efficiency.

You know  more about effects of an instruction cache than me bu wouldn't a short loop like that be likely to fit in a cache line?
Your example with EXECUTE-EXIT made me think that I ought to be able to change mine to include an R> DROP at the start of each state to get the same effect and eliminate the loop. Non-standard of course, slower but apparently more portable. Possibly replacing the NEXT-STATE value with a common deferred word to handle forward definitions as before..

 I have worked out an example:
https://www.complang.tuwien.ac.at/forth/programs/fsm-ae.4th

Got to go but I'll return to this and look at your example in more detail later today hopefully.
[...]

- anton

--
Gerry