ecaxpr

ecaxpr is a tiny, declarative, expressions and predicate logic-based language for elementary cellular automata simulation.

There are a total of only 256 distinct elementary cellular automata. We can refer to each of them via a number from 0 to 255 by representing their state evaluation tables as bits. However, ecaxpr represents their rules not by just a simple number, but as a logical formula. This provides a distinct way of experimenting with and thinking about these cellular automata.

Here, an expression like

l == ~(r | t)

***************#*************** 15

becomes...

***************#***************
**************###**************
*************##**#*************
************##*####************
***********##**#***#***********
**********##*####*###**********
*********##**#****#**#*********
********##*####**######********
*******##**#***###*****#*******
******##*####*##**#***###******
*****##**#****#*####*##**#*****
****##*####**##*#****#*####****
***##**#***###**##**##*#***#***
**##*####*##**###*###**##*###**
*##**#****#*###***#**###**#**#*
##*####**##*#**#*#####**#######

Installing

Cargo Install

More about this option: cargo-install(1).

Ensure that the Rust toolchain is available to your environment. Then,

cargo install ecaxpr

Manual Build

Ensure that the Rust toolchain is available to your environment.

git clone https://tangled.org/@did:plc:h5uflu6cfdbvjsggusevvy6i/ecaxpr
cd ecaxpr
cargo build --release

Finally, you can take ./target/release/ecaxpr and do whatever you wish with your executable binary.

Guide

This is a guide meant to help you getting started with using ecaxpr. It does not provide technical documentation outright, and focuses more on examples and walkthroughs.

ecaxpr is a domain-specific language. That domain here is elementary cellular automata.

If you are unfamiliar with elementary cellular automata, and cellular automata in general, then this guide will not be able to help you. As such, you may consider resources like

This guide assumes that you have ecaxpr installed on your system. You may refer to the Installation Instructions page if you have not already installed it.

Hello, ecaxpr!

Let's begin with the simplest elementary cellular automata (ECA) we can! These will yield true cells if and only if the present cell is true, and vice versa for false cells.

Let's write the following and save the file as rule255.ecaxpr.

t
***#***
3

The first line is just t, which stands for the "this" cell. It simply says that for each generation, each cell stays what its "this cell" is, which is itself. This part of the expression is called an L-expr in ecaxpr.

The second line is our initial configuration, where * stand for false and # for true cells. This is called a State-expr in ecaxpr.

Finally, the 3 tells ecaxpr to step through the simulation 3 times. This is also called the Steps-expr, though it is just a number.

Thus, if we run this using ecaxpr rule255.ecaxpr, we get

***#***
***#***
***#***
***#***

The progression of the cellular automaton is shown from top to bottom. The first line is the state before the first step, the second after the first step, the third after the second step, and so on. As we can see, nothing changes.

In the place of t, you can also put r for the right cell's value and l for the left's, respectively. In those cases, the hash symbol should move to either to the left or right. This is because our expression is basically telling each cell to be true its neighbor on one particular side is true, and false otherwise.

r
******#******
7

becomes

******#******
*****#*******
****#********
***#*********
**#**********
*#***********
#************
************#

It appears to move to the left because we specified that the new state values should dependent on the values to their right in their past generation.

You might also notice that in the last line, the hash symbol jumped from the left-most point to the right. ecaxpr wraps the cells around the edges, so that the left-most point connects back to the right-most post, like joining a line to a circle.

Rule 30

If you are sufficiently familiar with the domain of elementary cellular automata, you might have eventually come across Rule 30. Rule 30 in particular is known to demonstrate complex behavior from simple rules, and we can even see patterns similar to it in certain sea shells!

Given any cell, if the cell to its left is true, then Rule 30 says that to be true, the value of this cell and the right must both be false. If the left cell is false, at least one of the left and right cell must be true.

This corresponds to the the following L-expr

l == ~(r | t)

If you are already familiar with boolean operations in typical programming languages, the symbols map neatly here. This expression uses the values of all of the three cells to determine whether the present cell will be true or false.

Here, == is the outermost operation between operands l and ~(r | t). It simply states that the current cell is true only if those operands have the same truth values. If l is true, so is ~(r | t), and vice versa for false.

As for the right-hand operand ~(r | t), the outermost operation now is ~, which stands for negation. This simply inverts the truth value of r | t. Finally, r | t is true if either r or t are. Otherwise, it is false.

Overall, this says what we wanted it to say.

If we now pair this with a State-expr and a number,

l == ~(r | t)

***************#***************
15

We get,

***************#***************
**************###**************
*************##**#*************
************##*####************
***********##**#***#***********
**********##*####*###**********
*********##**#****#**#*********
********##*####**######********
*******##**#***###*****#*******
******##*####*##**#***###******
*****##**#****#*####*##**#*****
****##*####**##*#****#*####****
***##**#***###**##**##*#***#***
**##*####*##**###*###**##*###**
*##**#****#*###***#**###**#**#*
##*####**##*#**#*#####**#######

Experiments

While there are only 256 distinct elementary cellular automata, and we can refer to each of them via a number from 0 to 255 by representing their state evaluation tables as bits, ecaxpr aims to provide a way to refer to them via a logical formula. This also provides a distinct way of experimenting with and thinking about them.

We can take something like

~t | l

*****#***** 15

which becomes

*****#*****
#####*#####
######*####
#######*###
########*##
#########*#
##########*
*##########
#*#########
##*########
###*#######
####*######
#####*#####
######*####
#######*###
########*##

and then wonder what it will become if you swap out the |, disjunction, for &, conjunction.

Here's what it becomes:

*****#*****
******#****
*******#***
********#**
*********#*
**********#
#**********
*#*********
**#********
***#*******
****#******
*****#*****
******#****
*******#***
********#**
*********#*

Other than the first line, everything got inverted!

This makes sense. In the first expression, we ask ecaxpr to make cells true if they are false OR their left cell is true. This meant every cell in *****#***** other than the # would already become true, including the cell to its left. When it came to the # itself, the expression ~t | l evaluate to false. For the subsequent steps, the new # just "loop through" due to the | l part. The * also "loops through" as it would become true, but the value to its right will not.

The second expression is similar. We are asking it to make cells true if they are false AND their left cell is true. The only way for this, which is ~t & l, to evaluate to true would be if t is false and l is true. The only l that could be true here is the same as that which could be in the disjunction experiment. Hence, the inversion.

Rule 90 with an inelegant formula.

It is possible to encode the entire the table of left, "this", and right values to cell states in a case-by-case manner in ecaxpr as well, but also with L-expr.

Here's the table for Rule 90:

l	t	r	result	`L-expr` portion
0	0	0	0	-
0	0	1	1	~l & ~t & r
0	1	0	0	-
0	1	1	1	~l & t & r
1	0	0	1	l & ~t & ~r
1	0	1	0	-
1	1	0	1	l & t & ~r
1	1	1	0	-

and here's that as an L-expr, no simplifications:

(~l & ~t & r) | (~l & t & r) | (l & ~t & ~r) | (l & t & ~r)

Let's run it. Here's a full ecaxpr expression.

(~l & ~t & r) | (~l & t & r) | (l & ~t & ~r) | (l & t & ~r)

*********#********* 8

Result:

*********#*********
********#*#********
*******#***#*******
******#*#*#*#******
*****#*******#*****
****#*#*****#*#****
***#***#***#***#***
**#*#*#*#*#*#*#*#**
*#***************#*

In general, it is possible to express any ECA rule in ecaxpr like this.

Wrapping Up

That's mostly it for the guide. If you find yourself lost, you can refer back to this, or consider the Language Reference!

Language Reference

Every ecaxpr file corresponds to an ecaxpr expression.

An ecaxpr expression consists of three parts:

L-expr: A predicate logic expression representing the rules.
State-expr: An expression representing the initial state.
Steps-expr: A non-negative integer representing the number of steps to simulate.

These names are mostly neologisms given for convenience and precise reference.

Each part of the ecaxpr expression must occur in order exactly as stated.

Newlines, spaces, and tabs do not matter.

L-expr

The following is a verbal description of the grammar of L-expr.

For any operation that is mentioned as "taking in" L-expr, it should be assumed that what they produce are also L-expr. No exceptions arise.

Predicates

The simplest of L-expr are l, t, and r.

Given any cell in our elementary cellular automaton, l is the value of the cell to the left, t the value of the present cell ("this" cell), and r the value of the cell to the right.

These are called predicates, a fancy name for variables in logic.

Negation

Given any L-expr, we can take its negation.

To take the negation of a statement or predicate in logic means to invert its truth value. If it is true, then its negation is false, and vice versa.

If an L-expr predicate is writen as X, we take its negation as ~X in an L-expr. Thus, if X is t, its negation is ~t.

Conjunction ("AND")

Given any set of at least two L-expr, we can take their conjunction.

To take the conjunction in logic means to check if all the conjuncted statements or predicates are true. The conjunction statement/predicate itself is only true if all of them are true, and false otherwise.

For two statements/predicates, this corresponds to stating that both of them are true. In general, it corresponds to stating that all of them are true.

Suppose that we have two L-expr predicates written as A and B, respectively. Then, their conjunction is written as A & B.

Suppose that we have a list of N L-expr predicates, where N is some non-negative integer greater than or equal to 2. Suppose that they are written as L1, L2, L3, ..., LN, respectively. Then, their conjunction is written out as L1 & L2 & ... & LN.

Disjunction ("OR")

Given any set of at least two L-expr, we can take their disjunction.

To take the disjunction in logic means to check if at least one of the disjuncted statements or predicates is true. The disjunction statement/predicate itself is only false if all of them are false, and true otherwise.

Suppose that we have two L-expr predicates written as A and B, respectively. Then, their disjunction is written as A | B.

Suppose that we have a list of N L-expr predicates, where N is some positive integer greater than or equal to 2. Suppose that they are written as L1, L2, L3, ..., LN, respectively. Then, their disjunction is written out as L1 | L2 | ... | LN.

Equality

Given any two L-expr, we can take their equality.

To "take the equality" here means to check if both of the operands are of the same truth values. If so, then the equality is true, and false otherwise.

Suppose that we have two L-expr predicates written as A and B, respectively. Then, their equality is written as A == B.

State-expr

A State-expr consists of * and # in succession.

* represents white or false cells.
# represents black or true cells.

Thus, ***#*** would correspond to an initial states configuration where the first three cells are false, followed by a true one, which is then followed by three more false cells.

Steps-expr

A Steps-expr is simply a non-negative integer.

The ecaxpr Book