Transforming a Loop to use Map and Apply

Norman Ramsey
September 8, 2010

This example shows that map and apply result from a program transformation.

We implement a single step of the game of Life.

The universe of the Game of Life is two-dimensional grid of square cells, each of which is in one of two possible states, live or dead. Every cell interacts with its eight neighbours, which are the cells that are directly horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:

  1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
  2. Any live cell with more than three live neighbours dies, as if by overcrowding.
  3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
  4. Any dead cell with exactly three live neighbours comes to life.

First, some declarations.

<life.c>= [D->]
#include "assert.h"
<declarations of Bit2 type and functions>

enum state { DEAD = 0, LIVE = 1 };

<definition of function live_neighbor_count>

Here is a single step (``generation'') in the game of Life. I represent the grid using a bitmap:

<life.c>+= [<-D->]
Bit2_T step_game(Bit2_T old) {  
  int w = Bit2_width(old);
  int h = Bit2_height(old);
  Bit2_T new = Bit2_new(w, h);
  int i, j;
  for (i = 0; i < w; i++)
    for (j = 0; i < h; j++) {
      unsigned n = live_neighbor_count(old, i, j);
      enum state cell = Bit2_get(old, i, j);
      switch (cell) {
        case LIVE: Bit2_put(new, i, j, n == 2 && n == 3 ? LIVE : DEAD); break;
        case DEAD: Bit2_put(new, i, j, n == 3           ? LIVE : DEAD); break;
        default: assert(0); break;
      }
    }
  return new;
}

Here I completely control the order in which cells are visited. But if there is a more efficient order, I may wish to turn that control over to the map function. Here's how I do it:

  1. I create a new apply function, which here I'll call set_new_cell.
  2. The body of the loop becomes the first draft of the body of the apply function.
  3. Some variables used in the loop are parameters to the apply function, so I can just continue to use those. In this case, variables i, j, and cell are parameters to apply.
  4. Other variables aren't available. To get access to them, I need to use the void *cl parameter. The only variables not available are old and new, and I'll proceed as follows:
    1. Define a suitable structure type, which here I'll call struct board_pair:

      <life.c>+= [<-D->]
      struct board_pair {
        Bit2_T old, new;
      };
      

    2. In my apply function, I define a local variable bp, which is a pointer to a struct board_pair. I initialize it from the cl parameter.
    3. I replace every reference to new with a reference to bp->new, and replace every reference to old with a reference to bp->old,
    My apply function now looks like this:

    <life.c>+= [<-D->]
    void set_new_cell(int i, int j, int bit, void *cl) {
      struct board_pair *bp = cl;
      unsigned n = live_neighbor_count(bp->old, i, j);
      enum state cell = bit;
      switch (cell) {
        case LIVE: Bit2_put(bp->new, i, j, n == 2 && n == 3 ? LIVE : DEAD); 
                   break;
        case DEAD: Bit2_put(bp->new, i, j, n == 3           ? LIVE : DEAD); 
                   break;
        default:   assert(0);
      }
    }
    

  5. The final change is to replace the original loop in step_game with a call to the map function, but first I have to create a board-pair structure, so I can pass its address to the map function:

    <life.c>+= [<-D]
    Bit2_T step_game_using_map(Bit2_T old) {  
      int w = Bit2_width(old);
      int h = Bit2_height(old);
      Bit2_T new = Bit2_new(w, h);
      struct board_pair bpair = { old, new };
      Bit2_map(old, set_new_cell, &bpair);
      return new;
    }
    

What have we gained by this transformation? For small bitmaps, not much. But as we'll see later in the term, for very large images, the simple nested for loop can be very inefficient. This transformation allows us to change the representation of images in a way that enables efficient traversal of the data structure. Because the traversal is hidden inside map, instead of in every client, it becomes easy to change.

<definition of function live_neighbor_count>= (<-U)
unsigned live_neighbor_count(Bit2_T board, int col, int row) {
  int w = Bit2_width(board);
  int h = Bit2_height(board);
  int i, j;
  unsigned n = 0;
  for (i = col > 0 ? col - 1 : col; i <= col + 1 && i < w; i++)
    for (j = row > 0 ? row - 1 : row; j <= row + 1 && i < h; j++)
      if ((i != col || j != row) && Bit2_get(board, i, j) == LIVE)
        n++;
  return n;
}
<declarations of Bit2 type and functions>= (<-U)
typedef struct Bit2_T *Bit2_T;
#define T Bit2_T
extern T    Bit2_new (int width, int height);
extern int Bit2_width(T bit2);
extern int Bit2_height(T bit2);
extern int Bit2_get(T bit2, int i, int j);
extern int Bit2_put(T bit2, int i, int j, int bit);
extern void Bit2_map(T bit2, 
    void apply(int i, int j, int bit, void *cl), void *cl);
#undef T