sicp-ex-2.4


 ;; ex 2.4.  Alternate procedural rep of pairs. 
  
 ;; given: 
  
 (define (cons a b) 
   (lambda (m) (m a b))) 
  
 ;; Commentary: cons returns a function that takes a function of 2 
 ;; args, a and b.  The function will receive the values of a and b 
 ;; passed to cons when cons was called initially. 
  
 ;; z is a function that takes a 2-arg function.  That inner function 
 ;; will be passed p and q in that order, so just return the first arg, p. 
 (define (car z) 
   (z (lambda (p q) p))) 
  
  
 ;; ... so this is obvious. 
 (define (cdr z) 
   (z (lambda (p q) q))) 
  
  
  
 ;; Usage: 
 (define x (cons 3 4)) 
 (car x) 
 (cdr x) 

Using applicative-order evaluation, verify that (car (cons x y)) yields x for any objects x and y:

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

<< Previous exercise (2.3) | Index | Next exercise (2.5) >>


jz

Proof that this works through the substitution rule:

 (car (cons a b)) 
 ;-> ((cons a b) (lambda (p q) p)) 
 ;-> ((lambda (m) (m a b)) (lambda (p q) p)) 
 ;-> ((lambda (p q) p) a b) 
 ;-> a 

I'm not 100% with this demonstration, please edit if you can improve it. jz