Structure and Interpretation of Computer Programs

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.

31

 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:

a.  Add some segments to the primitive 

wave

 painter of exercise  2.49 (to add a smile, for example).

b.  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).

c.  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.) 

6

 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. 

7

 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.’’ 

8

 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. 

9

 Since nested applications of 

car

 and 

cdr

 are cumbersome to write, Lisp dialects provide

abbreviations for them -- for instance, 

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. 

10

 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. 

---