💾 Archived View for gemini.circumlunar.space › users › alchemist › gemlog › aplstuff.gmi captured on 2021-12-17 at 13:26:06. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2020-09-24)
-=-=-=-=-=-=-
Today I wanted to talk a little about cellular automata. But not on a generic context; no, instead I want to show some of the things I did by using the APL language.
First of all, let's adjust your Gemini browser. See if the following code...
{1+⊃+/((-⍺-(⌊⍺÷2))+⍳⍺)⌽¨(⌽2*¯1+⍳⍺)ר⊂⍵}
appears to you similar to this image:
Example image of APL characters
If it does, then you're all set! If not, you may want to install a font for APL characters. I recommend the following fonts; most of them made me very happy for APL programming, in the given order.
GNU FreeFont will provide with most of the things you need, but depends on your taste. APL385 is good for APL and code in general, but lacks some other symbols for other languages. And Nerd Fonts are actually a collection of many fonts, patched to include many symbols, including APL characters.
I currently use FuraMono Nerd Font, a patched, monospaced version of Fira Code font.
I spent the last weeks working on an APL book, which is intended to mix analytic geometry and linear algebra problem solving with the APL language. But the book will also work with other things, such as maze generation and of course cellular automaton building.
Let me show some of those things, since APL is a rather interesting language for manipulating vectors and matrices.
The following code is what we call dyadic a function. It takes two arguments; APL functions may take no arguments (niladic), one argument to the right (monadic), or one argument to the left and another one to the right (dyadic).
findrule←{1+⊃+/((-⍺-(⌊⍺÷2))+⍳⍺)⌽¨(⌽2*¯1+⍳⍺)ר⊂⍵}
Don't be scared; APL functions don't bite. Basically, what is happening is that, given a lattice of cells we call omega (⍵), we calculate the neighborhood rule number for each of the cells, given the size of a neighborhood (⍺). Usually, the size is an odd number, since it accounts for the same number of individuals to the left and to the right of the current cell, plus the current cell.
We'll be only exploring a fixed neighborhood number of 3, so we might as well derive a function which only takes the lattice and works with that fixed neighborhood size. This is a monadic function, since the only missing information will be the lattice.
findrule3←{3 findrule ⍵}
The idea here is that we should have our so-called lattice of cells working somewhat like the following drawing:
Example drawing of a torus-shaped lattice of cells
As you can see, it is a circular shape, so there's no known beginning nor end. The lattice is made like this so that the actual first and last elements of a binary vector always have known neighbors, so we don't have to care about exceptional cases of neighborhoods.
Rules for a neighborhood -- specially on the case of three neighbors -- can be represented by using the visual notation designed by Wolfram. The picture below will show it properly.
Visual representation of Rule 90 (Wolfram, 2002; adapted)
In the picture, white squares are said to be "dead", and black squares are said to be "alive". Furthermore, this can be represented in binary notation, therefore a dead cell is represented by number 0, and a living cell is represented by number 1.
Now, every "T" represented on that drawing is what I personally call a "clause" on a given rule. The top row of three cells is supposed to be the state of the neighborhood in question; the sole square below is supposed to be the new state to be given to the cell at the center of that neighborhood, on the next step of time.
For example, for a neighborhood containing alive-dead-dead cells (100 in binary), the cell at the center will pass from the "dead" state for the "alive" state. This can be verified on the previous image at the fourth "clause", counting from left to right.
Finally, we can think of these "clauses" as 3-digit binary numbers summing up from right to left. First clause is 000, second is 001, then 010, 011.. and so on. Then we can just ignore the neighborhoods above and take only the result states of cells; the image above will yield a binary number of 01011010, which happens to be the number 90 in binary, thus we can call this set of "clauses" Rule 90.
To build Rule 90, we can start by building a small function abstraction which takes the number of the "clauses" (from left to right) where the center cell will remain alive. This uses findrule3, and applies this new rule to the lattice to be given on the left.
do_rule3←{(findrule3 ⍺)⌷¨⊂⌽(⍳8)∊⍵}
We can build many rules with these very simple functions we wrote so far, but for now, let's define Rule 90. We can see that the only "clauses" where the center cell remains alive in Rule 90 are 2, 4, 5 and 7. So we'll build a monadic function which transforms a single argument -- the lattice -- around these numbers and the use of do_rule3.
rule90←{⍵ do_rule3 2 4 5 7}
A very interesting thing to do is to generate images, representing the evolution of repeated application of a rule over a cell lattice. Here is a fragment of a code which represents a dyadic function, which takes a lattice at its left side and the amount of generations at its right side; it produces a matrix of lattices, given the rule evolution from top to bottom.
∇z←board genboard iter ;tmp z←⍬ tmp←board begin: →(iter=0)/end z←(⊂tmp),[1]z tmp←fn tmp iter←iter-1 →begin end: z←((≢z) 1)⍴(⌽z) ∇
Notice also that the function definition is very different from the other ones. This is because genboard uses a traditional definition (tradfns); the other functions are on their dynamic definition (dfns).
Below we have an image representation for Rule 90, produced from a matrix generated by genboard.
Application of Rule 90 over a lattice for 255 generations
This image shows 255 generations of Rule 90 over a lattice of 501 cells, beginning with all cells dead but the one on the center. I do that by generating a .pbm file, as the accompanying code suggests, but I have converted it manually to .png for better portability. Here's the line of code for image generation.
fn←rule90 ⋄ 500 255 genfigure 'img/rule90.pbm'
The generated image is famously known as the Sierpinski Triangle, a fractal.
There are other interesting rules which you can see below. I'll leave their building as an exercise to the reader, but they are not hard to figure out (you can also search for their names, there is no secrecy involved here!).
The special ones are Rule 30, which exhibit completely chaotic behavior, and Rule 110, which is mathematically proven to be Turing-complete, so theoretically it may be used to write computer programs and to emulate a computer as well, though this would be very tough to do.
Cellular automata fascinate me. This is a very extensive topic. Wolfram's book is still catching dust on my bookshelf, but is an interesting read so far to catch one's attention to cellular automata.
This is just a very small fragment of my activities, and I've been exploring deeper meanings on AC's, mostly related to computational intelligence, cognitive science and complex systems -- I still think that there is room for exploration on it, though we may want to incorporate some concepts to help us visualize what we need to do on this topic. Hope you enjoyed this small amuse-bouche of APL functions.
