6502.org • View topic - A Finite State Machine Engine in Forth

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Forth

All times are UTC

A Finite State Machine Engine in Forth

Page 1 of 1

[ 13 posts ]

Previous topic | Next topic

Author

Message

JimBoyd

Post subject: A Finite State Machine Engine in Forth

Posted: Sat Mar 09, 2024 9:00 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

Some time ago I read about the Isopod and Servopod microcontrollers from New Micros. I also read the article "Robots and Finite-State Machines" by Everett F. Carter, Jr. in the February 1997 issue of Dr. Dobb's Journal. I've reacquired the user manuals and although New Micros is gone and I have no idea where or how to get either microcontroller, I thought the programming paradigm was interesting; therefore, I am starting this thread on implementing a finite state machine engine in Forth. New Micros called their finite state machine engine IsoMax.
Here is an example of IsoMax.
First, define a machine and its states.

Code:

MACHINE <MACHINE.NAME>         \ Define a state machine
ON-MACHINE <MACHINE.NAME>      \ and select this machine
   APPEND-STATE <STATE.NAME.1> \ to append  new states
   APPEND-STATE <STATE.NAME.2>
   APPEND-STATE <STATE.NAME.3>

Define the state transitions.

Code:

IN-STATE
   <STATE.NAME.1>
CONDITION
   <WORD OR WORDS WHICH RETURN A TRUE/FALSE VALUE>
CAUSES
   <ACTION>
THEN-STATE
   <STATE.NAME.2>
TO-HAPPEN

Other transitions can be added to a state.

Code:

IN-STATE
   <STATE.NAME.1>
CONDITION
   <ANOTHER LOGIC TEST>
CAUSES
   <SOME OTHER ACTION>
THEN-STATE
   <STATE.NAME.3>
TO-HAPPEN

More information can be found here courtesy of Brad Rodriguez.
The IsoMax syntax is somewhat verbose and I found in my implementation that two of the words are no-ops; however, the wording of the syntax helps guide the programmer to correctly define a state transition.

I'm not trying to reimplement IsoMax and I've never seen the source code for IsoMax, I just want to implement some kind of finite state machine engine in Forth. Is there a better syntax? I really don't know. The IsoMax syntax is already in use, so that is the syntax I'm using.

Here is my initial attempt to reproduce this functionality for my Forth.

Code:

CODE CELL+  ( ADR -- ADR+2 )
   ' 2+ @ LATEST NAME> ! \ Make CELL+ an alias for 2+
END-CODE

VARIABLE CFSM            \ Current Finite State Machine
VARIABLE DUMMY-STATE

: STATE-MACHINE  ( ++ )
   CREATE
      HERE CFSM !        \ Make new FSM current
      DUMMY-STATE ,      \ Set it to run DUMMY-STATE
      [ HERE CELL+ 2 ! ] \ Save address of DO.STATE.MACHINE
                         \ STC will need different offset
   DOES>
      @ @ ?DUP 0EXIT     \ If the current state's pointer
                         \ is zero, exit.
      ENTER              \ else enter the thread it points to.
      [ HERE DUMMY-STATE ! ] ;  \ DUMMY-STATE points to
                                \ a thread with EXIT .
                                
: ON-MACHINE  ( ++ )
   ' DUP @ [ 2 @ ] LITERAL <> 
   ABORT" NOT A STATE MACHINE"
   >BODY CFSM ! ;     \ Make named state machine current.

\ A machine state has three cells.
\ A pointer to threaded code to ENTER .
\ A pointer to its parent finite state machine.
\ A pointer to an address to patch.
: APPEND-STATE  ( ++ )       
   CREATE   ( ++ )           \ Create and add a new state
      HERE 0 ,  CFSM @ ,  ,  \ to the current FSM.
      [ HERE CELL+ 2 ! ]     \ Save address of DO.STATE
   ;CODE   ( -- SADR )       \ it's a jump to DO.VARIABLE
      ' FENCE @ JMP  END-CODE

The variable CFSM holds the PFA of the current finite state machine, the one to append new states.
STATE-MACHINE creates a new finite state machine. When a state machine is created, it becomes the current finite state machine. The only data a state machine has is a pointer to its current state. When a state machine is executed, it will run its current state; therefore, a new state machine has the DUMMY-STATE as its default state.
ON-MACHINE is used to change the current state machine. The name of a state machine must follow it in the text stream.
APPEND-STATE creates a new state for the current state machine. The body of each state has three cells.
1) A pointer to threaded code, or zero.
2) A pointer to its state machine.
3) A pointer to an address to patch.
A state returns its PFA just like a variable. A state's CFA points to a different address so error handling words can tell it's a machine state and not just a variable.

Code:

: ?STATE  ( SADR -- )
   BODY> @ [ 2 @ ] LITERAL <>  \ use address of do.state
   ABORT" NOT A STATE" ;       \ stored at address 2
                               \ and abort if not a state.

: SET-STATE  ( SADR -- )
   DUP ?STATE        \ Confirm address is PFA of a state.
   DUP CELL+ @ ! ;   \ set parent machine to run this state.

: IS-STATE?  ( STATE.ADDRESS -- )
   DUP ?STATE        \ Confirm address is PFA of a state.
   DUP CELL+ @ @ = ; \ fetch current state from machine
                     \ and compare

?STATE takes the PFA of a state and aborts if it's not really the PFA of a state.
SET-STATE takes the PFA of a state and makes it the state its state machine will run.
IS-STATE? takes the PFA of a state and returns a true flag if it is the state its machine is set to run and a false flag otherwise.
The words to define a transition for a state.

Code:

: IN-STATE  ( -- ) ;

: CONDITION  ( SADR -- SADR+4 -2 )  \ Store HERE at patch
   DUP ?STATE                       \ address and leave address
   CELL+ CELL+ HERE OVER @ ! -2 ] ; \ of third cell on stack.

: CAUSES  ( -- )
   -2 ?PAIRS COMPILE ?BRANCH        \ compile a branch to
   HERE SWAP!                       \ Forth thread with EXIT
   [ ' DUMMY-STATE >BODY ] LITERAL  \ and make cell after
   @ , ; IMMEDIATE                  \ ?BRANCH the new
                                    \ patch address.
: THEN-STATE   ; IMMEDIATE

: TO-HAPPEN
   COMPILE SET-STATE COMPILE EXIT
   [COMPILE] [ ; IMMEDIATE

Two of the words are actually no-ops, IN-STATE and THEN-STATE . These five words could have been written differently, but the documentation for the IsoPod indicates that each of these words can be on a line by itself. When using source files instead of blocks, this means none of these words parse.
These five words could have been written with a bit more compiler security to enforce the use of the no-op words, which wouldn't be no-ops anymore.
The three words which actually do something (at least in this implementation).
Given a machine state named GREEN.BORDER , in this code fragment:

Code:

IN-STATE
   GREEN.BORDER
CONDITION

the Forth system is interpreting. CONDITION takes the PFA of a machine state and confirms it is a machine state. If this is the first transition defined for this state, it's third cell will point to it's first cell. If it is not this states first transition, it's third cell will point to a branch address from the previous transition defined for this state. That address points to threaded code with an EXIT . In either case, the current value of HERE will be stored in the address the machine state's third cell points to since this is where the thread of high level Forth will be compiled. It leaves the address of the states third cell and a security value of -2 on the stack and sets the system's compiling state.
CAUSES confirms that -2 is on the stack (compiler security) and compiles ?BRANCH , the Forth-83 Standard word to branch if there is a zero on the data stack (FIG Forth called this word 0BRANCH ).
My Forth's ?BRANCH and BRANCH have an inline address, NOT an offset. The address following ?BRANCH is stored in the machine state's third cell for future use. The address of the threaded code fragment with EXIT is compiled right after ?BRANCH . This is where ?BRANCH will branch to if there is a zero on the data stack.
TO-HAPPEN compiles SET-STATE and EXIT then returns the system to interpreting.

The idea here is to be able to define a finite state machine and test it interactively. When it works, add it to a chain of state machines running in the background using the word INSTALL , which I haven't written yet. From what the IsoPod document stated, there are only sixteen slots to install state machines; however, one or more state machine chains can be installed instead of or in addition to state machines. State machine chains are created with the words MACHINE-CHAIN and END-MACHINE-CHAIN .

Code:

MACHINE-CHAIN MY.MACHINES
   MACHINE1
   MACHINE2
   MACHINE3
     ...
END-MACHINE-CHAIN

In this implementation, MACHINE-CHAIN and END-MACHINE-CHAIN are just aliases for colon and semicolon.
Here is a demo for this finite state machine engine.

Code:

VARIABLE SWITCH1
VARIABLE SWITCH2

STATE-MACHINE M1
ON-MACHINE M1
   APPEND-STATE GREEN.BORDER
   APPEND-STATE RED.BORDER

IN-STATE
   GREEN.BORDER
CONDITION
   SWITCH1 @  SWITCH2 @ AND
CAUSES
   GREEN BORDER
THEN-STATE
   RED.BORDER
TO-HAPPEN

IN-STATE
   RED.BORDER
CONDITION
   SWITCH1 @  SWITCH2 @ AND 0=
CAUSES
   RED BORDER
THEN-STATE
   GREEN.BORDER
TO-HAPPEN

RED BORDER
GREEN.BORDER SET-STATE

A state machine is normally tested interactively before installing it in a list of state machines which run in the background. This machine, M1 , can be tested by setting the variables SWITCH1 and SWITCH2 with ON or OFF and executing M1 .
I did not have the multitasker running so I set the state machine M1 to PAUSE to run M1 in the background.

Code:

' M1 IS PAUSE

When both variables SWITCH1 and SWITCH2 have a TRUE value, the border turns green. When either on holds a FALSE value, the border turns red.
Here is a decompilation of the threaded code run for the two states of this finite state machine.

Code:

GREEN.BORDER @ :DIS 
 24693 24614 SWITCH1
 24695  3580 @
 24697 24630 SWITCH2
 24699  3580 @
 24701  4574 AND
 24703  2275 ?BRANCH 24149  ' STATE-MACHINE >BODY 27 +
 24707 18327 GREEN
 24709 18386 BORDER
 24711 24685 RED.BORDER
 24713 24303 SET-STATE
 24715  2472 EXIT
24 
 OK
RED.BORDER @ :DIS 
 24717 24614 SWITCH1
 24719  3580 @
 24721 24630 SWITCH2
 24723  3580 @
 24725  4574 AND
 24727  4675 0=
 24729  2275 ?BRANCH 24149  ' STATE-MACHINE >BODY 27 +
 24733 18355 RED
 24735 18386 BORDER
 24737 24662 GREEN.BORDER
 24739 24303 SET-STATE
 24741  2472 EXIT
26 
 OK
24149 :DIS 
 24149  2472 EXIT
2 
 OK

Here is an example of appending a new machine state to the state machine M1 and appending new transitions to its machine states.

Code:

ON-MACHINE M1
   APPEND-STATE CYAN.BORDER
   
IN-STATE
   GREEN.BORDER
CONDITION
   SWITCH1 @ SWITCH2 @ XOR
CAUSES
   CYAN BORDER
THEN-STATE
   CYAN.BORDER
TO-HAPPEN

IN-STATE
   RED.BORDER
CONDITION
   SWITCH1 @ SWITCH2 @ XOR
CAUSES
   CYAN BORDER
THEN-STATE
   CYAN.BORDER
TO-HAPPEN

IN-STATE
   CYAN.BORDER
CONDITION
   SWITCH1 @ SWITCH2 @ AND
CAUSES

THEN-STATE
   GREEN.BORDER
TO-HAPPEN

IN-STATE
   CYAN.BORDER
CONDITION
   SWITCH1 @ SWITCH2 @ OR 0=
CAUSES

THEN-STATE
   RED.BORDER
TO-HAPPEN

RED BORDER
GREEN.BORDER SET-STATE

Notice that in the two transitions for CYAN.BORDER the CAUSES clause is empty. A state transition can cause anything (within reason), even nothing, to happen. A state transition can also cause a transition back to the same state.
Here is the decompilation for machine state CYAN.BORDER's threaded code fragment.

Code:

CYAN.BORDER @ :DIS 
 24813 24612 SWITCH1
 24815  3580 @
 24817 24628 SWITCH2
 24819  3580 @
 24821  4574 AND
 24823  2275 ?BRANCH 24833 
 24827 24660 GREEN.BORDER
 24829 24303 SET-STATE
 24831  2472 EXIT
 24833 24612 SWITCH1
 24835  3580 @
 24837 24628 SWITCH2
 24839  3580 @
 24841  4597 OR
 24843  4675 0=
 24845  2275 ?BRANCH 24149  ' STATE-MACHINE >BODY 27 +
 24849 24683 RED.BORDER
 24851 24303 SET-STATE
 24853  2472 EXIT
42 
 OK

The decompilations for the other two machine state's threaded code fragments.

Code:

GREEN.BORDER @ :DIS 
 24691 24612 SWITCH1
 24693  3580 @
 24695 24628 SWITCH2
 24697  3580 @
 24699  4574 AND
 24701  2275 ?BRANCH 24765  ' CYAN.BORDER >BODY 6 +
 24705 18327 GREEN
 24707 18386 BORDER
 24709 24683 RED.BORDER
 24711 24303 SET-STATE
 24713  2472 EXIT
24 
 OK
24765 :DIS 
 24765 24612 SWITCH1
 24767  3580 @
 24769 24628 SWITCH2
 24771  3580 @
 24773  4617 XOR
 24775  2275 ?BRANCH 24149  ' STATE-MACHINE >BODY 27 +
 24779 18347 CYAN
 24781 18386 BORDER
 24783 24757 CYAN.BORDER
 24785 24303 SET-STATE
 24787  2472 EXIT
24 
 OK
RED.BORDER @ :DIS 
 24715 24612 SWITCH1
 24717  3580 @
 24719 24628 SWITCH2
 24721  3580 @
 24723  4574 AND
 24725  4675 0=
 24727  2275 ?BRANCH 24789  ' CYAN.BORDER >BODY 30 +
 24731 18355 RED
 24733 18386 BORDER
 24735 24660 GREEN.BORDER
 24737 24303 SET-STATE
 24739  2472 EXIT
26 
 OK
24789 :DIS 
 24789 24612 SWITCH1
 24791  3580 @
 24793 24628 SWITCH2
 24795  3580 @
 24797  4617 XOR
 24799  2275 ?BRANCH 24149  ' STATE-MACHINE >BODY 27 +
 24803 18347 CYAN
 24805 18386 BORDER
 24807 24757 CYAN.BORDER
 24809 24303 SET-STATE
 24811  2472 EXIT
24 
 OK

For this demo, I only set or reset the variables SWITCH1 and SWITCH2 with ON and OFF so they would only have the values -1 and 0.
I would have liked to test this on a Commodore 64 with signals from real hardware and outputs to real hardware, but I haven't owned a real Commodore 64 in a long time.

There are other words to add. INSTALL installs a finite state machine, or a chain of finite state machines, in a list of machines to run in the background. UNINSTALL removes the last machine or machine chain from the list and does nothing if there are no more machines installed. How INSTALL is implemented depends on whether multitasking will also be supported, or if the state machines running in the background will take the place of background tasks.

As I said, I'm not trying to reimplement IsoMax. If there is a better syntax for a finite state machine engine, I'd like to know about it.

Last edited by JimBoyd on Sun Mar 10, 2024 7:32 pm, edited 1 time in total.

Top

barnacle

Post subject: Re: A Finite State Engine in Forth

Posted: Sun Mar 10, 2024 9:21 am

Joined: Mon Jan 19, 2004 12:49 pm
Posts: 660
Location: Potsdam, DE

JimBoyd wrote:

A state transition can cause anything (within reason), even nothing, to happen. A state transition can also cause a transition back to the same state.

Fascinating stuff. Not Forth, but I have a *huge* state machine hiding in a cat feeder (which unfortunately I can't show code of; commercially sensitive) but it controls all the interactions of the cat and the human*. It has over fifty states, and nearly as many triggers, and the paths between those states took us three walls' worth of whiteboards to plot. The formal definition for the state transitions resides in a large spreadsheet, which automatically converts to the state data in the final code. Without that automation, it was far too easy to make a change in one part of the machine and miss somewhere else... however, the point is that often the state does nothing but remain where it is; indeed, for most states, most triggers don't apply.

The actual state machine is two lines of C. The state data is a couple of thousand...

I do like the If/condition/then/dostuff/newstate construct.

Neil

* We thought we had all the possible interractions, but we missed a couple: human picks up kitten and uses that to open the lid, and cat turns feeder upside down and tries to get in through the bottom...

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sun Mar 10, 2024 7:37 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

I was in such a hurry to post this topic that I left the word 'Machine' out of the title.

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sat Mar 16, 2024 8:48 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

I neglected some of the stack comments for the Finite State Machine engine words.
I've also modified THEN-STATE and TO-HAPPEN and added THEN-SAME-STATE to improve the efficiency when a machine state transitions back to itself.
The same syntax will still work.

Code:

IN-STATE
   <STATE.NAME.1>
CONDITION
   <WORD OR WORDS WHICH RETURN A TRUE/FALSE VALUE>
CAUSES
   <ACTION>
THEN-STATE
   <STATE.NAME.2>
TO-HAPPEN

Now there is an alternate syntax for the case where the finite state machine transitions back to the current state.

Code:

IN-STATE
   <STATE.NAME.1>
CONDITION
   <WORD OR WORDS WHICH RETURN A TRUE/FALSE VALUE>
CAUSES
   <ACTION>
THEN-SAME-STATE
TO-HAPPEN

Note that there is nothing between THEN-SAME-STATE and TO-HAPPEN .
In this example, since a transition to a new state has not been specified, <STATE.NAME.1>'s parent machine will run <STATE.NAME.1> again.
Here is the new source.

Code:

CODE CELL+  ( ADR -- ADR+2 )
   ' 2+ @ LATEST NAME> ! \ Make CELL+ an alias for 2+
END-CODE

VARIABLE CFSM            \ Current Finite State Machine
VARIABLE DUMMY-STATE

: STATE-MACHINE  ( ++ )
   CREATE
      HERE CFSM !        \ Make new FSM current
      DUMMY-STATE ,      \ Set it to run DUMMY-STATE
      [ HERE CELL+ 2 ! ] \ Save address of DO.STATE.MACHINE
                         \ STC will need different offset
   DOES>
      @ @ ?DUP 0EXIT     \ If the current state's pointer
                         \ is zero, exit.
      ENTER              \ else enter the thread it points to.
      [ HERE DUMMY-STATE ! ] ;  \ DUMMY-STATE points to
                                \ a thread with EXIT .
                                
: ON-MACHINE  ( ++ )
   ' DUP @ [ 2 @ ] LITERAL <> 
   ABORT" NOT A STATE MACHINE"
   >BODY CFSM ! ;     \ Make named state machine current.

\ A machine state has three cells.
\ A pointer to threaded code to ENTER .
\ A pointer to its parent finite state machine.
\ A pointer to an address to patch.
: APPEND-STATE  ( ++ )       
   CREATE   ( ++ )           \ Create and add a new state
      HERE 0 ,  CFSM @ ,  ,  \ to the current FSM.
      [ HERE CELL+ 2 ! ]     \ Save address of DO.STATE
   ;CODE   ( -- SADR )       \ it's a jump to DO.VARIABLE
      ' FENCE @ JMP  END-CODE

: ?STATE  ( SADR -- )          \ compare PFA of a machine state
   BODY> @ [ 2 @ ] LITERAL <>  \ with address of do.state
   ABORT" NOT A STATE" ;       \ and abort if not a state.

: SET-STATE  ( SADR -- )
   DUP ?STATE        \ Confirm address is PFA of a state.
   DUP CELL+ @ ! ;   \ set parent machine to run this state.

: IS-STATE?  ( SADR -- )
   DUP ?STATE        \ Confirm address is PFA of a state.
   DUP CELL+ @ @ = ; \ fetch current state from machine
                     \ and compare

: IN-STATE  ( -- ) ;

: CONDITION  ( SADR -- SADR+4 )  \ Store HERE at patch
   DUP ?STATE                    \ address and leave address
   CELL+ CELL+ HERE OVER @ ! ] ; \ of third cell on stack.

: CAUSES  ( SADR+4 -- )
   COMPILE ?BRANCH  HERE SWAP!       \ Compile a branch to TCF
   [ ' DUMMY-STATE >BODY @ ] LITERAL \ with EXIT and make cell
   , ; IMMEDIATE                     \ after ?BRANCH the new
                                     \ patch address.
: THEN-STATE  ( -- TRUE )
   TRUE ; IMMEDIATE

: TO-HAPPEN  ( FLAG -- )
   IF  COMPILE SET-STATE  THEN
   COMPILE EXIT
   [COMPILE] [ ; IMMEDIATE

: THEN-SAME-STATE  ( -- FALSE )
   FALSE ; IMMEDIATE

I've added a new word to this syntax and made one of the useless words useful. Can anyone recommend useful additions or changes to this syntax which are compatible with the syntax for IsoMax presented in the New Micros IsoPod and ServoPod documents?

Top

IamRob

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sun Mar 17, 2024 6:09 am

Joined: Sun Apr 26, 2020 3:08 am
Posts: 357

One change I would make is change the word CONDITION to IF and the word CAUSES to THEN.

Or do you not like IF/THEN statements any more? Or are they not same?

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sun Mar 17, 2024 8:24 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

IamRob wrote:

One change I would make is change the word CONDITION to IF and the word CAUSES to THEN.

Or do you not like IF/THEN statements any more? Or are they not same?

That change would break the machine state transition. It would not work. I like IF THEN and the other control flow words just fine. These machine state transition words are not the same as IF and THEN .
Second, I did not devise this syntax. It is the syntax used in IsoMax for the IsoPod and ServoPod microcontrollers.

Code:

: IF  ( -- >SYS )
   COMPILE ?BRANCH
   >MARK ; IMMEDIATE
: THEN  ( >SYS -- )
   ?COMP >RESOLVE ; IMMEDIATE

Code:

: CONDITION  ( SADR -- SADR+4 )  \ Store HERE at patch
   DUP ?STATE                    \ address and leave address
   CELL+ CELL+ HERE OVER @ ! ] ; \ of third cell on stack.

: CAUSES  ( SADR+4 -- )
   COMPILE ?BRANCH  HERE SWAP!       \ Compile a branch to TCF
   [ ' DUMMY-STATE >BODY @ ] LITERAL \ with EXIT and make cell
   , ; IMMEDIATE                     \ after ?BRANCH the new
                                     \ patch address.

A machine state is created when it is appended to a finite state machine.

Code:

STATE-MACHINE M1
ON-MACHINE M1
   APPEND-STATE <MACHINE.STATE1>
             .
             .
   APPEND-STATE <MACHINE-STATEN>

This is a diagram of the state transitions for a machine state with three transitions defined. More transitions can be defined for a machine state at any time after the machine state is created.

Code:

\ TRANSITIONS FOR <MACHINE.STATE1>
   <MACHINE.STATE1>
      |
      V
   <TEST1>        ---> <TEST2>        ---> <TEST3>        ---> EXIT
   ?BRANCH >------     ?BRANCH >------     ?BRANCH >------
   <ACTION1>           <ACTION2>           <ACTION3>
   <MACHINE.STATE2>    <MACHINE.STATE3>    <MACHINE.STATE1>
   SET-STATE           SET-STATE           SET-STATE
   EXIT                EXIT                EXIT

The first transition is entered by <MACHINE.STATE1> and if the test returns a FALSE value, this transition branches to the next transition and so on.
The first transition with a test to return a TRUE value will execute all the words from the ?BRANCH to the EXIT shown at the bottom of the transition, skipping all the other transitions for this machine state. If none of the tests return TRUE, the last transition will branch on zero to the threaded code fragment with EXIT
Note that the different transitions could have a transition to any of the machine states for the parent finite state machine.
Notice that if a test returns false, not only does the action not take place, the transition to another machine state for this transition does not take place either.

When defining a state transition for a machine state, until CONDITION executes, the Forth system is interpreting. CONDITION does not compile any kind of branch. It takes the PFA of a machine state on the data stack. If this is the first transition being defined for this machine state, CONDITION will point the machine state to the start of this threaded code fragment. If this is not the first transition being defined for this machine state, CONDITION patches the ?BRANCH address from the previous transition for this machine state to point to the start of this threaded code fragment. It also leaves the address of the third cell of the machine state on the data stack for use by CAUSES .
CAUSES compiles a branch if zero out of the state transition into a threaded code fragment which contains an EXIT . If a new transition is added to a machine state, the branch if zero address will be patched to the start of the new transition for the machine state. As I said, there could be several of these transitions chained in this manner, the last branching on zero to the threaded code fragment with an EXIT . CAUSES also stores the address of its ?BRANCH address in the third cell of this machine state.

Brad Rodriguez has a copy of the manuals for the IsoPod and ServoPod on his website. In the head post I provided a link to the IsoPod users manual. That manual gives examples showing how to define finite state machines and their states and transitions.

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Thu Mar 21, 2024 12:55 am

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

I'll need to read the IsoPod manual again to see if the following is a feature or just a side effect of my implementation.
It is possible for one finite state machine to directly affect which machine state another machine will run.

Code:

STATE-MACHINE M1
ON-MACHINE M1
   APPEND-STATE GREEN.BORDER
   APPEND-STATE RED.BORDER

STATE-MACHINE M2
ON-MACHINE M2
   APPEND-STATE BUZZER
   APPEND-STATE CHIME

IN-STATE
   BUZZER
CONDITION
   <LOGIC TEST>
CAUSES
   <SOME ACTION>
THEN-STATE
   RED.BORDER
TO-HAPPEN

In this example, finite state machine M2's state BUZZER does not transition to another state (at least not with this transition). It does make the finite state machine M1 run machine state RED.BORDER when M1 next runs.

SET-STATE can also be used in the definition of a machine state's transition. If the machine state BUZZER did have a transition to another state, it could still make M1 run the machine state RED.BORDER when M1 next runs.

Code:

STATE-MACHINE M1
ON-MACHINE M1
   APPEND-STATE GREEN.BORDER
   APPEND-STATE RED.BORDER

STATE-MACHINE M2
ON-MACHINE M2
   APPEND-STATE BUZZER
   APPEND-STATE CHIME

IN-STATE
   BUZZER
CONDITION
   <LOGIC TEST>
CAUSES
   <SOME ACTION>
   RED.BORDER SET-STATE
THEN-STATE
   CHIME
TO-HAPPEN

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sun Mar 31, 2024 9:17 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

Here are the Finite State Machine Engine words for the background machine chain and words to install and uninstall machines. This version is for use without multitasking. The system still has PAUSE but the multitasker is not in use.
The background machine chain is the word (FSM) it is an ordinary colon definition with seventeen EXIT's the first sixteen are placeholders for machines or machine chains.

Code:

: (FSM)  ( -- )   \ Chain of finite state machines
   EXIT EXIT EXIT EXIT EXIT EXIT EXIT EXIT   \ 16 extra EXIT's
   EXIT EXIT EXIT EXIT EXIT EXIT EXIT EXIT ; \ as placeholders

: FSM  ( -- )   \ Set PAUSE to run (FSM) . No multitasking.
   ['] (FSM) IS PAUSE ;

The word FSM sets PAUSE to execute (FSM). This works if no machine state for any finite state machine contains words which will lead to the execution of PAUSE . The multitasker will be needed if some machine states need to execute words which may cause the execution of PAUSE .

Code:

#USER C/L +  \  Task user area + here & small pad
AP0 @ #41 -  \  Half of aux stack
SP0 @ #62 -  \  Half of data stack
RP0 @ #128 - \  Half of return stack
TASK BACKGROUND-MACHINE-CHAIN

: <FSM>  ( -- )
   BEGIN (FSM) PAUSE AGAIN ;

: FSM  ( -- )
   [ ' <FSM> >BODY ] LITERAL
   BACKGROUND-MACHINE-CHAIN ACTIVATE  \ Set task to run <FSM>
   BACKGROUND-MACHINE-CHAIN LINK-TASK \ and install task.
   MULTI ;                            \ Enable multitasker.

NO-MACHINES removes all machines and/or machine chains from the background machine chain.

Code:

: NO-MACHINES  ( -- )   \ Remove all machines and machine chains
   [ ' (FSM) >BODY ] LITERAL
   ['] EXIT OVER !      \ Fill all placeholders with EXIT .
   DUP 2+ #30 CMOVE ;

INSTALL parses the text stream for the name of a finite state machine, or finite state machine chain, and adds it to the background machine chain. Only sixteen machines or machine chains can be installed. If an attempt is made to install more than sixteen machines, or machine chains, INSTALL aborts with an error message.

Code:

: INSTALL  ( ++ )   \  Add machine or machine chain to first
   '                \  unused placeholder.
   [ ' (FSM) >BODY ] LITERAL #32 BOUNDS
   DO
      I @ ['] EXIT =
      IF   I ! UNLOOP  EXIT  THEN
   LOOP
   ABORT" 16 MACHINES INSTALLED" ;

UNINSTALL removes the last machine installed in the background machine chain. If an attempt is made to remove a machine, or machine chain, when there are none, UNINSTALL will abort with an error message.

Code:

: UNINSTALL  ( -- )   \ Remove machine or machine chain from
   ['] EXIT           \ last used placeholder.
   [ ' (FSM) >BODY ] LITERAL
   DUP #30 +
   DO
      DUP I @ <>
      IF  I !  UNLOOP EXIT  THEN
      -2
   +LOOP
   ABORT" NO MACHINES INSTALLED" ;

Here is a demo with two finite state machines installed.

Code:

VARIABLE SWITCH1
VARIABLE SWITCH2

STATE-MACHINE M1
ON-MACHINE M1
   APPEND-STATE GREEN.BORDER
   APPEND-STATE RED.BORDER

IN-STATE
   GREEN.BORDER
CONDITION
   SWITCH1 @  SWITCH2 @ AND
CAUSES
   GREEN BORDER
THEN-STATE
   RED.BORDER
TO-HAPPEN

IN-STATE
   RED.BORDER
CONDITION
   SWITCH1 @  SWITCH2 @ AND 0=
CAUSES
   RED BORDER
THEN-STATE
   GREEN.BORDER
TO-HAPPEN


STATE-MACHINE M2
ON-MACHINE M2
   APPEND-STATE BLACK.INK
   APPEND-STATE BLUE.INK
   
IN-STATE
   BLACK.INK
CONDITION
   SWITCH1 @ SWITCH2 @ XOR
CAUSES
   BLACK INK
THEN-STATE
   BLUE.INK
TO-HAPPEN

IN-STATE
   BLUE.INK
CONDITION
   SWITCH1 @ SWITCH2 @ XOR 0=
CAUSES
   BLUE INK
THEN-STATE
   BLACK.INK
TO-HAPPEN

RED BORDER
GREEN.BORDER SET-STATE

BLACK INK
BLUE.INK SET-STATE

INSTALL M1
INSTALL M2

Finite state machine M1 changes the border color, on a Commodore 64, to red if SWITCH1 is off or SWITCH2 is off. It changes the border color to green if they are both on.
Machine M2 changes the text color to blue if both switches have the same setting (on or off), and black if they differ.
This is an example of two finite state machines using the same inputs without interacting with each other. On a real Commodore 64 the machines would read inputs connected to actual hardware and set outputs to actual hardware.

When I first wrote this demo, I accidentally typed the following:

Code:

THEN-STATE
   BLUE INK
TO-HAPPEN

rather than the intended

Code:

THEN-STATE
   BLUE.INK
TO-HAPPEN

The error was not caught until runtime. One improvement to the Finite State Machine Engine would be having THEN-STATE parse for the name of a machine state and check to be sure the parsed name is a machine state. This would differ from IsoMax by requiring the name of the next state to be on the same line as THEN-STATE (or on the same screen on block based systems).

Code:

THEN-STATE BLUE.INK
TO-HAPPEN

I don't know how much IsoMax code used the pretty print format (vertical alignment), but this change would break it.

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Tue Apr 02, 2024 2:38 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

The modification mentioned in my previous post requires changing two words.

Code:

: THEN-STATE  ( ++ )
   ' DUP >BODY ?STATE ,
   COMPILE SET-STATE ; IMMEDIATE

: TO-HAPPEN  ( -- )
   COMPILE EXIT
   [COMPILE] [ ; IMMEDIATE

THEN-STATE parses for the name of a machine state and tests if it is really a machine state with ?STATE . The machine state is compiled along with the word SET-STATE . Because THEN-STATE parses, the name of the machine state must follow it on the same line (or be on the same screen when source is in Forth blocks).

Code:

IN-STATE
   GREEN.BORDER
CONDITION
   SWITCH1 @  SWITCH2 @ AND
CAUSES
   GREEN BORDER
THEN-STATE RED.BORDER
TO-HAPPEN

THEN-STATE is now optional. It is only needed if a machine state will transition to a different state. Because each state belongs to a specific finite state machine, THEN-STATE can also be used to set the next state for other machines. When used for this purpose, THEN-STATE can be used multiple times in a state transition.

Code:

IN-STATE
   GREEN.BORDER
CONDITION
   SWITCH1 @  SWITCH2 @ AND
CAUSES
   GREEN BORDER
THEN-STATE RED.BORDER
THEN-STATE AUDIO.TONE.ON   \ Machine states for different
THEN-STATE BLINK.LED       \ state machines.
TO-HAPPEN

TO-HAPPEN now only compiles EXIT and switches off compiling.

I should mention that the implementation I presented for the Finite State Machine Engine is for an Indirect Threaded Code Forth. It's also written for a Forth where the high level branch words, ?BRANCH and BRANCH are followed by an absolute address, not a relative offset as in some Forths.

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Wed Apr 03, 2024 5:33 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

The Finite State Machine Engine I wrote was not written in blocks of screens. I started with a (Linux) text file and started trying out some ideas. The source still has not been transferred to Forth block screens. I used the ability of VICE to paste source into the simulation. As I mentioned previously, Fleet Forth behaves as though the text is typed in. This does introduce a problem. When loading source from screens on blocks or even from a Commodore sequential file, an ABORT stops the load and returns control to Forth's QUIT loop. When text is pasted into the simulator the QUIT loop still has control. an ABORT stops interpreting text which has already been EXPECTed, or ACCEPTed; however, the simulator continues to fill the keyboard buffer until all pasted text has been inserted into the keyboard buffer. The behavior is exactly as if a programmer typing in source ignores errors and continues typing. Since the system's STATE is set to interpreting, words which were meant to be compiled will now be interpreted with possibly disastrous results.
Fleet Forth's ABORT , which is called by ABORT" , is extensible. It has the deferred word ERR .

Code:

: ABORT  ( -- )
   ERR SP! AP! QUIT -;

ERR is normally set to the no-op NOOP ;however, when pasting text into the simulation, I can set it to the word PURGE , which will purge (or consume) characters from the keyboard buffer until the buffer is empty for at least one sixtieth of a second. Since PURGE is only executed when an error occurs, it is not normally executed. When an error occurs, PURGE allows the system to handle the error as gracefully as when loading source from a screen in a Forth block or from a Commodore 64 sequential file. In other words, PURGE brings sanity to handling errors in source which is pasted into the simulator.

Code:

: KEY?  ( -- FLAG )  \ ANSI Forth standard word.
   #198 C@ 0<> ;     \ C64 implementation.

: PURGE  ( -- )      \ Empty keyboard buffer.
   BEGIN
      BEGIN
         KEY?        \ Any keystrokes?
      WHILE
         KEY DROP
      REPEAT
      1 JIFFIES      \ Wait 1/60th of a second.
      KEY? 0=        \ Is the buffer still empty?
   UNTIL ;

' PURGE IS ERR

After an error occurs, when the Commodore 64's cursor resumes its steady blinking I know the PURGE for this error is complete.

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sat Apr 06, 2024 12:38 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

One thing I don't think I mentioned is the virtually parallel machine architecture supported by IsoMax. When a state machine is run, it runs its current machine state and EXITs. The state machine needs executed again to either run the same machine state, if there was no transition to another, or the next state. This allows the state machines to run virtually in parallel.
The background machine chain, (FSM) , is just a colon definition with lots of EXITs for placeholders. When state machines M1 and M2 from my last example are installed, (FSM) looks like this:

Code:

SEE (FSM) 
(FSM)
 24794 25099 M1
 24796 25208 M2
 24798  2472 EXIT
6 
 OK

Without a forward branch in the colon definition, SEE will not show anything past the first EXIT .
When (FSM) is executed, state machine M1 runs its current state and exits. State machine M2 then runs its current state and exits. (FSM) then exits. As long as (FSM) continues to run in the background, M1 and M2 appear to run in parallel. For this to work, none of the machine states can have code that loops or branches backwards.
What about delays? IsoMax had counter variables created with the word -LOOPVAR . A -LOOPVAR is created with an initial value. Each time it is called it decrements that value until it is zero. It is then reset to the initial count. When the value is zero the -LOOPVAR returns a TRUE flag. When the value is not zero, a FALSE flag is returned.
As an example, I defined a -LOOPVAR named CNT and tested it interactively at the console.

Code:

3 -LOOPVAR CNT  OK
CNT . 0  OK
CNT . 0  OK
CNT . -1  OK
CNT . 0  OK
CNT . 0  OK
CNT . -1  OK
CNT . 0  OK
CNT . 0  OK
.S EMPTY  OK

Here is an example of a state machine, BLINK , with two states, GREEN.BORDER and RED.BORDER . GREEN.BORDER sets the border color to green an makes RED.BORDER the next state for the state machine BLINK . RED-BORDER sets the border color to red and makes GREEN.BORDER the next state for the state machine BLINK .

Code:

STATE-MACHINE BLINK
ON-MACHINE BLINK
   APPEND-STATE RED.BORDER
   APPEND-STATE GREEN.BORDER

IN-STATE
RED.BORDER
CONDITION
TRUE
CAUSES
RED BORDER
THEN-STATE GREEN.BORDER
TO-HAPPEN

IN-STATE
GREEN.BORDER
CONDITION
TRUE
CAUSES
GREEN BORDER
THEN-STATE RED.BORDER
TO-HAPPEN

GREEN.BORDER SET-STATE
INSTALL BLINK

This changes the border color fast enough that color bars appear to run up the screen.
Now to uninstall BLINK and forget it.

Code:

UNINSTALL
FORGET BLINK

Always make sure a state machine is NOT installed before forgetting it!
The next version of the state machine BLINK incorporates a -LOOPVAR named DELAY .

Code:

STATE-MACHINE BLINK
ON-MACHINE BLINK
   APPEND-STATE RED.BORDER
   APPEND-STATE GREEN.BORDER

200 -LOOPVAR DELAY

IN-STATE
RED.BORDER
CONDITION
DELAY
CAUSES
RED BORDER
THEN-STATE GREEN.BORDER
TO-HAPPEN

IN-STATE
GREEN.BORDER
CONDITION
DELAY
CAUSES
GREEN BORDER
THEN-STATE RED.BORDER
TO-HAPPEN

GREEN.BORDER SET-STATE
INSTALL BLINK

When this version of BLINK is installed, the delay between border color changes is about one second.
Here is the source for my version of -LOOPVAR .

Code:

: -LOOPVAR
    CREATE   ( U ++ )
       DUP , , 
    DOES>   ( -- FLAG )
       DUP @ 1- TUCK 
       DUP 0= 
       IF 
          DROP DUP 2+ @ 
       THEN 
       SWAP! 0= ;

Although the name -LOOPVAR leaves much to be desired, it is the name used in the IsoPod user manual.
Note: Some of you might be wondering what ( ++ ) means. It's a normal stack diagram but -- has been replaced with ++ to indicate this word parses. I don't recall where I saw this idea, but I like it.

[Edit: Corrected the stack diagram for -LOOPVAR . Since it is a CREATE DOES> word, it has two different stack diagrams, one is for -LOOPVAR itself and the other is for the child words of -LOOPVAR .]

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Sun Apr 14, 2024 9:33 pm

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

Note: I edited the previous post to show the correct stack diagrams for -LOOPVAR .

With the parsing version of THEN-STATE it is possible to factor out of SET-STATE the act of setting the state of a state machine.

Code:

: >STATE  ( SADR -- )
   DUP CELL+ @ ! ;   \ SET PARENT MACHINE TO RUN THIS STATE.

: SET-STATE  ( SADR -- )
   DUP ?STATE        \ CONFIRM ADDRESS IS PFA OF A STATE.
   >STATE ;          \ SET PARENT MACHINE TO RUN THIS STATE.

and compile this new word, >STATE , in the state transition.

Code:

: THEN-STATE  ( ++ )
   ' DUP >BODY ?STATE ,
   COMPILE >STATE ; IMMEDIATE

Since THEN-STATE tests the parsed word to determine if it is a machine state, the test does not need performed at run time in the state transition. >STATE can be compiled rather than SET-STATE .

Top

JimBoyd

Post subject: Re: A Finite State Machine Engine in Forth

Posted: Fri Apr 19, 2024 12:09 am

Joined: Fri May 05, 2017 9:27 pm
Posts: 851

My last finite state machine demo used a -LOOPVAR as a delay. A machine state of a finite state machine on a system with a virtually parallel architecture can not have a delay loop; hence -LOOPVARs.
Using PAUSE to run a chain of finite state machines in the background or using PAUSE to switch to a task to run the chain of finite state machines can result in different delay times between runs of the background chain.
While running that demo, if something like WORDS is run in the foreground, the delay between each run of the background chain of state machines will be longer than if the foreground is waiting for user input. For state machines which wait on external events to trigger a state transition, this isn't a problem (as long as the delay between running the background chain of machines is not so long that the system can not keep up with changing external events). From what I understand, this is not a problem with the Isomax or Isopod microcontrollers because the background chain of state machines is run by an interrupt.
With my Forth running on the Commodore 64, a -LOOPVAR doesn't work as well as a DOWN-COUNTER .
Here is the source for a finite state machine demo using a DOWN-COUNTER .

Code:

STATE-MACHINE BLINK
ON-MACHINE BLINK
   APPEND-STATE LT-RED.BORDER
   APPEND-STATE RED.BORDER

DOWN-COUNTER DELAY

IN-STATE
   LT-RED.BORDER
CONDITION
   DELAY @ 0<
CAUSES
   #5 DELAY !
   LT-RED BORDER
THEN-STATE RED.BORDER
TO-HAPPEN

IN-STATE
   RED.BORDER
CONDITION
   DELAY @ 0<
CAUSES
   #53 DELAY !
   RED BORDER
THEN-STATE LT-RED.BORDER
TO-HAPPEN

RED.BORDER SET-STATE
INSTALL BLINK

Note that the same DOWN-COUNTER can be used with each machine state while giving each of the two states a different wait time.
Also note that DELAY is tested to see if its value is less than zero, so a value one less than the actual delay is used.

Top

Page 1 of 1

[ 13 posts ]

Board index » 6502.org Users Forum » Forth

All times are UTC

Who is online

Users browsing this forum: No registered users and 15 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum