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.