3 ms·

An Interactive State Machine Demo

nickpsecurity 8y ago
I’ve been pushing state machines for a long time with decision trees on Animat's recommendation. They managed to smoothly combine in a visual tool with automation? Hell yeah! I like that the article describes the benefit clearly: “Behavior is notoriously difficult to test. The number of possible paths that a typical interactive program has is combinatorial. Besides, the previous actions affect the program’s state, and thus its future responses. State machines drastically reduce the number of combinations that need to be tested. However, to be useful, state machines must be organized in a strict hierarchy. A well-chosen hierarchy removes irrelevant combinations of states.” This also isn’t speculative. Dijkstra invented and used hierarchical layering of state machines to build THE Multiprogramming System [1] in the 1960’s. It was very reliable at a time when computers weren’t. High-assurance security required that approach on all systems at B3/A1/EAL6-7 both to reduce errors and facilitate mathematical verification. Best example being Karger et al’s VAX VMM [2] illustrating it in Section G., “Layered Design.” The only thing that’s changed since then is that there’s more automated methods than ever to help specify, verify, and generate/optimize code for ISM’s. Every year, this approach from early-to-mid 60’s becomes more usable and verifiable. Decision trees being the wild card here with the combo worth further design experimentation. [1] https://en.wikipedia.org/wiki/THE_multiprogramming_system https://en.wikipedia.org/wiki/THE_multiprogramming_system [2] http://lukemuehlhauser.com/wp-content/uploads/Karger-et-al-A-retrospective-on-the-VAX-VMM-security-kernel.pdf http://lukemuehlhauser.com/wp-content/uploads/Karger-et-al-A...
- airbreather 8y ago
  "However, to be useful, state machines must be organized in a strict hierarchy. A well-chosen hierarchy removes irrelevant combinations of states.” - yes state machines are awesome and I use them all the time when programming real time controllers for machinery/process automation and sequencing. The best thing for me is that telling the process engineers I want them to tell me their required functionality as a state table (which then is our common/overlapping language of interface) forces them to think about every state needed and to exhaustively and unambiguously consider every transition. But, as per the text I included at the beginning of this comment, the surprisingly most difficult thing is deciding appropriate system decomposition and hierarchy so you don't end up with the "state explosion" of many, many states when someone tries to cram everything into one state machine.
kleer001 8y ago
I just learned about state machines last month in preparation for NaNoGenMo. They're pretty cool! I squeeled with joy to realize that Markov Chains can be a form of state machine. Then I started coding an adventure and the if statements began to pile up. Escalated quickly. Now I have to refactor the protagonist's narrative engine library if I want to add more complexity and reduce total lines code. It'll take a bit, and maybe I can't finish by the end of the month, but it'll allow for more emergent behaviour. Going to lean towards "Utility Functions" as they're called.
airbreather 8y ago
Can't believe this topic isn't getting more up votes.

I’ve been pushing state machines for a long time with decision trees on Animat's recommendation. They managed to smoothly combine in a visual tool with automation? Hell yeah! I like that the article describes the benefit clearly: “Behavior is notoriously difficult to test. The number of possible paths that a typical interactive program has is combinatorial. Besides, the previous actions affect the program’s state, and thus its future responses. State machines drastically reduce the number of combinations that need to be tested. However, to be useful, state machines must be organized in a strict hierarchy. A well-chosen hierarchy removes irrelevant combinations of states.” This also isn’t speculative. Dijkstra invented and used hierarchical layering of state machines to build THE Multiprogramming System [1] in the 1960’s. It was very reliable at a time when computers weren’t. High-assurance security required that approach on all systems at B3/A1/EAL6-7 both to reduce errors and facilitate mathematical verification. Best example being Karger et al’s VAX VMM [2] illustrating it in Section G., “Layered Design.” The only thing that’s changed since then is that there’s more automated methods than ever to help specify, verify, and generate/optimize code for ISM’s. Every year, this approach from early-to-mid 60’s becomes more usable and verifiable. Decision trees being the wild card here with the combo worth further design experimentation. [1] https://en.wikipedia.org/wiki/THE_multiprogramming_system https://en.wikipedia.org/wiki/THE_multiprogramming_system [2] http://lukemuehlhauser.com/wp-content/uploads/Karger-et-al-A-retrospective-on-the-VAX-VMM-security-kernel.pdf http://lukemuehlhauser.com/wp-content/uploads/Karger-et-al-A...

airbreather 8y ago
"However, to be useful, state machines must be organized in a strict hierarchy. A well-chosen hierarchy removes irrelevant combinations of states.” - yes state machines are awesome and I use them all the time when programming real time controllers for machinery/process automation and sequencing. The best thing for me is that telling the process engineers I want them to tell me their required functionality as a state table (which then is our common/overlapping language of interface) forces them to think about every state needed and to exhaustively and unambiguously consider every transition. But, as per the text I included at the beginning of this comment, the surprisingly most difficult thing is deciding appropriate system decomposition and hierarchy so you don't end up with the "state explosion" of many, many states when someone tries to cram everything into one state machine.

kleer001 8y ago

I just learned about state machines last month in preparation for NaNoGenMo. They're pretty cool! I squeeled with joy to realize that Markov Chains can be a form of state machine. Then I started coding an adventure and the if statements began to pile up. Escalated quickly. Now I have to refactor the protagonist's narrative engine library if I want to add more complexity and reduce total lines code. It'll take a bit, and maybe I can't finish by the end of the month, but it'll allow for more emergent behaviour. Going to lean towards "Utility Functions" as they're called.

airbreather 8y ago

Can't believe this topic isn't getting more up votes.