CASTLE

CASTLE

Paradigm(s)	Declarative
Designed by	User:Quintopia
Appeared in	2014
Computational class	Turing complete
Reference implementation	Unimplemented
Influenced by	ALPACA,Clue (oklopol),Golly's .rule
File extension(s)	.cas

CASTLE, which stands for "Cellular Automaton Specification by Transforming Lists of Examples", is a 2014 experimental language by User:Quintopia. Inspired by example-driven languages like Clue (oklopol) and CA specification languages, particularly the .rule file format for Golly. The goal was to create a method for specifying CAs in which nearly arbitrary transformations can be specified, even those with non-traditional neighborhood shapes and sizes and those with neighborhoods that change over time, in a human-readable format.

File Format

Files are organized thusly (comments and placeholders in italics are not a part of the format):

def list,of,state,symbols
def id(list of included states) or def id[list of disincluded states]
partition (tesselation symmetry) This section is optional, used only for block CAs
symmetries of blocks
Description of partition time-dependence. See relevant section.
(blank line) The following section is not optional, because it is the actual specification of the CA rules
[prob:]state1|id1->state2|id2 describe which state/class of states we are transitioning from and to (with optional probability)
state2|id2->state3|id3 it's possible for multiple states to be simultaneously transformed in a single transition description
(etc.)
[symmetries to apply to this example (space for none)
.r.e.c.t
.a.n.g.u
.l.a*r.p
.a.t.t.e
.r.n.b.l
.o.c.k.?
=== 
symmetries for this example
.a.n.o.t
.h.e.r.p
.a.t*e.r
.n.f.o.r
.t.h.i.s
.c.a.s.e
]

It's also possible to specify hexagonal grid by starting alternating lines with spaces:
 .h.e.x.a
.g.o.n.a.l
 .g.r.i.d
.s.l*o.o.k
 .l.i.k.e
.t.h.i.s.?
So a hexagonal moore neighborhood:
 .6.x
.m*o.o
 .r.e

No file may contain both hexagonal and rectangular grids.

States and state classes

Any string of characters not given a special meaning by this document can symbolize a state (all of =*,.:?!@;()[]-> are disincluded, for example), and an automaton may have any number of states. For instance, CGoL has two, Wireworld has four, and REDGREEN has 23. These are defined using a "def" statement followed by the comma-separated list of state names. For convenience, it is recommended to make state names as short as possible and all the same length. It is also possible to assign a name to an entire class of states. "def id()" and "def id[]" serve this purpose. The brackets should contain a comma-separated list of state or class names which were previously defined. In the case of square brackets, all states except for those listed will be assigned to the class. There is one special predefined class called ?, which automatically contains all defined states.

Defining block automata

Using the "partition" keyword, it is possible to define automata which use irregularly shaped blocks in the place of cells, as long as the blocks can be tessellated by a rectangular or hexagonal symmetry, such that the position of each block varies with each time step. This is done by describing the shape of a neighborhood of blocks visually, and providing a description of the symmetry by which it is tesselated as described below. The shape of the block description must be either a rectangle or hexagon, in which regions belonging to separate blocks are assigned different numbers. For each cell is given a list of numbers enclosed by curly braces, providing block numbers corresponding to different partitions at each time tick (mod the length of a list). Each list must be the same length, and all blocks must all be congruent in each time tick described. The compiler will check that the description can be tessellated according to the symmetry provided. See the example for the Billiard ball machine to see how a time-dependent moving square partition can be described.

When defining blocks, arbitrary ways of tessellating the blocks are permitted. By default, they will be tessellated by straight translation in a rectangular or hexagonal grid as seems most appropriate, but any permutation of edges may be defined using permutation cycle notation. An edge permutation is given using i for no reflection and r for reflection with edges numbered clockwise from the top. So (1r3r)(2i4i) is a Klein bottle and (1r2r3r4r) is another type of Klein bottle. (1r2i3r4i) is a type of projective plane. (If no such symmetry is specified, it's assumed to be (1i3i)(2i4i) for rectangular and (1i4i)(2i5i)(3i6i) for hexagonal.)

Describing State Transitions by Example

Central to CASTLE is the ability to give examples to describe the ways in which states are updated on each tick. Because CASTLE truly allows arbitrary (local) conditions to play a role in determining state transitions, it must be possible to easily describe large classes of conditions with relatively few examples. In CASTLE, this is done by providing a list of examples, each one consisting of a list of transitions that should take place in the described conditions; a list of descriptions of representative neighborhoods, each consisting of a set of symmetries that should apply to the example (and only that example!); and a visual description of a representative neighborhood of the cell/block in which those state transitions should be performed. The representative neighborhoods are separated from each other by a line consisting only of "===". The compiler will generate from these examples a rule such that the overall board state is matched against each example in the order they are provided, and the transitions are performed in the first one that matches. By default, if no example is matched for a given cell/block, that cell or block will remain in the same state, which one could take to mean that there is an implied example at the end of the list that matches all conditions and maps every state to itself. See example programs at the bottom to make this clearer.

Note that the representative neighborhoods and their corresponding symmetries are optional. If absent, the provided transitions will always occur, unless an earlier transition is matched. Also note that not all states/classes on the left sides of transitions must be marked in a matched representative neighborhood. Only those transitions whose left sides match a marked state/class will be performed. It is possible for multiple cells to be marked, each corresponding to different states/classes, and therefore to different transitions. It is illegal to mark a state/class for which there is no associated transition with that state/class on the left-hand side. Since symmetries are applied only with respect to the "first marked cell", it is possible for the other marked cells to be permuted by symmetries, matching different cells depending on the permutation chosen. When multiple ways to match a neighborhood are possible, one should be chosen uniformly at random (where randomness is available) or else the first available match should be chosen (where no randomness is available).

Class names or state names may appear on either side of the '->' in a transition description. In the event that a class name appears on the right side of a transition, it may followed by a number in square brackets. In each example provided for that transition, a cell labeled with that class may also include the same number in square brackets to indicate which specific state in that class is to be matched and transitioned to. If no numbers are given in square brackets, the first cell labeled with that class in the examples in row major order will be matched. If no cell is labeled with that class, the first cell in the example region which happens to contain a member of that class (matched perhaps by ? or some other more inclusive class) will be matched. If it is possible that the example will match without containing any member of that class, compilation must fail.

Each state transition provided for a given set of examples can also be given an optional probability. This shall be a decimal number between 0 and 1. If present, before performing the transition, the automaton simulator will pick a random number between 0 and 1 and perform the transition if and only if the resulting number is less than or equal to the provided probability. This ability is only supported when the compilation target is one which is capable of probabilistic transitions in cellular automata, and the probability will be ignored otherwise. One may also specify conditional transitions using the "also" and "else" keywords, which would be placed where a probability would be placed. "also" evaluates to 1 if the transition on the previous line probabilistically succeeded and 0 otherwise. "else" evaluates to 1 if the previous line probabilistically failed and 0 otherwise.

The visual neighborhood description is a multi-line arrangement of cell descriptions, each of which consists of a special cell marker and a state/class id. In a block automaton, the shape of the example must correspond exactly to the shape of the partition in the orientation assigned the number 1 according to the partition description or compilation must fail.

Special Syntax for Examples

Individual cells in an a neighborhood description can be marked to modify the way they are parsed and permuted when matching state transitions.

Symbol	Meaning
.	This prefix indicates a reference cell, which must be exactly the state or class it indicates. Its position may be permuted by relevant symmetries for matching.
:	This prefix indicates a reference cell, which must be anything other than the state or class it indicates. Its position may be permuted by relevant symmetries for matching.
*	This prefix marks cells which will be updated by this state transition. The state/class given should be its starting state. Unless the marked cell's state corresponds to the left-hand-side of the first state transition, and it is the first such cell in row major order, its position may be permuted by relevant symmetries for matching.
@	This prefix marks cells which may be updated by this state transition. The state/class given should be its starting state. Symmetries will not alter its position. If symmetry is not +, the collective shape of cells not flagged with this prefix must be symmetrical under the described symmetries.
!	This prefix indicates this cell must be in exactly this position, and that symmetries do not apply to it. If symmetry is not +, the collective shape of cells not flagged with this prefix must be symmetrical under the described symmetries.
;	This prefix is like ! except that it matches only states and classes other than the one indicated.

Symmetry

All cellular automata require a grid of cells of some sort, each of which can be in one of a number of states. Depending on the nature of the grid and the nature of the automaton, the neighborhoods of each cell can be different shapes and sizes. In CASTLE, one describes a state transition by simply "drawing" the state of a cell's neighborhood in which the transition would take place, but for, for example, a totalistic automaton like Conway's Game of Life, it would be tedious to draw all 56 neighborhood arrangements that would result in an off cell turning on. Therefore, it is necessary to be able to define symmetries that can be applied to an example, so that 55 of those neighborhood arrangements can be inferred from the example given by simply permuting the neighborhood in all ways allowed by the symmetry. Symmetries are applied relative to the "first marked cell", which is the first cell in row-major order whose current state/class corresponds to the left-hand-side of the first transition for this example set. CASTLE supports the following symmetry types:

Symbol	Symmetry Type	Description
|	Left-right reflective symmetry	All non-fixed cells in the neighborhood could be mirrored left/right. This may optionally be followed immediately by a list of pairs of states, such that, when the neighborhood is mirrored, any state in such a pair will be swapped for the its counterpart. For instance: |[(«,»)] will swap all «'s for »'s and vice versa, but only when the neighborhood is mirrored. The same goes for all of the reflective symmetries below.
-	Top-bottom reflective symmetry	All non-fixed cells in the neighborhood could be mirrored top/bottom.
/	NW-SE reflective symmetry	All non-fixed cells in the neighborhood could have their first-marked-cell-relative coordinates within that neighborhood swapped.
\	NE-SW reflective symmetry	All non-fixed cells in the neighborhood could have their first-marked-cell-relative coordinates within that neighborhood swapped and negated.
2	2-way rotational symmetry	All non-fixed cells in the neighborhood could be rotated a half-turn around the first marked cell
3	3-way rotational symmetry	All non-fixed cells in the neighborhood could be rotated a third-turn around the first marked cell in either direction. (Only available for hexagonal grids). This may optionally be followed immediately by a list of triples of states, such that, when the neighborhood is rotated, any state in such a triple will be swapped for the state circularly following it in the list.
4	4-way rotational symmetry	All non-fixed cells in the neighborhood could be rotated by any multiple of a quarter-turn around the first marked cell. (Only available for square grids). This may optionally be followed immediately by a list of quadruples of states, such that, when the neighborhood is rotated, any state in such a pair will be swapped for the state circularly following it in the list.
6	6-way rotational symmetry	All non-fixed cells in the neighborhood could be rotated by any multiple of a one-sixth-turn around the first marked cell. (Only available for hexagonal grids.) This may optionally be followed immediately by a list of hextuples of states, such that, when the neighborhood is rotated, any state in such a pair will be swapped for the state circularly following it in the list.
>	Quarter-turn clockwise rotational symmetry	All non-fixed cells could be rotated exactly one quarter-turn clockwise around the first marked cell. (Only available for square grids.)
<	Quarter-turn counter-clockwise rotational symmetry	All non-fixed cells could be rotated exactly one quarter-turn counter-clockwise around the first marked cell. (Only available for square grids. Note that >2< means the same as 4.)
'n	n-sixths-turn counter-clockwise rotational symmetry	All non-fixed cells could be rotated exactly n-sixths of a turn counter-clockwise around the first marked cell. (Only available for hex grids. Note that '1'3'53 is equivalent to 6.)
+	All possible spatial symmetries	All permutations of non-fixed cells will be matched. (Use with ? for totalistic automata.)

Examples

CGoL:

def 0,1

0->1
+
.1.1.1
.0*0.0
.0.0.0

1->0
+
.?.0.0
.0*1.0
.0.0.0
===
+
.1.1.1
.1*1.?
.?.?.?

Schrödinger's Game of Life:

def 0,1,C
def A(1,C)
def D(0,C)

D->1
+
.1.1.1
.0*D.0
.0.0.0

A->0
+
.?.0.0
.0*A.0
.0.0.0
===
+
.1.1.1
.1*A.?
.?.?.?

1->1
+
.1.1.?
.0*1.0
.0.0.0

0->0
+
.?.?.0
.0*0.0
.0.0.0
===
+
.1.1.1
.1*0.?
.?.?.?

0->C
1->C

Rule 110 (notice the blank lines containing only space characters indicating no symmetries will be applied, as all variation is done with the use of wildcards):

def 0,1
 
0->1

.?*0.1

1->0
 
.1*1.1

Wireworld:

def 0,h,t,c

h->t

t->c

c->h
+
.h.?:h
:h*c:h
:h:h:h

Billiard ball machine:

def o,#
partition
{1,4}{1,3}{2,3}{2,4}
{1,2}{1,1}{2,1}{2,2}
{3,2}{3,1}{4,1}{4,2}
{3,4}{3,3}{4,3}{4,4}

o->#
#->o
4
*#.#
.#*o
===
4
*#*o
*o*#

Circute:

def N,—,~,#,0

—->#
4
.#
*—
===
|-
.—.N.?
.?*—.?

#->~
4
.~
*#
===
-
.#.N.#
.?*#.?

~->—

REDGREEN:

def a,~,%,#,&,s,k,o,f,p,t,^,-,=,D,O,1,z,Z,¿,«,»,T
def F(p,:,O,1)
def P(a,~,%,s,k,o,z,Z)
def M(D,O,1)
def S(s,k,o)
def B(%,&,^,z,Z)
def _(#,&,:,^,-,=,D,1,¿)
def |[_,D]
def C[T,D,1]
def d[~,f]
def n[%,&]

F->a
+
.a.a:D
:D*F:D
:D!|:D

F->~
+
.~.~.~
.~*F:D
:D!|:D

F->F
|[(«,»)]
:P*F
.?.«

P->F
 
.F
*P
===
|[(«,»)]
*P.F
.?.«

M->%
+
.B.?.?
.?*M.?
.?.?.?

S->~
+
.~.?.?
.?*S.?

S->a

a->~
+
.~.?.?
!?*a!?
===
|
.~*a
._.?
===
|
.~*a
.~.~

a->s
+
!?*a!?
.s.?.?

a->k
+
!?*a!?
.k.?.?

a->z
+
.^.?.?
.?*a.?
.?.?.?

~->s
+
.%.?.?
.?*~.?
.?.?.?
===
+
.&.?.?
.?*~.?
.?.?.?

~->o
 
*~
.S

~->f
+
.f.f.f
.~*~.~
.~.~.~

%->k
+
.~.?.?
.?*%.?
.?.?.?
===
 
:a:a:a
:a*%:a
:a:a:a
===
 
.C.C.C
.C*%.C
.C.C.C

#->&
+
.%.?.?
.?*#.?
.?.?.?

&->#
+
:%.n.n
.n*&.n
.n.n.n

f->a
+
.d:~:~
:~*f:~
:~:~:~

f->~
+
.f.f.f
.f*f.?
.?.?.?
===
+
.~.~.~
.~*f.~
.~.~.?

p->t
 
.p
*p
._

=->^
+
.^.?:^
:^*=:^
:^:^:^

D->O
+
.?:D:D
:D*D:D
:D:D:D
===
+
:_:_:_
:_*D:_
:_:_:_

0.5:«->»
0.5:»->«
|[(«,»)]
*«
.¿