PROGRAMMING WITH FUNCTIONS

18.01

•	What is programming about?        
		solving (classes of) problems by means of a computer
•	What do you need?
		an algorithm (i.e. a series of actions or instructions) 
		that solves your problem
•	Do you need more than that?
		translation of the algorithm to C
		a compiler and a computer

•	Programming activities            
		we distinguish a series of phases from
		problem to problem-solving-program.
	                                   
	•	Study and analyze the problem   until complete understanding
	•	Design one or more solutions     to solve the problem
	•	Validate your solution(s)             show them to be correct
	•	Implement your solution(s)         translate them into C
	•	Certify your implementation       show your program to be correct
	•	Performance analysis                  how efficient is your program?

18.01

TABLE OF CONTENTS HC 18

18.02

A CONCRETE EXAMPLE

18.02

Let us require that a, b and c represent the lenghtes of the sides of 
a triangle [A,B,C], i.e., a = distance(B,C) and so on, must hold.
Problem: determine the perimeter and the area of this triangle.

•	Study and analyze the problem until completely understood.

	•	Is the problem completely understood?
		"... require that a, b and c represent ..." 
		What does this mean?
	•	What is the perimeter of a triangle?
	•	Oke, perimeter is obvious
		but how do you determine the area of a triangle?

After some study you will find the answers:

	•	The triangle exists iff a, b and c satisfy ...
	•	The perimeter of the triangle is given by ...
	•	The area of the triangle is given by ...

18.01

TABLE OF CONTENTS HC 18

18.03

DESIGN

18.03

•	Design a solution that solves the problem.
	
	•	 input: get values for a, b and c
	•	if the triangle does not exist 
			message "triangle [A,B,C] does not exist"  
		else
			 determine perimeter and area
			message "results for [A,B,C] are ..."
	•	 output: print message

•	Validate your solution.
		show that formulas for existence, perimeter and area are correct
	
•	Implement your solution(s).
		translation into C will be discussed later

•	Certify your implementation i.e. show the program to be correct.
	•	by executing simple cases where the answers are known
	•	by executing special cases where the answers are known
	•	by computing the area in two or more distinct ways and then
		comparing the results

18.02

TABLE OF CONTENTS HC 18

18.04

SUMMARY

18.04

Summarizing:

•	Problem analysis        without a correct analysis 
	                                  you will not arrive at a correct design
•	Algorithm design        without a correct design
	                                  you will not arrive at a correct program
•	Program testing         end even then ...
	                                  programmers always make mistakes!

Designing is partly a work of art and therefore, generally speaking, each
programmer will generate a different program for one and the same problem.

Structured Programming Guidelines can be of help:
•	top-down
•	breadth first

Example: twin primes.
	A prime is a number p that has no divisors other than 1 and itself.
	A twin prime is a pair of numbers of the form tpn = (n-1, n+1) 
	such that both n-1 and n+1 are prime.
Problem:
	Determine all twin primes in a given interval [lbnd .. ubnd].

18.03

TABLE OF CONTENTS HC 18

18.05

ANOTHER EXAMPLE: TWIN PRIMES

18.05

Top down design:

	main
		declare interval bounds lbnd and ubnd 
		and require that lbnd < ubnd-1
		
1.1		get values for lbnd and ubnd from keyboard
1.2		determine twinprimes in interval from lbnd to ubnd

	Subproblem 1.1
		getInterval(&lbnd, &ubnd);
		the user of this program enters the lower- and upperbound  
		of the interval from the keyboard
1.1.1	 	message "enter lowerbound please"
1.1.2	 	get lbnd
		 	do
				message "enter upperbound please"
				get ubnd
			while (ubnd < lbnd+2)

18.04

TABLE OF CONTENTS HC 18

18.06

TOP DOWN DESIGN

18.06

Thus:

		void getInterval(int* lbnd, int* ubnd) {
1.1.1		printf("enter lowerbound please\n");
1.1.2		scanf(lbnd);
			do {
1.1.1			printf("enter upperbound please\n");
1.1.2			scanf(ubnd);
			} while(*ubnd < *lbnd+2);
		}

Subproblem 1.2

		void getTwinPrimes(int lbnd, int ubnd);
		•	decide on the loop you are going to use
			i will use a for loop
		•	int n;
			for (n = lbnd+1; n < ubnd; n++) // performance??
1.2.1			if (isTwinPrime(n))
1.2.2				print result [n-1, n+1]
		

18.05

TABLE OF CONTENTS HC 18

18.07

TOP DOWN DESIGN

18.07

Subproblem 1.2.1
	isTwinPrime(n) =
		isPrime(n-1) and isPrime(n+1)  // subproblem 1.2.1.1

Subproblem 1.2.1.1
	isPrime(k) =
		d = 2;
		while (d < k) {                // performance??
			if (isDivisor(d, k))      // subproblem 1.2.1.1.1
				return false;
			++d;
		}
		return true;
		
Subproblem 1.2.1.1.1
	isDivisor(d, k) =
		k % d == 0
		
OK: now you can finish the implementation (depending on how much C 
you know) and you can test the program.
The last question is about the performance of your program!

18.06

TABLE OF CONTENTS HC 18

18.08

PERFORMANCE

18.08

Performance of the while loop in isPrime(k):
Here divisibility is checked for all d = 2, 3, 4, ... k-1.

After some thought it becomes clear that 
•	d can be restricted by d*d <= k
	since if d divides k then e = k/d divides k as well, and
•	if you first perform a check on k being even you can improve
	performance by a factor of 2.
Thus
	int isPrime(int k) {
		if (isDivisor(2, k))         // subproblem 1.2.1.1.1
			return (0);
		else {
			int d = 3;
			while (d*d <= k) 
				if (isDivisor(d, k)) // subproblem 1.2.1.1.1
					return (0);
			d += 2;
		}
		return (1);
	}

18.07

TABLE OF CONTENTS HC 18

18.09

PERFORMANCE

18.09

Performance of the for loop in getTwinPrimes(lbnd, ubnd):
Here, for each n = lbnd+1 to ubnd-1 we perform the test

	isPrime(n-1) and isPrime(n+1)
	
A lot of superfluous tests are executed and 
you can make this loop 6 times as fast!
Consider numbers 6*k-2, 6*k-1, 6*k, 6*k+1, 6*k+2 and 6*k+3
Then only 6*k-1 and 6*k+1 can possibly be prime implying that twinprimes
must be of the form (6*k-1, 6*k+1).
Hence the for loop starts with the smallest 6-fold larger than lbnd
                 and ends with the largest 6-fold smaller than ubnd
                 and its stepsize becomes 6.
Thus:
	void getTwinPrimes(int lbnd, int ubnd) {
		int n, lbnd6 = lbnd + 6 - lbnd%6, 
		       ubnd6 = ubnd - 6 + ubnd%6;
		for (n = lbnd6; n <= ubnd6; n += 6)
			if (isTwinPrime(n))
				printf("[%d, %d]\n", n-1, n+1);
	}

18.08

TABLE OF CONTENTS HC 18

18.10

THE FUNCTION printf()

18.10

The function printf()

	int printf("format string", list of expressions);

•	the format string consists of a sequence of characters delimited by "
	and when you need to print " you must use \"

•	printf evaluates the expressions that occur in the list and prints the
	resulting values according tot the specifications of the format string

•	the format string contains format specifiers and regular characters
	the regular characters are printed as such
	the format specifiers control the printing of their arguments

•	a format specifier starts with % and ends with a conversion character
	it just tells printf how to print the corresponding argument
	and when you need to print % you must use %%

•	printf returns the number of characters it writes to standard output
	if successful!, otherwise it returns -1.

18.09

TABLE OF CONTENTS HC 18

18.11

EXAMPLE OF printf()

18.11

A simple printf() example:

	int     c  = 299997;
	
	printf("c = %d km/sec and pi = %5.3f.\n", c, 4*atan(1));

		format string         c = %d km/sec and pi = %5.3f.\n
		regular charachters   c =    km/sec and pi =      .\n
		format specifiers         %d                 %5.3f                        
 		expressions           c                  4*atan(1)

	%d tells printf to print the value of c as an integer 
	%5.3f tells printf to print the result of the evaluation of the expression
	as a real number in a field of width 5 with a precision of 3 digits
	after the decimal point.

Format specifiers are rather complicated objects that can contain 
up to six attributes:
% flag(s) fieldwidth precision sizeModifier conversionChar

See your reference manual or the collected examples in the reader appendix B
or the summary in section 1.2.4.2

18.10

TABLE OF CONTENTS HC 18

18.12

THE FUNCTION scanf()

18.12

The function scanf() parses formatted input, reads characters from an 
inputstream and converts sequences of characters according to its 
control string format. Whew! Just study the reader Appendix B!
Simple examples:

	char   c;
	int    n;
	double x;
	
	printf("enter a character please.\n"); 
	scanf("%c", &c);
	printf("enter a whole number please.\n"); 
	scanf("%d", &n);
	printf("enter any real number please.\n"); 
	scanf("%f", &x);

NOTE: 
	for value types like char, int and double the argument in scanf()
	is the name of the variable preceded by an &.

The character value obtained from the keyboard 
is stored at the address of the character variable c.

18.11

TABLE OF CONTENTS HC 18

18.13

THE FUNCTION scanf()

18.13

The function scanf() is a complicated function and must be used with care.
Many easily made mistakes have been collected in the reader Appendix B.

The best or most beautiful mistakes have been collected in 
program 1.2.4.3.01 on page 31

Personally I like this one:

void Test2(void) {
	char c1, c2, c3; int n1, n2; double x;
	printf("Enter three chars, two ints an one real.\n");
	printf("Separate input elements by a single space.\n>>\t");
	scanf("%c%c%c%d%d%lf", &c1, &c2, &c3, &n1, &n2, &x);
	printf("|%c||%c||%c||%d||%d||%f|\n", c1, c2, c3, n1, n2, x);
}
Sample run:
	Enter three chars, two ints an one real.
	Separate input elements by a single space.
	>>	a b c 123 1234 1.0
	|a|| ||b||44615512||44240382||-1096337729661848233.000000|

and this is not what I had in mind!!

18.12

TABLE OF CONTENTS HC 18

18.14

DEFINING YOUR OWN TYPES

18.14

The programming language C offers the possibility to introduce new types
using the typedef mechanism:

	typedef oldType newType;

This mechanism can be used to introduce types that do not exist in C.
Some simple examples used to introduce the mechanism:

	typedef int bool;
	const bool FALSE = 0, TRUE = 1;
	
From now on you can use your own truth-value type bool 
whenever you mean boolean:

	bool isPrime(int k);

Maybe you do not like the type double

	typedef double real;
	real circleArea(real radius);

18.13

TABLE OF CONTENTS HC 18

18.15

DEFINING ENUMERATED TYPES

18.15

Sometimes variables have a restricted set of values like the days of the week
or the months of the year. In these cases C offers the possibility to define
new types using the typedef enum mechanism.

	typedef enum {comma-separated list of identifiers} newType;

The internal representation of the identifiers uses integer values starting
from 0 (unless otherwise specified).

Some examples:

	typedef enum {FALSE, TRUE} bool;

	typedef enum {RED, ORANGE, GREEN} color;
	color trafficLight;

and now trafficLight is a variable of type color that can take only 3 values,
known by name, which can be used in a selection statement: 

18.14

TABLE OF CONTENTS HC 18

18.16

MORE ENUMERATED TYPES

18.16

	switch (trafficLight) {
		case RED    : /*         stop        */ break;
		case ORANGE : /*      accelarate     */ break;
		case GREEN  : /*          go         */ break;
		default     : /* weird traffic light */ break;
	}

Some other examples: 

typedef enum {UNDEF, MON, TUE, WED, THU, FRI, SAT, SUN} days1;
internal rep      0    1    2    3    4    5    6    7

typedef enum {MON = 1, TUE, WED, THU, FRI, SAT, SUN} days2;
internal rep        1    2    3    4    5    6    7

typedef enum {SUN, MON, TUE, WED, THU, FRI, SAT} days;
internal rep    0    1    2    3    4    5    6

This last type is most convenient:

18.15

TABLE OF CONTENTS HC 18

18.17

MORE ENUMERATED TYPES

18.17

day  aDay, tomorrow, aWorkDay; // three variables of type day

day theNextday(day d) { // function that returns tomorrow
	return((d+1) % 7);
}

day d;
for (d = MON; d < SAT; d++) { // a for loop processing work days
	// work!!
}
Some more examples:	
typedef enum {NORTH, EAST, SOUTH, WEST} directions;
	
typedef enum {ZERO, ONE, TWO, THREE, FOUR,
              FIVE, SIX, SEVEN, EIGHT, NINE} digits;

typedef enum {ONE = 1, TWO, THREE, FOUR, FIVE, SIX} dice;
	
typedef enum {HEARTS, DIAMONDS, CLUBS, SPADES} suits;
typedef enum {TWO = 2, THREE, FOUR, FIVE, SIX, SEVEN,
              EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE} faces;

18.16

TABLE OF CONTENTS HC 18

18.18

THE struct IN C

18.18

A struct is a datatype where variables of different types can be grouped 
toegether. Here you can think of 
•	your name: one or more initials and a last name,
•	your home address: street, streetnum, postcode, city,
•	a circle: center and radius,
•	a point: x- and y-coordinate,
•	etc., etc.

The syntax of struct will be introduced by some very simple examples.
A point is characterized by x- and y-coordinate:

	struct point {      // defines the type struct point
		double x;      // member x of type double
		double y;      // member y of type double
	};                 // do not forget the semicolon!
	
	struct point p, q; // variables p and q of type struct point
	
Now define points p and q:

	p.x = 0.0; p.y = 0.0;
	q.x = 3.0; q.y = 4.0;

18.17

TABLE OF CONTENTS HC 18

18.19

POINTs AND CIRCLEs

18.19

A circle is characterized by the x- and y-coordinate of its center 
and the value of its radius:

	struct circle1 {       // defines the type struct circle1
		double x;           // x-coordinate of type double
		double y;           // y-coordinate of type double
		double radius;      // radius of type double
	};                     // do not forget the semicolon!
	
	struct circle1 c1;     // variable c1 of type struct circle1

	c1.x = c1.y = 0.0;     // c1 has the origin as its center
	c1.radius = 5.0;       // and the radius is equal to 5.0
	
	double circleArea(struct circle1 anyCircle) {
		return(PI * anyCircle.radius * anyCircle.radius);
	}

or better by composition: struct can contain struct which can contain ....

18.18

TABLE OF CONTENTS HC 18

18.20

THE struct AND COMPOSITION

18.20

	struct circle2 {       // defines type struct circle2
		struct point center;     // center of type struct point
		double radius;           // radius of type double
	};                     // do not forget the semicolon!
	
	struct circle2 c2;     // variable c2 of type struct circle2

	c2.center.x = 4.0;
	c2.center.y = 5.0;     // c2 has center [4.0, 5.0]
	c2.radius = 10.0;      // and the radius is equal to 10.0
	
The new types are struct point, struct circle1 and struct circle2.
Here point, circle1 and circle2 are called structure tags. 
However, it is far more convenient to have a type as short as the tag 
and this can be achieved using the typedef mechanism.

	typedef struct point {    // tag is optional
		double x;
		double y;
	} point;                  // defines the new type point
	
	point p, q;               // variables of type point

18.19

TABLE OF CONTENTS HC 18

18.21

A LARGER EXAMPLE

18.21

	typedef struct circle {   // tag is optional
		point center;
		double radius;
	} circle;                 // defines the new type circle
	
	circle c;                 // variable of type circle

A larger example: A library contains books. 
My library has a restricted capacity of 1024 books (libCapacity = 1024), 
and the number of books currently present is given by numBooks.
Each book is characterized by title, author, isbn-code and purchase date.

Design of the library:
•	since my library has a fixed capacity 
	books will be stored in an array that can contain 1024 books at most.
•	the current number of books will be kept in  int numBooks and 
	books are arranged 0..numBooks-1 with numBooks < libCapacity.
•	the array of books will be called bookStore and 
	contains elements of type book.
•	the library itself is of type library.

18.20

TABLE OF CONTENTS HC 18

18.22

THE LIBRARY

18.22

	#define libCapacity 1024
	
	typedef struct library {
		book bookStore[libCapacity]; // array of book
		int  numBooks;               // current number of books
	} library;                       // type library
	
	library theLibrary;              // variable theLibrary

The attributes title, author and isbn-code will be represented by our
own type string
and the purchase date will be of some type date to be designed below.

	typedef struct book {
		string title,
		       author,
		       isbncode;
		date   purchase;
	} book;

	book aBook;

18.21

TABLE OF CONTENTS HC 18

18.23

BOOKs AND DATEs

18.23

Our strings are declared as array of char:

	#define maxStrSize 32
	typedef char string[maxStrSize];
	string aString;

Our dates:
	typedef struct date {
		int day,
		    month,
		    year;
	} date;
	date aDate;

Initialization of a date variable:

	aDate = {
		16, 5, 2003
	};

18.22

TABLE OF CONTENTS HC 18

18.24

BOOKs AND THE LIBRARY

18.24

Initialization of a book variable:

	aBook = {
		"Programming in ANSI C", // title
		"Kochan SG",             // author
		"0-672-3039-6",          // isbn code
		{15,  8, 1994}           // date
	};

In the same spirit theLibary can be initialized according to

	theLibrary = {{
		{title0, author0, isbn0, {day0, month0, year0}},
		{title1, author1, isbn1, {day1, month1, year1}},
		{title2, author2, isbn2, {day2, month2, year2}},
		{title3, author3, isbn3, {day3, month3, year3}},
		{title4, author4, isbn4, {day4, month4, year4}},
		5
	}

18.23

TABLE OF CONTENTS HC 18

18.25

RETRIEVING DATA

18.25

Retrieving data:
When was the last book bought?

	book lastBook = 
		theLibrary.bookStore[theLibrary.numBooks - 1];
	date theRequiredDate = lastBook.purchase;

Inserting and updating data:
Yesyerday I bought a new book which I will now insert into the library

	book newBook;
	date yesterday = {2003, 6, 10};
	strcpy(newBook.title, "Il nome della rosa");
	strcpy(newBook.author, "Eco U");
	strcpy(newBook.isbncode, "90-351-1413-2");
	newBook.purchase = yesterday;
	theLibrary.bookStore[theLibrary.numBooks++] = newBook;
	

18.24

TABLE OF CONTENTS HC 18

18.26

ASSIGNMENTs

18.26

	book copyOfBook123 = theLibrary.bookStore[123];
	
	library copyOfTheCompleteLibrary = theLibrary; // WHEW!!
	
follows the same pattern as any value-type assignment like int n2 = n1;
	
Indeed: structs that contain no pointer members (some_type*) 
        are value types and behave like value types!
Consequences:

•	A struct can be used as a formal parameter in a function.
	At calling time the formal parameter receives a copy of an actual argument
	which must be a struct of the same type as the formal parameter.
	
	double distanceToOrigin(point p) {
		return(sqrt(p.x * p.x + p.y * p.y));
	}
	usage:
	point somePoint = {1.0, 5.0};
	double d = distanceToOrigin(somePoint);

18.25

TABLE OF CONTENTS HC 18

18.27

FUNCTION CAN RETURN struct

18.27

•	A function can return a struct

	book newBook(string title, string author, string isbn,
	                                               date d) {
		book b;
		strcpy(b.title, title);
		strcpy(b.author, author);
		strcpy(b.isbn, isbn);
		b.purchase = d;
		return(b);
	}
	
	usage:
	string title  = "Il nome della rosa",
	       author = "Eco U",
	       isbn   = "90-351-1413-2";
	date d = {31, 1, 1995};
	      
	book b = newBook(title, author, isbn, d);

Note that this is what a constructor looks like in the language C.

18.26

TABLE OF CONTENTS HC 18

18.28

CALL BY VALUE AND ...

18.28

Let  
	return_type function_name (formal_parameter_type, ...)

denote any function in C used as

	return_type result = function_name(expression, ...);

Then expression is evaluated and the result is assigned to the corresponding
formal parameter.
Expression can be a simple constant or a variable and in that case the formal
parameter receives a copy of the value of the constant or variable.

•	Formal value parameter receives copy of value of actual variable.
	Function can use/modify this value but since the function works on a
	copy the value of the actual variable will not change during execution 
	of the function. This mechanism/behaviour is known as CALL BY VALUE. 
	
•	Formal pointer parameter receives copy of address of actual variable 
	(an address value) and again the function can use and modify this 
	value but since the function works on a copy, the address of the 
	actual variable will not change during execution of the function. 
	Again we have CALL BY VALUE. 

18.27

TABLE OF CONTENTS HC 18

18.29

CALL BY REFERENCE AGAIN ...

18.29

But:
	through the copy of the address of the actual variable the value of this
	variable can be accessed and modified and this behaviour/mechanism 
	is known as CALL OR PASS BY REFERENCE.

So, whenever a result must be passed back to the caller of the function you 
need to pass the result using a pointer. Schematically:

void f1(res_type* r1);   // prototype for function f1
                         // parameter r1 is ptr to res_type
int main(void) {

	res_type theResult1; // actual theResult1 is res_type
	...
	f1(&theResult1);     // invocation of the function f1
	                     // actual expression is ptr to res_type
	...
}
	
Parameter r1 receives &theResult1 and manipulates theResult1 using *r1.
If execution changes the value *r1 then the value of the actual variable 
theResult1 changes accordingly.

18.28

TABLE OF CONTENTS HC 18

18.30

AND DOUBLE INDIRECTION

18.30

Now, if the result that must be passed back is itself a pointer variable
and this happens very often (double indirection or pointer to pointer to ..)
the scheme above becomes:

	void f2(res_type** r2);    // prototype for function f2
	                           // r2 is ptr to ptr to res_type
	int main(void) {
		res_type* theResult2;   // theResult2 is ptr to res_type
		...
		f2(&theResult2);        // invocation of the function f2
		                 // expression is ptr to ptr to res_type
		...
	}

The scheme of double indirection is consistent and should not trouble you.
If you are confused however you better use the typedef mechanism:

	typedef res_type* res_type_ptr;

	void fun(res_type_ptr* r);    // prototype for function fun
	                              // r is ptr to res_type_ptr
	                              // ie ptr to ptr to res_type

18.29

TABLE OF CONTENTS HC 18

18.31

APPLICATION OF typedef

18.31

int main(void) {
	res_type_ptr theResult; // theResult of type ptr to res_type
	...
	fun(&theResult);        // invocation of the function fun
	                        // expression is ptr to res_type_ptr
	...
}

The last scheme only differs from the first in res_type versus res_type_ptr
and are textually identical. The first scheme expresses pass by reference
of a variable of type res_type and the last scheme expresses pass by 
reference of a variable of type res_type_ptr.

A last example: Create a list of words and sort the list alphabetically.

•	a word might be represented as an array of characters
	in C we will use a pointer to char to refer to a word: type char*
•	a wordlist might be represented as an array of word
	in C ptr to ptr to char to refer to a wordlist:              type char**
•	sorting this list passing it by reference to a
	function sort then requires a formal parameter of     type char***

18.30

TABLE OF CONTENTS HC 18

18.32

GET RID OF THE STARS

18.32

Functions like 
	fill_wordlist() 
	sort_wordlist() and 
	show_wordlist() 

will have prototypes like:


	void fill_wordlist(char*** wlist, int* length);
	void sort_wordlist(char*** wlist, int  length);
	void show_wordlist(char**  wlist, int  length);

This might be confusing and easily leads to programming errors.
Actually, without any documentation at all, you should be confused!!

18.31

TABLE OF CONTENTS HC 18

18.33

INCLUDING THE DOCUMENTATION

18.33

Use typedef to get rid of the stars in order to express yourself more clearly:

typedef char*  word;
typedef word*  wordlist;

	void fill_wordlist(wordlist* wlist, int* length);
	// pre:    wlist and length are undefined
	// action: fill the list with length words
	// post:   wlist refers to a list of length words
	void sort_wordlist(wordlist* wlist, int  length);
	// pre:    wlist refers to a list of length words
	// action: sort the list "from a to z"
	// post:   wlist refers to a sorted list of length words
	void show_wordlist(wordlist wlist, int  length);
	// pre:    wlist refers to a list of length words
	// action: print the list "from first to last word"
	// post:   wlist still refers to the same list of words

Again: if a formal parameter has no star
the function can not change the actual argument
and if a formal parameter has one star  
the function can change the actual argument to which it refers.

18.32

TABLE OF CONTENTS HC 18

18.34

xx

18.34

34

18.33

TABLE OF CONTENTS HC 18

18.35

xx

18.35

35

18.34

TABLE OF CONTENTS HC 18

18.01

TABLE OF CONTENT HC 18

TOC

TOC