{"id":191,"date":"2006-10-20T14:07:31","date_gmt":"2006-10-20T14:07:31","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2006\/10\/20\/a-metalanguage-for-pathological-programming-cellular-automata-in-alpaca\/"},"modified":"2006-10-20T14:07:31","modified_gmt":"2006-10-20T14:07:31","slug":"a-metalanguage-for-pathological-programming-cellular-automata-in-alpaca","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2006\/10\/20\/a-metalanguage-for-pathological-programming-cellular-automata-in-alpaca\/","title":{"rendered":"A Metalanguage for Pathological Programming: Cellular Automata in Alpaca"},"content":{"rendered":"

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.
\nFrankly, 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!
\nAlpaca 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.
\nAlpaca’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.<\/p>\n


\nIn case you’re non familiar with cellular automatons, here’s a very quick explanation.
\nIn 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.
\nIt’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.
\nFor 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)
\nLife is trivial in Alpaca:
\nstate Dead ” ” to Alive when 3 Alive and 5 Dead;
\nstate Alive “*” to Dead when 4 Alive or 7 Dead.
\nYou nawe the states, and the rules by which they’ll change states. The thing in quotes is
\nthe character that will be used in input files to represent a cell in that state.
\nHere’s an example of a very simple input file for the life automaton: it’s called a *glider*.<\/p>\n

\n*\n* *\n**\n<\/pre>\n
If you run the glider, what you’ll get is basically that figure moving diagonally across the grid. Here’s a few steps:
\n
\nOr much cooler, here’s a pattern called the turbine:<\/p>\n
\n****** **\n****** **\n**\n**     **\n**     **\n**     **\n**\n** ******\n** ******\n<\/pre>\n
If you run the turbine in life, it will go though a cycle of eight steps over and over again:
\n\"life-turbine-one.jpg\"
\n\"life-turbine-two.jpg\"
\nAnother 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).
\nIn 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:
\n1. If you’re the leading edge of a spark, next step, you turn to tail.
\n2. 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.
\n3. If you’re the trailing edge of a spark, next step, you turn to wire.
\n4. Otherwise, just stay the way you are.
\nWritten in Alpaca, wireworld is:
\nstate Empty ” “;
\nstate Spark “#” to Tail;
\nstate Tail “-” to Wire;
\nstate Wire “=” to Spark when 1 Spark and not 3 Spark.
\nAnd 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:
\n
\nNow, 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:
\n\/*
\n* The Braktif Cellular Automaton
\n* June 2005, Chris Pressey
\n*
\n* Braktif is an esoteric programming language very similar to
\n* ‘Brainfuck F’ and ‘Archway’, with a small but significant
\n* difference: Braktif is formulated as a 28-state cellular automaton.
\n*
\n* Braktif playfields are divided into a program on the right and
\n* a data storage area on the left.  (The data storage area can be
\n* considered to extend indefinately to the left.)  The program
\n* and data area are connected by a ‘bus’.  On the bus sit the
\n* instruction pointer, which rests underneath the part of the
\n* program which is currently executing, and the data pointer, which
\n* rests underneath the part of the storage which is currently being
\n* addressed.  The instruction pointer and data pointer communicate
\n* by means of signals (from the IP to the DP) and replies (from the
\n* DP to the IP) sent along the bus.
\n*
\n* The instructions of a Braktif program resemble those of Smallfuck
\n* or Brainfuck F:
\n*
\n*   *   flip current data bit
\n*   >   advance DP one cell to the right
\n*   +]
\n*
\n* Braktif:
\n*                            WendCmd) or (> SkipBack),
\nto SkipStart when ^< SkipReply and ^ InstrMark,
\nto SkipFore when v< SkipStart or  when > is Signal,
\nto ^> when ^> is Signal,
\nto v> when v> is Signal,
\nto < when < is Reply,
\nto ^< when ^< is Reply,
\nto v< when v LeftTool or < RightTool,
\nto ContReply when < ContTool,
\nto SkipReply when  InstrPtr and ^> LeftCmd,
\nto RightSig when > InstrPtr and ^> RightCmd,
\nto FlipSig when > InstrPtr and ^> FlipCmd,
\nto QuerySig when > InstrPtr and ^> WhileCmd,
\nto InstrPtr when < WakeMark or v< WakeMark or ^< Wakemark,
\nto InstrPtr when < InstrPtr and ^ SkipBack,
\nto SkipStop when < SkipFore,
\nto InstrPtr when  FlipSig,
\nto LeftTool when > LeftSig,
\nto RightTool when > RightSig,
\nto SkipTool when > QuerySig and ^ OffBit,
\nto ContTool when > QuerySig and ^ OnBit;
\nstate FlipTool\t“f”
\nto ContTool;
\nstate LeftTool\t“l”
\nto Bus;
\nstate RightTool\t“r”
\nto Bus;
\nstate ContTool  “c”
\nto DataPtr;
\nstate SkipTool\t“s”
\nto DataPtr;
\n\/* —————– Data Store: Tape Contents —————– *\/
\nstate OnBit\t“1”
\nto OffBit when v FlipTool;
\nstate OffBit\t“0”
\nto OnBit when v FlipTool;
\n\/* —————– Program: Instruction Pointer ————– *\/
\nstate InstrPtr\t“i”
\nto Bus when ^ Space,
\nto InstrMark;
\nstate InstrMark\t“I”
\nto WakeMark when < ContReply,
\nto Bus when < SkipReply;
\nstate WakeMark\t"W"
\nto Bus;
\n\/* —————– Program: Instruction Skipper ————– *\/
\nstate SkipStart\t"!"
\nto Space;
\nstate SkipStop\t"%"
\nto Bus;
\nstate SkipFore\t"}"
\nto Space;
\nstate SkipBack\t"{"
\nto Space;
\n\/* ——————– Program: Instructions ——————- *\/
\nstate FlipCmd\t"*";
\nstate LeftCmd\t"”;
\nstate WhileCmd\t“[“;
\nstate WendCmd\t“]”.
\nI 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-191","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-35","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/191","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=191"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/191\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=191"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=191"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=191"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}