Held: Wednesday, 20 April 2016

Back to Outline 42 - Trees. On to Outline 44 - Files in Scheme.

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

• Reading: Design Patterns and Higher-Order Procedures
• Lab: Design Patterns and Higher-Order Procedures
• EBoard 43 (Source 43)

Overview

• Some program design principles.
• Thinking about repetition.
• Procedures as first-class values.

Administrivia

• New partners!
• I will continue to bring you food (or food-like substances) until I am caught up on grading. (You may be getting food until you graduate from Grinnell.)
• Sorry about yesterday. My wife tells me that it's about the fifth time she can recall that I've skipped class because I was sick. (And we've been married over 28 years.)
• Note that there's a grading rubric for the project. Pay attention to it as you work on your proposal and project.

Reminders

• Office hours this week
  • See http://rebelsky.youcanbook.me.
  • Ask me about other available times.
• Tutor hours
  • Sunday, 3-5 p.m.
  • Sunday-Thursday, 7-10 p.m.
• Review Sessions
  • Wednesday at 8pm in CS commons with Zachary
  • Thursday at 10 am with SamR
  • Thursday at 8pm in CS commons with Alex

Upcoming Work:

• Reading for Friday
  • Files
• Lab Writeup:
  • Send email titled CSC 151 Lab Writeup 43 (Your Names)
  • Do not include the underscores.
  • Send to CSC151-02-grader@grinnell.edu
  • Due before class on Monday.
• Quiz Friday!
• Project proposals Monday.

Extra Credit

• Send your reports to rebelsky@grinnell.edu with subject "CSC 151 Extra Credit". (Do not include the quotation marks.)
• Send opportunities to me before class with subject "CSC 151 EXTRA CREDIT OPPORTUNITY!"

Academic / Artistic

• Any of the fora on the report from the Residential Learning Task Force.
  • Wednesday, April 20, 7:00-8:30 p.m., Noyce 2022
  • Friday, April 22, 1:00-2:30 p.m., JRC 209
  • Tuesday, April 26, 11:00 a.m. - 12:00 noon, JRC 101
  • Tuesday, 6:00-7:00 pm, JRC 209
• Math/Stats Student Seminar, Elizabeth Eason and Jun Take Lee: Cascades and Multifractals - noon, Thursday, April 21
• Presentation, Statistical Modeling in Genome-Wide Association Studies: Identifying Disease-associated Genes Using Gene Pathways", Thursday, April 21, 4:15 p.m., ARH 102
• Classics Seminar, April 21, Jeffrey Hurwitt, JRC 101, 4:15 pm
• Scholars' Convocation: Dutch Global Horizons, Thursday, April 28, 11 am, JRC 101
• Damon Williams: Bigger Than The Cops, April 28, 4pm or 5:15 pm

Peer

• Lords of the Flies, 7:30 pm April 22nd, 2:00 pm April 23rd, 2:00 9pm April 24th. (Only 50-60 tickets per show)
• Second Annual Contra into Spring Dance, April 22nd, Main Quad, 7:30 p.m.
• R&B Soul Friday in Herrick at 7pm
• Drag, Saturday. Bring money to give to the performers to give to charity.

Regular Peer

• Social Dance Workshop Tuesdays 7:00-8:00 in Bucksbaum Dance Studio
• Post-break ExCo on British Politics Wednesdays at 8:00 in JRC 203.
  Just show up; you don't need to sign up.
• Pun club Saturdays at 4pm in Younker
• Electronic Potpourri on KDIC Fridays at Five
• Space Odyssey KDIC Fridays at Six
• Bollywood, Fridays, 7:30-8:30, Younker
• Effective Altruism club, 2:30-3:30 Sundays in JRC 226.

Misc

Not so Far in the Future

• Adaptation of Rushdie's East West. Early May.
• Is anyone in 25th Annual Putnam County Spelling Bee?

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.