Home Previous Next

CSC240 :: Lecture Note :: Week 04
{GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates}

Overview

Assignment(s):

Code: ``` extremelyodd.cpp | ArrayEG.cpp | Fibonacci.cpp | BingoCard.cpp | bingo.cpp | LotteryTickets.cpp pointer0.cpp | pointer1.cpp | cmdline.cpp | temps.cpp | [memory allocation] alloc.cpp [recursion] factorial.cpp | power.cpp | printld.cpp | fibonacci.cpp ```

### Reference Parameters

C++ passes arguments to functions "by value." This calling mechanism prohibits called functions from modifying the variables defined in the caller functions.

Reference parameters  allows arguments to be passed "by reference" instead of by value. If you pass an argument to a function by reference, then the called function can access that variable.

Passing an argument by reference causes the address of the variable argument to be passed rather than its value; consequently, the called function receives a "pointer" to the variable. Although the called function is dealing with a pointer, pointer notation is not required.

A parameter that is received as a reference becomes an alias for the variable that was passed.

Reference parameters are often used when passing large arguments to a function (e.g. a structure). It is more efficient to by reference than it is to pass by value (less data must be copied).

Suppose we have a function that converts inches to feet and inches. We have a problem: our function needs to return two pieces of information, but is allowed to return only one value. One solution to the problem is to use reference parameters:

```   int convertInches(int totalInches, int& feet);
// the & after the type  int  indicates that the function
// receives a reference to an  int

...

int feet;
int inches = convertInches(80, feet);
// feet is passed by reference; no special notation is needed

...

/**
The function receives the total inches.  The return value
of the function is the inches, and the feet are copied
into the reference parameter supplied as the 2nd argument.
**/

int convertInches(int totalInches, int& feet) {
const int INCHES_PER_FOOT = 12;
feet = totalInches / INCHES_PER_FOOT;
}
```

{TopOfPage} {Resources}

### Default Function Arguments

Default function arguments can be specified in either the function definition or prototype (but not both). Convention is to specify them in the function prototype.

Only the rightmost arguments can be defaulted. Once a default function argument is used, all remaining arguments must be default arguments.

Default arguments are useful when a function needs more arguments than are necessary to handle simple cases; in particular, functions that construct objects often provide several options for flexibility.

```   Syntax:  data-type function_name(Type param = value);

If  param  is not passed by the caller, then it will be set
to  value  .

Example:

void printReport(char filename[], bool condensed = false);
// one argument is required:  a filename, but the second is a
//     default argument and it defaults to  false  if not passed

printReport("report.out");           //1
printReport("report.out", true);     //2
printReport("report.out", false);    //3
//statements 1 and 3 are equivalent
```

{TopOfPage} {Resources}

Function overloading is the ability to give different functions the same name.

Stroustrup says:

Most often, it is a good idea to give different functions different names, but when some functions conceptually perform the same task on objects of different types, it can be more convenient to give them the same name.
Use descriptive overloaded function names to describe similar operations, not different behaviors.
```   Good:
int max(int, int);        //find max of two ints
float max(float, float);  //find max of two floats

Not so Good:
void draw(Image*);        //draw an image
void draw(Card*);         //draw a card
```
The following is an example of an overloaded function:
```   void print(int), print(double), print(long), print(char),
print(int, int), print(double, double);

char c;
short s;
int i;
float f;

print(c);            // invoke print(char)
print(i);            // invoke print(int)
print(s);            // invoke print(int); s promoted to int
print(f);            // invoke print(double); f promoted to double
print('A');          // invoke print(char); 'A' is a char
print(200);          // invoke print(int); 200 is an int
print(200L);         // invoke print(long); 200L is a long
print(99.9);         // invoke print(double); 99.9 is a double
print(i, i);         // invoke print(int,int)
print(i, 'a');       // invoke print(int,int); 'a' promoted to int
print(s, 'A');       // invoke print(int,int); s - 'A' promoted to int
//! print(1.1L);     // ambiguous -- compiler can't decide
print(200L, i);      // invoke print(int,int);
//! print(i, 3.14);  // ambiguous -- compiler can't decide
```
When  `print()`  is called, the compiler must figure out which of the functions with the name "print" is to be invoked. This is done by comparing the types of the actual arguments with the types of the parameters of all functions called "print". The function with the best match is called; if none exist, then a compile-time error.

Definition:

The  signature  of a function is defined to consist of the name of a function and its ordered set of parameter data types.

Criteria used to determine a match (partial):
1. exact match of function call arguments with an overloaded function signature
2. trivial conversions (exact match after applying promotions to argument data types -- char ==> int, short ==> int, float ==> double)
3. exact match after applying promotions and standard conversions to argument data types (float ==> int, double ==> float)
4. exact match after programmer defined conversions (e.g. typecast)
Note:  `const`  arguments can be distinguished from non-`const` arguments.
```	void foo(const char*);
void foo(char*);

These two functions have different signatures.
```
Return types are not considered in overload resolution.

Functions declared in different scopes do not overload.

If not careful, you can be surprised as to which function is called. It is poor programming practice to redefine library functions (your code may end up calling the correct function, but existing code in the library may end up invoking the wrong function).

Internally, the compiler accomplishes function overloading by  mangling  function names. Function name mangling makes each translated function name unique. A function name is mangled by adding prefixes and suffixes to the the name. The prefixes and suffixes are determined in part by the ordered lists of the function's parameter data types.

```	print(200);             // mangled name: print_Fi
print(float(3.14));     // mangled name: print_Ff
```

C: C++: Java: no yes yes

{TopOfPage} {Resources}

Lifetime is the period, during execution of a program, in which a variable or function exists (all functions in a program exist at all times during its execution).

Visibility is the portions of the program in which a variable or function can be referenced by name (also referred to as scope (scope units: file, function, block or function prototype).

##### Local and Global Variables

Local variables are declared and/or defined within a block (either a function or a compound statement).

• function parameters are local variables
• uninitialized (except for parameters)
• visible from point of definition to the end of the block
• lifetime is from the point of definition to the end of the block
• memory is allocated from the stack
• memory is de-allocated at the end of the block

Global variables are declared and/or defined outside of any function.

• initialized to zero
• visible from the point they are defined to the end-of-source-file (may be visible in other source files also - see extern)
• memory allocated from the data segment at program startup
• memory is never de-allocated
##### auto

The `auto` storage class indicates that a variable is a local variable and that memory is automatically allocated/de-allocated. By default, local variables are defined to be `auto`; therefore, this storage class is rarely specified.

Using `auto` on a global variable is illegal.

Automatic variables are not initialized to any known value.

##### extern

The `extern` storage class allows a global variable to be visible across multiple source files.

A global variable defined in file A can be accessed in file B if and only if file B contains the following declaration.

```	extern type variable_name;

extern int errno;  /* errno is defined in some other file */
```

Use of `extern` results in a declaration -- not a definition. In other words, an `extern` declaration does not result in the allocation of memory.

It is not legal to initialize an external variable at the time it is declared (i.e. `extern float rate = 5.3;` is illegal).

##### static

When `static` is applied to a global variable, then it limits the scope of an object to the rest of the file (i.e. it cannot be externally declared in other source files).

When `static` is applied to a local variable, then it causes the local variable to remain in existence across function calls providing private, permanent storage within a single function.

When `static` is applied to a function, then the function is visible only to the source file in which is defined (in a way, the function is made "private").

##### register

A register is a high speed memory location located on the CPU.

The `register` storage class is used on local variables that are going to be accessed many times (for example, loop control variables).

• register usage can result in smaller/faster programs
• using `register` is often times ignored by the compiler
• applies only to locals and parameters
• cannot use the address-of operator

{TopOfPage} {Resources}

### Arrays

An array is a collection of individual data values with two characteristics: it is ordered and homogeneous.

The following are some terms commonly used when talking about arrays:

• an element of an array is a single data value
• the type of an array is the data type of its elements
• the location of an array is the location of its first element
• the length of an array is the number of elements in the array
• the size of an array is it's length times the size of an element

An array is homogeneous because each element must be of the same type. For example, an array of int's, an array of float's, an array of char's.

An array is ordered -- it has a 1st element, a 2nd element, a 3rd element, and so on. Array elements are stored in contiguous memory locations.

Just like any other variable, an array must be defined before it is used.

```   Syntax:  element-data-type array-name [ length ];

int intArray[10];
name:  intArray
type:  int
length:  10
size:  10 * sizeof(int)

char someString[32];
name:  someString
type: char
length: 32
size:  32 * sizeof(char)
```

Each element of the array is identified by a numeric value called its index (index numbers always start at 0).

When defining an array, its length must be specified at compile-time. In addition, the specification of the length must be a constant integral EXPR.

```
int i = 10;
/* double salaries[i];   // illegal (not a constant) */
/* char name[15.5];      // illegal (not an integral type) */
const int MAX_ELEMENTS = 10;
short scores[MAX_ELEMENTS];  /* okay in C++, not C */
#define LENGTH 5
float someArrayOfFloats[LENGTH];

```

Typically, array lengths are defined to be manifest constants.

##### Array Initialization

Arrays can be initialized at the time they are defined.

```   int evenNumbers[5] = { 2, 4, 6, 8, 10 };

note:  it is a syntax error if the # of initializers is
greater than the array length (i.e. # of elements)

The elements of the initializer list must be constant
EXPRs.  If the number of initializers is less than the
array length, then remaining elements are set to zero.
```

If an array is initialized when defined, then the length is not needed -- the compiler will set the length depending on the number of initializers. If the length of the array needs to be greater than the number of initializers specified, then the length must be specified.

```   float radioStations[] = { 103.1, 93.3, 100.7 };

radioStations  has a length of 3; to figure out the length
of the array using code:

sizeof(radiostations)  evaluates to the size of the array
and  sizeof(radioStations[0])  evaluates to the size of a
single element of the array (recall, an array size is equal
to the length of the array times the size of the array type)

the following EXPR also works to determine the length of
an array    sizeof(radioStations) / sizeof(float)    but could
result in the defect if the type of the array is changed and
the EXPR is not
```

There is not a convenient mechanism for initializing all elements of an array to a single value (exception: it is easy to set all elements of an array to zero -- `int a[10] = { 0 };`).

For efficiency, locally declared arrays that are initialized at definition may be declared to be `static`.

```   static short tvStations[99] = { 3, 10, 12, 61 };

tvStations  is an array of length 99; elements 0, 1, 2, 3
have non-zero values, whereas elements 4 through 98 equal 0;
the array is initialized once -- at program load time
```

Once an array has been defined, its length (i.e. number of elements) cannot be altered.

Elements of the array are accessed using the unary array operator `[]`.

```   const int LEN = 10;
int a[LEN];

a[3] = 150;  /* set element #4 to 150 */
a[1] = 200;  /* assign the value 200 to element #2 */

if (a[1] == a[3]) /* compare the value of element #2 with element #4*/
```

Array indicies must be integral values, but they are not restricted to being constants.

```   int i, j, k;

a[0] = 100;
a[i] = 150;
a[i * j - k] = 210;
a[a[a[i]]] = 250;
a[rand() % LEN] = 178;
```

The language does not protect against indexing beyond the ends of an array. Typically, if this happens, then a run-time error is encountered.

```   a[-1] = 100;
a[sizeof(a)/sizeof(a[0]) + 2] = 200;
```

Array 'a' cannot be copied to array 'b' using simple assignment.

```   #define LEN 5
int a[LEN] = { 100, 200, 210, 120, 240 }, b[LEN];

/* b = a;   //syntax error -- array name not a lvalue */
for (int i = 0; i < LEN; i++)
b[i] = a[i];
```
##### Arrays and Functions

Arrays are passed to functions "by reference." (Think about the overhead if arrays were passed by value.)

A function that receives an array as a parameter, obtains a constant pointer to the first element of the array.

Unless specifically qualified to be `const`, the function can modify the content of the array.

When a function receives an array as a parameter, it does not know, nor can it figure out, the length or size of the array. In many cases, the caller passes the array length (`size_t`) to the function.

```   void func1(int[]);         //do *not* specify the array length
void func2(const int[]);   //func2() not allowed to modify the array
void func3(int [], int);
#define A_LEN 10
int a[A_LEN];

func1(a);  //using array name w/o [] operator "decays" into a
//constant pointer to the 1st element of the array
func2(a);
func3(a, A_LEN);  //pass the array length to the function
...

void func1(int i[]) {  //again, array length not specified
int len = sizeof(i) / sizeof(i[0]);
// does not work -- sizeof(i) evaluates to the size
// allocated for pointer variables, which is typically
// the sizeof(int)...
...
}

void func2(const int i[]) {
//! i[0] = 100;    //use of  const  implies the content of the
//array cannot be changed...
}

void func3(int i[], int len) {
for (int i = 0; i < len; i++)
//loop through each element of the array
...
}
```

Pointer notation can be used when prototyping and defining functions that receive arrays as parameters.

```   void func1(int*);  //this syntax indicates that the function receives
//a pointer to an array
void func2(const int*);  //array content cannot be modified
```

{TopOfPage} {Resources}

### Pointers

A pointer is a variable whose value is an address of another variable.

• pointers are referred to as derived data types
• a pointer is a variable (it has a name, and it points to a particular type of data)
• the amount of space allocated for a pointer variable is typically the size allocated for an `int`
• pointer variables are assigned address values obtained using the address-of operator `&`
• local pointer variables are uninitialized
##### Defining and Initializing Pointer Variables
When defining a variable, prefixing the variable's name with an asterik `*` causes the variable to be a pointer.

```   int* iptr;   /*define variable iptr that will point to an int variable*/
float * fptr; /*define variable fptr that will point to a float variable*/
char *cptr;  /*define variable cptr that will point to a character*/
int i, j;
float f;
char c;

iptr = &i;  /*assign the address-of variable 'i' to iptr*/
fptr = &f;  /*assign the address-of variable 'f' to fptr*/
cptr = &c;  /*assign the address-of variable 'c' to cptr*/
int* iptr2 = &j; /*define and initialize an int pointer*/
iptr = iptr2;  /*now iptr points to the variable 'j'*/

note:  Placement of the  *  when defining a pointer variable is
a matter of style -- I like to place the  *  next to the
data type, but others prefer to place it next to the
variable name.  Placing it next to the data type does
require caution when multiple variables are defined on
the same declaration statement.  Example:

int* ip1, ip2;
// ip1  is a pointer to an  int  , but  ip2  is a
regular  int

int* ip1, *ip2;
// ip1  and  ip2  are both pointers to an  int
```

The address-of operator only applies to objects in memory: variables and array elements.

Locally defined non-static pointers, unless explicitly initialized, are garbage and using them without initialization can cause a program to execute incorrectly (or abort).

Global and statically defined pointers are initialized to the `NULL` pointer.

##### Accessing Data Using Pointers

The unary operator `*` is the indirection or dereferencing operator; when applied to a pointer, it accesses the object the pointer points to.

```   int i = 200;
int* iptr = &i;

cout << *iptr;    /*prints 200 -- the value of 'i' which is the object
iptr points to*/
```
##### Pointers and Function Arguments

Since C passes arguments to functions by value, there is no way for the called function to alter a variable in the calling function. A way to obtain the desired effect is for the calling program to pass pointers to the values to be changed.

```   void swap(int*, int*);

int i, j;

swap(&i, &j);

void swap(int* a, int* b) {
int tmp = *a;
*a = *b;
*b = tmp;
}
```

Using pointers is similar to using reference variables; however, reference variables are part of C++ and they are not part of C.

Advantage of using reference variables over pointers.

• cleaner syntax

##### Introduction to Pointers and Arrays

There is a strong relationship between pointers and arrays.

When an array name is used by itself, it evaluates to a constant pointer to the first element of the array.

Everywhere you use `arrayName[index]` you can use `*(ptr + index)` (assuming `ptr` points to some part of the array).

```   int scores[10];

scores[0] = 2;      // or  *scores = 2
scores[1] = 3;      // or  *(scores + 1) = 3
*(scores + 2) = 5;  // or  scores[2] = 5
```

{TopOfPage} {Resources}

### Recursion

Recursion is any solution technique in which large problems are solved by reducing them to smaller problems of the same form.

According to multiple sources, the text `Thinking Recursively` by Eric Roberts (John Wiley 1986) is an excellent resource on recursion.

Internally, recursive functions are supported using a stack.

Almost every recursive function has the same basic structure:

```   if (test for simple case)
return (simple solution computed w/o using recursion)
else
return (recursive solution involving a call to the same function)
```

A recursive function is a function that calls itself in its function body. The call uses different arguments that ultimately read values that allow the function to return a result.

A recursive algorithm must have a well-defined stopping state, or termination condition.

Tail recursion is when the only recursive call appears in the function and that recursive call is the last operation performed at that procedural level. Typically, tail recursive functions can be easily rewritten as non-recursive functions. The traverse linked-list example provides an example of tail recursion.

• Recursion replaces the loop.
• Recursion may provide no saving in storage, since somewhere a stack of the values being processed must be maintained.
• Recursion will not be faster.
• Recursive code is more compact, and often much easier to write and understand than the non-recursive equivalent.
• Recursion is especially convienent for recursively defined data structures likes trees.
• Recursive procedures can be carried out with a stack.

#### Interesting Recursion Related Tidbit

Headline: "Microsoft's Java JIT compiler bungles tail recursion."

A programmer from England has discovered a flaw in Microsoft's Java environment running in Internet Explorer under Windows. On 10/20/1998 Andrew Kennedy posted a note to Java programming newsgroups showing that jview, Microsoft's command-line interface to its just-in-time compiler, calculates the factorial of 5 (i.e., 5 * 4 * 3 * 2 * 1 * 0!) to be 16. Kennedy writes:
> Microsoft seem to have confused addition with multiplication. > Such an easy mistake to make.
Followup postings pin down the likely source of the bug as incorrectly handled tail recursion in Microsoft's JIT compiler. Unfortunately there seems to be no way to turn off JIT. Kennedy speculates that this error may be responsible for the failure of a large number of Java applets to run in the IE 4 environment.

#### The Factorial Example

Computing the factorial of a number is popular example of using recursion.

```   Mathematically:  n! = { 1  if n = 0; otherwise,  n * (n-1)! }
```

To compute `n!` you must:

1. remember what  `n`  is
2. go compute  `(n-1)!`
3. once  `(n-1)!`  is computed, multiply by  `n`  to get the final answer
```   To compute (n-1)!, you 1st compute (n-2)!.  Computing (n-2)!
requires finding (n-3)! and so on.  Eventually we end up at 0!
and 0! is defined to be the value 1.

In C:
printf("%i\n", factorial(4));

int factorial(int n) {
if (n == 0) return 1;
return n * factorial(n -1);
}

4 is pushed onto the stack
3 is pushed onto the stack
2 is pushed onto the stack
1 is pushed onto the stack
0 is pushed onto the stack
returns 1
1 * 1 returns 1
2 * 1 returns 2
3 * 2 returns 6
4 * 6 returns 24
```
See factorial.cpp and Factorial.java.

Recall: When a function is called, EXPRs are evaluated and are passed by value. An implicit argument that is passed to a function is a return address. Function return values, if any, are placed in a secure location from which the calling program may retrieve it.

#### The Power Example

Raising a number to a power can also be solved recursively.
```   Power function:   n**k = { 1  if k is 0; otherwise, n * (n**(k-1)) }
```
Computing  `xn` , where  `x`  is a real number and  `n`  is a non-negative integer, is called the power function and its calculation is usually accomplished with repeated multiplication:
```   xn = x * x * x * ... *x * x

where  x  multiplied with itself  n  times

20 = 1
21 = 2 * 1 = 2
22 = 2 * 2 = 4
23 = 2 * 2 * 2 = 8
24 = 2 * 2 * 2 * 2 = 16
```
The power function can be implemented as follows:
```
power(x, n) = xn = { 1, n = 0 | x * xn-1, n > 0 }

double power(double x, int n) {
if (n == 0) return 1;
return x * power(x, n-1);
}

```
See power.cpp and Power.java.

#### Coverting an Integer to a String

```   printd(150);

printd(int n) {
if (n / 10)
printd(n / 10);
putchar(n % 10 + '0');
}

150 / 10 -- 15 pushed onto the stack
15 / 10 -- 1 pushed onto the stack
1 / 10
1 is printed
5 is printed
0 is printed
```
See printld.cpp and PrintLD.java.

{TopOfPage} {Resources}

Home Previous Next