Reviewing 'C' - Part 3

A function is like a container that allows for the reuse of a given code block.  But this is only half the story.  Related functions are often found in a so-called library.  The 'C' language itself provides no input or output capability.  Input and output operations can be handled by functions in the Standard Input-Output Library.  In addition, the 'C' language only provides basic math capability.  The 'C' math library provides a collection of advanced math functions, including a square root function.

This part reviews topics directly related to the use of functions.  The use of prototypes are outlined.  Example uses of prototypes are presented in example programs.  The notions of pass-by-value, storage class, and scope are outlined.  An iterative solver is presented as a more realistic example.  The concepts of arrays and pointers are also reviewed.  Finally, an example of recursion is presented.

Functions and Prototypes

Each module in a 'C' program is separately compiled, starting at the top.  Once compiled, the linker connects each function call to its corresponding function.  Because of this, it is possible for a compiler to encounter a function call before the function itself is declared.  To prepare for calling a function, the compiler writes code that forms what is called a stack-frame.  The name is descriptive as the code uses the stack to pass values into the function.  Obviously, to produce this code the compiler needs to know what arguments the function expects and what it returns. 

A function prototype provides a summary description of the expected arguments and type returned.  A function prototype has the same form as the declaration of a function, however a prototypes ends with a semicolon.  The following is the outline. 

type_returned FUNCTION_NAME(type1 in1, type2 in2, ..., typen inn);

Function prototypes are placed at the top of a module or in a so called header file and are referenced using an #include directive.  The file stdio.h referred to in the example programs actually provides the necessary prototypes for the functions in the standard input-output library. 

In compiling a function call, the compiler does not need to know how the called function is implemented.  The compiler just creates the stack frame and later, the linker associates the call with the called function.  In writing 'C' programs, besides using the functions that you write, you will also use pre-written functions like those in the standard input-output library or math library.  For various reasons, such as the need for speed, libraries are sometimes written in a programming language other than 'C', such as assembly language. 

Formal Parameters and Passing by Value

Each programming language defines a convention regarding parameter passing.  In 'C', values passed into a function, called the formal parameters are copied from the calling arguments.  It is important to realize that 'C' doesn't pass variables into functions, but rather the values themselves are copied into the formal parameters.  The following example calls a function that calculates the sum of integers from one to a given value and then returns the sum.

/******************************************
 * AddInts.c 
 * Illustrates pass-by-value concept
 *****************************************/
#include <stdio.h>
int AddInts(int NN);

int main()
{
  int Sum, N = 5;

  printf("N = %d\n",N);
  Sum = AddInts( N );
  printf("N = %d sum = %d\n", N, Sum);

  return 0;
}

/******************************************
 * AddInts()
 * Add up integers 1 to NN
 *****************************************/
int AddInts(int NN)
{
  int sum = 0;

  while (NN > 0) {
    sum += NN;
    --NN;
  }
  return sum;
}

Because 'C' passes formal parameters by value, any change to a formal parameter is only seen in the function itself.  The corresponding variable in the calling statement is not changed.  While it is certainly possible in a function to change the value of a formal parameter, the formal parameters are all discarded when the function returns.  To make the point clear, predict the output of the following program. 

/*********************************
 * exarg1.c - Krista Hill
 * Argument and parameter example
 *********************************/
#include <stdio.h>
void swap(int x1, int x2);

int main()
{
  int a = 1, b = 2;
  swap(a,b);
  printf("a = %d b = %d\n",a,b);
}

void swap(int x1, int x2)
{
  int x3;
  x3 = x1;
  x1 = x2;
  x2 = x3;
}

While the values in x1 and x2 certainly are swapped, the program has no mechanism to propagate the values back to a or b.  Hence the values in a and b remain unchanged.  We will soon investigate a way out of this dilemma.

Storage Class and Scope

int ival = 4;

Static variables are allocated memory once and assigned an initial value only when the program begins execution.  In the example below, the keyword static is used to to qualify a variable as static.

static int maxval = 12;

Static and automatic type variables differ in the way they are allocated.  Automatic type variables are allocated on the stack.  When a function exits the allocation no longer exists, and any reference to it is not valid.  Static variables are allocated in one of two possible memory areas, depending on whether or not they are initialized. 

The notion of scope relates to the visibility of variables and other named items.  Variables defined inside a function are visible only inside the function itself.  Scope is very useful, in writing a function is it not necessary to memorize the names of variables in other functions.  A large program may literally have thousands of variables and the repeat use of a name is inevitable.  The notion of scope guarantees that each local variable a unique.

Global Variables
Variables declared outside a function are said to be global variables.  Global variables are allocated when the program initializes, and are initialized once.  The scope of global variables extends throughout the whole module.  The keyword extern tells the compiler to not allocate the global and assume that its already allocated elsewhere.  Hence, extern allows the scope of a global to extend to another module. 

The keyword static has special meaning with global variables, different than with local variables.  The keyword static restricts the scope of global variables, to the module in which the global is declared, causing the global to be considered private to that module.  This restriction in helpful in avoiding name conflicts between global variables in different modules.

Square Root Example

The following example illustrates the use of a function named mysqrt(), but first a comment about macros.  The lines starting with the keyword #define are preprocessor commands, each defines a macro.  A macro performs simple text replacement, replacing the use of the macro, with its definition, replacing argument given in the macro definition.  The first macro defines an absolute value operation.  The second macro squares a value.  Remember that a macro looks like a function, but is really just a simple text replacement. 

/*************************************************************
 * mysqrt.c - Krista Hill
 * Calculate and displays square roots, page 54 of Van Sickle
 ************************************************************/
#include <stdio.h>
#define  abs(arg)    (((arg) >= 0) ? (arg) : -(arg))
#define  square(arg) (arg)*(arg)

double mysqrt(double val);

int main(void)
{
  int ix;
  double val;

  printf("Table of square roots\n");
  printf(" ix v = sqrt(ix) v^2\n");
  for (ix = 1; ix < 11; ix++)
    {
      val = mysqrt( (double)ix );
      printf(" %3d %7.4f %8.4f\n",ix, val, square(val));
    }
  return 0;
}

/********************************************************
 * my square root
 * Uses an iterative solver to estimate the square root
 *******************************************************/
double mysqrt(double val)
{
  double c, x1 = 1, x2 = 1;

  do {
    x1 = x2;
    x2 = (x1 + val/x1)/2;
    c = x1 - x2;
  } while (abs(c) >= 1.0e-8);
  return x2;
}

Note the automatic variables used in the function mysqrt().  The values x1 and x2 are used to store successively better estimates of the square root.  The variable c represents the difference between estimates.  Since x1 and x2 are automatic, the initial estimate always equals one. Take a moment to consider how the expression is evaluated. 

x2 = (x1 + val/x1)/2;

The number 2 is an integer, but the other values in this expression are of type double.  To evaluate the expression, the number 2 is first converted to type double, this operation is called promotion.  Such details are neatly handled by the compiler. 

Make note of the use of the function prototype, this allows main() to call mysqrt() before the function itself is declared.  To use the square-root function sqrt() in the math library instead, first include the #include <math.h> preprocessor command to include the math.h file and inform your tool chain that it needs to access the math library.

Arrays

long rd[10];	// an uninitialized array of ten elements
float vals[] = {1.1, 2.2, 3.6};	// an array of three elements
float list[5] = {1.0};	// an array of five elements

Square brackets have a second use outside that of the declaration of the size of an array.  Square brackets are used to refer to individual elements in an array. The first element in an array is always numbered zero, thus vals[0] and vals[2] equal 1.1 and 3.6, respectively. 

A special comment applies to how an array reference is handled in calling an function.  The array itself isn't copied, but rather the reference to the array is copied.  Copying a reference is handled by copying a pointer, which we discuss in greater depth later.  For now, understand that because the array is allocated once, changes made from inside the function are seen by the calling code.  The following example illustrates the use of a function that passes an array reference. 

/************************************************
 * modax.c - Krista Hill (kmhill@hartford.edu)
 * Illustrates how an array reference is passed 
 ***********************************************/
#include <stdio.h>
#define  NX  4
void ListFill(int list[], int NN);

int main()
{
  int ix, ax[NX];

  ListFill(ax,NX);
  for (ix = 0; ix < NX; ix++) {
    printf("ax[%d] = %d\n", ix, ax[ix]);
  }
}

/************************************************
 * ListFill()
 * Fill an array with values 0 to NN
 ***********************************************/
void ListFill(int list[], int NN)
{
  int ix;

  for (ix = 0; ix < NN; ix++) {
    list[ix] = ix;
  }
}

Pointer Basics

A pointer is an address associated with a data type.  The following declaration defines the integer x as well as the pointer px which is of type int.  The ampersand symbol (&) returns the address of a variable.  In storing the address of x, px is said to point at x. 

int x, *px;
px = &x;

A pointer to type void is a special type, sometimes called a generic pointer in that it not associated with any specific type.  The value in such a pointer value is type-cast to associate it with a type.  Functions such as malloc that allocate memory won't know what type to assign to the pointer to a block of memory, and generally return a pointer of type void.

The second use of the asterisk symbol involving pointers is called dereferencing, that is to access the thing that a pointer points at.  Since px points at x, assigning a value to *px is equivalent to assigning a value to x. 

*px = 12;
 x  = 12;

The name of an array is a special case of a pointer.  In declaring an integer array named val with 10 elements, the address of the first integer in the list is assigned to the array name.  The following statements are equivalent, each assigns the address of the fist element in an array to a pointer.

p = &val[0];
p = val;

It is now time to put an end to a lingering mystery.  You may have wondered why the & operator is used in calling the scanf() function.  Well, scanf() uses pointers to pass input back to the caller.  Since &val returns the address of val, scanf() simply writes an input value to the address of val.

scanf("%d", &val);

Note that a & is not used in scanf() with an array, as the name of an array is already a pointer.  An array name points at the first element in the array.  Next, reconsider the swap example given earlier.  We can use pointers to allow swap() to actually swap the calling values.  Pointers allow a function to manipulate variables outside its scope.

/*********************************
 * exarg2.c - p.70 of Van Sickle
 * Argument and parameter example
 *********************************/
#include <stdio.h>
void swap(int *x1, int *x2);

int main()
{
  int a = 1, b = 2;
  swap(&a,&b);
  printf("a = %d b = %d\n",a,b);
  return 0;
}

void swap(int *p1, int *p2)
{
  int x3;
  x3  = *p1;
  *p1 = *p2;
  *p2 = x3;
}

Now we achieve the desired result:

$ exarg2
a = 2 b = 1

Character Strings

A character string is a special case of an array.  To be a proper 'C' string, the last element will be a zero value.  This zero value is called a null and is said to terminate the string.  Rather than assigning each individual character to a character string, which you can do, it is more convenient to enclose the characters in a string between a pair of quotation marks.  Thus the character string "Hello" is actually six characters long, the characters are 'H', 'e', 'l', 'l', 'o', and the '\0' null character.  Nearly all 'C' library functions involving strings assume the use of the terminating null character.  Whenever you write your own code to directly manipulate the parts of a character string, be sure to position a terminating null at the end of the string.  Consider the meaning of the following:

char *pntr1;
pntr1 = "Hello There?";

In making such an assignment, the characters themselves are not copied.  Consider, where would the characters be copied to?  A pointer variable can only store an address value.  Hence the assignment above saves in pntr1 the address of the first character in the string.  The following example illustrates these concepts.

/******************************************
 * charpnt.c
 * Illustrate the character string format
 *****************************************/
#include <stdio.h>
int main()
{
  static char messg[] = {"Hello There?"};
  char *pntr;

  pntr = messg;

  printf("Before: %s\n", messg);
  pntr[5] = '!';
  pntr[6] = '\0';
  printf("After.: %s\n", messg);
  return 0;
}

The empty square brackets in messg[] tell the 'C' compiler to allocate enough memory to store the entire character string, including the terminating null.  The memory address of the character string is assigned to messg.  The characters in the string aren't copied.  Rather, 'messg' and 'pntr' point at the same character string.  The assignments to pntr[5] and pntr[6] shorten and change the character string contents.

$ charpnt
Before: Hello There?
After.: Hello!

The example shows us that pointers can be adjusted and dereferenced using square brackets.  Pointers can also be adjusted using pointer arithmetic.

Pointer Arithmetic

Pointers make special use of addition and subtraction.  Given the type that a pointer refers to, the 'C' compiler knows the size of the thing it references.  Rather than advancing to the next byte address, the following statement advances the pointer to point at the next integer. 

p = p + 1;

Similarly, the subtraction operation is defined to return the number of elements between pointer values.  To be valid, the pointers must be of the same type.  Thus (p - val) equals one.  The following example uses simple pointer arithmetic to find the length of a character string.  Such use of pointers is actually quite common 'C'.

/*****************************************************
 * charcount.c
 * An example use of pointer math
 ****************************************************/
#include <stdio.h>
int mystrlen(char *p);

int main()
{
  int n;
  char string[80];

  // fgets also normally inserts the newline character  
  printf("Enter a string of characters\n:");
  fgets(string,80,stdin);

  n = mystrlen(string);
  printf("String length = %d\n",n);
  
  return 0;
}

/* produce the string length */
int mystrlen(char *p)
{
  char *x = p;  /* declare and initialize pointer */
  
  while(*x != '\0') {
    x++; }
  return x - p;
}

The function fgets reads characters into a character string, till it either fills the character string or encounters a terminating character.  The function mystrlen() continues to advance a pointer until the terminating null is encountered.  The length is difference between end pointer x and start pointers p.

Next, consider the popular straight sort that uses the same algorithm you might use to sort a set of index cards.  Imagine you are holding the index cards.  Starting with the first and second cards, put them in order.  Next take the third card and insert that in order.  The algorithm starts with an unsorted list, and builds a sorted list, by inserting in order, one card at a time.  This program however, uses pointers.

/*******************************************************************
 * stsort.c - Krista Hill
 * straight sort example - Sorts a list of numbers
 ******************************************************************/
#include <stdio.h>
void straight_sort(int array[], int n);

int main()
{
  int ix, val[16] = {16, 7,14,10,12, 9,13, 1,
                      8,15, 6, 5, 4, 3, 2,11};
  straight_sort(val,16);

  for (ix = 0; ix < 16; ix++) {
    printf("%2d: %2d\n", ix, val[ix]);
  }
  return 0;
}

/*******************************************************************
 * straight sort
 * This sort inserts each entry in order, in the growing sequence.
 * For modest size lists.  See page 243 of Numerical recipes in C.
 ******************************************************************/
void straight_sort(int array[], int n)
{
  int a, *i, *j, *limit = array + n;

  // loop through list, grab next unsorted entry
  for (j = array + 1; j < limit; j++) {
    a = *j;

    // Move entries to make space for this one
    i = j - 1;
    while (i >= array && *i > a) {
      *(i+1) = *i;
      i--;
    }

    // Insert the entry in sequence
    *(i+1) = a;
  }
}
/* end of straight sort */

To understand the sort it helps to simplify things.  Just for now, assume that the array starts at address zero and that an integer is 1 byte long.  Trace the execution, using an array 4 elements long, listing the values in a, i, *i, j, and *j, and limit.  Consider the list 4, 2, 1, 3.

Recursion

Consider what happens when a function calls itself.  The idea of recursion is a style of coding in which a function is meant to call itself.  The notion of automatic variables allows a compiler to allocate a fresh set of local variables every time the function calls itself.  It is useful to think of each such calling as causing an instance of the function to be created.  The following example program produces the factorial for a given number.

/****************************************************
 * factorial.c  - Krista Hill
 * A traditional yet contrived example of recursion
 ***************************************************/
#include <stdio.h>
long factorial(int n);

int main()
{
   int  n = 4;
   long result;

   result = factorial(n);
   printf("A simple use of recursion\n");
   printf("%d factorial = %ld\n", n, result);

   return 0;
}

// recursive solver
long factorial(int n)
{
  if (n == 0)
    return 1;
  else
    return (long)n * factorial(n - 1);
}

This example is meant to emphasize the automatic memory allocation that occurs with automatic variables.  Unfortunately, without very careful planning, recursive programming can be disastrous for an embedded microcontroller with modest resources.  Can you explain why this is so and what this has to do with the stack?

Two Dimensional Arrays

A two dimensional array can be initialized at declaration time, in this example the first index refers to the row and the second index refers to the column. 

int array[3][4] = {{10,11,12,13},
                   {14,15,16,17},
                   {18,19,20,21}};

Two pairs of square brackets are used to reference elements in a two dimensional array.  The following snippet of code prints the left most column of values in the above array.

for (ix = 0; ix < 3; ix++) {
  printf("%d\n", array[ix][0]);
}

A two dimensional array is handled by the 'C' compiler as an array of arrays.  In the example array above, array is a double pointer, in that it points at an array of pointers.  Each pointer in this array, in turn points at an array of integers.  Hence, the first pair of square brackets dereferences a double pointer, producing a pointer to an array, that is a row of values in the array.  The second set of square brackets dereferences the pointer, producing one element in the array. 

Two dimensional array structure

Homework Problems - Part 3

1. It has been observed that 'C' makes heavy use of the stack.  In a brief paragraph use concepts in this document to justify this observation. 

2. Enter the code for AddInts.c and for homework produce a printout of the file and the execution results.  In a brief statement explain why the value in N is not chaged by AddInts() despite the fact that NN is changed.

3. Enter the code for exarg1.c and for homework produce a printout of the file and the execution results.  In a brief statement explain why the values in a and b are not swapped.

4. Write a function named CountCall( ) that has a static integer used to count the number of times the function is called.  In calling the function the integer is incremented and the new value is passed back, using a return statement.

5. Enter the code for modax.c and for homework produce a printout of the file and the execution results.  In a brief statement explain how the function ListFill() is able to modify the contents of the array named list.

6. The iterative solver use in mysqrt.c is nearly guaranteed to converge, but nevertheless lets add a test.  Insert into the mysqrt() function an integer variable named n that counts the number of loop iterations.  Also, at the top of the program use the following to define the macro MAX_ITERATION_COUNT.  Insert into the mysqrt() function a test such that if the number of iterations exceeds MAX_ITERATION_COUNT, a printf() statement produces an appropriate error message and mysqrt() exits, returning the value in x2 as the estimate of the square root.

   #define MAX_ITERATION_COUNT   10

   For homework produce a listing of your program, example output for normal operation, as well as results with the iteration count error handler invoked.  To produce this second case it should be enough to set MAX_ITERATION_COUNT equal to 2.

7. The function mystrlen() in charcount.c uses pointer arithmetic to count the length of a character string.  Rather than pointer arithmetic, rewrite mystrlen<> to use an integer with square brackets to refer to characters in the character string. 

Please Let me know that you read my web pages.