Yay. Now that Stack Overflow has bronze badges for tags I got a whole bunch of them (they are awarded for 100 upvotes in a specific tag). But by that I rose into a quite exclusive circle: The only person with a batch-file badge:

Specializing in obscure languages pays off after all. Then I'm one of only two persons with a batch badge:

And PowerShell doesn't look too bad either:

That's me among a bunch of PowerShell MVPs :-)

It's been a few years by now I am writing batch files every now and then, some for trivial tasks, some for things other people would just declare me insane for doing it with batch files. Anyway, cmd has become boring by now. I now want to concentrate on another target for writing batch files, one that's still very much alive, at least on 32-bit systems: command.com.

In a way, cmd was too powerful. It's more fun the more limited you are so I'll gradually rewrite all batch files on this site to run in command.com instead. That also allows them to run on all non-NT versions of Windows as well as DOS. I consider that to be quite an improvement over the limited platform availability of cmd.

Cellular automata

One-dimensional elementary cellular automata are very simple. You just got a single row of cells which have one of two states: On or Off (0 or 1, living or dead, whatever you want to call it), so they can be nicely represented by a simple two-color bitmap.

States in cellular automata change according to the neighbourhood of a cell in the previous (global) state. Let's say you're a living cell (On, 1) and your neighbours in both directions are dead (Off, 0). Suppose you also have a table that states that your state in exactly this case changes to dead (might happen, maybe you just were too lonely to exist, don't blame me). But in another configuration your left neighbour might still be living and in that case you get to live on. Or in yet another configuration you are a dead cell and regardless what your neighbours are you change state to living.

State transitions

Such a table essentially needs only a few things: State of a cell, state of all neighbour cells (two in this case) and the state of the cell in the following generation. We can visualize this as follows:

In the top row we have a cell with two neighbours, one left, one right, so three cells each. The bottom row gives the following state for each configuration. As you may have noticed, there are only eight possible configurations. And we can impose an order on them as I have done here. And the relevant part, once that order is established is simply a string of eight zeros and ones—so essentially eight bits. We can simply write this rule as a number. What wonderful way of shortening things. This numbering was conceived by Stephen Wolfram, a British mathematician and thus it's called Wolfram code or a Wolfram rule.

The rule pictured above is rule 30.

Display

So we now know that such a cellular automaton might be described by a single number and that it can change states. What good is that?

Well, we might display a certain state of the automaton as a series of either black or white boxes:

and then we might display each of these states below the previous one:

et voila, we got a nice picture. Slightly chaotic, but that's usual for rule 30 and we got some nice recurring triangle formations in there.

So the point of all that was to generate a weird-looking image. Now for the fun part of this. Programming such a beast.

The code

It isn't exactly complicated to do this, so lets start at the top:

We obviously need some control over how much is calculated and rendered. I put a single cell with state 1 in the center of the first row (initial state) so it's advisable to choose an uneven width because many patterns fan out to both sides (as seen above) and then they reach the left and right edge simultaneuosly. Height might be chose for a similar reason, since as the pattern fans out and reaches the sides it gets meaningless pretty quickly.

If the rule is given as the first parameter we only ask for it if it lies outside the permitted range (0–255), else we ask anyway until a correct rule is given.

Following that I wrote a simple subroutine which dissects the numerical rule into its eight parts:

So after that we have eight variables, named <cmd>wolfram_x</cmd> with <cmd>x</cmd> being a number from 0 to 7 which hold the successor states for each configuration.

We then initialize the area in which we store the states of each cell for each generation:

Basically we just initialize everything with zero and add a single one in the center of the first generation.

We have a problem with this approach, however, since when states are computed they need a neighbourhood. But how does the neighbourhood look for the first and last cells in each row? At first I simply put another cell to the left and right of the row, containing a zero. This works fine for most rules and we leave it as that for now. How one would implement this I leave as an exercise for the reader.

We might need a subroutine to display the whole area:

As you can see, that are actually two subroutines. They come in handy later.

What is still missing, however, is the calculation of successor states. So let's do that now.

Nothing fancy here, we just delegate the computation of a single cell to another subroutine. As you may note we display the calculated row immediately after we calculated it, this makes the watching experience while the batch file runs a bit less boring as we see a new line every few seconds (yes it is that slow).

Here we calculate the new state for a given cell, by using another helper subroutine which looks up the specific case from the table. We make use of the fact that the configuration of a cell and its neighbours are essentially three-bit numbers and the table is laid out in such a way here that we can access it simply by converting the configuration into a number between 0 and 7. The code for that looks a little ugly, since lots of escaping is needed (I escaped the parentheses just out of fear they might break something, as they often do when nesting structures).

But that was it, essentially. Running the batch without arguments produces the following prompt:

entering, say, 54 in there, yields the following picture:

The actual source code is a bit longer, since I offer an option how the sides of the area are handled (all zero, all one, wraparound and copy, the last of which is now the default which seems the most sensible to me—rules like 169 look very different when calculated with the edges being zero).

I am now working on SVG export from within the same batch file and I hope I found all major bugs by now. But the first working version was just 54 lines long. I think, had I been using Java instead (which was the other choice here), I would have needed significantly more.

UPDATE (2008–12–26 16:21): SVG export is now done and works as it should. At the moment I am mis-using the terminal server in the uni to compute all 256 rules simultaneously:

Aah, recursion, the favorite pet of every programmer. Surely it must be possible to recurse even in Windows batch files (I'm still trying to prove Turing-completeness, by the way :-)).

The first tentative test would be an infinite recursion:

And know what? It works. Well, kinda:

But that's ok, we didn't expect this to do anything useful except of causing a stack overflow. But as we can see, cmd has a stack of some sort and seemingly manages it well enough to allow for recursion.

Time for another test, this time something remotely practical: Factorials. Never mind that those are more easily done with iteration, we want to make sure that recursion works properly:

We need a temporary variable at the end, unfortunately, since cmd does not allow computations inline. But aside from that it looks pretty much how it should. The case for breaking the recursion is also provided in the form of an IF block (sorry, no functional programming niceties, like different function definitions).

But does it work? Oh, sure it does:

And my calculator tells me that those are actually correct. 12! is unfortunately the highest factorial we can compute with it, since we are limited to 32-bit signed integers. A minor bug is still present when using negative numbers, though (infinite recursion, again). This is corrected in the attached version (as well as giving a helpful hint when running the batch without arguments).

Just as a side note, a fun way to implement factorial calculation by leveraging cmd's own „calculator“:

We simply construct the complete term and evaluate that by using SET /A. Nothing fancy, but probably faster than the recursion.

What happened here?

Note, that if you have the parentheses in a variable (such as the 32-bit program files directory on x64 systems), then you need to either use delayed expansion or a subroutine (to avoid the parentheses).

Things to learn from this: The escape character is applicable anywhere in batch files. It causes every character to be recognized as not being part of the syntax.

Seriously, I get some strange referrers from Google. Who the hell gets the idea to clear that from a batch file? I mean, most programs store that kind of stuff either in the registry or in some ugly binary files. The first option is the easier one, at least on Windows 5.1 onwards, since you could use reg.exe. The other part is trickier except the application doesn't mind a missing file.

As for Word 2007, the most recently use files reside under <text>HKCU\Sof­tware\Microsof­t\Office\12.0\Wor­d\File MRU</text> so a simple <cmd>reg delete „HKCU\Software\Mi­crosoft\Office\12­.0\Word\File MRU“</cmd> will do the trick. Of course, you can still put that into a batch file.

It works, but reminds me a bit of How do I inflate a bicycle tire with a potato?.