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

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

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:
  • Analyzing Procedures
• 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))))))

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