CS 2005 - Notes for students transitioning from CS 1101 to CS 2005

Background

In CS 1101 you wrote programs using DrScheme. Scheme is a functional programming language, that is, it views every task in terms of functions. A function transforms one or more arguments into a single value. In Scheme, the transformation is specified with a (define...), and combinations of transformations are allowed by nesting defined and primitive operators.

In CS 2005 we will be using the programming language C++. We will start by studying the C-language subset of C++ that is defined using the procedural or imperative paradigm. In a procedural language, a program consists of a sequence of statements that transform data by changing the contents of memory cells. In Scheme, the (set!...) operator was used only in specific circumstances. In C, changing the contents of memory by setting variables to new values is at the heart of every programming problem.

We will later expand the C subset to include C++'s object-oriented capabilities. The fundamental idea behind an object-oriented language is to define both data and the functions that operate on that data as a single unit called a class. An instance of a class is called an object. An object-oriented program typically consists of objects that communicate with each other by calling each other's member functions.

Examples: converting Scheme functions to C++ functions

Here are examples of tasks similar to ones you wrote in Scheme for CS 1101, and the corresponding tasks written in C++. We will cover additional examples in the first few class meetings in B-term.

Scheme: write a function that computes a letter grade given a numeric grade, where grades are assigned according to the following conditions:
- grade >= 90 is an 'A
- grade >= 80 but < 90 is a 'B
- grade >= 70 but < 80 is a 'C
- grade < 70 is an 'F
```
;;letter-grade: number -> symbol
;;consumes a number (assume in the range 0 to 100) and produces a letter grade
(define (letter-grade score)
  (cond [(>= score 90) 'A]
        [(>= score 80) 'B]
        [(>= score 70) 'C]
        [else 'F]))
```
C++: write a function that returns a letter grade given a numeric grade (according to the same table as above)
```
//PRE:  score is an int the range 0 to 100
//POST: the function returns a letter grade according to the score
char LetterGrade(int score)
{
  if (score >= 90)
     return 'A';
  else if (score >= 80)
     return 'B';
  else if (score >= 70)
     return 'C';
  else
     return 'F';
}
```
Differences: The type char in C++ is like the type symbol in Scheme, except that a char can be a single character only. The information in the Scheme contract (letter-grade: number -> symbol) is captured in the C++ function heading char LetterGrade (int score). LetterGrade consumes score (an int, one of C++'s numeric data types), and produces a char. In Scheme, the result returned by the function is the symbol specified as the answer to a question in one of the cond clauses. In C++, the result returned by the function is returned by the return statement. The type of the value returned (char)must match the return type of the function (the char in the function heading). The C++ function is commented with pre-conditions and post-conditions. The precondition states the conditions that are required to be true when the function is called. The postcondition states what will be true when the function call is completed.
Scheme: write a function that determines whether or not a symbol is a vowel (one of 'a, 'e, 'i, 'o, 'u)
```
;;is-a-vowel?:  symbol -> boolean
;;consumes a symbol (assume lower-case alphabetic) and produces true if the symbol is a vowel, false otherwise
(define (is-a-vowel? letter)
 (or (symbol=? letter 'a)
     (symbol=? letter 'e)
     (symbol=? letter 'i)
     (symbol=? letter 'o)
     (symbol=? letter 'u)))
```
C++: write a function that determines whether or not a character is a vowel (one of 'a', 'e', 'i', 'o', 'u')
```
//PRE:  letter is a lower-case alphabetic char
//POST: the function returns true if letter is one of 'a', 'e', 'i', 'o', 'u',
//      and returns false otherwise
bool is_a_vowel(char letter)
{
  return (letter == 'a' || 
          letter == 'e' || 
          letter == 'i' || 
          letter == 'o' ||
          letter == 'u');
}
```
Differences: The symbols "||" represent the Boolean operation or in C++ ("&&" is and, and "!" is not). Note that in Scheme, the or operator is used only once in the function definition, but in C++ the || operator connects every relational expression (relational expressions are expressions that evaluate to true or false, and use the relational operators = =, !=, >, >=, <, <=). C++ has strict rules about naming functions and variables. The only characters that can be used in a function or variable name are upper- and lower-case alphabetics, numbers, and underscore. Thus, the name of the C++ function is is_a_vowel, rather than is-a-vowel?
Scheme: write an expression that will create a list containing the numbers 1, 2, 3, 4
```
(cons 1 (cons 2 (cons 3 (cons 4 empty))))
```
C++: write a sequence of statements that will create an array of four integers and initialize the array to contain the values 1, 2, 3, 4
```
int numArray[4];    // create an array large enough to hold four integers
numArray[0] = 1;
numArray[1] = 2;
numArray[2] = 3;
numArray[3] = 4;
```
Differences: In Scheme, a list can grow as large as it needs to be (the size of a list is limited only by the amount of memory on the computer). The end of the list is signified by the use of empty. In C++, the size of an array needs to be chosen at the time the array is created (we'll see ways to get around this restriction later). The programmer needs to keep track of the "end" of the array by keeping track of the number of elements currently in use. Typically, an array is created with some maximum size in mind; the array is created to hold this maximum number of elements, and a separate variable is used to record the number of elements currently in use. Arrays are accessed using an index, or subscript. The index of the first element in an array is 0.
Scheme: using the list defined in the example above, write an expression that extracts the third element of the list
```
(first (rest (rest (cons 1 (cons 2 (cons 3 (cons 4)))))))
```
C++: using the array defined in the example above, write an expression that extracts the third element of the array
```
numArray[2]
```
Differences: C++ has no equivalent to first, rest, or cons. Access to a particular element in an array is done by specifying the index of the element (its position in the array).
Scheme: write a function that takes a number and produces the sum of the numbers from 1 through that number
```
;;sum-up:  number -> number
;;produces the sum of the numbers up to the given number
(define (sum-up anum)
   (cond [(zero? anum) 0]
         [else (+ anum (sum-up (- 1 anum)))]))
```
C++: write a function that takes a number and produces the sum of the numbers from 1 through that number
```
//PRE:  anum is an int greater than 0
//POST: the function returns the sum of the numbers from 1 to anum
int sum_up (int anum)
{
  for (int sum=0; anum > 0; anum--)
       sum = sum + anum;           // this is the loop body
  return sum;
}
```
Differences: Scheme uses recursion to generate the sum of the numbers. C++ uses a loop and a variable that accumulates the sum. Note the three expressions in the for-loop definition. The first expression, int sum=0; serves to initialize the accumulator. The second expression, anum > 0; is the condition that is tested prior to each execution of the loop body. If the condition evaluates to true, the loop body is executed again. If the condition evaluates to false, the loop terminates and the next statement to execute is the one immediately following the loop body. The third expression, anum--, executes after each iteration of the loop body. This expression decrements anum and serves to guarantee that eventually the condition that is tested will evaluate to false (in other words, the loop will eventually stop). Look at the statement in the loop body. C++ evaluates this statement by evaluating the expression on the right-hand-side of the assignment operator (=), and then assigns the value of that expression to the variable on the left-hand-side. So with each execution of the loop body, the answer is built up (accumulates) in the variable sum.
Scheme: write a function that adds the number k to every element of a list of numbers
```
;;add-k:  list-of-number number -> list-of-number
;;consumes a list of numbers and a number k and produces a new list
;;consisting of the elements of the original incremented by k
(define (add-k alon k)
        (cond [(empty? alon) empty]
              [(cons? alon) (cons (+ k (first alon)) (add-k (rest alon) k))]))
```
C++: write a function that adds the number k to every element in an array of integers
```
//PRE:  numbers is an array of int with size elements
//      k is an int
//POST: every element of the array numbers has been incremented by k
void add_k(int numbers[], int size, int k)
{
  for (int i=0; i< size; i++)
      numbers[i] = numbers[i] + k;
  return;
}
```
Differences: in the Scheme version, a brand-new list is created that contains the new values (the Scheme version returns a list-of-numbers). The return type for the C++ version is void. That's because in the C++ version, assignment is used to overwrite the previous values in the array with new values. In the Scheme version, recursion is used to hit each element in the list, and the empty? condition terminates the recursion. In the C++ version, a for-loop is used to sequentially step through the "size" elements of the array from beginning to end.)

Scheme: write an "accumulator-style" program that produces the sum of the numbers in a list

;;sum-accum:  list-of-number number -> number
;;produces sum of numbers in a list, where result so far is in given number
(define (sum-accum alon total)
  (cond [(empty? alon) total]
        [(cons? alon) (sum-accum (rest alon) (+ (first alon) total))]))

;;sum:  list-of-number -> number
;;produces sum of numbers in the list
(define (sum alon)
  (sum-accum alon 0))

C++: write a function that returns the sum of the numbers in an array

//PRE:   numbers is an array of int with size elements
//POST:  the function returns the sum of the elements of the array

int sum(int numbers[], int size)
{
  int total=0;
  for (int i=0; i<size; i++)
      total = total + numbers[i];
  return total;
}

Differences: In C++, summing functions are naturally written accumulator-style. Note that all of the array-processing examples in this handout use a for-loop to step through the elements of the array, as opposed to Scheme's use of first and rest to break apart a list into smaller components.

Executing a C++ program

Let's look at how functions are executed in Scheme and in C++. In Scheme's Interactions Window the function is-a-vowel? is applied to actual arguments and the result is immediately calculated and displayed:

> (is-a-vowel? 'g)
false

Executing a function in C++ is a more complicated process. That is because C++ is a compiled language rather than an interpreted language. In a compiled language, a source file containing both the function definition and the function call is translated and the resulting "object code" is stored in an "object file". This object file can then be loaded into memory and executed. Here is a complete C++ program that defines two functions, is_a_vowel (described above) and main, whose purpose is to call is_a_vowel on user-specified input, and then display a message based on the result of the function call. (The mechanics of entering, compiling, and running a C++ program on the Unix system will be covered in the first lab in CS 2005.)

// Program reads in a character entered at the keyboard, and displays a
// message indicating whether or not the character is a vowel

#include <iostream>              //the cin and cout statements used below are
                                 //defined in the library iostream
using namespace std;             

bool is_a_vowel (char letter);   //this is the function prototype
                                 //it serves a purpose similar to that
                                 //of the contracts you wrote in Scheme

int main()                       //every C++ program begins execution
{                                //in the function main()

  char letterToTest;             //creates a variable to hold the user's input

  // prompt the user for input, and read the character typed by the user into letterToTest
  cout << "Which letter do you want to test?  ";
  cin >> letterToTest;

  // call the function to determine if letterToTest is a vowel or not,
  // and print an appropriate message
  if (is_a_vowel(letterToTest))
     cout << "That letter is a vowel" << endl;
  else
     cout << "That letter is not a vowel" << endl;

  // terminate the main function
  return 0;
}

//PRE:  letter is a char
//POST: the function returns true if letter is one of 'a', 'e', 'i', 'o', 'u',
//      and returns false otherwise
bool is_a_vowel(char letter)
{
  return (letter == 'a' || 
          letter == 'e' || 
          letter == 'i' || 
          letter == 'o' ||
          letter == 'u');
}

If we were to compile and execute this program from a Unix terminal, we would see this interaction:

Which letter do you want to test?  g
That letter is not a vowel

CS 2005 - Notes for students transitioning from CS 1101 to CS 2005

Background

Examples: converting Scheme functions to C++ functions

Executing a C++ program

Further reading