## **Note: this wiki is now retired and will no longer be updated!**

**The static final versions of the pages are left as a convenience for readers. Note that meta-pages such as "discussion," "history," etc., will not work.**

# SICP exercise 2.04

## 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