Sierpinski triangle (Sed)

From LiteratePrograms

Other implementations: C | Erlang | Forth | Haskell | JavaScript | OCaml | Perl | Python | Scheme | Sed

The following is an implementation of the one-dimensional cellular automata, and the Sierpinski cellular automaton in particular, in sed(1).

practice

We conflate the Empty and Full states with their on-screen representation, as space and @ respectively.

To transform the automaton from one generation to the next we apply the rules to each cell in the automaton in turn. Rule application consists of examining the cells to the right of a cursor, c, and writing the result to the left.

<<empty if similar>>=
s/c \(  \)/ c\1/
s/c@\(@@\)/ c\1/

<<full otherwise>>=
s/c.\(..\)/@c\1/

Because the cursor steps from left to right, repeating these substitutions until convergence will run the cursor over multiple cells.

(NB. cursor comes from the Latin word for "runner". sed comes from the Latin word for "but", as in "not this, but that")

The patterns are not disjoint, so we must apply them in order, and restart the loop after each of the cases.

<<scan cells>>=
:loop
empty if similar;tloop
full otherwise;tloop

In order to process an entire line, we initialize the loop with the cursor on the left-hand end, and empty neighbors at either end of the automaton space. Once the cursor reaches the right-hand end, the scan is finished and we remove the cursor.

<<calculate line>>=
s/.*/c  &  /
scan cells
s/c.*//

wrapping up

Finally, we arrange for the hold space to save our state from one step to the next.

• x;s/^$/@/;p retrieves the state from the hold space

(initializing to a single Full cell if necessary) and prints it

• x;d saves the state in the hold space and waits for input

<<sierpinski.sed>>=
x;s/^$/@/;p
calculate line
x;d

This single steps, producing a left-justified output each time the user presses the enter key. To produce the diagram above, use the following wrapper:

jot 32 | sed -f sierpinski.sed | awk '{print substr("                                        ",1,40-length($0)/2),$0}'

Download code