4. Computation
"If [a program] doesn't have to produce correct results, I can make it arbitrarily fast." -- Gerald M. Weinberg
4.1 Computation
 
                        - All programs "compute": they run on computers, after all! And all they do can be called computation.
- But: we can usefully break down this truism and say that different parts of a program compute based on input from another part, and then output the result to be used by some other part.
- So we can view our programs as pockets of computation connected by I/O channels.
- Inside a program, the inputs are often called arguments and the outputs are called results.
- So our refined view of our programs is:
 
                        4.2 Objectives and tools
 
                        We want to express computations:
- Correctly
- Simply
- Efficiently
These are the requirements of professionalism! And the order matters: no one cares if a program is fast at getting the wrong answer. And it can be correct and fast, but if it is too complex to understand, no one will be able to maintain it.
Our chief tool for organizing our programs is to break up large problems into smaller ones. This divides into two variations:
- Abstraction: hide messy details behind a simple interface.
- "Divide and conquer": break up the problem we have to solve into smaller problems, each of which is easier to solve then the big problem.
                        We break up our code into discrete "chunks" because a
                        1000-line chunk of code will have far more than 10
                        times the bugs as ten 100-line chunks of code.
                        Also, we should use existing tools, such as libraries,
                        whenever possible: someone else wrote and debugged it
                        for us!
                        iostream is a great example of this: if we
                        had to deal with the I/O hardware directly, we might be
                        writing hundreds of lines of code to do so.
                    
4.3 Expressions
 
                        - An expression computes a value from a number of operands.
- The simplest expression is a literal value, such as 10, "Hello NYU students", or 2.71828.
- 
                            The names of variables are also expressions.
                            
 int length = 20;
 In the above, a literal (20) is used to initialize a variable.
 
                        4.3.1 Constant expressions
                            We often have the idea of some constant value we
                            want to name, but we don't want ever to be changed;
                            for instance, pi can't change in the
                            course of a program, so we can write:
                            
                            
                                constexpr double pi = 3.14159;
                            
                            
                            After that, we can just use pi
                            whenever we need that value. And if we at some
                            point need more precision, we can just add it to
                            the constexpr and not need to roam
                            around our program changing it in many spots.
                        
                            C++ also has the idea of a
                            const the value of which is not known
                            at compile time, but can't be changed after it is
                            set. So:
                            
                            
                                const c2 = n + 7;
                            
                            
                            The value of n won't be known until
                            the code is run, but once c2 is set to
                            n + 7, it can't be changed later on.
                        
4.3.2 Operators
Operators serve to combine literal or variable values to create a new value. Here are the most common operators:
| Operator | Name | Explanation | 
|---|---|---|
| f(a) | function call | pass a to f as an argument | 
| ++lval | pre-increment | increment and use the incremented value | 
| --lval | pre-decrement | decrement and use the decremented value | 
| !a | not | result is bool | 
| -a | unary minus | negates a | 
| a*b | multiply | |
| a/b | divide | |
| a%b | modulo (remainder) | only for integer types | 
| a+b | add | |
| a-b | subtract | |
| out<<b | write b to out | where out is an ostream | 
| in>>b | read b from in | where in is an istream | 
| a<b | less than | result is bool | 
| a<=b | less than or equal | result is bool | 
| a>b | greater than | result is bool | 
| a>=b | greater than or equal | result is bool | 
| a==b | equal | result is bool | 
| a!=b | not equal | result is bool | 
| a && b | logical and | result is bool | 
| a || b | logical or | result is bool | 
| lval = a | assignment | avoid confusion with == | 
| lval *= a | compound assignment | also works with /, + and - | 
4.3.3 Conversions
 
                            We can "mix" different types in expressions: what is the type of the result? There are rules for this. For instance:
- 
                                5/2is2
- 
                                2.5/2means2.5/double(2)==1.25
- 
                                'a'+1meansint{'a'}+1
                            type(value)
                            and
                            type{value}
                            mean "convert value
                            to type.
                            The difference between them is that the version
                            with squiggly braces {} prevents narrowing, but the
                            one with parentheses () does not.
                        
Be careful not to write something like:
                        
                            
                        
double dc;
cin >> dc;
double df = 9/5*dc+32;
                            
                        
                        9/5 is equal to 1, not 1.8!
                        Write 9.0/5.0 to get the result you want.
                        
4.4 Statements
A statement is the next level of C++ language structure up from an expression. The simplest statement is just an expression followed by a semi-colon:
                    
                            a=b;
                            
                    
                            ++b;
                    
                        When statements simply follow each other, the computer
                        executes them in order. We typically want statements to
                        have an effect:
                        
                        3+3;
                        
                        is a useless statement, since it has no effect on the
                        state of future computations.
                    
                        A common error: accidentally create an empty statement,
                        e.g.:
                        
                        if(x==5);
                        
                            { y = 3; }
                        
                        The programmer meant to assign
                        3 to y only if
                        x equaled
                        5, but the "extra" semi-colon
                        means y is set to 3
                        regardless.
                    
Code that just executes statements in order is a bit... boring. We want to be able to select what statements to execute, and excute some statements many times. Let's see how to do those things.
4.4.1 Selection
 
                            
                            The simplest form of selection is an
                            if statement, which selects between
                            two alternatives; for instance, here is code that
                            returns the maximum of two values: 
                        
                        
                            
                        
int max(int a, int b)
{
    if(a<b)
        return b;
    else
        return a;
}
                            
                        
                            The notion is simple: if a condition is true, do
                            one thing, else if it is false, do another. If the
                            class you want is available, register for it, else,
                            choose a different class:
                            
                            if(my_choice==available) choose_it();
                            
                        
                            else choose_another();
                            
                            When we have many alternatives to choose among, it
                            may be clearer to express them in a
                            switch statement, like this:
                        
                        
                            
                        
switch (grade) {
case 'A':
    cout << "You done great!"
    break;
case 'B':
    cout << "That's pretty good."
    break;
case 'C':
    cout << "Not bad, but we hope for better."
    break;
case 'D':
    cout << "Consider retaking the course."
    break;
case 'F':
    cout << "You're going to have to retake the course."
    break;
}
                            
                        
                            When many cases should result in the same behavior,
                            then omitting the break statement can
                            merge those cases:
                        
                        
                            
                        
                                switch (num) {
                                case '0': case '2': case '4': case '6': case '8':
                                    cout << "Digit entered was even.";
                                    break;
                                case '1': case '3': case '5': case '7': case '9':
                                    cout << "Digit entered was odd.";
                                    break;
                                default:
                                    cout << "That wasn't a digit".
                                }
                            
                        
Switch technicalities:
- The value switched on must be a character, integer, or enumeration type. You can't switch on strings or other more complex objects.
- 
                                The values in the caselabels must be constants.
- 
                                No two caselabels can have the same value.
- 
                                You can use several caselabels for a single case.
- 
                                Typical source of bugs: forgetting to use a 
                                breakwhen you don't want to drop through to the next case. The compiler will think you meant to do 4. above.
Drill
                            Write a program that accepts some input from a
                            range, like letter grades, and then uses a
                            switch statement to reply with a
                            message based on the input.
                        
4.4.2 Iteration
 
                            Iteration executes the same (block) of statements repeatedly. (Hopefully, this stops at some point!) The two C++ looping constructs are:
                                The while statement
                            
                        A while loop that prints the first 100 squares of integers:
                        
                            
                        
int main()
{
    int i=0;
    while(i<100) {
         cout << i << '\t' << square(i) << '\n';
         i++;
    }
}
                            
                        
Drill
                            Write a program that uses a while
                            loop to print the ASCII value of all lowercase
                            letters, relying on the fact that 'b'
                            is 'a' + 1.
                            
Blocks
                                Blocks in C++ are set off by 
                                { some code; }: we often
                                call those "squiggly braces".
                                They delimit what is done inside an
                                if, for,
                                while statement, or a function.
                                They aren't needed when what is to be done
                                is only a single statement. (See for loop below
                                for an example.)
                            
                                The for statement
                            
                            
                                When we want to loop over a sequence of
                                numbers, C++ offers a more concise form than
                                the while statement: the
                                for statement:
                            
                        
                            
                        
int main()
{
    for(int i=0; i<100; ++i)
        cout << i << '\t' << square(i) << '\n';
}
                            
                        
Drill
                            Write a program like the previous one,
                            but that uses a for
                            loop to print the ASCII value of all 
                            letters, both upper and lower.
                            
4.5 Functions
 
                        
                        What was square() in the code above?
                        It is a function. A function is a named sequence
                        of statements, that may accept one or more
                        arguments and it may return a value.
                        Here is a possible definition of square:
                    
                    
                        
                    
int square(int x)
{
    return x*x;
}
                        
                    
                        What does all that mean? Well, the first bit says this
                        function will return an int value to its
                        caller. square is the name of the
                        function, the name that can be used to call it. And
                        int x says that the function will require
                        and only accept a single argument, x, that
                        must be an integer. And the function body is the
                        block between the squiggly braces, here
                        return x*x, that actually does the work.
                    
4.5.1 Why bother with functions?
- Makes the computation logically separate
- Make the program logically clearer (by naming the computation)
- Makes it possible to use the function in more than one place
- Eases testing (we can test functional units separately)
                            Why use square() instead of a function
                            named print_square() that both
                            squares a number and then prints it?
                            
                            Basically, we want a function to do one thing, not
                            two, as then we can use it in more places: e.g,
                            where we just want to square a number but then use 
                            the result in another computation without printing
                            it.
                        
4.5.2 Function declarations
                            We must differentiate between function
                            declarations and function
                            definitions.
                            The declaration of a function need only announce
                            the type it returns, its name, and the types of its
                            arguments. The function definition must include how
                            it carries out its work. Often in our programs, we
                            just want to mention the declaration part of a
                            function, so the compiler knows if we are using it
                            wrongly, and not include the definition, which may
                            live in some third-party library. We typically do
                            that in header files, with the extension ".h".
                            
                            A function declaration looks like:
                            
                            int square(int);
                        
                    4.6 vector
                    
                    Programs typically need a collection of data to work on, say, to calculate the average shooting percentage of all NBA basketball players, we need a list of how many shots each player took, and how many he made. To catalogue a library, we need a list of books in it.
                        A vector is one of the simplest and most
                        useful ways of storing data. It is a sequence of
                        elements you can access by an index, like this:
                    
 
                        
                        We access the elements by "indexing" the  vector,
                        starting from position 0, so in the above case,
                        v[0] is 5, 
                        v[1] is 7, 
                        and so on.
                    
4.6.1 Traversing a vector
                            We can traverse a vector as follows:
                        
                        
                            
                        
vector<int> v = {5, 7, 9, 4, 6, 8};
for(int i = 0; i<v.size(); i++)
    cout << v[i] << '\n';  
                            
                        
                            To traverse a vector we need to
                            traverse the half-open sequence v[0]
                            to v[v.size()-1].
                        
C++ has a built-in way to loop over everything in a half-open sequence:
                        
                            
                        
vector<int> v = {5, 7, 9, 4, 6, 8};
for(int x : v)
    cout << x << '\n';  
                            
                        
                            This is called a range-for-loop, since range
                            is a synonym for "a sequence of elements."
                            
                            More complicated loops involving vectors are
                            tyoically better coded in the traditional for-loop
                            style listed above.
                        
4.6.2 Growing a vector
                            We grow a vector by using its 
                            push_back() method. For instance, this
                            code:
                        
                        
                            
                        
vector<double> v; // empty vector! 
v.push_back(2.7);
v.push_back(5.6);
v.push_back(7.9);
                            
                        
Results in:
 
                            
                            push_back() is a member
                            function of the class vector.
                        
Drill
                            Write a program that uses a while 
                            loop to accept a series of integers
                            from the user, adds them as new elements to a
                            vector, and then, once the user ends input, prints
                            out the vector with a for loop.
                        
4.6.3 A numeric example
To illustrate a somewhat realistic example of growing a vector, we're going to read in a series of values and calculate their mean.
                        
                            
                        
#include "std_lib_facilities.h"
int main()
{
    cout << "Enter recent temperatures and we will calculate their average:\n";
    vector<double> temps;
    for(double temp; cin>>temp; )
        temps.push_back(temp);
    double total = 0.0;
    for(double temp : temps)
        total += temp;
    double mean = total / temps.size();
    cout<<"Your mean temperature for the last "<<temps.size()<<" days was "<<mean<<'\n';
    keep_window_open();
    return 0;
}
                            
                        
Drill
                            Modify the above program, using the 
                            sort() facility to also get the
                            median temperature.
                        
4.6.4 A text example: Drill
                            Write a program that accepts a series of words as
                            input and writes out a concordance, a 
                            list of all the words in the text, in alphabetical
                            order, along with how many times each word
                            occurred.
                            
                            Hint: Use the sort function
                            provided in std_lib_facilities.h 
                            to do this.
                        
Drill
                            Modify the mean temperature program to produce
                            a concordance of words, listing each word in a text
                            in alphabetical order, along with the number of
                            times it occurred in the text. (Hint: You will find
                            sort() useful here as well.)
                        
4.7 Language features
                        We were able to do a lot using a few fundamental
                        language features: if, while,
                        for, cout, cin,
                        and a few functions and variables. That's the idea!
                    
Test Yourself!
 
                        - Which of these operators can be used on integers but not floating point numbers?
- /
- +
- %
- -
- *
- Which of the following operators requires an lvalue?
- +=
- %
- +
- /
- Which of the following operations can be used on an int but not a string?
- +
- /
- +=
- The first part of the header of a for loop...
- is done each time around the loop.
- initializes the loop variable.
- determines when the loop terminates.
- We should prefer a switch statement to if and else statements when...
- we only have two options to consider.
- there are many cases to consider.
- the conditions for the branches are string comparisons.
- What is the index of the third element of a vector?
- 4
- 2
- 3
- can't say
- If a function is declared as int f(double x); that means...
- it doubles the value of its argument x and then converts it to an int.
- the name of the function is int and it applies the operator f to a double.
- it returns an int and accepts a double as an argument.
Answers
1. c; 2. a; 3. b; 4. b; 5. b; 6. b; 7. c;
Drill
