-
Finite state machines (FSM) are one of the bedrocks of computing.
You define your problem with states and then come up with rules to progress from one state to another.
You can have outputs that get generated with any state transition, or you can just do something useful with the states.
States can be things like offline, online, failure, waiting for a closing parenthesis, pause, whatever.
For instance, we can make a flip-flop using four states, A, B, C, D and one input Ck.
You can diagram this out yourself.
if you wrote this in C:
switch(state)
{
case A:
if (ck==1) then state=B;
break;
case B:
if (ck==0) then state=C;
break;
case C:
if (ck==1) then state=D;
break;
case D:
if (ck==0) then state=A;
break;
}
Ok, that was the introductory material.
There's a bunch of problems with this.
It's cumbersome to do all these switch cases (and this is a simple case).
What if you want a reset? Do you have to put a reset clause in each switch case?
Things can get quickly complicated.
Your inputs could be much more complicated than a single bit.
Some of the inputs could have the same effect even for a few different states.
There are numerous ways besides switch cases to do the mechanics of an FSM.
You could just make it a look-up table that you use the state and any inputs as the address and read out the next state (and maybe an output or two).
So (I'm eventually getting to the point) my idea of a source code to FSM generator is:
Use a table addressed by state and input, delivering next state and outputs.
Initialize this table to all states being stable (i.e. A->A, B->B, etc)
Initialize this table to no outputs for any state.
Our flip flop would have 4 rules.
(A, ck=1) -> B, (B, ck=0) -> C, (C, ck=1) -> D, (D, ck=0) -> A
Ok, that is a simple example, so there is no great benefit.
Where this gets the benefit is that rules overwrite whatever is in the table.
There is never a conflict between rules, they just write the table as they go along.
If after those 4 rules we have (*, ck=0, res=1) -> A, (*, ck=1, res=1) -> B
We have added a reset without an explicit if to each of our 4 original rules.
Notice that the first 4 rules depend on state and ck and that the last 2 rules just depend on ck and res.
You could view that as a don't care. Or you could sit down and figure explicitly the action for every single combination of state and input.
We would like our source code to be these simple 6 rules. We want the output to be a table.
Question, are there any existing tools to do this?
-
There are many existing tools to convert a "readable" definition of an FSM into executable code in a standard language. Some are proprietary and some are open source. Some have been used for misson-critical behaviour. Some contain a complete runtime environment, some are embedded code fragments. One of the better known and more accessible tools is http://smc.sourceforge.net/ (http://smc.sourceforge.net/)
All such tools have the significant problems and benefits associated with tiny domain-specific language (DSL). A useful question is whether it is better to simply write the code in a standard HLL using a recognised design pattern.
One such design pattern is:
- each state maps onto a separate OOD class
- each event maps onto a separate method implemented by the classes
- the current state is a singleton instance of one of the state classes
- substates are modelled by the corresponding class hierarchy
- the abstract superclass of all state classes contains methods for every event, with an implementation that aborts execution becauses that method should never be executed
- every event is handled where appopriate in the state classes
- eventA is executed by invoking currentState.eventA(), and state transtions are currentState = aStateClassInstance
-
Thanks for the pointer to SMC, it's interesting.
I guess that I was thinking of lighter weight things than making everything a class.
The classic FSM doesn't really "do" transitions in the sense that it only has its states and outputs.
If you plumb internally into the FSM you can have it do something on a state transition.
In old-skool FSM you can only flag an output to tell something external to do something.
You end up writing an FSM then you have to write something to decode the FSM's outputs and do something.
The table method I was speaking of is an efficient way of specifying/implementing old-skool FSM.
I do write enough standard switch(state), do something, next state code for other things, mostly task-based.
-
Classes aren't, on their own, heavyweight. They are no more than a sparse table of function pointers, arranged in a way that matches the way the specification is written. In many cases there is only one instance of the class, containing the state in the form of a variable of the class that matches the state. In other cases, e.g. a telephone exchange, there is one instance per call.
The table method is very applicable when the FSM is sparse and unlikely to change over time. I've used that technique to convert incoming characters into a float or double number, or to convert from one 5-channel paper tape code to another.
FSMs must have transitions from one state to another. Whether or not you should "do" something as part of the transition is an orthogonal decision. I have found that to be unnecessary in practice, and an "unnecessary" complexity of Harel Statecharts (i.e. UML state diagrams).
In one company where I worked, a main product was effectively a runtime with an enormous if-then-else statement doing the control. Over a decade it had become a monstrosity, and the simplest change took 6 months from request to acceptance. A significant part of the problem was that the if statements were nested up to 10 deep. That made it impossible to be sure exactly which line had to be changed, and that the change didn't cause a new problem. Totally braindead, of course - in that and other ways!
Nonetheless, I've seen distant echoes of that problem in all but the simplest if-the-else based state machines.
-
Well, in any case, even before I posted the first post I had already written something.
My need was for a bunch of char stream FSM.
I have the input definition in XML.
It generates:
- Char map to input index
- State/input array generates state/output
- Stub function to wrap it all
-
https://automl.org ?
also scikit-learn ?
-
https://automl.org ?
Ich mag Hannover.
Actually, I wrote it all myself, or was this a suggestion?
-
I was just speculating that automated tools (not necessarily these ones) are rapidly evolving which might be able to take a body of inputs and desired outputs and prodice a blob that would give you the deired outputs from the same inputs and when you provided a new input guess at an approriate output or vice versa..
gradually infer the rules needed to do so.
However it might screw up perhaps spectacularly, or interestingly, once in a while.
-
I was just speculating that automated tools (not necessarily these ones) are rapidly evolving which might be able to take a body of inputs and desired outputs and prodice a blob that would give you the deired outputs from the same inputs and when you provided a new input guess at an approriate output or vice versa..
gradually infer the rules needed to do so.
However it might screw up perhaps spectacularly, or interestingly, once in a while.
The problem with such machine learning techniques is that you cannot know why they work.
Classic simple case from the early 80s was a machine to distinguish cars from tanks it worked well in the lab,but failed dismally in real world tests. Eventually they realised the training set was pictures of tanks on Luneberger Heath and cars from adverts. Yes, it was distinguishing sunny days from cloudy days.
Nowadays nothing so crude would happen; it would be more subtle, and classified as a transient glitch (that killed or maimed people).
-
It is important to have anything that is automatically generated to give a bit of insight into its logic.
That's why my program throws in some comments.
static uint8_t code_fsm[]=
{
// EOL * /
0x00, 0x07, 0x00, 0x14, // IDLE
0x00, 0x07, 0x20, 0x40, // PREFIX
0x20, 0x23, 0x30, 0x20, // OPEN
0x20, 0x23, 0x20, 0x02, // SUFFIX
0x40, 0x03, 0x40, 0x40 // LINE
};
-
It is important to have anything that is automatically generated to give a bit of insight into its logic.
Please convince the people that regulate Elon Musk's toys of the value of that :(
-
Elon Musk
OT:
This guy is a master in selling himself and his words. Now NASA has still a lot of problems with the new Orion missions, and that fellow is already talking about selling tickets for five days of kind of Holiday-something around the moon like if it was a kind of Disneyland amusement park.
Well, before the Moon landing, Neil Armstrong Saved NASA when in one of the Gemini missions almost the whole crew fainted due to still immature technology combined with the effect of spaceflight on the human body. Almost everybody passed out except Neil Armstrong, who, with the spacecraft and crew seemingly in peril, needed to act fast.
He remembered what he was said "[..] if you run into trouble and the control system fails [..] just…turn it off and take control with the spacecraft.", and thank god he didn't pass out, he remembered these words, and he fixed the problem.
Now somehow everything must be AI-driven, and this kind of stuff now sounds the perfect job for an on board AI that doesn't "pass out" like humans, but we need to be careful with AI autonomous choices!
And even electrical systems may fail, or worse still have malfunctions, and the AI itself can take the wrong decision, like we have already seen in science fiction when the super advanced HAL 9000 went nuts and decided to kill the crew.
edit:
typo "to go nuts"
-
And even electrical systems may fail, or worse still have malfunctions, and the AI itself can take the wrong decision, like we have already seen in science fiction when the super advanced HAL 9000 went nut and decided to kill the crew.
You missed the point of the story. HAL 9000 didn't go nuts, it operated exactly as instructed. And that's the exact problem with expert systems in general.
-
You missed the point of the story. HAL 9000 didn't go nuts, it operated exactly as instructed. And that's the exact problem with expert systems in general.
I am not sure about that.
The AI received instructions, but not a precise order "kill the crew". It deducted (for a malfunctioning? or for a logical mistake in its programming?) that the crew was "expendable" due to of two considerations:
- completing the mission had the highest priority (this idea is also represented in the first Alien movie)
- on board human life was not necessary to be guaranteed, because the spaceship was built able to autonomously complete the mission
HAL-9000 is science fiction, but how a similar AI-driven autonomous machine like the one Elon Musk is thinking about will react to a serious malfunction or something when it will drive a couple of tourists (aka inexpert civil persons, and not pro-astronauts) on holiday around the moon?
Like Neil Armstrong during the Gemini-8 mission? Better than him? Or worse than him?
-
The AI received instructions, but not a precise order "kill the crew". It deducted (for a malfunctioning? or for a logical mistake in its programming?) that the crew was "expendable" due to of two considerations:
I don't see any error in the deduction – so no malfunction, no logical mistake. (If you place yourself in HAL's position, all its actions are logical and in line with its directives.)
The only mistake is on part of humans who believe a simple set of instructions suffices. It does not; humans base their actions on a huge, unseen context, that they have developed during their lifetime. A large part of crew selection is to find the individuals whose such contexts are suitable for the task at hand. When you realize this, you realize why AI and expert systems are so hard: the integrated context that controls actions when decisions need to be made, is absolutely massive.
how a similar AI-driven autonomous machine like the one that "should" take a couple of tourists on holiday around the moon will react to a serious malfunction or something?
It is much simpler to develop an expert system to do a task no humans are currently doing, than to create an expert system that behaves like a human would.
The error is in expecting to be able to define the operating rules for such a system in human terms, or model it after human actions.
-
If we circle back to the original topic from my last sentence in my previous post, I do believe that finite state machines – in general terms – fall into a similar category as expert systems: human-conversational rules do not suffice.
Instead, I believe the best option is to use a domain-specific descriptive language, which can be used to generate the state machine code at one hand, and the human-readable documentation on the other hand.
Personally, I would use Python for the translation, as its associative arrays (dict type) are quite performant, and are well suited for the intermediate description of the state machine. This way, it should be possible to run full state machine traces (fully map all states and transitions) to verify each transition and each state – in particular, to find states that lead to uninterruptible cycles or dead ends. (For this, one can use graph theory, although path tracing and detecting already visited states should suffice.)
Then, the question is, what should that descriptive "language" look like. That's the hard question here.
Personally, I prefer a declarative structure, where a keyword at the start of a line defines the rest of the line, and a new state always begins with a line defining its identity (abstract ID, or human-readable name, used to refer to that state). Whether that works better than any others, I do not know; I only know that it maps well to an associative-array-based description of graphs, and is fast and robust to parse.
-
An interesting decision point is whether states have specific, pre-assigned values.
Inputs have defined values, outputs have defined values.
You could make things so that the numeric value of a state is not assigned and not used at all outside the FSM.
States would simply be collected and assigned an arbitrary value during compilation.
The one semi-exception would be initial state or you could use an explicit reset input.
-
States would simply be collected and assigned an arbitrary value during compilation.
Yes; I tend to use the address of the structure (in ROM/Flash) describing the state. The reason you need some sort of an identifier or name is so that you can refer to it from the other states (when defining transitions). In C, this means that basically all states need to be declared first (static const struct fsm_state name;), followed by the definition of each of the declared states (static const struct fsm_state name = { ... };); then, you can use &name as the identifier of each state. (The identifier is then of type const struct fsm_state *. For an unsigned integer, one can use(uintptr_t)(&name) as the numerical identifier.)
I've prattled on about FSMs and especially Mealy machines here (https://www.eevblog.com/forum/microcontrollers/state-machines-is-this-topic-taught-any-more/msg1942750/#msg1942750) (table form implementing this (https://www.eevblog.com/forum/microcontrollers/state-machines-is-this-topic-taught-any-more/msg1943593/?topicseen#msg1943593) graph) and here (https://www.eevblog.com/forum/programming/simple-menu-system-with-dynamic-keypad-functions-(embedded-alphanumeric-display)/msg2860070/#msg2860070) (Arduino menu example skeleton).
-
this (https://www.eevblog.com/forum/microcontrollers/state-machines-is-this-topic-taught-any-more/msg1943593/?topicseen#msg1943593) graph
What program did you use to create that graph? Gnome/Dia (http://live.gnome.org/Dia)?
-
For me, a simple language to describe a simple FSM, should look like
state: rst, s0, s1, s2, s3, err;
bininput: i0 ;
output[]: o0='000',
o1='001',
o2='010',
o3='011',
oe='111';
on state rst
{
always: state <- s0, output <- o0;
}
on state s0'downedge
{
when (i0 is '1'): state <- s1, output <- o0;
when (i0 is '0'): state <- s0, output <- o3;
}
on state s1'downedge
{
when (i0 is '1'): state <- s2, output <- o1;
when (i0 is '0'): state <- s1, output <- o0;
}
on state s2'downedge
{
when (i0 is '1'): state <- s3, output <- o2;
when (i0 is '0'): state <- s2, output <- o1;
}
on state s3'downedge
{
when (i0 is '1'): state <- s0, output <- o0;
when (i0 is '0'): state <- s2, output <- o2;
}
on state s4'downedge
{
when (i0 is '1'): state <- s1, output <- o0;
}
whateverelse'downedge
{
always: state <- err, output <- oe;
}
-
For me, a simple language to describe a simple FSM, should look like
Simple anything is easy, by definition. It becomes more interesting when things become more complicated. Then it becomes more important to have techniques to reduce the complications.
For example, consider a FSM which has (say) 20 states in "normal" operation, but if one of (say) 5 "error" events occurs in any of those states, the FSM transitions to a "reduced capability" set of states. In one naive implementation, that would imply 5*20=100 clauses in the "normal operation" states, which all have to be implemented and kept in synchronism as the FSM evolves over time. Good luck with that.
-
this (https://www.eevblog.com/forum/microcontrollers/state-machines-is-this-topic-taught-any-more/msg1943593/?topicseen#msg1943593) graph
Interesting.
It's not the FSM itself, but how it's used.
In your cat/dog detector you could have made it lazy.
When it gets a 'c' the FSM can output MARK and have the program save the location in the input stream.
Then when you have gotten 'a', 'n' the FSM can output FLUSH and the program will output "can".
Unless of course it got 'a', 't' the FSM can output DOG and the program will output "dog".
This is not a full implementation, but gives an idea of making the program be able to print the largest sequence in a single shot.
Imagine that this was a graphics program and "dog" had to be in color.
-
this (https://www.eevblog.com/forum/microcontrollers/state-machines-is-this-topic-taught-any-more/msg1943593/?topicseen#msg1943593) graph
What program did you use to create that graph? Gnome/Dia (http://live.gnome.org/Dia)?
Dia, exported as SVG, with a bit of post-processing (colors, the break in one of the lines, converting text to paths, then similar strokes and fills merged) in Inkscape, then simplified, and finally extra cruft (metadata and useless attributes) removed by hand. This way, it's just eight paths and a white background rectangle, and scales to whatever size wanted. It may sound like a lot of work, but it only takes me a few minutes to do.
(If you wonder why the nodes resemble so much Graphviz Dot struct nodes, wonder no more: I started by defining the graph in Graphviz DOT language to see what the overall graph looked like. Then I fired up Dia, and chose the locations of the nodes, and redrawing the graph in a few minutes, according to my own personal preferences. This is a surprisingly efficient and fast workflow, even though one ends up using several different tools and even editing SVG by hand; there is very little guesswork, as long as you write the initial graph description in DOT correctly. Which is also why that was not the first version; I realized a better way to describe the FSM (in DOT), and this was the result of that.)
In your cat/dog detector you could have made it lazy.
Very true. This way, it was a pure Mealy machine (transitions depending only on the current state and current input). The partially detected strings aren't "stored", they're implicit in the state, so the machine describes fully the operation without external state.
I prefer Mealy-type finite state machines, as my typical FSM is for a menu system on a microcontroller. (There, the inputs are buttons (and possible error situations), and the state corresponds to the currently active menu entry; so it makes sense that the state transition only depends on the current state and inputs. Makes for predictable menu systems, really. Plus, there is minimal RAM usage, as the states can reside purely in ROM/flash. I like that.)
(It isn't my intention to imply that Mealy machines are 'better' than other FSM types; it completely depends on the task at hand, in my opinion.)
I believe the most widely used FSM generator from domain-specific descriptive language is flex (https://github.com/westes/flex), which generates deterministic finite automatons (https://en.wikipedia.org/wiki/Deterministic_finite_automaton) (DFA in flex documentation and internals). I never found it particularly intuitive or well-designed for its task, but practice always trumps intuition: combined with e.g. bison (https://www.gnu.org/software/bison/manual/bison.html), you have a powerful lexer-parser used in hundreds, if not thousands of large-scale long-term projects like interpreters and compilers.
If I were to design my own domain-specific language for example for implementing Mealy menus, I would ensure it generates not only sensible C/C++ (GNU C/C++ in my case), but also easily readable formatted text, and state graphs (similar to the one shown) via Graphviz. (I'd like to have extra directives to add specific details to each state; including C/C++ hooks when entering and exiting the state – meaning, you could add literal code to the state if needed.) Unfortunately, that makes the domain rather small: just menu systems, instead of FSMs in general.
-
Simple anything is easy, by definition. It becomes more interesting when things become more complicated. Then it becomes more important to have techniques to reduce the complications.
That's the job for specialists. I am not. But I am 100% able to implement the above language which is "enough" for simple FSMs in VHDL.
For example, consider a FSM which has (say) 20 states in "normal" operation, but if one of (say) 5 "error" events occurs in any of those states, the FSM transitions to a "reduced capability" set of states. In one naive implementation, that would imply 5*20=100 clauses in the "normal operation" states, which all have to be implemented and kept in synchronism as the FSM evolves over time. Good luck with that.
Great example! I wrote the above lines to show how I would represent the legible source: how would you represent your example by legible source? :D
-
For example, consider a FSM which has (say) 20 states in "normal" operation, but if one of (say) 5 "error" events occurs in any of those states, the FSM transitions to a "reduced capability" set of states. In one naive implementation, that would imply 5*20=100 clauses in the "normal operation" states, which all have to be implemented and kept in synchronism as the FSM evolves over time. Good luck with that.
Well, that was the idea of my "overwriting table" approach.
You specify all your normal clauses, then your global clauses.
if (STATEA) -> STATEB
if (STATEC) -> STATED
if (RESET) -> STATEX // global rule for all states
if (RESET && STATEC) -> STATEY // specific exception to reset rule overwrites previous rule
Or you could also write it as:
if (STATEA) -> STATEB
if (RESET) -> STATEX // global rule for all states
if (STATEC) -> STATED // generates "clean" STATEC with no reset rule
if (RESET && STATEC) -> STATEY // new reset rule
-
override: or0, or1;
state: or0: { srst, serr, sovr },
or1: { s0, s1, s2, s3 };
input[2]: i0 ;
output[]: o0='000',
o1='001',
o2='010',
o3='011',
of='xxx', // this allows custom values, not enumerated here
oo='101'; // output on override-condition
oe='111'; // output on "handled by nobody" condition
on override or0
{
always: null; /* never override */
}
on override or1
{
when (i0 is '11'): state <- sovr, output <- oo;
whateverelse: null; /* don't override */
}
on state srst
{
always: state <- s0, output <- o0;
}
on state s0'downedge
{
when (i0 is '10'): state <- s1, output <- o0;
when (i0 is '00'): state <- s0, output <- o3;
}
on state s1'downedge
{
when (i0 is '10'): state <- s2, output <- o1;
when (i0 is '00'): state <- s1, output <- o0;
}
on state s2'downedge
{
when (i0 is '10'): state <- s3, output <- o2;
when (i0 is '00'): state <- s2, output <- o1;
}
on state s3'downedge
{
when (i0 is '10'): state <- s0, output <- o0;
when (i0 is '00'): state <- s2, output <- o2;
}
on state s4'downedge
{
when (i0 is '10'): state <- s1, output <- o0;
}
on state sovr
{
when (i0 is '00'): state <- srst;
}
whateverelse'downedge
{
always: state <- serr, output <- oe;
}
what do you think about this? It indirectly uses monads :o
-
As I prefer to use structures rather than switch cases in C, I have much more options on how to deal with error conditions.
For example:
#define READONLY const
typedef struct fsm_state fsm_state;
typedef struct fsm_transition fsm_transition;
typedef unsigned char fsm_event;
typedef unsigned char fsm_condition;
enum {
FSM_EVENT_END = 0,
FSM_EVENT_A = 1,
FSM_EVENT_B = 2,
FSM_EVENT_C = 3,
};
enum {
FSM_CONDITION_NONE = 0,
FSM_CONDITION_NORMAL = 1<<0,
FSM_CONDITION_PAUSED = 1<<1,
FSM_CONDITION_CONFUSED = 1<<2,
FSM_CONDITION_ON_FIRE = 1<<3,
FSM_CONDITION_ALL = (fsm_condition)(~0),
};
struct fsm_transition {
READONLY fsm_state *state; /* Target state */
READONLY fsm_condition allow; /* Conditions allowed for this transition, 0 if end of array */
READONLY fsm_event event; /* Event number or mask triggering this transition, 0 if end of array */
};
#define FSM_END_TRANSITIONS { (void *)0, 0, 0 }
struct fsm_state {
READONLY fsm_condition clear; /* Condition bits to be cleared on entering this state */
READONLY fsm_condition set; /* Condition bits to be set on entering this state */
READONLY fsm_transition transition[]; /* Array of transitions/events, terminated with FSM_END */
};
READONLY fsm_state state_foo, state_bar, state_baz;
READONLY fsm_state state_foo = {
.clear = FSM_CONDITION_NONE,
.set = FSM_CONDITION_NONE,
.transition = {
{ &state_bar, FSM_CONDITION_NORMAL | FSM_CONDITION_CONFUSED, FSM_EVENT_A },
{ &state_baz, FSM_CONDITION_ON_FIRE, FSM_EVENT_A },
FSM_END_TRANSITIONS
},
};
READONLY fsm_state state_bar = {
.clear = FSM_CONDITION_NONE,
.set = FSM_CONDITION_CONFUSED,
.transition = {
{ &state_foo, FSM_CONDITION_NORMAL, FSM_EVENT_B },
{ &state_bar, FSM_CONDITION_ALL, FSM_EVENT_A },
{ &state_baz, FSM_CONDITION_ALL, FSM_EVENT_C },
FSM_END_TRANSITIONS
},
};
READONLY fsm_state state_baz = {
.clear = FSM_CONDITION_ON_FIRE,
.set = FSM_CONDITION_NONE,
.transition = {
{ &state_foo, FSM_CONDITION_NORMAL, FSM_EVENT_A },
{ &state_foo, FSM_CONDITION_NORMAL, FSM_EVENT_B },
{ &state_bar, FSM_CONDITION_ALL, FSM_EVENT_A },
{ &state_bar, FSM_CONDITION_ALL, FSM_EVENT_B },
{ &state_bar, FSM_CONDITION_ALL, FSM_EVENT_C },
FSM_END_TRANSITIONS
},
};
Above, each state consists of changes to the condition mask (bits cleared and set when entering the state), and one or more transitions.
Each transition consists of a pointer to the target state, the allowed condition mask, and the event/input that triggers this particular transition.
Because the transitions are an immutable array, such a state machine is automatically deterministic: the first matching allowed transition occurs.
State 'foo' does not modify the condition mask. Only event 'A' triggers a transition: in 'normal' and 'confused' conditions, to state 'bar'; in 'on fire' condition, to state 'baz'.
State 'bar' always sets the 'confused' condition mask bit on entering. Event 'B' in 'normal' condition causes a transition to state 'foo'. Event 'A' in all conditions causes a transition to this state (i.e., this is a superfluous transition!). Event 'C' in all conditions causes a transition to state 'baz'.
State 'baz' always clears the 'on fire' condition mask bit on entering. Event 'A' in 'normal' condition causes a transition to state 'foo', and in all other conditions to state 'bar'. Event 'B' in normal condition also causes a transition to state 'foo', and in all other conditions to state 'bar'. Event 'C' in all conditions causes a transition to state 'bar'.
As you can probably imagine, this sort of structure definition is easy to convert from a domain-specific language. The "name" used to refer to each state could be the name of the C state structure variable, with e.g. a suitable prefix (keeping the namespace sane). You could add function pointers to the state (with a fixed prototype), so that custom C code (specified in the domain-specific language) would be executed when entering/exiting the state.
Is this better than the others shown in this thread? I really do not have an opinion on that; I do not know. I haven't tried the others in practice. All I know is that this kind of approach has worked really well for me in implementing menus and such human interface stuff.
-
Is this better than the others shown in this thread? I really do not have an opinion on that; I do not know. I haven't tried the others in practice. All I know is that this kind of approach has worked really well for me in implementing menus and such human interface stuff.
Your approach looks great, but it's too much "C-oriented", hence much more difficult for me to implement it as meta-compiler.
I haven't fully implemented it yet, but the new "monad" concept is intriguing because it practically assumes that an abnormal condition can be handled with an "override behavior", described within the same definition of state; so the abnormal behavior is now part of a variable, and that's intriguing because it reduces the number of lines the final user has to write, and it also simplifies a lot of stuff for me in this specific implementation case.
It's not perfectly "legible", it tries to be legible with the compromise to also be simple to be implemented for those like me who are not specialists in writing compilers and translators.
Of course it still needs some work and it's limited only for a Mealy description :D
-
Is this better than the others shown in this thread?
I think that everyone is hitting different applications differently.
You've got states and "conditions" which could all be considered states.
For what you're describing though it might simplify/clarify things.
I don't want any conditions for what I was mainly doing.
(Just a note, I've only been posting pseudo code as my source rules. It's actually all XML.)
@0db you made me look up monad. I'm still chewing on that.
-
To generate the data structures and documentation from a single source, I might use an INI-file-like format:
[foo]
label: Foo
notes: On entering Foo state, we must call fsm_enter(), because bleghbok.
event bar: bar
event baz: baz
on enter call: fsm_enter
[bar]
label: Bar
notes: On entering and exiting Bar state, we must call fsm_enter()/fsm_exit(), because glarghblargh.
event foo: foo
event baz: baz
on enter call: fsm_enter
on exit call: fsm_exit
[baz]
label: Baz
notes: Cannot return directly to Foo, only via Bar. When exiting the state, fsm_exit() must be called, because glubwharf.
event baz: baz
on exit call: fsm_exit
The section name is the name used to refer to the state. In C, I would use a filtered version of it as the state variable name.
In each key:value pair, the key can consist of multiple space-separated words, with the first word being the directive.
For example, function call hooks would have form "on hookname call: funcname".
Transition specifications would have form "event eventname: sectionname" or "event eventname in condition: sectionname", and so on.
Note that some key:value pairs are functional (i.e., define fields in the C state structures), some informational/documentation (like notes:), and some are only useful when drawing a state transition graph (label:).
Parsing such a line-based format is dead simple. Lines without colons can be added to the value in the previous key:value pair, except ignored immediately after a new section start. We can even support escaping via e.g. \/→\ and \=→: for unambiguous escapes, leaving all other backslash-escapes intact. Most importantly, we can collect all event and condition names, and form human-readable enums for them; the structures would use those enums. Here, we have three states 'foo', 'bar', and 'baz'; and three events 'foo', 'bar', and 'baz'. While their names look the same, event 'foo' is not automagically tied to state 'foo'; the namespaces are separate.
The "trick" I would apply here, is to omit e.g. function pointers if no function call hooks are used, in the state structure type. Similarly, if "conditions" are not used, they are not included in the structure type. This does mean that one needs to test the generator for each combination of optional features, but it should be relatively straightforward.
The nice thing in a Python-based generator is that the parser is the same for generating code, documentation, the graphs, and even the state and transition analysis tool; and that allows for simple extensions to the generator itself.
To repeat, I am not suggesting this instead of anything else in this thread; just showing a model that works for me, in case anyone finds it interesting.
-
One of the advantages of using XML as source is the inherent hierarchy.
You could put multiple FSMs in a file and have them share the input/output declarations.
OTOH, I can understand people who say that <boring>true</boring> is boring!
-
I might be old skool, but I feel that in general domain specific languages (DSL) are bad idea.
Although interesting to design and program (and I've done a few) that I they add a level of abstraction and complexity usually adds more problems than it solves.
Would only recommend if it is a user requirement for the FSM to be reconfigurable, which can't easily be achieved in the native implementation language.
For other cases, find a pattern you hate the least and adopt it. The programmer that follow you (or you in 5 years time) will thank you.
At the moment my standard pattern for C is function that takes a pointer to a structure with all the state in it.
struct state_info {
int state;
int foo[10];
} s;
...
s.state = 0; //reset state
while(s.state) {
switch(s.state) {
case 0: func_state_reset(&s); break;
case 1: func_state_1(&s); break;
case 2: func_state_2(&s); break;
default: func_state_error(&s); break;
}
}
For more complex FSMs, a table of function pointers is a good idea, removing the switch/case statement, but only as long as you make sure your function lookup code is bulletproof at picking up errors - nothing worse than if you index off the end of the table and your code jumps to Lala land).
-
I might be old skool, but I feel that in general domain specific languages (DSL) are bad idea.
Although interesting to design and program (and I've done a few) that I they add a level of abstraction and complexity usually adds more problems than it solves.
Would only recommend if it is a user requirement for the FSM to be reconfigurable, which can't easily be achieved in the native implementation language.
For other cases, find a pattern you hate the least and adopt it. The programmer that follow you (or you in 5 years time) will thank you.
At the moment my standard pattern for C is function that takes a pointer to a structure with all the state in it.
struct state_info {
int state;
int foo[10];
} s;
...
s.state = 0; //reset state
while(s.state) {
switch(s.state) {
case 0: func_state_reset(&s); break;
case 1: func_state_1(&s); break;
case 2: func_state_2(&s); break;
default: func_state_error(&s); break;
}
}
For more complex FSMs, a table of function pointers is a good idea, removing the switch/case statement, but only as long as you make sure your function lookup code is bulletproof at picking up errors - nothing worse than if you index off the end of the table and your code jumps to Lala land).
DSLanguages are overblown; every comp sci graduate wants to invent one in the same way every EE wants to develop a processor.
DSLibraries in a standard language are usually preferable.
With a DSLanguage, you have to invent your own toolset, have to train staff in an unpopular nontransferable skill.
-
.
-
One of the advantages of using XML as source is the inherent hierarchy.
Ah yes, XML. The triumphant reinvention of a limited crap subset of Lisp :)
-
For example, consider a FSM which has (say) 20 states in "normal" operation, but if one of (say) 5 "error" events occurs in any of those states, the FSM transitions to a "reduced capability" set of states. In one naive implementation, that would imply 5*20=100 clauses in the "normal operation" states, which all have to be implemented and kept in synchronism as the FSM evolves over time. Good luck with that.
Great example! I wrote the above lines to show how I would represent the legible source: how would you represent your example by legible source? :D
This is the kind of problems where hierarchical state machines shine. In this case the 20 "normal" states will lay inside a super-state and the reduced capability states will lay inside another super-state. Transitions usually occur inside one of such super-states, but when one of the 5 error conditions happens, the HSM transitions from one super-state to the other.
Precisely :)
It is a standard design pattern.
But not knowing of a good way to textually describe a FSM, go figure an HSM.
Just write the effin code in your favourite OOP language :) For a standard design pattern, see the seminal "Gang of Four" "Design Patterns" book, p305.
With a little taste and discipline the implementation can be easily maintained and easily accomodate "non functional" (ugh!) aspects such as logging, timing analysis etc.
-
One of the advantages of using XML as source is the inherent hierarchy.
Ah yes, XML. The triumphant reinvention of a limited crap subset of Lisp :)
Mmm, okay, how about doing it in JSON then? >:D
-
writing a fsm by hand can be fraught with legibility problem especially if complex and revisiting it in a few months...
I would suggest either flex or yacc generators, in my opinion nearly any state machine that is deterministic can be
made with either if these parsers.
best of all you could modify the parser skeleton in a debug version so you can see and understand whats going on.
-
I might be old skool, but I feel that in general domain specific languages (DSL) are bad idea.
In general, I agree.
(I do not like to do code generation at all, if I can avoid it; and translation from one high-level procedural language to another just-as-high-level seems silly to me.)
Here, however, what I am suggesting is a generator that uses a single source definition – a descriptive language, not a procedural or functional one – to define human-readable documentation, visual graphs (illustrations), and the data structures used in the finite state machine.
In other words, the "language" – really just a list of sections with a list of key-value paris in each section; a build-time configuration file! – defines the data structures describing the finite state machine states and transitions; not the finite state machine implementation itself.
The practical problem in having the C data structures and documentation separately, is one of maintainability. Too many programmers are idiots who believe "someone" will take care of the documentation later on, that their time is too valuable to waste on such trivialities. Ensuring the documentation and the data in a single DSL (or build-time configuration file) makes it easy to track those idiots: if an edit only touches the data, not the documentation (in preceding/succeeding lines), and the commit message does not explain what bug the edit fixes, the edit will be reverted and the committer talked-to. It makes for a simple rule to follow, to ensure the long-term maintainability.
Note that I earlier mentioned that this applies predominantly to certain complex cases (AIs, expert systems), and that FSMs are an edge case. This is because it depends on what kind of FSM one intends to implement. Mine are typically menus and human interface stuff, so the data structure driven pattern (as opposed to switch/case pattern) works best for me; and since the data structures can easily be defined separately from the code that implements the core machine, I believe that on the balance, it is better to combine documentation and data definition in a single file.
-
One of the advantages of using XML as source is the inherent hierarchy.
Ah yes, XML. The triumphant reinvention of a limited crap subset of Lisp :)
Mmm, okay, how about doing it in JSON then? >:D
At least that is part of a turing complete programming language.
-
writing a fsm by hand can be fraught with legibility problem especially if complex and revisiting it in a few months...
I would suggest either flex or yacc generators, in my opinion nearly any state machine that is deterministic can be
made with either if these parsers.
best of all you could modify the parser skeleton in a debug version so you can see and understand whats going on.
Such techniques fail w.r.t.
- readability, when all the events and actions are added
- embeddability within the runtime environment that generates and delivers and emits events
- debuggability, especially after deployment
- efficient run-time logging, especially of state trajectory (a.k.a. how did we get here?!)
- run-time tools support
- quality of the FSM DSL; most DSLs are crap, and devolve into a cancerous pile of spaghetti (the FSMs implemented in such devolved DSLs are dreadful!)
That's more or less true of anything that uses a conventional language as an intermediate language. Such things are very attractive to the "all turing languages are equivalent" compsci mindset, but are a pain in the backside in most environments. There are exceptions, but they are rare.