1-d cellular automaton in a graph grammar

This is the first example I tried that really pushed my engine hard. It would be better broken up into multiple grammars, I think. I wanted to run Rule 30, a 1-d cellular automata, as a graph grammar in Soffit.

I decided to split up the construction into two phases, because I tried and failed several times to make "generate a row" and "implement the transition rule" work together. This way, the basic cell structure can be re-used for different rules fairly easily.

This grammar uses the techniques described here and here to grow a set of cells one row at a time. A cursor is used to grow the cells in a deterministic fashion, and a counter is used to limit the total number of rows, and tell us when it's done.

    "start" : "E1->X1->E2 [h]; E1[e]; E2[e]; X1[x]; S->X->C[h]; S[start]; X[x]; C[cursor]; E1->X[v]; X1->C[v]; R[row]; RE[end]; R->R1->R2->R3->R4->R5->R6->R7->R8->R9->RE",
    
    "X[x]; P[x]; P1[x]; C[cursor]; X->C [h]; P->C[v]; P->P1[h]" :
    "X[x]; P[x]; P1[x]; C[x];      X->C [h]; P->C[v]; P->P1[h]; N[cursor]; P1->N[v]; C->N[h]",
    
    "X[x]; P[x]; P1[e]; C[cursor]; X->C [h]; P->C[v]; P->P1[h]" :
    "X[x]; P[x]; P1[e]; C[x];      X->C [h]; P->C[v]; P->P1[h]; N[cursor]; P1->N[v]; C->N[h]",
    
    "X[x]; P[e]; C[cursor]; X->C [h]; P->C[v];" :
    "X[x]; P[e]; C[x];      X->C [h]; P->C[v]; N[cursor]; C->N[h]",
    
    "S[start]; XL[x]; EL[e]; S->XL [h]; EL->XL[v]; C[cursor]; XR[x]; ER[e]; ER->XR[v]; XR->C[h]; R[row]; RN; R->RN;" :
    "S[e];     XL[x]; EL[e]; S->XL [h]; EL->XL[v]; C[e];      XR[x]; ER[e]; ER->XR[v]; XR->C[h]; RN[row]; NewS[start]; NewX[x]; NewC[cursor]; NewS->NewX->NewC [h]; S->NewX[v]; XL->NewC[v];",

    "S[start]; XL[x]; EL[e]; S->XL [h]; EL->XL[v]; C[cursor]; XR[x]; ER[e]; ER->XR[v]; XR->C[h]; R[row]; RE[end]; R->RE" :
    "S[e];     XL[x]; EL[e]; S->XL [h]; EL->XL[v]; C[e];      XR[x]; ER[e]; ER->XR[v]; XR->C[h]; Z[initialcell]",

Then we populate the original row, and convert any "edge" cells into two "0" cells so that we can apply the rules to them correctly. This would be cleaner if we did it in a separate pass instead of having to deal with the possibility that some cells may have been filled in already.

    "Z[initialcell]; E1[e]; X[x]; E2[e]; E1->X->E2 [h]" :
    "Z[style=invis]; E1[e]; X[1]; E2[e]; E1->X->E2 [h]",

    "Z[style=invis];       A[e]; B[x]; A->B[h];" :
    "Z[style=invis]; N[0]; A[0]; B[x]; N->A->B[h];",

    "Z[style=invis];       A[e]; B[x]; A<-B[h];" :
    "Z[style=invis]; N[0]; A[0]; B[x]; N<-A<-B[h];",

    "Z[style=invis];       A[e]; B[0]; A->B[h];" :
    "Z[style=invis]; N[0]; A[0]; B[0]; N->A->B[h];",

    "Z[style=invis];       A[e]; B[0]; A<-B[h];" :
    "Z[style=invis]; N[0]; A[0]; B[0]; N<-A<-B[h];",

    "Z[style=invis];       A[e]; B[1]; A->B[h];" :
    "Z[style=invis]; N[0]; A[0]; B[1]; N->A->B[h];",

    "Z[style=invis];       A[e]; B[1]; A<-B[h];" :
    "Z[style=invis]; N[0]; A[0]; B[1]; N<-A<-B[h];",

The cellular automaton rules themselves are completely straightforward once all that setup has been done.

I used fake rules for comments. This is one severe weakness of using JSON. I'm thinking of scrapping it, since I don't think I'll be doing a JavaScript version of this engine.

    "X[rule 000 -> 0]" : "",
    
    "A[0]; B[0]; C[0]; A->B->C [h]; N[x]; B->N [v]" :
    "A[0]; B[0]; C[0]; A->B->C [h]; N[0]; B->N [v]",

    "X[rule 001 -> 1]" : "",
    
    "A[0]; B[0]; C[1]; A->B->C [h]; N[x]; B->N [v]" :
    "A[0]; B[0]; C[1]; A->B->C [h]; N[1]; B->N [v]",

    "X[rule 010 -> 1]" : "",
    
    "A[0]; B[1]; C[0]; A->B->C [h]; N[x]; B->N [v]" :
    "A[0]; B[1]; C[0]; A->B->C [h]; N[1]; B->N [v]",

    "X[rule 011 -> 1]" : "",
    
    "A[0]; B[1]; C[1]; A->B->C [h]; N[x]; B->N [v]" :
    "A[0]; B[1]; C[1]; A->B->C [h]; N[1]; B->N [v]",

    "X[rule 100 -> 1]" : "",
    
    "A[1]; B[0]; C[0]; A->B->C [h]; N[x]; B->N [v]" :
    "A[1]; B[0]; C[0]; A->B->C [h]; N[1]; B->N [v]",

    "X[rule 101 -> 0]" : "",
    
    "A[1]; B[0]; C[1]; A->B->C [h]; N[x]; B->N [v]" :
    "A[1]; B[0]; C[1]; A->B->C [h]; N[0]; B->N [v]",

    "X[rule 110 -> 0]" : "",
    
    "A[1]; B[1]; C[0]; A->B->C [h]; N[x]; B->N [v]" :
    "A[1]; B[1]; C[0]; A->B->C [h]; N[0]; B->N [v]",

    "X[rule 111 -> 0]" : "",
    
    "A[1]; B[1]; C[1]; A->B->C [h]; N[x]; B->N [v]" :
    "A[1]; B[1]; C[1]; A->B->C [h]; N[0]; B->N [v]"

Completely expanding this set of rules into a final graph takes about 80 seconds; the slow part is the grid expansion. I thought that should be straightforward and efficient because it's based around the unique "cursor" node, but I'll have to look into what the constraint solver is actually doing.

After some hand-editing of the output to make 1's black squares and 0's white squares, this is the output, which graphviz almost displays in a triangle:

This is probably one of the least efficient methods of implementing a 1-d cellular automata possible. But as a demonstration of the capabilities of a graph grammar, I think it's pretty cool.

The problem with doing the conversion from 1 and 0 to graphviz attributes inline is that there's no good way to say "OK, the CA part is done, now make it pretty" so the CA rules would have to accept the styled versions. I started out doing that and it was horrible. Multiple passes is a feature I'm going to add sooner rather than later.

A more radical change to Soffit would be to allow ASCII diagrams rather than Dot notation. My notes (like these):

   eXe
  SXXC
  
   eXe
  SXXXC

   eXe
  eXXXe
 SXC

are much clearer than the final rule set. But does this only work when writing planar graphs? Would making all the edges explicit make this just as much a mess as the current format?