Multiple Representations

Abelson & Sussman · 1996 · SICP §2.4

The same abstract data can have multiple concrete representations. Tagged data and dispatch tables let representations coexist without knowing about each other. This is the birth of extensibility: adding a new representation requires no changes to existing code.

Representations for complex numbers

A complex number can be stored as rectangular (real, imaginary) or polar (magnitude, angle). Both are valid. The operations real-part, imag-part, magnitude, angle define the abstract interface. Two teams can implement independently.

Scheme

; Two representations of complex numbers
; Rectangular: (real-part, imag-part) stored directly
(define (make-from-real-imag-rect x y) (cons x y))
(define (real-part-rect z) (car z))
(define (imag-part-rect z) (cdr z))
(define (magnitude-rect z)
  (sqrt (+ (* (real-part-rect z) (real-part-rect z))
           (* (imag-part-rect z) (imag-part-rect z)))))

; Polar: (magnitude, angle) stored directly
(define (make-from-mag-ang-polar r a) (cons r a))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))
(define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z))))

; Same number, two representations
(define z-rect (make-from-real-imag-rect 3 4))
(define z-polar (make-from-mag-ang-polar 5 0.9272952))

(display "Rectangular: real=")
(display (real-part-rect z-rect))
(display " imag=") (display (imag-part-rect z-rect))
(display " mag=") (display (magnitude-rect z-rect)) (newline)

(display "Polar:       real=")
(display (real-part-polar z-polar))
(display " imag=") (display (imag-part-polar z-polar))
(display " mag=") (display (magnitude-polar z-polar))

; Two representations of complex numbers
; Rectangular: (real-part, imag-part) stored directly
(define (make-from-real-imag-rect x y) (cons x y))
(define (real-part-rect z) (car z))
(define (imag-part-rect z) (cdr z))
(define (magnitude-rect z)
  (sqrt (+ (* (real-part-rect z) (real-part-rect z))
           (* (imag-part-rect z) (imag-part-rect z)))))

; Polar: (magnitude, angle) stored directly
(define (make-from-mag-ang-polar r a) (cons r a))
(define (magnitude-polar z) (car z))
(define (angle-polar z) (cdr z))
(define (real-part-polar z) (* (magnitude-polar z) (cos (angle-polar z))))
(define (imag-part-polar z) (* (magnitude-polar z) (sin (angle-polar z))))

; Same number, two representations
(define z-rect (make-from-real-imag-rect 3 4))
(define z-polar (make-from-mag-ang-polar 5 0.9272952))

(display "Rectangular: real=")
(display (real-part-rect z-rect))
(display " imag=") (display (imag-part-rect z-rect))
(display " mag=") (display (magnitude-rect z-rect)) (newline)

(display "Polar:       real=")
(display (real-part-polar z-polar))
(display " imag=") (display (imag-part-polar z-polar))
(display " mag=") (display (magnitude-polar z-polar))

Tagged data

Problem: both representations are just pairs. How does a generic operation know which one it's looking at? Answer: attach a type tag. (attach-tag 'rectangular (cons 3 4)) produces (rectangular 3 . 4). The generic operations dispatch on the tag.

Scheme

; Tagged data: attach a type symbol to each datum
(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum) (car datum))
(define (contents datum) (cdr datum))

; Tagged constructors
(define (make-rect x y) (attach-tag 'rectangular (cons x y)))
(define (make-polar r a) (attach-tag 'polar (cons r a)))

; Generic selectors — dispatch on tag
(define (real-part z)
  (cond ((eq? (type-tag z) 'rectangular) (car (contents z)))
        ((eq? (type-tag z) 'polar)
         (* (car (contents z)) (cos (cdr (contents z)))))))

(define (magnitude z)
  (cond ((eq? (type-tag z) 'rectangular)
         (sqrt (+ (* (car (contents z)) (car (contents z)))
                  (* (cdr (contents z)) (cdr (contents z))))))
        ((eq? (type-tag z) 'polar) (car (contents z)))))

(define z1 (make-rect 3 4))
(define z2 (make-polar 5 0.9272952))

(display "z1 tag: ") (display (type-tag z1)) (newline)
(display "z2 tag: ") (display (type-tag z2)) (newline)
(display "z1 real-part: ") (display (real-part z1)) (newline)
(display "z2 real-part: ") (display (real-part z2)) (newline)
(display "z1 magnitude: ") (display (magnitude z1)) (newline)
(display "z2 magnitude: ") (display (magnitude z2))

; Tagged data: attach a type symbol to each datum
(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum) (car datum))
(define (contents datum) (cdr datum))

; Tagged constructors
(define (make-rect x y) (attach-tag 'rectangular (cons x y)))
(define (make-polar r a) (attach-tag 'polar (cons r a)))

; Generic selectors — dispatch on tag
(define (real-part z)
  (cond ((eq? (type-tag z) 'rectangular) (car (contents z)))
        ((eq? (type-tag z) 'polar)
         (* (car (contents z)) (cos (cdr (contents z)))))))

(define (magnitude z)
  (cond ((eq? (type-tag z) 'rectangular)
         (sqrt (+ (* (car (contents z)) (car (contents z)))
                  (* (cdr (contents z)) (cdr (contents z))))))
        ((eq? (type-tag z) 'polar) (car (contents z)))))

(define z1 (make-rect 3 4))
(define z2 (make-polar 5 0.9272952))

(display "z1 tag: ") (display (type-tag z1)) (newline)
(display "z2 tag: ") (display (type-tag z2)) (newline)
(display "z1 real-part: ") (display (real-part z1)) (newline)
(display "z2 real-part: ") (display (real-part z2)) (newline)
(display "z1 magnitude: ") (display (magnitude z1)) (newline)
(display "z2 magnitude: ") (display (magnitude z2))

Data-directed programming

The conditional dispatch above doesn't scale: adding a new representation means editing every generic operation. Data-directed programming uses a two-dimensional table indexed by (operation, type). Each representation installs its own procedures. The generic operation just looks up the table.

Scheme

; Data-directed programming: a dispatch table
; Simulated with an association list of ((op type) . proc)

(define table '())

(define (put op type proc)
  (set! table (cons (list op type proc) table)))

(define (get op type)
  (define (lookup entries)
    (cond ((null? entries) #f)
          ((and (eq? (car (car entries)) op)
                (eq? (cadr (car entries)) type))
           (caddr (car entries)))
          (else (lookup (cdr entries)))))
  (lookup table))

; Install rectangular package
(put 'real-part 'rectangular (lambda (z) (car z)))
(put 'imag-part 'rectangular (lambda (z) (cdr z)))
(put 'magnitude 'rectangular
  (lambda (z) (sqrt (+ (* (car z) (car z))
                       (* (cdr z) (cdr z))))))

; Install polar package
(put 'real-part 'polar
  (lambda (z) (* (car z) (cos (cdr z)))))
(put 'imag-part 'polar
  (lambda (z) (* (car z) (sin (cdr z)))))
(put 'magnitude 'polar (lambda (z) (car z)))

; Generic apply
(define (apply-generic op datum)
  (let ((proc (get op (car datum))))
    (if proc
        (proc (cdr datum))
        (error "No method" op (car datum)))))

; Use it
(define z1 (cons 'rectangular (cons 3 4)))
(define z2 (cons 'polar (cons 5 0.9272952)))

(display "z1 real-part: ") (display (apply-generic 'real-part z1)) (newline)
(display "z2 real-part: ") (display (apply-generic 'real-part z2)) (newline)
(display "z1 magnitude: ") (display (apply-generic 'magnitude z1)) (newline)
(display "z2 magnitude: ") (display (apply-generic 'magnitude z2))

; Data-directed programming: a dispatch table
; Simulated with an association list of ((op type) . proc)

(define table '())

(define (put op type proc)
  (set! table (cons (list op type proc) table)))

(define (get op type)
  (define (lookup entries)
    (cond ((null? entries) #f)
          ((and (eq? (car (car entries)) op)
                (eq? (cadr (car entries)) type))
           (caddr (car entries)))
          (else (lookup (cdr entries)))))
  (lookup table))

; Install rectangular package
(put 'real-part 'rectangular (lambda (z) (car z)))
(put 'imag-part 'rectangular (lambda (z) (cdr z)))
(put 'magnitude 'rectangular
  (lambda (z) (sqrt (+ (* (car z) (car z))
                       (* (cdr z) (cdr z))))))

; Install polar package
(put 'real-part 'polar
  (lambda (z) (* (car z) (cos (cdr z)))))
(put 'imag-part 'polar
  (lambda (z) (* (car z) (sin (cdr z)))))
(put 'magnitude 'polar (lambda (z) (car z)))

; Generic apply
(define (apply-generic op datum)
  (let ((proc (get op (car datum))))
    (if proc
        (proc (cdr datum))
        (error "No method" op (car datum)))))

; Use it
(define z1 (cons 'rectangular (cons 3 4)))
(define z2 (cons 'polar (cons 5 0.9272952)))

(display "z1 real-part: ") (display (apply-generic 'real-part z1)) (newline)
(display "z2 real-part: ") (display (apply-generic 'real-part z2)) (newline)
(display "z1 magnitude: ") (display (apply-generic 'magnitude z1)) (newline)
(display "z2 magnitude: ") (display (apply-generic 'magnitude z2))

Python

import math

# Dispatch table: dict of (op, type) -> function
dispatch = {}

def put(op, typ, fn):
    dispatch[(op, typ)] = fn

def get(op, typ):
    return dispatch.get((op, typ))

# Rectangular package
put('real_part', 'rectangular', lambda z: z.get('x'))
put('imag_part', 'rectangular', lambda z: z.get('y'))
put('magnitude', 'rectangular',
    lambda z: math.sqrt(z.get('x')**2 + z.get('y')**2))

# Polar package
put('real_part', 'polar', lambda z: z.get('r') * math.cos(z.get('a')))
put('imag_part', 'polar', lambda z: z.get('r') * math.sin(z.get('a')))
put('magnitude', 'polar', lambda z: z.get('r'))

def apply_generic(op, datum):
    fn = get(op, datum.get('type'))
    return fn(datum) if fn else "No method: " + op

z1 = dict(type='rectangular', x=3, y=4)
z2 = dict(type='polar', r=5, a=0.9272952)

print("z1 real_part: " + str(apply_generic('real_part', z1)))
print("z2 real_part: " + format(apply_generic('real_part', z2), '.6f'))
print("z1 magnitude: " + str(apply_generic('magnitude', z1)))
print("z2 magnitude: " + str(apply_generic('magnitude', z2)))

import math

# Dispatch table: dict of (op, type) -> function
dispatch = {}

def put(op, typ, fn):
    dispatch[(op, typ)] = fn

def get(op, typ):
    return dispatch.get((op, typ))

# Rectangular package
put('real_part', 'rectangular', lambda z: z.get('x'))
put('imag_part', 'rectangular', lambda z: z.get('y'))
put('magnitude', 'rectangular',
    lambda z: math.sqrt(z.get('x')**2 + z.get('y')**2))

# Polar package
put('real_part', 'polar', lambda z: z.get('r') * math.cos(z.get('a')))
put('imag_part', 'polar', lambda z: z.get('r') * math.sin(z.get('a')))
put('magnitude', 'polar', lambda z: z.get('r'))

def apply_generic(op, datum):
    fn = get(op, datum.get('type'))
    return fn(datum) if fn else "No method: " + op

z1 = dict(type='rectangular', x=3, y=4)
z2 = dict(type='polar', r=5, a=0.9272952)

print("z1 real_part: " + str(apply_generic('real_part', z1)))
print("z2 real_part: " + format(apply_generic('real_part', z2), '.6f'))
print("z1 magnitude: " + str(apply_generic('magnitude', z1)))
print("z2 magnitude: " + str(apply_generic('magnitude', z2)))

Message passing

Instead of a central dispatch table, each object carries its own dispatch. You "send a message" (the operation name) to the object, and it returns the right value. This is what object-oriented programming looks like from first principles: an object is a closure that dispatches on a symbol.

Scheme

; Message passing: the object IS the dispatch
(define (make-from-real-imag x y)
  (lambda (op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (* x x) (* y y))))
          ((eq? op 'angle) (atan y x))
          (else (error "Unknown op" op)))))

(define (make-from-mag-ang r a)
  (lambda (op)
    (cond ((eq? op 'magnitude) r)
          ((eq? op 'angle) a)
          ((eq? op 'real-part) (* r (cos a)))
          ((eq? op 'imag-part) (* r (sin a)))
          (else (error "Unknown op" op)))))

; Generic apply = just call the object with the op
(define (apply-generic op obj) (obj op))

(define z1 (make-from-real-imag 3 4))
(define z2 (make-from-mag-ang 5 0.9272952))

(display "z1 real-part: ") (display (apply-generic 'real-part z1)) (newline)
(display "z1 magnitude: ") (display (apply-generic 'magnitude z1)) (newline)
(display "z2 real-part: ") (display (apply-generic 'real-part z2)) (newline)
(display "z2 magnitude: ") (display (apply-generic 'magnitude z2))

; Message passing: the object IS the dispatch
(define (make-from-real-imag x y)
  (lambda (op)
    (cond ((eq? op 'real-part) x)
          ((eq? op 'imag-part) y)
          ((eq? op 'magnitude)
           (sqrt (+ (* x x) (* y y))))
          ((eq? op 'angle) (atan y x))
          (else (error "Unknown op" op)))))

(define (make-from-mag-ang r a)
  (lambda (op)
    (cond ((eq? op 'magnitude) r)
          ((eq? op 'angle) a)
          ((eq? op 'real-part) (* r (cos a)))
          ((eq? op 'imag-part) (* r (sin a)))
          (else (error "Unknown op" op)))))

; Generic apply = just call the object with the op
(define (apply-generic op obj) (obj op))

(define z1 (make-from-real-imag 3 4))
(define z2 (make-from-mag-ang 5 0.9272952))

(display "z1 real-part: ") (display (apply-generic 'real-part z1)) (newline)
(display "z1 magnitude: ") (display (apply-generic 'magnitude z1)) (newline)
(display "z2 real-part: ") (display (apply-generic 'real-part z2)) (newline)
(display "z2 magnitude: ") (display (apply-generic 'magnitude z2))

Notation reference

Scheme	Python	Meaning
(attach-tag 'type data)	dict(type=..., ...)	Tag data with its type
(type-tag datum)	datum.get('type')	Extract the type tag
(contents datum)	datum (minus type key)	Extract the payload
(put op type proc)	dispatch[(op, type)] = fn	Install in dispatch table
(get op type)	dispatch.get((op, type))	Look up dispatch table
(apply-generic op datum)	apply_generic(op, datum)	Dispatch on type tag

Translation notes

The three dispatch strategies — explicit conditional, dispatch table, message passing — correspond directly to patterns in mainstream OOP. Explicit conditionals are isinstance checks. Dispatch tables are the visitor pattern. Message passing is virtual method dispatch. Python classes combine all three: isinstance for ad-hoc checks, __init_subclass__ for registry patterns, and regular methods for message passing.

SICP's insight is that these are all the same mechanism (dispatch on type) organized differently. Data-directed programming is the most extensible: new types and new operations can be added independently. This is exactly the expression problem that haunts every language design.

Neighbors

SICP chapters

🪄 Chapter 6 — Symbolic Data (pattern matching on expression types)
🪄 Chapter 8 — Generic Operations (extending dispatch to arithmetic across types)

Foundations (Wikipedia)

Multiple dispatch — generalizing single dispatch to multiple arguments
Dynamic dispatch — runtime selection of method implementations
Polymorphism — the broader concept behind multiple representations

Ready for the real thing? Read SICP §2.4.

← Symbolic Data by june.kim Generic Operations · 8 of 22 →