CSC151 2007S, Class 23: Pause for Breath (2): A Review of Procedures
Admin:
* Exam 1 returned. Not quite consistent with Friday's discussion.
* Yay! We have a prospie. Micah. What questions do you have for him?
* Don't forget today's 4:15 talk on Politics of Mourning in Civil War.
* Even more than a century ago, politicians abused causes for their own good
* FREE FOOD!
* And extra credit.
* No homework for tomorrow!
* Read (or re-read) the reading on documentation for tomorrow's class.
* Yes, we will go over some recursion stuff tomorrow, too.
Overview:
* What is a procedure?
* Describing procedures in Scheme.
* How Scheme evaluates procedures.
* Naming procedures in Scheme.
What is a procedure?
* Something that may or may not be defined
* It's like an algorithm: It solves a particular problem
* In order to write procedures, we may need multiple algorithms
* What constitutes an algorithm? A set of instructions for accomplishing
some goal
* Idea: Follow instructions non-reflectively, and you still get the result
* Often used in the accomplishment of other algorithms
So, a procedure is a series of instructions that, given some input, compute
some desired result - Encapsulated for ease of use
/Form of Procedures in Scheme/
(lambda (__input__) __instructions__)
* A declaration of *what* the procedure is and does: Given this input, we
compute a result by following these instructions
* E.g., "Given an integer in the range 0..255, compute a shade of grey by building a new color, each of whose components is that integer."
(lambda (number) (rgb.new number number number))
* To apply a procedure in Scheme, we typically write
(procedure thing)
/How Scheme Deals with Procedures/
* "OOh, it's a procedure because there's a lambda"
* Okay, let's look at what we're applying the procedure to.
Evaluate all of those arguments.
((lambda (number) (rgb.new number number number)) 128)
* 128 is already evaluated. Yay
((lambda (number) (rgb.new number number number)) (+ 23 x))
* Whoops, (+ 23 x) is not yet evaluated. I better evalute it
* Look up x in a table of definitions. We'll say that it's 17
* (+ 23 17) is 40
((lambda (number) (rgb.new number number number)) 40)
* For each input parameter, find the corresponding argument
* In this case, we say that "number is 40"
* Easy way to think about it: Substitute the corresponding argument for
each input parameter in the instructions
(rgb.new 40 40 40 )
* Evaluate the newly updated instructions
673720575
* IN practice, the Scheme interpreter does something slightly different
* In the table of names, add a line that maps each parameter to the
corresponding argument
* Evaluate the insturctions
(rgb.new number number number)
* Need to evaluate parameters
* Need to look up number
(rgb.new 40 40 40)
673720575
What if we'd decided to name the procedure?
(define grey (lambda (number) (rgb.new number number number)))
(grey 40)
* Look up grey in the table
((lambda (number) (rgb.new number number number)) 40)
What if we want to have a procedure that requires multiple inputs
Suppose we want a procedure that averages two colors
(lambda (color1 color2)
(rgb.new
(/ (+ (rgb.red color1) (rgb.red color2)) 2)
(/ (+ (rgb.green color1) (rgb.green color2)) 2)
(/ (+ (rgb.blue color1) (rgb.blue color2)) 2)))
((lambda (color1 color2)
(rgb.new
(/ (+ (rgb.red color1) (rgb.red color2)) 2)
(/ (+ (rgb.green color1) (rgb.green color2)) 2)
(/ (+ (rgb.blue color1) (rgb.blue color2)) 2)))
color.black color.white)
(rgb.new
(/ (+ (rgb.red color.black) (rgb.red color.white)) 2)
(/ (+ (rgb.green color.black) (rgb.green color.white)) 2)
(/ (+ (rgb.blue color.black) (rgb.blue color.white)) 2)))
((lambda (r g b) CODE_SO_CONFUSING_IT_WILL_HURT_TO_READ)
(/ (+ (rgb.red color.black) (rgb.red color.white)) 2)
(/ (+ (rgb.green color.black) (rgb.green color.white)) 2)
(/ (+ (rgb.blue color.black) (rgb.blue color.white)) 2)))
((lambda (r g b) CODE_SO_CONFUSING_IT_WILL_HURT_TO_READ)
(/ (+ (rgb.red 255) (rgb.red -1)) 2)
(/ (+ (rgb.green 255) (rgb.green -1)) 2)
(/ (+ (rgb.blue 255) (rgb.blue -1)) 2)))
((lambda (r g b) CODE_SO_CONFUSING_IT_WILL_HURT_TO_READ)
(/ (+ 0 255) 2)
(/ (+ 0 255) 2)
(/ (+ 0 255) 2))
Let's look at map
* Form of a call to map
(map proc lst)
* Goal is to compute a new list by applying proc to each elemetn of lst
* Start with
(map proc (v1 v2 v3 v4 v5 v6))
=> (list (proc v1) (proc v2) (proc v3) (proc v4) (proc v5) (proc v6))
Need to evaluate each of them
* Particular example
(map grey (list 0 64 128 192 255))a
* Look up grey
(map (lambda (c) (rgb.new c c c)))
* Hand waving: Convert into the list of things to do
(list ((lambda (c) (rgb.new c c c)) 0)
((lambda (c) (rgb.new c c c)) 64)
((lambda (c) (rgb.new c c c)) 128)
((lambda (c) (rgb.new c c c)) 192)
((lambda (c) (rgb.new c c c)) 255))
(list 255
((lambda (c) (rgb.new c c c)) 64)
((lambda (c) (rgb.new c c c)) 128)
((lambda (c) (rgb.new c c c)) 192)
((lambda (c) (rgb.new c c c)) 255))
(list 255
1077952767
((lambda (c) (rgb.new c c c)) 128)
((lambda (c) (rgb.new c c c)) 192)
((lambda (c) (rgb.new c c c)) 255))
...
(255 1077952767 -2139062017 -1061109505 -1)
(map rgb->string (list 255 1077952767 -2139062017 -1061109505 -1))
(list (rgb->string 255)
(rgb->string 1077952767)
(rgb->string -2139062017)
(rgb->string -1061109505)
(rgb->string -1))