Class 32: Procedures as values

Held Wednesday, October 25, 2000

Summary

Today we will discuss procedures that take other procedures as parameters.

Notes

• Are there any final questions on hw4?
  • The current list of courses can be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2000F/Examples/courses.ss
  • There are some more courses left to be added (I haven't had time since posting the list).
  • There was a request to go over the steps in writing a CGI script again, so we'll spend some class time on that.
• Reminder: I won't be available tomorrow.
• Today's class will be primarily lecture-based.

Overview

Design Patterns

• As you may have noticed in working on your labs, exams, and assignments, there are many problems whose solutions have similar structures.
• We might then want to look more abstractly at those structures and see what kinds of problems they apply to.
• These solution structures are typically called patterns or design patterns.
• In some languages, patterns are simply a guide to the programmer, giving techniques for designing solutions.
• In Scheme, you can actually encode patterns in procedures.
• Today we'll consider a few examples of design patterns (typically involving recursion) and see how they might be coded.

Apply to All

• Let's start with two similar problems, both of which somone might use to process a list of grades.
• Add 5 to every value in a list of numbers.
• Multiply every value in a list of numbers by 10/8.
• How might we code these?

  ;;; Add 5 to every value in a list of numbers.
  ;;; Parameters:
  ;;;   A list of numbers.
  ;;; Returns:
  ;;;   A list of numbers.
  ;;; Preconditions:
  ;;;   The list contains only numbers. [Unchecked]
  ;;; Postconditions:
  ;;;   The result list is the same length as the parameter.
  ;;;   Each element of the result list is five greater than the
  ;;;     corresponding element of the parameter.
  (define add-five-to-all
    (lambda (lst)
      (if (null? lst) null
          (cons (+ 5 (car lst)) 
                (add-five-to-all (cdr lst))))))
  
  ;;; Scale every value in a list of numbers by 5/4.
  ;;; Parameters:
  ;;;   A list of numbers.
  ;;; Returns:
  ;;;   A list of numbers.
  ;;; Preconditions:
  ;;;   The list contains only numbers. [Unchecked]
  ;;; Postconditions:
  ;;;   The result list is the same length as the parameter.
  ;;;   Each element of the result list is 5/4 the value of the
  ;;;     corresponding element of the parameter.
  (define scale-all-by-five-forths
    (lambda (lst)
      (if (null? lst) null
          (cons (* (/ 5 4) (car lst)) 
                (scale-all-by-five-forths (cdr lst))))))
  

• What do these have in common?
  • Both return null when given the null list.
  • Both cons function of the car to the result of recursing on the cdr.
• Here's a generalization:

  (define do-something-to-all
    (lambda (lst)
      (if (null? lst) null
          (cons (PROCEDURE (car lst)) (do-something-to-all (cdr lst))))))
  

• But where does the procedure come from? We could define it first.

  > (define PROCEDURE
      (lambda (val) (+ val 2)))
  > (PROCEDURE 4)
  6
  > (do-something-to-all '(1 2 3))
  (3 4 5)
  > (define PROCEDURE
      (lambda (val) (* (/ 5 4) val)))
  > (PROCEDURE 4)
  5
  > (do-something-to-all '(1 2 3))
  (5/4 5/2 15/4)
  

• As you may have noted, this seems a little bit inelegant.
• What else can we do?
  • We can take the procedure to apply to each value as a parameter to the general procedure!
• Here goes

  ;;; Apply a procedure to every value in a list of numbers.
  ;;; Parameters:
  ;;;   A list of numbers.
  ;;;   A procedure that takes a number as a parameter and returns a number.
  ;;; Returns:
  ;;;   A list of numbers.
  ;;; Preconditions:
  ;;;   The list contains only numbers. [Unchecked]
  ;;; Postconditions:
  ;;;   The result list is the same length as the parameter.
  ;;;   Each element of the result list is the result of applying the
  ;;;     procedure to the corresponding element of the parameter.
  (define apply-all
    (lambda (proc lst)
      (if (null? lst) null
          (cons (proc (car lst)) (apply-all proc (cdr lst))))))
  

• Here's a simple test

  > (define square (lambda (x) (* x x)))
  > (apply-all square '(1 2 3 4))
  (1 4 9 16)
  

• The moral: procedures can be parameters to other procedures!.
• Note that the ``apply to all'' design pattern is so common that Scheme includes it as a built-in procedure (called map).

Anonymous Procedures

• Of course, in the example above, square is just a helper procedure.
• Hence, we might write the more elegant

  > (let ((square (lambda (x) (* x x))))
      (apply-all square '(1 2 3 4)))
  

• But what does this say? It tells us that square is another name for (lambda (x) (* x x)) and then uses that name.
• When we use the name, Scheme simply substitutes the thing that's been named.
• We can do the substitution ourselves

  (apply-all (lambda (x) (* x x)) '(1 2 3 4))
  

• We've used a procedure without naming it!
• Such unnamed procedures are called anonymous procedures. You'll find that we often use them in conjunction with design patterns.

Some Other Patterns

• Extract all the elements of a list that meet some criteria.
• Generalization of sum and product?