Exercise 2.4 of SICP

Exercise 2.4: 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.)

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

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

(define (cdr z)
  (z (lambda (p q) q)))
> (car (cons 1 2))
1
> (cdr (cons 1 2))
2

The reason this works is because upon execution of cons the function that is returned is used in a clever way by car and cons. Car and cdr pass a function via the m parameter in the cons. That function then receives as arguments xand y. In the case of cdr the second parameter is returned. The thing to note is that x and y get stored in the lambda function when the cons procedure is called.

(car (cons 1 2))
(car (lambda (m) (m 1 2)))
((lambda (m) (m 1 2)) (lambda (p q) p))
((lambda (p q) p) 1 2)
(lambda (1 2) 1)
1