first-class status of programming-language elements is due to the British
computer scientist Christopher Strachey (1916-1975).
They may be named by variables.
They may be passed as arguments to procedures.
They may be returned as the results of procedures.
They may be included in data structures.
We'll see examples of this
after we introduce data structures in Chapter 2.
Lisp, unlike other common programming languages, awards procedures full
first-class status. This poses challenges for efficient implementation, but
the resulting gain in expressive power is enormous.
The major
implementation cost of first-class procedures is that allowing procedures to be
returned as values requires reserving storage for a procedure's free variables
even while the procedure is not executing. In the Scheme implementation we
will study in section 4-1, these variables are stored in the procedure's
environment.
Exercise 1.40: Define a procedure cubic
that can be used together with the newtons-method procedure in
expressions of the form
(newtons-method (cubic a b c) 1)
to approximate zeros of the cubic x^3 +
ax^2 + bx + c.
Exercise 1.41: Define a procedure double
that takes a procedure of one argument as argument and returns a procedure that
applies the original procedure twice. For example, if inc is a
procedure that adds 1 to its argument, then (double inc) should be a
procedure that adds 2. What value is returned by
(((double (double double)) inc) 5)
Exercise 1.42: Let f and g be two
one-argument functions. The composition
f after g is defined
to be the function x |-> f(g(x)). Define a procedure
compose that implements composition. For example, if inc is a
procedure that adds 1 to its argument,
((compose square inc) 6)
49
Exercise 1.43: If f is a numerical function
and n is a positive integer, then we can form the nth repeated
application of f, which is defined to be the function whose value at x
is f(f(...(f(x))...)). For example, if f is the
function x |-> x + 1, then the nth repeated application of f is
the function x |-> x + n. If f is the operation of squaring a
number, then the nth repeated application of f is the function that
raises its argument to the 2^nth power. Write a procedure that takes as
inputs a procedure that computes f and a positive integer n and returns
the procedure that computes the nth repeated application of f. Your
procedure should be able to be used as follows:
((repeated square 2) 5)
625
Hint: You may find it convenient to use compose from Exercise
1-42.
Exercise 1.44: The idea of smoothing
a
function is an important concept in signal processing. If f is a function
and dx is some small number, then the smoothed version of f is the
function whose value at a point x is the average of f(x -
dx), f(x), and f(x + dx). Write a procedure
smooth that takes as input a procedure that computes f and returns a
procedure that computes the smoothed f. It is sometimes valuable to
repeatedly smooth a function (that is, smooth the smoothed function, and so on)
to obtained the n
-fold smoothed function. Show how to generate
the n-fold smoothed function of any given function using smooth and
repeated from Exercise 1-43.
Exercise 1.45: We saw in section 1-3-3
that attempting to compute square roots by naively finding a fixed point of
y |-> x/y does not converge, and that this can be fixed by average
damping. The same method works for finding cube roots as fixed points of the
average-damped y |-> x/y^2. Unfortunately, the process does not
work for fourth roots---a single average damp is not enough to make a
fixed-point search for y |-> x/y^3 converge. On the other hand, if
we average damp twice (i.e., use the average damp of the average damp of y
|-> x/y^3) the fixed-point search does converge. Do some experiments
to determine how many average damps are required to compute nth roots as a
fixed-point search based upon repeated average damping of y |->
x/y^(n-1). Use this to implement a simple procedure for computing
nth roots using fixed-point , average-damp , and the
repeated procedure of Exercise 1-43. Assume that any arithmetic
operations you need are available as primitives.
Exercise 1.46: Several of the numerical methods
described in this chapter are instances of an extremely general computational
strategy known as iterative improvement
. Iterative improvement says
that, to compute something, we start with an initial guess for the answer, test
if the guess is good enough, and otherwise improve the guess and continue the
process using the improved guess as the new guess. Write a procedure
iterative-improve that takes two procedures as arguments: a method for
telling whether a guess is good enough and a method for improving a guess.
Iterative-improve should return as its value a procedure that takes a
guess as argument and keeps improving the guess until it is good enough.
Rewrite the sqrt procedure of section 1-1-7 and the
fixed-point procedure of section 1-3-3 in terms of
iterative-improve .
@chapter Building Abstractions with Data
We now come to the decisive step of mathematical abstraction: we forget about
what the symbols stand for. ...[The mathematician] need not be idle; there
are many operations which he may carry out with these symbols, without ever
having to look at the things they stand for.
---Hermann Weyl, @cite{The Mathematical Way of Thinking}
We concentrated in Chapter 1 on computational processes and on the role
of procedures in program design. We saw how to use primitive data (numbers)
and primitive operations (arithmetic operations), how to combine procedures to
form compound procedures through composition, conditionals, and the use of
parameters, and how to abstract procedures by using define . We saw that
a procedure can be regarded as a pattern for the local evolution of a process,
and we classified, reasoned about, and performed simple algorithmic analyses of
some common patterns for processes as embodied in procedures. We also saw that
higher-order procedures enhance the power of our language by enabling us to
manipulate, and thereby to reason in terms of, general methods of computation.
This is much of the essence of programming.
In this chapter we are going to look at more complex data. All the procedures
in Chapter 1 operate on simple numerical data, and simple data are not
sufficient for many of the problems we wish to address using computation.
Programs are typically designed to model complex phenomena, and more often than
not one must construct computational objects that have several parts in order
to model real-world phenomena that have several aspects. Thus, whereas our
focus in Chapter 1 was on building abstractions by combining procedures
to form compound procedures, we turn in this chapter to another key aspect of
any programming language: the means it provides for building abstractions by
combining data objects to form compound data
.
Why do we want compound data in a programming language? For the same reasons
that we want compound procedures: to elevate the conceptual level at which we
can design our programs, to increase the modularity of our designs, and to
enhance the expressive power of our language. Just as the ability to define
procedures enables us to deal with processes at a higher conceptual level than
that of the primitive operations of the language, the ability to construct
compound data objects enables us to deal with data at a higher conceptual level
than that of the primitive data objects of the language.
Consider the task of designing a system to perform arithmetic with rational
numbers. We could imagine an operation add-rat that takes two rational
numbers and produces their sum. In terms of simple data, a rational number can
be thought of as two integers: a numerator and a denominator. Thus, we could
design a program in which each rational number would be represented by two
integers (a numerator and a denominator) and where add-rat would be
implemented by two procedures (one producing the numerator of the sum and one
producing the denominator). But this would be awkward, because we would then
need to explicitly keep track of which numerators corresponded to which
denominators. In a system intended to perform many operations on many rational
numbers, such bookkeeping details would clutter the programs substantially, to
say nothing of what they would do to our minds. It would be much better if we
could ``glue together'' a numerator and denominator to form a pair---a
compound data object
---that our programs could manipulate in a way
that would be consistent with regarding a rational number as a single
conceptual unit.
The use of compound data also enables us to increase the modularity of our
programs. If we can manipulate rational numbers directly as objects in their
own right, then we can separate the part of our program that deals with
rational numbers per se from the details of how rational numbers may be
represented as pairs of integers. The general technique of isolating the parts
of a program that deal with how data objects are represented from the parts of
a program that deal with how data objects are used is a powerful design
methodology called data abstraction
. We will see how data
abstraction makes programs much easier to design, maintain, and modify.
The use of compound data leads to a real increase in the expressive
power of our programming language. Consider the idea of forming a
``linear combination'' ax + by. We might like to write
a procedure that would accept a, b, x, and y as
arguments and return the value of ax + by. This
presents no difficulty if the arguments are to be numbers, because we
can readily define the procedure
(define (linear-combination a b x y)
(+ (* a x) (* b y)))
But suppose we are not concerned only with numbers. Suppose we would like to
express, in procedural terms, the idea that one can form linear combinations
whenever addition and multiplication are defined---for rational numbers,
complex numbers, polynomials, or whatever. We could express this as a
procedure of the form
(define (linear-combination a b x y)
(add (mul a x) (mul b y)))
where add and mul are not the primitive procedures + and
* but rather more complex things that will perform the appropriate
operations for whatever kinds of data we pass in as the arguments a ,
b , x , and y . The key point is that the only thing
linear-combination should need to know about a , b ,
x , and y is that the procedures add and mul will
perform the appropriate manipulations. From the perspective of the procedure
linear-combination , it is irrelevant what a , b , x ,
and y are and even more irrelevant how they might happen to be
represented in terms of more primitive data. This same example shows why it is
important that our programming language provide the ability to manipulate
compound objects directly: Without this, there is no way for a procedure such
as linear-combination to pass its arguments along to add and
mul without having to know their detailed structure.
The
ability to directly manipulate procedures provides an analogous increase in the
expressive power of a programming language. For example, in section
1-3-1 we introduced the sum procedure, which takes a procedure
term as an argument and computes the sum of the values of term
over some specified interval. In order to define sum , it is crucial
that we be able to speak of a procedure such as term as an entity in its
own right, without regard for how term might be expressed with more
primitive operations. Indeed, if we did not have the notion of ``a
procedure,'' it is doubtful that we would ever even think of the possibility of
defining an operation such as sum . Moreover, insofar as performing the
summation is concerned, the details of how term may be constructed from
more primitive operations are irrelevant.
We begin this chapter by implementing the rational-number arithmetic system
mentioned above. This will form the background for our discussion of compound
data and data abstraction. As with compound procedures, the main issue to be
addressed is that of abstraction as a technique for coping with complexity, and
we will see how data abstraction enables us to erect suitable
abstraction barriers
between different parts of a program.
We will see that the key to forming compound data is that a programming
language should provide some kind of ``glue'' so that data objects can be
combined to form more complex data objects. There are many possible kinds of
glue. Indeed, we will discover how to form compound data using no special
``data'' operations at all, only procedures. This will further blur the
distinction between ``procedure'' and ``data,'' which was already becoming
tenuous toward the end of Chapter 1. We will also explore some
conventional techniques for representing sequences and trees. One key idea in
dealing with compound data is the notion of closure
---that the glue
we use for combining data objects should allow us to combine not only primitive
data objects, but compound data objects as well. Another key idea is that
compound data objects can serve as conventional interfaces
for
combining program modules in mix-and-match ways. We illustrate some of these
ideas by presenting a simple graphics language that exploits closure.
We will then augment the representational power of our language by introducing
symbolic expressions
---data whose elementary parts can be arbitrary
symbols rather than only numbers. We explore various alternatives for
representing sets of objects. We will find that, just as a given numerical
function can be computed by many different computational processes, there are
many ways in which a given data structure can be represented in terms of
simpler objects, and the choice of representation can have significant impact
on the time and space requirements of processes that manipulate the data. We
will investigate these ideas in the context of symbolic differentiation, the
representation of sets, and the encoding of information.
Next we will take up the problem of working with data that may be represented
differently by different parts of a program. This leads to the need to
implement generic operations
, which must handle many different types
of data. Maintaining modularity in the presence of generic operations requires
more powerful abstraction barriers than can be erected with simple data
abstraction alone. In particular, we introduce data-directed
programming
as a technique that allows individual data representations to be
designed in isolation and then combined additively
(i.e., without
modification). To illustrate the power of this approach to system design, we
close the chapter by applying what we have learned to the implementation of a
package for performing symbolic arithmetic on polynomials, in which the
coefficients of the polynomials can be integers, rational numbers, complex
numbers, and even other polynomials.
@menu
* 2-1:: Introduction to Data Abstraction
* 2-2:: Hierarchical Data and the Closure Property
* 2-3:: Symbolic Data
* 2-4:: Multiple Representations for Abstract Data
* 2-5:: Systems with Generic Operations
@end menu
Introduction to Data Abstraction
In section 1-1-8, we noted that a procedure used as an element in
creating a more complex procedure could be regarded not only as a collection of
particular operations but also as a procedural abstraction. That is, the
details of how the procedure was implemented could be suppressed, and the
particular procedure itself could be replaced by any other procedure with the
same overall behavior. In other words, we could make an abstraction that would
separate the way the procedure would be used from the details of how the
procedure would be implemented in terms of more primitive procedures. The
analogous notion for compound data is called data abstraction
. Data
abstraction is a methodology that enables us to isolate how a compound data
object is used from the details of how it is constructed from more primitive
data objects.
The basic idea of data abstraction is to structure the programs that are to use
compound data objects so that they operate on ``abstract data.'' That is, our
programs should use data in such a way as to make no assumptions about the data
that are not strictly necessary for performing the task at hand. At the same
time, a ``concrete'' data representation is defined independent of the programs
that use the data. The interface between these two parts of our system will be
a set of procedures, called selectors
and constructors
,
that implement the abstract data in terms of the concrete representation. To
illustrate this technique, we will consider how to design a set of procedures
for manipulating rational numbers.
@menu
* 2-1-1:: Example: Arithmetic Operations for Rational Numbers
* 2-1-2:: Abstraction Barriers
* 2-1-3:: What Is Meant by Data?
* 2-1-4:: Extended Exercise: Interval Arithmetic
@end menu
Example: Arithmetic Operations for Rational Numbers
Suppose we want to do arithmetic with rational numbers. We want to be able to
add, subtract, multiply, and divide them and to test whether two rational
numbers are equal.
Let us begin by assuming that we already have a way of constructing a rational
number from a numerator and a denominator. We also assume that, given a
rational number, we have a way of extracting (or selecting) its numerator and
its denominator. Let us further assume that the constructor and selectors are
available as procedures:
(make-rat > <@var{d>)} returns therational number whose
numerator is the integer > and whose denominator is the integer
>.
(numer >) returns the numerator of the rational number
>.
(denom >) returns the denominator of the rational number
>.
We are using here a powerful strategy of synthesis: wishful thinking
.
We haven't yet said how a rational number is represented, or how the procedures
numer , denom , and make-rat should be implemented. Even
so, if we did have these three procedures, we could then add, subtract,
multiply, divide, and test equality by using the following relations:
Now we have the operations on rational numbers defined in terms of the selector
and constructor procedures numer , denom , and make-rat .
But we haven't yet defined these. What we need is some way to glue together a
numerator and a denominator to form a rational number.
Pairs
To enable us to implement the concrete level of our data abstraction, our
language provides a compound structure called a pair
, which can be
constructed with the primitive procedure cons . This procedure takes two
arguments and returns a compound data object that contains the two arguments as
parts. Given a pair, we can extract the parts using the primitive procedures
car and cdr .
The name cons stands for
``construct.'' The names car and cdr derive from the original
implementation of Lisp on the IBM 704. That machine had an addressing scheme
that allowed one to reference the ``address'' and ``decrement'' parts of a
memory location. Car stands for ``Contents of Address part of
Register'' and cdr (pronounced ``could-er'') stands for ``Contents of
Decrement part of Register.''
Thus, we can use cons , car , and
cdr as follows:
(define x (cons 1 2))
(car x)
1
(cdr x)
2
Notice that a pair is a data object that can be given a name and manipulated,
just like a primitive data object. Moreover, cons can be used to form
pairs whose elements are pairs, and so on:
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
1
(car (cdr z))
3
In section 2-2 we will see how this ability to combine pairs means that
pairs can be used as general-purpose building blocks to create all sorts of
complex data structures. The single compound-data primitive pair
,
implemented by the procedures cons , car , and cdr , is the
only glue we need. Data objects constructed from pairs are called
list-structured
data.
Representing rational numbers
Pairs offer a natural way to complete the rational-number system. Simply
represent a rational number as a pair of two integers: a numerator and a
denominator. Then make-rat , numer , and denom are readily
implemented as follows:
Another way to define the selectors and
constructor is
(define make-rat cons)
(define numer car)
(define denom cdr)
The first definition associates the name make-rat with the value of the
expression cons , which is the primitive procedure that constructs pairs.
Thus make-rat and cons are names for the same primitive
constructor.
Defining selectors and constructors in this way is efficient: Instead of
make-rat calling cons , make-rat is cons , so there is only one procedure called, not two, when
make-rat is called. On the other hand, doing this defeats debugging
aids that trace procedure calls or put breakpoints on procedure calls: You may
want to watch make-rat being called, but you certainly don't want to
watch every call to cons .
We have chosen not to use this style of definition in this book.
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))
Also, in order to display the results of our computations, we can print
rational numbers by printing the numerator, a slash, and the
denominator:
Display is the Scheme primitive for printing data.
The Scheme primitive newline starts a new line for printing. Neither of
these procedures returns a useful value, so in the uses of print-rat
below, we show only what print-rat prints, not what the interpreter
prints as the value returned by print-rat .
As the final example shows, our rational-number implementation does not reduce
rational numbers to lowest terms. We can remedy this by changing
make-rat . If we have a gcd procedure like the one in section
1-2-5 that produces the greatest common divisor of two integers, we can
use gcd to reduce the numerator and the denominator to lowest terms
before constructing the pair:
(define (make-rat n d)
(let ((g (gcd n d)))
(cons (/ n g) (/ d g))))
Now we have
(print-rat (add-rat one-third one-third))
2/3
as desired. This modification was accomplished by changing the constructor
make-rat without changing any of the procedures (such as add-rat
and mul-rat ) that implement the actual operations.
Exercise 2.1: Define a better version of
make-rat that handles both positive and negative arguments.
Make-rat should normalize the sign so that if the rational number is
positive, both the numerator and denominator are positive, and if the rational
number is negative, only the numerator is negative.
Abstraction Barriers
Before continuing with more examples of compound data and data abstraction, let
us consider some of the issues raised by the rational-number example. We
defined the rational-number operations in terms of a constructor
make-rat and selectors numer and denom . In general, the
underlying idea of data abstraction is to identify for each type of data object
a basic set of operations in terms of which all manipulations of data objects
of that type will be expressed, and then to use only those operations in
manipulating the data.
We can envision the structure of the rational-number system as shown in figure
Figure 2-1. The horizontal lines represent abstraction
barriers
that isolate different ``levels'' of the system. At each level, the
barrier separates the programs (above) that use the data abstraction from the
programs (below) that implement the data abstraction. Programs that use
rational numbers manipulate them solely in terms of the procedures supplied
``for public use'' by the rational-number package: add-rat ,
sub-rat , mul-rat , div-rat , and equal-rat? . These,
in turn, are implemented solely in terms of the constructor and selectors
make-rat , numer , and denom , which themselves are
implemented in terms of pairs. The details of how pairs are implemented are
irrelevant to the rest of the rational-number package so long as pairs can be
manipulated by the use of cons , car , and cdr . In effect,
procedures at each level are the interfaces that define the abstraction
barriers and connect the different levels.
Figure 2.1: Data-abstraction barriers in the
rational-number package.
+------------------------------------+
--------| Programs that use rational numbers |--------
+------------------------------------+
Rational numbers in promblem domain
+---------------------------+
------------| add-rat sub-rat ... |-------------
+---------------------------+
Rational numbers as numerators and denominators
+------------------------+
--------------| make-rat numer denom |--------------
+------------------------+
Rational numbers as pairs
+----------------+
------------------| cons car cdr |------------------
+----------------+
However pairs are implemented
This simple idea has many advantages. One advantage is that it makes programs
much easier to maintain and to modify. Any complex data structure can be
represented in a variety of ways with the primitive data structures provided by
a programming language. Of course, the choice of representation influences the
programs that operate on it; thus, if the representation were to be changed at
some later time, all such programs might have to be modified accordingly. This
task could be time-consuming and expensive in the case of large programs unless
the dependence on the representation were to be confined by design to a very
few program modules.
For example, an alternate way to address the problem of reducing rational
numbers to lowest terms is to perform the reduction whenever we access the
parts of a rational number, rather than when we construct it. This leads to
different constructor and selector procedures:
The difference between this implementation and the previous one lies in when we
compute the gcd . If in our typical use of rational numbers we access
the numerators and denominators of the same rational numbers many times, it
would be preferable to compute the gcd when the rational numbers are
constructed. If not, we may be better off waiting until access time to compute
the gcd . In any case, when we change from one representation to the
other, the procedures add-rat , sub-rat , and so on do not have to
be modified at all.
Constraining the dependence on the representation to a few interface procedures
helps us design programs as well as modify them, because it allows us to
maintain the flexibility to consider alternate implementations. To continue
with our simple example, suppose we are designing a rational-number package and
we can't decide initially whether to perform the gcd at construction
time or at selection time. The data-abstraction methodology gives us a way to
defer that decision without losing the ability to make progress on the rest of
the system.
Exercise 2.2: Consider the problem of
representing line segments in a plane. Each segment is represented as a pair
of points: a starting point and an ending point. Define a constructor
make-segment and selectors start-segment and end-segment
that define the representation of segments in terms of points. Furthermore, a
point can be represented as a pair of numbers: the x coordinate and the
y coordinate. Accordingly, specify a constructor make-point and
selectors x-point and y-point that define this representation.
Finally, using your selectors and constructors, define a procedure
midpoint-segment that takes a line segment as argument and returns its
midpoint (the point whose coordinates are the average of the coordinates of the
endpoints). To try your procedures, you'll need a way to print points:
Exercise 2.3: Implement a representation for
rectangles in a plane. (Hint: You may want to make use of Exercise 2-2.)
In terms of your constructors and selectors, create procedures that compute the
perimeter and the area of a given rectangle. Now implement a different
representation for rectangles. Can you design your system with suitable
abstraction barriers, so that the same perimeter and area procedures will work
using either representation?
What Is Meant by Data?
We began the rational-number implementation in section 2-1-1 by
implementing the rational-number operations add-rat , sub-rat , and
so on in terms of three unspecified procedures: make-rat , numer ,
and denom . At that point, we could think of the operations as being
defined in terms of data objects---numerators, denominators, and rational
numbers---whose behavior was specified by the latter three procedures.
But exactly what is meant by data
? It is not enough to say
``whatever is implemented by the given selectors and constructors.'' Clearly,
not every arbitrary set of three procedures can serve as an appropriate basis
for the rational-number implementation. We need to guarantee that, if we
construct a rational number x from a pair of integers n and
d , then extracting the numer and the denom of x and
dividing them should yield the same result as dividing n by d .
In other words, make-rat , numer , and denom must satisfy
the condition that, for any integer n and any non-zero integer d ,
if x is ( make-rat n d ), then
(numer x) n
--------- = ---
(denom x) d
In fact, this is the only condition make-rat , numer , and
denom must fulfill in order to form a suitable basis for a
rational-number representation. In general, we can think of data as defined by
some collection of selectors and constructors, together with specified
conditions that these procedures must fulfill in order to be a valid
representation.
Surprisingly, this idea is very difficult to formulate
rigorously. There are two approaches to giving such a formulation. One,
pioneered by C. A. R. Hoare (1972), is known as the method of abstract
models
. It formalizes the ``procedures plus conditions'' specification as
outlined in the rational-number example above. Note that the condition on the
rational-number representation was stated in terms of facts about integers
(equality and division). In general, abstract models define new kinds of data
objects in terms of previously defined types of data objects. Assertions about
data objects can therefore be checked by reducing them to assertions about
previously defined data objects. Another approach, introduced by Zilles at
@acronym{MIT
, by Goguen, Thatcher, Wagner, and Wright at IBM (see Thatcher,
Wagner, and Wright 1978), and by Guttag at Toronto (see Guttag 1977), is called
algebraic specification
. It regards the ``procedures'' as elements
of an abstract algebraic system whose behavior is specified by axioms that
correspond to our ``conditions,'' and uses the techniques of abstract algebra
to check assertions about data objects. Both methods are surveyed in the paper
by Liskov and Zilles (1975).}
This point of view can serve to define not only ``high-level'' data objects,
such as rational numbers, but lower-level objects as well. Consider the notion
of a pair, which we used in order to define our rational numbers. We never
actually said what a pair was, only that the language supplied procedures
cons , car , and cdr for operating on pairs. But the only
thing we need to know about these three operations is that if we glue two
objects together using cons we can retrieve the objects using car
and cdr . That is, the operations satisfy the condition that, for any
objects x and y , if z is (cons x y) then (car
z) is x and (cdr z) is y . Indeed, we mentioned that
these three procedures are included as primitives in our language. However,
any triple of procedures that satisfies the above condition can be used as the
basis for implementing pairs. This point is illustrated strikingly by the fact
that we could implement cons , car , and cdr without using
any data structures at all but only using procedures.  Nevertheless, all we need to do to show that this is a valid
way to represent pairs is to verify that these procedures satisfy the condition
given above.
The subtle point to notice is that the value returned by (cons x y) is a
procedure---namely the internally defined procedure dispatch , which
takes one argument and returns either x or y depending on whether
the argument is 0 or 1. Correspondingly, (car z) is defined to apply
z to 0. Hence, if z is the procedure formed by (cons x
y) , then z applied to 0 will yield x . Thus, we have shown that
(car (cons x y)) yields x , as desired. Similarly, (cdr
(cons x y)) applies the procedure returned by (cons x y) to 1, which
returns y . Therefore, this procedural implementation of pairs is a
valid implementation, and if we access pairs using only cons ,
car , and cdr we cannot distinguish this implementation from one
that uses ``real'' data structures.
The point of exhibiting the procedural representation of pairs is not that our
language works this way (Scheme, and Lisp systems in general, implement pairs
directly, for efficiency reasons) but that it could work this way. The
procedural representation, although obscure, is a perfectly adequate way to
represent pairs, since it fulfills the only conditions that pairs need to
fulfill. This example also demonstrates that the ability to manipulate
procedures as objects automatically provides the ability to represent compound
data. This may seem a curiosity now, but procedural representations of data
will play a central role in our programming repertoire. This style of
programming is often called message passing
, and we will be using it
as a basic tool in Chapter 3 when we address the issues of modeling and
simulation.
Exercise 2.4: Here is an alternative procedural
representation of pairs. For this representation, verify that (car (cons
x y)) yields x for any objects x and y .
(define (cons x y)
(lambda (m) (m x y)))
(define (car z)
(z (lambda (p q) p)))
What is the corresponding definition of cdr ? (Hint: To verify that this
works, make use of the substitution model of section 1-1-5.)
Exercise 2.5: Show that we can represent pairs of
nonnegative integers using only numbers and arithmetic operations if we
represent the pair a and b as the integer that is the product 2^a
3^b. Give the corresponding definitions of the procedures cons ,
car , and cdr .
Exercise 2.6: In case representing pairs as
procedures wasn't mind-boggling enough, consider that, in a language that can
manipulate procedures, we can get by without numbers (at least insofar as
nonnegative integers are concerned) by implementing 0 and the operation of
adding 1 as
This representation is known as Church numerals
, after its inventor,
Alonzo Church, the logician who invented the [lambda] calculus.
Define one and two directly (not in terms of zero and
add-1 ). (Hint: Use substitution to evaluate (add-1 zero) ). Give
a direct definition of the addition procedure + (not in terms of
repeated application of add-1 ).
Extended Exercise: Interval Arithmetic
Alyssa P. Hacker is designing a system to help people solve engineering
problems. One feature she wants to provide in her system is the ability to
manipulate inexact quantities (such as measured parameters of physical devices)
with known precision, so that when computations are done with such approximate
quantities the results will be numbers of known precision.
Electrical engineers will be using Alyssa's system to compute electrical
quantities. It is sometimes necessary for them to compute the value of a
parallel equivalent resistance R_p of two resistors R_1 and R_2
using the formula
1
R_p = -------------
1/R_1 + 1/R_2
Resistance values are usually known only up to some tolerance guaranteed by the
manufacturer of the resistor. For example, if you buy a resistor labeled ``6.8
ohms with 10% tolerance'' you can only be sure that the resistor has a
resistance between 6.8 - 0.68 = 6.12 and 6.8 + 0.68 = 7.48 ohms. Thus, if you
have a 6.8-ohm 10% resistor in parallel with a 4.7-ohm 5% resistor, the
resistance of the combination can range from about 2.58 ohms (if the two
resistors are at the lower bounds) to about 2.97 ohms (if the two resistors are
at the upper bounds).
Alyssa's idea is to implement ``interval arithmetic'' as a set of arithmetic
operations for combining ``intervals'' (objects that represent the range of
possible values of an inexact quantity). The result of adding, subtracting,
multiplying, or dividing two intervals is itself an interval, representing the
range of the result.
Alyssa postulates the existence of an abstract object called an ``interval''
that has two endpoints: a lower bound and an upper bound. She also presumes
that, given the endpoints of an interval, she can construct the interval using
the data constructor make-interval . Alyssa first writes a procedure for
adding two intervals. She reasons that the minimum value the sum could be is
the sum of the two lower bounds and the maximum value it could be is the sum of
the two upper bounds:
Alyssa also works out the product of two intervals by finding the minimum and
the maximum of the products of the bounds and using them as the bounds of the
resulting interval. ( Min and max are primitives that find the
minimum or maximum of any number of arguments.)
To divide two intervals, Alyssa multiplies the first by the reciprocal of the
second. Note that the bounds of the reciprocal interval are the reciprocal of
the upper bound and the reciprocal of the lower bound, in that order.
(define (div-interval x y)
(mul-interval x
(make-interval (/ 1.0 (upper-bound y))
(/ 1.0 (lower-bound y)))))
Exercise 2.7: Alyssa's program is incomplete
because she has not specified the implementation of the interval abstraction.
Here is a definition of the interval constructor:
(define (make-interval a b) (cons a b))
Define selectors upper-bound and lower-bound to complete the
implementation.
Exercise 2.8: Using reasoning analogous to
Alyssa's, describe how the difference of two intervals may be computed. Define
a corresponding subtraction procedure, called sub-interval .
Exercise 2.9: The width
of an interval
is half of the difference between its upper and lower bounds. The width is a
measure of the uncertainty of the number specified by the interval. For some
arithmetic operations the width of the result of combining two intervals is a
function only of the widths of the argument intervals, whereas for others the
width of the combination is not a function of the widths of the argument
intervals. Show that the width of the sum (or difference) of two intervals is
a function only of the widths of the intervals being added (or subtracted).
Give examples to show that this is not true for multiplication or division.
Exercise 2.10: Ben Bitdiddle, an expert systems
programmer, looks over Alyssa's shoulder and comments that it is not clear what
it means to divide by an interval that spans zero. Modify Alyssa's code to
check for this condition and to signal an error if it occurs.
Exercise 2.11: In passing, Ben also cryptically
comments: ``By testing the signs of the endpoints of the intervals, it is
possible to break mul-interval into nine cases, only one of which
requires more than two multiplications.'' Rewrite this procedure using Ben's
suggestion.
After debugging her program, Alyssa shows it to a potential user, who complains
that her program solves the wrong problem. He wants a program that can deal
with numbers represented as a center value and an additive tolerance; for
example, he wants to work with intervals such as 3.5 +/- 0.15 rather than
[3.35, 3.65]. Alyssa returns to her desk and fixes this problem by supplying
an alternate constructor and alternate selectors:
Unfortunately, most of Alyssa's users are engineers. Real engineering
situations usually involve measurements with only a small uncertainty, measured
as the ratio of the width of the interval to the midpoint of the interval.
Engineers usually specify percentage tolerances on the parameters of devices,
as in the resistor specifications given earlier.
Exercise 2.12: Define a constructor
make-center-percent that takes a center and a percentage tolerance and
produces the desired interval. You must also define a selector percent
that produces the percentage tolerance for a given interval. The center
selector is the same as the one shown above.
Exercise 2.13: Show that under the assumption of
small percentage tolerances there is a simple formula for the approximate
percentage tolerance of the product of two intervals in terms of the tolerances
of the factors. You may simplify the problem by assuming that all numbers are
positive.
After considerable work, Alyssa P. Hacker delivers her finished system.
Several years later, after she has forgotten all about it, she gets a frenzied
call from an irate user, Lem E. Tweakit. It seems that Lem has noticed that
the formula for parallel resistors can be written in two algebraically
equivalent ways:
R_1 R_2
---------
R_1 + R_2
and
1
-------------
1/R_1 + 1/R_2
He has written the following two programs, each of which computes the
parallel-resistors formula differently:
(define (par1 r1 r2)
(div-interval (mul-interval r1 r2)
(add-interval r1 r2)))
(define (par2 r1 r2)
(let ((one (make-interval 1 1)))
(div-interval one
(add-interval (div-interval one r1)
(div-interval one r2)))))
Lem complains that Alyssa's program gives different answers for the two ways of
computing. This is a serious complaint.
Exercise 2.14: Demonstrate that Lem is right.
Investigate the behavior of the system on a variety of arithmetic
expressions. Make some intervals A and B, and use them in computing the
expressions A/A and A/B. You will get the most insight by
using intervals whose width is a small percentage of the center value. Examine
the results of the computation in center-percent form (see Exercise
2-12).
Exercise 2.15: Eva Lu Ator, another user, has
also noticed the different intervals computed by different but algebraically
equivalent expressions. She says that a formula to compute with intervals using
Alyssa's system will produce tighter error bounds if it can be written in such
a form that no variable that represents an uncertain number is repeated. Thus,
she says, par2 is a ``better'' program for parallel resistances than
par1 . Is she right? Why?
Exercise 2.16: Explain, in general, why
equivalent algebraic expressions may lead to different answers. Can you devise
an interval-arithmetic package that does not have this shortcoming, or is this
task impossible? (Warning: This problem is very difficult.)
Hierarchical Data and the Closure Property
As we have seen, pairs provide a primitive ``glue'' that we can use to
construct compound data objects. Figure 2-2 shows a standard way to
visualize a pair---in this case, the pair formed by (cons 1 2) . In this
representation, which is called box-and-pointer notation
, each object
is shown as a pointer
to a box. The box for a primitive object
contains a representation of the object. For example, the box for a number
contains a numeral. The box for a pair is actually a double box, the left part
containing (a pointer to) the car of the pair and the right part
containing the cdr .
Figure 2.2: Box-and-pointer representation of
(cons 1 2) .
We have already seen that cons can be used to combine not only numbers
but pairs as well. (You made use of this fact, or should have, in doing
Exercise 2-2 and Exercise 2-3.) As a consequence, pairs provide a
universal building block from which we can construct all sorts of data
structures. Figure 2-3 shows two ways to use pairs to combine the
numbers 1, 2, 3, and 4.
Figure 2.3: Two ways to combine 1, 2, 3, and 4
using pairs.
The ability to create pairs whose elements are pairs is the essence of list
structure's importance as a representational tool. We refer to this ability as
the closure property
of cons . In general, an operation for
combining data objects satisfies the closure property if the results of
combining things with that operation can themselves be combined using the same
operation.
The use of the word ``closure'' here comes from abstract
algebra, where a set of elements is said to be closed under an operation if
applying the operation to elements in the set produces an element that is again
an element of the set. The Lisp community also (unfortunately) uses the word
``closure'' to describe a totally unrelated concept: A closure is an
implementation technique for representing procedures with free variables. We
do not use the word ``closure'' in this second sense in this book.
Closure
is the key to power in any means of combination because it permits us to create
hierarchical
structures---structures made up of parts, which
themselves are made up of parts, and so on.
From the outset of Chapter 1, we've made essential use of closure in
dealing with procedures, because all but the very simplest programs rely on the
fact that the elements of a combination can themselves be combinations. In
this section, we take up the consequences of closure for compound data. We
describe some conventional techniques for using pairs to represent sequences
and trees, and we exhibit a graphics language that illustrates closure in a
vivid way.
The notion that a means of combination should satisfy
closure is a straightforward idea. Unfortunately, the data combiners provided
in many popular programming languages do not satisfy closure, or make closure
cumbersome to exploit. In Fortran or Basic, one typically combines data
elements by assembling them into arrays---but one cannot form arrays whose
elements are themselves arrays. Pascal and C admit structures whose elements
are structures. However, this requires that the programmer manipulate pointers
explicitly, and adhere to the restriction that each field of a structure can
contain only elements of a prespecified form. Unlike Lisp with its pairs,
these languages have no built-in general-purpose glue that makes it easy to
manipulate compound data in a uniform way. This limitation lies behind Alan
Perlis's comment in his foreword to this book: ``In Pascal the plethora of
declarable data structures induces a specialization within functions that
inhibits and penalizes casual cooperation. It is better to have 100 functions
operate on one data structure than to have 10 functions operate on 10 data
structures.''
@menu
* 2-2-1:: Representing Sequences
* 2-2-2:: Hierarchical Structures
* 2-2-3:: Sequences as Conventional Interfaces
* 2-2-4:: Example: A Picture Language
@end menu
Representing Sequences
Figure 2.4: The sequence 1, 2, 3, 4 represented as
a chain of pairs.
One of the useful structures we can build with pairs is a
sequence
---an ordered collection of data objects. There are, of
course, many ways to represent sequences in terms of pairs. One particularly
straightforward representation is illustrated in Figure 2-4, where the
sequence 1, 2, 3, 4 is represented as a chain of pairs. The car of each
pair is the corresponding item in the chain, and the cdr of the pair is
the next pair in the chain. The cdr of the final pair signals the end
of the sequence by pointing to a distinguished value that is not a pair,
represented in box-and-pointer diagrams as a diagonal line and in programs as
the value of the variable nil . The entire sequence is constructed by
nested cons operations:
(cons 1
(cons 2
(cons 3
(cons 4 nil))))
Such a sequence of pairs, formed by nested cons es, is called a
list
, and Scheme provides a primitive called list to help in
constructing lists.
In this book, we use list
to mean a
chain of pairs terminated by the end-of-list marker. In contrast, the term
list structure
refers to any data structure made out of pairs, not
just to lists.
The above sequence could be produced by (list 1 2 3 4) .
In general,
(list ... )
is equivalent to
(cons
(cons
(cons ...
(cons
nil)
...)))
Lisp systems conventionally print lists by printing the sequence of elements,
enclosed in parentheses. Thus, the data object in Figure 2-4 is printed
as (1 2 3 4) :
Be careful not to confuse the expression (list 1 2 3 4) with the list
(1 2 3 4) , which is the result obtained when the expression is
evaluated. Attempting to evaluate the expression (1 2 3 4) will signal
an error when the interpreter tries to apply the procedure 1 to
arguments 2 , 3 , and 4 .
We can think of car as selecting the first item in the list, and of
cdr as selecting the sublist consisting of all but the first item.
Nested applications of car and cdr can be used to extract the
second, third, and subsequent items in the list.
Since nested
applications of car and cdr are cumbersome to write, Lisp
dialects provide abbreviations for them---for instance,
(cadr (arg)) = (car (cdr (arg)))
The names of all such procedures start with c and end with r .
Each a between them stands for a car operation and each d
for a cdr operation, to be applied in the same order in which they
appear in the name. The names car and cdr persist because simple
combinations like cadr are pronounceable.
The constructor cons
makes a list like the original one, but with an additional item at the
beginning.
The value of nil , used to terminate the chain of pairs, can be thought
of as a sequence of no elements, the empty list
. The word
nil
is a contraction of the Latin word nihil, which means
``nothing.''
It's remarkable how much energy in the standardization of
Lisp dialects has been dissipated in arguments that are literally over nothing:
Should nil be an ordinary name? Should the value of nil be a
symbol? Should it be a list? Should it be a pair? In Scheme, nil is
an ordinary name, which we use in this section as a variable whose value is the
end-of-list marker (just as true is an ordinary variable that has a true
value). Other dialects of Lisp, including Common Lisp, treat nil as a
special symbol. The authors of this book, who have endured too many language
standardization brawls, would like to avoid the entire issue. Once we have
introduced quotation in section 2-3, we will denote the empty list as
'() and dispense with the variable nil entirely.
List operations
The use of pairs to represent sequences of elements as lists is accompanied by
conventional programming techniques for manipulating lists by successively
`` cdr ing down'' the lists. For example, the procedure list-ref
takes as arguments a list and a number n and returns the nth item of
the list. It is customary to number the elements of the list beginning with 0.
The method for computing list-ref is the following:
For n = 0, list-ref should return the car of the list.
Otherwise, list-ref should return the (n - 1)st item of the
cdr of the list.
Often we cdr down the whole list. To aid in this, Scheme includes a
primitive predicate null? , which tests whether its argument is the empty
list. The procedure length , which returns the number of items in a
list, illustrates this typical pattern of use:
The length procedure implements a simple recursive plan. The reduction
step is:
The length of any list is 1 plus the length of the cdr of
the list.
This is applied successively until we reach the base case:
The length of the empty list is 0.
We could also compute length in an iterative style:
(define (length items)
(define (length-iter a count)
(if (null? a)
count
(length-iter (cdr a) (+ 1 count))))
(length-iter items 0))
Another conventional programming technique is to `` cons up'' an answer
list while cdr ing down a list, as in the procedure append , which
takes two lists as arguments and combines their elements to make a new list:
Exercise 2.17: Define a procedure
last-pair that returns the list that contains only the last element of a
given (nonempty) list:
(last-pair (list 23 72 149 34))
(34)
Exercise 2.18: Define a procedure reverse
that takes a list as argument and returns a list of the same elements in
reverse order:
(reverse (list 1 4 9 16 25))
(25 16 9 4 1)
Exercise 2.19: Consider the change-counting
program of section 1-2-2. It would be nice to be able to easily change
the currency used by the program, so that we could compute the number of ways
to change a British pound, for example. As the program is written, the
knowledge of the currency is distributed partly into the procedure
first-denomination and partly into the procedure count-change
(which knows that there are five kinds of U.S. coins). It would be nicer to be
able to supply a list of coins to be used for making change.
We want to rewrite the procedure cc so that its second argument is a
list of the values of the coins to use rather than an integer specifying which
coins to use. We could then have lists that defined each kind of currency:
To do this will require changing the program cc somewhat. It will still
have the same form, but it will access its second argument differently, as
follows:
Define the procedures first-denomination ,
except-first-denomination , and no-more? in terms of primitive
operations on list structures. Does the order of the list coin-values
affect the answer produced by cc ? Why or why not?
Exercise 2.20: The procedures + ,
* , and list take arbitrary numbers of arguments. One way to
define such procedures is to use define with dotted-tail
notation
. In a procedure definition, a parameter list that has a dot before
the last parameter name indicates that, when the procedure is called, the
initial parameters (if any) will have as values the initial arguments, as
usual, but the final parameter's value will be a list
of any
remaining arguments. For instance, given the definition
(define (f x y . z) )
the procedure f can be called with two or more arguments. If we
evaluate
(f 1 2 3 4 5 6)
then in the body of f , x will be 1, y will be 2, and
z will be the list (3 4 5 6) . Given the definition
(define (g . w) )
the procedure g can be called with zero or more arguments. If we
evaluate
(g 1 2 3 4 5 6)
then in the body of g , w will be the list (1 2 3 4 5
6) .
To define f and g using lambda we would
write
(define f (lambda (x y . z) ))
(define g (lambda w ))
Use this notation to write a procedure same-parity that takes one or
more integers and returns a list of all the arguments that have the same
even-odd parity as the first argument. For example,
One extremely useful operation is to apply some transformation to each element
in a list and generate the list of results. For instance, the following
procedure scales each number in a list by a given factor:
We can abstract this general idea and capture it as a common pattern expressed
as a higher-order procedure, just as in section 1-3. The higher-order
procedure here is called map . Map takes as arguments a procedure
of one argument and a list, and returns a list of the results produced by
applying the procedure to each element in the list:
[Footnote
12] Scheme standardly provides a map procedure that
is more general than the one described here. This more general map
takes a procedure of n arguments, together with n lists, and applies
the procedure to all the first elements of the lists, all the second elements
of the lists, and so on, returning a list of the results. For example:
Map is an important construct, not only because it captures a common
pattern, but because it establishes a higher level of abstraction in dealing
with lists. In the original definition of scale-list , the recursive
structure of the program draws attention to the element-by-element processing
of the list. Defining scale-list in terms of map suppresses that
level of detail and emphasizes that scaling transforms a list of elements to a
list of results. The difference between the two definitions is not that the
computer is performing a different process (it isn't) but that we think about
the process differently. In effect, map helps establish an abstraction
barrier that isolates the implementation of procedures that transform lists
from the details of how the elements of the list are extracted and combined.
Like the barriers shown in Figure 2-1, this abstraction gives us the
flexibility to change the low-level details of how sequences are implemented,
while preserving the conceptual framework of operations that transform
sequences to sequences. Section 2-2-3 expands on this use of sequences
as a framework for organizing programs.
Exercise 2.21: The procedure square-list
takes a list of numbers as argument and returns a list of the squares of those
numbers.
(square-list (list 1 2 3 4))
(1 4 9 16)
Here are two different definitions of square-list . Complete both of
them by filling in the missing expressions:
Unfortunately, defining square-list this way produces the answer list in
the reverse order of the one desired. Why?
Louis then tries to fix his bug by interchanging the arguments to cons :
Exercise 2.23: The procedure for-each is
similar to map . It takes as arguments a procedure and a list of
elements. However, rather than forming a list of the results, for-each
just applies the procedure to each of the elements in turn, from left to right.
The values returned by applying the procedure to the elements are not used at
all--- for-each is used with procedures that perform an action, such as
printing. For example,
The value returned by the call to for-each (not illustrated above) can
be something arbitrary, such as true. Give an implementation of
for-each .
Hierarchical Structures
The representation of sequences in terms of lists generalizes naturally to
represent sequences whose elements may themselves be sequences. For example,
we can regard the object ((1 2) 3 4) constructed by
(cons (list 1 2) (list 3 4))
as a list of three items, the first of which is itself a list, (1 2) .
Indeed, this is suggested by the form in which the result is printed by the
interpreter. Figure 2-5 shows the representation of
this structure in terms of pairs.
Figure 2.5: Structure formed by (cons (list 1
2) (list 3 4)) .
Another way to think of sequences whose elements are sequences is as
trees
. The elements of the sequence are the branches of the tree,
and elements that are themselves sequences are subtrees. Figure 2-6
shows the structure in Figure 2-5 viewed as a tree.
Figure 2.6: The list structure in Figure 2-5
viewed as a tree.
((1 2) 3 4)
/\\
/ | \
(1 2) 3 4
/ \
1 2
Recursion is a natural tool for dealing with tree structures, since we can
often reduce operations on trees to operations on their branches, which reduce
in turn to operations on the branches of the branches, and so on, until we
reach the leaves of the tree. As an example, compare the length
procedure of section 2-2-1 with the count-leaves procedure, which
returns the total number of leaves of a tree:
(define x (cons (list 1 2) (list 3 4)))
(length x)
3
(count-leaves x)
4
(list x x)
(((1 2) 3 4) ((1 2) 3 4))
(length (list x x))
2
(count-leaves (list x x))
8
To implement count-leaves , recall the recursive plan for computing
length :
Length of a list x is 1 plus length of the
cdr of x .
Length of the empty list is 0.
Count-leaves is similar. The value for the empty list is the same:
Count-leaves of the empty list is 0.
But in the reduction step, where we strip off the car of the list, we
must take into account that the car may itself be a tree whose leaves we
need to count. Thus, the appropriate reduction step is
Count-leaves of a tree x is count-leaves of the car
of x plus count-leaves of the cdr of x .
Finally, by taking car s we reach actual leaves, so we need another base
case:
Count-leaves of a leaf is 1.
To aid in writing recursive procedures on trees, Scheme provides the primitive
predicate pair? , which tests whether its argument is a pair. Here is
the complete procedure:
The order of the first two clauses in the
cond matters, since the empty list satisfies null? and also is
not a pair.
Exercise 2.24: Suppose we evaluate the
expression (list 1 (list 2 (list 3 4))) . Give the result printed by the
interpreter, the corresponding box-and-pointer structure, and the
interpretation of this as a tree (as in Figure 2-6).
Exercise 2.25: Give combinations of car s
and cdr s that will pick 7 from each of the following lists:
(1 3 (5 7) 9)
((7))
(1 (2 (3 (4 (5 (6 7))))))
Exercise 2.26: Suppose we define x and
y to be two lists:
(define x (list 1 2 3))
(define y (list 4 5 6))
What result is printed by the interpreter in response to evaluating each of the
following expressions:
(append x y)
(cons x y)
(list x y)
Exercise 2.27: Modify your reverse
procedure of Exercise 2-18 to produce a deep-reverse procedure
that takes a list as argument and returns as its value the list with its
elements reversed and with all sublists deep-reversed as well. For example,
Exercise 2.28: Write a procedure fringe
that takes as argument a tree (represented as a list) and returns a list whose
elements are all the leaves of the tree arranged in left-to-right order. For
example,
Exercise 2.29: A binary mobile consists of two
branches, a left branch and a right branch. Each branch is a rod of a certain
length, from which hangs either a weight or another binary mobile. We can
represent a binary mobile using compound data by constructing it from two
branches (for example, using list ):
(define (make-mobile left right)
(list left right))
A branch is constructed from a length (which must be a number) together
with a structure , which may be either a number (representing a simple
weight) or another mobile:
Write the corresponding selectors left-branch and right-branch ,
which return the branches of a mobile, and branch-length and
branch-structure , which return the components of a branch.
Using your selectors, define a procedure total-weight that returns the
total weight of a mobile.
A mobile is said to be balanced
if the torque applied by its top-left
branch is equal to that applied by its top-right branch (that is, if the length
of the left rod multiplied by the weight hanging from that rod is equal to the
corresponding product for the right side) and if each of the submobiles hanging
off its branches is balanced. Design a predicate that tests whether a binary
mobile is balanced.
Suppose we change the representation of mobiles so that the constructors are
(define (make-mobile left right)
(cons left right))
(define (make-branch length structure)
(cons length structure))
How much do you need to change your programs to convert to the new
representation?
Mapping over trees
Just as map is a powerful abstraction for dealing with sequences,
map together with recursion is a powerful abstraction for dealing with
trees. For instance, the scale-tree procedure, analogous to
scale-list of section 2-2-1, takes as arguments a numeric factor
and a tree whose leaves are numbers. It returns a tree of the same shape,
where each number is multiplied by the factor. The recursive plan for
scale-tree is similar to the one for count-leaves :
Another way to implement scale-tree is to regard the tree as a sequence
of sub-trees and use map . We map over the sequence, scaling each
sub-tree in turn, and return the list of results. In the base case, where the
tree is a leaf, we simply multiply by the factor:
Exercise 2.32: We can represent a set as a list
of distinct elements, and we can represent the set of all subsets of the set as
a list of lists. For example, if the set is (1 2 3) , then the set of
all subsets is (() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) . Complete the
following definition of a procedure that generates the set of subsets of a set
and give a clear explanation of why it works:
In working with compound data, we've stressed how data abstraction permits us
to design programs without becoming enmeshed in the details of data
representations, and how abstraction preserves for us the flexibility to
experiment with alternative representations. In this section, we introduce
another powerful design principle for working with data structures---the use of
conventional interfaces
.
In section 1-3 we saw how program abstractions, implemented as
higher-order procedures, can capture common patterns in programs that deal with
numerical data. Our ability to formulate analogous operations for working with
compound data depends crucially on the style in which we manipulate our data
structures. Consider, for example, the following procedure, analogous to the
count-leaves procedure of section 2-2-2, which takes a tree as
argument and computes the sum of the squares of the leaves that are odd:
On the surface, this procedure is very different from the following one, which
constructs a list of all the even Fibonacci numbers Fib(k), where
k is less than or equal to a given integer n:
(define (even-fibs n)
(define (next k)
(if (> k n)
nil
(let ((f (fib k)))
(if (even? f)
(cons f (next (+ k 1)))
(next (+ k 1))))))
(next 0))
Despite the fact that these two procedures are structurally very different, a
more abstract description of the two computations reveals a great deal of
similarity. The first program
enumerates the leaves of a tree;
filters them, selecting the odd ones;
squares each of the selected ones; and
accumulates the results using + , starting with 0.
The second program
enumerates the integers from 0 to n;
computes the Fibonacci number for each integer;
filters them, selecting the even ones; and
accumulates the results using cons , starting with the
empty list.
A signal-processing engineer would find it natural to conceptualize these
processes in terms of signals flowing through a cascade of stages, each of
which implements part of the program plan, as shown in Figure 2-7. In
sum-odd-squares , we begin with an enumerator
, which generates
a ``signal'' consisting of the leaves of a given tree. This signal is passed
through a filter
, which eliminates all but the odd elements. The
resulting signal is in turn passed through a map
, which is a
``transducer'' that applies the square procedure to each element. The
output of the map is then fed to an accumulator
, which combines the
elements using + , starting from an initial 0. The plan for
even-fibs is analogous.
Figure 2.7: The signal-flow plans for the
procedures sum-odd-squares (top) and even-fibs (bottom) reveal
the commonality between the two programs.
Unfortunately, the two procedure definitions above fail to exhibit this
signal-flow structure. For instance, if we examine the sum-odd-squares
procedure, we find that the enumeration is implemented partly by the
null? and pair? tests and partly by the tree-recursive structure
of the procedure. Similarly, the accumulation is found partly in the tests and
partly in the addition used in the recursion. In general, there are no
distinct parts of either procedure that correspond to the elements in the
signal-flow description. Our two procedures decompose the computations in a
different way, spreading the enumeration over the program and mingling it with
the map, the filter, and the accumulation. If we could organize our programs
to make the signal-flow structure manifest in the procedures we write, this
would increase the conceptual clarity of the resulting code.
Sequence Operations
The key to organizing programs so as to more clearly reflect the signal-flow
structure is to concentrate on the ``signals'' that flow from one stage in the
process to the next. If we represent these signals as lists, then we can use
list operations to implement the processing at each of the stages. For
instance, we can implement the mapping stages of the signal-flow diagrams using
the map procedure from section 2-2-1:
(map square (list 1 2 3 4 5))
(1 4 9 16 25)
Filtering a sequence to select only those elements that satisfy a given
predicate is accomplished by
All that remains to implement signal-flow diagrams is to enumerate the sequence
of elements to be processed. For even-fibs , we need to generate the
sequence of integers in a given range, which we can do as follows:
This is, in fact,
precisely the fringe procedure from Exercise 2-28. Here we've
renamed it to emphasize that it is part of a family of general
sequence-manipulation procedures.
Now we can reformulate sum-odd-squares and even-fibs as in the
signal-flow diagrams. For sum-odd-squares , we enumerate the sequence of
leaves of the tree, filter this to keep only the odd numbers in the sequence,
square each element, and sum the results:
For even-fibs , we enumerate the integers from 0 to n, generate the
Fibonacci number for each of these integers, filter the resulting sequence to
keep only the even elements, and accumulate the results into a list:
The value of expressing programs as sequence operations is that this helps us
make program designs that are modular, that is, designs that are constructed by
combining relatively independent pieces. We can encourage modular design by
providing a library of standard components together with a conventional
interface for connecting the components in flexible ways.
Modular construction is a powerful strategy for controlling complexity in
engineering design. In real signal-processing applications, for example,
designers regularly build systems by cascading elements selected from
standardized families of filters and transducers. Similarly, sequence
operations provide a library of standard program elements that we can mix and
match. For instance, we can reuse pieces from the sum-odd-squares and
even-fibs procedures in a program that constructs a list of the squares
of the first n + 1 Fibonacci numbers:
We can also formulate conventional data-processing applications in terms of
sequence operations. Suppose we have a sequence of personnel records and we
want to find the salary of the highest-paid programmer. Assume that we have a
selector salary that returns the salary of a record, and a predicate
programmer? that tests if a record is for a programmer. Then we can
write
These examples give just a hint of the vast range of operations that can be
expressed as sequence operations.
Richard Waters (1979) developed a
program that automatically analyzes traditional Fortran programs, viewing them
in terms of maps, filters, and accumulations. He found that fully 90 percent
of the code in the Fortran Scientific Subroutine Package fits neatly into this
paradigm. One of the reasons for the success of Lisp as a programming language
is that lists provide a standard medium for expressing ordered collections so
that they can be manipulated using higher-order operations. The programming
language APL owes much of its power and appeal to a similar choice. In APL all
data are represented as arrays, and there is a universal and convenient set of
generic operators for all sorts of array operations.
Sequences, implemented here as lists, serve as a conventional interface that
permits us to combine processing modules. Additionally, when we uniformly
represent structures as sequences, we have localized the data-structure
dependencies in our programs to a small number of sequence operations. By
changing these, we can experiment with alternative representations of
sequences, while leaving the overall design of our programs intact. We will
exploit this capability in section 3-5, when we generalize the
sequence-processing paradigm to admit infinite sequences.
Exercise 2.33: Fill in the missing expressions
to complete the following definitions of some basic list-manipulation
operations as accumulations:
Exercise 2.34: Evaluating a polynomial in x
at a given value of x can be formulated as an accumulation. We evaluate
the polynomial
a_n r^n | a_(n-1) r^(n-1) + ... + a_1 r + a_0
using a well-known algorithm called Horner's rule
, which structures
the computation as
(... (a_n r + a_(n-1)) r + ... + a_1) r + a_0
In other words, we start with a_n, multiply by x, add
a_(n-1), multiply by x, and so on, until we reach
a_0.
According to Knuth (1981), this rule was formulated by
W. G. Horner early in the nineteenth century, but the method was actually used
by Newton over a hundred years earlier. Horner's rule evaluates the polynomial
using fewer additions and multiplications than does the straightforward method
of first computing a_n x^n, then adding
a_(n-1)x^(n-1), and so on. In fact, it is possible to prove
that any algorithm for evaluating arbitrary polynomials must use at least as
many additions and multiplications as does Horner's rule, and thus Horner's
rule is an optimal algorithm for polynomial evaluation. This was proved (for
the number of additions) by A. M. Ostrowski in a 1954 paper that essentially
founded the modern study of optimal algorithms. The analogous statement for
multiplications was proved by V. Y. Pan in 1966. The book by Borodin and Munro
(1975) provides an overview of these and other results about optimal
algorithms.
Fill in the following template to produce a procedure that evaluates a
polynomial using Horner's rule. Assume that the coefficients of the polynomial
are arranged in a sequence, from a_0 through a_n.
Exercise 2.36: The procedure accumulate-n
is similar to accumulate except that it takes as its third argument a
sequence of sequences, which are all assumed to have the same number of
elements. It applies the designated accumulation procedure to combine all the
first elements of the sequences, all the second elements of the sequences, and
so on, and returns a sequence of the results. For instance, if s is a
sequence containing four sequences, ((1 2 3) (4 5 6) (7 8 9) (10 11
12)), then the value of (accumulate-n + 0 s) should be the sequence
(22 26 30) . Fill in the missing expressions in the following definition
of accumulate-n :
(define (accumulate-n op init seqs)
(if (null? (car seqs))
nil
(cons (accumulate op init ?>)
(accumulate-n op init ?>))))
Exercise 2.37
Suppose we represent vectors v = (v_i) as sequences of numbers, and
matrices m = (m_(ij)) as sequences of vectors (the rows of the
matrix). For example, the matrix
+- -+
| 1 2 3 4 |
| 4 5 6 6 |
| 6 7 8 9 |
+- -+
is represented as the sequence ((1 2 3 4) (4 5 6 6) (6 7 8 9)) . With
this representation, we can use sequence operations to concisely express the
basic matrix and vector operations. These operations (which are described in
any book on matrix algebra) are the following:
__
(dot-product v w) returns the sum >_i v_i w_i
(matrix-*-vector m v) returns the vector t,
__
where t_i = >_j m_(ij) v_j
(matrix-*-matrix m n) returns the matrix p,
__
where p_(ij) = >_k m_(ik) n_(kj)
(transpose m) returns the matrix n,
where n_(ij) = m_(ji)
We can define the dot product as
This definition uses the extended
version of map described in Footnote 12.
(define (dot-product v w)
(accumulate + 0 (map * v w)))
Fill in the missing expressions in the following procedures for computing the
other matrix operations. (The procedure accumulate-n is defined in
Exercise 2-36.)
Exercise 2.38: The accumulate procedure
is also known as fold-right , because it combines the first element of
the sequence with the result of combining all the elements to the right. There
is also a fold-left , which is similar to fold-right , except that
it combines elements working in the opposite direction:
(define (fold-left op initial sequence)
(define (iter result rest)
(if (null? rest)
result
(iter (op result (car rest))
(cdr rest))))
(iter initial sequence))
We can extend the sequence paradigm to include many computations that are
commonly expressed using nested loops.
This approach to nested
mappings was shown to us by David Turner, whose languages KRC and Miranda
provide elegant formalisms for dealing with these constructs. The examples in
this section (see also Exercise 2-42) are adapted from Turner 1981. In
section 3-5-3, we'll see how this approach generalizes to infinite
sequences.
Consider this problem: Given a positive integer n, find all
ordered pairs of distinct positive integers i and j, where 1 <= j<
i<= n, such that i + j is prime. For example, if n is 6,
then the pairs are the following:
A natural way to organize this computation is to generate the sequence of all
ordered pairs of positive integers less than or equal to n, filter to
select those pairs whose sum is prime, and then, for each pair (i, j)
that passes through the filter, produce the triple (i,j,i + j).
Here is a way to generate the sequence of pairs: For each integer i <=
n, enumerate the integers j (enumerate-interval 1 n) . For each i in this sequence,
we map along the sequence (enumerate-interval 1 (- i 1)) . For each
j in this latter sequence, we generate the pair (list i j) . This
gives us a sequence of pairs for each i. Combining all the sequences for
all the i (by accumulating with append ) produces the required
sequence of pairs:
We're representing a pair here as a list of two
elements rather than as a Lisp pair. Thus, the ``pair'' (i,j) is
represented as (list i j) , not (cons i j) .
(accumulate append
nil
(map (lambda (i)
(map (lambda (j) (list i j))
(enumerate-interval 1 (- i 1))))
(enumerate-interval 1 n)))
The combination of mapping and accumulating with append is so common in
this sort of program that we will isolate it as a separate procedure:
Now filter this sequence of pairs to find those whose sum is prime. The filter
predicate is called for each element of the sequence; its argument is a pair
and it must extract the integers from the pair. Thus, the predicate to apply
to each element in the sequence is
Finally, generate the sequence of results by mapping over the filtered pairs
using the following procedure, which constructs a triple consisting of the two
elements of the pair along with their sum:
Nested mappings are also useful for sequences other than those that enumerate
intervals. Suppose we wish to generate all the permutations of a set S;
that is, all the ways of ordering the items in the set. For instance, the
permutations of @{1,2,3@} are @{1,2,3@}, @{1,3,2@}, @{2,1,3@}, @{2,3,1@},
@{3,1,2@}, and @{3,2,1@}. Here is a plan for generating the permutations of
S: For each item x in S, recursively generate the sequence of
permutations of S - x,
The set S - x is the set of all
elements of S, excluding x.
and adjoin x to the front of each one.
This yields, for each x in S, the sequence of permutations of S
that begin with x. Combining these sequences for all x gives all the
permutations of S:
Semicolons in Scheme code are used to introduce
comments
. Everything from the semicolon to the end of the line is
ignored by the interpreter. In this book we don't use many comments; we try to
make our programs self-documenting by using descriptive names.
(define (permutations s)
(if (null? s) ; empty set?
(list nil) ; sequence containing empty set
(flatmap (lambda (x)
(map (lambda (p) (cons x p))
(permutations (remove x s))))
s)))
Notice how this strategy reduces the problem of generating permutations of
S to the problem of generating the permutations of sets with fewer elements
than S. In the terminal case, we work our way down to the empty list,
which represents a set of no elements. For this, we generate (list
nil) , which is a sequence with one item, namely the set with no elements. The
remove procedure used in permutations returns all the items in a
given sequence except for a given item. This can be expressed as a simple
filter:
Exercise 2.40: Define a procedure
unique-pairs that, given an integer n, generates the sequence of
pairs (i,j) with 1 <= j< i <= n. Use unique-pairs
to simplify the definition of prime-sum-pairs given above.
Exercise 2.41: Write a procedure to find all
ordered triples of distinct positive integers i, j, and k less than
or equal to a given integer n that sum to a given integer s.
Figure 2.8: A solution to the eight-queens puzzle.
Exercise 2.42: The ``eight-queens puzzle'' asks
how to place eight queens on a chessboard so that no queen is in check from any
other (i.e., no two queens are in the same row, column, or diagonal). One
possible solution is shown in Figure 2-8. One way to solve the puzzle is
to work across the board, placing a queen in each column. Once we have placed
k - 1 queens, we must place the kth queen in a position where it does
not check any of the queens already on the board. We can formulate this
approach recursively: Assume that we have already generated the sequence of all
possible ways to place k - 1 queens in the first k - 1 columns of the
board. For each of these ways, generate an extended set of positions by
placing a queen in each row of the kth column. Now filter these, keeping
only the positions for which the queen in the kth column is safe with
respect to the other queens. This produces the sequence of all ways to place
k queens in the first k columns. By continuing this process, we will
produce not only one solution, but all solutions to the puzzle.
We implement this solution as a procedure queens , which returns a
sequence of all solutions to the problem of placing n queens on an
n*n chessboard. Queens has an internal procedure
queen-cols that returns the sequence of all ways to place queens in the
first k columns of the board.
(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list empty-board)
(filter
(lambda (positions) (safe? k positions))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(adjoin-position new-row k rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(queen-cols board-size))
In this procedure rest-of-queens is a way to place k - 1 queens in
the first k - 1 columns, and new-row is a proposed row in which to
place the queen for the kth column. Complete the program by implementing
the representation for sets of board positions, including the procedure
adjoin-position , which adjoins a new row-column position to a set of
positions, and empty-board , which represents an empty set of positions.
You must also write the procedure safe? , which determines for a set of
positions, whether the queen in the kth column is safe with respect to the
others. (Note that we need only check whether the new queen is safe---the
other queens are already guaranteed safe with respect to each other.)
Exercise 2.43: Louis Reasoner is having a
terrible time doing Exercise 2-42. His queens procedure seems to
work, but it runs extremely slowly. (Louis never does manage to wait long
enough for it to solve even the 6*6 case.) When Louis asks Eva Lu Ator for
help, she points out that he has interchanged the order of the nested mappings
in the flatmap , writing it as
(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
(adjoin-position new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long
it will take Louis's program to solve the eight-queens puzzle, assuming that
the program in Exercise 2-42 solves the puzzle in time T.
Example: A Picture Language
This section presents a simple language for drawing pictures that illustrates
the power of data abstraction and closure, and also exploits higher-order
procedures in an essential way. The language is designed to make it easy to
experiment with patterns such as the ones in Figure 2-9, which are
composed of repeated elements that are shifted and scaled.
The picture
language is based on the language Peter Henderson created to construct images
like M.C. Escher's ``Square Limit'' woodcut (see Henderson 1982). The woodcut
incorporates a repeated scaled pattern, similar to the arrangements drawn using
the square-limit procedure in this section.
In this language, the data
objects being combined are represented as procedures rather than as list
structure. Just as cons , which satisfies the closure property, allowed
us to easily build arbitrarily complicated list structure, the operations in
this language, which also satisfy the closure property, allow us to easily
build arbitrarily complicated patterns.
Figure 2.9: Designs generated with the picture
language.
[two graphic images not included]
The picture language
When we began our study of programming in section 1-1, we emphasized the
importance of describing a language by focusing on the language's primitives,
its means of combination, and its means of abstraction. We'll follow that
framework here.
Part of the elegance of this picture language is that there is only one kind of
element, called a painter
. A painter draws an image that is shifted
and scaled to fit within a designated parallelogram-shaped frame. For example,
there's a primitive painter we'll call wave that makes a crude line
drawing, as shown in Figure 2-10. The actual shape of the drawing
depends on the frame---all four images in Figure 2-10 are produced by the
same wave painter, but with respect to four different frames. Painters
can be more elaborate than this: The primitive painter called rogers
paints a picture of @acronym{MIT}'s founder, William Barton Rogers, as shown in
Figure 2-11.
William Barton Rogers (1804-1882) was the founder
and first president of @acronym{MIT
. A geologist and talented teacher, he
taught at William and Mary College and at the University of Virginia. In 1859
he moved to Boston, where he had more time for research, worked on a plan for
establishing a ``polytechnic institute,'' and served as Massachusetts's first
State Inspector of Gas Meters.
When @acronym{MIT} was established in 1861, Rogers was elected its first
president. Rogers espoused an ideal of ``useful learning'' that was different
from the university education of the time, with its overemphasis on the
classics, which, as he wrote, ``stand in the way of the broader, higher and
more practical instruction and discipline of the natural and social sciences.''
This education was likewise to be different from narrow trade-school education.
In Rogers's words:
The world-enforced distinction between the practical and the scientific worker
is utterly futile, and the whole experience of modern times has demonstrated
its utter worthlessness.
Rogers served as president of @acronym{MIT} until 1870, when he resigned due to
ill health. In 1878 the second president of @acronym{MIT}, John Runkle,
resigned under the pressure of a financial crisis brought on by the Panic of
1873 and strain of fighting off attempts by Harvard to take over @acronym{MIT}.
Rogers returned to hold the office of president until 1881.
Rogers collapsed and died while addressing @acronym{MIT}'s graduating class at
the commencement exercises of 1882. Runkle quoted Rogers's last words in a
memorial address delivered that same year:
``As I stand here today and see what the Institute is, ... I call to mind
the beginnings of science. I remember one hundred and fifty years ago Stephen
Hales published a pamphlet on the subject of illuminating gas, in which he
stated that his researches had demonstrated that 128 grains of bituminous coal
-- '' ``Bituminous coal,'' these were his last words on earth. Here he bent
forward, as if consulting some notes on the table before him, then slowly
regaining an erect position, threw up his hands, and was translated from the
scene of his earthly labors and triumphs to ``the tomorrow of death,'' where
the mysteries of life are solved, and the disembodied spirit finds unending
satisfaction in contemplating the new and still unfathomable mysteries of the
infinite future.
In the words of Francis A. Walker (@acronym{MIT}'s third president):
All his life he had borne himself most faithfully and heroically, and he died
as so good a knight would surely have wished, in harness, at his post, and in
the very part and act of public duty.
} The four images in Figure 2-11 are drawn with respect to the same four
frames as the wave images in Figure 2-10.
To combine images, we use various operations that construct new painters from
given painters. For example, the beside operation takes two painters
and produces a new, compound painter that draws the first painter's image in
the left half of the frame and the second painter's image in the right half of
the frame. Similarly, below takes two painters and produces a compound
painter that draws the first painter's image below the second painter's image.
Some operations transform a single painter to produce a new painter. For
example, flip-vert takes a painter and produces a painter that draws its
image upside-down, and flip-horiz produces a painter that draws the
original painter's image left-to-right reversed.
Figure 2.10: Images produced by the wave
painter, with respect to four different frames. The frames, shown with dotted
lines, are not part of the images.
[four graphic images not included]
Figure 2.11: Images of William Barton Rogers,
founder and first president of @acronym{MIT}, painted with respect to the same
four frames as in Figure 2-10 (original image reprinted with the
permission of the @acronym{MIT} Museum).
[four graphic images not included]
Figure 2-12 shows the drawing of a painter called
wave4 that is built up in two stages starting from wave :
In building up a complex image in this manner we are exploiting the fact that
painters are closed under the language's means of combination. The
beside or below of two painters is itself a painter; therefore,
we can use it as an element in making more complex painters. As with building
up list structure using cons , the closure of our data under the means of
combination is crucial to the ability to create complex structures while using
only a few operations.
Once we can combine painters, we would like to be able to abstract typical
patterns of combining painters. We will implement the painter operations as
Scheme procedures. This means that we don't need a special abstraction
mechanism in the picture language: Since the means of combination are ordinary
Scheme procedures, we automatically have the capability to do anything with
painter operations that we can do with procedures. For example, we can
abstract the pattern in wave4 as
We can also define recursive operations. Here's one that makes painters split
and branch towards the right as shown in figures Figure 2-13
and Figure 2-14:
We can produce balanced patterns by branching upwards as well as towards the
right (see Exercise 2-44 and figures Figure 2-13 and Figure
2-14):
(define (corner-split painter n)
(if (= n 0)
painter
(let ((up (up-split painter (- n 1)))
(right (right-split painter (- n 1))))
(let ((top-left (beside up up))
(bottom-right (below right right))
(corner (corner-split painter (- n 1))))
(beside (below painter top-left)
(below bottom-right corner))))))
Figure 2.14: The recursive operations
right-split and corner-split applied to the painters wave
and rogers . Combining four corner-split figures produces
symmetric square-limit designs as shown in Figure 2-9.
[two graphic images not included]
(right-split wave 4) (right-split rogers 4)
[two graphic images not included]
(corner-split wave 4) (corner-split rogers 4)
By placing four copies of a corner-split appropriately, we obtain a
pattern called square-limit , whose application to wave and
rogers is shown in Figure 2-9:
Exercise 2.44: Define the procedure
up-split used by corner-split . It is similar to
right-split , except that it switches the roles of below and
beside .
Higher-order operations
In addition to abstracting patterns of combining painters, we can work at a
higher level, abstracting patterns of combining painter operations. That is,
we can view the painter operations as elements to manipulate and can write
means of combination for these elements---procedures that take painter
operations as arguments and create new painter operations.
For example, flipped-pairs and square-limit each arrange four
copies of a painter's image in a square pattern; they differ only in how they
orient the copies. One way to abstract this pattern of painter combination is
with the following procedure, which takes four one-argument painter operations
and produces a painter operation that transforms a given painter with those
four operations and arranges the results in a square. Tl , tr ,
bl , and br are the transformations to apply to the top left copy,
the top right copy, the bottom left copy, and the bottom right copy,
respectively.
Rotate180 rotates a
painter by 180 degrees (see Exercise 2-50). Instead of rotate180
we could say (compose flip-vert flip-horiz) , using the compose
procedure from Exercise 1-42.
Exercise 2.45: Right-split and
up-split can be expressed as instances of a general splitting operation.
Define a procedure split with the property that evaluating
produces procedures right-split and up-split with the same
behaviors as the ones already defined.
Frames
Before we can show how to implement painters and their means of combination, we
must first consider frames. A frame can be described by three vectors---an
origin vector and two edge vectors. The origin vector specifies the offset of
the frame's origin from some absolute origin in the plane, and the edge vectors
specify the offsets of the frame's corners from its origin. If the edges are
perpendicular, the frame will be rectangular. Otherwise the frame will be a
more general parallelogram.
Figure 2-15 shows a frame and its associated vectors.
In accordance with data abstraction, we need not be specific yet about how
frames are represented, other than to say that there is a constructor
make-frame , which takes three vectors and produces a frame, and three
corresponding selectors origin-frame , edge1-frame , and
edge2-frame (see Exercise 2-47).
Figure 2.15: A frame is described by three vectors
-- an origin and two edges.
We will use coordinates in the unit square (0<= x,y<= 1) to specify
images. With each frame, we associate a frame coordinate map
, which
will be used to shift and scale images to fit the frame. The map transforms
the unit square into the frame by mapping the vector v = (x,y) to
the vector sum
Origin(Frame) + r * Edge_1(Frame) + y * Edge_2(Frame)
For example, (0,0) is mapped to the origin of the frame, (1,1) to the vertex
diagonally opposite the origin, and (0.5,0.5) to the center of the frame. We
can create a frame's coordinate map with the following
procedure:
Frame-coord-map uses the vector operations described
in Exercise 2-46 below, which we assume have been implemented using some
representation for vectors. Because of data abstraction, it doesn't matter
what this vector representation is, so long as the vector operations behave
correctly.
Observe that applying frame-coord-map to a frame returns a procedure
that, given a vector, returns a vector. If the argument vector is in the unit
square, the result vector will be in the frame. For example,
((frame-coord-map a-frame) (make-vect 0 0))
returns the same vector as
(origin-frame a-frame)
Exercise 2.46: A two-dimensional vector v
running from the origin to a point can be represented as a pair consisting of
an x-coordinate and a y-coordinate. Implement a data abstraction for
vectors by giving a constructor make-vect and corresponding selectors
xcor-vect and ycor-vect . In terms of your selectors and
constructor, implement procedures add-vect , sub-vect , and
scale-vect that perform the operations vector addition, vector
subtraction, and multiplying a vector by a scalar:
For each constructor supply the appropriate selectors to produce an
implementation for frames.
Painters
A painter is represented as a procedure that, given a frame as argument, draws
a particular image shifted and scaled to fit the frame. That is to say, if
p is a painter and f is a frame, then we produce p 's image
in f by calling p with f as argument.
The details of how primitive painters are implemented depend on the particular
characteristics of the graphics system and the type of image to be drawn. For
instance, suppose we have a procedure draw-line that draws a line on the
screen between two specified points. Then we can create painters for line
drawings, such as the wave painter in Figure 2-10, from lists of
line segments as follows:
Segments->painter uses the
representation for line segments described in Exercise 2-48 below. It
also uses the for-each procedure described in Exercise 2-23.
The segments are given using coordinates with respect to the unit square. For
each segment in the list, the painter transforms the segment endpoints with the
frame coordinate map and draws a line between the transformed points.
Representing painters as procedures erects a powerful abstraction barrier in
the picture language. We can create and intermix all sorts of primitive
painters, based on a variety of graphics capabilities. The details of their
implementation do not matter. Any procedure can serve as a painter, provided
that it takes a frame as argument and draws something scaled to fit the
frame.
For example, the rogers painter of Figure 2-11 was
constructed from a gray-level image. For each point in a given frame, the
rogers painter determines the point in the image that is mapped to it
under the frame coordinate map, and shades it accordingly. By allowing
different types of painters, we are capitalizing on the abstract data idea
discussed in section 2-1-3, where we argued that a rational-number
representation could be anything at all that satisfies an appropriate
condition. Here we're using the fact that a painter can be implemented in any
way at all, so long as it draws something in the designated frame. Section
2-1-3 also showed how pairs could be implemented as procedures. Painters
are our second example of a procedural representation for data.
Exercise 2.48: A directed line segment in the
plane can be represented as a pair of vectors---the vector running from the
origin to the start-point of the segment, and the vector running from the
origin to the end-point of the segment. Use your vector representation from
Exercise 2-46 to define a representation for segments with a constructor
make-segment and selectors start-segment and end-segment .
Exercise 2.49: Use segments->painter
to define the following primitive painters:
The painter that draws the outline of the designated frame.
The painter that draws an ``X'' by connecting opposite corners of the frame.
The painter that draws a diamond shape by connecting the midpoints of the sides
of the frame.
The wave painter.
Transforming and combining painters
An operation on painters (such as flip-vert or beside ) works by
creating a painter that invokes the original painters with respect to frames
derived from the argument frame. Thus, for example, flip-vert doesn't
have to know how a painter works in order to flip it---it just has to know how
to turn a frame upside down: The flipped painter just uses the original
painter, but in the inverted frame.
Painter operations are based on the procedure transform-painter , which
takes as arguments a painter and information on how to transform a frame and
produces a new painter. The transformed painter, when called on a frame,
transforms the frame and calls the original painter on the transformed frame.
The arguments to transform-painter are points (represented as vectors)
that specify the corners of the new frame: When mapped into the frame, the
first point specifies the new frame's origin and the other two specify the ends
of its edge vectors. Thus, arguments within the unit square specify a frame
contained within the original frame.
(define (flip-vert painter)
(transform-painter painter
(make-vect 0.0 1.0) ; new origin
(make-vect 1.0 1.0) ; new end of edge1
(make-vect 0.0 0.0))) ; new end of edge2
Using transform-painter , we can easily define new transformations.
For example, we can define a painter that shrinks its image to the
upper-right quarter of the frame it is given:
Frame transformation is also the key to defining means of combining two or more
painters. The beside procedure, for example, takes two painters,
transforms them to paint in the left and right halves of an argument frame
respectively, and produces a new, compound painter. When the compound painter
is given a frame, it calls the first transformed painter to paint in the left
half of the frame and calls the second transformed painter to paint in the
right half of the frame:
Observe how the painter data abstraction, and in particular the representation
of painters as procedures, makes beside easy to implement. The
beside procedure need not know anything about the details of the
component painters other than that each painter will draw something in its
designated frame.
Exercise 2.50: Define the transformation
flip-horiz , which flips painters horizontally, and transformations that
rotate painters counterclockwise by 180 degrees and 270 degrees.
Exercise 2.51: Define the below operation
for painters. Below takes two painters as arguments. The resulting
painter, given a frame, draws with the first painter in the bottom of the frame
and with the second painter in the top. Define below in two different
ways---first by writing a procedure that is analogous to the beside
procedure given above, and again in terms of beside and suitable
rotation operations (from Exercise 2-50).
Levels of language for robust design
The picture language exercises some of the critical ideas we've introduced
about abstraction with procedures and data. The fundamental data abstractions,
painters, are implemented using procedural representations, which enables the
language to handle different basic drawing capabilities in a uniform way. The
means of combination satisfy the closure property, which permits us to easily
build up complex designs. Finally, all the tools for abstracting procedures
are available to us for abstracting means of combination for painters.
We have also obtained a glimpse of another crucial idea about languages and
program design. This is the approach of stratified design
, the
notion that a complex system should be structured as a sequence of levels that
are described using a sequence of languages. Each level is constructed by
combining parts that are regarded as primitive at that level, and the parts
constructed at each level are used as primitives at the next level. The
language used at each level of a stratified design has primitives, means of
combination, and means of abstraction appropriate to that level of detail.
Stratified design pervades the engineering of complex systems. For example, in
computer engineering, resistors and transistors are combined (and described
using a language of analog circuits) to produce parts such as and-gates and
or-gates, which form the primitives of a language for digital-circuit
design.
Section 3-3-4 describes one such language.
These parts
are combined to build processors, bus structures, and memory systems, which are
in turn combined to form computers, using languages appropriate to computer
architecture. Computers are combined to form distributed systems, using
languages appropriate for describing network interconnections, and so on.
As a tiny example of stratification, our picture language uses primitive
elements (primitive painters) that are created using a language that specifies
points and lines to provide the lists of line segments for
segments->painter , or the shading details for a painter like
rogers . The bulk of our description of the picture language focused on
combining these primitives, using geometric combiners such as beside and
below . We also worked at a higher level, regarding beside and
below as primitives to be manipulated in a language whose operations,
such as square-of-four , capture common patterns of combining geometric
combiners.
Stratified design helps make programs robust
, that is, it makes it
likely that small changes in a specification will require correspondingly small
changes in the program. For instance, suppose we wanted to change the image
based on wave shown in Figure 2-9. We could work at the lowest
level to change the detailed appearance of the wave element; we could
work at the middle level to change the way corner-split replicates the
wave ; we could work at the highest level to change how
square-limit arranges the four copies of the corner. In general, each
level of a stratified design provides a different vocabulary for expressing the
characteristics of the system, and a different kind of ability to change it.
Exercise 2.52: Make changes to the square limit
of wave shown in Figure 2-9 by working at each of the levels
described above. In particular:
Add some segments to the primitive wave painter of Exercise 2-49
(to add a smile, for example).
Change the pattern constructed by corner-split (for example, by using
only one copy of the up-split and right-split images instead of
two).
Modify the version of square-limit that uses square-of-four so as
to assemble the corners in a different pattern. (For example, you might make
the big Mr. Rogers look outward from each corner of the square.)
Symbolic Data
All the compound data objects we have used so far were constructed ultimately
from numbers. In this section we extend the representational capability of our
language by introducing the ability to work with arbitrary symbols as data.
@menu
* 2-3-1:: Quotation
* 2-3-2:: Example: Symbolic Differentiation
* 2-3-3:: Example: Representing Sets
* 2-3-4:: Example: Huffman Encoding Trees
@end menu
Quotation
If we can form compound data using symbols, we can have lists such as
(a b c d)
(23 45 17)
((Norah 12) (Molly 9) (Anna 7) (Lauren 6) (Charlotte 4))
Lists containing symbols can look just like the expressions of our
language:
(* (+ 23 45) (+ x 9))
(define (fact n) (if (= n 1) 1 (* n (fact (- n 1)))))
In order to manipulate symbols we need a new element in our language: the
ability to quote
a data object. Suppose we want to construct the
list (a b) . We can't accomplish this with (list a b) , because
this expression constructs a list of the values
of a and
b rather than the symbols themselves. This issue is well known in the
context of natural languages, where words and sentences may be regarded either
as semantic entities or as character strings (syntactic entities). The common
practice in natural languages is to use quotation marks to indicate that a word
or a sentence is to be treated literally as a string of characters. For
instance, the first letter of ``John'' is clearly ``J.'' If we tell somebody
``say your name aloud,'' we expect to hear that person's name. However, if we
tell somebody ``say `your name' aloud,'' we expect to hear the words ``your
name.'' Note that we are forced to nest quotation marks to describe what
somebody else might say.
Allowing quotation in a language wreaks havoc
with the ability to reason about the language in simple terms, because it
destroys the notion that equals can be substituted for equals. For example,
three is one plus two, but the word ``three'' is not the phrase ``one plus
two.'' Quotation is powerful because it gives us a way to build expressions
that manipulate other expressions (as we will see when we write an interpreter
in Chapter 4). But allowing statements in a language that talk about
other statements in that language makes it very difficult to maintain any
coherent principle of what ``equals can be substituted for equals'' should
mean. For example, if we know that the evening star is the morning star, then
from the statement ``the evening star is Venus'' we can deduce ``the morning
star is Venus.'' However, given that ``John knows that the evening star is
Venus'' we cannot infer that ``John knows that the morning star is Venus.''
We can follow this same practice to identify lists and symbols that are to be
treated as data objects rather than as expressions to be evaluated. However,
our format for quoting differs from that of natural languages in that we place
a quotation mark (traditionally, the single quote symbol ' ) only at the
beginning of the object to be quoted. We can get away with this in Scheme
syntax because we rely on blanks and parentheses to delimit objects. Thus, the
meaning of the single quote character is to quote the next object.
The
single quote is different from the double quote we have been using to enclose
character strings to be printed. Whereas the single quote can be used to
denote lists or symbols, the double quote is used only with character strings.
In this book, the only use for character strings is as items to be printed.
Now we can distinguish between symbols and their values:
(define a 1)
(define b 2)
(list a b)
(1 2)
(list 'a 'b)
(a b)
(list 'a b)
(a 2)
Quotation also allows us to type in compound objects, using the conventional
printed representation for lists:
Strictly, our use of the quotation
mark violates the general rule that all compound expressions in our language
should be delimited by parentheses and look like lists. We can recover this
consistency by introducing a special form quote , which serves the same
purpose as the quotation mark. Thus, we would type (quote a) instead of
'a , and we would type (quote (a b c)) instead of '(a b c) .
This is precisely how the interpreter works. The quotation mark is just a
single-character abbreviation for wrapping the next complete expression with
quote to form (quote >). This is
important because it maintains the principle that any expression seen by the
interpreter can be manipulated as a data object. For instance, we could
construct the expression (car '(a b c)) , which is the same as (car
(quote (a b c))) , by evaluating (list 'car (list 'quote '(a b c))) .
(car '(a b c))
a
(cdr '(a b c))
(b c)
In keeping with this, we can obtain the empty list by evaluating '() ,
and thus dispense with the variable nil .
One additional primitive used in manipulating symbols is eq? , which
takes two symbols as arguments and tests whether they are the same.
We
can consider two symbols to be ``the same'' if they consist of the same
characters in the same order. Such a definition skirts a deep issue that we
are not yet ready to address: the meaning of ``sameness'' in a programming
language. We will return to this in Chapter 3 (section 3-1-3).
Using eq? , we can implement a useful procedure called memq . This
takes two arguments, a symbol and a list. If the symbol is not contained in
the list (i.e., is not eq? to any item in the list), then memq
returns false. Otherwise, it returns the sublist of the list beginning with
the first occurrence of the symbol:
Exercise 2.54: Two lists are said to be
equal? if they contain equal elements arranged in the same order. For
example,
(equal? '(this is a list) '(this is a list))
is true, but
(equal? '(this is a list) '(this (is a) list))
is false. To be more precise, we can define equal? recursively in
terms of the basic eq? equality of symbols by saying that a and
b are equal? if they are both symbols and the symbols are
eq? , or if they are both lists such that (car a) is equal?
to (car b) and (cdr a) is equal? to (cdr b) . Using
this idea, implement equal? as a procedure.
In practice,
programmers use equal? to compare lists that contain numbers as well as
symbols. Numbers are not considered to be symbols. The question of whether
two numerically equal numbers (as tested by = ) are also eq? is
highly implementation-dependent. A better definition of equal? (such as
the one that comes as a primitive in Scheme) would also stipulate that if
a and b are both numbers, then a and b are
equal? if they are numerically equal.
Exercise 2.55: Eva Lu Ator types to the
interpreter the expression
(car ''abracadabra)
To her surprise, the interpreter prints back quote . Explain.
Example: Symbolic Differentiation
As an illustration of symbol manipulation and a further illustration of data
abstraction, consider the design of a procedure that performs symbolic
differentiation of algebraic expressions. We would like the procedure to take
as arguments an algebraic expression and a variable and to return the
derivative of the expression with respect to the variable. For example, if the
arguments to the procedure are ax^2 + bx + c and x, the
procedure should return 2ax + b. Symbolic differentiation is of
special historical significance in Lisp. It was one of the motivating examples
behind the development of a computer language for symbol manipulation.
Furthermore, it marked the beginning of the line of research that led to the
development of powerful systems for symbolic mathematical work, which are
currently being used by a growing number of applied mathematicians and
physicists.
In developing the symbolic-differentiation program, we will follow the same
strategy of data abstraction that we followed in developing the rational-number
system of section 2-1-1. That is, we will first define a differentiation
algorithm that operates on abstract objects such as ``sums,'' ``products,'' and
``variables'' without worrying about how these are to be represented. Only
afterward will we address the representation problem.
The differentiation program with abstract data
In order to keep things simple, we will consider a very simple
symbolic-differentiation program that handles expressions that are built up
using only the operations of addition and multiplication with two arguments.
Differentiation of any such expression can be carried out by applying the
following reduction rules:
dc
-- = 0 for c a constant, or a variable different from x
dx
dx
-- = 1
dx
d(u + v) du dv
-------- = -- + --
dx dx dx
d(uv) / dv \ / du \
----- = u | -- | + v | -- |
dx \ dx / \ dx /
Observe that the latter two rules are recursive in nature. That is, to obtain
the derivative of a sum we first find the derivatives of the terms and add
them. Each of the terms may in turn be an expression that needs to be
decomposed. Decomposing into smaller and smaller pieces will eventually
produce pieces that are either constants or variables, whose derivatives will
be either 0 or 1.
To embody these rules in a procedure we indulge in a little wishful thinking,
as we did in designing the rational-number implementation. If we had a means
for representing algebraic expressions, we should be able to tell whether an
expression is a sum, a product, a constant, or a variable. We should be able
to extract the parts of an expression. For a sum, for example we want to be
able to extract the addend (first term) and the augend (second term). We
should also be able to construct expressions from parts. Let us assume that we
already have procedures to implement the following selectors, constructors, and
predicates:
(variable? e) Is e a variable?
(same-variable? v1 v2) Are v1 and v2 the same variable?
(sum? e) Is e a sum?
(addend e) Addend of the sum e .
(augend e) Augend of the sum e .
(make-sum a1 a2) Construct the sum of a1 and a2 .
(product? e) Is e a product?
(multiplier e) Multiplier of the product e .
(multiplicand e) Multiplicand of the product e .
(make-product m1 m2) Construct the product of m1 and m2 .
Using these, and the primitive predicate number? , which identifies
numbers, we can express the differentiation rules as the following procedure:
This deriv procedure incorporates the complete differentiation
algorithm. Since it is expressed in terms of abstract data, it will work no
matter how we choose to represent algebraic expressions, as long as we design a
proper set of selectors and constructors. This is the issue we must address
next.
Representing algebraic expressions
We can imagine many ways to use list structure to represent algebraic
expressions. For example, we could use lists of symbols that mirror the usual
algebraic notation, representing ax + b as the list (a * x +
b) . However, one especially straightforward choice is to use the same
parenthesized prefix notation that Lisp uses for combinations; that is, to
represent ax + b as (+ (* a x) b) . Then our data
representation for the differentiation problem is as follows:
The variables are symbols. They are identified by the primitive predicate
symbol? :
(define (variable? x) (symbol? x))
Two variables are the same if the symbols representing them are eq? :
The multiplier is the second item of the product list:
(define (multiplier p) (cadr p))
The multiplicand is the third item of the product list:
(define (multiplicand p) (caddr p))
Thus, we need only combine these with the algorithm as embodied by deriv
in order to have a working symbolic-differentiation program. Let us look at
some examples of its behavior:
(deriv '(+ x 3) 'x)
(+ 1 0)
(deriv '(* x y) 'x)
(+ (* x 0) (* 1 y))
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* (* x y) (+ 1 0))
(* (+ (* x 0) (* 1 y))
(+ x 3)))
The program produces answers that are correct; however, they are unsimplified.
It is true that
d(xy)
----- = x * 0 + 1 * y
dx
but we would like the program to know that x * 0 = 0, 1 * y = y,
and 0 + y = y. The answer for the second example should have been
simply y . As the third example shows, this becomes a serious issue when
the expressions are complex.
Our difficulty is much like the one we encountered with the rational-number
implementation: we haven't reduced answers to simplest form. To accomplish the
rational-number reduction, we needed to change only the constructors and the
selectors of the implementation. We can adopt a similar strategy here. We
won't change deriv at all. Instead, we will change make-sum so
that if both summands are numbers, make-sum will add them and return
their sum. Also, if one of the summands is 0, then make-sum will return
the other summand.
Here is how this version works on our three examples:
(deriv '(+ x 3) 'x)
1
(deriv '(* x y) 'x)
y
(deriv '(* (* x y) (+ x 3)) 'x)
(+ (* x y) (* y (+ x 3)))
Although this is quite an improvement, the third example shows that there is
still a long way to go before we get a program that puts expressions into a
form that we might agree is ``simplest.'' The problem of algebraic
simplification is complex because, among other reasons, a form that may be
simplest for one purpose may not be for another.
Exercise 2.56: Show how to extend the basic
differentiator to handle more kinds of expressions. For instance, implement
the differentiation rule
n_1 n_2
--- = --- if and only if n_1 d_2 = n_2 d_1
d_1 d_2
by adding a new clause to the deriv program and defining appropriate
procedures exponentiation? , base , exponent , and
make-exponentiation . (You may use the symbol ** to denote
exponentiation.) Build in the rules that anything raised to the power 0 is 1
and anything raised to the power 1 is the thing itself.
Exercise 2.57: Extend the differentiation
program to handle sums and products of arbitrary numbers of (two or more)
terms. Then the last example above could be expressed as
(deriv '(* x y (+ x 3)) 'x)
Try to do this by changing only the representation for sums and products,
without changing the deriv procedure at all. For example, the
addend of a sum would be the first term, and the augend would be
the sum of the rest of the terms.
Exercise 2.58: Suppose we want to modify the
differentiation program so that it works with ordinary mathematical notation,
in which + and * are infix rather than prefix operators. Since
the differentiation program is defined in terms of abstract data, we can modify
it to work with different representations of expressions solely by changing the
predicates, selectors, and constructors that define the representation of the
algebraic expressions on which the differentiator is to operate.
Show how to do this in order to differentiate algebraic expressions presented
in infix form, such as (x + (3 * (x + (y + 2)))) . To simplify the task,
assume that + and * always take two arguments and that
expressions are fully parenthesized.
The problem becomes substantially harder if we allow standard algebraic
notation, such as (x + 3 * (x + y + 2)) , which drops unnecessary
parentheses and assumes that multiplication is done before addition. Can you
design appropriate predicates, selectors, and constructors for this notation
such that our derivative program still works?
Example: Representing Sets
In the previous examples we built representations for two kinds of compound
data objects: rational numbers and algebraic expressions. In one of these
examples we had the choice of simplifying (reducing) the expressions at either
construction time or selection time, but other than that the choice of a
representation for these structures in terms of lists was straightforward. When
we turn to the representation of sets, the choice of a representation is not so
obvious. Indeed, there are a number of possible representations, and they
differ significantly from one another in several ways.
Informally, a set is simply a collection of distinct objects. To give a more
precise definition we can employ the method of data abstraction. That is, we
define ``set'' by specifying the operations that are to be used on sets. These
are union-set , intersection-set , element-of-set? , and
adjoin-set . Element-of-set? is a predicate that determines
whether a given element is a member of a set. Adjoin-set takes an
object and a set as arguments and returns a set that contains the elements of
the original set and also the adjoined element. Union-set computes the
union of two sets, which is the set containing each element that appears in
either argument. Intersection-set computes the intersection of two
sets, which is the set containing only elements that appear in both arguments.
From the viewpoint of data abstraction, we are free to design any
representation that implements these operations in a way consistent with the
interpretations given above.
If we want to be more formal, we can
specify ``consistent with the interpretations given above'' to mean that the
operations satisfy a collection of rules such as these:
For any set S and any object x ,
(element-of-set? x (adjoin-set x S))
is true (informally: ``Adjoining an object to a
set produces a set that contains the object'').
For any sets S and T and any object x ,
(element-of-set? x (union-set S T))
is equal to
(or (element-of-set? x S) (element-of-set? x T))
(informally: ``The elements of (union S T) are the elements that
are in S or in T '').
For any object x ,
(element-of-set? x '())
is false (informally: ``No object is an element of the empty set'').
Sets as unordered lists
One way to represent a set is as a list of its elements in which no element
appears more than once. The empty set is represented by the empty list. In
this representation, element-of-set? is similar to the procedure
memq of section 2-3-1. It uses equal? instead of
eq? so that the set elements need not be symbols:
(define (element-of-set? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set? x (cdr set)))))
Using this, we can write adjoin-set . If the object to be adjoined is
already in the set, we just return the set. Otherwise, we use cons to
add the object to the list that represents the set:
(define (adjoin-set x set)
(if (element-of-set? x set)
set
(cons x set)))
For intersection-set we can use a recursive strategy. If we know how to
form the intersection of set2 and the cdr of set1 , we only
need to decide whether to include the car of set1 in this. But
this depends on whether (car set1) is also in set2 . Here is the
resulting procedure:
In designing a representation, one of the issues we should be concerned with is
efficiency. Consider the number of steps required by our set operations.
Since they all use element-of-set? , the speed of this operation has a
major impact on the efficiency of the set implementation as a whole. Now, in
order to check whether an object is a member of a set, element-of-set?
may have to scan the entire set. (In the worst case, the object turns out not
to be in the set.) Hence, if the set has n elements,
element-of-set? might take up to n steps. Thus, the number of
steps required grows as [theta](n). The number of steps required by
adjoin-set , which uses this operation, also grows as [theta](n).
For intersection-set , which does an element-of-set? check for
each element of set1 , the number of steps required grows as the product
of the sizes of the sets involved, or [theta](n^2) for two sets of size
n. The same will be true of union-set .
Exercise 2.59: Implement the union-set
operation for the unordered-list representation of sets.
Exercise 2.60: We specified that a set would be
represented as a list with no duplicates. Now suppose we allow duplicates.
For instance, the set @{1,2,3@} could be represented as the list (2 3 2 1
3 2 2) . Design procedures element-of-set? , adjoin-set ,
union-set , and intersection-set that operate on this
representation. How does the efficiency of each compare with the corresponding
procedure for the non-duplicate representation? Are there applications for
which you would use this representation in preference to the non-duplicate one?
Sets as ordered lists
One way to speed up our set operations is to change the representation so that
the set elements are listed in increasing order. To do this, we need some way
to compare two objects so that we can say which is bigger. For example, we
could compare symbols lexicographically, or we could agree on some method for
assigning a unique number to an object and then compare the elements by
comparing the corresponding numbers. To keep our discussion simple, we will
consider only the case where the set elements are numbers, so that we can
compare elements using > and < . We will represent a set of
numbers by listing its elements in increasing order. Whereas our first
representation above allowed us to represent the set @{1,3,6,10@} by listing
the elements in any order, our new representation allows only the list (1
3 6 10) .
One advantage of ordering shows up in element-of-set? : In checking for
the presence of an item, we no longer have to scan the entire set. If we reach
a set element that is larger than the item we are looking for, then we know
that the item is not in the set:
(define (element-of-set? x set)
(cond ((null? set) false)
((= x (car set)) true)
((< x (car set)) false)
(else (element-of-set? x (cdr set)))))
How many steps does this save? In the worst case, the item we are looking for
may be the largest one in the set, so the number of steps is the same as for
the unordered representation. On the other hand, if we search for items of
many different sizes we can expect that sometimes we will be able to stop
searching at a point near the beginning of the list and that other times we
will still need to examine most of the list. On the average we should expect
to have to examine about half of the items in the set. Thus, the average
number of steps required will be about n/2. This is still
[theta](n) growth, but it does save us, on the average, a factor of 2
in number of steps over the previous implementation.
We obtain a more impressive speedup with intersection-set . In the
unordered representation this operation required [theta](n^2) steps,
because we performed a complete scan of set2 for each element of
set1 . But with the ordered representation, we can use a more clever
method. Begin by comparing the initial elements, x1 and x2 , of
the two sets. If x1 equals x2 , then that gives an element of the
intersection, and the rest of the intersection is the intersection of the
cdr s of the two sets. Suppose, however, that x1 is less than
x2 . Since x2 is the smallest element in set2 , we can
immediately conclude that x1 cannot appear anywhere in set2 and
hence is not in the intersection. Hence, the intersection is equal to the
intersection of set2 with the cdr of set1 . Similarly, if
x2 is less than x1 , then the intersection is given by the
intersection of set1 with the cdr of set2 . Here is the
procedure:
To estimate the number of steps required by this process, observe that at each
step we reduce the intersection problem to computing intersections of smaller
sets---removing the first element from set1 or set2 or both.
Thus, the number of steps required is at most the sum of the sizes of
set1 and set2 , rather than the product of the sizes as with the
unordered representation. This is [theta](n) growth rather than
[theta](n^2)---a considerable speedup, even for sets of moderate size.
Exercise 2.61: Give an implementation of
adjoin-set using the ordered representation. By analogy with
element-of-set? show how to take advantage of the ordering to produce a
procedure that requires on the average about half as many steps as with the
unordered representation.
Exercise 2.62: Give a [theta](n)
implementation of union-set for sets represented as ordered lists.
Sets as binary trees
We can do better than the ordered-list representation by arranging the set
elements in the form of a tree. Each node of the tree holds one element of the