I’m doing finite state machine design for work today, to handle communication between our embedded system and a new GPRS modem.

To refresh my memory about these things, I went hunting around on the web. I’m surprised by how few good resources I found, considering this is a cornerstone of computer science. Most resources are very academic/theoretical, with too-simple FSM examples like the alarm clock, traffic light, etc. Most are focused on the digital logic design side of things, as opposed to the compiler design/Yacc/Lex side. Maybe I’m not googling for the right things, maybe this is too common, but I would expect to find a lot of finished example code for finite automata.

FSMs are simple as long as you follow the standard procedure for them:

• Write a human description
  
• Draw out a state/transition graph
  
• Do some state minimization / Quine-McCluskey voodoo
  
• Build your transition table
  
• Write the code
  
• Test and enjoy!

I remember encountering CircleMUD when I was about 14, and learning C by reading it. It is chock full of all the most important procedural programming concepts, and it’s well written and well commented. It has a couple good state machines, excellent examples of TCP/IP socket code, pointers and structs galore, binary/flat file management, and some well-designed algorithms. Were I teaching computer science, this program would be the syllabus, and for a bit of back-story, students would read a few seminal books (a basic algorithms and data structures book, TCP/IP illustrated, and a compiler/FSM book). After my course, you’ve got yourself a minor.

I think it’s how we all learn best: we need some context in which to base the theoretical knowledge. Otherwise it’s just a vacuum of theory, with no concrete output, no results. It’s really only meaningful when you’re high as a kite, or if you’ve already had a lot of concrete experience and you’re looking to zoom out.

One benefit of OSS is that its increased this library of good code from which many can learn. It’s accessible. I’ve always wanted to step through the core of the Linux kernel source. There’s even a book of the Linux kernel source, neatly annotated.

Of course, OSS has also added to the vast wasteland of horrible code. Choose wisely the code you wish to learn from.

I think there’s a web site idea here somewhere (and it’s not Freshmeat or Sourceforge).