I. introduction to abstraction section (HR introduction) what is abstraction? What is it good for? --------------------------- ABSTRACTION The idea: user (client) === specification === implementation --------------------------- --------------------------- KIND OF ABSTRACTION \ HIDES functional algorithm data rep + algorithms control flow details --------------------------- II. control abstraction (HR 1) A. goals of chapter 1 B. control structures ------------------------- CONTROL STRUCTURES ARE ABSTRACTIONS 160 IF I >= J GO TO 163 161 LET I = I + 3 162 GO TO 160 163 LET K = 5 while (I < J) { I = I + 3; } K = 5; 170 LET X = I 171 LET Y = J 172 GO SUB 500 173 LET Z = X Z = max(I, J); ------------------------- 1. gotos 2. when to use what C. functional abstraction ------------------------ FUNCTIONAL ABSTRACTION function specification separates: behavior (what it does) from implementation (how it does it) double sqrt(double x) // PRE: x >= 0.0 // POST: FCTVAL is approximately the // positive square root of x ------------------------ 1. side effects (functions vs. procedures) ------------------------- SIDE EFFECTS def: a *side effect* of a function is any change to an object (variable) made by the function ---------------------------- what operators in C++ have side-effects? 2. parameter passage ------------------------- PARAMETER PASSAGE parameter values may flow: NAME EXPLANATION C++ FORMAL in in to a function int in out out of a function int &out inout in and out int &inout -------------------------- a. parameter modes --------------------------- in and out parameters void assign2(int& v1, int& v2, int e1, int e2) // MODIFIES: // POST: { v1 = e1; v2 = e2; } -------------------------- -------------------------- example of use: int a = 4; int b = 5; assign2(a, b, b + 3, a); ------------------------- ---------------------- inout parameters #include "assign2.h" void swap(int& x, int& y) // MODIFIES: // POST: { assign2(x, y, y, x); } ----------------------- ----------------------- example of use: int c = 28; int d = 200; swap(d, c); ----------------------- b. passing arrays ------------------------------ ARRAY PARAMETERS Arrays are passed by reference void initialize(int a[], int size) // PRE: size >= 0 // MODIFIES: // POST: { for (int i = 0; i < size; i++) { a[i] = 0; } } ------------------------------ -------------------------------- CONST PARAMETERS int array_sum(const int a[], int size) // PRE: size >= 0 // MODIFIES: // POST: FCTVAL is the sum of the // elements a[0] ... a[size-1]. { int total = 0; for (int i = 0; i < size; i++) { total += a[i]; } } -------------------------------- c. exercise ------------------------------- FOR YOU TO DO fill in the comments below: void sq_each(int arr[], int maxi) // PRE: // MODIFIES: // POST: { for (int i = 0; i < maxi; i += 1) { arr[i] *= arr[i]; } } then answer: what is the mode of each parameter? (in, out, inout?) ------------------------------- III. top down design (HR 1.3) A. context ---------------------- STEPS IN WRITING A PROGRAM 1. Decide what is to be done (requirements) 2. Design a program to do that (specification) 3. Implement the design (development or coding) 4. Validate the implementation (testing and verification) ---------------------- B. stepwise refinement ------------------------------ DESIGN STRATEGIES def: a *top-down design* proceeds by breaking a large problem into smaller ones, each of which is again broken down until each bit is easy to code. --------------------- --------------------- def: *stepwise refinement* involves concentrating on one subproblem at a time. SLOGANS: Divide and conquer. Separate concerns. Postpone details. Don't keep everything in your head at once. Debug at each level of refinement. ------------------------------ 1. example (HR pp. 37-46) --------------------------- EXAMPLE PROBLEM Sort up to 100 integer inputs in ascending order. ---------------------------- a. requirements ---------------------------- REQUIREMENTS ANALYSIS --------------------------- Where do the inputs come from? Where to place the answer? What if less than 100 values? How does input end? Should we prompt? Anything else? b. top-level design how shall we store the data? does that seem to work? c. first refinement d. recording design decisions about helping functions e. top-down testing (using stubs) f. refinement steps for each function can you write InputVec and OutputVec? 2. exercise (if time) IV. testing (HR 1.4, 1.5) A. strategies ------------------------- TESTING STRATEGIES top-down: make stubs for each function test main, then functions bottom-up: write test harness for each function test functions, then main ------------------------- B. test oracles ------------------------------- TEST ORACLE Input values Predicted Output ================================ 4 9 7^D 4 7 9 87^D 87 99 100^D 99 100 ^D ------------------------------- ------------------------------- EVALUATING TEST ORACLES Correct outputs predicted? Covers boundary conditions? Covers error cases? Covers all code in the program? Covers all meaningful kinds of input? Covers some "average" cases? ------------------------------- V. specification and correctness (HR 1.6) A. the correctness problem ------------------------------ CORRECTNESS OF PROGRAMS ret_type my_fun(arg_type x) // PRE: precondition // MODIFIES: object-list // POST: postcondition def: a function is *correct* if it has the specified interface, and when called with arguments that satisfy its precondition: a. it terminates b. it has changed no objects that are not listed following MODIFIES c. the postcondition is satisfied ------------------------------ 1. assertions, state -------------------------------- SATISFACTION OF ASSERTIONS // ASSERT: i > 7 states: i: [ 6 ] i: [ 8 ] i = 7; // ASSERT: i > 6 i = i + 1 // ASSERT: i > 7 ---------------------------- 2. post-conditions -------------------------------- // POST: i > i pre-state: i: [ 22 ] post-state: i: [ 23 ] pre-state: i: [ 22 ] post-state: i: [ 22 ] -------------------------------- -------------------------------- CORRECT OR NOT? extern int z; int foo(int x, int& y) // PRE: x > 0 // MODIFIES: y // POST: y == y * 2 * x // && FCTVAL == y + 7 // (a) int foo(int x, int & y) { y = (y + y) * x; return y + 4 + 2 + 1; } // (b) int foo(int x, int & y) { if (x < 0) { foo(x, y); } else { y = y * 2 * x; } return y+7; } // (c) int foo2(int x, int & y) { y = y * 2 * x; return y+7; } ----------------------- B. correctness of while loops (loop invariants) When writing a recursive (or iterative) function in Scheme, what did you think about? 1. deleting a conjunct -------------------------- CORRECTNESS OF WHILE LOOPS DELETING A CONJUNCT Problem: without using % or /, implement void quotient_remainder(int & q, int & r, int x, int y) // PRE: 0 <= x && 0 < y // MODIFIES: q, r // POST: 0 <= r && r < y // && q * y + r = x -------------------------- 2. replacing constants with fresh variables ---------------------------- CORRECTNESS OF WHILE LOOPS 2 REPLACING CONSTANTS WITH VARIABLES problem: void arr_min(int b[], int size, int & x) // PRE: size > 0 // MODIFIES: x // POST: x is the minimum element of // b[0..size-1] ---------------------------- What does that post-condition mean more formally? How to establish the INV? What variables involved? 3. summary ------------------------------- SUMMARY OF LOOP IDEAS Try to find an invariant by 1. deleting a conjunct from the desired postcondition 2. If that doesn't work, try replacing constants with variables Questions: What changes? (loop test) What relationship maintained? (invariant) How to establish the invariant? How to make progress while maintaining the invariant? ------------------------------- ------------------------------- WHAT INV ASSERTIONS MEAN // INV: 0 <= r && q * y + r = x while (!(r < y)) { r = r - y; q = q + 1; } means // ASSERT: 0 <= r && q * y + r = x while (!(r < y)) { // ASSERT: 0 <= r && q * y + r = x r = r - y; q = q + 1; // ASSERT: 0 <= r && q * y + r = x } Headington and Riley's notation: while (!(r < y)) { // INV (before test): // 0 <= r && q * y + r = x r = r - y; q = q + 1; } -------------------------------