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

From Drewiki
Jump to: navigation, search

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
Personal tools