4 ms·

I was dreading taking Computer Science Theory for my undergraduate degree. Turing machines bored me when I studied them in my introductory class, and I saw the

I was dreading taking Computer Science Theory for my undergraduate degree. Turing machines bored me when I studied them in my introductory class, and I saw the class as a necessary evil - a core requirement as well as a prerequisite for my compilers class. Boy, was I wrong. Despite what I'd anticipated, that class ended up being the single most useful CS class that I took. I had the fortune of taking the class with Alfred Aho[1] - I can't imagine a person more qualified to teach a class on computation via automata; he literally thinks in automata. One day, I mentioned how I'd solved a particular programming problem (not for class) by reasoning about it as if it were a pushdown automaton, and how I was surprised that these techniques were still relevant, even for problems far more high-level than, say, writing egrep. He told me, 'Sometimes when I have a tough problem, I like to think of it as a language recognition problem, and it becomes easier to solve.' My brain may not be quite as oriented towards state machines as Prof. Aho's is, but that trick has saved me countless times. Like functional programming, it takes a bit of practice to wrap your head around it if you're not used to it, but it can present really elegant solutions to problems that seem daunting at first glance. [1]http://en.wikipedia.org/wiki/Alfred_Aho http://en.wikipedia.org/wiki/Alfred_Aho

jacquesm 14y ago
Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is, quite possibly some genius would be able to solve it in many different ways, but this to me only underscores the value of statemachines as a tool).
- plinkplonk 14y ago
  "Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats." If you don't mind being taught by Prof Ullman instead, Coursera has a course on Automata coming up https://www.coursera.org/course/automata https://www.coursera.org/course/automata
  - jacquesm 14y ago
    The other half of the dragon book... figures :)
- charlieflowers 14y ago
  Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.
  - chas 14y ago
    I first learned about them from a digital logic perspective, so they were already very practical tools for me when I ran into them in my theory classes. One of the best free resources I can find in short order is the wiki article on them. http://en.wikipedia.org/wiki/Finite-state_machine http://en.wikipedia.org/wiki/Finite-state_machine The wiki page on deterministic finite automata would be useful to see the CS theory/language side of the idea. http://en.wikipedia.org/wiki/Deterministic_finite_automaton http://en.wikipedia.org/wiki/Deterministic_finite_automaton
  - jacquesm 14y ago
    Hm, I never thought there would be anybody interested in this stuff so it's all over the place. Basically what I've done is to model state machines using a bunch of C macros, added a simple event system to drive the state transitions (receipt of message translates into an event) which allows you to run any number of statemachines in parallel inside a single C thread. The events are prioritized to make sure that urgent stuff gets processed first (such as statemachines terminating). Imagine turning a very large bowl of spaghetti into a neatly ticking Swiss watch :) The particular element that made this a powerful tool was the fact that statemachines (unlike function calls) are restrictive, the state-to-state transitions are all known up front and any state changes that are not explicitly allowed are forbidden. This simplifies design and debugging. An extra benefit of doing it this way is that to run the resulting code on a cluster requires only one (relatively, see 'fallacies of distributed computing') simple addition, a way to pass messages between statemachines on different nodes. The end result of all this is that what was an absolutely gargantuan knot of hard to read code became almost trivial by comparison, each statemachine is so simple that the business logic portion is usually less than a page of code or so (with a few exceptions), and all of the boilerplate is abstracted out and taken care of by the macros. Statemachines are small enough that they can be tested with ease and can then be glued together using instantiation from within other statemachines. The main loop of the program reads input and as soon as it has a complete message will instantiate a statemachine to process it and will then send that statemachine the message to set the ball rolling. I'll see if I can find the time to describe the method in a bit more detail, statemachines communicating using messages is a powerful metaphor for many programming problems and I think it comes into its own when you're making really complicated systems that have to be very predictable and reliable. Note that even though there are some parallels with threads threads are simply multiple paths of execution running in parallel through the same body of code, statemachines are different in that instead of functions calling other functions statemachines operate on a single chunk of data (called the state) and will note the changes to the state by transiting to a new state. Every program you write is in essence a statemachine but you normally don't make the states explicit, instead you embody the (single) state that you've got in the combination of program counter, stack and data memory. That makes the state rather hard to untangle at any given moment. Using statemachines explicitly breaks up this giant state vector into smaller ones that operate on much simpler pieces of data using a series of permitted operations, the outcome of which is rigidly defined. I hope this all makes sense (it's 6:15 am and I haven't slept yet...)

jacquesm 14y ago

Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats. Statemachines are an incredibly useful tool. I've spent the better part of last year untangling a huge pile of code and the solution in the end was to split it all up into statemachines that communicate with each other using simple synchronous messages. That and that alone made the problem tractable. (Tractable to me, that is, quite possibly some genius would be able to solve it in many different ways, but this to me only underscores the value of statemachines as a tool).

plinkplonk 14y ago
"Consider me extremely jealous that you are studying under Prof. Aho, he's one of the greats." If you don't mind being taught by Prof Ullman instead, Coursera has a course on Automata coming up https://www.coursera.org/course/automata https://www.coursera.org/course/automata
- jacquesm 14y ago
  The other half of the dragon book... figures :)
charlieflowers 14y ago
Would love to get your recommendations for good reading on state machines, please. Getting curation from a someone who understands them well and uses them in practice often would be fantastic.
- chas 14y ago
  I first learned about them from a digital logic perspective, so they were already very practical tools for me when I ran into them in my theory classes. One of the best free resources I can find in short order is the wiki article on them. http://en.wikipedia.org/wiki/Finite-state_machine http://en.wikipedia.org/wiki/Finite-state_machine The wiki page on deterministic finite automata would be useful to see the CS theory/language side of the idea. http://en.wikipedia.org/wiki/Deterministic_finite_automaton http://en.wikipedia.org/wiki/Deterministic_finite_automaton
- jacquesm 14y ago
  Hm, I never thought there would be anybody interested in this stuff so it's all over the place. Basically what I've done is to model state machines using a bunch of C macros, added a simple event system to drive the state transitions (receipt of message translates into an event) which allows you to run any number of statemachines in parallel inside a single C thread. The events are prioritized to make sure that urgent stuff gets processed first (such as statemachines terminating). Imagine turning a very large bowl of spaghetti into a neatly ticking Swiss watch :) The particular element that made this a powerful tool was the fact that statemachines (unlike function calls) are restrictive, the state-to-state transitions are all known up front and any state changes that are not explicitly allowed are forbidden. This simplifies design and debugging. An extra benefit of doing it this way is that to run the resulting code on a cluster requires only one (relatively, see 'fallacies of distributed computing') simple addition, a way to pass messages between statemachines on different nodes. The end result of all this is that what was an absolutely gargantuan knot of hard to read code became almost trivial by comparison, each statemachine is so simple that the business logic portion is usually less than a page of code or so (with a few exceptions), and all of the boilerplate is abstracted out and taken care of by the macros. Statemachines are small enough that they can be tested with ease and can then be glued together using instantiation from within other statemachines. The main loop of the program reads input and as soon as it has a complete message will instantiate a statemachine to process it and will then send that statemachine the message to set the ball rolling. I'll see if I can find the time to describe the method in a bit more detail, statemachines communicating using messages is a powerful metaphor for many programming problems and I think it comes into its own when you're making really complicated systems that have to be very predictable and reliable. Note that even though there are some parallels with threads threads are simply multiple paths of execution running in parallel through the same body of code, statemachines are different in that instead of functions calling other functions statemachines operate on a single chunk of data (called the state) and will note the changes to the state by transiting to a new state. Every program you write is in essence a statemachine but you normally don't make the states explicit, instead you embody the (single) state that you've got in the combination of program counter, stack and data memory. That makes the state rather hard to untangle at any given moment. Using statemachines explicitly breaks up this giant state vector into smaller ones that operate on much simpler pieces of data using a series of permitted operations, the outcome of which is rigidly defined. I hope this all makes sense (it's 6:15 am and I haven't slept yet...)