Fundamentals of Computer Science I (CS151 2003F)
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Guidelines for Lab Writeups]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Scheme Report]
[Glimmer Scheme Reference]
[CSC151.01 (Gum)]
[CSC151 2003S]
[CSC151 2002F]
[SamR]
Summary: In this reading, you will investigate the so called higherorder procedures, procedures that take procedures as parameters or return procedures as results. In effect you are considering what happens when we allow procedures to serve as values.
Contents:
One mark of successful programmers is that they identify and remember common techniques for solving problems. Such abstractions of common structures for solving problems are often called patterns or design patterns. You should already have begun to identify some patterns. For example, you know that procedures almost always have the form
(define procname (lambda (parameters) body))
You may also have a pattern in mind for the typical recursive procedure over lists:
(define procname (lambda (lst) (if (null? lst) basecase (dosomething (car lst) (procname (cdr lst))))))
In some languages, these patterns are simply guides to programmers as they design new solutions. In other languages, such as Scheme, you can often encode a design pattern in a separate procedure.
Let's begin with two similar problems, both of which an instructor might apply to a list of grades after determining that grading was too harsh. That instructor might want to create a new list in which each grade is incremented by 5 or that instructor might want to multiply every value in the list by 5/4.
Here are simple implementations of the two procedures.
;;; Procedure: ;;; addfivetoall ;;; Parameters: ;;; lst, a list of numbers. ;;; Purpose: ;;; Add 5 to every value in lst. ;;; Returns: ;;; newlst, a list of numbers. ;;; Preconditions: ;;; lst contains only numbers. [Unverified] ;;; Postconditions: ;;; newlst is the same length as lst ;;; Each element of newlst list is five greater than the ;;; corresponding element of lst. (define addfivetoall (lambda (lst) ; If no elements remain, we can't add 5 to anything, so ; stick with the empty list. (if (null? lst) null ; Otherwise, add 5 to the first number, add 5 to all ; the remaining numbers, and shove 'em together. (cons (+ 5 (car lst)) (addfivetoall (cdr lst)))))) ;;; Procedure: ;;; scaleallbyfivefourths ;;; Parameters: ;;; lst, a list of numbers. ;;; Purpose: ;;; Scales every value in a list of numbers by 5/4 ;;; Returns: ;;; newlst, a list of numbers. ;;; Preconditions: ;;; lst contains only numbers. [Unverified] ;;; Postconditions: ;;; newlst is the same length as lst ;;; Each element of newlst list is 5/4 times the ;;; corresponding element of lst. (define scaleallbyfivefourths (lambda (lst) ; If no elements remain, we can't do any more multiplications, ; so stick with the empty list. (if (null? lst) null ; Otherwise, scale the first number, scale all ; the remaining numbers, and shove 'em together. (cons (* (/ 5 4) (car lst)) (scaleallbyfivefourths (cdr lst))))))
What do these two procedures have in common? Most of the documentation. They also both return null when given the null list. More importantly, both do something to the car of the list, recurse on the cdr of the list, and then cons the two results together.
Hence, we can design a general pattern for apply a procedure to every value in a list.
(define procname (lambda (lst) (if (null? lst) null (cons (modify (car lst)) (procname (cdr lst))))))
We can even turn this pattern into a procedure.
;;; Procedure: ;;; dosomethingtoall ;;; Parameters: ;;; lst, a list of numbers. ;;; Purpose: ;;; Applies MODIFY to each value in a list. ;;; Returns: ;;; newlst, a list of numbers. ;;; Preconditions: ;;; lst contains only numbers. [Unverified] ;;; MODIFY is defined, takes one number as a parameter ;;; and returns a number. [Unverified] ;;; Postconditions: ;;; newlst is the same length as lst ;;; Each element of newlst list the result of applying MODIFY ;;; to the corresponding element of lst. (define dosomethingtoall (lambda (lst) ; If no elements remain, we can't apply anything else, ; so stick with the empty list. (if (null? lst) null ; Otherwise, apply the procedure to the first number, ; apply the procedure to the remaining numbers, and ; put the results back together into a list. (cons (MODIFY (car lst)) (dosomethingtoall (cdr lst))))))
Where does MODIFY
come from? We could define it first
(as the preconditions suggest). For example, here's an application of
dosomethingtoall
in which we add 5 to each value.
> (define MODIFY (lambda (val) (+ val 5))) > (MODIFY 4) 9 > (dosomethingtoall (list 1 2 3)) (6 7 8)
Similarly, we can multiply all the values in a list by 4/5 by
redefining MODIFY
appropriately.
> (define MODIFY (lambda (val) (* (/ 5 4) val))) > (MODIFY 4) 5 > (dosomethingtoall (list 1 2 3)) (5/4 5/2 15/4)
You may find this strategy of defining MODIFY
first inelegant. I certainly do. It also won't work for all cases.
For example, what if we want to add five to all the numbers in a list and
then scale by fivefourths? We'd have to redefine MODIFY
in the middle of our code. Ugly.
Is there a better solution? Yes! Instead
of forcing MODIFY
to be defined before we call
dosomethingtoall
, we can make the procedure a
parameter to the pattern. For example, here's a renamed version
of dosomethingtoall
that takes the extra parameter.
;;; Procedure: ;;; applyall ;;; Parameters: ;;; proc, a procedure that takes one parameter (a number) and ;;; returns a number. ;;; lst, a list of numbers. ;;; Purpose: ;;; Applies proc to each value in a list. ;;; Returns: ;;; newlst, a list of numbers. ;;; Preconditions: ;;; The types of the parameters are correct. [Unverified] ;;; Postconditions: ;;; newlst is the same length as lst ;;; Each element of newlst is the result of applying proc ;;; to the corresponding element of lst. (define applyall (lambda (proc lst) ; If no elements remain, we can't apply anything else, ; so stick with the empty list. (if (null? lst) null ; Otherwise, apply the procedure to the first number, ; apply the procedure to the remaining numbers, and ; put the results back together into a list. (cons (proc (car lst)) (applyall proc (cdr lst))))))
Here are some simple tests
> (let ((addfive (lambda (v) (+ 5 v)))) (applyall addfive (list 1 2 3))) (6 7 8) > (let ((square (lambda (v) (* v v)))) (applyall square (list 1 2 3))) (1 4 9) > (applyall list (list 1 2 3)) ((1) (2) (3)) > (applyall odd? (list 1 2 3)) (#t #f #t)
You should have observed a very important (and somewhat stunning) moral from this example, procedures can be parameters to other procedures. We call the procedures that take other procedures as parameters higherorder procedures.
There are many advantages to encoding design patterns in higherorder
procedures. An important one is that it stops us from tediously writing
the same thing over and over and over again. Think about writing the
predicates listofnumbers?
, listofreals?
,
listofpairs?
, listofsymbols?
, and so on
and so forth. As one colleague says,
Writing and testing one of these definitions is an interesting and instructive exercise for the beginning Scheme programmer. Writing and testing another one is good practice. Writing and testing the third one is, frankly, a little tedious. If we then move on to [others], eventually programming is reduced to typing.
So, how do we avoid the repetitious typing? We begin with one of the procedures.
(define listofreals? (lambda (val) (or (null? val) (and (pair? val) (real? (car val)) (listofreals? (cdr val))))))
Next, we identify the parts of the procedure that depend on our current type (i.e., that everything is a list).
(define listofXXX? (lambda (val) (or (null? val) (and (pair? val) (XXX? (car val)) (listofXXX? (cdr val))))))
Finally, we remove the dependent part or parts from the procedure name and make them parameters to the modified procedure.
(define listof (lambda (pred? val) (or (null? val) (and (pair? val) (pred? (car val)) (listof pred? (cdr val))))))
Here's how we might test whether something is a list of numbers.
> (listof number? (list 1 2 3)) #t > (listof number? (list 1 'a 3)) #f
We can also define listofnumbers
using this procedure.
(define listofnumbers? (lambda (lst) (listof number? lst)))
The results are the same.
> (listofnumbers? (list 1 2 3)) #t > (listofnumbers? (list 1 'a 3)) #f
We have seen that it is possible to write our own higherorder procedures. Scheme also includes a number of builtin higherorder procedures. You can read about many of them in section 6.4 of the Scheme report (r5rs), which is available through the DrScheme Help Desk. Here are some of the more popular ones.
The map
procedure takes as arguments a procedure and one
or more lists and builds a new list whose contents are the result of
applying the procedure to the corresponding elements of each list.
(That is, the ith element of the result list is the result of applying
the procedure to the ith element of each source list.)
map
is essentially the same as our applyall
except that map
does not guarantee that it steps
through the list in a lefttoright order.
One of the most important builtin higherorder procedures is
apply
, which takes a procedure and a list as arguments
and invokes the procedure, giving it the elements of the list as its
arguments:
> (apply string=? (list "foo" "foo")) #t > (apply * (list 3 4 5 6)) 360 > (apply append (list (list 'a 'b 'c) (list 'd) (list 'e 'f) null (list 'g 'h 'i))) (a b c d e f g h i)
Recall that in the examples above we wrote something like
> (let ((square (lambda (v) (* v v)))) (map square (list 1 2 3)))
Let's take this code apart. The let
expression makes
square
the name of a procedure of one parameter that squares the parameter.
The code then applies the square
procedure to a list. Scheme
substitutes the procedure for square
(just as it
substitutes a value for a named value). Hence, to Scheme, the
code above is essentially equivalent to
(map (lambda (v) (* v v)) (list 1 2 3))
Because Scheme does this substitution, we can also do it. That is, we can write the previous code and have Scheme execute it.
> (map (lambda (v) (* v v)) (list 1 2 3))
(1 4 9)
So, what does this new code say? It says Apply a procedure that squares
its argument to ever element of the list (1 2 3)
. Do we care what
that procedure is named? No. We describe procedures without names
as anonymous procedures. You will find that you frequently
use anonymous procedures with design patterns and higherorder procedures.
In effect, you can read lambda
as a procedure
. Hence,
(lambda (params) body)
can be considered a shorthand
for a procedure of parameters params that computes body
.
At this point, you've seen many other design patterns that typically involve recursion. You may find it valuable to design corresponding procedures to encapsulate those patterns. Here are some of the patterns you may wish to think about:
insert
,
which inserts a binary (two parameter) operation between all
of values in a list. For example, sum
inserts a plus
between neighboring values in a list (i.e., (sum (list 1 2 3 4))
is 1+2+3+4
). Similarly, product
inserts
a times between neighboring values.
If we had defined insert (see the lab),
we might define sum
as
(define sum (lambda (lst) (insert + lst)))
tally
, which counts the number of values in a list that
meet a particular predicate. For example, to count the number of
odd values in a list, we'd use
(tally odd? lst)
Similarly, to count the number of sevens or elevens in a list, we'd use
(tally (lambda (v) (or (= 7 v) (= 11 v))) lst)
select
, which selects all elements of a list that match
a particular predicate. For example,
> (select odd? (list 1 2 3 4 5 6 7))
(1 3 5 7)
remove
, which removes all elements of a list that match
a particular predicate. For example,
> (remove odd? (list 1 2 3 4 5 6 7))
(2 4 6)
Just as it is possible to use procedures as parameters to procedures, it is also possible to return new procedures from procedures. For example, here is a procedure that takes one parameter, a number, and creates a procedure that multiplies its parameters by that number.
;;; Procedure: ;;; makemultiplier ;;; Parameters: ;;; n, a number ;;; Purpose: ;;; Creates a new procedure which multiplies its parameter by n. ;;; Produces: ;;; proc, a procedure of one parameter ;;; Preconditions: ;;; n must be a number ;;; Postconditions: ;;; (proc v) gives v times n. (define makemultiplier (lambda (n) ; Parameter ; Return value: A procedure (lambda (v) (* v n))))
Let's test it out
> (makemultiplier 5) #<procedure> > (define timesfive (makemultiplier 5)) > (timesfive 4) 20 > (timesfive 101) 505 > (map (makemultiplier 3) (list 1 2 3)) (3 6 9)
We can use the same technique to build the legendary compose operation that given two functions, f and g, builds a function that applies g and then f.
;;; Procedure: ;;; compose ;;; Parameters: ;;; f, a unary function ;;; g, a unary function ;;; Purpose: ;;; Functionally compose f and g. ;;; Produces: ;;; fun, a unary function. ;;; Preconditions: ;;; f can be applied to any values g generates. ;;; Postconditions: ;;; fun can be applied to any values g can be applied to. ;;; fun generates values of the type that f generates. ;;; (fun x) = (f (g x)) (define compose (lambda (f g) ; Parameters to compose ; Build a procedure of one parameter (lambda (x) (f (g x)))))
Here are some fun tests.
> (define add2 (lambda (x) (+ 2 x))) > (define mul5 (lambda (x) (* 5 x))) > (define fun1 (compose add2 mul5)) > (fun1 5) 27 > (fun1 3) 17 > (define fun2 (compose mul5 add2)) > (fun2 5) 35 > (fun2 3) 25
We can use a more advanced technique to build a procedure that builds list
predicates. We'll write
a procedure, makelistpred
that takes one parameter, a
predicate, and returns a procedure of one parameter, a list, and determines
whether the predicate holds for every element of the list. Since we need
to build a recursive procedure, we'll use letrec
to build
that procedure.
;;; Procedure: ;;; makelistpredicate ;;; Parameters: ;;; pred?, a unary predicate ;;; Purpose: ;;; Creates a predicate that takes one parameter, and verifies ;;; that (1) the parameter is a list and (2) pred? holds for ;;; each element of the list. ;;; Produces: ;;; listpred?, a unary predicate. ;;; Preconditions: ;;; pred? is a unary predicate [Unverified] ;;; pred? can be applied to any kind of value [Unverified] ;;; Postconditions: ;;; listpred? is a unary predicate (takes one parameter, returns ;;; #t or #f) ;;; (listpred? val) returns #t if (1) val is a list and (2) pred? ;;; holds for each element of val. ;;; (listpred? val) returns #f otherwise. (define makelistpredicate (lambda (pred?) ; Parameter to listpred ; Build an appropriate procedure with one parameter (letrec ((listpred? (lambda (val) (or (null? val) (and (pair? val) (pred? (car val)) (listpred? (cdr val))))))) ; And return it listpred?)))
It's now even simpler to define list predicates.
> (define listofnumbers? (makelistpredicate number?)) > (define listofodds? (makelistpredicate odd?)) > (define listofsymbols? (makelistpredicate symbol?)) > (listofnumbers? null) #t > (listofnumbers? (list 1 2 3)) #t > (listofnumbers? (list 3+4i 5 2.4)) #t > (listofnumbers? (list 3 2 'a)) #f > (listofnumbers? (list 'a 2 3)) #f > (listofsymbols? (list 'a 'b 'c)) #t > (listofsymbols? (list 'a 'b 1)) #f > (listofsymbols? null) #t > (listofodds? (list 1 2 3)) #f > (listofodds? (list 1 3 5)) #t > (listofodds? (list 'a)) odd? expects argument of type <integer>; given a
That last error message is a direct result of the author ignoring the
preconditions of makelistpredicate
. Since odd?
can't be applied to all values, (makelistpredicate odd?)
is not guaranteed to work.
Here are some common procedures that you might use to build other procedures. Not all are predefined in Scheme. We've included some definitions. You should be able to write the others.
(leftsection binaryproc arg1)

Creates a new procedure by filling in the first argument of a binary
procedure. For example, we might define a procedure that multiplies
a value by 2 with
(define mul2 (leftsection * 2))
The leftsection
procedure is surprisingly powerful. Note
that with a little more work, we could even use it to define a variant of
makelistpredicate
.
(define makelistpredicate (lambda (pred?) (leftsection listof pred?)))
The code for leftsection
is relatively straightforward.
(define leftsection (lambda (binproc arg1) ; Build a new procedure of one argument (lambda (arg2) ; That calls binproc on the appropriate arguments (binproc arg1 arg2))))
(rightsection binaryproc arg2)

Creates a new procedure by filling in the second argument of a binary
procedure. For example, we might define a procedure that subtracts 3 from
a value with
(define sub2 (rightsection  3))
(makefilter pred?)
 Creates a new filter
that uses pred?
to determine whether or not to keep
elements. Note that makefilter
is very similar to remove
except that remove
takes two parameters (the predicate and
the list) and returns a list, while makefilter
takes
one parameter (the predicate) and returns a function whose purpose is
to read a list and remove elements that match the predicate.
(conjunction pred1? pred2? ... predn?)
 Create a new predicate that holds only if all of
pred1?
, pred2?
, through
predn?
hold (the predicates should be tested in
order). We can use conjunction
to build a better version of
even
.
(define bettereven? (conjunction number? even?))
(disjunction pred1? pred2?
... predn?)
 Create a new predicate that holds if
pred1?
holds or pred2?
holds or
... or predn?
hods. The predicates should be tested
in order.
(complement pred?)
 Create a new predicate
whose result is the opposite of the result of pred?
.
This procedure can be defined as
(define complement (lambda (pred?) ; Result procedure (lambda (val) (not (pred? val)))))
Some people refer to conjunction
as ^and
(for higher and
), disjunction
as
^or
(for higher or
) and complement
as ^not
(for higher not
).
Wednesday, 14 March 2001 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2001S/Readings/higherorder.html
.
Tuesday, 15 October 2002 [Samuel A. Rebelsky]
listof
.
Wednesday, 16 October 2002 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2002F/Readings/higherorder.html
.
Thursday, 13 February 2003 [Samuel A. Rebelsky]
andp
to conjunction
and from orp
to
disjunction
). Also added notes on the highernames
of these procedures.
Friday, 14 February 2003 [Samuel A. Rebelsky]
apply a procedure to every value in a list.
Monday, 11 March 2003 [Samuel A. Rebelsky]
http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003S/Readings/higherorder.html
.
[Skip to Body]
Primary:
[Front Door]
[Current]
[Glance]

[Honesty]
[Instructions]
[Links]
[Guidelines for Lab Writeups]
Groupings:
[EBoards]
[Examples]
[Exams]
[Handouts]
[Homework]
[Labs]
[Outlines]
[Readings]
[Reference]
Misc:
[Scheme Report]
[Glimmer Scheme Reference]
[CSC151.01 (Gum)]
[CSC151 2003S]
[CSC151 2002F]
[SamR]
Disclaimer:
I usually create these pages on the fly
, which means that I rarely
proofread them and they may contain bad grammar and incorrect details.
It also means that I tend to update them regularly (see the history for
more details). Feel free to contact me with any suggestions for changes.
This document was generated by
Siteweaver on Tue Dec 9 14:00:12 2003.
The source to the document was last modified on Mon Sep 1 13:26:32 2003.
This document may be found at http://www.cs.grinnell.edu/~rebelsky/Courses/CS151/2003F/Readings/higherorder.html
.
; ; Check with Bobby
Samuel A. Rebelsky, rebelsky@grinnell.edu