SICP Study

2.3 Symbolic Data

2.3.1 Quotation

(define a 1)
(define b 2)

(list a b)
→ (1 2)

(list 'a 'b)
→ (a b)

(list 'a b)
→ (a 2)
(eq? 'a 'b)
→ #f

(eq? 'a 'a)
→ #t

2.3.2 Example: Symbolic Differentiation

Symbolic differentiation is of special historical significance in Lisp. It was one of the motivating examples behind the development of a computer language for symbol manipulation. (Section 2.3.2)

The differentiation program with abstract data

Procedure Result
(variable? e) Is e a variable?
(same-variable? v1 v2) Are v1 and v2 the same variable?
(sum? e) Is e a sum?
(addend e) Addend of the sum e
(augend e) Augend of the sum e
(make-sum a1 a2) Construct the sum of a1 and a2
(product? e) Is e a product?
(multiplier e) Multiplier of the product e
(multiplicand e) Multiplicand of the product e
(make-product m1 m2) Construct the product of m1 and m2
(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" exp))))

Representing algebraic expressions

2.3.3 Example: Representing Sets

There are a number of possible ways we could represent sets. A set is a collection of distinct objects. Our sets need to work with the following operations:

Procedure Result
(element-of-set? x s) Is x a member of the set s?
(adjoin-set x s) Set containing x and the elements of set s
(union-set s t) Set of elements that occur in either s or t
(intersection-set s t) Set of elements that occur in both s and t

Sets as unordered lists

Sets as ordered lists

Sets as binary trees

Sets and information retrieval

2.3.4 Example: Huffman Encoding Trees

Generating Huffman trees

Huffman gave an algorithm for constructing the best code for a given set of symbols and their relative frequencies:

  1. Begin with all symbols and their weights as isolated leaves.
  2. Form an internal node branching off to the two least frequent symbols.
  3. Repeat until all nodes are connected.

Representing Huffman trees

The decoding procedure

The following procedure decodes a list of bits using a Huffman 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" bit))))

Sets of weighted elements

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