Outline 42: Higher-Order Procedures, Revisited

Held: Wednesday, 15 April 2015

Back to Outline 41 - Project Kickoff. 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!
Review sessions Thursday at 9am (or slightly later), 1:15 pm, and 8:00 pm. (Also a chance for project advice.)

Upcoming Work

Lab writeup: 3, 4, and 6. http://bit.ly/151-2015S-lab42
Quiz Friday: Vectors, Randomness, (Not higher-order procedures)
Reading for Friday: Analyzing Procedures

Extra Credit Opportunities

Academic

CS Extras Thursday: NBB on her summer REU (Android and Robots!)
CS Table Friday: Coding Clubs
Convocation April 22nd, Erica Lehrer '92 (Post-Conflict Memory, Ethnography)

Peer Support (Morning Section)

KY's radio show, "We Think We're Funny", 9-10pm Mondays.
Julia's radio show, "The Hot Box". Wednesday night/Thursday morning 1:00-2:00 a.m. Four lads from Liverpool.
Host an admitted student this coming Sunday night. Contact JMU for info.
Salsa Showcase, 6:00 or 8:00 pm Friday, April 17 in Roberts.
Drag Show April 18
Heed the Senses in Bucksbaum Wed 8-11 pm (go for at least 30 minutes).
Department of Music Voice event noon in Sebring-Lewis
KDIC Music Festival Saturday
Chamber Concert Saturday at 2pm in Sebring-Lewis

Peer Support (Afternoon Section)

Host an admitted student this coming Sunday night. Contact JMU for info.
Contra Dance Workshop Thursday the 16th at 7:30 pm in BCA Dance Studio.
Salsa Showcase, 7:30 pm Friday, April 17 in Harris.
Drag Show April 18
Contra Dance April 24 in Main Hall.
Psych Job Talk Thursday.
Bio seminar noon on Friday.
Financial Literacy workshop Monday night 7-8 in JRC 226.
KDIC Music Festival Saturday

Miscellaneous

Town hall April 23, noon or 7:30 pm, "How we have conversations."
Sexual conduct survey: http://tinyurl.com/GCSurvey2015. (Just tell me that you filled it out; I don't need a receipt or comments.)

Other Good Things (no extra credit)

Contra Dance Workshop Thursday the 16th at 7:30 pm in BCA Dance Studio.
Contra Dance April 24 in Main Hall.
Heed the Senses in Bucksbaum Wed 8-11 pm (go for at least 30 minutes).
Department of Music Voice event noon in Sebring-Lewis
KDIC Music Festival Saturday
Chamber Concert Saturday at 2pm in Sebring-Lewis

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

Common code

(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.