Answers to tutorial exercises #7: Functions, pointers

Before this tute, please have a look at the wikipedia article on
"Conway's game of life", and compile and run the program conway.c in
/home/subjects/20006/local/tutorials, whose source code is shown in the last
question for this tutorial.

QUESTION 1
Walk through the execution of the following program, keeping track of the
values of all the variables. For each reference to the variable x, say
*which* of the several xs in the program is being referred to.

Either before or after the tutorial, try compiling this program (which is
available as /home/subjects/20006/local/tutorials/visibility.c) with gcc and
with gnuc.

int x = 3;

int f(int x)
{
    int y;

    x++;
    y = x;
    return x + y;
}

int g(void)
{
    return f(x + 1) + f(x + 2);
}

int h(int z)
{
    int x;

    x = z * 2;
    return x;
}

int main(void)
{
    printf("%d\n", g());
    printf("%d\n", h(x));
    printf("%d\n", x);
    return 0;
}

ANSWER
In g, the only x visible is the global variable, which is initialized to 3.

The call to g() first calls f(x + 1), i.e. f(4). This initializes the formal
parameter x of f to 4. The statement x++ increments this formal parameter
to 5, so y is assigned 5 and f returns 10.

The call to g() next calls f(x + 2), i.e. f(5). This initializes the formal
parameter x of f to 5. The statement x++ increments this formal parameter
to 6, so y is assigned 6 and f returns 12.

g then returns 10 + 12 = 22, which main prints.

The call to h invokes h with the actual parameter 3, since the global variable
x has not been updated up to now. H has its own local variable x, so it cannot
refer to the global variable. This local variable is assigned 6 (since z = 3),
and that is what h returns for main to print.

Since the global variable x still has not been updated, main then prints 3.

gcc compiles this program without complaint, but gnuc generates two warnings:
visibility.c:12: warning: declaration of 'x' shadows a global declaration
visibility.c:10: warning: shadowed declaration is here
visibility.c: In function `h':
visibility.c:28: warning: declaration of 'x' shadows a global declaration
visibility.c:10: warning: shadowed declaration is here

QUESTION 2
Last week's workshop exercises asked you to write a program to test your
implementation of the functions that implement the push and pop operations
on stacks.

This program involved several variables, including at least these:

- One variable, stack, is the array that implements the stack.
- One variable, sp, holds the stack pointer.
- One variable holds the number that you read in from the user.

For each of these variables, say whether it should be a global variable
or a local variable, and if the latter, which function it should be local to.
Give your reasons.

ANSWER
Both the push and the pop functions must be able to refer to both the stack
and the stack pointer, so these two variables cannot be local to either
function; they must be global.

The variable that holds the number that main reads in and tests whether
it is positive or negative needs to be accessible from main, but not from
anywhere else. If it were a global variable and therefore accessible from
functions other than main, any such accesses would be bugs. The best way to
prevent such bugs is to make this variable local to main.

In general, unless there is a compelling reason to make a variable global,
it should be kept local to the only function that uses it. In fact, if a
variable is only used e.g. in one arm of an if-then-else, then it should be
declared in the block that forms that arm.

QUESTION 3
Given an array of floats "a" whose number of elements is stored in the
variable "n", you can compute the mean and standard deviation of the numbers
in the array with this code:

	sum = 0.0;
	sum_sq = 0.0;

	for (i = 0; i < n; i++) {
		sum += a[i];
		sum_sq += a[i] * a[i];
	}

	mean = sum / n;
	stddev = sqrt((sum_sq / n) - mean * mean);

If you had to write a function to compute the mean and standard deviation
of the numbers in an array, you could use this code as the (bulk of)
the function body, but how would you declare the function, and how would you
return its results?

You should ensure that your function works even if n = 0.

ANSWER
One function signature would be

int compute_mean_stddev(float *mean_ptr, float *stddev_ptr)

The comment describing the function would say something like this:

	Given the array "a" of which the first "n" elements are meaningful,
	attempt to compute the mean and the standard deviation of those
	elements. If the attempt is meaningful (because n > 0), then assign
	the mean to *mean_ptr and the standard deviation to *stddev_ptr, and
	return true; otherwise (if n <= 0) return false.

This assumes that "a" and "n" are global variables. The function would be
much more general if it worked for all arrays, not just this one, so a better
signature would be

int compute_mean_stddev(float a[], int n, float *mean_ptr, float *stddev_ptr)

The comment above still works.

QUESTION 4
Write a function that reads a line of input into a buffer (a character array),
and then checks whether the contents of the line fits one particular pattern of
dates: a day within a month, the 3-letter abbreviation of the name of a month,
and a four-digit year number. For example,

	2 Sep 1945
	20 Jul 1969
	1 Jan 2001

all fit this pattern.

Your function should return an indication of whether the input line matches
this pattern. If it does, it should also return three integers: the day number
within the month, the number of the month (january being month 1) and the year
number.

You should decide on every detail of the interface between the function and
its callers, including the comment describing the function. However, you do
NOT need to flesh out all the details in the body of the function, at least
not during the tutorial. However, you may wish to consider how to use
the values returned by the function to figure out *which* day of its year
the provided date represents, with 1 Jan being day 1 and 31 Dec being either
day 365 or day 366, depending on whether the year is a leap year.

ANSWER
Here is one possible program that does what this question asks you to do.
However, please note that the important point here is NOT the final code
of the program, but the PROCESS you follow in order to arrive at it.

// vim: ts=4 sw=4 et

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define FALSE 0
#define TRUE  1

const int   nonleap_month_lengths[12] =
                { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
const int   leap_month_lengths[12] =
                { 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

extern  const int   *get_month_lengths(int year);
extern  int         read_and_check_date(int *day_in_month_ptr, int *month_ptr,
                        int *year_ptr);

const int *get_month_lengths(int year)
{
    const int   *month_lengths;

    if ((year % 400) == 0) {
        month_lengths = leap_month_lengths;
    } else if ((year % 100) == 0) {
        month_lengths = nonleap_month_lengths;
    } else if ((year % 4) == 0) {
        month_lengths = leap_month_lengths;
    } else {
        month_lengths = nonleap_month_lengths;
    }

    return month_lengths;
}

int read_and_check_date(int *day_in_month_ptr, int *month_ptr, int *year_ptr)
{
    char        buf[80];
    int         len;
    int         c;
    int         i;
    int         day_in_month;
    int         month_start_offset;
    int         month;
    int         year;
    const int   *month_lengths;

    len = 0;
    while ((c = getchar()) != EOF && c != '\n') {
        if (len > 79) {
            return FALSE;
        }

        buf[len] = c;
        len++;
    }
    buf[len] = '\0';

    i = 0;
    while (buf[i] != '\0' && isspace(buf[i])) {
        i++;
    }

    day_in_month = 0;
    while (buf[i] != '\0' && !isspace(buf[i])) {
        if (isdigit(buf[i])) {
            day_in_month = day_in_month * 10 + buf[i] - '0';
        } else {
            return FALSE;
        }

        i++;
    }

    while (isspace(buf[i])) {
        i++;
    }

    month_start_offset = i;
    while (buf[i] != '\0' && !isspace(buf[i])) {
        if (!isalpha(buf[i])) {
            return FALSE;
        }

        i++;
    }

    if (i != month_start_offset + 3) {
        return FALSE;
    }

    if (strncmp(&buf[month_start_offset], "Jan", 3) == 0) {
        month = 1;
    } else if (strncmp(&buf[month_start_offset], "Feb", 3) == 0) {
        month = 2;
    } else if (strncmp(&buf[month_start_offset], "Mar", 3) == 0) {
        month = 3;
    } else if (strncmp(&buf[month_start_offset], "Apr", 3) == 0) {
        month = 4;
    } else if (strncmp(&buf[month_start_offset], "May", 3) == 0) {
        month = 5;
    } else if (strncmp(&buf[month_start_offset], "Jun", 3) == 0) {
        month = 6;
    } else if (strncmp(&buf[month_start_offset], "Jul", 3) == 0) {
        month = 7;
    } else if (strncmp(&buf[month_start_offset], "Aug", 3) == 0) {
        month = 8;
    } else if (strncmp(&buf[month_start_offset], "Sep", 3) == 0) {
        month = 9;
    } else if (strncmp(&buf[month_start_offset], "Oct", 3) == 0) {
        month = 10;
    } else if (strncmp(&buf[month_start_offset], "Nov", 3) == 0) {
        month = 11;
    } else if (strncmp(&buf[month_start_offset], "Dec", 3) == 0) {
        month = 12;
    } else {
        return FALSE;
    }

    while (isspace(buf[i])) {
        i++;
    }

    year = 0;
    while (buf[i] != '\0' && !isspace(buf[i])) {
        if (isdigit(buf[i])) {
            year = year * 10 + buf[i] - '0';
        } else {
            return FALSE;
        }
        
        i++;
    }

    month_lengths = get_month_lengths(year);
    if (1 <= day_in_month && day_in_month <= month_lengths[month - 1]) {
        *day_in_month_ptr = day_in_month;
        *month_ptr = month;
        *year_ptr = year;
        return TRUE;
    } else {
        return FALSE;
    }
}

int main(void)
{
    int         day;
    int         month;
    int         year;
    int         day_in_year;
    int         i;
    const int   *month_lengths;

    while (read_and_check_date(&day, &month, &year)) {
        printf("date is ok: %d %d %d\n", day, month, year);

        month_lengths = get_month_lengths(year);

        i = 0;
        day_in_year = 0;
        while (i < month - 1) {
            day_in_year += month_lengths[i];
            i++;
        }
        day_in_year += day;

        printf("day in year: %d\n", day_in_year);
    }

    printf("date is not ok\n");
    return 0;
}

Note that the first example date, 2 Sep 1945, is the day when World War 2
officially ended, while the second, 20 Jul 1969, is the day when human beings
first set foot on the moon.

QUESTION 5
Read and then discuss the following program, which plays Conway's game of life.
Some of the things you can talk about are

- How does the program work?
- What do the individual functions do?
- Is the overall task of each individual function documented properly?
- Is the detailed operation of each individual function documented properly?
- How could any of this code be improved?

// vim: ts=4 sw=4 et
// Conway's Game of Life
// Author: Matt Giuca

#include <stdio.h>
#include <time.h>

#define BOARD_WIDTH  40
#define BOARD_HEIGHT 24

extern  void    showboard(void);
extern  int     count_neighbours(int x, int y);
extern  void    step(void);
extern  void    reset(void);

char board[BOARD_HEIGHT][BOARD_WIDTH] = {
    "                                        ",
    "                                        ",
    "     X  X                               ",
    "         X                              ",
    "     X   X                              ",
    "      XXXX                              ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
    "                                        ",
};

void showboard(void)
{
    int row, col;

    for (row = 0; row < BOARD_HEIGHT; row++) {
        for (col = 0; col < BOARD_WIDTH; col++) {
            putchar(board[row][col]);
        }
        putchar('\n');
    }
}

// Return the number of live neighbours of the cell at (x,y).
int count_neighbours(int x, int y)
{
    int row, col;
    int count;

    count = 0;
    for (row = y - 1; row <= y + 1; row++) {
        for (col = x - 1; col <= x + 1; col++) {
            // A cell is not its own neighbour.
            if (row == y && col == x) {
                continue;
            }

            // Check whether the neighbour exists on the board.
            if (0 <= row && row < BOARD_HEIGHT &&
                0 <= col && col < BOARD_WIDTH)
            {
                if (board[row][col] != ' ') {
                    count++;
                }
            }
        }
    }

    return count;
}

// Perform one "step" of the game.
// Updates board to reflect the successor state of board.

void step(void)
{
    char    next_board[BOARD_HEIGHT][BOARD_WIDTH];
    int     row, col;
    int     neighbours;

    for (row = 0; row < BOARD_HEIGHT; row++) {
        for (col = 0; col < BOARD_WIDTH; col++) {
            neighbours = count_neighbours(col, row);
            if (board[row][col] != ' ') {
                /* Alive */
                if (neighbours < 2 || neighbours > 3) {
                    /* Dies */
                    next_board[row][col] = ' ';
                } else {
                    /* Lives */
                    next_board[row][col] = 'X';
                }
            } else {
                /* Dead */
                if (neighbours == 3) {
                    /* Born */
                    next_board[row][col] = 'X';
                } else {
                    /* Stay dead */
                    next_board[row][col] = ' ';
                }
            }
        }
    }

    // Copy next_board back to board.
    for (row = 0; row < BOARD_HEIGHT; row++) {
        for (col = 0; col < BOARD_WIDTH; col++) {
            board[row][col] = next_board[row][col];
        }
    }
}

void reset(void)
{
    printf("\x1b[H");
}

int main(void)
{
    int iterations;

    system("clear");
    iterations = 0;
    while (iterations < 10000) {
        iterations++;
        reset();
        showboard();
        step();
        // Sleep for a second.
        sleep(1);
    }

    return 0;
}

ANSWER
This is a discussion question, so there cannot be a single correct answer,
but here are some points that the discussion should cover.

Most functions of the program access the board via the global variable named
"board", whose dimensions are given by the symbolic constants BOARD_WIDTH and
BOARD_HEIGHT.

- The showboard function prints the board.
- The count_neighbours function returns the number of neighbours of the given
  coordinate that are currently occupied.
- The step function figures out, for each square of the board, whether that
  square should be occupied in the next generation. If it updated the board
  after each such decision, the count of the occupied neighbours of the
  neighbour cells that have not been processed yet would be inaccurate,
  which is why step doesn't update board directly. Instead, it calculates
  the contents of the board in the next generation into a local variable,
  next_board. Only after all calculations that need the old contents of the
  board have been completed does step copy the next board to the actual board.
- If you observe the behavior of this program, you will see that it starts by
  clearing the screen (which is done by the call to the "system" function),
  drawing the initial board, and then redrawing the board at one-second
  intervals. The reset function moves the cursor back to the top left of the
  screen, so that the showing of the next board will overwrite the board before
  it. How the reset function does this is not documented at all, much less
  properly.