IM204 Coursework 1: The Game Of Life

! ----------------------------------------------------------------------------
! IM204: Declarative Programming                           Lecturer: S.Danicic
! Coursework 1                  The Game of Life                 Submission #2
! ----------------------------------------------------------------------------
! Eamonn Martin  -  BSc (hons) Computing                         ID: 96/D59682
! ----------------------------------------------------------------------------

! Executable Functions:
!   generate     - returns the next generation of a grid.
!   gennum       - returns a specific generation number:
!                  gennum(grid, 1) = generate(grid)
!   genseq       - returns a sequence of generations:
!                  genseq(grid, 1) = [ generate(grid) ]

! The grid is a list of lists of alphas.  The actual values for the occupied
! and unoccupied states of each alpha-cell are determined by the cellstate
! function, which is defined to return true (occupied) or false (unoccupied).

! There may be any number of rows and columns in the grid but it must be a
! rectangle (ie. the same number of elements in each row).

! If the truval-constant 'wrap' is true, the edge (and corner) cells are
! considered to be neighbours of cells at the opposite edge.

! ----------------------------------------------------------------------------

! Return the number of items in a list
dec count : list (alpha) -> num ;
--- count ( [] ) <= 0;
--- count ( n :: m ) <= 1 + count(m);

! Return true if n is within the range 0..r-1
infix inrange : 8 ;
dec inrange : num # num -> truval ;
--- n inrange r <= if (n < 0) or (n >= r) then false else true;

! Grid-wrap is enabled if wrap is true
dec wrap : truval ;
--- wrap <= true;

! Define a generic grid structure
type state == alpha;
type row   == list (state);
type grid  == list (row);

! Define the cell state-values
dec cellstate : truval -> state ;
--- cellstate ( s ) <= if s then true else false;

! Return state-values for occupied and unoccupied cells
dec occupied, unoccupied : state ;
--- occupied <= cellstate(true);
--- unoccupied <= cellstate(false);

! Return 1 if cell-value is occupied, otherwise 0
dec cellvalue : state -> num ;
--- cellvalue ( s ) <= if (s = occupied) then 1 else 0;

! Return a cell-value for a cell in a row (1 or 0)
dec _element : num # row -> num ;
--- _element ( x, [] ) <= 0;
--- _element ( x, n :: m ) <=
    if (x > 0) then _element(x-1, m) else cellvalue(n);

! Bound element index within the number of row-elements
dec element : num # row -> num ;
--- element ( x, [] ) <= 0;
--- element ( x, l ) <=
    if not (wrap or (x inrange count(l))) then 0
    else _element(if wrap then x mod count(l) else x, l);

! Return the value of cell x,y in a grid
dec _cell : num # num # grid -> num ;
--- _cell ( x, y, [] ) <= 0;
--- _cell ( x, y, n :: m ) <=
    if (y < 1) then element(x, n) else _cell(x, y-1, m);

! Bound cell-row index within the number of grid-rows
dec cell : num # num # grid -> num ;
--- cell ( x, y, [] ) <= 0;
--- cell ( x, y, l ) <=
    if not (wrap or (y inrange count(l))) then 0
    else _cell(x, if wrap then y mod count(l) else y, l);

! Return the number of neighbours of a cell
dec neighbours : num # num # grid -> num ;
--- neighbours ( x, y, [] ) <= 0;
--- neighbours ( x, y, l ) <=
    cell(x-1,y-1,l) + cell(x,y-1,l) + cell(x+1,y-1,l) +
    cell(x-1,y  ,l)          +        cell(x+1,y  ,l) +
    cell(x-1,y+1,l) + cell(x,y+1,l) + cell(x+1,y+1,l) ;

! Return the new state of a cell in state with num neighbours
dec isalive : state # num -> state;
--- isalive ( s, n ) <=
    if ((s /= occupied) and (n = 3)) then occupied
    else if ((s = occupied) and (n > 1) and (n < 4)) then occupied
    else unoccupied;

! Generate the cells for a row
dec gencells : num # num # grid # row -> row ;
--- gencells ( x, y, l, [] ) <= [];
--- gencells ( x, y, l, n :: m ) <=
    [isalive(n, neighbours(x, y, l))] <> gencells(x+1, y, l, m);

! Generate the rows for the grid
dec genrows : num # grid # grid -> grid ;
--- genrows ( y, l, [] ) <= [];
--- genrows ( y, l, n :: m ) <=
    [ gencells(0, y, l, n) ] <> genrows(y+1, l, m);

! ----------------------------------------------------------------------------

! Generate the next generation
dec generate : grid -> grid ;
--- generate ( [] ) <= [];
--- generate ( l ) <= genrows(0, l, l);

! Generate a specific generation number
dec gennum : grid # num -> grid ;
--- gennum ( [], n ) <= [];
--- gennum ( l, n ) <=
    if (n < 1) then l else gennum(generate(l), n-1);

! Generate a sequence of generations
dec genseq : grid # num -> list (grid) ;
--- genseq ( [], n ) <= [];
--- genseq ( l, n ) <=
    if (n < 1) then []
    else [ generate(l) ] <> genseq(generate(l), n-1);

! ----------------------------------------------------------------------------

! Test Data
dec testgrid : grid ;
--- testgrid <= [[unoccupied,  occupied,  occupied,  occupied,unoccupied],
                 [unoccupied,  occupied,unoccupied,  occupied,unoccupied],
                 [unoccupied,unoccupied,  occupied,unoccupied,unoccupied],
                 [unoccupied,  occupied,unoccupied,  occupied,unoccupied],
                 [unoccupied,  occupied,  occupied,  occupied,unoccupied]];

! Test Functions
dec testseq : list (grid) ;
--- testseq <= genseq(testgrid, 4);

dec testnum : list (grid) ;
--- testnum <= genseq(gennum(testgrid, 2), 2);

! Shorthand
dec t, f : truval ;
--- t <= true;
--- f <= false;

! END