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.
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).
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.
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 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
This book[1] seems to really help people (don't be put off by the title):
Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems
In particular, it discusses the main implementation strategies and why you'd want to use them. Also, the specific codebase described in the book is excellent. I use it all the time in implementing server software.
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...)
It sounds like we've had similar experiences. I converted a handful of ad hoc "state machines" in a telephony system to FA. The original code was loaded with exceptions and special cases (and bugs). Converting to FA required detailed analysis of the existing system to extract the distinct events and states. I used a tool I wrote [1] to generate C state tables and an event loop from a description of the states+events.
While the state machines that came out of the analysis were a big improvement, they still weren't perfect. We came across a few bugs later on. Using a strict representation of the state machines was a huge advantage in debugging and maintenance. When everything is moving through the same event loop, it's easy to add logging in the form "[timestamp] state A: event X -> state B". Adding a new state or event to the machine (to fix a bug or add a new feature) is much easier when everything is in one place.
In a couple of cases, the state machine started to become large and unwieldy. Usually the cause was that there would be a couple of "meta" states: we'd have states A, B, and C, but then we'd need to represent "states B and C when X is true; states A and B when Y is true". Pulling X and Y into a separate machine simplified the parent state machine -- every X and Y moved into the child divides the number of states in the parent by as much as half. Then the parent can inject events into the child, and the child can fire events back to the parent.
Indeed, it really sounds like a very similar experience, up to and including the code generation.
One more thing I ended up adding (that isn't on your list above) is a true string type to the 'C' language (backwards compatible, works with pre-defined strings as well), including garbage collection. I found that in order to get the right level of abstraction the C string type was simply inadequate, it kept forcing things into the foreground that should not even be visible at that level.
The one thing still missing is copy-on-write for string duplication, but that's a pretty tricky thing to implement in a thread safe and portable way. This would give a huge performance boost, but at the moment that would be just another case of premature optimization.
Honestly, my answer to this came about many years after living through a very theoretical CS undergrad, by way of a chapter in Charles Petzold's book, 'Code' (of all things. I originally bought the book for my dad to help him understand 'what it was I did all day'). Basically, the insight centered around the physicality of how FA are taught; FA are usually taught by thinking of the FA itself as being fixed in space, and the tape as moving through it. I always found that this lead to me thinking of the FA as a mechanical entity, driven by some sort of magical tape; a useful thought exercise to be sure, but not something that had many direct impacts on modern computing (outside of the obvious regular language avenues). If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register. It's a seemingly small difference of conception, but one that finally brought together two worlds for me that had evolved largely distinctly before then.
It's tough to give justice to this insight, except to say that it really helped crystalize the jump between the theoretical side of CS (which had always been clear to me, if never terribly 'real'), and the applied side of CS (which had always seemed to have evolved in some sort of semi-influenced paralel universe to theory).
I don't know that it's the enlightenment you're looking for, but it's the one that eventually found me.
It sounds a bit like you are talking about a Turing machine rather than a finite automaton (the latter is much weaker than the former in computational power).
(Not that it matters much, your point still stands.)
They are equivalent. None of them is weaker. And, by the way, your PC (Von Neuman architecture) is an example of finite automatum.
I've seen the FA formalism used in computing theory a few times. Yet, I'm also missing whatever enlightment the author is looking for. But, if for no other reason, it's worth learning just because it's a very nice tool.
Where is the infinite tape? Finite automata are as capable, in the real world, as Turing-like machines, because it is impossible to fabricate a machine with infinite storage.
Turing machines have infinite storage by definition, no such machine has ever been built (we're using approximations), real world restrictions do not apply to imaginary constructs.
If a Turing machine were not defined that way then you'd have to set some upper limit to the size of the tape and that in turn would have odd implications for what would be considered 'computable'. By making the tape infinite by definition you get much more meaningful answers about what is in principle computable and what is not.
Indeed, we have done everything we can to provide ways to keep the illusion of running on a Turing machine going -- I'm thinking about mmap(), swapping to disk, tape robots, and databases, among others.
robrenaud did not respond to the argument that the PC is a Finite Automata.
His only comment was that "Finite Automata are quite weak" (in the context of the _theoretical difference_ between Turing machines and FA). He's absolutely correct. FA can compute a strict subset of what Turing machines can compute.
> If you instead envision a FA as being a flying head that moves back and forward across a tape that is fixed in space, the ideas behind modern CPUs become much more clear: the tape is memory, the FA is a CPU being stepped through successive states, and the 'location' of the FA is the PC register.
It would seem an apt analogy for the (basic) Von Neumann architecture, but "modern" CPUs have a hierarchy of "cache lines" that quite neatly -- at least in my mind -- map to a FA "fixed in space" [the cache line], with a "magical tape" [virtual memory and cache coherence].
Of course -- the reality of even the simplest CPU is obviously much, much more complex than what I described above. The analogy is really only helpful as a bridge between the world of theory, and the CPU as it exists in the world.
I think Turing's key insight was that a special FA with a tape mechanism could be devised that could imitate any other FA. The power of this FA in imitating other FAs is limited only by the length of the tape.
However the improvement of this construction over any specific FA is that you have a device that can run any FA. As the length of the tape increases you have a device that can imitate the any and all possible FAs.
The CPU is precisely this FA which can imitate any other FA. The tape is memory.
However it is important to note that, at the end of it, any specific program that is being run on finite memory is still an FA.
Incidentally the answer to that question provides a concrete example of something you can easily do if you understand finite automata, that you couldn't do without it, and that knowing how to use pre-built interfaces with finite automata behind them (like regular expressions) would not help you solve.
I find there's no point in participating in SO beyond a certain level of ability. If you ask a truly difficult question, the odds of getting an answer from someone who knows what they are talking about is not very good. Meanwhile, any sort of discussion question gets closed.
The remainder is basic to intermediate questions that get answered with "this is a duplicate of X".
It seems like both Wikipedia and Stack Overflow are done, at least approximately. It is just that Wikipedia has at least some structures that have adapted to being done while it seem that SO framework never considered the possibility of the "frontier of general questions" being settled.
Wikipedia hasn't adapted as well to being "done" as you might think. For instance, there's apparently at least one editor who just goes around Wikipedia deleting random sections from articles that appear to be uncited. He never adds anything, any contributions come from actual subject area experts who have to take time away from editing other articles to deal with the mess he leaves behind. The Wikipedia bureaucracy seems to think he's doing a great job though! And this is just something I stumbled across a couple of days ago by accident without following Wikipedia behind-the-scenes stuff; from what I've heard they have problems with favouring policy wonks over content contributers everywhere.
Yep, this is the stackoverflow I know. They have practically killed all the meaningful C++ activity on the website by closing duplicate questions. Maybe some easy questions have already been answered but they don't let junior members contribute by answering them.
By the way Wikipedia is worse. In English anyway, in French it's cool.
Wikipedia carries with it a political edge. Companies pay good money to protect their reputation and apparently every central country was the true cradle of civilization. The most I have seen on SO is bored NVIDIA engineers answering questions related to the CUDA tag :-)
The concepts themselves have helped me a lot when programming parsers / interpreters / compilers. Recently I've developed a language extension for Fortran 90 along with a parser/analyzer in python that extracts structural information of the the program as well as the additional directives. Solved it in <1000 lines of python by combining an FA like structure (state switch using a dictionary function lookup with a state variable inside a loop) with regular expressions for the individual lines / state transitions. Sure, you could come up with this on your own quite easily, but FA give you some powerful concepts - even just knowing the keywords to google for can save you days of work.
The gist: When it comes to computer science and mathematical concepts, don't ask why to study it, just study it - possible applications will probably come at some point later in your career.
When you understand a subject well enough, the true basics become fascinating. Without the full round trip from introduction to complexity to revealed simplicity, the basics are nigh unto incomprehensible - yet giving new students an intro thereto at least shows them where they are going. Quantum mechanics is simple, but baffling to beginners; give them a taste and the "aha" moment will come in time.
A = {0|1,...}
A[x] = !(A[y]•A[z])
That's all there is to computing, near as I've been able to simplify it. Cellular automata may do a better job.
> Quantum mechanics is simple, but baffling to beginners
Quantum mechanics is weird to us because we're human-sized and quantum effects are mostly gone at our scale. Therefore, the only language we have for actually doing quantum mechanics is mathematics, so it makes sense to get a firm grasp of the math first. Fortunately, the fundamentals of the math aren't that difficult. I like to think of quantum mechanics as being 'mind-bendingly simple' for that reason.
Scott Aaronson has a fascinating lecture on quantum mechanics seen as a branch of probability theory:
> Quantum mechanics is what you would inevitably come up with if you started from probability theory, and then said, let's try to generalize it so that the numbers we used to call "probabilities" can be negative numbers.
That's a wonderful link. I know very little about quantum mechanics (or physics in general) but I do know some linear algebra, and for me that was a wonderful revelation. Thank you for sharing.
I don't understand why FA are so difficult for CS students to grasp.
I have the reverse problem. The concept of FA makes perfect sense. It's how I naturally think of a computer. It's the theory stuff that is not based on state machnes which I can't get my head around.
So my question is, what enlightenment would I attain if I understood all the theory (instead of just the reality)?
You did a great job summarizing those topics concisely, but I have some quibbles about the P and NP stuff:
1. NP isn't the set of problems that can't be solved in a polynomial amount of time, but rather the set of problems that can be solved non-deterministically in polynomial time. This distinction is important, since this means by definition that P is a subset of NP, and furthermore means that uncomputable problems such as the Halting Problem do not belong in NP.
2. Your definitions for NP-completeness seem mixed up -- the polytime reduction property you're mentioning is the definition of an NP-hard problem, and you've said it backwards. If a problem is NP-hard, every problem in NP can be reduced to it in polynomial time (i.e. it is just as "hard" as every problem in NP). NP-completeness requires in addition to this the property that the problem itself is in NP. For example, although the Halting Problem is NP-hard, it is not NP-complete, since it is not in NP. NP-hardness of a problem can be shown by polytime reducing any NP-complete problem to it, since any problem in NP can be polytime reduced to the NP-complete problem.
Recursion is the key to enlightenment. There are may ways to achieve this recursion, and contemplation of finite automata is one of them. The point of recursion happens when you realize that the thought process which is considering finite automata is itself composed of finite automata. The subjective experience of recursion leads to enlightenment.
Chemical processes are not measurably discrete, so it is only a conjecture that the universe could be modeled as a finite automaton.
Varying reference frames make it impossible to agree on an order for the input our brains receive, even if we can think of it as discrete. Agreeing on the state of a brain is also impossible, due to relativity.
Quantum entanglement makes it impossible to accurately model a portion of the physical universe, such as a brain. If you want complete accuracy you must model the whole universe or none of it.
I am aware of no accepted model of the universe that is deterministic. Finite automata are deterministic, the brain and the universe are not. Look up "hidden variables".
Only a more sophisticated model than finite automata could possibly be useful for describing physical phenomena in general. All models are wrong, but finite automata are not even useful for describing brains.
That assertion badly needs some proof, and I'm not currently aware that such a proof even exists (but I am aware that there is substantial evidence that it isn't all that simple).
A 'finite automaton' implies that you can capture the complete state vector and for many reasons this is unfeasible. So if there is proof to the contrary then please supply it. (I understand you're merely transcribing the original comment, which to me feels clever but wrong).
"Aha! moment". Well, I have to say that, for me, this came with the practice, not the study, of FSM's and, in particular Turing Machines. I could not imagine a world without them. Look around you.
While I studied FA formally it never really clicked until years later. Sometimes you don't really learn until you are holding a cat by the tail.
I should say that I've always called them "FSM" when, in most cases, in reality I was using a TM. A TM, of course, is also an FSM, so I'm at peace with my loose use of the term.
I really started to use FSM's with great frequency while working on developing hardware with FPGA's. Everything from reset modules to FIFO and SD/DD RAM controllers and more benefit from FSM's. They greatly reduce complexity and allow you to express very complex logic in code that can actually be followed and understood. For some reason FSM's feel more "at home" in hardware rather than software for me (although I use them extensively in software as well). There's something about looking at the definition of an FSM's states and realizing that it's a bunch of single bits (flip-flops) that makes it real:
Later, when you code the FSM --and if you've been doing this for a while-- you can look at the code and almost literally see the flip-flops and latches forming the structure:
always @ (posedge SOME_CLK) begin
case(state)
STATE_RESET: begin
// Do something in this state
end
STATE_STOP: begin
// Do something in this state
end
STATE_FORWARD: begin
// Do something in this state
end
STATE_TURN_RIGHT: begin
// Do something in this state
end
STATE_TURN_LEFT: begin
// Do something in this state
end
endcase
end
It's really cool. Geeking-out just thinking about it.
In the software front, everything from communications packet processors to email address validation and menu processors benefit from using FSM's. I like the application of FSM's to web app controllers where you can encode a lot of knowledge and sophistication into your control module and not end-up with a huge rats-nest of procedural code that is nearly impossible to understand and maintain.
I have to admit being guilty of "thinking like an FSM" at times to the extent that I see the opportunity to use them in almost every project, hardware or software.
Again, today I could not imagine designing hardware or writing software without FSM's.
What's the logic behind defining your states as bitflags instead of enums? I would typically write STATE_RESET = 0, STATE_STOP = 1, STATE_FORWARD = 2, STATE_TURN_RIGHT = 3, STATE_TURN_LEFT = 4...
Unless, of course, you're doing an NFA and have a reason to superimpose states (i.e. be in STATE_TURN_RIGHT and STATE_TURN_LEFT simultaneously).
Ah, remember, this is hardware and, this is Verilog, not C.
What you are looking at is called "one-hot" encoding.
If you enumerate your states you are asking Verilog to infer a register to hold your states. This also means that you have to have additional (slow) combinatorial logic to identify which state you are in.
With one-hot encoding each state is represented by a single and discrete flip-flop (FF) and no combinatorial logic is required. If you have 33 states the state machine has 33 FF's and only one of them can be "hot" or set to "1" at any given time.
One-hot encoding is faster, and offer a lot of other advantages (ease of debugging, ease of optimization, timing closure, etc.).
Of course, a more subtle aspect of state machine design is that Xilinx's tools can actually change the encoding your state machine uses behind the scenes. I actually traced a fun and very intermittent stability issue in one design to this. (Bitcoin mining stuff which used a state machine for clock domain crossing; the Xilinx tools replaced a safe state machine that could handle getting into an invalid state with one that couldn't.)
That's always fun. You just have to know your tools. That's why I tend to be very verbose and explicit in some aspects of my FPGA work. I rather not-so-gently guide the tools towards what I want them to infer vs. what they sometimes think I want them to infer.
Circuit inference is one aspect of HDL that sets it apart from writing software. To begin with, you are describing hardware and have to be aware of and live within the constraints it imposes. Then there's this inference thing that I've come to call my "secret contract" with the compiler: I say X and we agree that it is going to implement X12345 and we are all happy.
I've never actually done hardware design. I last looked at it a few years ago and it seemed really confusing.
What I really want is an FPGA on a board like the Raspberry Pi, where I can just plug in USB, network and power, copy-paste some code from a tutorial, have it run, and start learning HDL from that point.
I want to be able to develop an FPGA program that can maybe do a specific bitwise computation faster than a CPU or GPU (like SHA hashes for bitcoin mining, but this is just one example) and send inputs and outputs back and forth with a regular computer. Without also having to design and solder my own circuit board in order to do it.
It seems, though, like as soon as you say the word "FPGA," people automatically assume you have a ton of experience and equipment for building your own circuit boards. Which I really don't. And learning this on the same project learning HDL seems like it would really make things kinda hard. "It doesn't work" could mean anything from a solder blob shorting two wires, to some screw-up earlier in the process having destroyed a component and now it'll never work even if you do the rest of it correctly (and you have to increase your budget to replace the now-fried chip), to a failure to understand something about HDL, to some electromagnetic bug in the design of the circuit (like "you need a capacitor here, you need an inductor there, your resistor is 100x too big or too small")...a bug in the HDL of course...or it could be a bug in the USB interface hardware/software I made on the board...or in the custom USB driver I wrote (I've also never actually written a hardware driver before) running on the general-purpose computer...In short, it seems like, to get started teaching yourself hardware design, you have to have approximately one university degree worth of hardware design knowledge already.
Learning HDL, I want to be able to eliminate all of the above sources of error but "if it doesn't work, it must be a bug in my HDL code."
Bootstrapping software programming through self-learning is easy enough that probably at least tens of thousands of middle and high school kids do it on their own every year (I was one of them). Bootstrapping GPU programming is a little harder but still seems doable (I haven't actually done more than dabbling, though). Bootstrapping FPGA should be just as easy, but it isn't.
I haven't been able to find what hardware I should buy to do this, and I haven't even been able to figure out what search terms I should be using. It's been a few years since I looked, though, so maybe I should look again.
Honestly, there's absolutely nothing that would prevent you from learning HDL. There are a number of excellent development boards and tutorials. Start here:
The issue with doing higher-level work is that you really need to understand circuit design and implementation. A lot of what you do in an FPGA is to type out text that looks like code but in reality is a "secret contract" with the compiler for it to "infer" the circuit you want. In many ways you could say that there are idioms that you learn that will result in specific circuit constructs once they go through one turn of the wheel.
Then there's the issue of optimization. Sometimes you just don't get the performance you want and have to resort to, effectively, hand-wiring stuff in code. Whether VHDL or Verilog, you have the ability to literally hand-wire FPGA internals to build circuits that usually perform or place better than the what the tools can do:
(sorry, this is long)
module ADDER
#(parameter WIDTH = 8)
(
input wire CLK,
input wire CE,
input wire RST,
input wire CIN,
input wire [WIDTH - 1:0] A,
input wire [WIDTH - 1:0] B,
output wire [WIDTH:0] SUM
);
genvar i;
wire [WIDTH - 1:0] xor2;
wire [WIDTH:0] cy;
wire [WIDTH - 1:0] xorcy;
assign cy[0] = CIN;
generate
for(i=0; i <= WIDTH; i=i+1) begin:BIT
if(i != WIDTH)begin:_
myXOR2 x(.O(xor2[i]), .I0(A[i]), .I1(B[i]));
MUXCY m(.O(cy[i+1]), .CI(cy[i]), .DI(A[i]), .S(xor2[i]));
XORCY xc(.O(xorcy[i]), .CI(cy[i]), .LI(xor2[i]));
FDRE f(.Q(SUM[i]), .C(CLK), .CE(CE), .D(xorcy[i]), .R(RST));
end
else begin:_
FDRE f(.Q(SUM[i]), .C(CLK), .CE(CE), .D(cy[i]), .R(RST));
end
end
endgenerate
//synthesis attribute RLOC of BIT[0]._.x is X0Y0
//synthesis attribute RLOC of BIT[1]._.x is X0Y0
//synthesis attribute RLOC of BIT[2]._.x is X0Y1
//synthesis attribute RLOC of BIT[3]._.x is X0Y1
//synthesis attribute RLOC of BIT[4]._.x is X0Y2
//synthesis attribute RLOC of BIT[5]._.x is X0Y2
//synthesis attribute RLOC of BIT[6]._.x is X0Y3
//synthesis attribute RLOC of BIT[7]._.x is X0Y3
//synthesis attribute RLOC of BIT[8]._.x is X0Y4
//synthesis attribute RLOC of BIT[9]._.x is X0Y4
//synthesis attribute RLOC of BIT[10]._.x is X0Y5
//synthesis attribute RLOC of BIT[11]._.x is X0Y5
//synthesis attribute RLOC of BIT[12]._.x is X0Y6
//synthesis attribute RLOC of BIT[13]._.x is X0Y6
//synthesis attribute RLOC of BIT[14]._.x is X0Y7
//synthesis attribute RLOC of BIT[15]._.x is X0Y7
//synthesis attribute RLOC of BIT[16]._.x is X0Y8
//synthesis attribute RLOC of BIT[17]._.x is X0Y8
//synthesis attribute RLOC of BIT[18]._.x is X0Y9
//synthesis attribute RLOC of BIT[19]._.x is X0Y9
//synthesis attribute RLOC of BIT[20]._.x is X0Y10
//synthesis attribute RLOC of BIT[21]._.x is X0Y10
//synthesis attribute RLOC of BIT[22]._.x is X0Y11
//synthesis attribute RLOC of BIT[23]._.x is X0Y11
//synthesis attribute RLOC of BIT[24]._.x is X0Y12
//synthesis attribute RLOC of BIT[25]._.x is X0Y12
//synthesis attribute RLOC of BIT[26]._.x is X0Y13
//synthesis attribute RLOC of BIT[27]._.x is X0Y13
//synthesis attribute RLOC of BIT[28]._.x is X0Y14
//synthesis attribute RLOC of BIT[29]._.x is X0Y14
//synthesis attribute RLOC of BIT[30]._.x is X0Y15
//synthesis attribute RLOC of BIT[31]._.x is X0Y15
<... a bunch more of this snipped due to HN message length constraints ...>
endmodule
//synthesis attribute LUT_MAP of myXOR2 is YES;
module myXOR2
(
output O,
input I0,
input I1
);
assign O = I0 ^ I1;
endmodule
That's the kind of thing you have to do if you have to squeeze the last MHz in performance out of an FPGA. That code was part of an FIR filter I designed that, about ten years ago, could not break 150MHz using the "hey compiler, you figure it out" approach. If I remember correctly, the hand-wired filter easily did 200MHz.
It's interesting that both the question and the answer do focus on pattern matching. I maybe mistaken on this but that is really just one use of FSMs.
I've implement event-driven FSMs and to me the biggest "ah ah" moment was that it was trivial to make a list of valid (or non valid) state transitions. I used it in one particular case which was really complex (IMHO) to model and were my code was quickly becoming a gigantic mess. I ended up rewriting that part using an event-driven FSM and things became smooth.
Nowadays I don't like the 'S' in "FSM" that much anymore: I've moved to FP and can't really say I'm missing mutability.
I don't think you need to abandon the S. I think FSMs embody the core of functional thinking. Structuring your computation as a FSM splits your code into your current state and a combinatorial logic block that takes a current state and outputs a new state along with some optional side-effects. Splitting your computations into pure functions that hold state on their end-points sounds very much like the philosophy behind FP.
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