An Alien Message?

This just may be the ultimate 'tweetable program' that does something interesting. I first saw this kind of conciseness in a pamphlet sized book back in the seventies that highlighted the efficiency of the language used, APL (A Programming Language). The author had taken the winning code from a programming contest, where conciseness and correctness were highly scored, and adapted it to APL. One line to do the classic brain teaser puzzle Instant Insanity.

If I recall correctly, the original code was either in C (fairly new at the time) or BASIC (some pretty powerful versions existed even then), and the winning code was something like eighty lines of actual code (not counting the required comments for the contest.)

The particular piece of code heading this entry produces the generations of the board for Conway's Game of Life.

The game is 'played' algorithmically, by applying simple rules to an initial matrix of 'creatures' set up to the player's desired configuration:

•  Any live cell with fewer than two live neighbours dies, as if caused by underpopulation.
• Any live cell with more than three live neighbours dies, as if by overcrowding.
• Any live cell with two or three live neighbours lives on to the next generation.
• Any dead cell with exactly three live neighbours becomes a live cell.

The complexity of the patterns that result, and the 'behaviors' that appear can be mind boggling. One pattern might result in every cell quickly dying. Another could result in fantastic evolutions of patterns and shapes. Some patterns produce 'gliders' that crawl their way across the matrix. Some even birth copies of themselves (none have been seen yet, but the proof of such patterns in the game is available in Winning Ways for your Mathematical Plays by Berlekamp, Conway and Guy).

The list of possible patterns is endless, as are the results they generate, and aficionados of the game actually host contests where players supply initial patterns that 'fight' each other until a winner is decided.

An example of a pattern known as a 'gun', that produces 'gliders' is seen in the animation below:



You can view other more complex patterns, including some that do useful work, at the video link at the end of this article.

The game is perhaps the first widely known example of a cellular automaton, and exhibits Turing completeness, that is, the game is sufficient to simulate the Universal Turing machine. This means a sufficiently complex initial game board, given a sufficient time span, can perform the same 'program' as a computer with infinite memory and no time constraints. If that doesn't startle you, it's time to fill up your coffee mug!

All of this complexity captured in one line of APL code.

Take a moment to absorb these two morsels you've been handed. In one line of APL, we have the Game of Life. In the Game of Life, we have a Universal Turing Machine. That one line of APL could conceptually (given no constraints on memory or time) run any program you could possibly write, or even imagine. Any program that could ever be written. What an amazingly concise language!

I quickly fell in love with APL, particularly because of my mathematical bent, which the language is ideally suited for. I suffered many a time from the denseness of the language though. A running joke of the time was that the language was 'write once, read never', capturing the difficulties that the author of particularly terse APL might have deciphering their own code when returning to it after some time.

The language uses a family of special characters to represent various monadic (taking the result of everything to the right of the symbol as the argument) and dyadic (accepting an additional argument, the first data to the left of the symbol) functions. It is in fact based on a mathematical notation developed by Kenneth Iverson for array manipulation that he used with his students at Harvard University.

In some cases, functions are represented by overstrikes, that is, literally typing a symbol and then typing another symbol over the original. The use of this depended on the system involved, and in general the same functionality could be accomplished without needing overstrikes. There are also versions of APL that provide special character input using combinations of standard characters via input method editors to represent the symbols.

The concise use of functions applied using the language's simple recursive precedence rules (the right argument of a function is the result of the entire expression set to the function's right) and the incredibly high level of abstraction possible makes for ridiculously rapid, interactive and iterative solutions to even the most fiendishly complex problems.

Functional programming before functional programming was cool.

Soon after I learned the language, this beauty came along:

Oh Man! This was a computer lover's dream machine. Arguably the first 'portable' computer (at over 53 pounds wet), the IBM 5100 represented a giant leap in movable computing power.

Fully equipped with a whopping 64KB of memory and tape drive, with BASIC and APL programming languages (selected by flipping a toggle switch on the front panel), and a giant 5" CRT  display of 16 lines of 64 characters each, it cost about $20,000.00 in the mid seventies. That's roughly $80,000.00 in today's dollars.

A sophisticated digital wristwatch likely has more processing power today, and certainly most smart phones would leave the 5100 in their dust. I still lust after one!

I found one some time ago that had been uncovered in a garage. Perfect condition. With all the trimmings, including the rare external tape unit and printer. The last example I'd seen sold for somewhere north of $15,000.00, and it was in only fair shape, with only BASIC on no peripherals. I called the seller, and he indeed still had the unit. The price? Under $2,000.00. He'd had no calls (no surprise to me: the ad he placed was in a place no one would possibly look for one of these.)

I didn't have the heart. Or the lack of one, I suppose. I pondered it for a day, then called the seller and filled them in on the rising collectible value of these units. My feeling was his unit, as perfect as it was, belonged in a museum. I'm sure he thought I was nuts for spilling the beans. I felt good about it. After weeping...

Enough already with the trip down memory lane! Back to the subject at hand: APL. Functional programming in the seventies. Preceded only by Lisp.

The more things change, the more they stay the same!

You can watch an expert APL user building the game of life from scratch in the video below. Fascinating and frankly still jaw dropping to me after all this time.




In addition, an interesting five minute video that shows many different initial starting patterns and their results including one where prime numbers are part of the resulting behavior can be seen at Amazing Game of Life Demo on YouTube.

If you want to experiment with the game and try your own patterns, the open source, cross platform implementation of the game in Golly is superb. Golly also provides a large library of already built patterns ranging from simple to complex, amusing to beautiful, and useless to startlingly capable.