# SICP-2.1.3节练习

lispor posted @ Feb 25, 2011 03:02:40 PM in Scheme with tags SICP , 1406 阅读

```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)))

scheme@(guile-user)> (define a (cons 1 2))
scheme@(guile-user)> (car a)
1
scheme@(guile-user)> (cdr a)
2```

```Show that we can represent pairs of nonnegative integers using only numbers and arithmetic
operations if we represent the pair a and b as the integer that is the product 2^a 3^b. Give the
corresponding definitions of the procedures cons, car, and cdr.
```

```程序：
(define (cons a b)
(* (expt 2 a)
(expt 3 b)))

(define (car z)
(define (iter a z)
(if (not (= 0 (remainder z 2)))
a
(iter (+ a 1) (/ z 2))))
(iter 0 z))

(define (cdr z)
(define (iter b z)
(if (not (= 0 (remainder z 3)))
b
(iter (+ b 1) (/ z 3))))
(iter 0 z))

scheme@(guile-user)> (define a (cons 3 5))
scheme@(guile-user)> (car a)
3
scheme@(guile-user)> (cdr a)
5```

```In case representing pairs as procedures wasn't mind-boggling enough, consider that, in a language
that can manipulate procedures, we can get by without numbers (at least insofar as nonnegative
integers are concerned) by implementing 0 and the operation of adding 1 as
(define zero (lambda (f) (lambda (x) x)))
(lambda (f) (lambda (x) (f ((n f) x)))))
This representation is known as Church numerals, after its inventor, Alonzo Church, the logician who
invented the [lambda] calculus.
Define one and two directly (not in terms of zero and add-1). (Hint: Use substitution to evaluate
(add-1 zero)). Give a direct definition of the addition procedure + (not in terms of repeated
```

```(define zero
(lambda (f)
(lambda (x) x)))

(lambda (f)
(lambda (x)
(f ((n f) x)))))

(define one
(lambda (f)
(lambda (x)
(f x))))

(define two
(lambda (f)
(lambda (x)
(f (f x)))))

(define (+ a b)
(lambda (f)
(lambda (x)
((a f) ((b f) x)))))
``` (输入验证码)
or Ctrl+Enter