In 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.
2.1.1Example: 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 ⟨n⟩ ⟨d⟩) returns the rational number whose numerator
is the integer ⟨n⟩ and whose denominator is the integer
⟨d⟩.- (numer ⟨x⟩) returns the numerator of the rational number
⟨x⟩.- (denom ⟨x⟩) returns the denominator of the rational number
⟨x⟩.
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. Thus, we can use cons, car, and
cdr as follows:
>>> x = [1, 2]
>>> x[0]
1
>>> x[1]
2
(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:
>>> x = [1, 2]
>>> y = [3, 4]
>>> z = [x, y]
>>> z[0][0]
1
>>> z[1][0]
3
(define x (cons 1 2))
(define y (cons 3 4))
(define z (cons x y))
(car (car z))
1
(car (cdr z))
3
In 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:
(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:
def print_rat(x):
print()
# display numerator, slash, and denominator without newlines between them
print(numer(x), end='')
print("/", end='')
print(denom(x))
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
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:
def make_rat(n, d):
g = gcd(n, d)
return [n // g, d // g]
(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
(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.
2.1.2Abstraction 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 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.
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:
from math import gcd
def make_rat(n, d):
return [n, d]
def numer(x):
g = gcd(x[0], x[1])
return x[0] // g
def denom(x):
g = gcd(x[0], x[1])
return x[1] // g
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?
2.1.3What Is Meant by Data?
We began the rational-number implementation in 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
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.
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. Here are the
definitions:
def cons(x, y):
def dispatch(m):
if m == 0:
return x
elif m == 1:
return y
else:
raise ValueError(f"Argument not 0 or 1: CONS {m}")
return dispatch
def car(z):
return z(0)
def cdr(z):
return z(1)
(define (cons x y)
(define (dispatch m)
(cond ((= m 0) x)
((= m 1) y)
(else
(error "Argument not 0 or 1:
CONS" m))))
dispatch)
(define (car z) (z 0))
(define (cdr z) (z 1))
This use of procedures corresponds to nothing like our intuitive notion of what
data should be. 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 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
def zero(f):
def inner(x):
return x
return inner
def add_1(n):
def new_num(f):
def result(x):
return f(n(f)(x))
return result
return new_num
This representation is known as
Church numerals, after its inventor,
Alonzo Church, the logician who invented the λ-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).
2.1.4Extended 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
$$R_{p}\; = \;\frac{1}{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:
def make_interval(a, b):
return [a, b]
> (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:
$$\frac{R_{1}R_{2}}{R_{1} + R_{2}}$$
and
$$\frac{1}{1/R_{1} + 1/R_{2}}.$$
He has written the following two programs, each of which computes the
parallel-resistors formula differently:
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.)
⇡
2.2Hierarchical 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.
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. 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.
2.2.1Representing Sequences
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:
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, 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. 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.”
List operations
The use of pairs to represent sequences of elements as lists is accompanied by
conventional programming techniques for manipulating lists by successively
“cdring down” the lists. For example, the procedure list-ref
takes as arguments a list and a number $n$ and returns the $n^{\text{th}}$ 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.
def list_ref(items, n):
if n == 0:
return items[0]
else:
return list_ref(items[1:], n - 1)
squares = [1, 4, 9, 16, 25]
>>> list_ref(squares, 3)
16
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 cdring down a list, as in the procedure append, which
takes two lists as arguments and combines their elements to make a new list:
Append is also implemented using a recursive plan. To append
lists list1 and list2, do the following:
- If list1 is the empty list, then the result is just list2.- Otherwise, append the cdr of list1 and list2, and
cons the car of list1 onto the result:
def append(list1, list2):
if not list1:
return list2
return [list1[0]] + append(list1[1:], list2)
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: return the final "pair" of a list as a one-element Python list
def last_pair(items):
if not items:
return None
if len(items) == 1:
return [items[0]]
return last_pair(items[1:])
>>> last_pair([23, 72, 149, 34])
[34]
> (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:
Exercise 2.19: Consider the change-counting
program of 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:
def cc(amount, coin_values):
# Count the number of ways to make change for `amount` using `coin_values`
if amount == 0:
return 1
elif amount < 0 or not coin_values:
return 0
else:
# ways without using the first coin + ways using at least one of the first coin
return cc(amount, coin_values[1:]) + cc(amount - coin_values[0], coin_values)
us_coins = [50, 25, 10, 5, 1]
>>> cc(100, us_coins)
292
> (cc 100 us-coins)
> 292
>
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
def f(x, y, *z):
...
> (define (f x y . z) ⟨body⟩)
>
the procedure f can be called with two or more arguments. If we
evaluate
>>> f(1, 2, 3, 4, 5, 6)
> (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
def g(*w):
...
> (define (g . w) ⟨body⟩)
>
the procedure g can be called with zero or more arguments. If we
evaluate
>>> g(1, 2, 3, 4, 5, 6)
> (g 1 2 3 4 5 6)
>
then in the body of g, w will be the list (1 2 3 4 5
6).
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,
def same_parity(*nums):
"""Return a list of numbers from nums that have the same parity as the first number."""
if not nums:
return []
first = nums[0]
parity = first % 2
return [n for n in nums if n % 2 == parity]
# REPL-style examples
>>> same_parity(1, 2, 3, 4, 5, 6, 7)
[1, 3, 5, 7]
>>> same_parity(2, 3, 4, 5, 6, 7)
[2, 4, 6]
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 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:
def map(proc, items):
# Recursive map: apply proc to each element of items (a Python list)
if not items:
return []
return [proc(items[0])] + map(proc, items[1:])
# REPL-style demonstration
print(">>> map(abs, [-10, 2.5, -11.6, 17])")
print(map(abs, [-10, 2.5, -11.6, 17]))
print(">>> map(lambda x: x * x, [1, 2, 3, 4])")
print(map(lambda x: x * x, [1, 2, 3, 4]))
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.
>>> def square_list(lst):
... return [x * x for x in lst]
>>> square_list([1, 2, 3, 4])
[1, 4, 9, 16]
> (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:
# Recursive version of square-list
def square_list_recursive(items):
# (define (square-list items)
# (if (null? items)
# nil
# (cons (square (car items)) (square-list (cdr items)))))
if not items:
return []
head, *tail = items
return [head * head] + square_list_recursive(tail)
# Map-based version of square-list
def square_list_map(items):
# (define (square-list items)
# (map (lambda (x) (* x x)) items))
return list(map(lambda x: x * x, items))
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,
>>> for x in [57, 321, 88]:
... print(x)
57
321
88
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.
2.2.2Hierarchical 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
>>> [[1, 2]] + [3, 4]
[[1, 2], 3, 4]
(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 inFigure 2.5viewed as a tree.
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 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)))
x = [[1, 2]] + [3, 4]
(define x (cons (list 1 2) (list 3 4)))
>>> len(x)
3
(length x)
3
>>> def count_leaves(tree):
... # A leaf is anything that's not a list; an empty list has 0 leaves
... if not isinstance(tree, list):
... return 1
... if len(tree) == 0:
... return 0
... total = 0
... for elem in tree:
... total += count_leaves(elem)
... return total
>>> x = [[1, 2], 3, 4]
>>> count_leaves(x)
4
>>> [x, x]
[[[1, 2], 3, 4], [[1, 2], 3, 4]]
>>> len([x, x])
2
>>> count_leaves([x, x])
8
(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 cars 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:
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 cars
and cdrs that will pick 7 from each of the following lists:
Exercise 2.26: Suppose we define x and
y to be two lists:
>>> x = [1, 2, 3]
>>> y = [4, 5, 6]
> (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:
>>> x + y
>>> [x] + y
>>> [x, y]
> (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,
# Define x
x = [[1, 2], [3, 4]]
def reverse(lst):
"""Return a new list with the top-level elements of lst reversed."""
return lst[::-1]
def deep_reverse(lst):
"""Recursively reverse a list and any nested lists."""
if not isinstance(lst, list):
return lst
return [deep_reverse(item) for item in reversed(lst)]
# REPL-style interaction
# >>> x
# [[1, 2], [3, 4]]
# >>> reverse(x)
# [[3, 4], [1, 2]]
# >>> deep_reverse(x)
# [[4, 3], [2, 1]]
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,
def fringe(tree):
# Return the list of leaves (fringe) of a tree represented with nested Python lists.
if tree == []:
return []
if not isinstance(tree, list):
return [tree]
result = []
for item in tree:
result.extend(fringe(item))
return result
x = [[1, 2], [3, 4]]
if __name__ == '__main__':
print(fringe(x))
print(fringe([x, x]))
# REPL-style examples:
# >>> x = [[1, 2], [3, 4]]
# >>> fringe(x)
# [1, 2, 3, 4]
# >>> fringe([x, x])
# [1, 2, 3, 4, 1, 2, 3, 4]
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.2. Using your selectors, define a procedure total-weight that returns the
total weight of a mobile.3. 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.4. 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 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:
def scale_tree(tree, factor):
# (define (scale-tree tree factor) ...)
if tree == []:
return []
if not isinstance(tree, list):
return tree * factor
return [scale_tree(sub, factor) for sub in tree]
>>> scale_tree([1, [2, [3, 4], 5], [6, 7]], 10)
[10, [20, [30, 40], 50], [60, 70]]
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:
def scale_tree(tree, factor):
# If tree is not a list, treat it as a leaf and scale it
if not isinstance(tree, list):
return tree * factor
return [
scale_tree(sub_tree, factor) if isinstance(sub_tree, list) else sub_tree * factor
for sub_tree in tree
]
Many tree operations can be implemented by similar combinations of sequence
operations and recursion.
Exercise 2.30: Define a procedure
square-tree analogous to the square-list procedure of
Exercise 2.21. That is, square-tree should behave as follows:
# Square every number in a tree (nested Python lists)
def square_tree(tree):
"""Return a new tree with every element squared.
A tree is represented as nested Python lists; leaves are numbers.
"""
if not isinstance(tree, list):
return tree * tree
return [square_tree(sub) for sub in tree]
# REPL-style demonstration:
# >>> square_tree([1, [2, [3, 4], 5], [6, 7]])
# [1, [4, [9, 16], 25], [36, 49]]
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 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 2.2.2, which takes a tree as
argument and computes the sum of the squares of the leaves that are odd:
>>> def sum_odd_squares(tree):
... # empty tree
... if tree is None or tree == []:
... return 0
... # atom (not a pair/list)
... elif not isinstance(tree, list):
... return tree * tree if tree % 2 != 0 else 0
... else:
... return sum_odd_squares(tree[0]) + sum_odd_squares(tree[1:])
On the surface, this procedure is very different from the following one, which
constructs a list of all the even Fibonacci numbers $\text{Fib}(k)$, where
$k$ is less than or equal to a given integer $n$:
# Simple fib implementation (can be replaced by another definition)
def fib(k):
if k < 2:
return k
a, b = 0, 1
for _ in range(2, k + 1):
a, b = b, a + b
return b
def even_fibs(n):
def next(k):
if k > n:
return []
f = fib(k)
if f % 2 == 0:
return [f] + next(k + 1)
else:
return next(k + 1)
return next(0)
(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 proceduressum-odd-squares(top) andeven-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 2.2.1:
Filtering a sequence to select only those elements that satisfy a given
predicate is accomplished by
def filter(predicate, sequence):
# Recursive filter: returns a new list of elements x in sequence for which predicate(x) is true
if len(sequence) == 0:
return []
elif predicate(sequence[0]):
return [sequence[0]] + filter(predicate, sequence[1:])
else:
return filter(predicate, sequence[1:])
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:
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:
import operator
def accumulate(op, initial, seq):
result = initial
for x in seq:
result = op(result, x)
return result
def square(x):
return x * x
def is_odd(x):
return x % 2 != 0
def enumerate_tree(tree):
... # Placeholder: define to yield/return all items in the tree
def sum_odd_squares(tree):
return accumulate(
operator.add,
0,
map(square, filter(is_odd, enumerate_tree(tree)))
)
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:
def enumerate_interval(a, b):
# returns a list of integers from a to b inclusive
return list(range(a, b + 1))
def fib(n):
# iterative Fibonacci: fib(0)=0, fib(1)=1
if n < 2:
return n
a, b = 0, 1
for _ in range(n - 1):
a, b = b, a + b
return b
def even_fibs(n):
# corresponds to:
# (accumulate cons nil (filter even? (map fib (enumerate-interval 0 n))))
return list(filter(lambda x: x % 2 == 0, map(fib, enumerate_interval(0, n))))
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:
# Translated from Scheme (SICP) to Python 3
def accumulate(combiner, null_value, sequence):
# recursive fold-right to preserve order
if not sequence:
return null_value
return combiner(sequence[0], accumulate(combiner, null_value, sequence[1:]))
def cons(x, xs):
return [x] + xs
nil = []
def map_(proc, seq):
return [proc(x) for x in seq]
def enumerate_interval(low, high):
if low > high:
return []
return list(range(low, high + 1))
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
def square(x):
return x * x
def list_fib_squares(n):
return accumulate(lambda x, xs: cons(x, xs),
nil,
map_(square, map_(fib, enumerate_interval(0, n))))
# REPL-style demonstration
print(">>> list_fib_squares(10)")
print(list_fib_squares(10))
We can rearrange the pieces and use them in computing the product of the squares of the odd
integers in a sequence:
def accumulate(op, initial, sequence):
result = initial
for x in sequence:
result = op(result, x)
return result
def square(x):
return x * x
def is_odd(x):
return x % 2 != 0
def product_of_squares_of_odd_elements(sequence):
return accumulate(lambda a, b: a * b, 1, map(square, filter(is_odd, sequence)))
>>> product_of_squares_of_odd_elements([1, 2, 3, 4, 5])
225
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
def salary_of_highest_paid_programmer(records):
# accumulate max 0 over map salary of filter programmer? records
# assumes `salary(record)` and `is_programmer(record)` are defined elsewhere
return max((salary(r) for r in records if is_programmer(r)), default=0)
These examples give just a hint of the vast range of operations that can be
expressed as sequence 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 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:
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}$.
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}$.
def accumulate(op, initial, sequence):
if not sequence:
return initial
else:
return op(sequence[0], accumulate(op, initial, sequence[1:]))
def horner_eval(x, coefficient_sequence):
return accumulate(lambda this_coeff, higher_terms: this_coeff + x * higher_terms,
0,
coefficient_sequence)
For example, to compute $1 + 3x + 5x^{3} + x^{5}$ at $x = 2$ you
would evaluate
def horner_eval(x, coeffs):
"""Evaluate a polynomial at x using Horner's rule.
Coeffs are given from highest-degree to lowest (e.g. [a_n, ..., a_0])."""
result = 0
for a in coeffs:
result = result * x + a
return result
>>> horner_eval(2, [1, 3, 0, 5, 0, 1])
101
> (horner-eval 2 (list 1 3 0 5 0 1))
>
Exercise 2.35: Redefine count-leaves from
2.2.2 as an accumulation:
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:
def accumulate_n(op, init, seqs):
# seqs is a list of sequences (lists)
if not seqs or len(seqs[0]) == 0:
return []
return [accumulate(op, init, [s[0] for s in seqs])] + accumulate_n(op, init, [s[1:] for s in seqs])
> (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
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:
$$\begin{array}{ll}
> \text{(dot-product v w)} & \text{returns the sum}\;Σ_{i}v_{i}w_{i} ; \\
> \text{(matrix-*-vector m v)} & \text{returns the vector}\;t, \\
> & \text{where}\;t_{i} = Σ_{j}m_{ij}v_{j} ; \\
> \text{(matrix-*-matrix m n)} & \text{returns the matrix}\;p, \\
> & \text{where}\;p_{ij} = Σ_{k}m_{ik}n_{kj} ; \\
> \text{(transpose m)} & \text{returns the matrix}\;n, \\
> & \text{where}\;n_{ij} = m_{ji}.
> \end{array}$$
We can define the dot product as
def dot_product(v, w):
"""Return the dot product of vectors v and w."""
return sum(x * y for x, y in zip(v, w))
> (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.)
def dot_product(v, w):
# Assumes v and w are sequences of equal length
return sum(a * b for a, b in zip(v, w))
def matrix_mul_vector(m, v):
# Multiply matrix m (list of rows) by vector v
return [dot_product(row, v) for row in m]
def transpose(mat):
# Transpose a matrix (list of rows) to a list of columns
if not mat:
return []
return [list(col) for col in zip(*mat)]
def matrix_mul_matrix(m, n):
# Multiply matrices m and n
cols = transpose(n)
return [[dot_product(row, col) for col in cols] for row in m]
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:
def fold_left(op, initial, sequence):
"""Fold a binary operation op left-to-right over sequence, starting with initial."""
result = initial
for item in sequence:
result = op(result, item)
return result
> (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. Consider this problem: Given a positive integer $n$, find all
ordered pairs of distinct positive integers $i$ and $j$, where
$1 \le j < i \le 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 \le n$,
enumerate the integers $j < i$, and for each such $i$ and $j$
generate the pair $(i,j)$. In terms of sequence operations, we map along
the sequence (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:
# accumulate, append, enumerate-interval, and the mapped expression translated from Scheme to Python
def enumerate_interval(a, b):
# return a list of integers from a to b inclusive; empty list if a > b
return [] if a > b else list(range(a, b + 1))
def append(x, y):
# append two lists (x and y)
return x + y
def accumulate(op, init, sequence):
# recursively accumulate over a Python list
if not sequence:
return init
first, *rest = sequence
return op(first, accumulate(op, init, rest))
def pairs_up_to(n):
# corresponds to:
# (accumulate
# append
# nil
# (map (lambda (i)
# (map (lambda (j) (list i j))
# (enumerate-interval 1 (- i 1))))
# (enumerate-interval 1 n)))
mapped = list(map(
lambda i: list(map(lambda j: [i, j], enumerate_interval(1, i - 1))),
enumerate_interval(1, n)
))
return accumulate(append, [], mapped)
# REPL-style demonstration
>>> pairs_up_to(3)
[[2, 1], [3, 1], [3, 2]]
(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:
Combining all these steps yields the complete procedure:
def prime_sum_pairs(n):
# Generate all pairs [i, j] with 1 <= j < i <= n, keep those whose sum is prime,
# and apply make_pair_sum to each.
pairs = [[i, j] for i in range(1, n + 1) for j in range(1, i)]
return list(map(make_pair_sum, filter(prime_sum_p, pairs)))
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$, 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$:
# permutations: generate all permutations of a sequence s
def permutations(s):
# if empty set?
if not s:
# sequence containing empty set
return [[]]
result = []
for i, x in enumerate(s):
# remove x from s by skipping index i
rest = s[:i] + s[i+1:]
for p in permutations(rest):
# cons x p -> [x] + p
result.append([x] + p)
return result
(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:
def remove(item, sequence):
return [x for x in sequence if x != item]
Exercise 2.40: Define a procedure
unique-pairs that, given an integer $n$, generates the sequence of
pairs $(i,j)$ with $1 \le j < i \le 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$.
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 $k^{\text{th}}$ 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 $k^{\text{th}}$ column. Now filter these, keeping
only the positions for which the queen in the $k^{\text{th}}$ 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.
Figure 2.8:A solution to the eight-queens 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 \times 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.
def queens(board_size):
def queen_cols(k):
if k == 0:
return [empty_board]
candidates = []
for rest_of_queens in queen_cols(k - 1):
for new_row in enumerate_interval(1, board_size):
candidates.append(adjoin_position(new_row, k, rest_of_queens))
return [positions for positions in candidates if safe(k, positions)]
return queen_cols(board_size)
(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 $k^{\text{th}}$ 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 $k^{\text{th}}$ 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 \times 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
>>> [adjoin_position(new_row, k, rest_of_queens)
... for new_row in enumerate_interval(1, board_size)
... for rest_of_queens in queen_cols(k - 1)]
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$.
2.2.4Example: 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. 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.
The picture language
When we began our study of programming in 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 MIT’s founder, William Barton Rogers, as shown in
Figure 2.11. The four images in figure 2.11 are drawn with respect to the same four
frames as the wave images in figure 2.10.
Figure 2.10:Images produced by thewavepainter, with respect to four different frames. The frames, shown with dotted lines, are not part of the images.
Figure 2.11:Images of William Barton Rogers, founder and first president ofMIT, painted with respect to the same four frames as inFigure 2.10(original image from Wikimedia Commons).
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.12 shows the drawing of a painter called
wave4 that is built up in two stages starting from wave:
Figure 2.12:Creating a complex figure, starting from thewavepainter ofFigure 2.10.
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 produce balanced patterns by branching upwards as well as towards the
right (see Exercise 2.44, Figure 2.13 and Figure 2.14):
def corner_split(painter, n):
if n == 0:
return painter
else:
up = up_split(painter, n - 1)
right = right_split(painter, n - 1)
top_left = beside(up, up)
bottom_right = below(right, right)
corner = corner_split(painter, n - 1)
return beside(below(painter, top_left),
below(bottom_right, corner))
(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 operationsright-splitandcorner-splitapplied to the painterswaveandrogers. Combining fourcorner-splitfigures produces symmetricsquare-limitdesigns as shown inFigure 2.9.
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.
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 \le x,y \le 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
$$\text{Origin(Frame)} + x ⋅ \text{Edge}_{1}\text{(Frame)} + y ⋅ \text{Edge}_{2}\text{(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:
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))
((frame-coord-map a-frame) (make-vect 0 0))
returns the same vector as
>>> origin_frame(a_frame)
(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:
def segments_to_painter(segment_list):
def painter(frame):
coord_map = frame_coord_map(frame)
for segment in segment_list:
start = coord_map(start_segment(segment))
end = coord_map(end_segment(segment))
draw_line(start, end)
return painter
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.
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:
1. The painter that draws the outline of the designated frame.2. The painter that draws an “X” by connecting opposite corners of the frame.3. The painter that draws a diamond shape by connecting the midpoints of the sides
of the frame.4. 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.
def flip_vert(painter):
return 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
)
(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. 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:
1. Add some segments to the primitive wave painter of Exercise 2.49
(to add a smile, for example).2. 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).3. 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.)
Adapted from Structure and Interpretation of Computer Programs
by Harold Abelson and Gerald Jay Sussman (MIT Press, 1996).
Original Scheme examples translated to Python.