Finite State Machines Implementation

bmentink · 2008-08-12 21:24

Hi All,

I would like to implement finite state-machine execution tables in Spin, but I see no way of getting pointers to methods, does this mean this is not possible?

What I would like to implement is the following:

A 2-dimentional table who's horiz axis is indexed by inputs 0..n, and who's vertical axis is states 0..n.
Each cell in the table would hold a pointer to an output method and a pointer to a transition method, a FSM method given an input event would look up the correct
cell in the table and execute the output method then the transition method (which would update the state variable).

This sort of efficient FSM handling is easy to do in Forth (You can create a compile word that creates FSM tables .. see Julian Noble's paper)
but if we can't get pointers to methods, then I believe this is a serious deficiency in spin.

Maybe someone knows how this can me achieved in assembly?

Thanks.

Peter Verkaik · 2008-08-12 21:30

Instead of pointers, use integer values.
Then use a CASE to call the routine assigned to the used integer value.

regards peter

bmentink · 2008-08-12 21:52

Hi Peter,

That method is very messy, slow and hard to follow , I am looking to do this direct with method pointers. I want to create a table like this:

Input: | 0 | 1 | 2 |
state:

0 out1 -->2 out4 -->0 out2 -->1
1 out1 -->1 out6 -->0 out0 -->2
2 etc

The "outn" methods should be more descriptive names, the "-->n" are descriptive method names showing what state is transitioned to for that combination of input and current state.

Hope this is clear, you can't represent this "self documenting" clear table with integers and a case statement.

Cheers,
Bernard

Peter Verkaik · 2008-08-12 22:01

I understand what you would like, but there are no pointers to methods.
In spin, you must emulate those pointers with integer values. Each value
represents a method. The code that reads the table, uses the integer value
to call the appropiate method.
In assembly you can of course store the address of a method,·and
call that address using selfmodifying code.

regards peter

jazzed · 2008-08-12 22:12

Theoretically speaking: Spin has no direct provision for using function pointer calls. However it has been found that there is no "object" bounds checking, and you can use that to define functions to be called on an index basis. The actual implementation will not be very pretty (function pointers never are really), but it should be do-able.

CON
  ' theoretical function pointer call example
  
OBJ
  ob[noparse][[/noparse]1]  : "object"
  ob1    : "object1"
  ob2    : "object2"
  ob3    : "object3"
 
PUB main
  repeat ii from 0 to 3
    call(ii)
 
PUB call(index)
  ob[noparse][[/noparse]index].function

All objects in such an example of course will require a method named function. I've never actually tested this mainly for having no real reason to try [noparse]:)[/noparse] Maybe you can follow up with results if you try it.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔

Carl Jacobs · 2008-08-12 22:41

As mentioned by Bernard, state machines are quite easy to do in Forth. It's a bit harder in JDForth,·being a compiled Forth·but here is an example of how it could be done:

VAR16 current_state
VAR32 state_table -1 ALLOT
      0 , 0 , 0 ,
      0 , 0 , 0 ,
      0 , 0 , 0 ,
   
: out1 "1" emit ;
: out2 "2" emit ;
: out3 "3" emit ;
: out4 "4" emit ;
: out6 "6" emit ;
: out0 "0" emit ;
 
: --> ( addr func next -- aadr+4 )
  16 << or swap 1 cells + tuck ! ;
 
: init_state_table
  state_table 
  [noparse][[/noparse]'] out1 2 -->   [noparse][[/noparse]'] out4 0 -->   [noparse][[/noparse]'] out2 1 -->
  [noparse][[/noparse]'] out1 1 -->   [noparse][[/noparse]'] out6 0 -->   [noparse][[/noparse]'] out0 2 -->
  [noparse][[/noparse]'] out3 1 -->   [noparse][[/noparse]'] out2 0 -->   [noparse][[/noparse]'] out2 2 -->
  0 current_state!
;
 
: next_state ( state -- )
  current_state@ 3 cells *   \ Go to the current state
  cells +                    \ Add the offset to the new state
  state_table + @            \ Get the state table information
  dup execute                \ Execute the state word
  16 >> current_state!       \ Change to the new state
;  
 
\ To use it
: demo
  init_state_table
  0 next_state 2 next_state 2 next_state
  1 next_state 2 next_state 1 next_state
;

In this way it would be quite easy to have·state-machine type operation in one cog (the JDForth cog) and still have your spin objects in the other cogs.

If this comes up often enough, then it may be worthwhile extending the compiler to recognise the word ,' or the 16 bit variant H,' which could then be used to make the state table at compile time. As per:

\ NOT YET SUPPORTED BY JDFORTH - JUST A CONCEPT VAR32 state_table -1 allot
   H,' out1 2 H,  H,' out4 0 H,  H,' out2 1 H,
   H,' out1 1 H,  H,' out6 0 H,  H,' out0 2 H,
   H,' out3 1 H,  H,' out2 0 H,  H,' out2 2 H,

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Carl Jacobs

JDForth - Forth to Spin Compiler http://www.jacobsdesign.com.au/software/jdforth/jdforth.php·

bmentink · 2008-08-13 00:38

Hi Carl,

Your implementation is quit messy still and not flexible enough to have the transition execute code as well as changing state. I have implemented Julian Nobles FSM for amforth, it works like this:

 : one ." one " ;
 : two ." two " ;
 : three ." three " ;
 : four ." four " ;
 : nop ." nop " ;

 0 constant >0
 1 constant >1
 2 constant >2

\ a test state-machine table  
 4 wide fsm: test_fsm 
\ input:  |  0      |  1      |   2    |     3     |
\ state:  ---------------------------------------------
    ( 0 )     nop >0    one >1   one >1     two >2
    ( 1 )     four >1    one >1   nop >1     two >2
    ( 2 )     nop >2    two >2   nop >2     nop >2 ;

It is used then as " 1 test_fsm 3 test_fsm" etc etc ..... nice and clean.

The transition words ">0" etc don't have to be constants, they can be normal 4th words performing some action, as long as they leave a state variable on the stack.
Hey Carl, when are you going to make JDForth a proper forth interpreter/compiler? I would be the 1st one to use it then. It is the interactiveness of forth that I like, being able to
interactively test words as you build up to the final word, that and being able to extend the compiler is Forth's main strength IMHO.

Jazzed, your example makes absolutely no sense to me at all, sorry!

Carl Jacobs · 2008-08-13 01:44

Hi Bernard,

I'm sorry that you didn't notice that my implementation does execute code as well as change state. Although the code you've presented looks "clean", you have not shown your word fsm: which would have in essence the same functionality performed by my word next_state - It really just moves the "messiness" (or algorithm)·from one place to another.

I'm not planning at any stage to turn the compiler into a interpreting compler, but I am planning to release a version later this year that allows the compilation of interprative environments. Personally I probably wont use the interprative environment - the edit-compile-run cycle being more than quick enough for me (even with just spin).

I guess my primary goal is a faster language that allows easy inclusion of PASM words without consuming extra cogs. It's probably not going to please·everyone, but it has been designed·as a direct result of the needs that I've personally experienced while programming with the Propeller chip.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Carl Jacobs

JDForth - Forth to Spin Compiler http://www.jacobsdesign.com.au/software/jdforth/jdforth.php·

bmentink · 2008-08-13 02:12

Hi Carl,

Still missing it. In your "init_state_table" word and the line "[noparse][[/noparse]'] out1 2 --> "
the "2" seems to be a number not a function. In my example the >2 is a function (forth word), this allows exit code to be written before changing state,
this is a function that is called " in addition" to the action word (in your example out1).

I didn't include the fsm: code, because I didn't think it was relevant since it was written for amforth, but here it is:

\ This word creates FSM transition tables
: fsm:   ( width -- )
      create  0 >ram  ,  ,   ]     \ ram addr of state stored in dict,also width.
      does>               ( col# adr -- )
      dup dup >r i2@  @  * rot + ( -- col#+width*state )
      2* + 1+ 1+       ( -- offset-to-action)
          dup >r           ( -- offset-to-action)
          perform          ( ? )
          r> 1+            ( -- offset-to-update)
          perform          ( -- state')
          r>  i@ !  ;       \ update state

Carl Jacobs · 2008-08-13 02:29

Hi Bernard,
I'm sorry, I did misread your initial post. Oh well, I guess it could be written as:

VAR16 current_state
VAR32 state_table -1 ALLOT
      0 , 0 , 0 ,
      0 , 0 , 0 ,
      0 , 0 , 0 ,
   
: out1 "1" emit ;
: out2 "2" emit ;
: out3 "3" emit ;
: out4 "4" emit ;
: out6 "6" emit ;
: out0 "0" emit ;
 
: ->0 0 current_state! ;
: ->1 1 current_state! ;
: ->2 2 current_state! ;
 
: | ( addr func next -- addr+4 )
  16 << or swap 1 cells + tuck ! ;
 
: init_state_table
  state_table 
  [noparse][[/noparse]'] out1 [noparse][[/noparse]'] ->2  |  [noparse][[/noparse]'] out4 [noparse][[/noparse]'] ->0  |  [noparse][[/noparse]'] out2 [noparse][[/noparse]'] ->1 
  [noparse][[/noparse]'] out1 [noparse][[/noparse]'] ->1  |  [noparse][[/noparse]'] out6 [noparse][[/noparse]'] ->0  |  [noparse][[/noparse]'] out0 [noparse][[/noparse]'] ->2 
  [noparse][[/noparse]'] out3 [noparse][[/noparse]'] ->1  |  [noparse][[/noparse]'] out2 [noparse][[/noparse]'] ->0  |  [noparse][[/noparse]'] out2 [noparse][[/noparse]'] ->2 
  drop
  0 current_state!
;
 
: next_state ( state -- )
  current_state@ 3 cells *   \ Go to the current state
  cells +                    \ Add the offset to the new state
  state_table +              \ Get the state table information
  dup H@ execute             \ Execute the state word
  2+  [url=mailto:H@6]H@[/url] execute            \ Execute the state transition word
;  
 
\ To use it
: demo
  init_state_table
  0 next_state 2 next_state 2 next_state
  1 next_state 2 next_state 1 next_state
;

If placed in a file, most of the words could be surrounded with <PRIVATE PRIVATE>, and the internal mechanism of the state-machine could then be protected. The shortcut word proposed in my earlier post would·still be of benefit, and it would be possible to include the width and current state of the state machine as part of state_table at the expense of slightly more tricky control words.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Carl Jacobs

JDForth - Forth to Spin Compiler http://www.jacobsdesign.com.au/software/jdforth/jdforth.php·

ChrisCantrell · 2015-05-06 16:28

I added this object to the OBEX. It allows you to declare a state machine in a DAT section and support functions in SPIN. The runner ties the two together and manages the state transitions.

http://obex.parallax.com/object/816

The declaration syntax is a bit clunky, but it works. Here is an example state from the Soda Machine demo in the object archive:

S15
word "##!##", FN_showDeposit, 15
word "##NICKEL##", @S20
word "##DIME##", @S25
word "##QUARTER##", @S25, FN_refundDime, "%%", FN_refundNickel
word "@@"

S20
word "##!##", FN_showDeposit, 20
word "##NICKEL##", @S25
word "##DIME##", @S25, FN_refundNickel
word "##QUARTER##", @S25, FN_refundDime, "%%", FN_refundDime
word "@@"

Tapperman · 2015-05-07 10:49

bmentink wrote: »

Maybe someone knows how this can me achieved in assembly?

Thanks.

Hum, I have my own variant [post=1326203]here[/post]. State [post=1326389]table[/post] its built from.

... Tim

Finite State Machines Implementation

Comments