Only one of them knew what a state machine was ...
Only one of them knew what a state machine was ...
May be state machines aren't used much as most of the programming is done for pre-emptive OSes. Did they know about threads, mutexes etc.?
Only one of them knew what a state machine wasAnd it is on this basis I hope to keep employed for a few more years. 8)
Edit: I think you may be onto something regarding the programming methodologies in use today, where in high level applications and systems we have moved away from explicit event driven models with super loops to method driven OO technologies.Many things have very persistent state. Frequently persisting far longer than any piece of software ever runs without a break. Whatever you call them, and however you look at them, FSMs won't go away. Remember that they even have their own religion. :)
Only one of them knew what a state machine wasAnd it is on this basis I hope to keep employed for a few more years. 8)
Many things have very persistent state. Frequently persisting far longer than any piece of software ever runs without a break. Whatever you call them, and however you look at them, FSMs won't go away. Remember that they even have their own religion. :)
You see this deficiency in a lot in software, where someone has written a function or group of functions that interact with shared state variables at various times under varying circumstances, and the result is software that usually kinda works, but sometimes does X or Y one call before or after it should, etc, because the programmer never just drew a state diagram and coded to that, but instead just sort of poked at the problem until it kinda mostly worked.
A few years ago I took an EDX course from UT 6.02x Embedded Systems.
One of the labs was indeed to design a finite state machine for a traffic lights and pedestrian lights at a major intersection. Major pain!
While a good tutorial, the argument was that using no "if" or other type statements and being able to prove (to a judge and such) that there was no way it could have misbehaved.
So, yes, it is still being thought as a basic concept, albeit not that efficient as a programming method.
reasonably experienced developerswell there are experienced developers that dont know how to use #define properly nor know what reusable codes are. their qualification maybe was only hands on experience, no proper education line.
nor know what reusable codes are.
So, yes, it is still being thought as a basic concept, albeit not that efficient as a programming method.
So, yes, it is still being thought as a basic concept, albeit not that efficient as a programming method.
If, for example, one uses function pointers to maintain state, efficiency is rarely a problem.
More likely, though, is that without a state machine you risk ending up with a complex decision tree with plenty of duplicated code that's difficult to maintain.
I'm pretty sure that many programmers use state machines without knowing it, for example in event driven programming, the state machine is performed by the framework.
If you worked with lower level embedded (meaning NOT RPi embedded linux and similar stuff) and had to handle precise timings and edge cases, I rally can't believe you are unfamiliar with SMs or doubt their efficiency.
Java and such stuff, I understand people not being familiar with SMs
Yup, basically whenever you have important timings and coverage of edge cases (critical systems) SMs seem like a must.If you worked with lower level embedded (meaning NOT RPi embedded linux and similar stuff) and had to handle precise timings and edge cases, I rally can't believe you are unfamiliar with SMs or doubt their efficiency.
Java and such stuff, I understand people not being familiar with SMs
They are just as valuable at a high level. Consider telecom control software, or flight control.
I conjecture they ought be used for some event-driven smartphone apps as well.
Common saying around here is "if everyone knew what they were doing, we would all be flipping burgers".
Formal education on state machines? I had ONE course (EE) where it was touched on, in terms of digital logic. I would assume a more CS oriented track would cover this in far more detail, but I was more interested in hardware design so I went EE.
I think state machines are common in academia, hence people with education probably know about them. However "state machine" is a common design pattern, so you would think computer science people (even self taught) will know about it....And self thinking pea-counters to give enough timely resources.
Hardware designers will come across FSM at some point, Moore and Mealy machines.. basics of any VHDL course.
Theoretical computer scientists use automata to describe state machines. There are many modelling languages and paradigms to describe automata, and prove certain properties of a system. You could use temporal logic, like LTL or CTL, to reason about the temporal behavior of systems. Or PCTL to reason with probabilities in mind as well.
For example, the probability of a system failing and not recovering within a certain timespan.
Unfortunately, these tools are mostly academic because modelling any real large system requires at least a PhD in the field plus access to sufficiently powerful simulators and machines to do any meaningful experiments.
Notice your words control. What you are describing is RT system with HMI.If you worked with lower level embedded (meaning NOT RPi embedded linux and similar stuff) and had to handle precise timings and edge cases, I rally can't believe you are unfamiliar with SMs or doubt their efficiency.
Java and such stuff, I understand people not being familiar with SMs
They are just as valuable at a high level. Consider telecom control software, or flight control.
I conjecture they ought be used for some event-driven smartphone apps as well.
Regarding if-then comment - yes they end up being nested if-then, but that is not what you’re maintaining and modifying, and that is a huge difference.Notice your words control. What you are describing is RT system with HMI.If you worked with lower level embedded (meaning NOT RPi embedded linux and similar stuff) and had to handle precise timings and edge cases, I rally can't believe you are unfamiliar with SMs or doubt their efficiency.
Java and such stuff, I understand people not being familiar with SMs
They are just as valuable at a high level. Consider telecom control software, or flight control.
I conjecture they ought be used for some event-driven smartphone apps as well.
I also do not understand how some claims that IF =/= FSM, every FSM lockdown network is in the end multiple IF-THEN statement, similarly not every SR-latch became a practical SM.
Notice your words control. What you are describing is RT system with HMI.If you worked with lower level embedded (meaning NOT RPi embedded linux and similar stuff) and had to handle precise timings and edge cases, I rally can't believe you are unfamiliar with SMs or doubt their efficiency.
Java and such stuff, I understand people not being familiar with SMs
They are just as valuable at a high level. Consider telecom control software, or flight control.
I conjecture they ought be used for some event-driven smartphone apps as well.
I also do not understand how some claims that IF =/= FSM, every FSM lockdown network is in the end multiple IF-THEN statement, similarly not every SR-latch became a practical SM.
Notice your words control. What you are describing is RT system with HMI.If you worked with lower level embedded (meaning NOT RPi embedded linux and similar stuff) and had to handle precise timings and edge cases, I rally can't believe you are unfamiliar with SMs or doubt their efficiency.
Java and such stuff, I understand people not being familiar with SMs
They are just as valuable at a high level. Consider telecom control software, or flight control.
I conjecture they ought be used for some event-driven smartphone apps as well.
I also do not understand how some claims that IF =/= FSM, every FSM lockdown network is in the end multiple IF-THEN statement, similarly not every SR-latch became a practical SM.
A standard way to model a saga orchestrator is a State Machine where each transformation corresponds to a command or message. State machines are an excellent pattern to structure a well-defined behavior as they are easy to implement and particularly great for testing.
I think protocols can also be commonly implemented as statemachines. Look at TCP and the common states a socket can have.
what do you use, guys, to represent the FSM (its flowchart) on a document?
DIA?
Graphviz?
umm? :-//
it doesn't have to be graphical
flowcharts != FSM diagrams. Flowcharts merely illustrate a subset of the possible event/state trajectories
that's the question: what is convenient? :Dit doesn't have to be graphical
no doubt about, just for some details it's more illustrative and easy to understand.
flowcharts != FSM diagrams. Flowcharts merely illustrate a subset of the possible event/state trajectories
flowcharts are enough to illustrate an FSM in Mealy or Moore form
We use both, Mealy, and Moore, depending on our convenience :-//
Anyway, I need a software to illustrate the FSM of my team's hw debugger engine made for a hobby. This weird gear has a protocol as well as several FSMs in the (v)HDL code as well as server FSM in the C code on the host-software, and I am oriented to Dia since it has a lot of primitives already done which might be used to represent a FSM. Unfortunately, it's not scriptable, therefore I can't automatize the process.
I mean, what I have is a lot of vHDL modules and C code, and it would be "cool" extracting the documentation rather than have to manually create it, and the design itself offers a decent modularity, therefore extracting this info should be easy ... to be then converted into Graphwiz scripts? I am really tempted since even LaTex is able to understand them :D
I know, I know, ideally, you should start from the documentation which describes the protocol and things, with flowcharts of the FSM etc, and then implement it on HDL/C/wherever.
However, here we are working in reverse because unfortunately (and thanks to my group of hobbyists who help me, and to whom I would always say THANK for the help) this hobby project has never been disciplined like it should have been(1) :horse:
what do you use, guys, to represent the FSM (its flowchart) on a document?
DIA?
Graphviz?
umm? :-//
I used to teach FSMs as one of many programming paradigms (both to undergraduates and master's students) until very recently. Like many paradigms, there are some problems it is particularly well suited to, and others for which it is a poor model.
However, I suspect their popularity went down in mainstream CS when structured programming came in, and the GOTO was ruled to be unacceptable. While it's not the only approach, unfortunately, the simplest way of implementing FSMs is based around GOTOs, and I suspect the FSM baby got thrown out with the GOTO bathwater to some degree.
I'd agree with that. It was the late 70s when people like Michael Jackson (the Jackson Structured Programming one) and Edward Yourdon were a big thing. In the 1980s FSMs were still a thing every good software developer was still trying to find good programming patterns for.QuoteHowever, I suspect their popularity went down in mainstream CS when structured programming came in, and the GOTO was ruled to be unacceptable. While it's not the only approach, unfortunately, the simplest way of implementing FSMs is based around GOTOs, and I suspect the FSM baby got thrown out with the GOTO bathwater to some degree.There I disagree. Gotos disappeared and structured programming appeared long before FSMs were relegated to parsers/compilers.
The modus operandi is very much customer driven, in that there is continuous development, integration and deployment, with pushes as an when they’re needed, on average one or two per week. However, there has been little strategy around the application, and almost no methodology around the approach other than a reasonably strong change control system that’s recently been effected since it became owned by a single large player.
And thereby lies the problem, for many years there were a few developers, many I believe self-taught, and what I’d call startup types, with a JFDI attitude, which works for instant short term gratification for their customers when delivering a cacophony of small changes, but not so much for a longer term product roadmap and maintainability.
For a period of time you can hide what’s going on under the hood, but it’s going to come and bite you as the sheer weight of top heavy plasterwork comes crashing down.
The solution wasn’t just to use a state machine though. It was to use the database equivalent of passing by reference rather than passing by value. Passing by reference, it’ll never catch on ;-)
At uni my line was simulation and visualization, so I didn't get the full regular comp sci treatment, and the only time I explicitly encountered state machines at uni was during my course on compilers. Even then, it was more a tool for the job at hand (parsing) than something taught explicitly.
That said, state machines are, in principle, quite simple and I can't imagine an otherwise experienced developer having much issue picking up the concept. Most will have used a state machine without thinking about it as such.
Though, getting handed an existing complex state machine can be a daunting task to get to grips with for anyone.
Though, getting handed an existing complex state machine can be a daunting task to get to grips with for anyone.Documenting them exactly (and that means keeping the documentation in sync with implementation changes) is what makes that kind of hand-off possible. But that applies to all complex systems, not just state machines.
State +=3 ;// Move to the state that checks the dilthium interposer before enable IPS conduits)WarpDriveStateTransition(CHECK_DILITHIUM_INTEPOSER);To answer the original question. Yes. I teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course) as well as to junior engineers in my company.
What I see as the biggest oversight in implementations is the lack of guards when transitioning between states. Regardless of how the state machine is implemented in code (function pointer table, switch/case), I never allow a state variable to be directly modified. There is always a singular function that (i.e. TransitionToState(.....)) that accepts the new state, checks to see if it valid, implements any logic during the transition, etc.
Seeing things likeCode: [Select]State +=3 ;// Move to the state that checks the dilthium interposer before enable IPS conduits)
scare me!
I personally likeCode: [Select]WarpDriveStateTransition(CHECK_DILITHIUM_INTEPOSER);
There are many structured programming design patterns that are very well-suited for FSMs, with 2D arrays of function pointers being an excellent example. One dimension's index is the state, the other dimension's is the event.
There are many structured programming design patterns that are very well-suited for FSMs, with 2D arrays of function pointers being an excellent example. One dimension's index is the state, the other dimension's is the event.
That's certainly one way of doing it, and a neat way of doing it, if your supports functions as first class values.
But it's still nowhere as easy for undergarduates to grasp as
GOTO stateN...
What are the odds? I posted this (https://stackoverflow.com/a/53064647) on stackoverflow.com a day before OP started this thread.
void cat_to_dog(FILE *in, FILE *out)
{
int ch;
ch = fgetc(in); // blocking call
while (ch != EOF) {
if (ch != 'c') {
fputc(ch, out);
ch = fgetc(in);
continue;
}
ch = fgetc(in); // blocking call
if (ch == EOF) {
fputc('c', out);
break;
} else
if (ch != 'a') {
fputc('c', out);
continue;
}
ch = fgetc(in); // blocking call
if (ch == EOF) {
fputc('c', out);
fputc('a', out);
break;
} else
if (ch != 't') {
fputc('c', out);
fputc('a', out);
continue;
}
fputc('d', out);
fputc('o', out);
fputc('g', out);
ch = fgetc(in); // blocking call
}
}void dogger_init(dogger_state *s);
void dogger_update(dogger_state *s, char c);
void dogger_fin(dogger_state *s);void main()
{
char c;
char *p = "dog eat cat\n";
dogger_state s;
dogger_init(&s);
while (c = *p++) {
dogger_update(&s,c);
}
dogger_fin(&s);
}typedef struct {
char a, b;
} dogger_state;void dogger_init(dogger_state *s) {
s->a = 0;
s->b = 0;
}
void dogger_update(dogger_state *s, char c) {
// check for "cat" and replace if found
if (c=='t'&&s->b=='a'&&s->a=='c') {
s->a = 'd';
s->b = 'o';
c = 'g';
}
// send out the pending character
if (s->a) putchar(s->a);
// advance the state
s->a = s->b;
s->b = c;
}
void dogger_fin(dogger_state *s) {
dogger_update(s,0);
dogger_update(s,0);
}#include <stdio.h>
#include <stdint.h>
typedef struct {
char a, b;
} dogger_state;
void dogger_init(dogger_state *s) {
s->a = 0;
s->b = 0;
}
void dogger_update(dogger_state *s, char c) {
// check for "cat" and replace if found
if (c=='t'&&s->b=='a'&&s->a=='c') {
s->a = 'd';
s->b = 'o';
c = 'g';
}
// send out the pending character
if (s->a) putchar(s->a);
// advance the state
s->a = s->b;
s->b = c;
}
void dogger_fin(dogger_state *s) {
dogger_update(s,0);
dogger_update(s,0);
}
void main()
{
char c;
char *p = "dog eat cat\n";
dogger_state s;
dogger_init(&s);
while (c = *p++) {
dogger_update(&s,c);
}
dogger_fin(&s);
}$./dogger
dog eat dog
$guards when transitioning between states.It is nice to see there are still those who teach proper engineering principles with software :)
Code: [Select]State +=3 ;// Move to the state that checks the dilthium interposer before enable IPS conduits)
// State = 23;
// 20080323 devnam1: Fix PR#20121.
// State += 5;
// 20101130 devnam2: Fix #PR30115 and #PR30121.
State += 3;I wouldn't qualify this as a state machine.Then you're using the term wrong. It is a classic state machine, just described using a flowchart.
The state machine is basically a function which calculates new state based on the old state and the input:No. You are confusing finite state machines as a model of computation, and design patterns used for implementing state machines. (Exactly the sort of thing I was complaining about earlier; the gap between software engineering and information technology.)
There are many structured programming design patterns that are very well-suited for FSMs, with 2D arrays of function pointers being an excellent example. One dimension's index is the state, the other dimension's is the event.
That's certainly one way of doing it, and a neat way of doing it, if your supports functions as first class values.
But it's still nowhere as easy for undergarduates to grasp as
GOTO stateN...
The state machine is basically a function which calculates new state based on the old state and the input:No. You are confusing finite state machines as a model of computation, and design patterns used for implementing state machines. (Exactly the sort of thing I was complaining about earlier; the gap between software engineering and information technology.)
I had an unexpected experience today, I was handing over a project to half a dozen reasonably experienced developers which uses a state machine to orchestrate and synchronise its tasks. Only one of them knew what a state machine was, so I ended up spending half the meeting explaining the concept, not the easiest of tasks if you’re not prepared.
Admittedly this isn’t an embedded system, it’s a big server-side database manipulation task, but I’d still expect any software developer to have at least heard of state machines, or are state machines outside of embedded systems a bit too old school nowadays?
are state machines outside of embedded systems a bit too old school nowadays?
FSMs are taught in any (decent) introductory CS courseI dunno. It's a "data structures and algorithms" topic, maybe. 2nd year or so?
I teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course)Neither is ""outside" of embedded systems"
I took an EDX course from UT 6.02x Embedded Systems.Heh. I was in that class (or the 1st one, anyway.) IIRC, that lab was quite the disaster for a lot of the participants. Generated MUCH discussion.
One of the labs was indeed to design a finite state machine for a traffic lights
So, what is the definition of the finite state machine in your eyes?See e.g. the Wikipedia finite-state machine (https://en.wikipedia.org/wiki/Finite-state_machine) article. It has a pretty good definition, and also differentiates between the model itself, and its various representation/implementation methods.
(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding." Sigh.Dammit, that's exactly what I was trying to say above, with software engineering and information technology. Me fail English |O.
(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding." Sigh.Dammit, that's exactly what I was trying to say above, with software engineering and information technology. Me fail English |O.
I may disagreeBelieve or not, but I actually appreciate that a lot (from everyone, not just you), when the differing viewpoint/reasoning is shown. I'd often miss my own errors otherwise, and I'd rather admit to and fix my own errors, than lead others astray. That also means that I can be quite aggressive when I see claims that might lead others astray; I can't usually just let them be. :P
State │ Description │ Input │ Action │ Next state
═══════╪═══════════════╪═══════╪═══════════════════════╪═══════════════
INIT │ Initial state │ EOF │ │ END
│ ├───────┼───────────────────────┼───────────────
│ │ 'C' │ │ C
│ ├───────┼───────────────────────┼───────────────
│ │ │ Output input │ INIT
───────┼───────────────┼───────┼───────────────────────┼───────────────
C │ Have 'C' │ EOF │ Output 'C' │ END
│ ├───────┼───────────────────────┼───────────────
│ │ 'A' │ │ CA
│ ├───────┼───────────────────────┼───────────────
│ │ 'C' │ Output 'C' │ C
│ ├───────┼───────────────────────┼───────────────
│ │ │ Output 'C' and input │ INIT
───────┼───────────────┼───────┼───────────────────────┼───────────────
CA │ Have "CA" │ EOF │ Output "CA" │ END
│ ├───────┼───────────────────────┼───────────────
│ │ 'T' │ Output "DOG" │ INIT
│ ├───────┼───────────────────────┼───────────────
│ │ 'C' │ Output "CA" │ C
│ ├───────┼───────────────────────┼───────────────
│ │ │ Output "CA" and input │ INIT
───────┼───────────────┼───────┼───────────────────────┼───────────────
END │ End of input │
I may disagreeBelieve or not, but I actually appreciate that a lot (from everyone, not just you), when the differing viewpoint/reasoning is shown. I'd often miss my own errors otherwise, and I'd rather admit to and fix my own errors, than lead others astray. That also means that I can be quite aggressive when I see claims that might lead others astray; I can't usually just let them be. :P
I do not have a strong opinion on what form or what tools are best for describing state machines, as I always pick on a case-by-case basis.
I used the flowchart at SO simply because I thought it would be easiest for new programmers to understand. In general, the table forms are easier to maintain. With a large number of states, using visualization tools like Graphviz that can be used to generate nice graphs from text, make it easier to get an overall picture of the complexity, and proper context when contemplating changes.
So, what is the definition of the finite state machine in your eyes?See e.g. the Wikipedia finite-state machine (https://en.wikipedia.org/wiki/Finite-state_machine) article. It has a pretty good definition, and also differentiates between the model itself, and its various representation/implementation methods.
A deterministic finite state machine or acceptor deterministic finite state machine is a quintuple,
"Sigma" is the input alphabet (a finite, non-empty set of symbols).
"S" is a finite, non-empty set of states.
"S0" is an initial state, an element of S.
"Selta" is the state-transition function: Delta : S × Sigma -> S
"F" is the set of final states, a (possibly empty) subset of S.A Mealy machine (https://en.wikipedia.org/wiki/Mealy_machine) is just one specific model with an associated representation (the model is restricted to fit a specific representation). Not all finite-state machines are Mealy machines, even when all Mealy machines are finite-state machines.
Quoteare state machines outside of embedded systems a bit too old school nowadays?QuoteFSMs are taught in any (decent) introductory CS courseI dunno. It's a "data structures and algorithms" topic, maybe. 2nd year or so?
It's barely mentioned in Sedgewick, and only in conjunction with searching.
I had it (~1980) as part of the digital logic and/or computer architecture class (very hardware oriented), and again as part of the Compiler class (WRT "parsing.") These days it ought to show up in networking internals classes, too.
"Automata Theory" tends to be a grad class, very mathematical and theory-based.
(ie https://online.stanford.edu/courses/soe-ycsautomata-automata-theory (https://online.stanford.edu/courses/soe-ycsautomata-automata-theory))
I think most students would be lucky to have done one example (the infamous "traffic light"), and have never seen it show up as a general purpose tool. FSMs are sort of "unclean" compared to modern tools like graphs and trees - the concept is simple, but there's a lot of complexity in setting things up. Also, they're hard to document internal to softare (yeah, state diagrams are swell. Til you try to do one in ASCII art), and they can be a pain to debug. Software FSMs can easily suffer from a lot of "sloppiness" in terms of implementing things in a particular state that ought to be mutiple states, and WRT integrating some sort of "clock."
(sort of classic cases of "coders are not taught enough CS" and "CS majors are not taught enough coding." Sigh.
And even if you learned it, you probably don't remember it until after you've had to actually use it a few times.)QuoteI teach them in 2 different classes (a digital design w/ FPGA and a microcontrollers course)Neither is ""outside" of embedded systems"QuoteI took an EDX course from UT 6.02x Embedded Systems.Heh. I was in that class (or the 1st one, anyway.) IIRC, that lab was quite the disaster for a lot of the participants. Generated MUCH discussion.
One of the labs was indeed to design a finite state machine for a traffic lights
In my university state machines are a 2nd semester mandatory class for Bachelor CSA whole class? Software State Machines?Do you happen to have a class syllabus and/or textbook reference handy?I'd be interesting looking at educational material that is more in-depth than The Traffic Light while being less theoretical than the advanced FSA classes I've seen...
Ok. Here's the definition from the page you quoted:No, that's the formal definition of the mathematical model that can represent any finite-state machine. Here's the actual definition, shortened a bit:
Finite-state machine is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number of states at any given time. The FSM can change from one state to another in response to some external inputs; the change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition.
Doesn't look much different from the Mealy pageWell of course the mathematical definition is the same, for chrissakes! What part of all Mealy machines are finite-state machines did you miss?
Looking at the code you wrote for your cat->dog machine, can you point out where is the "set of states" and where is the "state-transition function"?The model the code implements is a finite state machine. It does not mean that the code must contain identifiable elements that correspond to the mathematical description.
Is your cat->dog machine Mealy?So funny, ha-ha. Only if your definition of a Mealy machine allows the output function G to output more than one symbol at a time.
QuoteIn my university state machines are a 2nd semester mandatory class for Bachelor CSA whole class? Software State Machines?Do you happen to have a class syllabus and/or textbook reference handy?I'd be interesting looking at educational material that is more in-depth than The Traffic Light while being less theoretical than the advanced FSA classes I've seen...
Would this diagram work better than my earlier one?
Would this diagram work better than my earlier one?
Is there a software that helps you to generate flowcharts like this without doing everything by hand?
A comment: when coding a state machine, the current state may be represented either explicitly by a specific, dedicated variable, or implicitly, by the program counter. The software will be more maintainable (=easier for humans to read and understand) using explicit state storage.
Would this diagram work better than my earlier one?
Is there a software that helps you to generate flowcharts like this without doing everything by hand?
If you mean "draw", then search for UML StateCharts and similar.
If you mean "reverse engineer" from code, good luck.
Would this diagram work better than my earlier one?
Is there a software that helps you to generate flowcharts like this without doing everything by hand?
If you mean "draw", then search for UML StateCharts and similar.
If you mean "reverse engineer" from code, good luck.
nah, draw :) it's for my own documentation.. i would be fine with WORD if they were a bit more flexible. Will read on UML!
i don't know why i wrote generate... must have been too late or too early
Be wary of attempting to autogenerate a complete application from such drawings. There have been many attempts and products over the decades; I even proposed one in 1986! The unsuccessful ones forget that the edge case interactions with the real-world can be very messy. The successful ones have a carefully specified and limited domain of applicability.I have seen successful uses of state drawing to code generation, but they have always been in tightly defined domains. For example, in the late 80s we produced ITU SDL charts (basically a representation of an FSM in drawing form), using AutoCAD, for telephony signalling algorithms. These were automatically compiled into the state tables that went into the custom FSM hardware in our telephony systems. Because custom hardware was used, the boundaries of what needed to be represented were well defined, and the compilation process was fairly simple and closed ended.
Looking at the code you wrote for your cat->dog machine, can you point out where is the "set of states" and where is the "state-transition function"?The model the code implements is a finite state machine. It does not mean that the code must contain identifiable elements that correspond to the mathematical description.
This is exactly what I mean by there being a gap between "coding" and "computer science".
Be wary of attempting to autogenerate a complete application from such drawings. There have been many attempts and products over the decades; I even proposed one in 1986! The unsuccessful ones forget that the edge case interactions with the real-world can be very messy. The successful ones have a carefully specified and limited domain of applicability.I have seen successful uses of state drawing to code generation, but they have always been in tightly defined domains. For example, in the late 80s we produced ITU SDL charts (basically a representation of an FSM in drawing form), using AutoCAD, for telephony signalling algorithms. These were automatically compiled into the state tables that went into the custom FSM hardware in our telephony systems. Because custom hardware was used, the boundaries of what needed to be represented were well defined, and the compilation process was fairly simple and closed ended.
BTW: When I was a kid, I read a book about programming (which wasn't a new book even back then). The author suggested drawing a flowcharts (similar to your first diagram). He thought this was mandatory. Now I cannot tell whether this was a mainstream thing, or just this one author. Once you have a flowchart, the programming then becomes the implementation of the flowchart. Blocks get their lables, square blocks are replaced with sequential code, conditional blocks are replaced with ifs, lines become gotos. As soon as you have created the structure with labels and gotos, you can fill in. The same approach works equally well with any language - algol, assembler. Would work with C too. This may be a good idea when you write your program on sheets of paper (one sheet per block), but when looking at it on the screen, it looks horrid. It later was called spaghetti code and is now completely frown upon. Interesting, your flowchart led you to exact this kind of implementation. Of course, you replaced gotos with modern "continue" etc., but this doesn't change the structure of the code.
For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of the go to statements in the programs they produce.
One of my clients (I'm a contract software developer) models a number of state machines in Enterprise Architect (EA). A custom c# application then interrogates this model via the API published by EA and generates the c++ code to the coding standards the client adheres to (quite strict given it's a medical device). All passes Lint and internal human code review. So if we change the model we just regenerate the state machine code.
EA versioning isn't that good.
The C++, although the c# tool is also under full code review / versioning etc. EA versioning isn't that good.
The code review ensures we have unit tests that prove the state machine matches the model. i.e. every transition / event is tested, including custom reactions.
(...) on the assumption that if they threw their 200 domain object model into it and used the code generator it would solve world peace.
(...) on the assumption that if they threw their 200 domain object model into it and used the code generator it would solve world peace.
So true. :palm:
As I teasingly hinted above, just wait until aspect-oriented programming becomes the next silver bullet in embedded programming. Fun days ahead.
:-DD
(...) they will work out which state they should be in.
Is there a software that helps you toDia (http://dia-installer.de/), for example. Graphviz (https://www.graphviz.org/) too. Have them save/export the output to SVG, then edit that in Inkscape (https://inkscape.org/). The former was drawn in Dia, the latter directly in Inkscape with on a grid. Like I said, the tools I happen to use, vary a lot.generatedraw flowcharts like this without doing everything by hand?
But the code you wrote is still disconnected from this representation.No, what you mean is that you find it difficult to map the code to the underlying model. That's just your own personal limitation.
Ah yes, "patching the binaries" enshrined in the architecture; code reviews rendered meaningless.
I always use this as a reference on that subject:
https://youtu.be/h73PsFKtIck
You keep claiming that the two must match 1:1. I disagree, because one is about software engineering and dealing with real world imperfect languages and tools, and the other is about computer science and mathematics. They are at completely different levels, and deal with completely different problems. This is the gap.
You keep claiming that the two must match 1:1. I disagree, because one is about software engineering and dealing with real world imperfect languages and tools, and the other is about computer science and mathematics. They are at completely different levels, and deal with completely different problems. This is the gap.
...
Dx = (B.x - A.x) * (p.y - A.y);
Dy = (B.y - A.y) * (p.x - A.x);
is_on_edge = do_speculative prediction(A, B, p);
if (is_on_edge isEqualTo True)
...
drawing diagrams usually doesn't help much even if you use them to build your code
Good luck trying to explain a complex state machine with decision points and transitions to a systems engineer, who doesn't code, without a diagram. Fine if your system doesn't do a great deal or you're a one-man-band, but not if it's complicated or requires support in the future by someone else.
well, for example, the edge equation A*X + B*Y + C = 0 assumes that, given two points p1(x,y), p2(x,y), a system of two of these equations is always equal to zero, therefore the cross-point equation should be also fine to check if a point belongs to the border of a triangle, which ... only works when numbers are defined on the paper rather than on the grid (compter screen-pixel plane).
On the subject of state machines: plotting a real line segment requires an infinite state machine. Plotting an integer line segment requires only a finite state machine. :D
One of the things I did when I built my state machine compiler was generate output for graphviz. That turned the DSL into a state diagram from the IR.
Code in the DSL, generate code and diagram from output. The DSL was VCS friendly thus solving the problems of synchronising documentation with reality.
... but the error at each step is not predictable by unrolling the algorithm, because the equation becomes recursive.
Which is very very bad!
Very true indeed. The diagrammatic representation doesn't scale very far either. As the number of states increases, the more it resembles the phone junction box down the road.
However the point in this case was that there was one canonical "source of truth" which was the DSL rather than a separate document that was interpreted by meatspace and turned into a hand generated state machine that sort of did what it was supposed to do. The diagram was a soft requirement for the analysts. It was there, regardless of ugly factor so they were happy. Think of it more as "ladder logic" for the developers here who couldn't be trusted to write it themselves.
I have come to the conclusion you can't actually ever win with these situations other than making code the intermediate representation somewhere. Plus I like writing lexers and parsers so every problem that looks like that is a handy nail :-DD
I think graphical tools work really well for expressing this sort of stuff until one of three conditions occur:
1. Someone did something on one branch that requires merging. I watched two (contract) graphic designers merging a PSD a couple of weeks back which was hilarious as most of it was spent outside smoking and arguing with each other.
2. The company selling the tool discontinues it, usually because the only guys who know how it works left for a cushy job doing nothing of importance (aka SRE) at Google.
3. It uses some obscure windows API badly and doesn't work on windows 10 and no one wants to run a Windows XP VM until the sun implodes.
The bottom line is that for really small FSMs almost any representation is adequate, and for really big state machines all representations suck when you are trying to get your head around them. Welcome to life. :) I just try to live with what annoys the people around me the least.Very true indeed. The diagrammatic representation doesn't scale very far either. As the number of states increases, the more it resembles the phone junction box down the road.
However the point in this case was that there was one canonical "source of truth" which was the DSL rather than a separate document that was interpreted by meatspace and turned into a hand generated state machine that sort of did what it was supposed to do. The diagram was a soft requirement for the analysts. It was there, regardless of ugly factor so they were happy. Think of it more as "ladder logic" for the developers here who couldn't be trusted to write it themselves.
I have come to the conclusion you can't actually ever win with these situations other than making code the intermediate representation somewhere. Plus I like writing lexers and parsers so every problem that looks like that is a handy nail :-DD
I think graphical tools work really well for expressing this sort of stuff until one of three conditions occur:
1. Someone did something on one branch that requires merging. I watched two (contract) graphic designers merging a PSD a couple of weeks back which was hilarious as most of it was spent outside smoking and arguing with each other.
2. The company selling the tool discontinues it, usually because the only guys who know how it works left for a cushy job doing nothing of importance (aka SRE) at Google.
3. It uses some obscure windows API badly and doesn't work on windows 10 and no one wants to run a Windows XP VM until the sun implodes.
That sums up my beliefs and experiences.
Its a bit like WISYWIG editors vs markup editors. I like WISYWIG for small, quick and dirty things. But if I'm doing something large that may change over time, I prefer markup editors.
It is nice to have a graphical representation, hence UML exists. (And the nice thing about UML is that there are so many incompatible diagrams to choose from!)
In the end, it is often easier to JWTFC - just write the f*g code. But it helps if the code structure/style/architecture is simple, regular, and firmly implements FSM concepts.
The bottom line is that for really small FSMs almost any representation is adequate, and for really big state machines all representations suck when you are trying to get your head around them. Welcome to life. :) I just try to live with what annoys the people around me the least.
The bottom line is that for really small FSMs almost any representation is adequate, and for really big state machines all representations suck when you are trying to get your head around them. Welcome to life. :) I just try to live with what annoys the people around me the least.Very true indeed. The diagrammatic representation doesn't scale very far either. As the number of states increases, the more it resembles the phone junction box down the road.
However the point in this case was that there was one canonical "source of truth" which was the DSL rather than a separate document that was interpreted by meatspace and turned into a hand generated state machine that sort of did what it was supposed to do. The diagram was a soft requirement for the analysts. It was there, regardless of ugly factor so they were happy. Think of it more as "ladder logic" for the developers here who couldn't be trusted to write it themselves.
I have come to the conclusion you can't actually ever win with these situations other than making code the intermediate representation somewhere. Plus I like writing lexers and parsers so every problem that looks like that is a handy nail :-DD
I think graphical tools work really well for expressing this sort of stuff until one of three conditions occur:
1. Someone did something on one branch that requires merging. I watched two (contract) graphic designers merging a PSD a couple of weeks back which was hilarious as most of it was spent outside smoking and arguing with each other.
2. The company selling the tool discontinues it, usually because the only guys who know how it works left for a cushy job doing nothing of importance (aka SRE) at Google.
3. It uses some obscure windows API badly and doesn't work on windows 10 and no one wants to run a Windows XP VM until the sun implodes.
That sums up my beliefs and experiences.
Its a bit like WISYWIG editors vs markup editors. I like WISYWIG for small, quick and dirty things. But if I'm doing something large that may change over time, I prefer markup editors.
It is nice to have a graphical representation, hence UML exists. (And the nice thing about UML is that there are so many incompatible diagrams to choose from!)
In the end, it is often easier to JWTFC - just write the f*g code. But it helps if the code structure/style/architecture is simple, regular, and firmly implements FSM concepts.
But if the theory doesn't translate into the code, what is the point of drawing diagrams, tables, formulae.Map ≠ translate. That translation is in the gap I've been talking about in this thread; bridging computer science and practical coding (or software engineering).
if you have ever read this (https://www.eevblog.com/forum/microcontrollers/test-if-a-point-belongs-to-the-output-of-the-bresenhams-line-drawing/) topic about pixel-color interpolation, ... well, for example, the edge equation A*X + B*Y + C = 0 assumes that, given two points p1(x,y), p2(x,y), a system of two of these equations is always equal to zero, therefore the cross-point equation should be also fine to check if a point belongs to the border of a triangle, which ... only works when numbers are defined on the paper rather than on the grid (compter screen-pixel plane).Yup. That one is even harder than usual, because Bresenham's line algorithm is iterative; converting it to a direct analytical function is mathematically hard. (A solution that works for all nondegenerate inputs is certainly worth submitting to one of the ACM journals.)
The diagrammatic representation doesn't scale very far either.It's the human brain that doesn't scale! The diagrams and tables can describe the machine exactly, but if they're outside the humans grokking capability, they could be abstract art for all intensities and porpoises. :P
However the point in this case was that there was one canonical "source of truth" which was the DSL rather than a separate document that was interpreted by meatspace and turned into a hand generated state machine that sort of did what it was supposed to do.I'd wager you found out that the real underlying problem was to get the domain-specific language users to write machines that actually solve the problem they're supposed to. I mean, it is so easy for humans to believe they know how a problem should be solved, but either be completely wrong, or only solve a part of it. Tools that make it easier for them to implement their solution does not fix that. Yet, if you create a tool that points out the flaws in their reasoning, they're more likely to hate it than use it; most people just cannot stand having their errors pointed out.
I love the software industry if I'm honest. It's so fun watching the incredible level of dysfunction wherever you look. When it comes to it you can sit back and watch the human race slowly coding itself into a nasty little corner somewhere.It depresses me to no end... that's why I switched to physics. Not that it isn't just as inane, though: applying for funding is closer to buzzword bingo than anyone would guess. I wish I could just sit back and enjoy the show.
It's not a matter of calculating if something is within the limit, it's not so simple, you have a decision variable that is a true hidden state
therefore it's a matter of having a floating error that changes at every step, while the algorithm needs to take branch according to the decision variable, which is not predictable at each step.
as you see the next point x and y depends on "x += sx;" and "y += sy;" which depends on the decision variable "magic", which depends on the floating error, which may change at each step "err += Dy;", "err += Dx;", and it's difficult to predict the value of the next_step, because if you try to open/unroll this loop in order to calculate the error at each step, you get a recursive function.
It can be demonstrated, even mathematically, as Zeda did.
int condition = xAccum > yAccum; // 1 if true, 0 else
xAccum += Dx * condition;
yAccum += Dy * (condition - 1);
xAccum -= Dy * (condition - 1);
yAccum -= Dx * condition;