Program Documentation

Tom Kelliher, CS23

Feb. 7, 1997

Announcements:

1. Keystone accounts: I need your Novell userids.

2. Pointers to C/C++ reviews (lecture outlines):
   1. Basics: CS18 weeks 1 and 2.

   2. Interactive I/O: CS17 February 21.

   3. File I/O: CS17 May 3 and 6.

   4. Structures: CS18 March 4 and 11.

   5. Strings: CS17 May 13.

   6. Memory model and recursion: CS18 weeks 3 and 4.

   7. Pointers: CS18 April 22 and 29.

   8. Classes: March 15, 18, and 20. April 24. May 6.

3. You should be able to do all of the CS18 homework problems, with the exception of those problems involving recursion, dynamic memory allocation, and classes. If you cannot, you should let me know by Tuesday.

Outline:

1. Acceptable program documentation.

2. Pre- and post-conditions.

3. Loop invariants.

``Key'' Programming Issues

Modularity

Aids comprehension, debugging, modification; eliminates redundancy

Modifiability

No ``magic numbers'' --- use NAMED CONSTANTS.

Ease of use

Don't leave user in the dark.

Fail-safe programming

Always validate inputs.

Invariants, pre- and post-conditions (discussed later)

Style

Very personal subject.

Issues:

1. Documentation
2. Documentation
3. Documentation
4. Identifier naming conventions
5. Sane Code structure
6. Code structure conventions
7. Don't litter the global namespace with variables
8. Lots of functions.
9. Clarity of reference parameters vs. pointer parameters

Debugging

1. Symbolic debuggers
2. Use of the preprocessor in adding/ignoring debugging code:

   #ifdef DEBUGGING
   cout << "Debugging was compiled-in." << endl;
   #endif
   

Pre- and Post-Conditions

Two purposes:

• An aid in design verification
• Very good form of function documentation

A contract between caller (client) and callee (server)

Pre-condition states what must be true upon function entry

Post-condition states what will be true upon exit --- describing the transformation accomplished

Example:

/**********************************************************************

sort

pre-condition: the int array data contains integer values in its first
numElems locations

post-condition: the first numElems values of data are sorted into
ascending order

**********************************************************************/

void sort(int data[], int numElems)
{
   ...
}

What would the pre- and post-conditions be for:

int linkedListInsert(LinkedList& l, int position, ListItem item);

Loop Invariants

Four characteristics:

1. Must be true upon entry into the loop
2. Execution of the loop body must preserve the invariant
3. Invariant must capture the correctness and the meaning of the loop
4. Loop must terminate

Consider the code:

const int SIZE = 100;
int data[SIZE];
int i;
int sum;

// stuff to initialize data

sum = 0;
for (i = 0; i < SIZE; i++)
   sum += data[i];

cout << "Sum: " << sum << endl;

Three more examples:

prod = 1;
for (i = 2; i <= n; i++)
   prod *= n;             // careful!!

void SelectionSort(dataType A[], int N)
{
   for (int Last = N-1; Last >= 1; --Last)
   {
      // select largest item in A[0..Last]
      int L = IndexOfLargest(A, Last+1);

      // swap largest item A[L] with A[Last]
      Swap(A[L], A[Last]);
   }  // end for
}  // end SelectionSort

int IndexOfLargest(const dataType A[], int Size)
{
   int IndexSoFar = 0;  // index of largest item found so far

   for (int CurrentIndex = 1; CurrentIndex < Size;
                              ++CurrentIndex)
   {
      if (A[CurrentIndex] > A[IndexSoFar])
         IndexSoFar = CurrentIndex;
   }  // end for

   return IndexSoFar;  // index of largest item
}  // end IndexOfLargest

Student Exercises

Determine pre- and post- conditions and loop invariants for the following:

1. A function which computes the sum of the first n elements of the Fibonacci sequence

   int fibSum(int n)
   {
      int fib1 = 0;   // First number in Fibonacci sequence.
      int fib2 = 1;   // Second number in Fib. sequence.
      int fib3;
      int i;
      int sum = 0;
   
      for (i = 2; i <= n; ++i)
      {
         fib3 = fib2 + fib 1;   // Generate next number in sequence.
         fib1 = fib2;           // "Move up" one sequence number.
         fib2 = fib3;
         sum += fib3;
      }
   
      return sum;
   }
   

2. A function which finds the sum of the first five positive values in an integer array with n elements

   int sumFive(int array[], int n)
   {  int count;   // # of positive elements found
      int i;       // loop counter
      int sum      // sum of positive elements
   
      for (count = i = sum = 0; i < n && count < 5; i++)
         if (array[i] > 0)
         {  count++;
            sum += array[i];
         }
   
      if (count == 5)
         return sum;
      else
         return -1;   // Return garbage value if we can't find five
                      // positive values.
   }
   

3. A function which iteratively performs binary search

   int binSearch(int data[], int n, int item)
   {
      int first = 0;
      int last = n - 1;
      int mid
   
      while (first < last)
      {
         mid = (first + last) / 2;
   
         if (data[mid] == item)
            return mid;
         else if (data[mid] < item)
            first = mid + 1;
         else
            last = mid - 1;
      }
   
      return -1;
   }