A Deterministic Finite State Machine in HTML
Thomas Jansen of the Shift Happens blog has a post up titled A Game in plain HTML (no JavaScript, no Flash, no PHP), which sparks an interesting conundrum concerning what and what isn’t a computer program with an interesting example. The goal is to set all squares to white and the center square black:
Click on a Square to Play
Such a demo would be unextrordinary if it were written in JavaScript or some other programming language, but Jansen’s demo is written purely in HTML. This means that what you are seeing in the above example is a webpage, with each square as a link to another webpage, just like any website on the Inernet.
Jansen has programmed this game using only HTML pages and hypertext links. The programming logic in a visual programming interface would look something like this:
| IF STATE= |  |
||||
| AND SELECTED_SQUARE= |  |
||||
| THEN |  |
||||
| IF STATE= | |
||||
| AND SELECTED_SQUARE= |  |
||||
| THEN |  |
||||
So hidden behind each box on the initial page display are the following links:
It takes 512 HTML files to cover all the possible states these nine squares can be in. This is not a true program, but a Deterministic Finite State Machine, like a subway turnstile that either lets you through or blocks your entry depending on whether you feed it money. It has a set of predetermined states.
Naturally, this kicked off a lot of complaints in the comments of Jansen’s post, such as:
I’m not sure I can agree that this proves that HTML is a programming language. I can implement the same game with a 512 page book by using a “Choose Your Own Adventure” scheme (”to choose the bottom square, turn to page 437), but I certainly wouldn’t consider books to be a programming language.
to which another commenter responds:
That’s actually a great metaphor for [Deterministic Finite State Machines], thanks.
Now I want to write a choose-your-own adventure with just webpages.
The above puzzle can be solved in five moves. Use your mouse cursor to select the hidden text below to see the algorithm to solve the puzzle.
<HIGHLITE HERE FOR SOLUTION>
- Click a corner.
- Click the opposite diagonal corner.
- Click a black corner.
- Click the opposite diagonal black corner.
- Click the center.
<STOP HIGHLITING HERE>
Heh. The lengths some people will go to to prove a point are never surprising. That’s pretty neat. I guess it’s a tad inefficient in space/bandwidth, but super-efficient in CPU use [i’m not counting the http calls but maybe i should be] :)
Comment by ClintJCL — October 16, 2008 @ 1:42 pm
You would have to count the http calls.
This state machine could be easily represented by 9 binary bits. Even if you were to inefficiently use a 16 bit number to hold that value, the overhead of the http calls is still much greater than the calculation performed.
Comment by chriggy — October 16, 2008 @ 3:46 pm
But would it be more than the http call required to send me javascript code to display such a machine in the browser? I’m still thinking yes, but it’s a bit closer then.
Comment by ClintJCL — October 16, 2008 @ 4:46 pm
Depends on how often you click to get to the end. Each of the pages is 1546 characters, plus the actual overhead of the http request. Add some more overhead for actually parsing and operating on the http and displaying it.
With javascript, this would be no more than a few lines of code. The biggest part would be the lookup table. Since he needs 512 html pages, I’ll assume there are 512 possible states, with 9 possible outcomes each. So if we use a lookup table, that’s 512*9*2=9275 bytes. BUT, it only needs to be sent once. And there’s probably a more efficient way to do it too.
Sooo, roughly 6 clicks before the JS becomes more efficient.
Not that it’s still not a neat implementation.
Comment by Chriggy — October 16, 2008 @ 8:07 pm
Hmmm, but you can win in 5 clicks! So if you win in 1 try, you “win” in another sense too.
I’m surprised it’s 1500 bytes for the damn thing! My guess would have been closer to 150, but I didn’t look too closely (didn’t view source or pay attention to status bar).
Comment by ClintJCL — October 16, 2008 @ 8:16 pm
And yes. It’s very neat.
I’ve actually thought some areas of some websites in some particular circumstances might benefit from pre-rending their pages in some sort of fashion like this, simply as a way of using the CPU during less popular times to render pages to save you CPU time during more popular times. But I guess it’s always going to be easier to throw more CPUs at the problem… But if you only had one… and it was irreplaceable….
Comment by ClintJCL — October 16, 2008 @ 8:18 pm
This conversation is much more intelligent and constructive than the user comments Thomas Jansen got on his original post. Thanks guys!
Comment by ideonexus — October 19, 2008 @ 7:59 pm