From: do-not-use@swldwa.uk   
      
   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    
       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   
      
   --- SoupGate-DOS v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)