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)
#
> (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
>