\$B&K(B2.3\$B@a(B

\$BLdBj(B 2.53\$B!!(B \$BLdBj(B 2.54\$B!!(B \$BLdBj(B 2.55\$B!!(B \$BLdBj(B 2.56\$B!!(B \$BLdBj(B 2.57\$B!!(B
\$BLdBj(B 2.58\$B!!(B \$BLdBj(B 2.59\$B!!(B \$BLdBj(B 2.60\$B!!(B \$BLdBj(B 2.61\$B!!(B \$BLdBj(B 2.62\$B!!(B
\$BLdBj(B 2.63\$B!!(B \$BLdBj(B 2.64\$B!!(B \$BLdBj(B 2.65\$B!!(B \$BLdBj(B 2.66\$B!!(B \$BLdBj(B 2.67\$B!!(B
\$BLdBj(B 2.68\$B!!(B \$BLdBj(B 2.69\$B!!(B \$BLdBj(B 2.70\$B!!(B \$BLdBj(B 2.71\$B!!(B \$BLdBj(B 2.72\$B!!(B
\$B5-9fHyJ,(B\$B!!(B

\$B5-9fHyJ,(B
```\$B\$3\$N%U%!%\$%k\$r(Bsymdiff\$B\$H\$9\$k(B. \$B0J2<\$NLdBj\$GFI\$_9~\$`(B
(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
(else
(error "unknown expression type -- DERIV" exp))))

(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
(and (variable? v1) (variable? v2) (eq? v1 v2)))
(define (make-sum a1 a2) (list '+ a1 a2))
(define (make-product m1 m2) (list '* m1 m2))
(define (sum? x)
(and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (product? x)
(and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(display (deriv '(+ x 3) 'x)) (newline)
(display (deriv '(* x y) 'x)) (newline)
(display (deriv '(* (* x y) (+ x 3)) 'x)) (newline)
(define (make-sum a1 a2)
(cond ((=number? a1 0) a2)
((=number? a2 0) a1)
((and (number? a1) (number? a2)) (+ a1 a2))
(else (list '+ a1 a2))))
(define (=number? exp num)
(and (number? exp) (= exp num)))
(define (make-product m1 m2)
(cond ((or (=number? m1 0) (=number? m2 0)) 0)
((=number? m1 1) m2)
((=number? m2 1) m1)
((and (number? m1) (number? m2)) (* m1 m2))
(else (list '* m1 m2))))
(display (deriv '(+ x 3) 'x)) (newline)
(display (deriv '(* x y) 'x)) (newline)
(display (deriv '(* (* x y) (+ x 3)) 'x)) (newline)
```
\$BLdBj(B 2.53
```(list 'a 'b 'c) ==> (a b c)

(list (list 'george)) ==> ((george))

(cdr '((x1 x2) (y1 y2))) ==> ((y1 y2))

(cadr '((x1 x2) (y1 y2))) ==> (y1 y2)

(pair? (car '(a short list))) ==> ()

(memq 'red '((red shoes) (blue socks))) ==> ()
```
\$BLdBj(B 2.54
```(define (equal? a b)
(or (and (not (pair? a)) (not (pair? b)) (eq? a b))
(and (pair? a) (pair? b)
(equal? (car a) (car b)) (equal? (cdr a) (cdr b)))))
```
\$BLdBj(B 2.53
''abracadabra\$B\$O(BScheme\$B\$N%7%9%F%`Fb\$X\$O(B (quote (quote abracadabra))\$B\$H\$7\$FFI\$_9~\$^\$l(B, (car ''abracadabra)\$B\$NI>2A;~\$N0z?tI>2A\$G(Bquote\$B\$,0l\$D\$H\$l(B, (quote abracadabra) \$B\$H\$7\$F(Bcar\$B\$KEO\$5\$l\$k(B. \$B\$7\$?\$,\$C\$F\$=\$N(Bcar, \$B\$D\$^\$j(Bquote\$B\$,I>2A7k2L\$H\$J\$k(B.

\$BLdBj(B 2.56
```(load "symdiff.sch") ;; \$B5-9fHyJ,\$N%U%!%\$%k\$rFI\$`(B

(define (make-exponentiation base exponent)
(cond ((=number? exponent 0) 1)
((=number? exponent 1) base)
(else (list '** base exponent))))

(define (exponentiation? x)
(and (pair? x) (eq? (car x) '**)))

(define (base e) (cadr e))

(define (exponet e) (caddr e))

(define (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(make-sum (deriv (addend exp) var)
(deriv (augend exp) var)))
((product? exp)
(make-sum
(make-product (multiplier exp)
(deriv (multiplicand exp) var))
(make-product (deriv (multiplier exp) var)
(multiplicand exp))))
((exponentiation? exp)
(make-product (exponet exp)
(make-product
(make-exponentiation
(base exp) (- (exponet exp) 1))
(deriv (base exp) var))))
(else
(error "unknown expression type -- DERIV" exp))))

(deriv '(+ (** x 3) (+ (** x 2) (+ x 1))) 'x)
```
\$BLdBj(B 2.57
```(define (augend s)
(if (null? (cdddr s))
(caddr s)
(cons '+ (cddr s))))
(define (multiplicand p)
(if (null? (cdddr p))
(caddr p)
(cons '* (cddr p))))

```
\$BLdBj(B 2.58
```a.

87\$B%Z!<%8\$N9=@.;R\$HA*Br;R\$rJQ99\$9\$k(B.

(define (make-sum a1 a2) (list a1 '+ a2))

(define (make-product m1 m2) (list m1 '* m2))

(define (sum? x)
(and (pair? x) (eq? (cadr x) '+)))

(define (addend s) (car s))

(define (augend s) (caddr s)) ;\$BJQ99\$J\$7(B

(define (product? x)
(and (pair? x) (eq? (cadr x) '*)))

(define (multiplier p) (car p))

(define (multiplicand p) (caddr p)) ;\$BJQ99\$J\$7(B

b. compiler\$B\$r=q\$/I,MW\$,\$"\$k(B.

(define (compile exp)
(cond ((symbol? exp) exp)
((number? exp) exp)
((eq? (car exp) '+) exp)
((eq? (car exp) '*) exp)
((= (length exp) 3)
(list (cadr exp) (compile (car exp)) (compile (caddr exp))))
((> (length exp) 4)
(cond ((eq? (cadr exp) (cadddr exp))
(compile (cons (list (cadr exp) (compile (car exp))
(compile (caddr exp)))
(cdddr exp))))
((and (eq? (cadr exp) '+) (eq? (cadddr exp) '*))
(let ((a (car exp)) (b (cadr exp)) (c (caddr exp))
(d (cadddr exp)) (e (list-ref exp 4))
(f (list-tail exp 5)))
(compile (cons a (cons b (cons
(list d (compile c) (compile e)) f))))))))))

;\$B%F%9%H(B

(compile '(x + 3 * (x + y + 2)))
;==> (+ x (* 3 (+ (+ x y) 2)))
```
\$BLdBj(B 2.59
```(define (union-set set1 set2)
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else (cons (car set1)
(union-set (cdr set1) set2)))))

```
\$BLdBj(B 2.60
```(define (element-of-set? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
(cons x set)))

(define (union-set set1 set2)
(append set1 set2))

(define (intersection-set set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((element-of-set? (car set1) set2)
(cons (car set1)
(intersection-set (cdr set1) set2)))
(else (intersection-set (cdr set1) set2))))
```
\$BLdBj(B 2.61
```(define (adjoin-set x set)
(cond ((null? set) (list x))
((= x (car set)) set)
((< x (car set)) (cons x set))
(else (cons (car set) (adjoin-set x (cdr set))))))

(define set '(2 4 6))

(adjoin-set 1 set) ==> (1 2 4 6)
(adjoin-set 3 set) ==> (2 3 4 6)
(adjoin-set 7 set) ==> (2 4 6 7)
```
\$BLdBj(B 2.62
```(define (union-set set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
(else (let ((x1 (car set1)) (x2 (car set2)))
(cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2))))
((< x1 x2) (cons x1 (union-set (cdr set1) set2)))
((> x1 x2) (cons x2 (union-set set1 (cdr set2)))))))))

(union-set '(1 2 3) '(4 5 6)) ==> (1 2 3 4 5 6)
(union-set '(1 2 3) '(1 2 3)) ==> (1 2 3)
(union-set '() '(1 2)) ==> (1 2)
(union-set '(1 2) '()) ==> (1 2)
(display (union-set '() '())) (newline)
(display (union-set '(1 3 5) '(2 4 6))) (newline)
```
\$BLdBj(B 2.63
```(define (tree->list-1 tree)
(display "1")
(if (null? tree)
'()
(append (tree->list-1 (left-branch tree))
(cons (entry tree)
(tree->list-1 (right-branch tree))))))

(define (tree->list-2 tree)
(define (copy-to-list tree result-list)
(display "2")
(if (null? tree)
result-list
(copy-to-list (left-branch tree)
(cons (entry tree)
(copy-to-list (right-branch tree)
result-list)))))
(copy-to-list tree '()))

a. \$BFs\$D\$N
\$BLdBj(B 2.64
(define (list->tree elements)
(car (partial-tree elements (length elements))))

(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let ((left-size (quotient (- n 1) 2)))
(let ((left-result (partial-tree elts left-size)))
(let ((left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1))))
(let ((this-entry (car non-left-elts))
(right-result (partial-tree (cdr non-left-elts)
right-size)))
(let ((right-tree (car right-result))
(remaining-elts (cdr right-result)))
(cons (make-tree this-entry left-tree right-tree)
remaining-elts))))))))

(define (make-tree entry left right)
(list entry left right))

(list->tree (list 1 3 5 7 9 11)) ==> (5 (1 () (3 () ())) (9 (7 () ()) (11 () ())))

partial-tree\$B\$NF/\$-(B:

elts\$B\$O%=!<%H\$7\$F\$"\$k\$H2>Dj!%(B

n = 0 \$B\$N;~(B (() . elts) \$B\$rJV\$9!%(B
n > 0 \$B\$N;~(B (elts\$B\$N:G:8(Bn\$B8D\$ND`\$j9g\$C\$?Fs?JLZ(B . elts\$B\$N;D\$j(B) \$B\$rJV\$9!%(B
n\$B8D\$N\$&\$A:8ItJ,LZ\$K\$J\$k8D?t(B left-size (n - 1)/2 (1\$B\$O(Bthis-entry\$B\$N\$?\$a\$N?t(B
\$B\$G(Bpartial-tree\$B\$r8F\$V(B
(\$B:8ItJ,LZ(B \$B!%;D\$j(B) \$B\$,JV\$k!%:8ItJ,LZ\$r(Bleft-tree\$B\$K5-21!%;D\$j\$r(Bnon-left-tree
\$B\$H\$9\$k!%(Bnon-left-tree\$B\$N@hF,\$r(Bthis-entry\$B\$H\$7\$F5-21!%\$=\$N;D\$j\$+\$i(Bright-size
\$B8D\$N1&ItJ,LZ\$r:n\$j\$K9T\$/(B
(\$B1&ItJ,LZ(B \$B!%;D\$j(B) \$B\$,JV\$k!%1&ItJ,LZ\$r(Bright-tree\$B\$K5-21!%;D\$j\$r(B remaining-elts
\$B\$H\$9\$k!%(B
make-tree\$B\$r;H\$\$!\$(B((this-entry left-tree right-tree) . remaining-elts)
\$B\$rJV\$9!%(B

(1 3 5 7 9 11)\$B\$r(Bpartial-tree\$B\$K\$+\$1\$k!%D9\$5\$O(B6\$B\$@\$+\$i!\$(Bleft-size\$B\$O(B2\$B!%(B
\$B
\$BLdBj(B 2.65
\$BLdBj(B2.63, 2.64\$B\$G(Btree->list-1, list->tree\$B\$O&H(B(n)\$B\$G\$"\$k\$3\$H\$,(B
\$BJ,\$+\$C\$?\$N\$G(B, \$B\$=\$l\$r;H\$&(B. union-set\$B\$H(Bintersection-set\$B\$O(B, \$B=g=x(B
\$B\$D\$1\$i\$l\$?%j%9%H\$H\$7\$F\$N=89g\$GDj5A\$7\$?&H(B(n)\$B\$Ntree (union-set (tree->list-1 tree1)
(tree->list-1 tree2))))

(define (intersection-set-tree tree1 tree2)
(list->tree (intersection-set (tree->list-1 tree1)
(tree->list-1 tree2))))

\$BLdBj(B 2.66
(define (look-up given-key set-of-record)
(cond ((null? set-of-record) false)
((equal? given-key (key (car set-of-record)))
(car set-of-record))
((< (order given-key) (order (key (car set-of-record))))
(look-up given-key (cadr set-of-record)))
(else (look-up given-key (caddr set-of-record)))))

key\$B\$O(Brecord\$B\$+\$i%-!<\$NItJ,\$r
\$BLdBj(B 2.67
(define (make-leaf symbol weight)
(list 'leaf symbol weight))

(define (leaf? object)
(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)
(if (leaf? tree)
(list (symbol-leaf tree))
(caddr tree)))

(define (weight tree)
(if (leaf? tree)
(weight-leaf tree)
(cadddr tree)))

(define (decode bits tree)
(define (decode-1 bits current-branch)
(if (null? bits)
'()
(let ((next-branch
(choose-branch (car bits) current-branch)))
(if (leaf? next-branch)
(cons (symbol-leaf next-branch)
(decode-1 (cdr bits) tree))
(decode-1 (cdr bits) next-branch)))))
(decode-1 bits tree))

(define (choose-branch bit branch)
(cond ((= bit 0) (left-branch branch))
((= bit 1) (right-branch branch))
(else (error "bad bit -- CHOOSE-BRANCH" bit))))

(define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))

(define sample-message '(0 1 1 0 0 1 0 1 0 1 1 1 0))

(decode sample-message sample-tree) ;; ==> (a d a b b c a)

\$BLdBj(B 2.68
(define (make-leaf symbol weight)
(list 'leaf symbol weight))

(define (leaf? object)
(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)
(if (leaf? tree)
(list (symbol-leaf tree))
(caddr tree)))

(define (weight tree)
(if (leaf? tree)
(weight-leaf tree)
(cadddr tree)))

(define sample-tree
(make-code-tree (make-leaf 'A 4)
(make-code-tree
(make-leaf 'B 2)
(make-code-tree (make-leaf 'D 1)
(make-leaf 'C 1)))))

(define (encode message tree)
(if (null? message)
'()
(append (encode-symbol (car message) tree)
(encode (cdr message) tree))))

(define (element-of-set? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (element-of-set? x (cdr set)))))

(define (encode-symbol symbol tree)
(if (leaf? tree) '()
(let ((lb (left-branch tree)) (rb (right-branch tree)))
(cond ((element-of-set? symbol (symbols lb))
(cons 0 (encode-symbol symbol lb)))
((element-of-set? symbol (symbols rb))
(cons 1 (encode-symbol symbol rb)))))))

(encode '(a d a b b c a) sample-tree) ;; ==> (0 1 1 0 0 1 0 1 0 1 1 1 0)

\$BLdBj(B 2.69
(define (make-leaf symbol weight)
(list 'leaf symbol weight))

(define (leaf? object)
(eq? (car object) 'leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

(define (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

(define (left-branch tree) (car tree))

(define (right-branch tree) (cadr tree))

(define (symbols tree)
(if (leaf? tree)
(list (symbol-leaf tree))
(caddr tree)))

(define (weight tree)
(if (leaf? tree)
(weight-leaf tree)
(cadddr tree)))

(define (generate-huffman-tree pairs)
(successive-merge (make-leaf-set pairs)))

(define (adjoin-set x set)
(cond ((null? set) (list x))
((< (weight x) (weight (car set))) (cons x set))
(else (cons (car set)
(adjoin-set x (cdr set))))))

(define (make-leaf-set pairs)
(if (null? pairs)
'()
(let ((pair (car pairs)))
(adjoin-set (make-leaf (car pair)
(cadr pair))
(make-leaf-set (cdr pairs))))))

(define (successive-merge set)
(if (= (length set) 1) (car set)
(let ((sorted-set (sort set (lambda (x y) (< (weight x) (weight y))))))
(successive-merge
(cons (make-code-tree (car sorted-set) (cadr sorted-set))
(cddr sorted-set))))))

(define sample-pairs '((a 8) (b 3) (c 1) (d 1) (e 1) (f 1) (g 1) (h 1)))

(generate-huffman-tree sample-pairs)

;; ==> ((leaf a 8)
;;      ((((leaf c 1) (leaf d 1) (c d) 2)
;;        ((leaf h 1) (leaf g 1) (h g) 2) (c d h g) 4)
;;       (((leaf f 1) (leaf e 1) (f e) 2)
;;        (leaf b 3) (f e b) 5) (c d h g f e b) 9)
;;      (a c d h g f e b) 17)

\$BLdBj(B 2.70
Huffman\$BLZ(B

((leaf na 16)
((leaf yip 9)
(((leaf a 2) ((leaf wah 1) (leaf boom 1) (wah boom) 2) (a wah boom) 4)
((leaf sha 3) ((leaf job 2) (leaf get 2) (job get) 4) (sha job get) 7)
(a wah boom sha job get)
11)
(yip a wah boom sha job get)
20)
(na yip a wah boom sha job get)
36)

\$BId9f2=(B
(1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0
1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1
1 0 1 1)

Huffman\$BId9f\$G\$O(B 84\$B%S%C%H(B

\$B8GDjD9Id9f\$G\$O(B 36*3= 108\$B%S%C%H(B

\$BLdBj(B 2.71
(generate-huffman-tree '((a 1) (b 2) (c 4) (d 8) (e 16))) ==>

(((((leaf a 1) (leaf b 2) (a b) 3) (leaf c 4) (a b c) 7)
(leaf d 8)
(a b c d)
15)
(leaf e 16)
(a b c d e)
31)

(generate-huffman-tree '((a 1) (b 2) (c 4) (d 8) (e 16)
(f 32) (g 64) (h 128) (i 256) (j 512))) ==>

((((((((((leaf a 1) (leaf b 2) (a b) 3) (leaf c 4) (a b c) 7)
(leaf d 8)
(a b c d)
15)
(leaf e 16)
(a b c d e)
31)
(leaf f 32)
(a b c d e f)
63)
(leaf g 64)
(a b c d e f g)
127)
(leaf h 128)
(a b c d e f g h)
255)
(leaf i 256)
(a b c d e f g h i)
511)
(leaf j 512)
(a b c d e f g h i j)
1023)

\$B:G9bIQEY(B 1\$B%S%C%H(B
\$B:GDcIQEY(B n-1\$B%S%C%H(B

\$BLdBj(B 2.72 \$BLdBj(B2.71\$B\$NIQEY\$@\$H>e\$N\$h\$&\$J(BHuffman\$BLZ\$,\$G\$-\$k!%(B

\$B\$7\$?\$,\$C\$F:G9bIQEY\$N5-9f\$O(B
encode-symbol     2\$B2s(B
element-of-set? n+1\$B2s(B

\$B:GDcIQEY\$N5-9f\$O(B
encode-symbol     n\$B2s(B
element-of-set? n-1\$B2s(B

```