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`.