"Have we forgotten what's wrong with goto statements?" asked Andrew Koenig recently. Bradford Miller had a pithy reply: you need too many "thumbs" when reading code. Better to use a language with proper control structures, not bodge them from labels that will, for all a reader can tell, leave you leaping around your program like a flea on a dog full of coffee. This reminded me of spreadsheets, which unrestricted cell references can make just as unreadable. So I'm going to show how to write and document a spreadsheet in a high-level language I've implemented: Excelsior, which I've made available here. The spreadsheet runs Life; linking a clear English-and-equations account of Life with Excel's graphic appeal, it may interest school maths teachers, as well as those seeking to write and document safer spreadsheets.
Spreadsheet documentation is notoriously bad, partly because you can't embed comments in Excel as you can in a normal language. This has horrendous effects. Consider that notorious spreadsheet holding 179 "hidden" Lehman contracts which accidentally got unhidden and included in Barclays's purchase of Lehman assets — as Debra Cassens Weiss reported for the American Bar Association Journal, Excel Error by a Cleary Gottlieb Associate Alters Lehman Asset Deal. Had there been a clear specification of what each column represented, and of the contract-selection criteria, could the mistake have been avoided? Perhaps the real culprit was a culture of rush-rush-rush, no-sleep, no-time-to-think. But it shows the cost of spreadsheet errors, and why we must prevent them.
This is a long posting. If your interest is mainly in safer spreadsheets, you may want to skim the opening sections, which explain the game of Life. But as an experiment, I have written this so it can also be used by elementary maths teachers. That's why it's long: I've tried to make it stand alone, with an intro to Life in my first two sections, John Horton Conway's game of Life and Life simulators.
The section after that, Running the Life spreadsheet, explains how to use the Life spreadsheet I mentioned in my opening paragraph. You can run this without needing to understand the rest of this posting. The spreadsheet comes with some predefined Life patterns, explained, not surprisingly, under Predefined patterns.
I then start on how I used Excelsior to write my spreadsheet. As I said, you can download Excelsior from here, and the download includes my Life program. You can use this in several ways. First, it's useful just as a succinct specification of what the spreadsheet does. The equations in it may, therefore, interest students who want to know how Life, or cellular automata, work.
Second, you can use it as input to Excelsior, to generate a new version of the spreadsheet. For example, you can change board sizes, or change the Life rules by adding new cell states or by changing the number of neighbours needed for life and death.
So in the next part of this posting, Writing spreadsheets in Excelsior is a general explanation of Excelsior as a programming language. The section after it, Literate Spreadsheet Programming, explains how I used it to document my spreadsheet. And the section on Iterative calculations in Excel explains how to change Excel's normal behaviour so you can run Life without getting circular reference errors.
Then I come to The program. This is a documented program listing, and has subsections explaining different parts of the program: display_board; board; selected_menu_option; index_of_selected_menu_option; menu_options; start_board; next_board; neighbour_count; blinker; glider; and Layout. It may be the best-documented spreadsheet in the world.
Then, under Compiling Life, I show how to install Excelsior and compile my Life spreadsheet, and propose some ideas for changing its rules. If you're feeling ambitious, you might also like to try the following sections: Compiling a foxes-eat-rabbits model and Compiling a science-fiction generator. These tell you how to compile a predator-prey spreadsheet and the science-fiction generator I blogged in Earth Falls Toward The Sun And Everybody Dies. I end this with a note on a novel kind of recursion.
And finally, there are Life links and references and Other links.
Let me now start explaining the game of
It was invented by
John Horton Conway,
and must be the most famous
Life runs in a rectangular board, where
each cell has two possible states: empty or
occupied. Or, if you prefer, dead or live.
The game proceeds in generations. To get generation N+1 from generation N, make a table the same size and shape as the board. Let's call this the "neighbour count". In the first cell of neighbour count, write the number of live cells immediately bordering the first cell of the board. (By immediately bordering, I mean the eight surrounding cells.) Then do the same for all the other cells.
Then make another table, also the same size and shape as the board. This will hold the next generation, so let's call it "next board". Make each cell live or dead according to these rules, using the numbers in neighbour count:
Finally, copy next board's cells back into the
board. If you do this
correctly, the shape above will evolve like this:
⇒ ⇒ ⇒ ⇒
Subsequent generations will continue to move, taking four steps to shift one cell along the diagonal. This is one quarter of the fastest possible speed, so Life enthusiasts call it "a quarter of the speed of light", or "c/4".
Why these particular rules? In an article that helped make Life notorious, Scientific American's Mathematical Games for October 1970, Martin Gardner writes that Conway chose his rules after a good deal of experimenting, to satisfy three principles:
As Gardner says in a follow-up article, Mathematical Games for February 1971:
Conway was fully aware of earlier games and it was with them in mind that he selected his recursive rules with great care to avoid two extremes: too many patterns that grow quickly without limit and too many that fade quickly. By striking a delicate balance he designed a game of surprising unpredictability and one that produced such remarkable figures as oscillators and moving spaceships.My images above showed one of these remarkable figures, that simplest of self-moving objects known as a glider.
There are many Life simulators on the Web. I like the quick-to-load applet at Paul Callahan's World of Math Online page, What is the Game of Life? This page is studded with buttons that run the applet on predefined patterns. I recommend the "Run 6 Gliders" button in the section headed Gliders. This sets six gliders on a collision course; from the debris, six more gliders emerge, three waddling off to top right and three to bottom left.
You should also try "Run Wickstretcher", which sends a continuous stream of pulses down a steadily elongating wick, and "Run Lightspeed". These are both under the "Artistic Life" sidebox on the right-hand side of the page.
The applet is written by Alan Hensel, and is also linked from his Conway's Game of Life page. It has an Open button, replete with more patterns, of which you should definitely open the "Breeder". Run this on the lowest magnification, Zoom setting 0, with the applet window as big as you can make it!
Because I'm writing about structured spreadsheet programming and documentation, I'll now turn to my own simulator, the Life spreadsheet. I am running it on XP; but because it calls only a few elementary Excel functions, and doesn't use Visual Basic for Applications, I'd expect it to work in any Windows Excel and in Mac Excel.
When you open the spreadsheet, you
should see the
sheet, "Display". It contains: a blank board
where you can type a starting
pattern; a control menu; and, at the bottom, the main
board. It should open with most of the start board
out of view, and the menu near the top:
The pattern in red is a "glider gun", which I've preloaded into the main board. It's famous because it's a counterexample to a conjecture Conway made that no pattern could grow without limit. William Gosper, and his colleagues Robert April, Michael Beeler, Richard Howell, Rich Schroeppel and Michael Speciner, using a program that displayed moves on an oscilloscope — this was 1970 — discovered the glider gun, and won a $50 prize from Conway. The gun does, of course, grow without limit, because it keeps firing out gliders.
Remarkably, the glider gun can be built by firing 13 gliders at each other. I don't know an online picture of this, but there's a printed one in that February 1971 Mathematical Games article.
To step the glider gun through one generation, all you have to do is to press F9. Repeatedly pressing F9, or holding it down, will run more generations, and a stream of gliders will waddle out from the middle of the gun, wagging their tails behind them as they head diagonally down and to the right.
You may want to adjust the zoom. Mine is 50%, which makes all the glider gun visible, but the menu options a bit small. To change it, select View on Excel's toolbar. This will pop up a menu which should have a Zoom option. Selecting this will open a little window with radio buttons, each with a percentage zoom. Select one, then click OK.
To run other patterns, you need to know the spreadsheet's menu options. The first option, Start, copies a pattern that you type. Type a pattern into the start board. Use space to empty a cell you've previously typed into, and any non-space character to make a live cell. Then select Start, and hit F9. The pattern should appear on the main board. Then select Run, also on the menu, and hit F9 again. This will step the pattern through a generation, and you can continue as for the glider gun.
Each solid red square, incidentally, is in fact an "n". They appear as squares because I've switched the cells into the Wingdings font. I'll say more about this at the end of the section on my program's Layout.
Instead of typing your own pattern, you can load one I've provided. Use these options, linked here to explanations of the patterns in the following section: Blinker, Clock, Figure 8, Glider, Glider gun, Lightweight spaceship, Pulsar, Reflector, Relay, Toad, Toadsucker. Select one, then press F9. This will copy it to the board, and it will appear in the display. Then select Run and and press F9 again. Then continue as above.
The final option, Clear, clears the board. This probably isn't very useful, but as a mathematician, I always like to implement the trivial case.
These three are oscillators of period 2. The blinker and clock flip 90° on each cycle; the toad springs up and puffs itself out, then falls back. As well as being figures that every Life fan knows, they're good tests: if they don't work, the simulator is badly broken. (The glider is also a good test, and found an early bug in my code.) Also, the toad shows where the toadsucker gets its name.
The toadsucker is an oscillator of period 60. At its centre is a toad, flanked by two patterns that repeatedly expand and "hassle" it. In Life, I learnt from Eric Weisstein's Treasure Trove of Life, a hassler is an oscillator that can alternately change an object and then change it back.
Yet more oscillators: the pulsar of period 3, and figure 8 of period 8. Mimicking the numeric designations used in star catalogues, the pulsar is sometimes called pulsar CP 48-56-72, where the numbers are the numbers of live cells in each phase.
I've already said that the glider moves diagonally at a quarter of the speed of light. The lightweight spaceship moves along or across at half the speed of light. I've pointed the one in my spreadsheet so that it heads off to the right, eventually vanishing off the end of the long board. Both are amongst the smallest moving patterns in Life — there are, I presume, an infinite number of others. You can read about some of these in David Bell's 1993 Web page, Spaceships in Conway's Game of Life Of Blinkers, Jellyfish, and Everything....
Watching the glider gun, it's natural to ask whether its gliders could carry information. Could we build a universal computer out of Life components? Indeed so: this page shows a Turing Machine designed by Paul Rendell. In principle, you could even implement Excel in Life, and then another Life on top of that. But the result might be rather slow. Even more difficult would be cajoling Microsoft to give you the source code of Excel.
With universal computation in mind, Life enthusiasts spend much time looking for patterns that manipulate glider pulses: the Life analogues of NOT, AND, and OR gates. But because Life is two-dimensional, we also need components to direct pulses in the right direction, and I've put two of these in my spreadsheet: a reflector and a relay. The reflector reflects an incoming glider through 90°. There are many reflectors known, and a bit of Web-browsing tells me that they tend to suffer from the disadvantage that, after reflecting one moving object, they take a huge number of cycles — perhaps several hundred — before they are ready to reflect another.
The relay continuously shuttles a glider between two reflectors.
Of course, the brain is a computer, and could (most computer scientists believe) be implemented on a Turing Machine, and hence in Life. There is actually a science-fiction novel that takes this idea to its limit, Greg Egan's Permutation City, reviewed here by Cosma Shalizi. Read Egan's novel and discover what it feels like to be implemented by a cellular automaton!
The rest of this posting is mainly about how I programmed the Life spreadsheet, and how to regenerate it. My program lives in a text file, which can be edited with a bog-standard text editor such as Windows Notepad. It consists of commentary interspersed with code, and — as I said in my introduction — combines a clear English-and-equations account of Life with Excel's graphic appeal. If you are familiar with Excel formulae, or with conventional programming, it easy to modify the Life rules. For example, you could introduce new cell states or change how many neighbours are needed for life and death.
Before delving into the program, I'll briefly explain Excelsior. Excelsior programs are text files. To make a spreadsheet from them, you run Excelsior as described in Compiling Life. This translates equations in the program into Excel formulae, then writes these to your new spreadsheet.
Actually, the equations are Excel formulae, except they refer to table elements instead of cells. Tables are rectangular groups of cells, like arrays in C++, Java, and other languages. In essence, a program declares tables, states their sizes, and describes how to calculate their elements with equations. Separate layout statements specify how the tables map onto worksheets. To translate a program, Excelsior works out from the layout statements and table sizes where each table goes on a worksheet, and then replaces table elements in the equations by cell references to give Excel formulae.
Most programming languages assume program text to be code unless inside comment delimiters. For example, C++ and Java assume stuff between // and the end of the line to be comment: exposition meaningful to a human but ignored by the computer. They do the same for anything between /* and */ .
But this is not the only way to explain a program. When we write mathematics, we write English commentary separated by indented equations. The English is primary, because we emphasise explanation over "code", that is, over equations. Some computer scientists believe we should program in the same way, as this quote on literateprogramming.com by Donald Knuth proposes:
I believe that the time is ripe for significantly better documentation of programs, and that we can best achieve this by considering programs to be works of literature. Hence, my title: "Literate Programming."
Let us change our traditional attitude to the construction of programs: Instead of imagining that our main task is to instruct a computer what to do, let us concentrate rather on explaining to human beings what we want a computer to do.
The practitioner of literate programming can be regarded as an essayist, whose main concern is with exposition and excellence of style. Such an author, with thesaurus in hand, chooses the names of variables carefully and explains what each variable means. He or she strives for a program that is comprehensible because its concepts have been introduced in an order that is best for human understanding, using a mixture of formal and informal methods that reinforce each other.
I've made Excelsior work in both modes. In its default mode, it reads programs from .exc files, which use the same comment delimiters I showed above.
But Excelsior also has a Literate Programming mode, wherein it makes (and then generates a spreadsheet from) .exc files by preprocessing .lexc files. In this mode, it treats any text indented by two or more spaces as code, and everything else as commentary. It writes the former to the .exc file verbatim, and the latter enclosed in /* to */ symbols.
In this mode it also translates
the .lexc files to Web pages, styling
code in a "computer" font and putting
it on a pale background so it
stands out from the commentary. Table
names get cross-referenced so that each appearence of
a name in the code links to its definition.
a foxes-eat-rabbits model, I point you at an example; here
is part of one page:
You can see all the HTML files, and the spreadsheet, here.
This, in fact, is how I prepared the program description that follows the next section: I wrote it as a .lexc file, preprocessed it into HTML, and then tweaked it to fit in with the rest of this text.
I sometimes like to imagine that I am a plumber and Excel is pipework. In most spreadsheets, water enters the house from the supply pipe and passes each spot only once before arriving at the drains. Er, output cells. Though some spreadsheets, it must be said, are so badly written you might as well dump their outputs straight into a sewer. Which, really, is what I want to remedy with my research.
At any rate, my Life spreadsheet is unusual. Its calculations are organised in the way described at the start of the introduction to Life, with the board in one table, the neighbour counts in another, and the next generation in a third. Because I copy the "next board" back into the board, cells in the board depend on themselves. Excel is perfectly capable of detecting this, and in normal use, will warn about "circular reference" errors. This is partly because the circular dependencies might indicate a typo, and partly because if Excel were to try to calculate in their presence, it would be like flushing water round and round the pipes for ever. We need to tell it not to give the warning, and not to get its calculations into an infinite loop.
I've already done this with the ready-made spreadsheet, which is why you must press F9 to run a generation. But if you use Excelsior to make a new spreadsheet, you will need to do it yourself. Here's how. Go to the Tools menu on Excel's toolbar and select Options, then select the Calculation tab on the window this pops up. This has three radio buttons at the top: click the one labelled "Manual". Below them is an "Iterations" checkbox and a "Maximum iterations" field containing the number 100. Click the checkbox so it has a tick in, and change maximum iterations to 1. Then click OK.
There is a second thing we may need to do, this time in our program. Like the switch to iterative mode above, I learnt it from Iteration & Conway’s Game of Life, a blog posting by Chris Rae, a program manager on Microsoft's Excel team. He explains:
The Game of Life is played on a board which flips state in one single move, and unfortunately what we’ve made is a board which will change as we iterate through the cells establishing their new values. The way the game is supposed to work, no changes are made as you run through the cells — you just work out what the new values will be and then set them all at once at the end of the pass. Fiddlesticks.
We need to find some way of saying to Excel that the number of neighbours the cell has should come from the board as it stood at the beginning of the iteration, not from the board as it stands now with us in the middle of modifying it. To do this we can take advantage of one of the powerful foibles of iterative calculation mode — in iterative mode, Excel will calculate worksheets one by one in alphabetical order.
So — to get around this problem, we can create a new sheet containing the number of neighbours for each cell and we know that this sheet won’t be calculated until the whole of the main grid has finished. Let’s go ahead and rename our main sheet to "1.run" and create a new "2.nbors" worksheet. I’ve used the numeric prefixes to remind myself that these sheets need to be calculated in that order. In actual fact in this instance it doesn’t matter in which order they’re calculated, but for other iterative sheets it might well, and I find it makes debugging easier.
As far as I can see, putting these different tables on different sheets should be enough, for me. I don't think I also need to choose sheet names that make the sheets be calculated in a specific order, because with my spreadsheet, there's only one order that makes sense. But I'm not an expert on this aspect of Excel, and may be wrong, so I have prefixed my names as Rae suggests. This will become evident under Layout.
Now let's look at the code for the Life spreadsheet. This is organised as I mentioned above: one table for the board, another for its neighbour count, and a third to hold the next generation which this determines.
Actually, I keep two copies of the board. When calculating the effect of the Life rules, I use 0 to represent an empty cell and 1 for an occupied cell. This makes it easy to work out the number of neighbours.
But when displaying a cell, I use "n" for an occupied cell, because of how it appears as a solid box in the Wingdings font. I shall explain how to switch the display board into this font at the end of the section on Layout; for the moment, let's just assume I have done so.
So there are two copies of the board. In general, separating display from internal workings is good discipline: it stops the workings getting cluttered by such matters as choice of natural language, plurals, character sets, colours, and output for users with poor sight. As Phil Bewig says in a safer-spreadsheets paper How do you know your spreadsheet is right? Principles, Techniques and Practice of Spreadsheet Style :
Keep input, logic, and reports in separate sections of a spreadsheet, preferably on different tabs. That way you can always see the assumptions neatly in a single place, formulas are less likely to be overwritten, you know where to go to make changes, and output can be formatted for the reader while logic can be laid out for the developer. If you can’t put the three sections on separate tabs, arrange them on a single tab in a stepped diagonal so that rows and columns can be inserted or deleted in each area without affecting the other areas. But beware the false modularity of separate worksheets; since all cells in a worksheet are globally readable, and globally writeable with a macro, using separate worksheets hides no information.
Let's now look at the display board. The program listing is divided into sections headed by the names of tables, and this is the first.
In my code, I call this table "display_board", and I regard it as a function, which maps an (x,y) position to the contents of the cell at that position. A mathematician would write that like this:
display_board : X Y → Swhere X is the set of possible x positions, Y is the set of possible y positions, and S is the set of strings allowed in cells. I chose a similar notation for Excelsior, and so this is how I declare display_board to be a table:
table display_board : board_x_range board_y_range -> text.
The names "board_x_range" and "board_y_range" stand for the set of possible x and y positions. I declare them thus:
type board_x_range = 1:board_width.
type board_y_range = 1:board_height.
When programming, it's good to plan for change. People may want to change the board size, so I've made that easier by coding the upper bounds of board_x_range and board_y_range as named constants. Here's how I declare these and give them values:
constant board_width=10.So all I need do to generate a spreadsheet with a different sized board is to edit these and recompile this program! The sizes above, by the way, are for a smaller spreadsheet than the one I linked to, whose board is 70 × 35.
And finally, having defined what display_board is, I must say how it gets its contents:
display_board[ x, y ] =The way to read this is: the cell at position (x,y) of the display board is "n" if the cell at position (x,y) of "board" is 1, and " " otherwise.
if( board[ x, y ] = 1, "n", " " ).
The table "board" in the above equation is the board in its internal representation, with empty cells stored as 0 and occupied cells as 1. It must range over the same coordinates as display_board:
table board : board_x_range board_y_range -> general.
The board can get its contents in various ways, depending which of the menu options described in Running the Life spreadsheet the user selected. These are:
In code, this becomes:
board[ x, y ] =To shorten my listing, I've assumed only two predefined patterns.
, if( len(trim(start_board[ x, y ])) = 0, 0, 1 )
, if( and( x<=upb(blinker_x_range), y<=upb(blinker_y_range), blinker[ x, y ] = "n" ), 1, 0 )
, if( and( x<=upb(glider_x_range), y<=upb(glider_y_range), glider[ x, y ] = "n" ), 1, 0 )
, next_board[ x, y ]
There are several things about this code. One is Excel's "choose" function. This is a multi-way switch. Its first argument must be an integer. If this is 1, "choose" returns its second argument. If it's 2, it returns the third argument. And so on. In the code above, its first argument is "index_of_selected_menu_option", which as I'll explain later, is the position of the selected option in the set of options: 1 for "Start", 2 for "Blinker", and so on. Because I've written "choose"'s arguments in the same order as these, it returns the value of the subexpression corresponding to the selected option. Take care here: you must keep its arguments in this order, i.e. the same order as the options in table menu_options.
Incidentally, in my first version of this program, I used nested "if"s instead of "choose". However, this started giving me Excel formula errors, probably caused by a limit on the number of nested "if"s, as Chip Pearson explains in his page on Nested Functions. So I turned to "choose", even though this need to keep its arguments in the same order as the menu options makes bugs more likely.
Two other things are worth remarking. First, "len(trim(...))". These are both Excel functions. The "trim" function removes all spaces from text except for single spaces between words. And "len" returns the length of a string. So if C is a cell in the start board, "len(trim(C))" returns 0 if it contains only spaces or is empty. This lets us treat any cell that looks blank as empty, enabling the user to type any non-blank character for an occupied cell.
Second, expressions such as "upb(blinker_x_range)". The "upb" looks like an Excel function, but isn't: it's a functionette that Excelsior evaluates when generating formulae. It expects a type name as argument, and returns the upper bound of the type. This lets us write stuff that depends on these upper bounds, without having to wire them into the code as numbers. It's an alternative to the use of explicit constants such as board_width.
Now I'll deal with the menu options. The menu itself is in the following table:
table selected_menu_option : -> text.Because the table has only one cell, we needn't worry about x or y coordinates. So in contrast with the tables "board" and "display_board", I've not written anything before the arrow. This again follows the mathematician's notation for describing functions, this time ones with no arguments.
I shall initialise the menu to the "Start" option:
selected_menu_option = "Start".I'll explain under Layout how we make Excelsior actually put a menu in this cell.
In the equation for "board", I explained that the first argument of "choose" is the position of the selected menu option in the list of options. I hold this in another single-cell table, "index_of_selected_menu_option":
table index_of_selected_menu_option : -> general.
I shall calculate it using Excel's "match" function, with a zero third argument to say the match must be exact:
index_of_selected_menu_option =This just does what I've indicated, namely returns the position of the first argument (a string) in the cell range given as the second argument. Here, that second argument is "menu_options[all]". Excelsior translates this into the cell range occupied by all cells of menu_options.
match( selected_menu_option, menu_options[all], 0 ).
And here is that table:
type menu_options_base = 1:5.
table menu_options : menu_options_base -> text.
menu_options = "Start".
menu_options = "Blinker".
menu_options = "Glider".
menu_options = "Run".
menu_options = "Clear".
Note that these options get used in two places. One is the match function call above. The other is in the menu. Making the same table do for both eliminates one possible out-of-step error.
Let's now turn our attention back to the board. The table "start_board" is where the user types a starting pattern. I shall make it range over the same coordinates as the board, although it need not be as large:
table start_board : board_x_range board_y_range -> text.
And I shall initialise it so its cells look empty:
start_board[ x, y ] = " ".
This is the table where I calculate the next generation: next_board[x,y] is 1 if the next generation of the cell at (x,y) will be occupied, and 0 if it will be empty. The table must range over the same coordinates as the board:
table next_board : board_x_range board_y_range -> general.
It is here that we apply the rules of Life:
next_board[ x, y ] =
if( and( board[ x, y ] = 1, neighbour_count[ x, y ] < 2 )
, if( and( board[ x, y ] = 1, neighbour_count[ x, y ] > 3 )
, if( board[ x, y ] = 1
, if( and( board[ x, y ] = 0, neighbour_count[ x, y ] = 3 )
The above equation depends on neighbour_count, which I shall now define. It holds the number of each cell's live neighbours: neighbour_count[x,y] is the number of live cells bordering the cell at (x,y). It must range over the same coordinates as the board:
table neighbour_count : board_x_range board_y_range -> general.
The code below calculates the number of live neighbours by summing the contents of the neighbouring cells:
neighbour_count[ x, y ] =
if( and( x>1 , y>1 ) , offset( board[x,y], -1, -1 ), 0 ) +
if( x>1 , offset( board[x,y], 0, -1 ), 0 ) +
if( and( x>1 , y<board_height ), offset( board[x,y], 1, -1 ), 0 ) +
if( y>1 , offset( board[x,y], -1, 0 ), 0 ) +
if( y<board_height , offset( board[x,y], 1, 0 ), 0 ) +
if( and( x<board_width , y>1 ) , offset( board[x,y], -1, 1 ), 0 ) +
if( x<board_width , offset( board[x,y], 0, 1 ), 0 ) +
if( and( x<board_width , y<board_height ), offset( board[x,y], 1, 1 ), 0 ).
The code may look a bit tricky. This is because of an irritating problem common to this kind of simulation: what to do at the board's edges? I could have coded this so that the board wraps round, making the bottom edge wrap back to the top, and the lefthand edge wrap round to the right. And vice-versa. But instead, I've kept things simple by defining all off-board neighbours of the edge and corner cells to be always unoccupied.
However, there is another problem due to the number of special cases needed. To see why, suppose I had written:
neighbour_count[ x, y ] =What would happen for the top-left cell? Its (x,y) coordinates are (1,1), so the right-hand side will become board[0,0]+board[0,1] plus the other cells. In terms of the table "board", this is meaningless, being outside its bounds. If we think of "board" as a function, as I suggested when discussing "display_board", this is as senseless as asking for, say, the logarithm of 0, when log isn't defined for 0.
board[ x-1, y-1 ] +
board[ x-1, y ] +
... other cells ...
If we think how "board" is implemented, as a two-dimensional area on a worksheet, it is equally meaningless, because it refers to a cell outside the board. That could be anything: a label; a menu; even off the worksheet. Any formula generated would be rubbish.
One way round this would be to write special cases. But we'd need a lot, because there'd have to be one for each corner, and one for the rest of each edge. So I have sidestepped such proliferation by using Excel's "offset" function. Its first argument is a cell reference, its second argument a row offset, and its third argument a column offset. It returns the contents of the cell at these offsets. For example, offset(B1,2,3) returns the contents of the cell 2 rows down and 3 columns along from A1, namely C4.
To see why this works, consider how Excelsior would translate this equation for the case where x and y are 1:
neighbour_count[ x, y ] =Suppose that the board's left-hand corner is B1. The right-hand side of the equation would become:
if( and( x>1, y>1 ), offset( board[x,y], -1, 0 ), 0 ).
if( and( x>1, y>1 ), offset( B1, -1, -1 ), 0 )which Excelsior will put into cell B1.
Now suppose instead that the equation were:
neighbour_count[ x, y ] =Now, the formula Excelsior puts into B1 will be:
if( and( x>1, y>1 ), board[x,y-1] ).
if( and( x>1, y>1 ), B0, 0 )But there is no row 0, and so the formula is meaningless, in the same way as the one for board[x-1,y-1]+board[x-1,y] I showed earlier. Using "offset" avoids the problem, because "offset" doesn't generate an explicit cell reference, but calculates it while Excel is running.
I've now explained how the board is updated, and how this depends on the selected menu option. If this names one of the predefined patterns, that gets copied into the board, so let's look at them. To save paper in this small version of the program, I shall have only two. The first is a blinker, standing up:
type blinker_x_range = 1:2.
type blinker_y_range = 1:4.
table blinker : blinker_x_range blinker_y_range -> text.
blinker[2,2] = "n".
blinker[2,3] = "n".
blinker[2,4] = "n".
The second predefined pattern is a glider, oriented to move diagonally down and to the right. It is defined in the same way as the blinker, but its table is called "glider", and its dimensions are glider_x_range and glider_y_range. To save space, I'll omit the code.
That completes the calculations and tables. It's now time to arrange the tables on their worksheets. The idea here is that Excelsior uses "layout" statements to define a super-grid, each super-cell of which is a table, a heading or other label, or blanks. Sometimes, a super-cell will be one Excel cell, but more often, it will be several. All super-cells in a super-row have the same depth, and all super-cells in a super-column have the same width. Excelsior ensures this by padding below and on the right with blank cells.
Let's see this at work with my first layout statement, for the "board" table:
layout( '1.Board', rows( heading, row( board ) ) ).
Its super-grid has two super-rows and one super-column. The first super-row contains a heading — as indicated by the word "heading". Excelsior will replace this by a row of labels. Each label will name the table directly below it, and is generated from the table's name by replacing underlines in the name by spaces. So if you name your tables with meaningful words or phrases, using underlines to join words, the headings above will be useful and automatic reminders of a sheet's contents.
The second super-row in the above layout statement holds the "board" table. Because this is more than one cell wide, Excelsior will right-pad the heading above it with board_width-1 blank cells.
Note that this layout statement, like all of them, describes one sheet. The sheet name is the first argument to "layout", "1.Board". I explained why I was giving it this funny name in my section on Iterative calculations in Excel.
The next two layout statements follow the same principle:
layout( '2.Neighbour count', rows( heading, row( neighbour_count ) ) ).
layout( 'Next board', rows( heading, row( next_board ) ) ).
Now, on the Menu sheet, we lay out the menu options and the working table that holds the index of the selected option. This sheet has one super-column and four super-rows:
, rows( heading
, row( menu_options )
, row( index_of_selected_menu_option )
The next table holds the predefined blinker. It introduces a new concept, which I am using to associate the blinker with the Wingdings font. This is the "as" functionette:
, rows( heading
, row( as( blinker, xy, , life_text ) )
Notice that the fourth argument of "as" is "life_text". This, Excelsior uses to style the blinker table's cells, putting them into Wingdings. Here's how.
Excel has a notion of "template file". Template files are spreadsheets, but have the extension .xlt rather than .xls. The point of a template is that you use it as a style library. If you define new styles in it, there are ways of creating a new spreadsheet and copying these styles into it. The spreadsheet will then remember them, so that you can use their names when styling its cells.
Exelsior makes use of this to provide
control over formatting. I supply a predefined
template, template.xlt , in which I've
defined styles with the same names as the
result types I allow for tables, shown below:
When you run Excelsior from the command line, you must give it the name of a template, using the -t option. You can use the supplied template.xlt , or a different file. For example:
excelsior -t c:\life\life_template.xlt smalllife.excHere, the template is c:\life\life_template.xlt . And here's what it looks like :
So now look again at my layout statement for the "blinker" table:
layout( 'Blinker'The "life_text" in the "as" tells Excelsior that it must style "blinker"'s cells with the "life_text" style. It will take this style from the .xlt file given as the -t command-line option. Which styles it as Wingdings. Incidentally, I learnt about Wingdings from David Ellerman's Life spreadsheet, linked from his page Math on Spreadsheets. Which I do recommend.
, rows( heading
, row( as( blinker, xy, , life_text ) )
I ought to explain the other arguments to "as". The first, clearly, is a table. The second states its orientation: how it maps onto a worksheet. My default, for two-dimensional tables, is to arrange the first dimension pointing across (the x direction), and the second dimension pointing down (the y direction). When you use "as", you have to be explicit about this, by writing "xy". You could also write "yx", which would swap the axes. One-dimensional tables are arranged either as "x" or "y".
The third argument to "as" is either  or a table of menu options, and is used to make dropdown menus. We'll see this shortly.
I've finished explaining how the blinker is laid out. The next sheet, for the glider, works the same way, so I'll miss that out. And that leaves the final sheet, Display:
, rows( heading
, row( skip, as( start_board, xy, , life_text ) )
, row( skip )
, row( as( selected_menu_option, null, menu_options ) )
, row( skip )
, row( skip, as( display_board, xy, , life_text ) )
This is the most complicated sheet, having a super-grid of two super-columns and eight super-rows. The second super-row holds the start board. Its first super-cell is blank, which is what the "skip" means. That's to push the board one cell to the right. The fourth super-row holds the menu, selected_menu_option. Its "as" has menu_options as its third argument. This creates a dropdown menu with the contents of menu_options as its options. The second argument of the "as" is "null", which is the default way of arranging zero-dimensional tables on a worksheet. (There are not many.) And the eighth super-row holds the display board. Like the start board, it's pushed one cell to the right, and styled in Wingdings.
I hope everything above gives you enough information to modify the program, if you want to experiment with changing the Life rules. So now, let me tell you how to generate a spreadsheet from it.
In the Excelsior download here, are two text files smalllife.exc and biglife.exc . The first is the version of Life I ran through just now, with two predefined patterns and a small board. The second has all the patterns and a much bigger board, and is what I generated the Life spreadsheet from. If you try any changes, I suggest you do so on the small file first, because it generates more quickly and the big spreadsheet is a bit unwieldy.
The download also contains life_template.xlt , which I talked about under Layout.
To install, download Excelsior and unzip it into a clean directory. Hereon, I'll assume you've named this c:\life\ . The zip file contains several subdirectories: make sure your unzip command preserves their structure, and doesn't flatten them into the top-level directory.
You must now set three environment variables. In case you don't know how, this is what I'd do on XP. I click on Start, then on Control Panel halfway down the righthand column in the resulting pop-up. This opens a window with icons labelled "Accessibility Options", "Add Hardware", and so on: I am viewing it in what Microsoft call Classic View, rather than Category View. I double-click on the System icon, then on the Advanced tab in the window this opens, and then on the Environment Variables button near the bottom. This makes another pop-up, with two fields headed "User Variables" and "System variables". I click the "New" button below the "System variables" field, and a pop-up appears with a "Variable name" and a "Variable value" field. Then I type (e.g.) EXCEL_HOME into the "Variable name" field, and (e.g.) c:\Program Files\Microsoft Office\Office11 for "Variable value". I then click "OK", and then either add another variable, or click "OK" on the pop-up below. And that's it.
So now, set the first environment variable EXCEL_HOME to the directory your Excel is in. On my laptop, that's c:\Program Files\Microsoft Office\Office11 . Every time it successfully compiles a program, Excelsior runs excel.exe from this directory, with "interface.xls" as a command-line argument. This activates a VBA routine in interface.xls (which I also supply), which will copy an intermediate file of generated formulae into your new spreadsheet.
Second, set EXCELSIOR_HOME to the directory you unzipped into, which I've assumed is c:\life\ . Excelsior looks in here to find files such as interface.xls .
Third, set EXCELSIOR_TEMP to a scratch directory where files such as the intermediate file of generated formulae can safely be created and deleted. I use C:\WINDOWS\TEMP .
Now, open a new MS-DOS window, and change directory to c:\life\ or your equivalent. Then type the command
excelsiorYou should get a summary of Excelsior's command-line syntax. If it doesn't work, perhaps the unzip has failed to copy some of the files, possibly DLLs that Excelsior uses.
But if it does work, you are now ready to compile Life! To compile the small one, type this, but with your directory instead of c:\life\ :
excelsior -t c:\life\life_template.xlt smalllife.exc
If compilation is OK, the new Life spreadsheet will appear in front of you. If it doesn't, one of your environment variables may be wrong.
Before you can run the new Life spreadsheet, you will need to switch it into iterative mode, as I explained under Iterative calculations in Excel. Otherwise, Excel will keep reporting "circular reference" errors.
Now try the same with biglife.exc . Be warned that this will take longer, because more cells need to be set up.
To make your new spreadsheet more congenial to read, you may want to alter the zoom setting as I described under Running the Life spreadsheet, and to resize rows and columns in the grids on the "Display" sheet. The resizing is best done visually, in Excel. Excel's HELP for "Change column width and row height" explains how. Under the subheading "Of multiple columns", it says:
Select the columns you want to change, and then drag a boundary to the right of a selected column heading.Similarly for rows:
Select the rows you want to change, and drag a boundary below a selected row heading.
You can now experiment with altering the rules of Life. There's a summary of the Excelsior language at the start of my user guide. The things you're most likely to want to change are the right-hand sides of the equations, particularly that for next_board. The formula here is exactly like an Excel formula — it uses "if" in the same way, and so on — except that instead of cell references, there are table elements. (I've written the functions in lower-case, because it's easier to read, but that's inconsequential.) So if you change the numbers against which the neighbour counts are compared, for example, it will have exactly the same effect as in Excel.
If you're feeling ambitious, you could also try running try_rabbits.bat . This batch file is in the Excelsior distribution, so will appear when you unzip it. It contains a command similar to:
excelsior -l rabbits\ -t c:\kb7\mm7\template.xlt rabbits\rabbits.exc rabbits\foxes.exc rabbits\time.exc rabbits\layout.excEdit this to change the c:\kb7\mm7\ to your equivalent of c:\life\ . Running the command will preprocess all the .lexc files in the rabbits subdirectory to .exc files, generating the documentation that I showed under Literate Spreadsheet Programming and linked from here. It will also create .exc files and generate a spreadsheet from them. That looks like this, and is one that I reverse-engineered from an original at Norman Herr's Spreadsheets for teaching science:
Now do the same, but with
try_spin.bat . This
spin.lexc in the "spin"
I blogged in
Falls Toward The Sun And Everybody Dies.
Compilation should make
a spreadsheet spring up with a story like this:
To generate a new story, select the single menu option in cell B4. Some stories are gloomy; some are hopeful:
Planet 9 of Alpha-CentauriAnd some are ambiguous:
falls toward the Sun
and is visited by evil
are converted by the village priest (who tells them of God) to
rewind time to before the disaster
and give the secret of
free fusion power
so all live happily ever after.
is struck by a comet
and is visited by evil
steal its reserves of
are stopped by a logician
who says 'I am lying'
and so he must be telling a falsehood
so he must be telling the truth
and so he must be telling a falsehood
so he must be telling the truth
(STACK OVERFLOW DURING RECURSION.)
An interesting point, should you be teaching computing, is that this spreadsheet actually does use recursion, but oddly. I said above that display_board and other tables can be regarded as functions. This is true of any table, including those in the science-fiction generator. It stores possible plot events as nodes in a network, and generates a plot by recursively finding a path through this network. Using recursion to traverse networks is no novelty. But what is, is that here, regarding tables as functions, we call a table from itself. There is recursion, but it is laid out — spread out, one might say — not in time but in space.
The famous printed reference is Scientific American's Mathematical Games for October 1970 (Volume 223), by Martin Gardner. He wrote a follow-up article, Mathematical Games for February 1971 (Volume 224), and probably has follow-ups to that.
en.wikipedia.org/wiki/Conway%27s_Game_of_Life — Conway's Game of Life, Wikipedia.
en.wikipedia.org/wiki/John_Horton_Conway — John Horton Conway, Wikipedia.
en.wikipedia.org/wiki/Cellular_automata — Cellular automaton, Wikipedia.
www.fourmilab.ch/cellab/manual/chap5.html — Origins of CelLab, CellLab User Manual Chapter 5, by Rudy Rucker and John Walker. A brief history of cellular automata, from Stanislaw Ulam and John von Neumann onward, and including Conway.
www.math.com/students/wonders/life/life.html — What is the Game of Life?, Paul Callahan's World of Math Online page. Contains the buttons that run Alan Hensel's Life applet.
www.ibiblio.org/lifepatterns/ — Conway's Game of Life. Alan Hensel's applet page.
www.chaos.org.uk/~eddy/craft/weblife.html — Another Life simulator, by Eddy Welbourne
www.j-paine.org/life.xls — My Life spreadsheet.
www.ellerman.org/Davids-Stuff/Maths/Math-on-SS/MathonS.htm — Math on Spreadsheets, by David Ellerman. Links to the iterative Life spreadsheet I learnt about Wingdings from.
radicaleye.com/lifepage/lifepage.html — Patterns, Programs, and Links for Conway's Game of Life, by Paul Callahan, 2001. Lots of Life links: pattern dictionaries, people trying to build exotic oscillators, delay-line memories, all kinds of Life "engineering".
radicaleye.com/lifepage/enoexcerpt.html — Conway's Life and generative music, by Paul Callahan. Includes part of a talk featuring Life and generative music by Brian Eno.
www.inmotionmagazine.com/eno1.html — Generative Music: "Evolving metaphors, in my opinion, is what artists do", the talk by Brian Eno, 1996.
www.bitstorm.org/gameoflife/lexicon/ — Dictionary of Life patterns by Stephen A. Silver, modified by Edwin Martin so that they can be loaded into a Life program linked from the top of the page.
www.radicaleye.com/lifepage/picgloss/picgloss.html — A Brief Illustrated Glossary of Terms in Conway's Game of Life. Glossary and dictionary of patterns, by Alan Hensel, with help from Achim Flammenkamp, John Conway, Dean Hickerson, David Bell, Bill Gosper, Bob Wainwright, Noam Elkies, Nathan Thompson, Harold McIntosh, and Dan Hoey. The patterns link to dot-and-star text files, which should be easy to convert into input for most Life programs.
www.ericweisstein.com/encyclopedias/life/ — Eric Weisstein's Treasure Trove of Life. Includes a glossary and dictionary of patterns.
www.ericweisstein.com/encyclopedias/life/Hassler.html — Hassler, from Eric Weisstein's Treasure Trove of Life.
radicaleye.com/lifepage/patterns/p1/p1.html — The Oscillator Problem, by Paul Callahan. The engineering challenges of designing a period-k oscillator for any positive integer k.
pentadecathlon.com/lifeNews/2007/12/new_180degree_glider_reflector.html — Game of Life News, 17 December 2007, site by H. Koenig and Dave Greene. Reports on a new 180-degree glider reflector, period 4 and up.
surf.de.uu.net/people/joke/rsc/ships_toc.html — Spaceships in Conway's Game of Life: Of Blinkers, Jellyfish, and Everything.... Edition 1.2, (Part 1-6b, Addendum 1), October 1993, by David I. Bell. Reports recent (then) results on spaceships.
rendell-attic.org/gol/tm.htm — A Turing Machine in Life, by Paul Rendell.
en.wikipedia.org/wiki/Turing_machine — Turing Machine, Wikipedia.
gregegan.customer.netspace.net.au/ — Greg Egan's home page.
www.cscs.umich.edu/~crshalizi/reviews/permutation-city/ — Review of Egan's Permutation City, by Cosma Shalizi.
blogs.msdn.com/excel/archive/2007/11/02/iteration-conway-s-game-of-life.aspx — Iteration & Conway’s Game of Life, by Chris Rae, 2 November 2007. How to implement Life using iterative calculations in Excel.
abajournal.com/news/excel_error_by_a_cleary_gottlieb_associate_alters_lehman_asset_deal1 — Excel Error by a Cleary Gottlieb Associate Alters Lehman Asset Deal, by Debra Cassens Weiss, American Bar Association, 16 October 2008.
www.eusprig.org/hdykysir.pdf — How do you know your spreadsheet is right? Principles, Techniques and Practice of Spreadsheet Style, by Phil Bewig, 2005.
www.cpearson.com/excel/nested.htm — Excel limits on nesting "if" and other functions, by Chris Pearson.
www.csun.edu/science/ref/spreadsheets/ — Spreadsheets for teaching science, collected by Norman Herr.
www.csun.edu/science/ref/spreadsheets/xls/predator_prey.xls — The predator-prey spreadsheet from this site.
www.j-paine.org/excelsior/repository/rabbits/index.html — My reconstruction of this, including "Literate Programming" documentation generated from it.
www.j-paine.org/eusprig2008/index.html — Less Excel, More Components, by Jocelyn Ireson-Paine, 2008. A presentation that, in the section How do spreadsheet components work?, demonstrates the kind of reverse-engineering I used to create the above.
www-cs-faculty.stanford.edu/~knuth/ — Donald Knuth's home page.
www.literateprogramming.com/ — literateprogramming.com's site. Contains the quote I cited by Knuth.
en.wikipedia.org/wiki/Wingdings — Wingdings, Wikipedia.
dobbscodetalk.com/index.php?option=com_myblog&show=Have-we-forgotten-whats-wrong-with-goto-statements-.html&Itemid=29 — Have we forgotten what's wrong with 'goto' statements?, by Andrew Koenig, 23 February 2009. Comments include the "too many thumbs" reply by Bradford Miller.
www.spreadsheet-parts.org/excelsior.html — Excelsior download page, by Jocelyn Ireson-Paine.
www.spreadsheet-parts.org/excelsior_guide.html — Excelsior user guide, by Jocelyn Ireson-Paine.