I recently came across the following image:

And I thought it greatly sums up the usual problem. Both users and developers think at vastly different levels of abstraction. To the developer the UI is „just another shell“ around the core and most erratic behavior of the UI can easily be explained by the inner workings of another component in the program. To the user, however, the UI is the program. And she just doesn't bother with understanding anything else. For all intents and purposes it's really magic.

Now, above image is a bit small, unfortunately and I didn't find an original creator or a higher-resolution version, so I created a vector version of the image which is attached to this post. Actually, I made two vector versions, one white on black and one black on white, the latter of which should use up substantially less toner when printed:

The font used on the high-res PDFs versions is the free (and pretty) Fontin font.

I attached the Expression Design files as well, if someone wants the „source“ files. The Design and PDF files are released into the public domain by me.

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:

Talk about weird problems that can occur:

I never knew there could be compatibility issues with cables …

If there is one thing the Windows Command Processor (cmd.exe) can do (except starting other programs) it's string processing. Not at Perl's level but certainly more sohpisticated than the C standard library (not counting regex here).

I was just playing around a bit and came up with this:

And it works in Unicode, too:

Ever wondered which exact executable will be executed when running a command from the command line? UNIXes and Linux have which(1) which tells that. There are implementations on Windows, but not one in batch language I was aware of :-)

UPDATE (2008–06–01): I found another bug that manifests itself most prominently on Windows Vista x64, concerning paths with closing parentheses in them (as happens when installing x86 applications there). That means I have to do a bit escaping as soon as those paths show up in the argument of a FOR loop. Using ! and FOR /F seems to work somehow, except that I only get a single token from that.

A while ago a fellow student of mine held a „lecture“ for pupils on programming where I should help helping the kids. Prime numbers are a nice topic for introductory courses, since they are easy to understand and a simple search for them is written in a few lines of code. I suggested mentioning the Sieve of Eratosthenes as well as giving an implementation of it, since I think the algorithm is pretty easy to understand and nicely fast in generating the first n primes. The programming language we used was Pascal and I was able to come up with a naïve implementation in a manner of minutes. Glancing over the program again I thought it wouldn't be that hard to implement in CMD, so I tried … there was still plenty of time left so I wrote the following perversion of batch language :-)

There is a practical limit for n, though. The batch runs fine for 100 or even 1000 numbers, but sieving 20000 numbers already takes about a minute on my notebook. And there was a point at which the environment seemed to grow too large to handle in a sensible way.

And no, it does not compute all this in parallel, though I wonder how hard it would be to create batch files that calculate things concurrently in multiple processes; might actually make use of all those multicore systems out there. But I don't have a good idea currently how they should communicate if need arises; files are an option but slow and subject to races … well, I still have a lot of lectures I only attend physically, so my mind may be free to solve these problems :-)

This innocent batch file sports a finite state machine for parsing the parameters which may be given by the following regular expression:

I allow both German and English notation (w vs. d as separator of number and sides of the dice) as well as optional adding of all rolls and a constant (for Shadowrun 3 initiative rolls). Due to the nature of parsing the user will get pretty precise feedback where a parsing error occurred and what was expected (Hmm, this may call for a general batch FSM generation tool :).

A few limitations, however:

• Rolling is slow, so 1000 rolls will take a while.
• Since CMD only knows 32 bit signed integers, the maximum number of dice is 2147483647.
• Since the results are stored in a single environment variable which are limited to 32764 characters, the maximum practical number of dice reduces further. Otherwise the results will be truncated.
• Since CMD's random number generator will only yield random numbers between 0 and 32767 the maximum practical number of sides is 32768, otherwise, no roll will yield a result above 32768.
• Since capping rolls to the number of sides is done by a modulo operation, the results won't be equally distributed if the number of sides is no divisor of 32768 (might be especially noticeable above 16384).

The code is nearly undocumented, but that just adds to the fun :-)

@echo off
set X=0
echo set /a X+=1 >>%0
echo echo %%X%%>>%0

... But it does work ... each time you run it, the list of numbers grows by one :-)

The interesting part here is that the lines added during running are executed in the same instance of the running batch.