Know the Words: State Machine

Hello again, World.

Today we’ll be doing two things. First, we’ll be learning what computer science people mean by state machine, and second we’ll be picking up with our implementation of a Zork interpreter in C#. (I am, with increasing distance, following Eric Lippert’s discussion of the Zork Machine in OCaml.) My code is here on Github. We’ll see in a moment why these topics go together. (Also, please note that state machine is an official, talked-about-in-grad-school kind of term, and my explanation is certain to fall a little short; this is a beginner’s blog, and I’m a bit of a beginner myself, so the goal is to get everyone to understand the term, not get everyone ready to defend a thesis on it.)

Basically, a state machine is an abstract way of talking about machines that store some state. A state machine has a state and an input, and uses these to calculate the next state. We can think of a computer as a machine that has state (what’s in the memory now) and inputs (commands from the user) that calculates a new state (change to the memory) based on the inputs. [Aside: this explains why restarting computers can be helpful. When the computer turns on, a series of predefined commands are executed, designed to get the computer into a state that is generally usable. If we have somehow gotten our computer into an unusable state, turning it off and letting this predefined steps can get it back into a usable state without our having to figure out what went wrong.]

On my Android phone, I use SwiftKey, and I love it. SwiftKey (or, if you prefer, a mechancial typewriter) can be understood as a state machine. We have basically three states: normal, the shift key has been pressed, and the caps lock key has been pressed. If you press ‘a’ in normal, you get a lowercase ‘a’. If you press ‘a’ in the shifted state, you get an uppercase ‘A’, and state transitions back to normal. If you press ‘a’ in the caps locked state, you get an ‘A’ and the state doesn’t transition back to normal. If you press the shift/caps lock key again in the caps locked state, you get no character, but the state changes back to normal. Here’s a table:

 

State Input Output Next State
Normal A letter That letter, in lower case Normal
Normal Shift/Caps (the same key on Swiftkey) none Shifted
Shifted A letter That letter, in UPPER case Normal
Shifted Shift/Caps none Caps Locked
Caps Locked A letter That letter, in UPPER case Caps Locked
Caps Locked Shift/Caps none Normal

If you’d like, take a moment to walk through the table in your head. “If I’m in state Shifted, and I press a letter, I’ll see that letter appear in upper case, and then I’ll be back in state Normal.” The entire behavior of the keyboard (well, except for the emoji, special symbols, auto complete, and voice recognition) is modeled in this table.

Thinking of computer programs as state machines is super helpful. (Actually, I’m convinced a lot of tech support calls are because people don’t use computers in two separate steps: Get the machine in the state you want, then issue the command you want to do.)

What does this have to do with Zork? Well, the way that strings are decoded by the Zork story files is a state machine. Basically, there are a few states: lower, upper, symbol, abbreviation, and special. The way a program prints a string is by reading the next number, checking the state, and then acting on it. Like this:

  1. If the state is lower, the next number is an index into the lowercase alphabet.
  2. If the state is upper, the next number is an index into the uppercase alphabet, and the next state is lower.
  3. If the state is symbol, the next number is an index into the symbol table, and the next state is lower.
  4. If the state is abbreviation, pause this machine. The next numbers make an index into a table of where abbreviations are. Go look up that abbreviation, and decode the whole thing (using this same process) and insert it here. The next state is lower.
  5. If the state is special, the next two numbers form the bits of an ASCII character that we don’t have a symbol for somewhere else.
  6. If the next character is the designation of a state, print nothing, but switch to that state.

One nice feature of C# that I learned from reading C# in Depth is that you can use the foreach syntax to make your own state machine, and don’t have to write a lot of the boilerplate code for tracking what state you’re in. My somewhat messy implementation of this state machine is here.

Till next week, happy learning!

-Will

 

Explaining Names

I’m adding a new section to the blog. It’s called “Explaining Names.” In it I explain names.

Why bother explaining names? I explain names because names are rarely accidents. The name of a thing is what it’s discoverer, or author, or publicist or whoever thought would be a good way for everyone in the world to remember the thing. When we explain names, we guess what this originator of the name was thinking, which, because the originator of the name presumably understood what he or she was naming, tells us a lot about the thing.

Continue reading “Explaining Names”