CSC302 2006S, Class 5: Why Functional Programming? Admin: * More LISP readings. Yay! * Please use spell checkers! (E.g., ispell on Linux) Overview: * More examples from Hoare. * Key points from Graham and McCarthy. * Other reflections on the readings. * More on higher-order functions. /Hoare Examples/ * What is the point of the multiply(A,A,A) example? * Suppose we have a method, multiply(X,Y,Z) that means 'multiply Y by Z and store the result in X', X := Y*Z that X,Y, and Z are NxN matrices, that matrices are passed by reference (necessary for changing X) What is wrong with multiply(A,A,A)? - We change A during the computation, leading to incorrect results in the rest of the matrix. Conclusion: Aliasing is dangerous * What is the point of "Suppose X is a refernce variable" * 'X := Y' always changes X * 'X := Y + 1' never changes X * CONTEXT: Implicit language actions (particularly coercion) * For numbers int i; float f; f = i; is considered acceptable, even though we have not explicitly said "convert i from int to float" * In Algol-68, pointers were also coerced. Suppose ip is a pointer to an integer * ip := 5; * To a C programmer: "Make ip point at memory location 5" * To an Algol programmer, "Store 5 in the contents of the memory location pointed to by ip" * ip + 1 * To a C programmer: The location in memory after ip. * To an Algol programmer: "Get the contents of the memory location that ip points to, add 1" (If following the previous command, the expression has the value 6.) * ip := i * To a C programmer: Make ip point to the memory location whose value is stored in i. * To an Algol programmer: Make ip point to i; Store the location of i in ip. * ip := jp * To both C and Algol programmers: Make ip and jp point to the same memory location. /Why Recurse?/ * Recursive programs can be shorter void count() { count-helper(1); } void count-helper(n) { if (n < 0) { printf("%d\n", n); count(n + 1); } } void count() { for (int i = 0; i < 100; i++) printf("%d\n", n); } * Sometimes recursion provides an easier way to phrase a sol'n. * Quicksort Partition the array into small and large Sort the two halves * In Scheme (define qs (lambda (ls) (if (null? ls) null (append (qs (select ls (lambda (val) (<= val (car ls))))) (list (car ls)) (qs (select ls (lambda (val) (> val (car ls))))))))) * Exponentiation expt(x,0) = 1 expt(x,2k) = square(expt(x,k)) expt(x,k+1) = x * expt(x,k) // k even * Need to compute 2^1000 * Compute 2^500 * Compute 2^250 * Compute 2^125 * Compute 2^124 * Compute 2^62 * Compute 2^31 * Compute 2^30 * ... * This algorithm is logarthmic in the exponent, that is computing x^n is in O(log_2(n)) (define expt (lambda (x n) (cond ((zero? n) 1) ((even? n) ((lambda (r) (* r r)) (expt (x (/ n 2))))) (else (* x (expt x (- n 1))))))) * Challenge: Phrase this efficient alg. iteratively (in C or Java or ...) FOR FRIDAY! * Moral: Some algorithms are more naturally phrased (and therefore implemented) recursively.