Reading 32a: Notes on Higher-Order Procedures

Guiding Principles

• Be concise.
• Name appropriately.
  • Good names for things that need names
  • No names for things that don't
  • Example: Don't name the components in

    (define hypotenuse (lambda (a b) (sqrt (+ (* a a) (* b b))))) 
    

• Don't repeat code. Refactor.

Procedures as Parameters

• First explored in the color-grid exercise.
• 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 (+ amt (red color)) (green color) (blue color)))))
  

• 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 two functions with compose

  (define compose
    (lambda (f g)
      (lambda (x)
        (f (g x)))))
  

• Examples :
  
  • make a color purpler: (compose (redder 33) (bluer 33))
  • sine of square root of x: (compose sin sqrt)
  • last element of a list: (compose car reverse)
• Another: fill in the first parameter to a binary procedure with left-section

  (define left-section
    (lambda (func left)
      (lambda (right)
        (func left right))))
  (define l-s left-section)
  

• Examples:
  • increment: (l-s + 1)
  • add two: (l-s + 2)
  • double: (l-s * 2)
  • inverse: (l-s / 1)
• Not mentioned in the reading, but there's a corresponding right-section

  (define right-section
    (lambda (func right)
      (lambda (left)
        (func left right))))
  (define r-s right-section)

• Example:
• decrement: (r-s - 1)
• halve: (r-s / 2)

Encapsulating Control

• Possible for complex common code, too (particularly control).
• Sample: Whoops ... suppose no one got problem 2 right. Perhaps I should just scale each grade by 4/3.

  (define scale-grades
    (lambda (grades)
      (if (null? grades)
          null
          (cons (* 4/3 (car grades))
                (scale-grades (cdr grades))))))
  

• Another sample: Oh yeah, everyone gets three points of extra credit.

  (define extra-credit
    (lambda (grades)
      (if (null? grades)
          null
          (cons (+ 3 (car grades))
                (extra-credit (cdr grades))))))
  

• A philosophy
  • 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.
  • 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 no benefit.
  • So ... extract the common code so you don't have to write it again.
  • And yes, you learn something.
• Applied above:

  (define map
    (lambda (func lst)
       (if (null? lst)
           null
           (cons (func (car lst))
                 (map func (cdr lst))))))
  

• Rewriting ...

  (define scale-grades
    (lambda (grades)
       (map (lambda (grade) (* 4/3 grade)) grades)))
  (define extra-credit
    (lambda (grades)
       (map (lambda (grade) (+ 7 grade)) grades)))
  

• We can simplify by using left-section:

  (define scale-grades
    (lambda (grades)
       (map (l-s * 4/3) grades)))
  (define extra-credit
    (lambda (grades)
       (map (l-s + 7) grades)))
  

• Or even more concisely
  • (define scale-grades (l-s map (l-s * 4/3)))
  • (define extra-credit (l-s map (l-s + 2)))

• Another issue: Checking the type of elements in a list:

  (define list-of-numbers?
    (lambda (lst)
      (or (null? lst)
          (and (pair? lst)
               (real? (car lst))
               (list-of-numbers? (cdr lst))))))
  (define list-of-symbols?
    (lambda (lst)
      (or (null? lst)
          (and (pair? lst)
               (symbol? (car lst))
               (list-of-symbols? (cdr lst))))))
  

• Refactoring the common code in these two procedures gives us

  (define list-of?
    (lambda (test? lst)
      (or (null? lst)
          (and (pair? lst)
               (test? (car lst))
               (list-of? test? (cdr lst))))))
  

• This might be useful on the exam for testing to see if the items in a grades-list are valid:

  (define valid-form?
    (lambda (val) (and (pair? val) (string? (car val)) (integer? (cdr val)))))
  (define all-valid?
    (lambda (lst) (list-of? valid-form? lst)))
  

• Or

  (define all-valid? (l-s list-of? valid-form?))
  

  Or

  (define all-valid? (l-s list-of? (lamda (val) (and (pair? val) (string? (car val)) (integer? (cdr val))))))
  

• 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 one of the key features of functional programming languages such as Scheme.
• It's one of the reasons we love Scheme at Grinnell.