Home Previous Next

CSC220 :: Lecture Note :: Week 06
Assignments | Code | Handouts | Resources | Email Thurman {Twitter::@compufoo Facebook::CSzero}
{GDT::Bits:: Time  |  Weather  |  Populations  |  Special Dates}

Overview

Assignment(s): To Be Defined

Code: ArrayEG.cpp | Fibonacci.cpp | BingoCard.cpp | bingo.cpp | LotteryTickets.cpp
pointer0.cpp | pointer1.cpp | cmdline.cpp | temps.cpp | alloc.cpp | realloc.c | factorial.cpp | power.cpp | printld.cpp


Function Overloading

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

Function Overloading
C: no   C++: yes   Java: yes

{TopOfPage} {Resources}


Lifetime and Visibility (scope)

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).

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

Storage Classes
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).

{TopOfPage} {Resources}


Pointers

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

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.

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.

Some final comments:

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.

Programming Loops vs Recursion - Computerphile

What on Earth is Recursion? - Computerphile

Spiked Math Comics

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}


Introduction to Classes

We could spend weeks on the topic of class design. When developing a large program or a system (i.e. a collection of programs that work together to provide a specific application), class design is one of the most critical steps in the software development cycle.

In this course sequence we get an introduction to what classes are and how to create and use them using the C++ programming language.

A class is a blueprint from which objects are instantiated (i.e. created). [Classes are also referred to as models or patterns or templates -- although you should avoid using the term template.]

Objects are instances of a class. Objects have memory allocated for them and are usually considered system resources. Memory is allocated from the heap (or free store).]

Object-oriented programs require you to think of programs as being a collection of objects that work together to provide an application.

Object-oriented design is a software design methodology that models the characteristics of abstract or real objects using classes and objects.

The class declares data the defines the state that objects of the class can take on, and methods that define the behavior that the objects can exhibit or be subjected to.

An object is a software "capsule" containing variables and related methods. The values of the variables define an object's state, and the methods define the behavior an object can be subjected to.

A method is a function defined in a class. C++ classes can contain instance methods and class methods. Class methods are defined to be static.

The public methods of a class defines the API or Application Programmer Interface for the class.

The data that is specific to a particular instance of an object is called instance data. Ideally, clients should not have to beware of the instance data in order to use objects of your class.

A class declaration has the following syntax.

   class SomeClassName {
      private:
         0_or_more_data_members;
         0_or_more_method_members;
      public:
         0_or_more_data_members;
         0_or_more_method_members;
   };

   // class, private and public are C++ keywords

Once an object instantiated (created), messages can be sent to it as follows:

   SomeClassName objectVariable; 

   objectVariable.methodName(...)

Where objectVariable is the name of a variable that stores the data contained within an object, and methodName is the name of a method defined in the class SomeClassName.

objectVariable is referred to as the recipient object. Or here it described as: methodName() is invoked on behalf of objectVariable. Or the methodName message is sent to objectVariable.

The methodName() method is called. If arguments are supplied, then the value of those arguments are passed to the method (the method receives them as parameters). Implicitly, every method that is invoked on behalf of an object (referred to as an instance method), receives a parameter that has the name this. this is an objectVariable that points to the recipient object.

[class example: Time.cpp | Dog.cpp]

When defining instance variables, you should use private as much as possible. Private instance data members can be accessed only by the methods defined in the class.

Making data private provides the following benefits:

By convention, mutator methods begin with the word set. In many cases, set is followed with the name of instance variable.

When you want the client to be able to access private data, then an accessor or getter method is provided.

By convention, accessor methods begin with the word get which it then often following by the name of the instance variable.

Accessor methods are often covert the value of instance variables from their internal representation to types that are usable by the client.

Accessor methods are usually short methods.

{TopOfPage} {Resources}


Home Previous Next