4 ms·
The answer on SE is still very theoretical. Yes, technically we can model any computation [1] as an FSM, but when does it actually make sense to do so? FSMs ar
by azov 13y ago
The answer on SE is still very theoretical. Yes, technically we can model any computation [1] as an FSM, but when does it actually make sense to do so?
FSMs are often used when modelling physical devices - think microwaves, elevators, CD-players, something with buttons or sensors, something event-driven, embedded controllers, also network protocols, text parsers, etc. Basically, whenever we must ensure correct behavior having few constraints on sequence or timing of inputs.
How can you actually apply it in your everyday programming? Look at your class. Every method call is an event that can cause a transition. Member variables are the state. Theoretically changing any bit of any member variable gives you a different state. In practice you only care about the bits that affect your control flow. Figuring out how variables map to states is the tricky part. Sometimes one variable corresponds to several states (say, when airspeed goes over V1 a plane transitions from can abort to must takeoff state), sometimes several variables define one state (say, when ignition=on and door=closed car is ready to drive), sometimes you'll need to add an extra variable to distinguish between states. Then you draw a table with events on one side and states on another and look at each cell. This is when you have all those precious "oh, crap, what if the user hits play when the song is already playing" moments. And voila - now you know that your class behaves correctly because you've systematically considered every possible scenario. It takes enough effort that you probably don't want to do it for each and every class, but when you do it - it's magic :-)
[1] Any computation with finite memory, to be pedantic
- gwu78 13y agoThis is a great comment. Thank you. I have had the opposite question from one posted to SE: What enlightenment will I attain when I can move beyond thinking of every solution in programming as a FSM? I have never understood the obsession with higher level languages with objects, classes, methods, etc. I can't seem to think beyond lex, regular expressions and case statements. You comment is reassuring. Maybe I'm already emlightened. And I just don't know it.
- lmm 13y agoEncapsulation is what you're missing. OO programming only makes sense once you're working on a codebase too big to understand. I mean, I guess you could think of each object as its own FSM, but that's not particularly enlightening - in part because well designed objects don't have multiple possible states (rather, the state is captured in what they are. It's a hard notion to accept, like learning to use infinitesimals in mathematics - you've spent so long convincing yourself that this intuitive notion is wrong, and then suddenly you discover there's a way to make that intuitive notion correct after all, but you resist it because it seems like it's a messy, bad intuition). Yes, technically there are states to the whole system - but you need some way to factorize it into smaller systems if you're going to make any sense of it. There is a real enlightenment to be got from really understanding OO, and it's one that many supposedly good programmers seem never to reach. Keep seeking it.
- gwu78 13y ago"... only makes sense once you're working on a codebase too big to understand." My aim is to never reach this point. When I can no longer understand it, it's too big. That said, I will remain curious about OO.
- lmm 13y agoNo-one fully understands their programs; even if you understand all the code, few people understand the language implementation, fewer understand the underlying OS libraries, and I'm pretty sure no-one understands every level of the hardware (I've seen guys who were lead on some section of an Intel processor say they didn't understand the whole thing). Now sure, you can say that when a single code project becomes too big to understand then it should be split up into a bunch of libraries, or a bunch of independent services. Which is true up to a point. But I find there's value in having a more granular continuum of decoupling scales - method, class, package, module, library, service - which OO makes possible. And I'd argue that many of these kind of libraries and services - particularly the REST style - are inherently OO.
- gwu78 13y ago
- ern 13y agoI did EE, before switching to CS, and we covered state machines for digital design in some depth, without learning automata theory. So, I don't think it's strictly necessary to know Theory of Computation to be able to model state practically and effectively.