Wait a minute, that looks like an ordinary light switch, not some nerdish computer programming math'y gorp. Well, the lowly light switch is the perfect physical embodiment of a Finite State Machine, albeit a rather simple one.
If I were to start jabbering on about Digraphs or Multigraphs, your eyes would glaze over and you'd rightly wander off to go watch cat videos, so we gonna be talking light switches instead.
Light switches are something everyone has intuitive understanding of and there's not a whit of difference between what one can learn from them versus fancy jargon laden math'y graph shit. Switches now, jargon later.
Ok, what is a Finite State Machine?
In the case of the simple light switch, its either on or off, and you can only try to push it up or down. It has two "states", on/off, and its possible "inputs" are limited to push up/down as well. IOW, its a simple "finite" "machine".
Suppose the switch is in its OFF "state", and you give it an "input" of "push down" - the light its connected to remains off, and there's NO CHANGE in the "state" of the switch; its remains in its OFF "state". Similarly, if the switch is in its ON "state" and you were to push it up, it remains in the ON "state".
In a computer program, this kind of "do nothing and return to previous state" behavior is like some prompt that wants a particular input, checks what you typed in, and reasserts itself if you typed invalid crap, and refuses to go away until you type in correct shit. Basically, the "machine's" behavior is: "invalid input fool, try again", which we've all experienced.
FSM's are often used like this to check the validity of input data, but that's not their only use.
A light switch that you only feed invalid inputs doesn't do much. Its only useful when you have it "transition" between ON/OFF "states" to turn your light on or off based on "input data" (i.e. shoving it up or down).
If we're in the OFF "state" and you shove the handle up, we "transition" to the ON "state" and voila, things are getting brighter. Shove it up again, things remain bright. Similarly, if we're in the ON "state" and you shove it down, darkness ensues. Shove it down again - still dark.
Once you started thinking about how the light switch "machine" reacts to different "inputs" when its in its various "states" you've got the basics of how a simple FSM works.
FSM's are mechanistic - predictable in their behavior, just like the light switch. They have no surprises. For a "finite" numbers of "states", with well defined "transition" rules between them for all possible "inputs", you will get the same predictable behavior every time.
That on/off light switch example was pretty simple. Now ponder what sort of light switch "machine" is needed to control something like a light that can be turned on/off by several switches in different locations.
The 3-way and 4-way switches used to implement that don't have ON/OFF "states" like the simple switch, they're either up/down and the light bulb can be on/off with any particular switch in the up or down position depending on the "state" of the other switches that control the light bulb. That "machine" isn't so simple anymore, but its behavior will still be just as predictable as the simple one. If any of the multiple switches are flipped to their opposite position, the light bulb will turn on if it was off, and off if it was on.
This is the power of FSM's -- absolute predictability even when things start to get more complex. Of course one of the problems is when a FSM has a design flaw, it will fail predictably in certain circumstances too. That known as a "bug".
A example of predictable failure is some traffic stoplights. Their behavior is very FSM'ish. Based on their various timing settings, how many cars are waiting over roadbed sensors, etc they have very predictable mechanistic behaviors. We've probably all encountered a situation where some turn lane never gets a green arrow though. You could sit there forever and the damned thing won't change UNTIL someone pulls up in back of you, then suddenly you get the arrow.
When this happens you'll notice there's usually two sections of roadbed sensors in the turn lane. If you pull far enough forward that you're only sitting on the front most sensor, then the machine doesn't think there's enough traffic stacked up to warrant issuing a green arrow. During the day when traffic volume is higher, this is never an issue as there's always several cars stacking up waiting for a green arrow.
The failure mode happens late at night when traffic looking to make a turn is sparse. If that next car doesn't come along for hours, you could be sitting there literally for hours waiting for one to show up and trigger that second sensor. This is a design "bug" in the traffic signal FSM. Tip: if this ever happens to you, just back up so you're sitting over the second sensor, then you'll probably get the green arrow right away.
Which brings up an interesting point -- people usually know enough to test systems under hard load, but some failure modes will happen BECAUSE OF inactivity or very light loads. Years ago IBM shipped a disk drive that worked fine when it was bein flogged hard, but failed when it was sitting idle for some particular period. There was a bug in the onboard drive electronics FSM.
By now you're noticing I haven't said much about "programming" since after all this was claimed to be a programming lesson. Programming a computer, in reality, is just the electronic embodiment of notions that could also be "programmed" with mechanical systems, hydraulic systems, manually executed by humans, or various combinations.
When you've created a design that is sound, how its specifically embodied becomes an implementation detail. When I'm designing some computer program I often visualize its internal machinations as whirling mechanical or hydraulic systems.
Once I've convinced myself that "machine" works and have debugged it as best a virtual construct can be debugged, I know I could write code in any one of hundreds of computer languages to actually implement that "machine".
No comments:
Post a Comment