Structure and Interpretation of Computer Programs

Be careful not to confuse the expression 

(list 1 2 3 4)

 with the list 

(1 2 3 4)

, which is the

result obtained when the expression is evaluated. Attempting to evaluate the expression 

(1 2 3 4)

will signal an error when the interpreter tries to apply the procedure 

1

 to arguments 

2

, 

3

, and 

4

.

We can think of 

car

 as selecting the first item in the list, and of 

cdr

 as selecting the sublist

consisting of all but the first item. Nested applications of 

car

 and 

cdr

 can be used to extract the

second, third, and subsequent items in the list.

9

 The constructor 

cons

 makes a list like the original

one, but with an additional item at the beginning.

(car one-through-four)

1

(cdr one-through-four)

(2 3 4)

(car (cdr one-through-four))

2

(cons 10 one-through-four)

(10 1 2 3 4)

(cons 5 one-through-four)

(5 1 2 3 4)

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

10

List operations

The use of pairs to represent sequences of elements as lists is accompanied by conventional

programming techniques for manipulating lists by successively ‘‘

cdr

ing down’’ the lists. For

example, the procedure 

list-ref

 takes as arguments a list and a number n and returns the nth item

of the list. It is customary to number the elements of the list beginning with 0. The method for

computing 

list-ref

 is the following:

For n = 0, 

list-ref

 should return the 

car

 of the list.

Otherwise, 

list-ref

 should return the (n - 1)st item of the 

cdr

 of the list.

(define (list-ref items n)

  (if (= n 0)

      (car items)

      (list-ref (cdr items) (- n 1))))

(define squares (list 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:

(define (length items)

  (if (null? items)

      0

      (+ 1 (length (cdr items)))))

(define odds (list 1 3 5 7))

---

(length odds)

4

The 

length

 procedure implements a simple recursive plan. The reduction step is:

The 

length

 of any list is 1 plus the 

length

 of the 

cdr

 of the list.

This is applied successively until we reach the base case:

The 

length

 of the empty list is 0.

We could also compute 

length

 in an iterative style:

(define (length items)

  (define (length-iter a count)

    (if (null? a)

        count

        (length-iter (cdr a) (+ 1 count))))

  (length-iter items 0))

Another conventional programming technique is to ‘‘

cons

 up’’ an answer list while 

cdr

ing down a

list, as in the procedure 

append

, which takes two lists as arguments and combines their elements to

make a new list:

(append squares odds)

(1 4 9 16 25 1 3 5 7)

(append odds squares)

(1 3 5 7 1 4 9 16 25)

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:

(define (append list1 list2)

  (if (null? list1)

      list2

      (cons (car list1) (append (cdr list1) 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 (list 23 72 149 34))

(34)

Exercise 2.18.  Define a procedure 

reverse

 that takes a list as argument and returns a list of the

same elements in reverse order:

---

(reverse (list 1 4 9 16 25))

(25 16 9 4 1)

Exercise 2.19.  Consider the change-counting program of section 1.2.2. It would be nice to be able to

easily change the currency used by the program, so that we could compute the number of ways to

change a British pound, for example. As the program is written, the knowledge of the currency is

distributed partly into the procedure 

first-denomination

 and partly into the procedure 

count-change

 (which knows that there are five kinds of U.S. coins). It would be nicer to be able to

supply a list of coins to be used for making change.

We want to rewrite the procedure 

cc

 so that its second argument is a list of the values of the coins to

use rather than an integer specifying which coins to use. We could then have lists that defined each

kind of currency:

(define us-coins (list 50 25 10 5 1))

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

We could then call 

cc

 as follows:

(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 (cc amount coin-values)

  (cond ((= amount 0) 1)

        ((or (< amount 0) (no-more? coin-values)) 0)

        (else

         (+ (cc amount

                (except-first-denomination coin-values))

            (cc (- amount

                   (first-denomination coin-values))

                coin-values)))))

Define the procedures 

first-denomination

, 

except-first-denomination

, and 

no-more?

 in terms of primitive operations on list structures. Does the order of the list 

coin-values

 affect the answer produced by 

cc

? Why or why not? 

Exercise 2.20.  The procedures 

+

, 

*

, and 

list

 take arbitrary numbers of arguments. One way to

define such procedures is to use 

define

 with dotted-tail notation. In a procedure definition, a

parameter list that has a dot before the last parameter name indicates that, when the procedure is

called, the initial parameters (if any) will have as values the initial arguments, as usual, but the final

parameter’s value will be a list of any remaining arguments. For instance, given the definition 

(define (f x y . z) )

the procedure 

f

 can be called with two or more arguments. If we evaluate 

(f 1 2 3 4 5 6)

---