.. highlight:: c++

Chapter 4 Notes
===============

Please read chapter 4 of the textbook.


Top Down Design
---------------

designing big programs is a *very* challenging task

we won't be designing big programs in this course

but it is useful to start thinking about systematic ways to create programs

one way to design a program is to use **top-down design**

top-down design starts with the general problem and then splits it
into smaller sub-parts

each sub-part is refined into more and more detail, eventually reaching the
level of program code


Top Down Design
---------------

suppose you want to design a program to read a file of numbers and print their
sum and average

top-down design goes like this

#. (first version) read in numbers, print statistics

#. (more refined) open file, read in numbers, print statistics

#. (more refined) open file, use a loop to read numbers from a file, print
   statistics

#. (more refined) open file, use a loop to read numbers from a file, keep
   track of sum and count as numbers read in, print statistics

#. (more refined) open file, initialize sum and count variables, use a loop to
   read numbers from the file, keep track of sum and count as numbers read in,
   print statistics

etc.

the basic idea is to replace each part of such a design with a **function**


Function Terminology
--------------------

if possible, it's often best to implement parts of your program using pre-
defined functions

they are often faster and more accurate than functions you create yourself

``cmath`` has many useful basic math functions, e.g. see p. 187 of the
textbook for a list of some

confusingly, a few functions, like ``abs`` and ``rand``, are found in
``cstdlib``

of course, we can't always rely on pre-defined functions being the solution to
all are problems

(what if your job is to create these pre-defined functions for a new
compiler?)


Function Terminology
--------------------

we need some terminology for talking about functions

consider the pre-defined ``sqrt`` function from ``cmath`` as an example

``sqrt(x)`` is a **function call** or **function invocation**, i.e. we are
calling, or invoking, ``sqrt``

``x`` is the function's **argument**, i.e. the input to the function

``sqrt(x)`` **returns** some value, i.e. it evaluates to the square root of
``x``

all pre-defined functions have documentation, e.g.
http://www.cplusplus.com/reference/cmath/sqrt/

the documentation specifies things like the exact type of the arguments and
the exact type of the return value


Random Number Generation
------------------------

generating random numbers is useful and interesting

we collectively refer to the sub-programs that are used to get random numbers
as a **random number generator** (sometimes abbreviated RNG)

one basic C++ random number generator uses two functions, ``srand`` and
``rand``

``srand`` initializes the random number generator and should be called once at
the start of your program

``rand`` returns a new random number

.. note:: Since at least C++11, C++ has come with the standard library
   ``<random>``, which contains a much better and more flexible collection of
   random number generators. However, they are more difficult to use, and
   since this is a beginning course, we will stick to ``rand`` and ``srand``.


Random Number Generation
------------------------

this program prints 10 random numbers

::

    #include "cmpt_error.h"
    #include <iostream>
    #include <cstdlib>

    using namespace std;

    int main() {
        srand(532);  // set random number seed

        for(int i = 0; i < 10; ++i) {
            int r = rand();
            cout << r << "\n";
        }

        cout << "RAND_MAX = " << RAND_MAX << "\n";
    } // main

``srand`` takes a an ``unsigned int`` as input, and does not return any value

it's job is to initialize the random number generator

``rand()`` takes no input, but every time you call it returns a new random
number

``rand()`` always returns an ``int`` from 0 to ``RAND_MAX``, where
``RAND_MAX`` is a pre-defined value that is the largest value that ``rand()``
can return

the sequence of numbers ``rand()`` returns on each call depend upon the value
given to ``srand``

using the same seed, you can re-create the same sequence of calls to
``rand()`` (which can be quite useful for debugging)


Random Number Generation
------------------------

if you run the program multiple times, you'll always get the **same** sequence
of numbers

that's because the seed to ``srand`` is always the same

to get different numbers on each run, you need to give ``srand`` a different
seed each run

a common trick for doing this is to use the current time

::

    #include "cmpt_error.h"
    #include <iostream>
    #include <cstdlib>

    using namespace std;

    int main() {
        srand(time(NULL));  // set random number seed based on current time

        for(int i = 0; i < 10; ++i) {
            int r = rand();
            cout << r << "\n";
        }

        cout << "RAND_MAX = " << RAND_MAX << "\n";
    } // main


Random Number Generation
------------------------

often you want a random number between two given numbers

for instance, to simulate rolling a (fair!) 6-sided die, choose a random
number from 1 to 6

::

    int roll = 1 + (rand() % 6);

``rand() % 6`` returns a value from 0 to 5 (inclusive)

so ``1 + (rand() % 6)`` returns a value from 1 to 6

the expression ``4 + (rand() % 6)`` returns a value from 4 to 9 (inclusive)


Random Number Generation
------------------------

::

    // guesser.cpp

    #include "cmpt_error.h"
    #include <iostream>
    #include <cstdlib>
    #include <time.h>

    using namespace std;

    int main() {
        srand(time(NULL));  // set random number seed based on current time

        // secret is a randomly chosen number from 1 to 10
        int secret = 1 + rand() % 10;

        cout << "I'm thinking of a number from 1 to 10. Can you guess it?\n";

        int guess = 0;
        while (guess != secret) {
            cout << "What is your guess? ";
            cin >> guess;
        }

        cout << "That's right, you got it!\n";
    } // main


Type Casting
------------

C++ often needs to convert between different types of values

sometimes, C++ automatically coverts types

::

    int a = 4.9;   // 4.9 automatically converted to the int 4
    double b = 7;  // 7 automatically converted to the double 7.0

C++ lets you explicitly convert between types of data using function-like
expressions, and this process is known as **type casting**

there is old C-style casting and new C++-style casting

::

    double x = static_cast<double>(5);  // new-style C++ casting: prefer this style

    double y = double(5);               // older C++-style casting

    double z = (double) 5;              // C-style casting

all three statements do the same thing

in C++, the first one with ``static_cast`` is probably the best, because it is
the clearest and most explicit

but you will often see the other 2 in practice


Type Casting
------------

::

    double a = 1 / 5;  
    // 1 / 5 is 0, which is converted to 0.0

    double b = static_cast<double>(1 / 5); 
    // 1 / 5 is 0, and this is explicitly cast to 0.0

    double c = 1.0 / 5; 
    // 5 is converted to 5.0, and 1.0 / 5.0 is 0.2

    double d = 1 / 5.0; 
    // 1 is converted to 1.0, and 1.0 / 5.0 is 0.2

    double e = 1.0 / 5.0; 
    // no conversion since 1.0 and 5.0 are both doubles

it's important to note that ``static_cast<double>`` is always safe

that means converting from an ``int`` to a ``double`` never loses any
information


Type Casting
------------

casting a ``double`` to an ``int`` could lose information

::

    int f = static_cast<int>(3.14);  // f gets the value 3
    int g = static_cast<int>(2.99);  // g gets the value 2


.. note:: In addition to ``static_cast``, C++ has other kinds of casting
   functions including ``dynamic_cast`` (used with pointers and references),
   ``reinterpret_cast`` (converts pointer types), and ``const_cast`` (for
   manipulating ``const`` values). However, in this course we will only be
   using ``static_cast``.


Defining Functions
------------------

C++ lets you define your own functions

defining functions is familiar in mathematics

for example, :math:`f(x) = x^2`

we say :math:`f` is a function

we can use it to do calculations

like :math:`f(3) = 3^2 = 9`

or :math:`f(1 + f(2)) = f(1 + 2^2) = f(5) = 5^2 = 25`


Defining Functions
------------------

C++ lets you define many mathematical-type functions

and also many other kinds of functions that have no mathematical counterpart

for example, the ``main()`` function we use in every program is not a
mathematical function


Defining Functions
------------------

here's a C++ equivalent of :math:`f(x) = x^2`

::

    double square(double x) {  // function header (or signature)
        return x * x;          // function body
    }

the top line of the function is called the function **header**, or
**signature**

the header of a function contains the information you need to know to *call*
the function

the part between the ``{`` and ``}`` is called the function **body**

it contains the code that is run when the function is called


Function Headers
----------------

lets look at just the header of the function

::

    double square(double x) {
        // ...
    }

the name of this function is ``square``

like variables, functions should usually have clear, self-descriptive names

the ``double`` before the name is the type of value that the function will
return when it is called

``square`` takes one input which it calls ``x``

``x`` has type ``double``


Function Bodies
---------------

now lets look at the body of the ``square`` function

::

    double square(double x) {
        return x * x;
    }

the variable ``x`` is passed as a parameter to ``square``, and so we can use
it anywhere in the body

it's as if we had defined ``x`` at the very start of the function

inside a function, ``return`` indicates the value the function will evaluate
to

when a ``return`` statement is executed, the flow of control jumps out of the
function

so if we had put any statements after ``return`` they would not be executed

in this case our function body has only a single statement, but in general
bodies can have any number of statements


Defining Functions
------------------

::

    // square.cpp

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    // returns the square of x
    double square(double x) {
        return x * x;
    }

    int main() {
        cout << "Please enter a number: ";
        double x = 0.0;
        cin >> x;

        cout << "square(" << x << ") = " << square(x)
             << "\n";
    } // main


Another Function
----------------

here's a function that calculates the distance between two 2-dimensional
points

::

    // returns the distance between the points
    // (x1, y1) and (x2, y2)
    double dist(double x1, double y1, double x2, double y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        return sqrt(dx * dx + dy * dy);
    }

look at just the header

::

    double dist(double x1, double y1, double x2, double y2)

from this we can tell that the function's name is ``dist``

that it returns a ``double``

that it takes 4 inputs, all of type ``double``


Another Function
----------------

notice also that the body consists of three different statements

::

    // returns the distance between the points
    // (x1, y1) and (x2, y2)
    double dist(double x1, double y1, double x2, double y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        return sqrt(dx * dx + dy * dy);
    }

we've also declared two **local variables** in this function

``dx`` and ``dy`` are local variables

they only exist in the function

C++ automatically deletes them when the function ends


Functions Return Values
-----------------------

it's important the you use the proper terminology when talking about a
function

we say that a function **returns** a value

functions don't *print values* (unless they happen to use ``cout``)

*printing* means causing something to appear on the screen

returning means ending a function and providing a return value


Where do functions get their inputs from?
-----------------------------------------

::

    // returns the distance between the points
    // (x1, y1) and (x2, y2)
    double dist(double x1, double y1, double x2, double y2) {
        double dx = x1 - x2;
        double dy = y1 - y2;
        return sqrt(dx * dx + dy * dy);
    }

where do the value of ``x1``, ``y1``, ``x2``, and ``y2`` come from?

the could come from anywhere

maybe from ``cin``

or a file

or from the return value of some other functions

or as literals written directly in source code of the function call

...

when you call ``dist``, that's when you must provide the values of ``x1``,
``y1``, ``x2``, and ``y2``


Boolean functions
-----------------

a function whose return type is ``bool`` is called a *boolean function*

::

    bool is_digit(char c) {
        if (c >= '0' && c <= '9') {
            return true;
        }  else {
            return false;
        }
    }

recall that ``char``\ s are like small integers, with the integers
representing the character's numeric ASCII/Unicode value

it turns out that the ASCII/Unicode values of the characters ``'0'``, ``'1'``,
..., ``'9'`` are in sequential order

::

    for(char c = '0'; c <= '9'; ++c) {
        cout << "'" << c << "' = " << static_cast<int>(c) << "\n";
    }

this prints

::

    '0' = 48
    '1' = 49
    '2' = 50
    '3' = 51
    '4' = 52
    '5' = 53
    '6' = 54
    '7' = 55
    '8' = 56
    '9' = 57

this means that, for instance, the ASCII/Unicode value of ``'5'`` is 53

the expression ``c >= '0'`` asks if the ASCII/Unicode value of ``c`` is bigger
than, or equal to, the ASCII/Unicode value of ``'0'``

some programmers even write the expression as ``c >= 48``, because 48 is the
code for ``'0'`` (but that's pretty confusing!)

similarly, the expression ``c <= '9'`` asks if the ASCII/Unicode value of
``c`` is less than, or equal to, the ASCII/Unicode value of ``'9'``


Boolean functions
-----------------

the function body is more verbose than necessary

``c >= '0' && c <= '9'`` is a boolean expression because it evaluates to
either ``true`` or ``false``

so we could just return its value

::

    bool is_digit(char c) {
        return c >= '0' && c <= '9';
    }

many programmers like this style, but it takes some getting used to

it's short, simple, and fast (only 2 comparisons!)


void Functions
--------------

a function that doesn't return a value uses the keyword ``void`` in place of a
type for its return value

::

    void print_title() {
        cout << "BIOS Diagnostics Screen\n"
             << "-----------------------\n\n";
    }

``void`` is **not** a type, e.g. variables and values cannot be ``void``

sometimes, ``void`` functions are called **procedures** to distinguish them
from functions that return a value

but we'll just call them ``void`` functions


Functions as Black Boxes
------------------------

almost all well-designed programs use, and define, a lot of functions

a well-made function is sometimes referred to as a **black box**

you put input into the black box, and the black returns some output

because the box is black, you can't see inside of it

but that's okay, we can still use it

try to write functions that act like a black box

programmers should not need to know how a function is implemented in order to
use it

for example, we don't need to know exactly *how* C++ implements its ``sqrt``
function in order to use it in our programs; we only need to know *what* it
does


Functions as Black Boxes
------------------------

functions that work as black boxes often need some documentation explaining
**what** they do

for example, the documentation for ``sqrt`` tells us that it returns the
square root of a number

it says nothing about *how* it actually calculates the square root

for our functions, we will usually write documentation to make it clear to the
programmer what the function is supposed to do


Local and Global Variables
--------------------------

a variable declared inside a function is called a **local variable**

local variables can only be used inside the function in which they are defined

**global variables** are defined outside of any function

they can be used by any function

here are some global variables

::

    const double PST_RATE = 0.07;
    const double GST_RATE = 0.05;

    int main() {
        cout << "What is the cost of your purchase? ";
        double cost = 0.0;
        cin >> cost;

        double total_tax = (PST_RATE + GST_RATE) * cost;
        double total_cost = cost + total_tax;

        cout << "The tax is $" << total_tax << "\n";
        cout << "The total cost is $" << total_cost << "\n";
    } // main

the globals have been declared ``const``, which means the compile does not
allow them to be changed (i.e. they are read-only)

this can help stop you from making certain kinds of errors

traditionally, constant global C++ variables are written in ALL_CAPS so they
can be recognized at a glance


Local and Global Variables
--------------------------

experience shows that global variables can lead to subtle bugs

since any code could modify a global variable, it can be hard to see how they
change in a large program

the Java language doesn't even have traditional global variables!

**rule of thumb**: if you must use global variables in C++, make them
``const``

it will make your programs easier to understand, and prevent a subtle class of
errors


Function Parameters are Local Variables
---------------------------------------

the parameters in a function act like local variables

they come into existence when the function is called

and disappear when the function is returned

they can't be accessed outside the function


Block Scope
-----------

the scope of variable where in a program a variable is accessible

C++ use block scope, i.e. variables are accessible inside the inner-most block
in which they are defined

``{`` and ``}`` usually mark the begin and end of a block (an exception is an
if-statement or loop that consists of a single --- then the braces are
optional)

note that C++ global variables are not inside any block, and so they are
accessible anywhere


Overloading Function Names
--------------------------

C++ lets you give two different functions the same name as long as they have
different input parameters (so that C++ can tell them apart)

for example

::

    // constraint x to be in the range 0.0 to 1.0
    double clip(double x) {
        if (x < 0.0) {
            return 0.0;
        } else if (x > 1.0) {
            return 1.0;
        } else {
            return x;
        }
    }

    // constraint x to be in the range lo to hi
    double clip(double x, double lo, double hi) {
        if (x < lo) {
            return lo;
        } else if (x > hi) {
            return hi;
        } else {
            return x;
        }
    }

notice that if you've written the second general-purpose ``clip`` function
the other one could be written like this

::

    // constraint x to be in the range 0.0 to 1.0
    double clip(double x) {
        return clip(x, 0.0, 1.0);
    }

another example

::

    int twice(int n) {
        return 2 * n;
    }

    string twice(string s) {
        return s + s;
    }

by checking the type of the input parameter, C++ can always tell which
function to call


C++ Functions are Not Mathematical Functions
--------------------------------------------

even relatively simple-looking C++ functions can behave in ways that break the
rules of how mathematical functions behave

::

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    //////////////////////////////////////////////////////////////////////////////
    //
    // WARNING!
    //
    // This is an example of how functions in C/C++ can behave differently than
    // functions in mathematics. The functions f and g are artificial examples of
    // the weird things functions can end up doing. They are not examples of how
    // you should actually write functions in real programs!
    //
    //////////////////////////////////////////////////////////////////////////////

    int f_count = 0;

    int f(int n) {
        f_count++;
        return n + f_count;
    }

    bool g_called_with_1 = false;

    int g(int n) {
        if (n == 1) {
            g_called_with_1 = true;
        }
        if (g_called_with_1) {
            return 1;
        } else {
            return n;
        }
    }

    int main() {
        // Shows that calling the same function more than once doesn't necessarily
        // result in the same value being returned.
        cout << f(1) << "\n";  // 2
        cout << f(1) << "\n";  // 3

        // Some mathematical simplifications cannot be used because they change
        // the number of times a function is called.
        cout << f(2) + f(2) << "\n";  // 15
        f_count = 0;
        cout << 2 * f(2) << "\n";     // 6
        f_count = 0;

        // The order in which you call functions can make a difference.
        cout << g(1) + g(2) << "\n";  // 2
        g_called_with_1 = false;
        cout << g(2) + g(1) << "\n";  // 3
    }

the problem here is that the behaviour of functions ``f`` and ``g`` depends in
part on the values of global variables


C++ Functions are Not Mathematical Functions
--------------------------------------------

here's another C++ function that doesn't really have a mathematical
counterpart

::

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    bool loop_forever() {
        cout << "loop_forever called ...\n";
        for(;;) { 
            // runs forever ...
        }
        cout << "... loop_forever done\n";
        return true;
    }

    int main() {
        int x = 5;
        if (x > 0 || loop_forever()) {
            cout << "loop_forever not called!\n";
        }
    } // main


C++ Functions are Not Mathematical Functions
--------------------------------------------

a function that calls ``cmpt::error`` does not return

instead, we say that the function has **thrown an exception**

::

    #include "cmpt_error.h"
    #include <iostream>

    using namespace std;

    int twice(int n) {
        cout << "twice(" << n << ") called ...\n";
        if (n < 0) error("n is negative");
        cout << "... twice(" << n << ") done\n";
        return 2 * n;
    }

    int main() {
        int a = twice(1) + twice(-2) + twice(3);
        cout << "a = " << a << "\n";
    } // main

this shows that when an exception is thrown, a function does not return in the
normal sense

instead, the function is immediately exited


Function Side Effects
---------------------

when a function "communicates" with the rest of a program if it modifies some
non-local value, or performs an action (such as printing to the screen) that
has some noticeable effect

common **side effects** include: modifying a global variable, printing to the
screen (or a file)

some side effects, such as printing, or obviously important and useful

but they can lead to unexpected behaviour

consider this code fragment

::

    char a() { 
        cout << "a() called\n";  // side effect
        return 'a'; 
    }

    char b() { 
        cout << "b() called\n";  // side effect
        return 'b'; 
    }


    int main() {
        cout << a() << "\n"
             << b() << "\n";
    }

compiling this with g++ on my computer, the program prints the following

::

    b() called
    a() called
    a
    b

this shows that function ``b`` is called before function ``a``

just because ``a()`` appears before ``b()`` in the ``cout`` statement does not
guarantee that ``a()`` is called first

C++ does not guarantee in what order functions are evaluated when they are use
with ``cout`` and ``<<`` as in this example

some compilers might evaluate ``a()``, while others (such as g++) might
evaluate ``b++`` first

the order of evaluation is not specified by C++, and so the compiler is free
to evaluate them in whatever order is most convenient