Re: Efficient implementation of Finite State Machines (FSM)

Liste des GroupesRevenir à cl forth 
Sujet : Re: Efficient implementation of Finite State Machines (FSM)
De : do-not-use (at) *nospam* swldwa.uk (Gerry Jackson)
Groupes : comp.lang.forth
Date : 16. Jul 2025, 13:23:02
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <10585j6$m1on$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11
User-Agent : Mozilla Thunderbird
On 09/03/2025 16:29, Anton Ertl wrote:
I have worked out an example:
https://www.complang.tuwien.ac.at/forth/programs/fsm-ae.4th
Sorry about a late reply but I've just got round to looking more closely at your FSM example

 Let's first look at the example: The example recognizes and prints
numbers in a text and ignores everything else.  It terminates when it
sees '$'.  It has two states, one for being inside a number and one
for outside:
 state outside-num
state inside-num
 (Note that this is not the standar Forth word STATE).
 Then we define transitions:
 : out->out ( c-addr -- c-addr1 )
     count outside-num transition ;
 ' out->out outside-num all-transitions
 The out->out transition is the simplest one: It fetches the next char
(with COUNT) and switches to OUTSIDE-NUM.  TRANSITION already starts
the dispatch for that state and the next char; this (and maybe also
COUNT) could be put in the general FSM interpreter (START-DFA), but by
having TRANSITION in the individual transition actions (e.g.,
OUT->OUT), the implementation is more flexible, as we will see.
 At first OUT->OUT is put in transitions from OUTSIDE-NUM for all
characters using ALL-TANSITIONS; later the transitions of various
characters are overwritten:
 ' out->in '9' 1+ '0' outside-num some-transitions
' out->stop '$' outside-num one-transition
 Note that the stack effect comment for out->out is from the start of
the word to the start of the next state-transition word; the actual
stack effect depends on the implementation of transition.
 For more state transitions and the corresponding transition words see
the source code.
 Example usage:
 s" 123 abc 456 df$" drop outside-num start-dfa \ prints "123 456"
 Now for the implementations: States are just arrays of xts, indexed by
the character, and the xt is that of the transition from the state
with that character.
 The implementation without EXECUTE-EXIT looks as follows:
      : transition ( c addr -- xt )
         \ addr specifies the next state
         ]] swap th @ [[ ; immediate
          : stop ( c-addr -- 0 )
         drop 0 ;
      : start-dfa ( c-addr addr -- )
         swap count rot transition
         begin ( ... xt )
             execute dup
         0= until
         drop ;
 TRANSITION could be a plain colon definition here, but it is a macro
in order to make it more competetive in Gforth with the EXECUTE-EXIT
variant.  Here the termination is performed by replacing the next
c-addr with 0 and testing for 0 in the loop.
 An alternative implementation is to use EXECUTE-EXIT to tail-call the
next transition:
      : transition ( c addr -- )
         ]] swap th @ execute-exit [[ ; immediate
      : stop ( -- )
         \ let the ";" behind the STOP do the stopping
         ]] drop [[ ; immediate
      : start-dfa ( c-addr addr -- )
         \ let the dfa work on the string starting at c-addr, with initial
         \ state addr
         swap count rot transition ;
 Here TRANSITION contains the EXECUTE in the form of EXECUTE-EXIT, and
so each transition word directly calls the next one, and no loop is
necessary; with EXECUTE this would fill the return stack after a few
thousand transitions, but EXECUTE-EXIT takes the return address off
the return stack before EXECUTEing the next word and therefore can
perform an indefinite number of state transitions.
 So how do we get out of the state machine?  By not performing a
transition; instead we simply return to the caller of START-DFA.
 I looked at the generated code and thought that we can get rid of the
SWAP in the transition code by using the generalized constant folding
feature of Gforth.  This replaces the definition of TRANSITION with:
          : noopt-transition-compile, ( xt -- )
             \ basic compile, implementation for TRANSITION
             drop ]] swap th @ execute-exit [[ ;
But you can get rid of the SWAP because in GForth
     see th
     : th
       cells + ; ok
After executing your macro TRANSITION the out->out transition expands to
     : out->out  count swap th @ execute-exit  ;
Puttin TH in line we get:
     : out->out  count outside-num swap cells + @ execute-exit  ;
which can be rewritten
     : out->out  count cells outside-num + @ execute-exit  ;
Similarly the other transitions. This is portable unlike constant folding.
I've never thought that TH was a definition worth having except perhaps for readability. But then using COUNT to get the next character from a string is very misleading :)
The structure of your FSM can be achived by using Michael Gassanenko's (MLG) CHOOSE statement that I re-implemented in Standard Forth in 2020 as CREATE-SWITCH. See
https://github.com/gerryjackson/Forth-switch/blob/master/README.md
(MLG's implementation used return stack manipulation extensively which made it difficult to understand). Ruvim also has an implementation of a simple CHOOSE on GitHub see:
https://gist.github.com/ruv/1688fc01a861c3dd3243c128fd992a68
that could also be used provided it was extended to have a range selector.
To use CREATE-SWITCH the OUTSIDE-NUM state could be defined as:
defer inside-num  \ Forward reference
synonym create-state create-switch  \ To emphasise that it's creating
                                     \ a state
create-state  outside-num ( "name" -- )
    '$'         when  stop end       \ out-> stop
    '0' ... '9' when  dup 1- c@ '0' - swap count
                      inside-num transition  end   \ out->in
     bl ... '~' when  count outside-num transition end \ out->out
     0 ... 31   when  input-error end
                other input-error end
end
which would create almost the same array of action XTs as your example.
The INSIDE_NUM state would be similar
Note that the selectors contain duplicated values where the first occurence of a duplicated value 'wins'. Later duplications are ignored
If slightly slower runtime code is acceptable the above definition could be reduced to:
create-state  outside-num ( "name" -- )
    '$'         when  stop end       \ out-> stop
    '0' ... '9' when  dup 1- c@ '0' - swap count
                      inside-num transition  end   \ out->in
                other count outside-num transition  end
end
with a much smaller XT array (22 cells) but invalid values would cause an out->out transition, effectively being ignored.
--
Gerry

Date Sujet#  Auteur
3 Mar 25 * Fetch string from comment29sjack
3 Mar 25 +* Re: Fetch string from comment2minforth
4 Mar 25 i`- Re: Fetch string from comment1sjack
4 Mar 25 +* Re: Fetch string from comment10dxf
4 Mar 25 i`* Re: Fetch string from comment9sjack
4 Mar 25 i `* Re: Fetch string from comment8dxf
5 Mar 25 i  +* Re: Fetch string from comment4mhx
5 Mar 25 i  i+- Re: Fetch string from comment1Anton Ertl
5 Mar 25 i  i`* Re: Fetch string from comment2dxf
6 Mar 25 i  i `- Re: Fetch string from comment1dxf
5 Mar 25 i  `* Re: Fetch string from comment3sjack
5 Mar 25 i   `* Re: Fetch string from comment2sjack
5 Mar 25 i    `- Re: Fetch string from comment1minforth
4 Mar 25 +* Re: Fetch string from comment14mhx
5 Mar 25 i`* Re: Fetch string from comment13Gerry Jackson
5 Mar 25 i `* Re: Fetch string from comment12Anton Ertl
5 Mar 25 i  +* Re: Fetch string from comment10mhx
5 Mar 25 i  i`* Re: Fetch string from comment9Anton Ertl
6 Mar 25 i  i `* Re: Fetch string from comment8mhx
6 Mar 25 i  i  `* Re: Fetch string from comment7Anton Ertl
7 Mar 25 i  i   +- Re: Fetch string from comment1mhx
7 Mar 25 i  i   `* Efficient implementation of Finite State Machines (FSM)5Gerry Jackson
9 Mar 25 i  i    `* Re: Efficient implementation of Finite State Machines (FSM)4Anton Ertl
10 Mar 25 i  i     +- Re: Efficient implementation of Finite State Machines (FSM)1Gerry Jackson
11 Mar 25 i  i     +- Re: Efficient implementation of Finite State Machines (FSM)1Anton Ertl
16 Jul 25 i  i     `- Re: Efficient implementation of Finite State Machines (FSM)1Gerry Jackson
5 Mar 25 i  `- Re: Fetch string from comment1Gerry Jackson
4 Mar 25 +- Re: Fetch string from comment1sjack
7 Mar 25 `- Re: Fetch string from comment1sjack

Haut de la page

Les messages affichés proviennent d'usenet.

NewsPortal