\$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)
(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 (product? x)
(and (pair? x) (eq? (car x) '*)))
(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

\$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 (deriv exp var)
(cond ((number? exp) 0)
((variable? exp)
(if (same-variable? exp var) 1 0))
((sum? exp)
(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))
(cons '+ (cddr s))))
(define (multiplicand p)
(if (null? (cdddr 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 (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)
((> (length exp) 4)
(compile (cons (list (cadr exp) (compile (car exp))
(cdddr 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)))))

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

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 (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

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

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

(define (weight tree)
(if (leaf? tree)
(weight-leaf 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 (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

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

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

(define (weight tree)
(if (leaf? tree)
(weight-leaf 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 (make-code-tree left right)
(list left
right
(append (symbols left) (symbols right))
(+ (weight left) (weight right))))

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

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

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

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

(cond ((null? set) (list x))
((< (weight x) (weight (car set))) (cons x set))
(else (cons (car set)

(define (make-leaf-set pairs)
(if (null? pairs)
'()
(let ((pair (car pairs)))
(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

```