Programming Issues, Loop Invariants

Tom Kelliher, CS23

February 7, 1996

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

fact = 1;
for (i = 2; i <= n; i++)
   fact *= 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
2. A function which finds the sum of the first five positive values in an integer array with n elements
3. A function which iteratively performs binary search