CSC302 2006S, Class 6: Why Functional Programming?

Admin:
* Absent: Alex (sick)
* No readings.  Yay!
* Real homework (due next Friday)
* Strange/fun example today
* Discuss your solutions to 'homework'

Overview:
* Key points from Graham and McCarthy.
* More on higher-order functions.
* Other reflections on the readings.

New Homework
* Due 5 p.m. next Friday.
* Implement neweval that supports lambda and define
* Start with the cons, car, cdr, nil, null?, atom, eq, quote, cond,
  of Scheme - C grade
* First implement cons, car, etc. in Java or C/C++/Assembly.  
  Does not need a user interface. - B grade
* Add input and output (and, perhaps, read/eval/print loop) OR
  add garbage collection to the C/C++/Assembly version - A grade

Homework solutions
* Specification of expt(x,n) for non-negative n
  * expt(x,0)  = 1
  * expt(x,2k) = square(expt(x,k))
  * expt(x,k+1) = x * expt(x,k)  // k even
* Sam's recursive
(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)))))))
* Your iterative
  * Common solution: Brad Use an accumulator
  * Dimitar; Similate the stack
* Conclusion: Converting recursive to iterative is not straightforward - more programming time, more chance of errors

Key Ideas of Scheme

* Conditionals - Clearly clearer than conditional gotos
* Higher-order functions - Do they ease code writing?  Could introduce programming errors.  Affect readabilty (for dumb readers that are still smart enough to read LISP, and therefore smarter than the typical econ major).  Adds level of complexity.  Harder for progrmmer to predict efficiency of code.
* Recursion 
* Dynamic typing - W&H would hate it; They like strong compile-time typing
* Garbage collection - Positive.  Simplifies task for programmer.  But, shifts control (efficiency issue).
* Programming through expressions
  * Vs. many languages which distinguish statements from expressions
* Symbol type
* S-expressions - Trees
* "The whole language there all the time"; Can write it in itself ; eval
* Partial functions - Function only defined on part of its domain

Higher-Order Functions, Revisited

* Functions that take functions as params or return functions as values (or both)
* Also 'functions as first class data'
* Common ones:
  * compose ((compose f g) x) => (f (g x))
  * map (map f (v1 ... vn)) => ((f v1) (f v2) ... (f vn))
  * left-section - fills in the first argument of a binary function
    (left-section + 2) - a function that adds 2
  * right-section - fills in the right argument
    (righ-section - 5) - a function that subtracts 5
  * Why?
    (map! (left-section + 2) grades)
    vs.
    (let ((addtwo (lambda (x) (+ 2 x))))
      (map! addtwo grades))