4. Representing Patterns for the Game of Life

The lifepoint module defines the representation of cells for the Game of Life. We have an infinite square grid of cells, which can each be alive or dead. A finite number of live cells are distributed fairly sparsely within a finite area of the grid, forming a Game-of-Life pattern. The area of the grid occupied by the pattern can grow without limit, although it always remains finite. A suitable representation for Game-of-Life patterns is a sorted list of live points (PntList), where each point (Pnt) is a pair of integers. The strictness annotations ensures that evaluation of the elements of the pair, and of the points in the list, is forced. This allows the CLEAN compiler to generate more efficient code.

IMPLEMENTATION MODULE lifepoint;
IMPORT lifemisc;

TYPE
:: Pnt -> (!INT,!INT);
:: PntList -> [!Pnt];

To represent the rectangle actually occupied by live cells, we use the Rect type, which stores the coordinates of the upper left and lower right corners of the rectangle. We assume coordinates increase going downwards and to the right, so that the rectangle occupied by live cells is specified by the pair of minimum coordinate values and the pair of maximum coordinate values. To assist in calculating these values, the Lifestats type is intended to record the minimum, total (for calculating average), and maximum values of x and y coordinates of live cells:

:: Rect -> (!Pnt, !Pnt);
:: Lifestats -> (!INT, !INT, !INT, !INT, !INT, !INT);

The rules for the Game of Life specify that live cells die if they have less than two or more than three live neighbours, and dead cells become live if they have precisely three live neighbours. To keep track of this information, the Info type stores a point, plus a boolean value to indicate if the point was live, and an integer to record the number of live neighbours:

:: Info -> (!INT,!INT,!BOOL,!INT);
:: InfoList -> [!Info];

The functions for manipulating points include a recursive function to test if two sorted lists of points are identical. The && operator is an infix conditional-and for use in guards only. There is also a conditional-or (||) operator.

RULE
:: Same !PntList !PntList -> BOOL;
   Same [] [] -> TRUE;
   Same l  [] -> FALSE;
   Same [] l  -> FALSE;
   Same [(x,y)|t] [(x',y')|t'] -> Same t t', IF = x x' && = y y'
                               -> FALSE;

The SwapPnt function adds a point to a sorted list if it is absent, or deletes it if it is present. The notation z:e has the same meaning as e, but also defines the name z as a reference to e (implemented as a second pointer to e). Thus l denotes the entire input list [(x',y')|t], and u denotes the first point in the list. The variable p denotes the result of adding the point (x,y) to front of l in the case that it is missing, which is the result of the function in two cases. The variable q denotes the result of adding the original head u to the front of a recursive function call. This result is also returned in two cases. The == symbol introduces a comment terminated by end-of-line:

:: SwapPnt !INT !INT !PntList -> PntList;
   SwapPnt x y [] -> [(x,y)];
   SwapPnt x y l:[u:(x',y')|t] -> p:[(x,y) | l], IF < y y'
                               -> q:[u | SwapPnt x y t], IF > y y'
                               -> p, IF < x x'  == now y=y'
                               -> q, IF > x x'
                               -> t;    == now y=y' & x=x', so delete u

The SortPnt function performs a (slow) insertion sort on a list of points, using SwapPnt for insertion. It is used only to create an initial sorted list:

:: SortPnt !PntList -> PntList;
   SortPnt [] -> [];
   SortPnt [(x,y)|t] -> SwapPnt x y (SortPnt t);

The CropPnt function crops the Game-of-Life grid to a finite rectangular viewing window ((a,b),(c,d)), at the same time re-scaling coordinates so that (0,0) is the top left cell of the window. This function shows another form of local variable definition, where p is used first, and defined at the end of the rule:

:: CropPnt !INT !INT !INT !INT !PntList -> PntList;
   CropPnt a b c d [] -> [];
   CropPnt a b c d [(x,y)|t] -> p, IF < y b
                             -> [], IF > y d
                             -> p, IF < x a
                             -> p, IF > x c
                             -> [(- x a, - y b) | p],
                                p:CropPnt a b c d t;

The StatPnt function calculates the number of cells and other statistics for a list of points, using the tail-recursive auxiliary function StatPntAux. This auxiliary function takes as arguments the current minimum, total, and maximum values of x and y coordinates, and the number of points processed (initially 0). Since CLEAN has no unary negation operator, the initial value for the maximum x and y coordinates is defined using subtraction to be (- 0 Huge):

:: StatPnt !PntList -> (!INT, !Lifestats);
   StatPnt l -> StatPntAux Huge 0 (- 0 Huge) Huge 0 (- 0 Huge) 0 l;

:: StatPntAux !INT !INT !INT !INT !INT !INT !INT PntList 
                                                -> (!INT, !Lifestats);
   StatPntAux a b c d e f n [] -> (n, (a, b, c, d, e, f));
   StatPntAux a b c d e f n [(x,y)|t] 
    -> StatPntAux (Min x a) (+ x b) (Max x c) 
                  (Min y d) (+ y e) (Max y f) (++ n) t;

The StepInfo function converts a list of points to an unsorted list of Info entries, one for each live cell and its eight neighbours. The entry for the live cell is given a true liveness flag and a live-neighbour count of zero, while the neighbours are given a false liveness flag and a live-neighbour count of one:

:: StepInfo PntList -> InfoList;
   StepInfo [] -> [];
   StepInfo [(x,y)|t] -> [(-- x, -- y, FALSE, 1),
                          (-- x, y,    FALSE, 1),
                          (-- x, ++ y, FALSE, 1),
                          (x,    -- y, FALSE, 1),
                             (x, y, TRUE , 0),
                          (x,    ++ y, FALSE, 1),
                          (++ x, -- y, FALSE, 1),
                          (++ x, y,    FALSE, 1),
                          (++ x, ++ y, FALSE, 1) | StepInfo t];

The following three functions define a (fast) merge-sort InfoSort on a list of Info entries. The InfoMerge function merges two already sorted lists, combining Info entries that correspond to the same point, adding up the live-neighbour counts, and using logical OR to combine the liveness flags. The result of sorting is a list of entries corresponding to previously live cells or neighbours of previously live cells, with their live-neighbour counts. Such a use of merge-sort to combine together corresponding entries in a list is a useful functional programming technique.

:: InfoMerge InfoList InfoList -> InfoList;
   InfoMerge [] l -> l;
   InfoMerge l [] -> l;
   InfoMerge p:[u:(x,y,b,i)|t] q:[v:(x',y',b',j)|t']
        -> ls:[u | InfoMerge t q], IF < y y'
        -> gt:[v | InfoMerge p t'], IF > y y'
        -> ls, IF < x x'
        -> gt, IF > x x'
        -> [(x, y, OR b b', + i j) | InfoMerge t t'];

:: InfoSort InfoList -> InfoList;
   InfoSort l -> InfoSortAux (Len l) l;

The auxiliary function for the sorting process takes the length of the list as an argument, splits the list into two halves, sorts them recursively, and merges the results:

:: InfoSortAux !INT InfoList -> InfoList;
   InfoSortAux n l -> l, IF <= n 1
                   -> InfoMerge (InfoSortAux n2 (Take n2 l)) 
                                (InfoSortAux (- n n2) (Drop n2 l)),
                      n2: / n 2;

The DoRule function applies the rules of the Game of Life to the sorted InfoList to obtain the new list of points after one step of the game. The new live cells are those that were live with two or three live neighbours, or were dead with precisely three live neighbours:

:: DoRule InfoList -> PntList;
   DoRule [] -> [];
   DoRule [(x,y,b,i) | t] 
        -> [(x,y) | DoRule t], IF = 3 i || (b && = 2 i)
        -> DoRule t;

Combining StepInfo, InfoSort, and DoRule gives the step function which takes a list of points and gives the new list after one step:

:: Step !PntList -> PntList;
   Step l -> DoRule (InfoSort (StepInfo l));

The lifepoint definition module lists the exported types and functions, i.e. not including the auxiliary functions, or the Info types and operations, whose sole purpose was the definition of Step. It is stored in the file lifepoint.dcl.

UpTop Level

BackSome Miscellaneous Functions

DCLlifepoint.dcl

ForwardA Simple CLEAN Program