CSC151 2007S, Class 41: Higher-Order Procedures, Summarized

Admin:
* Questions on next homework?
* Missing office hours again (hopefully the last time this semester)
  * I should be around this weekend
* Sorry about the reading confusion.
  * Tomorrow's reading is available
* EC for Home track meet this weekend
* EC for camping out in the Joe Rosenfield '25 Center on Tuesday
  evening to encourage the College to raise tuition to pay for the
  cost of staffing Joe's Quarter 24/7.
* EC for baseball home game this weekend 50th anniversary of baseball
  at Grinnell!

Overview:
* Background: Guiding Principles.
* Background: Writing Similar Code.
* Procedures as Parameters.
* Anonymous Procedures.
* Procedures as Return Values.
* Encapsulating Control.
* Final Thoughts.

Past week
* Generated some interesting "pictures"
* Learned some programming techniques - Rubric of "Higher Order Programming"
  * Basic idea: A procedure can be a value, just like an integer or a list or ...
  * What does this mean?
    * You can pass procedures as parameters to other procedures!
    * You can write procedures without naming them (anonymous)
    * You can return procedures as results
  * Today: How and why

Background: Design Principles
* Concision - Try to write shorter programs that do the same thing
  * Potentially easier to proofread
  * Potentially easier to change
  * Potentially more efficient
  * Potentially easier to understand
* Refactoring - Don't write the same thing twice
  * Instead, write one procedure that "encapsulates" the common code
FIRST STRATEGY
(define add-five-to-each
  (lambda (lst)
    (if (null? lst)
        null
        (cons (+ 5 (car lst))
              (add-five-to-each (cdr lst))))))
(define add-ten-to-each
  (lambda (lst)
    (if (null? lst)
        null
        (cons (+ 10 (car lst))
              (add-ten-to-each (cdr lst))))))
REFACTORED
(define add-to-each
  (lambda (num lst)
    (if (null? lst)
        null
        (cons (+ num (car lst))
              (add-to-each num (cdr lst))))))
(define add-five-to-each
  (lambda (lst)
    (add-to-each 5 lst)))
(define add-ten-to-each
  (lambda (lst)
    (add-to-each 10 lst)))
  * Advantages of refactored
    * If I later decide to add a different number, I'm set.
    * And if there are more than two times i want to add numbers, I start
    seeing a net gain in the number of lines to write.
    * Once you've written add-to-each, you might not even need to write
    the other two programs.
    * Easier to correct errors
* Don't name things that don't have to be named.
  * E.g., don't name intermediate results in a computation
   (/ (sum grades) (length grades))

   vs.

   (let ((sum-of-grades (sum grades))
         (numgrades (length grades)))
     (/ sum-of-grades numgrades))

The three key aspects of higher order programming
* Procedures can be parameters to other proceduers
* Procedures can be anonymous
* Procedures can be returned from other procedures

/Procedures can be Parameters/

(define foo
  (lambda (proc)
    (proc ...)))

Silly example

(define apply-to-zero-and-one
  (lambda (proc)
    (proc 0 1)))

> (apply-to-zero-and-one +)
1
> (apply-to-zero-and-one *)
0
> (apply-to-zero-and-one list)
(0 1)
> (apply-to-zero-and-one max)
1
> (apply-to-zero-and-one floor)
. floor: expects 1 argument, given 2: 0 1
> (apply-to-zero-and-one divide)
. reference to undefined identifier: divide

Readings ...
* We can use this idea for map, which takes a procedure as the
  first parameter
* We used this idea for color-grid 
  (define foo (lambda (x y) x))
  (define bar (lambda (x y) (* 256 (sin (/ x 100)))))
  (define baz (lambda (x y) (* 5 (+ x y))))
  (color-grid 100 100 10 10 foo bar baz)

* Does this help with 
  * concision?
  * avoiding identical code?
  * naming?
* Once we learn anonymous procedures, it can help with all
  three

/Procedures don't need names/

* Particularly when passed as parameters
  * Problem: Call "apply-to-zero-and-one" using a procedure
    that squares both parameters and then computes the
    square root
    (define square-both-and-then-root
      (lambda (a b)
        (sqrt (+ (* a a) (* b b)))))
    (apply-to-seven-and-eleven square-both-and-then-root)
  * Vs.
    (apply-to-seven-and-eleven (lambda (a b) (sqrt (+ (* a a) (* b b)))))

; Map: Part of every Scheme programmer's toolbox

(define map
  (lambda (proc lst)
    (if (null? lst)
        null
        (cons (proc (car lst))
              (map proc (cdr lst))))))

To add five to each element of a list
(map (lambda (x) (+ 5 x)) lst)

Consider
 (map (lambda (x) (* x x)) (list 1 2 3 4 5))
 How does it know what to put in for x?
 (define square (lambda (x) (* x x)))
 (map square (list 1 2 3 4 5))
* Step one: What does map do?
  Make proc a name for square
  Make lst a name for (1 2 3 4 5)
* Step two: Is the list null? NO
* Step three
  (cons (proc (car lst))
        (map proc (cdr lst)))
* Approximately sixty eight hidden steps
  (cons (proc (car lst))
        (4 9 16 25))
* Next step
  * car lst is 1
  (cons (proc 1)
        (4 9 16 25))
* Next step: look up proc
  * proc is square
  (cons (square 1)
        (4 9 16 25))
* Inside square, make x a name for 1
* Inside square, computes (* x x)
* Inside square, substitutes 1 for x
  (* 1 1)
* Inside square, does the multiplication and finishes
* Back in map
  (cons 1
        (4 9 16 25))
* Result is (1 4 9 16 25)

Suppose that we hadn't use square, but instead had use 
(lambda (x) (* x x))

...
  (cons ((lambda (x) (* x x)) 1)
        (4 9 16 25))
* The anonymous procedure makes x a name for 1
* The anonymosu procedure then evaluates its body
  (* x x)
* The anonymous procedure looks up x
  (* 1 1)
* Computes result

Anonymous procedures plus procedures as paramters let you
write "do X to each element of a list" very concisely

/Procedures can return procedures/

A silly procedure

; Return a procedure of one parameter that adds x to its parameter
(define add-x
  (lambda (x) ; parameter to add-x
    (lambda (param) ; parameter to the unnamed returned procedure
      (+ x param))))

> (add-x 5)
#<procedure>
> (map (add-x 5) (list 1 2 3 4 5))
(6 7 8 9 10)
> (define f (add-x 5))
> (f 5)
10
> (f 11)
16
>