# Class 32: Procedures as values

Held Wednesday, October 25, 2000

Summary

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

Notes

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.
(lambda (lst)
(if (null? lst) null
(cons (+ 5 (car 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?

## History

Thursday, 24 August 2000

• Created as a blank outline.

Wednesday, 25 October 2000

• Filled in the details.

Disclaimer Often, these pages were created "on the fly" with little, if any, proofreading. Any or all of the information on the pages may be incorrect. Please contact me if you notice errors.