State machines, is this topic taught any more?

[tggzzz]

I always use this as a reference on that subject:

https://youtu.be/h73PsFKtIck

Of fond memory

Once, long ago, I booked a seat to see that on Boxing Day at the NFT in London. Later I found it was being shown on TV , starting 15 mins later. I still went to the NFT for the day out and cinema experience.

[bd139]

I bet that was a marvellous experience though. Well worth it. I still go to the cinema today. Usually go on my own on a week day when there’s no one to annoy me

[NorthGuy]

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.

But if the theory doesn't translate into the code, what is the point of drawing diagrams, tables, formulae. Why have you spent hours working on these things if you don't use them when you write the code. Languages and tools are perfectly capable of compiling any code you write. They has been capable of handling various state machine implementations for dozens of years.

IMHO, drawing diagrams usually doesn't help much even if you use them to build your code. But if you don't, what's the goal?

[legacy]

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.

See also the gap between the Math on a piece of paper, and ... the Math on a Computer 

if you have ever read this 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).

A*X + B*Y + C =!= 0 for the Bresenham's Line Drawing Algorithm

Elisabeth, Zeda, and I have spent two weeks at finding a solution, which physically consists in a correcting function.

Theory + correcting function to adapt the theory to the poor prosaicness of the world = problem solved

We are still referring to the original formula, which doesn't work on the grid, and we are explicitly keeping all the add-ons in the correcting formula: this illustrates where things come from, how they work, providing also a scientific background.

Code: [Select]

    ...
    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)
    ...

Imaging now those guys who don't follow this approach: you see magical C code that is supposed to work on the computer screen, but you have absolutely no idea where the idea comes from, hence you have to reverse engineering patterns comparing them to something known from Computer Graphics books, but sometimes the code is a mess up, or it doesn't follow any known pattern in Computer Science, and you end completely lost. Too bad, that's not a scientific approach.

[legacy]

drawing diagrams usually doesn't help much even if you use them to build your code

Well, diagrams help a lot people in a team to understand details. You don't have to draw diagrams on everything, but you'd better draw them about critical roles and details.

That's the point.

[RobBarter]

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 supporting in the future by someone else.

[legacy]

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.

yeah, exactly what I meant 

[bd139]

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.

[BrianHG]

Though I knew what a FSM was, I first come into contact with a project where the contractee demanded I developed their building management system based on their block diagram state machine.  This was the first time I had such a huge project which needed to be fitted to a 16 bit PIC MCU.  I was given a worded description of what the device had to do, written in english, then the multi-page block diagram made out by a few board members who designed the system functions.  The system had to run an update-able state machine so the board of directors could make their own modifications.  I couldn't make heads or tails of it as discussions went back and forth.  So I passed the design to one of my engineering colleagues who specialized in high level programming and state machines.  What should have been a 1 month project took over 6 months, because, and get this, the damn block diagrams were full of illogical inconsistency errors which was the first thing I brought up when first going over the illustrations, which is why I passed on the project. 

My second experience with a state machine project was an alarm/doorbell/automatic door opening system, because, this one was layed out by someone who knew a bit more of what they were doing, and I was able to talk to him personally.  The project took only 5 hours to complete and debug, where 75% of the state machine was left functionally intact as a FSM while an overriding emergency door locking state within the diagram I removed and hard coded it to kill & reset the state machine as this way, the safety aspect overrided any unforeseen state machine problems.

If the source of the state diagram make sense, I can deal with it.
If it doesn't, even if it may still function, my head will go "awol" as I try to create the project and I would rather be in a mental institute that work on such a project, no matter how much I'm offered in money...

[T3sl4co1l]

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).

Right, equals zero for an infinitesimal line, plotted in the domain of real numbers.  Which isn't very useful, because you can't see a zero-width line...

Also not very useful because real numbers are... very poorly named.  Nothing in the real world is actually a "real".  That would require infinite information.

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.

The insight you are missing is this: if it's not zero, then how close to zero will it be, given A, B, C, X and Y quantized to a grid of so-and-so size?

This is identical to the matter of testing floating point numbers by proximity to zero, not equality to zero (or equating two numbers within some ε, same thing).  Same logic, and numerical methods, apply.

It then follows that, for Bresenham's for example, the error term is a variable-scale measure of the sub-pixel position of the line, where it intersects a grid edge.  (Variable in terms of A/B.)

Tim

[legacy]

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.

the solution is a bit more complex due to the fact that the Bresenham's internal state to choose the next pixel is based on a not visible state which is derived step by step on a floating error, which is not exactly equal to the line equation's error

err0 = A *X + B * Y + C
err1 = Bresenham's error

err0 is not necessarily always equal to zero
err0 is not necessarily always equal to err1

Given a starting and ending points, the finite state machine of the Bresenham's algorithm computes in a finite number of steps (whose precise number can be calculated by the  Pythagoras formula), but the error at each step is not predictable by unrolling the algorithm, because the equation becomes recursive.

Which is very very bad!

So we had to invent a way to solve it. With a speculative algorithm that tries to speculate on the error magnitude compared to the magnitude of the A and B slopes. This trick is computationally light (it takes 2 multiplies and two adders, plus two comparators) and it works fine, it's not perfect, but it does an excellent job, even in HDL implementation.

This work is for a mini GTE (geometry transform engine).

[tggzzz]

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.

That addresses and solves some important issues, but raises the issue of readability of the diagram in two respects:

• it really can look like a bowl of spaghetti!
• "strange" things might be permissable in the text, but not have a good diagramatic representation

Both are solvable, with discipline. But discipline over the long-term is in short supply

I was once involved with assessing a large-scale commerical "FSM-type" product, Kabira. The salesman touted the new graphical design suite, proclaiming it could generate 0.5MLOC/day. My retort was that I could easily personally generate 1MLOC/day.

More interestingly, the Kabira application engineers didn't use the graphical tools, preferring to work with text. Now there may have been some stick-in-the-mud behaviour, but that wasn't the whole story.

[bd139]

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

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.

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.

[NorthGuy]

... but the error at each step is not predictable by unrolling the algorithm, because the equation becomes recursive.

Which is very very bad!

It is easy to estimate the precision you need in your calculations to make sure the error is within the limit. The fact that the algorithm is iterative doesn't change that. Say, for the 1000-point screen, if you want 0.1 pixel precision on your calculation, your coefficients must have 0.0001 precision, which is 14 bits. This guarantees that the maximum error of a single step is 0.0001 pixels, and therefore after 1000 steps your error will be less than 0.0001*1000 - 0.1 pixel. So, if you represent your coefficient as a 32-bit integer where 16 upper bits represent pixels and 16 lower bits represent fractions, you know that you will meet (and exceed) your 0.1 pixel requirement, and all your absolute errors will be less than 0.1 pixel.

[tggzzz]

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

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.

[coppice]

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

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.

[NorthGuy]

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.

There are rare cases where graphical presentation is extremely useful, such as JTAG protocol, for example.

[tggzzz]

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

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.

Frequently big FSMs can be usefully broken up into multiple independent small FSMs that send messages to each other. That is, after all, at the heart of telecom systems!

[Nominal Animal]

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).

Sure, you can write code that maps the model to code 1:1, but then you discard the practical considerations and code-level stuff that can make the implementation much better.  Or you can just write code and not care about the underlying models, but then you discard a lot of known-good models and algorithms.  Only by combining the two, you get the best of both worlds.

Yes, that sort of synthesis is hard.  It is also not taught anywhere, as far as I can see.  Yet, when looking at the development process, most problem-solving expert types do that constantly.

Note, however, that there is another expert type of programmer: those that write easily maintained code without other code-level considerations at all. I do not want to imply that all expert developers must be the synthesist type. Sometimes correctness, maintainability, and being easily verifiable is way more valuable than any code-level considerations.

Even if the code-implementation happens to be of write-only sort, the model-level documentation helps, because it allows anyone to rip out that particular piece of code, and re-implement it.  This kind of modularity has shown to be extremely useful: it was the only way the Linux kernel developers could overcome the bottleneck of limited maintainer throughput. (Yet, even they are struggling with the documentation part, especially things like locking schemes.  To avoid having to write it all out and maintain that as well as the code, they've developed tools that check for common problems.)

I like that kind of modularity a lot, because it allows competition of ideas and implementations even within a single project.

if you have ever read this 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.)

A pure model-level person (like, say, compiler or standard library developers tend to be) might quip that you need to switch to the fixed-point slope algorithm (which chooses slightly different pixels), but that is not a solution, it is just changing the problem to one that is easier to solve.  The reason why one would prefer to stay with Bresenham's, is that at the code level, it is extremely efficient, with the iteration loop only using additions, subtractions, and comparison or over/underflow test.  That synthesis/gap/whatchamacallit pops up here once again.

[Nominal Animal]

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.

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.

How did you avoid getting (yourself, via the DSL and its compiler/interpreter) blamed for user errors?

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.

[T3sl4co1l]

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

I mean, if you close your eyes and ignore the accumulator in the middle of the algorithm, maybe.

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.

How is it not predictable?  It is the remainder of a division operation.  These things aren't new by any means -- division, factoring and LCM/GCM algorithms were known to the ancients (and probably not even invented by them, that is, by the ones who left written history).

The ingenuity that went into them, is probably harder to understand though... many of these things, you look at them and it seems as if they're a gift from the heavens themselves.

Myself personally: I probably developed some of my insight on this subject, working with raycasters (i.e., the pseudo-3D technique famous from Wolfenstein 3D and such).  In this case, you must calculate not only the grid locations touched by a given ray, but the exact sub-pixel of each grid line intersection (which is used for the wall texture coordinate).  Some linear algebra takes care of perspective correction (a linear sequence of vectors is rotated by the viewing angle, and the iteration proceeds according to the X and Y components of the vector), and then you have it.

It's a problem I come back to every couple of years (or decade, it seems closer to now).  My first version was the naive add-a-fixed-distance-and-test method, which is very inefficient and coarse.  Then I learned the slope-intercept method, which involved a multiplication per step and which blows up under special cases (i.e., parallel to axes).  Finally, I developed the dual-accumulator method (which, I forget if that's also what Carmack worked with back then, or if I looked at the WOLF3D source and got it from there..), which uses two divisions to set up the calculation, then only conditional increment and addition in the inner loop.  Finally, the accumulator residues are converted to the texture coordinate.

For your case, the endpoints are known, which are the vector components fed to the accumulators.  At any point along the line, the accumulator values can be read and converted to the sub-pixel coordinate, in terms of X or Y intercept, however you like.

(If you're interested, I've got a public example here: https://github.com/T3sl4co1l/raycast_win/blob/master/main.cpp , written in floating point since a PC doesn't care, but it works equally well (with suitable adaptations of course) in fixed point.  Also, this isn't textured, so it doesn't have the coordinate transformation step, sorry about that.)

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.

If you want to know for a specific point, remainderAtX(Dx, Dy, AtX), then you have no choice but to calculate it the hard way, i.e., by division.  That division can be performed iteratively, or by the various numerical algorithms known.  Doesn't much matter, as long as the results are equivalent (as they must).

The loop can be unrolled, by using C-style logic operators.  That is (e.g.):

Code: [Select]

int condition = xAccum > yAccum; // 1 if true, 0 else
xAccum += Dx * condition;
yAccum += Dy * (condition - 1);
xAccum -= Dy * (condition - 1);
yAccum -= Dx * condition;

On many machines, this will compile as a conditional anyway (i.e., when the only nonlinear operation available is a test-and-branch sequence), but some have an instruction that can perform it without the pipeline hit, a sign-extend or a proper C-style condition-bits-to-register instruction.

Or, on still other machines: multiplication and division may be practically free, compared to, say, IO bandwidth limitations.  Vector machines -- GPUs and such -- fit here.  Example: https://youtu.be/bIjrSvGddDQ

Tim