Symbolic Data

Abelson & Sussman · 1996 · SICP §2.3

Quotation lets programs manipulate symbols as data. Code that writes code. Symbolic differentiation shows the power: mathematical rules become pattern-matching functions. The derivative of a sum is the sum of derivatives — and that sentence is the program.

Quotation

The quote mark ' stops evaluation. 'a is the symbol a, not the value bound to a. symbol? tests whether something is a symbol. eq? tests whether two symbols are the same. This is the foundation: data that looks like code.

Scheme

; Quotation: ' prevents evaluation
(define a 42)
(display "a evaluates to: ") (display a) (newline)
(display "'a is the symbol: ") (display 'a) (newline)
(display "symbol? 'a: ") (display (symbol? 'a)) (newline)
(display "symbol? 42: ") (display (symbol? 42)) (newline)

; eq? compares symbols
(display "(eq? 'a 'a): ") (display (eq? 'a 'a)) (newline)
(display "(eq? 'a 'b): ") (display (eq? 'a 'b)) (newline)

; Quoted lists are literal data
(define expr '(+ 1 (* 2 3)))
(display "expression: ") (display expr) (newline)
(display "operator:   ") (display (car expr)) (newline)
(display "operands:   ") (display (cdr expr))

Symbolic differentiation

The derivative rules from calculus translate directly into code. Each rule is one clause in a conditional:

Constant: derivative is 0.
Variable (with respect to itself): derivative is 1.
Sum: derivative of a sum is the sum of derivatives.
Product: apply the product rule.

Scheme

; Symbolic differentiation
; Represent expressions as lists: (+ a b), (* a b)

(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (sum? x) (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (make-sum a b)
  (cond ((and (number? a) (= a 0)) b)
        ((and (number? b) (= b 0)) a)
        ((and (number? a) (number? b)) (+ a b))
        (else (list '+ a b))))

(define (product? x) (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (make-product a b)
  (cond ((and (number? a) (= a 0)) 0)
        ((and (number? b) (= b 0)) 0)
        ((and (number? a) (= a 1)) b)
        ((and (number? b) (= b 1)) a)
        ((and (number? a) (number? b)) (* a b))
        (else (list '* a 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))))))

; d/dx (x + 3) = 1
(display "d/dx (x+3):     ")
(display (deriv '(+ x 3) 'x)) (newline)

; d/dx (x * y) = y
(display "d/dx (x*y):     ")
(display (deriv '(* x y) 'x)) (newline)

; d/dx (x*y + x*3) = y + 3
(display "d/dx (x*y+x*3): ")
(display (deriv '(+ (* x y) (* x 3)) 'x))

; Symbolic differentiation
; Represent expressions as lists: (+ a b), (* a b)

(define (variable? x) (symbol? x))
(define (same-variable? v1 v2)
  (and (variable? v1) (variable? v2) (eq? v1 v2)))

(define (sum? x) (and (pair? x) (eq? (car x) '+)))
(define (addend s) (cadr s))
(define (augend s) (caddr s))
(define (make-sum a b)
  (cond ((and (number? a) (= a 0)) b)
        ((and (number? b) (= b 0)) a)
        ((and (number? a) (number? b)) (+ a b))
        (else (list '+ a b))))

(define (product? x) (and (pair? x) (eq? (car x) '*)))
(define (multiplier p) (cadr p))
(define (multiplicand p) (caddr p))
(define (make-product a b)
  (cond ((and (number? a) (= a 0)) 0)
        ((and (number? b) (= b 0)) 0)
        ((and (number? a) (= a 1)) b)
        ((and (number? b) (= b 1)) a)
        ((and (number? a) (number? b)) (* a b))
        (else (list '* a 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))))))

; d/dx (x + 3) = 1
(display "d/dx (x+3):     ")
(display (deriv '(+ x 3) 'x)) (newline)

; d/dx (x * y) = y
(display "d/dx (x*y):     ")
(display (deriv '(* x y) 'x)) (newline)

; d/dx (x*y + x*3) = y + 3
(display "d/dx (x*y+x*3): ")
(display (deriv '(+ (* x y) (* x 3)) 'x))

Python

# Symbolic differentiation with tuples
def deriv(exp, var):
    if isinstance(exp, (int, float)):
        return 0
    if isinstance(exp, str):
        return 1 if exp == var else 0
    op, a, b = exp[0], exp[1], exp[2]
    if op == '+':
        return make_sum(deriv(a, var), deriv(b, var))
    if op == '*':
        return make_sum(
            make_product(a, deriv(b, var)),
            make_product(deriv(a, var), b))

def make_sum(a, b):
    if a == 0: return b
    if b == 0: return a
    if isinstance(a, (int,float)) and isinstance(b, (int,float)):
        return a + b
    return ('+', a, b)

def make_product(a, b):
    if a == 0 or b == 0: return 0
    if a == 1: return b
    if b == 1: return a
    if isinstance(a, (int,float)) and isinstance(b, (int,float)):
        return a * b
    return ('*', a, b)

print(f"d/dx (x+3):     {deriv(('+', 'x', 3), 'x')}")
print(f"d/dx (x*y):     {deriv(('*', 'x', 'y'), 'x')}")
print(f"d/dx (x*y+x*3): {deriv(('+', ('*','x','y'), ('*','x',3)), 'x')}")

# Symbolic differentiation with tuples
def deriv(exp, var):
    if isinstance(exp, (int, float)):
        return 0
    if isinstance(exp, str):
        return 1 if exp == var else 0
    op, a, b = exp[0], exp[1], exp[2]
    if op == '+':
        return make_sum(deriv(a, var), deriv(b, var))
    if op == '*':
        return make_sum(
            make_product(a, deriv(b, var)),
            make_product(deriv(a, var), b))

def make_sum(a, b):
    if a == 0: return b
    if b == 0: return a
    if isinstance(a, (int,float)) and isinstance(b, (int,float)):
        return a + b
    return ('+', a, b)

def make_product(a, b):
    if a == 0 or b == 0: return 0
    if a == 1: return b
    if b == 1: return a
    if isinstance(a, (int,float)) and isinstance(b, (int,float)):
        return a * b
    return ('*', a, b)

print(f"d/dx (x+3):     {deriv(('+', 'x', 3), 'x')}")
print(f"d/dx (x*y):     {deriv(('*', 'x', 'y'), 'x')}")
print(f"d/dx (x*y+x*3): {deriv(('+', ('*','x','y'), ('*','x',3)), 'x')}")

Sets as unordered lists

A set is a collection with no duplicates. The simplest representation: an unordered list. element-of-set? scans the whole list — O(n). adjoin-set adds only if not present. Simple but slow.

Scheme

; Sets as unordered lists
(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((equal? x (car set)) #t)
        (else (element-of-set? x (cdr set)))))

(define (adjoin-set x set)
  (if (element-of-set? x set) set
      (cons x set)))

(define (intersection-set s1 s2)
  (cond ((null? s1) '())
        ((element-of-set? (car s1) s2)
         (cons (car s1) (intersection-set (cdr s1) s2)))
        (else (intersection-set (cdr s1) s2))))

(define s1 (list 1 2 3 4 5))
(define s2 (list 3 4 5 6 7))

(display "s1: ") (display s1) (newline)
(display "s2: ") (display s2) (newline)
(display "3 in s1? ") (display (element-of-set? 3 s1)) (newline)
(display "9 in s1? ") (display (element-of-set? 9 s1)) (newline)
(display "adjoin 6: ") (display (adjoin-set 6 s1)) (newline)
(display "adjoin 3: ") (display (adjoin-set 3 s1)) (newline)
(display "intersection: ") (display (intersection-set s1 s2))

Sets as binary trees

Ordered trees give O(log n) lookup. Each node holds an entry, a left subtree (smaller entries), and a right subtree (larger entries). The tree representation is another example of the abstraction barrier: the set interface stays the same, only the performance changes.

Scheme

; Binary search tree: (entry left right)
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (entry set)) #t)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        (else
         (element-of-set? x (right-branch set)))))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        (else
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

; Build a tree: 5, 3, 7, 1, 4
(define t (adjoin-set 4
  (adjoin-set 1
    (adjoin-set 7
      (adjoin-set 3
        (adjoin-set 5 '()))))))

(display "tree: ") (display t) (newline)
(display "3 in tree? ") (display (element-of-set? 3 t)) (newline)
(display "6 in tree? ") (display (element-of-set? 6 t))

; Binary search tree: (entry left right)
(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

(define (element-of-set? x set)
  (cond ((null? set) #f)
        ((= x (entry set)) #t)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        (else
         (element-of-set? x (right-branch set)))))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set)
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        (else
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

; Build a tree: 5, 3, 7, 1, 4
(define t (adjoin-set 4
  (adjoin-set 1
    (adjoin-set 7
      (adjoin-set 3
        (adjoin-set 5 '()))))))

(display "tree: ") (display t) (newline)
(display "3 in tree? ") (display (element-of-set? 3 t)) (newline)
(display "6 in tree? ") (display (element-of-set? 6 t))

Notation reference

Scheme	Python	Meaning
'x	"x"	Quoted symbol (data, not code)
(symbol? x)	isinstance(x, str)	Test if symbol
(eq? 'a 'b)	"a" == "b"	Symbol equality
'(+ x 3)	("+", "x", 3)	Quoted expression as data
(deriv exp var)	deriv(exp, var)	Symbolic derivative
(make-tree e l r)	Tree(e, l, r)	Binary tree node

Translation notes

Scheme's quotation is fundamental to the language: '(+ 1 2) is a list of three elements. Python has no equivalent — you build symbolic expressions from tuples or strings, which means the boundary between code and data is always explicit. This is the tradeoff: Lisp's homoiconicity makes metaprogramming natural at the cost of a less familiar syntax. Python's syntax is readable at the cost of making code-as-data awkward.

The simplification rules in make-sum and make-product are a preview of algebraic simplification. SICP keeps it minimal (0+x=x, 0*x=0, 1*x=x). A real computer algebra system would need hundreds of such rules.

Neighbors

SICP chapters

🪄 Chapter 5 — Hierarchical Data (the list/tree structures quotation builds on)
🪄 Chapter 7 — Multiple Representations (extending the idea of dispatch on type)

Foundations (Wikipedia)

Homoiconicity — code and data share the same representation
Symbolic computation — manipulating mathematical expressions as data
Binary search tree — the tree-based set representation

Ready for the real thing? Read SICP §2.3.

← Hierarchical Data by june.kim Multiple Representations · 7 of 22 →