SICP Exercise 2.4: Procedural Pairs

Here is an alternative procedural representation of pairs. For this representation, verify that (car (cons x y)) yields x for any objects x and y.

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

What is the corresponding definition of cdr? (Hint: To verify that this works, make use of the substitution model of section 1.1.5.)

So let's evaluate (car (cons x y)) using substitution:

  (car (cons x y))
= (car (lambda (m) (m x y))
= ((lambda (m) (m x y)) (lambda (p q) p))
= ((lambda (p q) p) x y)
= x

We can also check it works at the interpreter prompt:

> (car (cons 1 2))
1

Okay, so that all seems to work. So let's now think about our definition of cdr. The alternative representation produced by cons is a single parameter lambda expression. The parameter needs to be a procedure that takes two parameters, the first and second values of the pair. The corresponding definition of car treats the representation as a single-parameter procedure, and passes a lambda expression as the parameter that takes two parameters and returns the first parameter. We need cdr to have equivalent functionality, except this time the lambda expression passed needs to return the second parameter passed to it. I.e.:

(define (cdr z)
  (z (lambda (p q) q)))

As with car, we can evaluate (cdr (cons x y)) using substitution:

  (cdr (cons x y))
= (cdr (lambda (m) (m x y))
= ((lambda (m) (m x y)) (lambda (p q) q))
= ((lambda (p q) q) x y)
= y

...and we can also check it works at the interpreter prompt:

> (cdr (cons 1 2))
2