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.