SICP exercise 2.04

From Drewiki

Problem

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 of the text.)

Solution

As the problem statement suggests, we can verify this representation using the substitution model of evaluation. If z is an object created by the cons procedure given above, then:

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

Substituting the definition of cons for z:

((lambda (m) (m x y)) (lambda (p q) p))

Now substitute the second lambda expression for the value of m in the first lambda expression to get:

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

Applying the lambda expression to its arguments x and y, we get this:

x

Now we need the definition of cdr:

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

Verifying by substitution, where z is an object constructed by cons:

(cdr z)
 
(z (lambda (p q) q))
 
((lambda (m) (m x y)) (lambda (p q) q))
 
((lambda (p q) q) x y)
 
y