state machine in spin?

sssidney

I’ve been trying to implement a table driven state machine in spin. When I do this in C I use function pointers for the transition routines.

Here’s the C struct I typically use to define the state table

typedef struct
{
  StateType curState;
  EventType event;
  StateType nextState;
  TransFnctPtr fnctPtr;                /* the function pointer */
}StateMachine_t;

So my state table is just an array of these structures.

StateMachine_t exStateMachine[noparse][[/noparse]] = {
  {
    INITIAL_STATE,
    HELLO_EVENT,
    STARTUP_STATE,
    startFnct
  },
  {
    STARTUP_STATE,
    DEV_OK_EVENT,
    IN_USE_STATE,
    waitForDataFnct
  },
/* etc... */
};

I can get by the lack of structs in spin by using an array and offsets to make the state table. My problem is the lack of a function pointer. I could substitute another constant for the function pointer and then have a huge case statement to execute the proper transition routine but that’s pretty ugly. Anyone have a better idea? Maybe I need to trash the C way of thinking about this and start fresh with a spin POV?

Post Edited (sssidney) : 6/8/2010 1:29:54 PM GMT

Dave Hein

In theory, function pointers can be implemented by manipulating the object's method table.· It's fairly straight-forward if all of the methods are in the same object.· However, I think the cleanest way to do it in Spin is to use a case statement or lookup.· The lookup may be the quicker technique, but I haven't timed it.

StefanL38

maybe I have only a very basic understanding of statemachines

I'm only familiar with delphi as a PC programming language. Your C-construct seems to be pretty complicated for me

A microcontroller is much smaller than a PC. You don't have a n-layer model and you don't use eventdriven programming like in windows where each application has dozens of threads.


What's so "huge" about a case-statement like this?

CON
  InitialState = 1
  State2       = InitialState + 1 
  State3       = State2 + 1 
  State4       = State3 + 1 


VAR
  long State

  
PUB StateMachine

  case State  
    InitialState: Method1
    State1: Do1
    State2: Do2
    State2: Do3
    State2: Do4


PUB Method1
...

PUB Do1
...

PUB Do2
...

PUB Do3
...

PUB Do4
...

best regards

Stefan

heater

StefanL38: "A microcontroller is much smaller.....and you don't use event driven programming like in windows where each application has dozens of threads."

Do what? This is the Prop we are talking about. We have at least a max of 8 event driven threads to play with. There are already micro-controllers around with far more.

However I agree with you, for the scale of program you are likely to be creating on the Prop that case based state machine is just fine. Not ugly at all.

On might argue the performance is not so hot unless the Spin compiler is smart enough to build a jump table for the cases rather than a string of "if casex.. if casey.. ifcasez...".

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

Timothy D. Swieter

I've used case statements to create state machines on the Propeller. I don't think the state machines I've created are fancy, but the structure and code setup I use has evolved over several projects. I'll have to find an example that I am able to post.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter, P.E.
www.brilldea.com - Prop Blade, LED Painter, RGB LEDs, 3.0" 16:9 LCD Composite video display, eProto for SunSPOT, PropNET, PolkaDOT-51
www.tdswieter.com

Ray0665

Take a look at my object "mother of all led sequencers" in the object exchange.
granted it is not a true state machine but the similarities are unavoidable.
heres a link
http://obex.parallax.com/objects/240/

Attached below is a possible stripped state demo in spin

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Never force anything - Always get a bigger hammer.

Post Edited (Ray0665) : 6/9/2010 12:17:33 AM GMT

sssidney

I think some of you are underestimating what can be done on a prop with a little work. Just a fairly simple state diagram like the some I’ve included can turn into more than 20 transitions.

I was just wondering if someone had discovered a cool method of doing a state machine other than using a case statement.

heater

What has the number of transitions got to do with it?

Any transition can be decided within the method that handles the current state. Just like one might do it in C.

So for only 20 states or so Stefan's case statement method is quite neat no matter how many ways there are to get from state to state.

There is a limit to the number of "arms" a Spin case statement can handle though. I don't remember what it is off hand.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

localroger

In Spin you're pretty much stuck with CASE statements. Yeah, the Spin interpreter has to check each one in turn. Spin explicitly does not provide for any mechanism to insert a program run point in a variable and call it. You might have noticed it doesn't have GOTO or line labels, which are both kind of a prerequisite for that sort of thing.

If you have a ridiculously large number of cases you can use a mothership CASE statement to break the condition down into ranges, and range CASE statements to refine the search.

sssidney

The number of transitions will definitely effect the maintainability of the state machine. I guess we'll have to agree to disagree on how neat (and maintainable) it would be using a case statement. Also in a reasonable size state machine having each individual transition routine manage the state is IMO a potential nightmare. In my job I've had to write state machines with hundreds of transitions to handle very complex situations so I've spent a lot of time designing a mechanism to handle them. I guess my strong opinions on the subject stem from this experience.

TinkersALot

In state machines I have done in the past, there was an object/method/code-chunk that implemented a singular node/state within the machine.

There was a top level manager/variable that kept track of the current state. This top level manager would select a object/method/code-chunk and capture the 'exit signal' from that execution.

Each state node would eject an "exit signal" when it finished running.

There was a collection of transition definitions that mapped the tuple formed by the current state + exit signal to a new state. This new state would be assigned to the top level manager/variable.

With this approach, each state handler knew nothing about the machine it was node of. The real mainteance point in the implementation was the implementation of the "edge mapping table" that would convert the input-state + exit code to a new state value.

I hope this explanation is not too obtuse and/or is helpful to somebody.

Timothy D. Swieter

sssidney - I'm interested in learning more about your experience and your code structure.



For overall discussion I will paste the code formats that I have been using. I'm interested to see how it could be improved. In general the state machines that I have coded have been synchronous loops. That is a loop that goes through the state machine, one pass at a state, every x milliseconds - usually 20 or 30ms.

First - a couple definitions in the CON section:

  '***************************************
  ' State Definitions
  '***************************************
  'Definitions of states so names are used instead of numbers

  StateInit     = 01            'Initialization Immediately run at startup
  StateOps1     = 10            '
  StateOps2     = 20            '
  StateOps3     = 30            '
  StateOps4     = 40            '
  StateConfig   = 50            'Config

  StateError    = 99            'Error

  'State flags
  FlagFirstPass   = |< 1        'Signal that this is the first pass through the state (1 = first pass, 0 = not first pass)
  FlagSyncSkip    = |< 2        'Signal that the synchronous delay should be skipped once (1 = skip, 0 = sync)
  FlagSyncEnable  = |< 3        'Signal that the synchronous delay is enabled or disabled (1 = enabled, 0 = disabled)
  FlagX           = |< 4        'A misc. flag
  Flagy           = |< 5        'A misc. flag
  Flagz           = |< 6        'A misc. flagthe state

  
  '***************************************
  ' Misc Definitions
  '***************************************

  _framerate    = 30              'Number of frames per second for state machine
  _duration     = 1000/_framerate 'Calculate milliseconds

Next, a few variables:

  'State Machine Related
  [b]byte[/b]  StatePrev               'Track the previous state of the state machine                        
  [b]byte[/b]  StateCurrent            'Track the current state of the state machine
  [b]byte[/b]  StateNext               'Track the next state for the state machine
  [b]byte[/b]  StateStored             'The state as recalled from the EEPROM
  
  [b]long[/b]  StateTicks              'A counter that increments with the framerate and is reset at each state change
  [b]long[/b]  StateFlags              'Various flags to indicate status or cause action

Next is the main routine:

'***************************************
[b]PUB[/b] main | loopDLY, loopTMR
'***************************************
'' First routine to be executed in the program
'' because it is first PUB in the file

  '**************************************
  ' Initialize the variables
  '**************************************
  
  'Initialize the sate machine with the first state
  StatePrev := StateInit 
  StateCurrent := StateInit
  StateNext := StateInit
  StateTicks := 0
  StateFlags |= FlagFirstPass
  
' StateFlags &= !FlagSyncEnable                         'disable the sync loop
  StateFlags |= FlagSyncEnable                          'enable the sync loop

  'Capture cnt for a synchronous delay and calculate the delay
  StateFlags |=   FlagSyncSkip
  loopDLY := (clkfreq / 1_000 * _duration)

  '**************************************
  ' Begin
  '**************************************

  'Inifinite loop begins
  [b]repeat[/b]

    'This is where the synchronous delay occurs, if allowed.  Other code
    'can turn this off as needed for longer processing times in certain
    'portions of the state machine.
    [b]if[/b] (StateFlags & FlagSyncEnable)                    'if enabled, process
      [b]if[/b] (StateFlags & FlagSyncSkip)                    'if skipping
        StateFlags &= !FlagSyncSkip                     'clear the flag
        loopTMR := [b]cnt[/b]                                  'setup the loop timer again
      [b]else[/b]
        [b]waitcnt[/b](loopTMR += loopDLY)                     'execute the synchronous delay

    'Button check code would go here (calling data from another cog doing debounce and other processing of presses)
  
    'Process the state activity
    [b]case[/b] StateCurrent
    
      StateInit     : StateInitRun                      'Initialization
      StateOps1     : StateOps1[b]Run[/b]                      '
      StateOps2     : StateOps2[b]Run[/b]                      '
      StateOps3     : StateOps3[b]Run[/b]                      '
      StateOps4     : StateOps4[b]Run[/b]                      '
      StateConfig   : StateConfigRun                    '

      StateError    : StateErrorRun                     'Error
      '...
      [b]other[/b]         : StateErrorRun                     'Error

    'Check the flags and do an special processing

    'Increment timers/counters
    StateTicks++

    'Clear any flags that need to be cleared per loop

    'Check for changing states and process appropriately
    [b]if[/b] StateCurrent <> StateNext
      'Move the state variables around
      StatePrev := StateCurrent
      StateCurrent := StateNext

      'Reset any counters and flags
      StateTicks := 0       
      StateFlags |= FlagFirstPass

      'Set the flag to save the value to EEPROM
      StateFlags |= FlagStoreValue

  [b]return[/b] 'end of main

Then after this are the various PUB and PRI subroutines such as:

'***************************************
[b]PRI[/b] StateInitRun
'***************************************
'' Initialize
'' Set the various devices to their default values
'' and start the appropriate cogs

  'Only execute on first pass through this state
  [b]if[/b] (StateFlags & FlagFirstPass)

    'Clear the flag, if code below fails, it could set
    'the flag to execute again if desired.
    StateFlags &= !FlagFirstPass

    '**************************************
    ' Start the processes in their cogs
    '**************************************

    'Start the cogs for handling UI, communication, etc

    '**************************************
    ' Initialize the variables
    '**************************************

    'Set default values, call values from EEPROM or SD card

     
    'Skip the time sync
    'This may be needed because the above operations may have taken a while, especially if you read/write to EEPROM
    StateFlags |= FlagSyncSkip
    '-----------------------

  StateNext := StateOps1

  [b]return[/b] 'end of StateInitRun

'***************************************
[b]PRI[/b] StateOps1[b]Run[/b]
'***************************************
'' Start up the device

  'Only execute on first pass through this state
  [b]if[/b] (StateFlags & FlagFirstPass)

    'Clear the flag, if code below fails, it could set
    'the flag to execute again if desired.
    StateFlags &= !FlagFirstPass

    'Do any items that you want to do only the first time into this state

    '-----------------------

  'Advance once enough time has passed
  [b]if[/b] stateticks == 50
    StateNext := StateOps2

  [b]return[/b] 'end of StateOps1Run

Now - you can advance from one state by an event that happens in each state. You have to write IF structures. I have a somewhat fancy button/UI code which is inaddition to the above items. There is a comment where I normally place the calls to button processing code. I'll save that bit of code for later.

Tell me what you think of the above.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter, P.E.
www.brilldea.com - Prop Blade, LED Painter, RGB LEDs, 3.0" 16:9 LCD Composite video display, eProto for SunSPOT, PropNET, PolkaDOT-51
www.tdswieter.com

StefanL38

Hello Sidney,

Sidney said...

Also in a reasonable size state machine having each individual transition routine manage the state is IMO
a potential nightmare.
In my job I've had to write state machines with hundreds of transitions to handle very complex situations

Why should be "each individual transition routine manage the state is IMO a potential nightmare" ????

To me this fact that each transistion sets the next state is one of the substancial things about stae-machines.

How does a statemachine work where NOT EVERY transistion-routine changes the state?

To be provocant: To me this sounds like spaghetti-code by avoiding gotos ! ; ; - )

How do you want to keep oversight of who is doing what in your code when at the end of each state the new state is NOT set????

maybe you have found a brilliant way how to code huge statemachines but I can't imagine a tiny bit of how this should work

so please give an example

best regards

Stefan

sssidney

Sure. These are rules I’ve learned and live by when I write state machines. I’ve learned these by having to trace my way through code that I’ve inherited from other programmers. Basically the “programmers gold rule” – don’t do to the next poor schmuck what this guy is doing to you.

So in the same vein as what TinkersALot said in their post in the state machines I write the currentState is only changed in one place in the main event loop and is selected using the combination of currentState value and the return value of the transition routine based on the state table data. currentState becomes the value of nextState from the selected transition struct.

Some other design rules for state machines I try to live by:

I like to implement my state table as data and keep the state machine infrastructure/code static i.e. when I need to add new states I just add the needed data to define the transitions and then write the transition routines. I can’t figure out how to do this in spin without function pointer capability so the case statement is necessary.

Don’t allow your transition routines to modify the next state variable. This becomes a nightmare looking for how you transitioned from state to state. Build it into the state transition data structure (or arrays in spin).

Unless the state is a “steady state” always have a timeout associated with it. You never want to get stuck in a transitory state. Have a timeout on each of these transitions and have an error handler routine to call if the timeout occurs.

Keep debug counters for state transition success and failures. This is good postmortem data.


While in debug mode have the routine that finds the appropriate next transition validate your state table.

So adding more detail to my state transition data structure:

typedef struct
{
  StateType curState;
  EventType event;
  StateType nextState;
  TransFnctPtr fnctPtr;                /* the function pointer */
  TransFnctPtr errFnctPtr;      /* the error handler function pointer – called if the transition routine fails. NULL if not needed. */
  int timeout;             /* timeout to load for next transition.  NO_TIMEOUT if not needed. */
  long flags;             /* describe the attributes of this state */
#ifdef  DBG_STATE_TRANSITIONS
  int dbgCounters;        /* used to keep stats during tests. Typically success, failure, etc. */
#endif
}StateMachine_t;

Post Edited (sssidney) : 6/10/2010 2:29:33 PM GMT

heater

Sidney and StefanL38: In a complex state machine one can move the selection of next state out of the individual state handlers.

That is to say it is not necessary for each state handler to know how it is connected in the state graph and it is not necessary to have a tangled mess of "if bla bla" in each state handler to determine the next state

This can be done by placing the state graph into some data structure, probably parallel arrays in Spin as it has no structures as such.

Each state handler function returns some indication of what has happened within that state. The state machine loop then uses that indication to determine the next state based on the current state, the indication returned from the handler and data in the state graph structure.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

sssidney

heater - exactly!

Timothy D. Swieter

So, if am following this conversation, what you are saying is that the code from my example above such as:

  StateNext := StateOps1

or

  'Advance once enough time has passed
  if stateticks == 50
    StateNext := StateOps2

wouldn't be in the state code area where it is? In its place would be some sort of data manipulation into an array?

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Timothy D. Swieter, P.E.
www.brilldea.com - Prop Blade, LED Painter, RGB LEDs, 3.0" 16:9 LCD Composite video display, eProto for SunSPOT, PropNET, PolkaDOT-51
www.tdswieter.com

heater

Yes indeed Timothy.

As a simple example. Let's say you have a state that checks for a charcter, or not, from a serial line. Using FullDuplexSerial One might write:

PUB someStateHandler
  c : = ser.rxtcheck
  if c == -1
     NextState := NoCharState
  else
     NextState := GotCharState
return NextState

Now this can be a mess as this state handler has to know where it is in the state transition diagram. That is it has to know about "NoCharState" and "GotCharState" and it has to know and decide which one of those states to go to next. The state "graph" is hard coded into the handlers.

How can we make it a bit more flexible? What about removing the info about next state from it and having it just return some indication of the event it has detected.

PUB someStateHandler
  c : = ser.rxtcheck
  if c == -1
     event := 0
  else
     event := 1
return NextState

Now we can put that state handler in any position in the state machine. We can fix the logic of the transitions without touching the method code. We can possibly use it in more than one state.

BUT where is the state transition map now?

Well lets invent a method "selctNextState", say. It will use the current state, the event and some data tables to determine the next state.

nextState := selectNextState(currentState, event)

We call this every time around the event loop somewhere.

So now the connectivity of our state machine is in some data structure used by selectNextState rather than hardwired into our code.

The nature of that data structure is an exercise for the reader[noparse]:)[/noparse]

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
For me, the past is not over yet.

TinkersALot

Heater, your illustration lines up well with what I attempted to explain....The mantra is "loose coupling" of the event handlers. Your observations and ease of adopting state machine mechanics using a loosely coupled set of state handlers and how that can aid re-use is spot on!

Dave Hein

I wanted to post this a couple of days ago but I couldn't find the thread on callbacks from a few months ago.· I stumbled across it today searching for something else.· The thread is located at http://forums.parallax.com/showthread.php?p=886844 .· I posted some code that implements a·method call based on an index.· A slightly simpler version is shown below.

This code modifies the object's method table so that a dummy method points at the desired function based on an index.· The method table consist of a long for each public method followed by a long for each private method in an object.· The long contains the method's address offset and the space used for the local stack variables.

This code is quite straight-forward as long as all the methods are in the same object.· It becomes a bit more complex if they are in different objects.· You would have to worry about the VAR offset, and you would have to modify Spin byte codes instead of just changing the method table.

Dave

CON
  _clkmode = XTAL1 + PLL16x
  _xinfreq = 5_000_000
  
obj
  ser : "fullduplexserial"
 
CON
  ' Define an index for each PUB method
  main_index = 1
  sub1_index = 2
  sub2_index = 3
  sub3_index = 4
  CallMethod_index = 5
  ' Define an index for each PRI method
  DummyMethod_index = 6
  
PUB main
  ser.start(31, 30, 0, 19200)
  waitcnt(clkfreq*5+cnt)
  CallMethod(sub1_index)
  CallMethod(sub2_index)
  CallMethod(sub3_index)
  
PUB sub1
 ser.str(string("sub1", 13))
 
PUB sub2
 ser.str(string("sub2", 13))
 
PUB sub3
 ser.str(string("sub3", 13))
 
PRI DummyMethod
 
PUB CallMethod(Method_index)
  long[noparse][[/noparse]@@0][noparse][[/noparse]DummyMethod_index] := long[noparse][[/noparse]@@0][noparse][[/noparse]Method_index]
  DummyMethod 

·

BradC

Dave Hein said...
I
This code modifies the object's method table so that a dummy method points at the desired function based on an index. The method table consist of a long for each public method followed by a long for each private method in an object. The long contains the method's address offset and the space used for the local stack variables.

I've look at a few ways of doing this, but always bump up against the same issue. None of this stuff is thread safe. As long as your code will never execute in more than one cog it's ok though.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"I mean, if I went around sayin' I was an emperor just because some moistened bint had lobbed a scimitar at me they'd put me away!"

Dave Hein

CallMethod could set a lock on entry, and each method that could be called would have to clear the lock on entry.· It could be done without locks by using an array of 8 DummyMethod's.· However, you would then need a case statement·indexed off of·cogid to figure out which DummyMethod to call.

The two techniques could be combined having 8 extra CallMethod's as well.· CallMethod would set a lock, and then configure the table entry for DummyMethod for CallMethod0, CallMethod1, etc.· It would then call CallMethod, whcih would indirectly call the correct version of CallMathodX.· This would clear the lock and then call the target method.· It's messy, but it would work.

BradC

Ugly and messy, but yes, it will work.
I have an idea for a jump table in SPIN, but I need some more time to get into the internals of the interpreter to see if its feasible first.

There's no way to do a jmp in spin that's not hard coded, but you can push an address on the stack (along with some other cruft) and use one of the portions of case or lookup/dn to jump to it (a bit like a buffer overflow exploit). If I can make the compiler generate constant 2 byte addresses (it uses 1 or 2 depending on the offset size), I *think* I could make an instruction along the lines of..

gosubtbl(index,method1,method2,method3,method4...)

If you overflowed the table, then you're in the hands of the big sky bully though.
I've also not really figured the parameter passing yet, but all the referenced methods would require the same numbers of parameters.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"I mean, if I went around sayin' I was an emperor just because some moistened bint had lobbed a scimitar at me they'd put me away!"