I. translation from Scheme to C++ (or fundamental C++) (H&R Appendix A) A. plan B. caveats C. overview ----------------------------- SCHEME TO C++ OVERVIEW Standard parts of a language: - primitives English: sounds, words Scheme: boolean, number, symbol, string, list, vector C++: int, long, float, double, char... struct, union, array - means of combination English: grammar, punctuation Scheme: if, cond, begin, recursion C++: if, switch, { }, while, for, ... - means of abstraction English: naming Scheme: lambda C++: declaration, function, class, ... --------------------- --------------------- MAIN NEW IDEAS IN C++ Type distinctions: Scheme: number C++: int, short int, long int unsigned int, unsigned short int, ... float, double, long double Scheme: char C++: char, signed char, unsigned char Type declarations: Scheme: (define square (lambda (x) (* x x))) C++: int square(int x) { return x * x; } Finiteness (square doesn't always work) ----------------------------- 1. type distinctions a. scalar types (HR A.6) ------------------------------ SCALAR TYPES IN C++ Enumeration types: enum FlagColor {red, white, blue}; enum Answer {yes, no, maybe}; -------------------- -------------------- Integral types: NAME TYPICAL SIZE LITERALS char 1 byte 'c' '\t' '\n' short int 2 bytes int 2 or 4 228 0342 0x72 long int 4 or 8 -228L ----------------- ----------------- Unsigned Versions: unsigned int 2 or 4 228U unsigned long 4 or 8 228UL Floating point types: float 4 bytes 2.28e2F double 8 bytes 228. .228e3 long double 12 or 16 -2280e-1L ------------------------------ b. structured types (HR A.7) -------------------------- STRUCTURED TYPES IN C++ Product types: Strings "a char string? \'yes\'\n" Arrays int myArray[5]; float myFA[228]; Records struct person { int age; char name[50]; }; ---------------------- ---------------------- Sum (coproduct) types: Unions union float_or_int { int i; float f; }; ---------------------- II. translation from Scheme to C++ (or fundamental C++) (H&R Appendix A) A. expressions 1. translations ---------------- EXPRESSION TRANSLATIONS Scheme: (myfunction 3 4) C++: myfunction(3,4) Scheme: (+ 2 3) C++: 2 + 3 Scheme: (* (+ 2 2) 7) C++: (2 + 2) * 7 Scheme: (add1 i) C++: i + 1 Scheme: (sub1 i) C++: i - 1 Scheme: (/ (mod 44 6) 2) C++: (44 % 6) / 2 ---------------- what is another way to write (a + b) * (a - b) in C++? what is the quadratic formula? can you write down the quadratic formula in C++? 2. example ------------------- PROBLEM Write a program to read in a, b, c, and print the two roots of ax^2 + bx + c = 0 ------------------- a. psuedo-code b. first draft c. fixing type errors where should we get the declaration for sqrt? d. fixing load error (on Unix) e. domain error f. labeling the outputs g. avoiding recomputation (and prompting) how can we avoid the redundancy? how can we avoid the repeated compuations? can you write a program that inputs two numbers, and prints their sum and difference? 3. type coercion (HR A.8) how did we get away with writing 2*a? ------------------------ TYPE PROMOTION (WIDENING) value of smaller type --> value of larger int i = 5; double d = i; // d is 5.0 idea: char --> short --> int --> long --> float --> double --> long double No problems: short --> int --> long unsigned short --> unsigned int --> ... float --> double --> long double Usually safe (may approximate): int --> float int --> double ... -------------------- -------------------- Machine dependent: char --> short char --> int ------------------- 4. type casting (HR A.9) ------------------------ TYPE CAST functional notation: int i = 5; double d = double(i); parentheses notation: unsigned int ui = 5U; unsigned long x = (unsigned long) ui; ------------------------ can you write the roots program with type casts? B. statements and control structures (HR A.13) 1. translations a. assignment --------------------------- STATEMENT TRANSLATIONS Scheme: (set! i 3) C++: i = 3; ------------------------- b. conditionals ------------------------ Scheme: (if (> x 0) (set! s 1) (set! s 0)) C++: if (x > 0) { s = 1; } else { s = 0; } Scheme: (if (< x 0) (writeln "x negative")) C++: if (x < 0) { cout << "x negative" << endl; } ------------------------ ------------------------ STATEMENT TRANSLATIONS 2 Scheme: (cond ((> (f x) 0) (set! s 1)) ((= (f x) 0) (set! s 0)) (else (set! s -1))) C++: if (f(x) > 0) { s = 1; } else if (f(x) == 0) { s = 0; } else { s = -1; } ---------------------- ---------------------- Scheme: (case e ((1 2 3) (set! x 1)) ((4 5 6) (set! x 2)) (else (set! x 3))) C++: switch (e) { case 1: case 2: case 3: x = 1; break; case 4: case 5: case 6: x = 2; break; default: x = 3; break; } ------------------------------ c. watch out! -------------------------- MOST COMMON AND PAINFUL C++ ERROR int alpha; alpha = 5; if (alpha = 3) { cout << "alpha is 3\n"; } else { cout << "alpha isn't 3\n"; } ------------------------- d. quadratic with test to see if root is negative what was a lingering problem with the quadratic formula program? i. variations ii. student exercise ----------------------- FOR YOU TO DO Write a program that inputs 2 integers and outputs their maximum. (Use if.) Include all comments, etc., as for a homework (or test). ----------------------- e. other simple statements ----------------------- OTHER C++ STATEMENTS declaration: int i; double d = 3.14159; null: ; expression: cout << 3 << endl; ----------------------- 2. loop statements ---------------------- LOOPS IN C++ while (n > 1) { if (odd(n)) { n = (3 * n + 1) / 2; } else { n = n / 2; } } do { if (odd(n)) { n = (3 * n + 1) / 2; } else { n = n / 2; } } while (!(n == 1)); // i.e., (n != 1) for (int i = 0; i < 20; i = i+1) { myarray[i] = 0.0; } ---------------------- a. example: quadratic with loop to input until user stops b. example: program which prints numbers from 1 to 10 in order III. expressions (HR A.12) A. operators ------------------------ C++ OPERATORS OP EXAMPLE VALUE Unary: ! !(3==4) - - 3 ++ c++ -- c-- (cast) (int)4.2 Arithmetic: * 2 * 8 / 2 / 8 % 5 % 2 + 3 + 4 - 3 - 4 Shifting, I/O: << cout << 3 >> cin >> i Relational: < 3 < 4 <= 3 <= 4 > 3 > 4 >= 3 >= 4 == 3 == 4 != 3 != 4 ------------------------------ ----------------------------- Logical: && 3>7 && b || 3<7 || b Other: ? : (3<7) ? 3.5 : 7.1 = i = 3 += i += 3 ----------------------------- B. parsing 1. predecence ----------------------------- OPERATOR PRECEDENCE 3 + 4 * 5 < 7 && 5 < - 9 def: higher precedence means ``binds more tightly''. ----------------------------- 2. associativity ------------------------------ ASSOCIATIVITY 3 - 4 - 5 - - 3 a = b = c = 5 ------------------------------ 3. exercises ------------------------------ FOR YOU TO DO Add parentheses to make the precedece and associativity obvious in: (a) 3 * 4 + 5 Answer: (3 * 4) + 5 (b) 3 - 4 / 5. / 6. (c) cout << 3 << 4 * 5 (d) cout << 3 << 4 == 5 ------------------------------ ----------------------------- (e) 0 <= i && i < MAX (f) 0 <= i <= MAX ----------------------------- C. side-effects in expressions -------------------------- EXPRESSIONS WITH SIDE EFFECTS EXPRESSION VALUE EFFECT i = 2 a = b = c = 3 ------------------------- ------------------- c = c + 1 c += 1 ------------------- ------------------- ++c c++ c ------------------- IV. statements (HR A.13) A. syntax 1. overview ----------------------- KINDS OF STATEMENTS expression: cout << 4; declaration: int count = 7; extern double cos(double); empty: ; compound: x = 1; y = 2; block: { int i; i = x + y; x = i; } control: if (alpha == 3) { cout << "it's 3\n"; } ----------------------- ---------------------------- SYNTAX NOTES Statements end in semicolon Generally don't put a semicolon after } but do put a semicolon before } { int i; i = x + y; x = i; } ---------------------------- any question about the details? 2. reading a grammar (HR 6.2, HR Appendix K, DD Appendix A) -------------------------- READING A BNF GRAMMAR Example rules: ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ::= 0 | ::= | ::= -------------------------- can you give some examples of these? ------------------------------ STATEMENT GRAMMAR (A SUBSET OF C++) ::= | | ; | ; | | while ( ) { } | do { } while ( ) ; | for ( ; ){ } | break ; | continue ; | | return ; | return ; ------------------------------- -------------------------------- ::= if ( ) { } | if ( ) { } else { } | if ( ) { } else -------------------------------- ------------------------------- ::= { } ::= | ::= ::= switch ( ) { } | switch ( ) { } ::= | ::= break ; ::= | ::= case : ::= default: break ; | default: ------------------------------- -------------------------- EXTENSIONS TO BNF GRAMMARS Headington and Riley optional text: ::= [ ] zero or more repetitions: ::= { } quotation of terminals: ::= "0" | Deitel and Deitel: optional text: ::= opt -------------------------- B. examples of while loops 1. infinite loops ------------------------------ // powers-of-2.C #include int main() { int i = 1; while (1) { cout << i << "\n"; i *= 2; } // ASSERT: false (never get here) } ---------------------- 2. count char types (switch, while, char input, end-of-file) ----------------------- PROBLEM Write a program to count the number of digits, operators (+, -, *, /) and other characters typed as input. ------------------------ a. psuedo-code outline b. first draft c. commentary on loop initialization (setup) and progress d. C++ details i. cin in tests ii. cin and whitespace iii. side effects in tests and redundancy e. loop body 3. student exercise -------------------------- FOR YOU TO DO Write a program that reads numbers and prints their average. Assume the numbers are type double Assume all inputs are numbers. -------------------------- C. for loops 1. example ------------------------- PROBLEM Write a program that inputs two integers, x and y, with y>0, and outputs x to the y power. ------------------------- a. student exercise --------------------------- FOR YOU TO DO Write a program that inputs an integer n, and outputs sum from 1 to n of 1/(n^2 + 1). Use double precision numbers, and a for loop. --------------------------- D. do loops 1. example (if time) E. break and continue in loops 1. example (if time) V. eliminating recursion (cf. Heddington Ch. 6) A. intro 1. recursion is a good tool for defining certain concepts, thinking ------------------ RECURSIVE DEFINITIONS n! = 1.0, if n = 0 (base) n! = n * (n-1)!, if n > 1 (recursion) dsum(x) = 0, if x = 0 dsum(x) = x%10 + dsum(x/10), if x > 0 ------------------ 2. potentially inefficient a. algorithmic inefficiency b. compilers usually give general, but space inefficient implementation B. operational view of recursion (6.3) ------------------- OPERATIONAL VIEW OF RECURSION double fact(unsigned int n) { if (n == 0) { return 1.0; } else { return n * fact(n-1); } } Control Flow Data -------------------- ------------------------------------- fact(x) x: 3 n * fact(n-1); n: 3 n * fact(n-1); n: 2 n * fact(n-1); n: 1 return 1.0; n: 0 return 1.0; n: 1 return 2.0; n: 2 return 6.0; n: 3 -------------------------------------- -------------------------------------- STACK SNAPSHOTS fact n: 3 main fact n: 2 fact n: 3 main fact n: 1 fact n: 2 fact n: 3 main fact n: 0 fact n: 1 fact n: 2 fact n: 3 main fact n: 1 fact n: 2 fact n: 3 main fact n: 2 fact n: 3 main fact n: 3 main ------------------------------ ------------------------------- INFORMATION STORED WHEN CALLING A (RECURSIVE) C++ FUNCTION For each call, allocate an *activation record* containing: - storage for parameters, with: * values (copies) of value parameters * address of reference parameters - storage for other local variables - return address ------------------------------- C. translating recursion to while-loops via tail-recursion ------------------------------- ELIMINATING RECURSION recursive definition | | straightforward v fully recursive function (psuedo)code | | design sequence using | extra parameters v tail-recursive function (psuedo)code | | standard pattern v iteration coded as a while-loop ------------------------------- 1. example: factorial ---------------------------- DESIGNING THE TAIL RECURSIVE FACTORIAL recursive factorial step: n! = n * (n-1)! 1 recursive call, so add 1 accumulator, f design sequence of steps: f n 1.0 * 4 4.0 * 3 12.0 * 2 24.0 * 1 24.0 done when n = 0 ---------------------------- ---------------------------- TAIL RECURSION // FULLY RECURSIVE FACTORIAL double fact_rec(unsigned int n) { if (n == 0) { return 1.0; } else { return n * fact_rec(n-1); } } // TAIL-RECURSIVE FACTORIAL double fact_it(unsigned int n, double f) { if (n == 0) { return f; } else { return fact_it(n-1, n * f); } } double fact(unsigned int n) { return fact_it(n, 1.0); } ---------------------------- ---------------------------- TAIL RECURSION INTO WHILE LOOP // TAIL-RECURSIVE FACTORIAL double fact_it(unsigned int n, double f) { if (n == 0) { return f; } else { return fact_it(n-1, n * f); } } double fact(unsigned int n) { return fact_it(n, 1.0); } // WHILE-LOOP FACTORIAL double fact(unsigned int n) { // LET oldN = n double f = 1.0; while (!(n == 0)) { // ASSERT: f * n! = oldN! f = n * f; n = n-1; } // ASSERT: n = 0 and f * n! = oldN! return(f); } ---------------------------- 2. example: fibonacci ----------------------------------- FIBONACCI NUMBERS fib(0) = 0 fib(1) = 1 fib(n) = fib(n-1) + fib(n-2), if n > 1. e.g., fib(7) = 13 2 recursive calls, so use 2 accumulators sequence is: acc1 acc2 n i fib(i) 0 1 7 1 1 1 1 6 2 1 1 2 5 3 2 2 3 4 4 3 3 5 3 5 5 5 8 2 6 8 8 13 1 7 13 ----------------------------------- ----------------------------------- FIBONACCI // FULLY RECURSIVE VERSION double fib(unsigned int n) { if (n < 2) { return n; } else { return fib(n-1) + fib(n-2); } } // TAIL RECURSIVE VERSION double fib_it(unsigned int n, double acc1, double acc2) { if (n == 1) { return acc2; } else { return fib_it(n-1, acc2, acc1 + acc2); } } double fib(unsigned int n) { if (n == 0) { return n; } else { return fib_it(n, 0.0, 1.0); } } --------------------------- --------------------------- FIBONACCI CONTINUED // TAIL RECURSIVE VERSION double fib_it(unsigned int n, double acc1, double acc2) { if (n == 1) { return acc2; } else { return fib_it(n-1, acc2, acc1 + acc2); } } double fib(unsigned int n) { if (n == 0) { return n; } else { return fib_it(n, 0.0, 1.0); } } // WHILE LOOP VERSION double fib(unsigned int n) { } ----------------------------------- 3. summary, the general case ------------------------------- GENERAL TRANSLATION OF TAIL RECURSION T tail_rec_fun(S x, T acc) { if (base_case(x)) { return acc; } else { tail_rec_fun(to_base(x), to_ans(x, acc)); } } T the_fun(S x) { ... tail_rec(x, init); ... } T the_fun(S x) { T acc = init; ... while (!(base_case(x))) { acc = to_ans(x, acc); x = to_base(x); } return acc; ... } ------------------------------- ------------------------------- SHORTCUT METHOD FOR IMPLEMENTING RECURSIVE DEFINITIONS 1. add accumulators, design sequence of variable values 2. use the form of the tail recursion *translation* as outline for the while-loop version ------------------------------- 4. exponentiation ------------------- FOR YOU TO WRITE USING A WHILE LOOP dsum(x) = 0, if x = 0 dsum(x) = x%10 + dsum(x/10), if x > 0 unsigned int dsum(unsigned int x) -------------------- VI. declarations (A.10-11) A. definitions vs. decarations (A.11, page A-29) ------------------------ DEFINITIONS VS. DECLARATIONS declaration: tells the reader about the properties of a name extern int square(int i); extern int count; definition: is a declaration that also gives a value for the name, or allocates storage int square(int i) { return i * i; } int count; ------------------ B. definitions (A.10) --------------------------- DEFINITIONS Constants: const char BLANK = ' '; const double PI = 3.141593; Variables: char b; char c = 'c'; double root; ----------------------------- ----------------------------- Types: enum FlagColor {red, white, blue}; typedef int miles; typedef char *string; Functions: void prompt(string promptstring) { cout << promptstring << flush; } ----------------------------- C. scope rules (A.11) 1. scope units ---------------------------- SCOPES IN C++ local to a block: if (discriminant > 0) { double sqrt_d = sqrt(discriminant); ... } // sqrt_d declaration not visible file scope: extern void prompt(string promptstring); ... int main() { ... prompt("a? "); ... } Scope of a declaration extends from point of declaration to end of block or file (as appropriate). ---------------------------- 2. lifetime of variables ------------------------ VARIABLE LIFETIME def: the lifetime of a variable is the time when it's active. automatic storage class (default): int j; int i = f(whatever); lifetime is from time of definition to time when block exited initialized each time, initializer arbitrary expression. static storage class: static double foo; static int count = 0; lifetime is from start of program execution to the end of the program. initialied only once, initializer constant expression -------------------------