A Metalanguage for Pathological Programming: Cellular Automata in Alpaca

Todays entry isn't so much a pathological language itself as it is a delightful toy which can be used to *produce* pathological languages. I'm looking at Chris Pressey's wonderful language [ALPACA](http://catseye.mine.nu:8080/projects/alpaca/), which is a meta-language for describing different kinds of cellular automata.

Frankly, I'm very jealous of Alpaca. I started writing a cellular automata language something like this on my own; I spent about two weeks of my free time working on it, and got it roughly 90% finished before I found out that he'd already done it, the bastard!

Alpaca definitely qualifies as a real language, in that it is capable of generating turing complete automatons. We can show this in two different ways. First, Conway's life is a trivial program in Alpaca, and you can build a turing machine simulator using life. And second, Alpaca includes an implementation of a Brainfuck clone as a cellular automaton.

Alpaca's a very simple language, but it lets you define pretty much any cellular automaton that works in a two-dimensional rectangular grid. And it comes with some very fun, and some very pathological examples.

In case you're non familiar with cellular automatons, here's a very quick explanation.

In a cellular automaton, you've got a grid made up of something almost like a collection of identical finite state machines, which are called a *cell*. A cell can be in any one of some finite list of *states*. Each time you step time forwards, the cell gets to modify its state by looking at its own current state, and the states of its immediate neighbors. The entire grid steps simultaneously.

It's a very simple idea, but a remarkably powerful. Some incredibly complicated and fascinating behaviors can be produced by simple cellular automata. Alpaca lets you define pretty much any two-dimensional rectangular grid based cellular automaton.

For example, the most famous cellular automaton is Conway's "Game of Life". In life, each cell can have one of two states: live, or dead. Each step, if a cell is dead and it has three neighbors that are alive, it switches to alive, otherwise it stays dead. If it's alive, and it has 4 or more life neighbors, it dies (overcrowding); if it has less that two neighbors, it dies (loneliness), and if it has three or four neighbors, it stays alive. That's it - that's enough to [simulate a turing machine!](http://www.cs.ualberta.ca/~bulitko/F02/papers/tm_words.pdf)

Life is trivial in Alpaca:

state Dead " " to Alive when 3 Alive and 5 Dead;
state Alive "*" to Dead when 4 Alive or 7 Dead.

You nawe the states, and the rules by which they'll change states. The thing in quotes is
the character that will be used in input files to represent a cell in that state.

Here's an example of a very simple input file for the life automaton: it's called a *glider*.

   *
 * *
  **

If you run the glider, what you'll get is basically that figure moving diagonally across the grid. Here's a few steps:

Or much cooler, here's a pattern called the turbine:

    ****** **                                                           
    ****** **
           **                                                           
    **     **                                                           
    **     **                                                           
    **     **                                                           
    **                                                                  
    ** ******                                                           
    ** ******                                                           

If you run the turbine in life, it will go though a cycle of eight steps over and over again:

Another wonderful example of what you can do in Alpaca is wireworld. Wirewold is an amazing automaton which simulates digital circuits. I wrote a bit about wireworld back on the [old GM/BM](http://goodmath.blogspot.com/2006/04/wireworld.html).

In wireworld, you have wires and sparks. Sparks are divided into two parts: the leading edge of a spark, and the trailing edge of a spark. So you end up with four states: empty, wire, spark, and tail. The rules for wireworld are:

1. If you're the leading edge of a spark, next step, you turn to tail.
2. If you're wire, and *one or two* of your neighbors is the leading edge of a spark, you turn into the leading edge of a spark.
3. If you're the trailing edge of a spark, next step, you turn to wire.
4. Otherwise, just stay the way you are.

Written in Alpaca, wireworld is:

state Empty " ";
state Spark "#" to Tail;
state Tail "-" to Wire;
state Wire "=" to Spark when 1 Spark and not 3 Spark.

And here's an example of wireworld running, with empty cells as black, wire as gold, leading edge of a spark as green, and tail of a spark as red:

Now, it's time to get *seriously* pathological. To demonstrate that this is turing complete, Chris implemented a bit-oriented brainfuck variant called Braktif as a cellular automaton. Here's the alpaca program for it, documentation included:

/*
* The Braktif Cellular Automaton
* June 2005, Chris Pressey
*
* Braktif is an esoteric programming language very similar to
* 'Brainfuck F' and 'Archway', with a small but significant
* difference: Braktif is formulated as a 28-state cellular automaton.
*
* Braktif playfields are divided into a program on the right and
* a data storage area on the left. (The data storage area can be
* considered to extend indefinately to the left.) The program
* and data area are connected by a 'bus'. On the bus sit the
* instruction pointer, which rests underneath the part of the
* program which is currently executing, and the data pointer, which
* rests underneath the part of the storage which is currently being
* addressed. The instruction pointer and data pointer communicate
* by means of signals (from the IP to the DP) and replies (from the
* DP to the IP) sent along the bus.
*
* The instructions of a Braktif program resemble those of Smallfuck
* or Brainfuck F:
*
* * flip current data bit
* > advance DP one cell to the right
* < advance DP one cell to the left
* [ if current data bit == 0, skip to matching ]
* ] skip back to matching [
*
* The structure of Braktif programs resembles that of Archway. Each
* nested loop must be raised up one level. In addition, extra space
* must be left after [ instructions, and at least one non-[]
* instruction must occur after a ] instruction, so that signals have
* sufficient space in which to propagate.
*
* The data storage area of a Braktif playfield resembles the tape of
* a Brainfuck F program (or a Smallfuck program, if an arbitrary limit
* is imposed on it) except that it is bounded on the *right*, not the
* left.
*
* The final result of all this is that the following Brainfuck F
* program translates to the following Braktif program (the '...'
* indicates the quiescent repeating pattern extending off to infinity):
*
* Brainfuck F: +[>+]
*
* Braktif:
* <*
* ... 00000000000000 *[---]
* ... -------------d-i- --
*
* So... why Braktif?
*
* - eliminates 'spooky action at a distance' from the Brainfuck model:
* the communication between the code and the tape is made explicit
* (and explicitly planar, FWIW WRT the wire-crossing problem.)
* - horribly inefficient because of this. Flipping the n'th data cell
* from the m'th instruction of the program is now an O(n+m) operation.
* What fun!
* - makes a passable "poor man's visual debugger" for Brainfuck F.
* - makes experimenting with concurrent models easily. For example it
* might be feasible to add a few states what would act as a simple
* mutex so that two different programs could share one data store.
*
* Finally, I do not claim that this is the most efficient formulation
* imaginable... there is certainly room for optimization. For
* example, half of the 'Tool' states could probably be done away with
* entirely if the signals were to transition themselves directly into
* responses. But a minimum of states is not the real goal (otherwise
* one could just settle for John Conway's Game of Life and be done
* with it,) and the 'Tool' states lend a certain straightforwardness.
*/

/* -------------------- Transmission Media --------------------- */
state Space" "
to SkipBack when (^ WakeMark and ^> WendCmd) or (> SkipBack),
to SkipStart when ^< SkipReply and ^ InstrMark,
to SkipFore when v< SkipStart or < SkipFore;

state Bus"-"
to > when > is Signal,
to ^> when ^> is Signal,
to v> when v> is Signal,
to < when < is Reply,
to ^< when ^< is Reply,
to v< when v< is Reply,
to ContTool when > LeftTool or < RightTool,
to ContReply when < ContTool,
to SkipReply when < SkipTool,
to LeftSig when > InstrPtr and ^> LeftCmd,
to RightSig when > InstrPtr and ^> RightCmd,
to FlipSig when > InstrPtr and ^> FlipCmd,
to QuerySig when > InstrPtr and ^> WhileCmd,
to InstrPtr when < WakeMark or v< WakeMark or ^< Wakemark,
to InstrPtr when < InstrPtr and ^< Space,
to InstrPtr when > SkipBack,
to SkipStop when < SkipFore,
to InstrPtr when < SkipStop;

/* -------------------- Signals and Replies -------------------- */
class Signal
to Bus;

class Reply
to Bus;

state LeftSig"L" is Signal;
state RightSig"R" is Signal;
state FlipSig"F" is Signal;
state QuerySig"Q" is Signal;

state ContReply"C" is Reply;
state SkipReply"S" is Reply;

/* ------------------- Data Store: Data Pointer ---------------- */
state DataPtr"d"
to FlipTool when > FlipSig,
to LeftTool when > LeftSig,
to RightTool when > RightSig,
to SkipTool when > QuerySig and ^ OffBit,
to ContTool when > QuerySig and ^ OnBit;

state FlipTool"f"
to ContTool;
state LeftTool"l"
to Bus;
state RightTool"r"
to Bus;
state ContTool "c"
to DataPtr;
state SkipTool"s"
to DataPtr;

/* ----------------- Data Store: Tape Contents ----------------- */
state OnBit"1"
to OffBit when v FlipTool;
state OffBit"0"
to OnBit when v FlipTool;

/* ----------------- Program: Instruction Pointer -------------- */
state InstrPtr"i"
to Bus when ^ Space,
to InstrMark;

state InstrMark"I"
to WakeMark when < ContReply,
to Bus when < SkipReply;

state WakeMark"W"
to Bus;

/* ----------------- Program: Instruction Skipper -------------- */

state SkipStart"!"
to Space;
state SkipStop"%"
to Bus;
state SkipFore"}"
to Space;
state SkipBack"{"
to Space;

/* -------------------- Program: Instructions ------------------- */
state FlipCmd"*";
state LeftCmd"<";
state RightCmd">";
state WhileCmd"[";
state WendCmd"]".

I don't know how to capture the execution of a braktif program for you to watch; I tried using a screen recorder, but it doesn't interact well with the terminal where I can run the Alpaca Braktif interpreter. I definitely recommend downloading it and running the braktif example programs: it's *fascinating* to watch. There's a data bus connecting the program to the data tape, and as the program runs, you can watch data operations flow across the bus to move the data pointer and alter data on the tape. Fascinating, brilliant, and quite definitely, pathological.