Exercise 2.4 gives us the following alternative procedual implementation for creating pairs.

`(define (cons x y)`

(lambda (m) (m x y)))

(define (car z)

(z (lambda (p q) p)))

Using this implementation, we are told to verify that

`(car (cons x y))`

yields x for any objects x and y using the substitution model from section 1.1.5.Once we've done that, we need to write the corresponding definition of

`cdr`

.Our first step to verifying that this implementation for

`cons`

and `car`

work should be to put the code in a Scheme interpreter and see them work.`> (car (cons 2 3))`

2

> (car (cons 15 "Hello"))

15

> (car (cons "Hi!" 42))

"Hi!"

Now let's use the substitution model to show that the following always yields x

`(car (cons x y))`

First we retrieve the body of

`cons`

`(lambda (m) (m x y))`

We could replace the formal parameters x and y with the arguments 2 and 3 (or any others that we choose) at this point, but I'm going to keep working with x and y. Let's substitute the body of

`cons`

.`(car (lambda (m) (m x y)))`

Now we can retrieve the body of

`car`

and substitute it.`((z (lambda (p q) p)) (lambda (m) (m x y)))`

The

`car`

procedure takes a procedure z as an argument and applies it to `(lambda (p q) p)`

, so there's one more substitution we need to do here before this step is really done. We need to take the second lambda in the expression above and replace z with it.`((lambda (m) (m x y)) (lambda (p q) p))`

That might look scary, but it's just a procedure applied to another procedure. Since the procedure on the left takes one formal parameter, we can substitute the procedure on the right for that parameter.

`((lambda (p q) p) x y)`

Now it should be clear that this expression is a procedure that takes two parameters p and q, and passes two parameters to it. The procedure returns the first of the two parameters passed to it, so this expression simplifies to x.

The definition for

`cdr`

that corresponds to the above implementation of `car`

is simply`(define (cdr z)`

(z (lambda (p q) q)))

We can test it out the same way we originally tested the code provided in the text,

by running it in the interpreter.

`> (cdr (cons 2 3))`

3

> (cdr (cons 15 "Hello"))

"Hello"

> (cdr (cons "Hi!" 42))

42

Related:

For links to all of the SICP lecture notes and exercises that I've done so far, see The SICP Challenge.

## 4 comments:

Fantastically mind-bending. This kind of thing is the reason SICP is worth working through.

Tim,

When I saw this comment in my email I thought for sure you were talking about 2.5. It applies equally well to 2.6.

SICP is definitely making me think in new ways. :)

it seems that cdr should return a list not the second value in general. But at this point the book only explains pairs.

@jieliu

cdr always returns the second item of a cons cell - sometimes that second item is another cons cell.

Post a Comment