Sierpinski triangle (Scheme)
From LiteratePrograms
- Other implementations: C | Erlang | Forth | Haskell | JavaScript | OCaml | Perl | Python | Scheme | Sed
This program is under development.
Please help to debug it. When debugging
is complete, remove the {{develop}} tag.
The following is an implementation of the one-dimensional cellular automata and
the Sierpinski cellular automaton in particular.
A one-dimensional cellular automaton is a linear space of cells, each of which has a state. The automaton changes in discrete time steps called generations. In each generation the state of each cell is decided according to a set of rules that is based on the states of neighboring cells. In the case of one-dimensional cellular automaton each cell has its state decided by considering three cells, itself and its left and right neighboring cells.
We will assume that the cells are arranged in a circle, so the first cell's left neighbor will be the last cell's right neighbor. We could also have assumed (as in the Haskell article) that the first cell's left neighbor and the last cell's right neighbor are constant cells with the value 0.
The Sierpinski cellular automaton has two states, Empty and Full. The only rule states that a cell will be set to Full if and only if of the three states considered exactly one or two are Full.
When run output similar to the following will be produced.
@
@@@
@@ @@
@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@@ @@
@@@@ @@@@
@@ @@ @@ @@
@@@@@@@@ @@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@
@@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@ @@@@@@@@ @@@@@@@@ @@@@@@@@
@@ @@ @@ @@ @@ @@ @@ @@
@@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@ @@@@
@@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@ @@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
First we must choose a representation for a cellular automaton's state. Given the wraparound condition, a Scheme vector seems slightly more convenient than a list. We'll use 0 to represent an empty cell, 1 to represent a filled cell.
One way to start is by defining a function that transforms states represented as vectors into strings that can be printed to screen, and a global variable to hold an initial state for testing purposes:
<<cellular.sc>>= (define (state->string astate) (list->string (map (lambda (x) (if (= x 0) #\space #\@)) (vector->list astate)))) (define *init-state* #80(0)) (vector-set! *init-state* 40 1)
To represent the possible states we will use an association list, for clarity's sake (at the expense of efficiency).
<<cellular.sc>>= (define *rules* '(((0 0 0) . 0) ((0 0 1) . 1) ((0 1 0) . 1) ((0 1 1) . 1) ((1 0 0) . 1) ((1 0 1) . 1) ((1 1 0) . 1) ((1 1 1) . 0)))
We define a vector lookup function that permits wraparound indexing to get our desired boundary conditions, and we use it to define a function that returns the neighbors of a position in a list of three elements:
<<cellular.sc>>= (define (vector-wrap-ref vec position) (vector-ref vec (modulo position (vector-length vec)))) (define (get-neighbors state position) (map (lambda (x) (vector-wrap-ref state (+ x position))) (list -1 0 1)))
The function state->neighbor-list builds a list of neighborhoods for each cell in the state vector. It is tail-recursive.
Now we only need to match each of these neighborhoods with its corresponding rule and turn the resulting list of cell values back into a vector. The whole process is referentially transparent; we're using vectors for their indexing convenience, not their mutability.
<<cellular.sc>>= (define (state->neighbor-list state) (define (list-builder pos accum-list) (if (< pos 0) accum-list (list-builder (- pos 1) (cons (get-neighbors state pos) accum-list)))) (list-builder (- (vector-length state) 1) (list))) (define (apply-rules neighbor-list) (list->vector (map (lambda (neighbors) (cdr (assoc neighbors *rules*))) neighbor-list)))
The program is essentially complete. We'll write another function to test it:
<<cellular.sc>>= (define (run-and-display state iters) (begin (display (state->string state)) (newline) (if (= iters 0) (display "end") (run-and-display (apply-rules (state->neighbor-list state)) (- iters 1))))) ;; we might call it like this: (run-and-display *init-state* 31)
| Download code |