.. highlight:: c++

Chapter 5 Notes
===============

Please read chapter 5 of the textbook.


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

recall that a ``void`` function is a function that doesn't return a value

::

    void greet(string name) {
        cout << "Hi " << name << "!\n";
    }

``void`` is not a data type, e.g. you *cannot* declare a variable to be
``void``

instead, it indicates that a function has no return value

if necessary, you can use ``return;`` (with no value before the ``;``) inside
a ``void`` function to immediately jump out of it

::

    void greet(string name) {
        cout << "Hi " << name << "!\n";
        return;  // optional
    }


Functions with No Inputs
------------------------

you can also have functions that take no inputs

such functions may, or may not, also be ``void``

::

    string url_prefix() {
        return "http://";
    }

    void ping() {
        cout << "ping!\n";
    }


Passing Parameters by Value
---------------------------

in what follows we'll use this function as an example

::

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

consider this code fragment

::

    double a = 2.0;
    cout << square(a) << "\n"; // 4.0
    cout << a << "\n";         // 2.0


when ``square(a)`` is called, a **copy** of the value in ``a`` is assigned to
``x`` in the function

this is way of passing parameters to functions is know as **pass by value**

it is the default way that all parameters are passed in C++ (and C)


Passing Parameters by Value
---------------------------

the value passed to ``square`` is a *copy* of the original value

thus, **a variable that is passed by value cannot be modified by the function
it is passed to**

so we can't do this::

    void set_zero(double x) {
        x = 0.0;  // sets the local x to 0
    }

    // ...

    double a = 5.0;
    set_zero(a);  // runs, but a doesn't change

there's no change to ``a`` because the actual value ``a`` refers to is not
passed to ``set_zero``

a copy of the value is passed and assigned to ``x``

``x`` does get set to 0, but this does not affect the value of ``a``

so ``set_zero`` does nothing!


Passing Parameters by Value
---------------------------

another issue with pass by value is that making a copy takes time and memory

::

    bool starts_with_dot(string s) {
        if (s.empty()) {
            return false;
        } else {
            return s[0] == '.';
        }
    }

``s`` is passed by value, which means a copy of the passed in string is made
and assigned to ``s``

if the passed-in string is big, this wastes time and memory

::

    if (starts_with_dot("some big huge multi-megabyte string ...")) {
        // ...
    }


Passing Parameters by Reference
-------------------------------

C++ provides a solution to these problems

it lets you pass parameters by **reference** if you like

**passing by reference** gives the function the actual value being passed

no copy is made when a parameter is passed by reference

::

    void set_zero(double& x) {  // note the &; x is passed by reference
        x = 0.0;
    }

    int main() {
        double a = 5.6;
        cout << "a = " << a << "\n"; // 5.6
        set_zero(a); 
        cout << "a = " << a << "\n"; // 0.0
    }

in C++, a ``&`` after the type name in the parameter will cause that parameter
to be passed by value


Passing Parameters by Reference
-------------------------------

this function is quite useful

::

    // exchanges the values of a and b
    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }

sorting vectors/arrays of data is often done by repeatedly calling this
``swap`` function

take a moment to trace through this carefully, step by step; compare it to a
version where the ``&`` characters are removed


Passing Parameters by Reference
-------------------------------

another use of pass-by-reference parameter is to get back multiple values from
a function

a function can only *return* a single value

but with pass-by-reference it can essentially "send back" any number of values

::

    void get_point(double& x, double& y, double& z) {
        cout << "What is x? ";
        cin >> x;
        cout << "What is y? ";
        cin >> y;   
        cout << "What is z? ";
        cin >> z;
    }

    void print_point(double x, double y, double z) {
        cout << "(" << x << ", " << y << ", " << z << ")\n";
    }

    int main() {
        double a = 0.0;
        double b = 0.0;
        double c = 0.0;
        get_point(a, b, c);
        print_point(a, b, c);
    }

notice that ``print_point`` uses pass-by-value, and not pass-by-reference

that's because ``print_point`` does not (and should not) change ``x``, ``y``,
or ``z``

passing-by-reference would not have much (if any) benefit here, and it opens
the door for errors related to accidentally changing ``x``, ``y``, or ``z``

also, if we used pass-by-reference we would **not** be able to write
statements like this

::

    print_point(1, 2, 3);  // compile-time error: can't pass ints by reference
                           // only variables can be passed by reference

you should only use pass-by-reference when you have a clear, concrete reason
for needing it


Passing Parameters by Reference
-------------------------------

when thinking about how C++ functions work, it's useful to consider the same
function but with parameters passed in different ways

::

    void set_zero1(int n) {   // n passed by value
        n = 0;
    }

    void set_zero2(int& n) {  // n passed by reference
        n = 0;
    }

    // ...

    int a = 4;
    int b = 5;

    set_zero1(a);   // a not changed
    set_zero2(b);   // b set to 0


Passing Parameters by Constant Reference
----------------------------------------

passing by **constant reference** lets you pass parameters by reference

but it does **not** let you *modify* those parameters (they are constant)

::

    void say_hello(const string& name) {  // note the use of const
        cout << "Hello, " << name << "!\n";
    }

the compiler ensures that the body of the function doesn't modify ``name``; it
will report an error if ``name`` is modified inside of ``say_hello``

no copy of ``name`` is made, so it is efficient


Specifying Functions with Pre and Post Conditions
-------------------------------------------------

functions are one of the key building blocks of C/C++ programs

we want functions to be efficient, readable, and easy to use

so it is often useful to very carefully specify what a function does

here we will see how we can use **pre-conditions** and **post-conditions** to
clearly explain what a function does


Specifying Functions with Pre and Post Conditions
-------------------------------------------------

::

    // Pre-condition:
    //     none
    // Post-condition: 
    //    The values of a and b are exchanged.
    void swap(int& a, int& b) {
        int temp = a;
        a = b;
        b = temp;
    }

the **pre-condition** says what must be true just **before** the function is
called

the **post-condition** guarantees what will be true **after** the function
finishes (assuming the pre-condition was true when it was called)

for ``swap``, there are no special pre-conditions on either ``a`` or ``b``,
i.e. you can pass in any ``int``\ s at all

so there is no pre-condition beyond the basic requirement that two ``int``\_s
be passed to it

the post-condition explains how the variables are changed after the function
is called


Specifying Functions with Pre and Post Conditions
-------------------------------------------------

::

    // Pre-condition: 
    //    radius > 0
    // Post-condition: 
    //    Returns the area of a circle with the given radius.
    double circle_area(double radius) {
        return 3.14 * radius * radius;
    }

the ``circle_area`` function has a pre-condition: ``radius`` must be greater
than 0

it never makes sense to have a circle with a radius of 0 or less

it's often useful to check the pre-condition inside the function

::

    // Pre-condition: 
    //    radius > 0
    // Post-condition: 
    //    Returns the area of a circle with the given radius.
    double circle_area(double radius) {
        if (radius <= 0) {
            cmpt::error("radius must be positive");
        }
        return 3.14 * radius * radius;
    }

now this function will crash if you give it an invalid ``radius``

that might seem harsh, but while *developing* a program we almost always want
the program to stop as soon as it knows there is an error

otherwise the program could continue computing nonsense values that are harder
to debug because their cause can be so far away from where they appear as
errors

in a correctly working program, function pre-conditions should *never* be
violated


Specifying Functions with Pre and Post Conditions
-------------------------------------------------

recall that we saw earlier in the course how to calculate the square root of
number without using the standard C++ ``sqrt`` function

here is that code inside a function

::

    // Pre-condition: 
    //    a >= 0, and precision > 0
    // Post-condition: 
    //    Returns a value x such that x * x is approximately equal to s,
    //    the true square root of a. It is guaranteed that
    //    abs(x - s) <= precision.
    // Example:
    //    my_sqrt(5, 0.001) will return the square root of 5 accurate 
    //    to two decimal places
    double my_sqrt(double a, double precision = 0.0001) {
        if (a < 0) {
            cmpt::error("can't take square root of a negative number");
        }
        if (precision <= 0) {
            cmpt::error("precision must be positive");
        }

        double prev_x = a;
        double x = a / 2;   // initial estimate of square root
        while (abs(x - prev_x) > precision) {
            prev_x = x;
            x = (x + a / x) / 2.0;
        }
        return x;
    }

the pre-condition makes explicit the valid and invalid values of the
parameters we can pass to ``my_sqrt``

in this case it's also relatively easy to check the pre-conditions inside the
function


A Few Small Functions
---------------------

::

    // Pre-condition:
    //    none
    // Post-condition: 
    //    returns the smaller of x and y
    double min(double x, double y) {
        if (x < y) {
            return x;
        } else {
            return y;
        }
    }

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns the smaller of x, y, and z
    double min(double x, double y, double z) {
        return min(x, min(y, z));
    }

in this case we have two functions named ``min``

but they have different parameters, so C++ will always know which one is being
called

note how the second function uses the previous ``min`` function to  calculate
its answer

this is good: it is clear and efficient

compare it to this version

::

    // Pre-condition:
    //    none
    // Post-condition:
    //    returns the smaller of x, y, and z
    double min(double x, double y, double z) {
        if ((x <= y) && (x <= z)) {
            return x;
        } else if ((y <= x) && (y <= z)) {
            return y;
        } else {
            return z;
        }
    }

this version also works, but the logic is more complicated and harder to read


Testing
-------

**testing** is an important topic in computer program

if you don't test your programs, how do you know they work?

usually, it's impossible to test all possible inputs to a function since there
are too many

for example, consider this function

::

    double calc(double x, int n)

assuming that ``double`` is 64 bits, and ``int`` is 32 bits, thats 96 bits of
input to this function

there are, exactly, :math:`2^{96}` different patterns for those 96 bits

this is exactly 79228162514264337593543950336 different possible inputs to
``calc``, i.e. about :math:`7.9 \times 10^{29}` different input patterns

suppose we could test 1 trillion calls to ``calc`` per second

then testing all :math:`2^{96}` different inputs would take over 2.5 billion
years to run


Testing
-------

so instead of testing all possibilities, we can usually only test a few cases

it's important to try to choose good tests cases

for example, very *common* inputs are often good test cases: make sure your
function works well for the most common cases

*boundary values* are also often good tests cases, e.g. values around some
natural boundary point in the input

for example, for ``int``\_s, -1, 0, 1, ``MIN_INT``, ``MIN_INT`` + 1,
``MAX_INT``, ``MAX_INT`` - 1

that can still be quite a few test cases, e.g.

::

    double calc(int a, int b, int c)

using just the extreme values above, this would result in :math:`7 \cdot 7
\cdot 7 = 7^3 = 343` test cases

most programmers would probably not test a function with so many cases

unless, perhaps, the function was very important


Testing
-------

``my_abs(x)`` should return the absolute value of ``x``

::

    double my_abs(double x) {
        if (x < 0) {
            return -x;
        } else {
            return x;
        }
    }

this implementation is pretty simple, and it's hard to see how it could be
wrong

there should be at least three test cases: a negative value, 0, and a positive
value

e.g. ``my_abs(-14)`` should equal 11, ``my_abs(289)`` should equal 289, and
``my_abs(0)`` should equal 0

this tests only a tiny fraction of possible inputs

but those tests, combined with the implementation that looks correct, should
give us confidence in its correctness


Test Drivers
------------

another useful technique is to test a function using a **driver program**

for example, lets write a driver for this function we wrote earlier

::

    // min_driver.cpp

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

    using namespace std;

    // Pre:
    // Post: returns the smaller of x, y, and z
    double min(double x, double y, double z) {
        if ((x <= y) && (x <= z)) {
            return x;
        } else if ((y <= x) && (y <= z)) {
            return y;
        } else {
            return z;
        }
    }

    int main() {
        for (;;) { // infinite loop
            cout << "Enter 3 doubles: ";
            double x = 0.0;
            double y = 0.0;
            double z = 0.0;
            cin >> x >> y >> z;
            cout << "min(" << x << ", " << y << ", " << z << ") = "
                 << min(x, y, z)
                 << "\n";
        }
    }

recall that ``for(;;)`` is an infinite loop

ctrl-C will end the program

the idea is to type in values to check that their output is correct


Function Stubs
--------------

as we mentioned earlier, **top-down design** is often a good way to design a
program

the idea is to start with a general, high-level description of the program

and then progressively refine that description to be more and more low-level

one way to do this to use function stubs

a function stub is a function with the proper header but with a body that does
nothing useful (yet)

here's a very general example of function stubs

::

    void print_intro() {
        cout << "Intro will be printed here\n";
    }

    void get_input() {
        cout << "get input here\n";
    }

    void process_input() {
        cout << "process input here\n";
    }

    void display_output() {
        cout << "display output here\n";
    }

    int main() {
        print_intro();
        get_input();
        process_input();
        display_output();
    }

notice that the ``main`` function reads almost like English

the logical structure is quite clear

all the details are hidden inside the functions

it also lets us run the program without having implementations for all the
functions


Debugging
---------

recognizing, finding, and fixing errors in programs is a major part of
programming

here we offer some general advice for debugging

- use ``cout`` statements to print the values of variables; for more
  complicated programs, you may also use a debugger, such as ``gdb``, or a
  debugger in your IDE

- keep an open mind: sometimes errors are due to trivial typing mistakes, or
  fundamental misunderstandings, or something you think can't possible be the
  case is the case

- don't be quick to assume there's an error with the compiler; compiler's
  definitely do have errors, but they are so rare in the sorts of programs we
  are writing that you can, practically speaking, assume they never occur

- narrow down the region where an error could occur (checking pre-conditions
  and post-conditions can help with this)