SICP Exercise 2.4

Question

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)
  (λ (m) (m x y)))

(define (car z)
  (z (λ (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.)

Answer

First, we should verify that car does what it is supposed to do:

(define (cons x y)
  (λ (m) (m x y)))

(define (car z)
  (z (λ (p q) p)))

(define z (cons 2 3))
(car z)

Results:

2

So car seems to work well. Let us implement cdr analogue to this.

(define (cdr z)
  (z (λ (p q) q)))

And let’s also look at the evaluation of cdr. Here, I am using normal order evaluation.

(cdr z)

; substitute definition of cdr
(z (λ (p q) q))

; substitute definition of z
((cons 2 3) (λ (p q) q))

;substitute definition of cons
((λ (m) (m 2 3)) (λ (p q) q))

; evaluate m
((λ (p q) q) 2 3)

; evaluate
3