SICP - Solution: Exercise 2.4

# SICP - Solution: Exercise 2.4

## 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 1.1.5.)

## Solution #

Applyting the substition model on cons to:

(car (cons x y))


will give:

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


It means that car will take as a parameter the anonymous function (lambda (m) (m x y)). This function takes a function m as a parameter and this function m will receive x and y as parameters.

The definition of car takes a function as parameters and will evaluate this function by passing an anonymous function as argument: (lambda (p q) p). This anonymous function takes two parameters and return the first one.

We can continue our substitution by inserting the definition of car:

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


This looks like a lot of parentheses, but it means that the first function (lambda (m) (m x y)) takes the anonymous function (lambda (p q) p) as a parameter. When substituting m for the parameter, we have:

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


which will evaluate to:

x
`