Tuesday, November 18, 2008

The Foisting of An Infinite State Machine

"I will not allow you to foist this convoluted scheme on the bank!", Sam yelled.

This was fun in a lot of ways. First of all come on this is a bank, three or four full floors of programmers all enthralled by nothing more technical than getting through the day unfired and back on the train home to their families and here is this aging cardpunch nutjob throwback not only noticing Someone Else's Code but caring?!

Second, I did not make that up. Sam actually used the word "foist" without trying. I use SAT words all the time but I am usually trying, you can see my eyebrows arch a little as my language organ reaches for the thesaurus. Nothing shabby about "convoluted", but "to foist"? And Sam tossed that off in earnest in anger in the heat of diatribe sans affectation and it is not clear to me I have ever before or since heard the word used in vitro. Which brings me to the third fun bit.

Sam was Jewish. Classic Orthodox home-by-sundown-on-Friday Brooklyn Jewish and of course he would be good with words. Right, get all PC on me and denounce me but what can you say?, he used "foist" in a sentence on the fly and I think I win on this. So there he is with this classic Billy Crystal Princess Bride accent yelling at me for foisting convoluted code on the bank.

"I will not allow this!" he cried. "I will stop you!"

Oh, please, tho Sam was a sweetheart. Yeah, "was". I heard he passed, Lord keep him, a beautiful soul. I could have choked him in that moment but at least he was attacking me for Code Quality. What was my sin?

I had been tossed a throw-away job of persuading two applications to exchange information reliably when either app was free to collapse in a heap at any time and I was not to lose any information. Nowadays we just pull packages off the shelf for that but this was a while ago. Oddly enough in my first IT job ever I had had to do the same and it was fun because there was nothing theoretical about it, the two applications did even during development reliably disappear left and right allllll the time. Decnet, PDP-11, RSTS/E, 1981... you understand.

What was different was that somewhere in the intervening ten years I had gotten this crazy idea of creating a domain-specific language to make it easier to develop a software Algebra tutor so I had gotten a book on compiler design because I did not realize I could Just Use Lisp. I do not like reading so I did not get very far but fortunately one of the earliest chapters was on parsing so I ended up learning about finite state machines. Oh, sorry.

This post came up because I am doing some Web2.0 programming these days from Lisp and I wanted to send over Lisp sexprs and since Javascript for some reason lacks a Lisp reader I was going to have to parse it myself and after ten minutes of trying to do it without a finite state machine I realize, damn, I should code up a finite state machine.

I will not in this space try to explain what is a finte state machine but it is really simple and powerful and no matter what level programmer you are you need to have it in your, well, toolbox. I think the example I learned on was a pocket calculater when folks still had those. Your initial state is "initial". Duh. Then what happens? Oh, I got "/". Bzzt! Or just ignore it and my next state is still "initial". Now I get a "1". Great! Save that, my new state is...I dunno..."got a digit". We're on a roll. But wait, what other inputs could I get? A "+". Ummm...well, it seems no different, but we'll say "got a plus sign", and indeed when we are done one of the cool things that can happen is that as we fill in the table we may well discover that the row for the state (did I mention that rows were for states and columns were for inputs? Sorry) ..the row for the state "got a plus sign" might be no different from the row "initial" and we first go "whoa, enlightenment" and then collapse the two rows into one. I digress.

But the idea is that we just break it down into cases. A fun example is that we now know whether a "+" is addition or a plus sign (or an error) without really trying, because we have aggrssively exploded the analysis into all these different states like "just got a digit" or "just got a left parens" or...yeah, it goes on, but guess what? Here comes the name! "Finite State Machine"! There are only so many!!! You may think there are a kabillion but after ten you are done, maybe after twenty. And you can collapse inputs (1-9 become "positive digit") and so you have a finite number there. Do you now have 150 cases to handle? Yeah, and each one you can code in your sleep. The alternative is one hyperglutionous mass of conditionals, tests, and branches that will fail on the one millionth execution because of a first time path execution.

Back to Sam.

I have realized that the reliable exchange between two autonomous systems permitted to fail at any point will best be solved using my old friend the finite state machine and I have enthusiastically shared this with Sam. Somehow I am now being denounced for using an algorithm learned from the top book in compiler design. Specifically, I am being denounced for foisting. I will be stopped. The bank will be saved from my convoluted scheme.


Well, what can one anachronistic lost in the Torah yamaha wearing card punching goto coding nut job do? Would you believe he could force a code review? Nay, a defense. Sam forced a frickin defense of about thirty lines of the best simplest most powerful correct code that bank had ever seen. Mind you Sam is also the man who produced my favorite line of code ever, using the Vax Basic statement modifier mechanism:
return if flag
That's right, an action at a distance code teleportation straight out of the middle of seventy line for loop using a flag he had named.... flag. You can imagine my reaction. And this guy is challenging my code?

If you are not yet suitably horrified, understand that novice programmers were regularly crashing production runs because no one anywhere was looking at their code and they were going to call a meeting of like twelve programmers to review my foistation of convolution upon the bank? Sorry, my ire is showing. Chase cut to.

Code review/defense: twenty minutes, here it is, any fucking questions?

Yes that was pretty much the tone of my presentation -- I like to consider people skills one of my strengths. And then Sam spoke and you will see why I loved him. At pain of repetition, probably no one else on those four floors would have even listened to me as I bragged on my FSM, but go to the mattresses to stop what he thought was bad code? One in a million. And one in ten million in my experience would have said what he said.

"OK," Sam he said. "That looks fine."

Of course now I am pissed off because I am just getting my turbines spun up for a full bore antler to antler knock down drag out kickin and a gougin in the mud and the blood and the beer round fifteen thrilla in manila finish and Sam is saying...fine?

"That is simple," Sam continued, gesturing towards my whiteboard diagram. "This infinite state machine idea is complicated, but the way it works is simple."

The beauty of that being......no. I would only ruin it.

RIP, Sam. RIP.


PJB said...

You cannot parse s-exps with a FSM. You need a stack machine, or at least, a FSM with a counter.

Said otherwise, FSM are equivalent to regular expressions, and you cannot parse s-exps with regular expressions, you need a recursive parser.

Of course, given than we don't use TM, but finite VN computers, we only deal with FSM, and we don't parse s-exps in general, only s-exps that can be held in our computer memories.

But still, it's easier to write a Recursive Descend parser for s-exps than a FSM.

Kenny Tilton said...

PJB: Well then I must be a god because I managed to do it. Moral: sometimes it helps not knowing what one cannot do.

Kenny Tilton said...

btw, PJB: "You cannot parse s-exps with a FSM. You need a stack machine, or at least, a FSM with a counter."

The neat thing here being that the second statement nicely identifies the error in the first statement, so having written the second statement you could have simply gone back and erased the first in which case you could then erase the second. One of those matter/anti-matter deals.

Antsan said...

I think the point is that an FSM doesn't have a counter. It's just not part of an FSM. An FSM with a counter is more than just an FSM.