CSC 151-02, Fall 2006 : Notes on Higher-Order Procedures

Notes on Higher-Order Procedures 

Background: 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 hyp (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

• Consider problem from exam. Some wrote
  • (define count-smoking (lambda (s1 s2) (if (equal? (smokes? s1) (smokes s2)) 1 0)))
  • (define count-bedtime (lambda (s1 s2) (if (equal? (get-bedtime s1) (get-bedtime s2)) 1 0)))
• Incredibly similar. Factor out the test
  • (define count-X (lambda (X s1 s2) (if (equal? (X s1) (X s2)) 1 0))))
• Now we can define the previous two in terms of this
  • (define count-smoking (count-X smokes?))
  • (define count-bedtime (count-X get-bedtime))
• In fact, we can even do without them
  • (if (>= (+ (count-X smokes? s1 s2) (count-X get-bedtime s1 s2) ...) 3) ...)

Anonymous Procedures

• Sometimes we don't even need to bother to define procedures (just like we don't define the parts of a compound expression).
• Strategy: Just use (lambda (params) body)
• We call such procedures anonymous.

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:
• halve: (r-s / 2)
• If we were confident with this procedure, we could use it in the exam:

  (define smokes? (r-s vector-ref 3))
  

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))))))
  (define fixed-grades (scale-grades original-grades))
  

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

  (define extra-credit
    (lambda (grades)
      (if (null? grades)
          null
          (cons (+ 5 (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.