Outline 42: Higher-Order Procedures, Revisited
Held: Monday, 17 November 2014
Back to Outline 41 - Randomized (Unpredictable) Drawing.
On to Outline 43 - Analyzing Procedures.
Summary
We revisit the topic of higher-order procedures, one of the most
important techniques in languages like Scheme. Higher-order procedures
are procedures -- like map
, left-section
, or compose
-- that
take other procedures as parameters, return other procedures as values,
or both.
Related Pages
Overview
- Some program design principles.
- Thinking about repetition.
- Procedures as first-class values.
Administrivia
- New partners!
- Exam 3 (and quizzes?) returned at the end of class.
- Office hours recomplicated by interviews and administrative junk. Sorry.
- I assume we'll have more questions than normal today.
Upcoming Work
- Lab writeup:
- Reading for Tuesday:
- Part one of the project due tonight!
- Sketches due in class on Tuesday.
- Part two of the project due next Tuesday.
Extra Credit Opportunities
Academic
- CS Extras Thursday: Weinmaniacs on Text Recognition in Maps
- CS Table Friday: One Year After Healthcare.gov
- CS Extras Tuesday the 25th: Summer Opportunities in CS
Peer Support
- Why didn't anyone mention the ISO dinner?
- Karan's radio show 11pm Thursday nights on KDIC
- Evan's radio show 5pm Friday nights on KDIC
- Donna's radio show Sunday midnight on KDIC
- One acts, coming soon
Miscellaneous
- VP Student Affairs Candidate Open Sessions
- Wednesday, 4:15, JRC 209
- Friday, 4:15, JRC 209
Project Notes
- Remember that you need at least three different approaches from the
menu of Gimp tools, Turtles, image-compute, image-variant, drawings
as values, and color trees. (If you want to suggest another, ....)
(image-redo! image (lambda (x y color) newcolor))
is the generalization
of image-transform!
and image-compute
.
Background: Guiding Principles
- Write less, not more
- It (usually) makes you faster.
- It (usually) makes your code more readable.
- It (usually) makes your code easier to maintain.
- Refactor
- Don't write repetitious code
- If you are programming by copy-paste-change, you're probably wasting
time.
- Name appropriately
- Good names for things that need names
- No names for things that don't need names
Background: The Value of Repetition
The following is variant of something my colleague John Stone says ...
You learn from reading.
- The first time you read a new procedure structure
(such as recursion over a list), you learn something.
- The second time you read the same structure, you learn something else.
- The third time, you learn a bit more.
- After that, reading doesn't give much benefit.
You learn from writing.
- The first time you write the same structure, you learn something more
about that structure
- The second time, you learn even more.
- The third time, you learn a bit more.
- After that, there's almost no benefit.
So ... extract the common code so you don't have to write it again.
Procedures as First-Class Values
- We'll look at one way to achieve our guiding principles and write
common code.
- The big picture ideas:
- You can write procedures (like
map
) that take other procedures
as parameters.
- You can write procedures (like
left-section
and compose
) that
return other procedures.
- Doing so makes your code better.
- Procedures are, in effect, yet another kind of value. What are the
questions we normally ask about new types of values?
- Taking a procedure as a parameter is easy. You just include it as a normal
parameter and use it as a normal procedure.
(define apply-to-2-and-3
(lambda (proc)
(proc 2 3)))
- Returning procedures is a bit harder. You usually just return an anonymous
procedure. That means you'll have multiple lambdas.
(define adder
(lambda (n)
(lambda (x)
(+ x n))))
(define inc (adder 1))
Old Notes
The following are notes I wrote for past versions of the course. I probably
won't discuss any/all in class.
Two Motivating Examples
all-real?
and all-integer?
add-5-to-each
and multiply-each-by-5
Procedures as Parameters
- We've been writing it a lot.
- Useful
- Concise
- Supports refactoring
Procedures as Return Values
- Another way to create procedures (anonymous and named).
- Strategy: Write procedures that return new procedures.
- These procedures can take plain values as parameters:
(define redder
(lambda (amt)
(lambda (color)
(rgb ...))))
- How to think about this:
- a procedure that takes amt as a parameter,
- returns a new procedure that takes color as a parameter
- Can also take procedures as parameters
- One favorite:
compose
<>boxcode
(define compose
(lambda (f g)
(lambda (x)
(f (g x)))))
- Examples
- sine of square root of x:
(compose sin sqrt)
- last element of a list:
(compose car reverse)
- Another:
left-section
(define left-section
(lambda (func left)
(lambda (right)
(func left right))))
(define l-s left-section)
- Examples:
- add two:
(l-s + 2)
- double:
(l-s * 2)
- Not mentioned int he reading, but there's a corresponding right-section
(define right-section
(lambda (func right)
(lambda (left)
(func left right))))
(define r-s right-section)
Encapsulating Control
- Possible for complex common code, too (particularly control).
map
is the standard example.
(define map
(lamda (fun lst)
(if (null? lst)
null
(cons (fun (car lst))
(map fun (cdr lst))))))
- Another issue: Checking the type of elements in a list
(define all-numbers?
(lambda (lst)
(or (null? lst)
(and (pair? lst)
(number? (car lst))
(all-numbers? (cdr lst))))))
(define all-symbols?
(lambda (lst)
(or (null? lst)
(and (pair? lst)
(symbol? (car lst))
(all-symbols? (cdr lst))))))
(define all
(lambda (test? lst)
(or (null? lst)
(and (pair? lst)
(test? (car lst))
(all test? (cdr lst))))))
Concluding Comments
- Yes, skilled Scheme programmers write this way.
- It's quick.
- It's clear (at least to skilled Schemers).
- It reduces mistakes.
- The ability to encapsulate control in this way is fairly unique to Scheme
(well, to functional languages).
- It's one of the reasons we love it at Grinnell.
- Or at least a reason I love it.