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

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

```