Finite State Machine and Forth
Paul F. Sehorne
Several years ago, I programmed a FORTH single board computer to control my
home air conditioning. Recently I pulled out an old hardcopy of the source
and got to thinking about implementing it as a FSM (just as an exercise).
If FSMs are feasible under FORTH it might affect future applications that I
write in FORTH.
Any ideas, white-papers or web pages you could point me to, or sample
source that address this subject (not FSM in general, but specifically
under FORTH).
I have never written using FSM, but several years ago (about 1993) I
attended a half-day session on the subject and could see its benefits. A
couple of years later I debugged a DBase application the used FSM; so I was
able to see a real program implemented as a FSM and was impressed with how
it simplified the logic (fewer IF...ELSE...THENs). But I have never
written FSM myself. This past weekend I found several papers and sample
source that addressed FSM under C and C++. What is available for FORTH?
Thanks for you input....
Paul
Greg Alexander
I'm probably especially ignorant, but FSM doesn't mean anything to me beyond
face value. Your machine is (ideally) a finite state machine. It is a
machine and it has a finite number of states. It has a finite amount of
RAM, both inside and outside the processor, it has a finite number of bus
states. Of course, it isn't ideal and it's made to work around that (i.e.,
signal transition times from logical 1 to 0), but, overall, it's a finite
state machine.
I assume you mean some type of small-state-machine?
--
Greg Alexander - also <gale...@indiana.edu> - http://sietch.ml.org/~galexand
----
"I think you bipeds have a catchphrase for it: ``To thine own self be true,
...'' though like a blind man's shadow, the second half is only there for
those who know it's missing. Merely a dog, I'll tell you what it is: ``...
as if you had a choice.''"
-- William Mathews in "Homer's Seeing-Eye Dog"
Paul F. Sehorne
> I'm probably especially ignorant, but FSM doesn't mean anything to me
beyond
>
FSM (Finite State Machine) is a way to implement a program that defines (in
C an array of structures that are composed of the following four elements)
1) the states a program can be in
2) events that can happen
3) actions to be taken when a program is in a particular state and
receives a specific event
4) the next state the program is to transition to
For instance in my air conditioning program I could define the following
four states
1) comfortable (a/c, heater, and fan are all off)
2) heating (heater and fan are on)
3) cooling (a/c and fan are on)
4) waiting (on compressor pressure to stabilize)
and the following circumstances ( I will interpet these as events below)
1) the temperature is above a comfortable level (78 degrees ? )
2) the temperture is below a comfortable level (68 degrees ?)
3) 5 minute timer fires
Then for each state I define what action to take when any event (that is
interesting ) for that state happens:
1) state, comfortable:
a) event #1, temperature is above 78
action = fan on, a/c on, heater off
next state = heating
b) event #2, temperature is below 68
action = fan on, a/c off, heater on
next state = cooling
2) state, heating
a) event #1, temperature is above 68
action = fan off, a/c off, heater off
next state = comfortable
3) state, cooling
b) event #1, temperature below 78
action =fan off, a/c off, heater off
next state = waiting
4) state, waiting
a) event, 5 minute timer expires
action = none
next state = comfortable
The 'heating' state is only interested in whether or not the temperature is
above 68 and it can only exit to the 'comfortable' state.
The 'cooling' state is only interested in whether or not the temperature is
below 78 and it can only exit to the 'waiting' state (to protect the
compressor).
The 'waiting' state only responds to one event, the timer, and only exits
to the 'comfortable' state.
The 'comfortable' state can go to either 'heating' or 'cooling' depending
on whether the temperature is below 68 or above 78.
In C, you would use code similar to (pseudo code more or less)
/* define a pointer to a funciton */
typedef void (*pf)()
/* define a structure to contain a single instance of a State/Event */
struct FSMStruct {
int CurrentState;
int Event;
int NextState;
pf Action;
}
/* Create an array of the above structures, one for each combination of
State/Event of interest. In the above example I was interested in 5
specific combinations of State/Event */
FSMstruct MyStates = [5];
The C code would then react to an event by searching the structures for a
combination that matched the CurrentState and the Event that just occurred.
This method of programming results (in may cases) in less use of logical
branching, fewer lines of code, and less opportunity for logic errors.
By providing this explanation, I already see ways that I can improve on my
original version of the program. But I'm still looking for help in exactly
how to code this in FORTH.
Thanks,
Paul
Paul F. Sehorne
were backwards for the two events:
This
1) state, comfortable:
a) event #1, temperature is above 78
action = fan on, a/c on, heater off
next state = heating <== should be 'cooling'
b) event #2, temperature is below 68
action = fan on, a/c off, heater on
next state = cooling <== should be 'heating'
Should be
1) state, comfortable:
a) event #1, temperature is above 78
action = fan on, a/c on, heater off
next state = cooling
b) event #2, temperature is below 68
action = fan on, a/c off, heater on
next state = heating
Bart Lateur
>Anyone have any experience prgramming a finite state machine under FORTH?
Yes, I did something like that once. I built a large scale chrono timer.
I doubt if it's the neatest approach possible, but here is basically how
I did it:
* Each "state" is an endlessly repeated sub. Once in a while, besides
doing useful stuff (like updating the screen), it did check the inputs
(three buttons), converted it to a "next state" using a translation
table, and exited the sub if it had to go to a next state, while keeping
that next state (xt) in a variable. If the result of that check was
zero, the sub repeated.
* There's a main endless loop, that goes to the next state, and than
repeats. Compare to "QUIT".
Basically:
: MAIN BEGIN NEXT-STATE @ EXECUTE AGAIN ;
Ugly, but it works. I'm still not sure how to improve on it.
The alternative would be clearing the return stack, and jumping to the
address of the next state.
: GOTO ( state-address ) >R ;
Bart.
Julian V. Noble
> Anyone have any experience prgramming a finite state machine under FORTH?
Yes, and I have written an article for JFAR about it. Also one in Computers
in Physics. I use 'em all the time for decision-avoiding programming.
It is much easier in Forth than other languages. See my article
in JFAR (online url http://www.jfar.org/) v. 7.
If you would like some sample code, e-mail me.
--
Julian V. Noble
j...@virginia.edu
"Elegance is for tailors!" -- Ludwig Boltzmann
Paul F. Sehorne
on it, the means to implement FSM in FORTH are formulating.
For instance, a pointer to a function is a FORTH WORD.
The FSM could be implemented as a CASE statement in C and this may
translate well into FORTH:
VARIABLE CURRENTSTATE
0 CONSTANT COMFORTABLE
1 CONSTANT HEATING
2 CONSTANT COOLING
3 CONSTANT WAITING
COMFORTABLE CURRENTSTATE !
WHILE(1) {
SWITCH(CURRENTSTATE)
CASE COMFORTABLE
IF TEMP>78
FAN-ON HEAT-OFF A/C-ON
COOLING CURRENTSTATE !
IF TEMP<68
FAN-ON HEAT-ON A/C OFF
HEATING CURRENTSTATE !
CASE HEATING
IF TEMP<78
FAN-OFF HEAT-OFF A/C-OFF
COMFORTABLE CURRENTSTATE !
CASE COOLING
IF TEMP<68
FAN-OFF HEAT-OFF A/C-OFF
START TIMER
WAITING CURRENTSTATE !
CASE WAITING
TIMER-EXPIRED? IF COMFORTABLE CURRENTSATE !
END SWITCH}
}
Right now I have to go to work, I will evolve this more this evening.
Paul F. Sehorne <pau...@ibm.net> wrote in article
<01bdfbc1$97748e20$0200a8c0@psehorne>...
> Anyone have any experience prgramming a finite state machine under FORTH?
>
> Several years ago, I programmed a FORTH single board computer to control
my
> home air conditioning. Recently I pulled out an old hardcopy of the
source
> and got to thinking about implementing it as a FSM (just as an exercise).
> If FSMs are feasible under FORTH it might affect future applications that
I
> write in FORTH.
>
> Any ideas, white-papers or web pages you could point me to, or sample
> source that address this subject (not FSM in general, but specifically
> under FORTH).
>
> I have never written using FSM, but several years ago (about 1993) I
> attended a half-day session on the subject and could see its benefits. A
> couple of years later I debugged a DBase application the used FSM; so I
was
> able to see a real program implemented as a FSM and was impressed with
how
> it simplified the logic (fewer IF...ELSE...THENs). But I have never
> written FSM myself. This past weekend I found several papers and sample
> source that addressed FSM under C and C++. What is available for FORTH?
>
Bart Lateur
Julian V. Noble wrote:
>> Anyone have any experience prgramming a finite state machine under FORTH?
>
>Yes, and I have written an article for JFAR about it. Also one in Computers
>in Physics. I use 'em all the time for decision-avoiding programming.
>
>It is much easier in Forth than other languages. See my article
>in JFAR (online url http://www.jfar.org/) v. 7.
Is this code actually tested? The next lines look wrong.
: TUCK COMPILE UNDER ; \ ANS compatibility
: WIDE ; \ NOOP for clarity
: CELLS COMPILE 2* ; \ ANS compatibility
: CELL+ COMPILE 2+ ; \ ANS compatibility
: PERFORM COMPILE @ COMPILE EXECUTE ; \ alias
All these words should be IMMEDIATE . Well, only for WIDE it doesn't
matter.
: FSM: ( width -- ) CREATE , ]
DOES> ( n adr -- )
TUCK @ mystate @ * + CELLS CELL+ +
( adr') PERFORM ;
Bart.
Philip Preston
: DEFER ( <spaces"name"> -- ) CREATE ['] ABORT ,
DOES> ( -- ) @ EXECUTE ;
: IS ( xt <spaces"name"> -- )
' >BODY STATE @ IF
POSTPONE LITERAL POSTPONE !
ELSE
!
THEN ; IMMEDIATE
: HEATER-ON ( -- ) ... ;
: HEATER-OFF ( -- ) ... ;
: A/C-ON ( -- ) ... ;
: A/C-OFF ( -- ) ... ;
: FAN-ON ( -- ) ... ;
: FAN-OFF ( -- ) ... ;
: TOO-HOT? ( -- flag ) ... ;
: TOO-COOL? ( -- flag ) ... ;
: TIME-UP? ( -- flag ) ... ;
DEFER BE-COMFORTABLE
DEFER BE-HEATING
DEFER BE-COOLING
DEFER BE-WAITING
: COMFORTABLE ( -- )
TOO-HOT? IF
FAN-ON A/C-ON HEATER-OFF BE-COOLING
ELSE
TOO-COOL? IF
FAN-ON A/C-OFF HEATER-ON BE-HEATING
THEN
THEN ;
: HEATING ( -- )
TOO-COOL? 0= IF
FAN-OFF A/C-OFF HEATER-OFF BE-COMFORTABLE
THEN ;
: COOLING ( -- )
TOO-HOT? 0= IF
FAN-OFF A/C-OFF HEATER-OFF BE-WAITING
THEN ;
: WAITING ( -- )
TIME-UP? IF
BE-COMFORTABLE
THEN ;
DEFER MY-STATE
:NONAME ['] COMFORTABLE IS MY-STATE ; IS BE-COMFORTABLE
:NONAME ['] HEATING IS MY-STATE ; IS BE-HEATING
:NONAME ['] COOLING IS MY-STATE ; IS BE-COOLING
:NONAME ['] WAITING IS MY-STATE ; IS BE-WAITING
: MY-FSM ( -- )
FAN-OFF A/C-OFF HEATER-OFF BE-COMFORTABLE
BEGIN MY-STATE ( PAUSE ) AGAIN ;
John Brien
from "Paul F. Sehorne" <pau...@ibm.net> contains these words:
> For instance in my air conditioning program I could define the following
> four states
> 1) comfortable (a/c, heater, and fan are all off)
> 2) heating (heater and fan are on)
> 3) cooling (a/c and fan are on)
> 4) waiting (on compressor pressure to stabilize)
VALUE Comfortable
VALUE Heating
VALUE Cooling
VALUE Waiting
> and the following circumstances ( I will interpet these as events below)
> 1) the temperature is above a comfortable level (78 degrees ? )
> 2) the temperture is below a comfortable level (68 degrees ?)
> 3) 5 minute timer fires
> Then for each state I define what action to take when any event (that is
> interesting ) for that state happens:
> 1) state, comfortable:
> a) event #1, temperature is above 78
> action = fan on, a/c on, heater off
> next state = heating
> b) event #2, temperature is below 68
> action = fan on, a/c off, heater on
> next state = cooling
:NONAME temperature 78 > IF fan on a/c on Cooling EXIT THEN
temperature 68 < IF fan on, heater on Heating EXIT THEN
Comfortable ; TO Comfortable
> 2) state, heating
> a) event #1, temperature is above 68
> action = fan off, a/c off heater off
> next state = comfortable
:NONAME temperature 68 > IF fan off heater off Comfortable EXIT THEN
Heating ; TO Heating
> 3) state, cooling
> b) event #1, temperature below 78
> action =fan off, a/c off, heater off
> next state = waiting
:NONAME temperature 78 < IF fan off a/c off Waiting EXIT THEN
Cooling ; TO Cooling
> 4) state, waiting
> a) event, 5 minute timer expires
> action = none
> next state = comfortable
:NONAME wait-timer Comfortable ; TO Waiting
> By providing this explanation, I already see ways that I can improve on my
> original version of the program. But I'm still looking for help in exactly
> how to code this in FORTH.
: Program heater off a/c off fan off Comfortable
BEGIN EXECUTE AGAIN ;
Each State, whatever its exit, leaves another on the stack to be
executed next time round the loop. What could be simpler?
--
Jack Brien
Prove all things - hold fast to that which is good (1 Thessalonians 5:21)
http://www.users.zetnet.co.uk/aborigine/forth.htm
Home of the FIG UK website
Philip Preston
(snip)
>VALUE Comfortable
>VALUE Heating
>VALUE Cooling
>VALUE Waiting
>:NONAME temperature 78 > IF fan on a/c on Cooling EXIT THEN
> temperature 68 < IF fan on, heater on Heating EXIT THEN
> Comfortable ; TO Comfortable
>:NONAME temperature 68 > IF fan off heater off Comfortable EXIT THEN
> Heating ; TO Heating
>:NONAME temperature 78 < IF fan off a/c off Waiting EXIT THEN
> Cooling ; TO Cooling
>:NONAME wait-timer Comfortable ; TO Waiting
>: Program heater off a/c off fan off Comfortable
> BEGIN EXECUTE AGAIN ;
>
>Each State, whatever its exit, leaves another on the stack to be
>executed next time round the loop. What could be simpler?
>
Very neat! Definitely a technique to remember.
Philip Preston.
Marcel Hendrix
> The message <01bdfbe6$2ca06180$0200a8c0@psehorne>
> from "Paul F. Sehorne" <pau...@ibm.net> contains these words:
[ .. ]
>> For instance in my air conditioning program I could define the following
>> four states
>> 1) comfortable (a/c, heater, and fan are all off)
>> 2) heating (heater and fan are on)
>> 3) cooling (a/c and fan are on)
>> 4) waiting (on compressor pressure to stabilize)
> VALUE Comfortable
> VALUE Heating
[ .. good code .. ]
> Each State, whatever its exit, leaves another on the stack to be
> executed next time round the loop. What could be simpler?
Normally each state, *combined* with all inputs, leads to the next state.
Generally, each of the states has a specific output. The implementation
is done with tables. Of course, each FSM can be written in 'normal'
style Forth, often becoming *much* better readable. However, the FSM will
automatically make sure each possible state has code attached to it (at
least the programmer is forced to make a decision before testing starts).
This is an advantage for real-time programs and protocol implementation.
The following program is 12 years old, and partly in Dutch. See how much
Forth evolved...
-marcel
=======
\ (* ********************************************************** *) /
\ (* G E L D W I S S E L M A C H I N E *) /
\ (* Author: Marcel Hendrix, April 28th 1986. *) /
\ (* Descrp: Experiment met Mealy-machine voor geldwisselen. *) /
\ (* CR: Rieks Joosten, Vijgeblad #13 *) /
\ (* LC: September 18th 1988, converted to IBM *) /
\ (* ********************************************************** *) /
FORTH DEFINITIONS DECIMAL
REVISION -coinvender "--- CoinVending Machine, Vsn 1.20 ---"
#10 VALUE #wissel \ Aantal guldens in voorraad
4 =: #Inputs
&o >< &g OR =: OuweF \ OudeGulden
&n >< &g OR =: NieuweF \ NieuweGulden
&m >< &e OR =: Monteur
: SOUND \ <Lengte> <freq>
?DUP
IF $10 UMAX
$FC07 8 ROT UM/MOD \ Calculate interval
$B6 $43 PC! \ Set intialize mode.
DUP $42 PC! >< $42 PC! \ Output interval
$61 PC@ 3 OR $61 PC! \ Switch on.
DROP ( mod )
ENDIF
0 ?DO $80 0 DO LOOP LOOP \ Delay.
$61 PC@ $FC AND $61 PC! ; \ Switch off.
#40 VALUE blen \ burp length
#64 VALUE fhigh \ burp frequency
: BURP blen fhigh CHOOSE fhigh + SOUND ;
: RINKELEN #10 0 DO BURP LOOP ;
: GETKEY KEY $20 OR ( upcase ) DUP EMIT ; \ <> --- <key>
: INPUT ?AT 0 #23 AT EOL ." ? " #wissel
0= IF -1 +TO #wissel 3
ELSE GETKEY >< GETKEY OR
DOCASE OuweF CASE 0
ELSE NieuweF CASE 1
ELSE Monteur CASE ABORT
ELSE DROP 2
ENDCASE
ENDIF
-ROT AT ;
: WisselGeld CR ." Munten: 25 25 25 5 5 5 5 5 " \ Wisselgeld
RINKELEN ;
: InworpRetour EOL ." Inworp retour. " BURP \ Inworp <--
#50 WAIT ?AT UNDER 0 SWAP AT EOL ;
: LampAan CR BLINK \ Lampje Aan
." Sorry, er is geen wisselgeld meer. "
-BLINK CR ;
: OUTPUT DOCASE 0 CASE WisselGeld -1 +TO #wissel
ELSE 1 CASE InworpRetour
ELSE DROP LampAan
ENDCASE ;
0 VALUE status \ 2 Toestanden Genoeg/Niet genoeg wisselgeld
CREATE delta 0 C, 0 C, 0 C, 1 C, \ Inputs+state->state
1 C, 1 C, 1 C, 1 C,
CREATE omega 0 C, 0 C, 1 C, 2 C, \ Inputs+state->output
1 C, 1 C, 1 C, 2 C,
: WISSELMACHINE CLS
BEGIN status #Inputs * INPUT +
DUP omega + C@ OUTPUT
delta + C@ TO status
AGAIN ;
: .HELP CR
CR ." Starten met WISSELMACHINE " CR
CR ." Het machien verwacht twee-letterige opdrachten: "
CR ." -- OG staat voor 'oude gulden'"
CR ." -- NG staat voor 'nieuwe gulden'"
CR ." -- ME staat voor 'monteur'"
CR ." Dit ding heeft een ijzeren geheugen: Op is OP!"
CR ;
.HELP
\ (* End of Source *) /
Julian V. Noble
> [mailed and posted]
>
> Julian V. Noble wrote:
>
> >> Anyone have any experience prgramming a finite state machine under FORTH?
> >
> >Yes, and I have written an article for JFAR about it. Also one in Computers
> >in Physics. I use 'em all the time for decision-avoiding programming.
> >
> >It is much easier in Forth than other languages. See my article
> >in JFAR (online url http://www.jfar.org/) v. 7.
>
> Is this code actually tested? The next lines look wrong.
>
> : TUCK COMPILE UNDER ; \ ANS compatibility
> : WIDE ; \ NOOP for clarity
> : CELLS COMPILE 2* ; \ ANS compatibility
> : CELL+ COMPILE 2+ ; \ ANS compatibility
> : PERFORM COMPILE @ COMPILE EXECUTE ; \ alias
>
> All these words should be IMMEDIATE . Well, only for WIDE it doesn't
> matter.
Yes. They were added for compatibility with F-PC at some late date
and the IMMEDIATE got left off (probably by me).
The following is the way I do it in ANS:
\ code to create state machines from tabular representations
: || ' , ' , ; \ add two xt's to data field
: wide 0 ; \ aesthetic, initial state = 0
: fsm: ( width state --) \ define fsm
CREATE , ( state) , ( width in double-cells) ;
: ;fsm DOES> ( x col# adr -- x' )
DUP >R 2@ ( x col# width state)
* + ( x col#+width*state )
2* 2 + CELLS ( x relative offset )
R@ + ( x adr[action] )
DUP >R ( x adr[action] )
PERFORM ( x' )
R> CELL+ ( x' adr[update] )
PERFORM ( x' state')
R> ! ; ( x' ) \ update state
\ set fsm's state, as in: 0 >state fsm-name
: >state POSTPONE defines ; IMMEDIATE ( state "fsm-name" --)
: state: ( "fsm-name" -- state) \ get fsm's state
'dfa \ get dfa
POSTPONE LITERAL POSTPONE @ ; IMMEDIATE
0 CONSTANT >0 3 CONSTANT >3 6 CONSTANT >6 \ these indicate state
1 CONSTANT >1 4 CONSTANT >4 7 CONSTANT >7 \ transitions in tabular
2 CONSTANT >2 5 CONSTANT >5 \ representations
\ end fsm code
Here is an example of a FSM used to check for duplicate operators in
a formula (they are typos):
: op_op_err TRUE ABORT" Can't have repeated operators!" ;
2 wide fsm: (op_op)
\ input: | other | +-*/^ |
\ state: --------------------------
( 0) || 1+ >0 || 1+ >1
( 1) || 1+ >0 || op_op_err >6
;fsm
: ~op_op ( end beg --) \ check for duplicate operators
BEGIN DUP C@ [token] 9 14 WITHIN ABS (op_op)
2DUP < UNTIL 2DROP ;
The word [token] is a translation table that produces contiguous
numbers for various sets of input characters (avoids lots of
comparisons).
The FORmula TRANslator code (latest version) and other (possibly)
interesting code is available at the URL:
http://erwin.phys.virginia.edu/classes/551/
Paul F. Sehorne
a couple of readings and reflexion to digest it all
(snip)
> > Julian V. Noble wrote:
> > >,,, I have written an article for JFAR about it (FORTH and Finite
State Machine) . Also one in Computers in Physics. I use 'em all the time
for decision-avoiding programming.
(snip)
Paul F. Sehorne
(both here and via email). I am well on my way now...
Paul F. Sehorne <pau...@ibm.net> wrote in article
<01bdfbc1$97748e20$0200a8c0@psehorne>...
> Anyone have any experience prgramming a finite state machine under FORTH?
(snip)
>
> Any ideas, white-papers or web pages you could point me to, or sample
> source that address this subject (not FSM in general, but specifically
> under FORTH).
>
(snip)