Generic Operations

Abelson & Sussman · 1996 · SICP §2.5

A generic arithmetic system that works across number types. Coercion and type towers let you add a rational to a complex number without either type knowing about the other. The dispatch table from Chapter 7 scales to an entire algebra.

Generic arithmetic operations

We want (add x y) to work whether x and y are ordinary numbers, rationals, or complex. Each number type installs its own add, mul, etc. in the dispatch table. The generic operations look up the types and delegate.

Scheme

; Generic arithmetic: dispatch table + tagged data
(define table '())
(define (put op types proc)
  (set! table (cons (list op types proc) table)))
(define (get op types)
  (define (lookup entries)
    (cond ((null? entries) #f)
          ((and (equal? (car (car entries)) op)
                (equal? (cadr (car entries)) types))
           (caddr (car entries)))
          (else (lookup (cdr entries)))))
  (lookup table))

(define (attach-tag tag x) (cons tag x))
(define (type-tag x) (car x))
(define (contents x) (cdr x))

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error "No method" op type-tags)))))

; Generic operations
(define (add x y) (apply-generic 'add x y))
(define (mul x y) (apply-generic 'mul x y))

; Install ordinary numbers
(define (make-scheme-number n) (attach-tag 'scheme-number n))
(put 'add '(scheme-number scheme-number)
  (lambda (x y) (make-scheme-number (+ x y))))
(put 'mul '(scheme-number scheme-number)
  (lambda (x y) (make-scheme-number (* x y))))

; Install rational numbers
(define (make-rat n d) (attach-tag 'rational (cons n d)))
(define (numer r) (car r))
(define (denom r) (cdr r))
(put 'add '(rational rational)
  (lambda (x y)
    (make-rat (+ (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y)))))
(put 'mul '(rational rational)
  (lambda (x y)
    (make-rat (* (numer x) (numer y))
              (* (denom x) (denom y)))))

; Test
(define a (make-scheme-number 3))
(define b (make-scheme-number 4))
(display "3 + 4 = ") (display (add a b)) (newline)
(display "3 * 4 = ") (display (mul a b)) (newline)

(define r1 (make-rat 1 3))
(define r2 (make-rat 1 4))
(display "1/3 + 1/4 = ") (display (add r1 r2)) (newline)
(display "1/3 * 1/4 = ") (display (mul r1 r2))

; Generic arithmetic: dispatch table + tagged data
(define table '())
(define (put op types proc)
  (set! table (cons (list op types proc) table)))
(define (get op types)
  (define (lookup entries)
    (cond ((null? entries) #f)
          ((and (equal? (car (car entries)) op)
                (equal? (cadr (car entries)) types))
           (caddr (car entries)))
          (else (lookup (cdr entries)))))
  (lookup table))

(define (attach-tag tag x) (cons tag x))
(define (type-tag x) (car x))
(define (contents x) (cdr x))

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (error "No method" op type-tags)))))

; Generic operations
(define (add x y) (apply-generic 'add x y))
(define (mul x y) (apply-generic 'mul x y))

; Install ordinary numbers
(define (make-scheme-number n) (attach-tag 'scheme-number n))
(put 'add '(scheme-number scheme-number)
  (lambda (x y) (make-scheme-number (+ x y))))
(put 'mul '(scheme-number scheme-number)
  (lambda (x y) (make-scheme-number (* x y))))

; Install rational numbers
(define (make-rat n d) (attach-tag 'rational (cons n d)))
(define (numer r) (car r))
(define (denom r) (cdr r))
(put 'add '(rational rational)
  (lambda (x y)
    (make-rat (+ (* (numer x) (denom y))
                 (* (numer y) (denom x)))
              (* (denom x) (denom y)))))
(put 'mul '(rational rational)
  (lambda (x y)
    (make-rat (* (numer x) (numer y))
              (* (denom x) (denom y)))))

; Test
(define a (make-scheme-number 3))
(define b (make-scheme-number 4))
(display "3 + 4 = ") (display (add a b)) (newline)
(display "3 * 4 = ") (display (mul a b)) (newline)

(define r1 (make-rat 1 3))
(define r2 (make-rat 1 4))
(display "1/3 + 1/4 = ") (display (add r1 r2)) (newline)
(display "1/3 * 1/4 = ") (display (mul r1 r2))

Python

# Generic arithmetic with dispatch dict
dispatch = {}

def put(op, types, fn): dispatch[(op, tuple(types))] = fn
def get(op, types): return dispatch.get((op, tuple(types)))

class Tagged:
    def __init__(self, tag, val): self.tag, self.val = tag, val
    def __repr__(self): return f"({self.tag} {self.val})"

def apply_generic(op, *args):
    types = [a.tag for a in args]
    fn = get(op, types)
    if fn: return fn(*[a.val for a in args])
    raise Exception(f"No method: {op} {types}")

def add(x, y): return apply_generic('add', x, y)
def mul(x, y): return apply_generic('mul', x, y)

# Ordinary numbers
def make_num(n): return Tagged('num', n)
put('add', ['num','num'], lambda x,y: make_num(x+y))
put('mul', ['num','num'], lambda x,y: make_num(x*y))

# Rationals
from fractions import Fraction
def make_rat(n,d): return Tagged('rat', Fraction(n,d))
put('add', ['rat','rat'], lambda x,y: Tagged('rat', x+y))
put('mul', ['rat','rat'], lambda x,y: Tagged('rat', x*y))

print(f"3 + 4 = {add(make_num(3), make_num(4))}")
print(f"3 * 4 = {mul(make_num(3), make_num(4))}")
print(f"1/3 + 1/4 = {add(make_rat(1,3), make_rat(1,4))}")
print(f"1/3 * 1/4 = {mul(make_rat(1,3), make_rat(1,4))}")

# Generic arithmetic with dispatch dict
dispatch = {}

def put(op, types, fn): dispatch[(op, tuple(types))] = fn
def get(op, types): return dispatch.get((op, tuple(types)))

class Tagged:
    def __init__(self, tag, val): self.tag, self.val = tag, val
    def __repr__(self): return f"({self.tag} {self.val})"

def apply_generic(op, *args):
    types = [a.tag for a in args]
    fn = get(op, types)
    if fn: return fn(*[a.val for a in args])
    raise Exception(f"No method: {op} {types}")

def add(x, y): return apply_generic('add', x, y)
def mul(x, y): return apply_generic('mul', x, y)

# Ordinary numbers
def make_num(n): return Tagged('num', n)
put('add', ['num','num'], lambda x,y: make_num(x+y))
put('mul', ['num','num'], lambda x,y: make_num(x*y))

# Rationals
from fractions import Fraction
def make_rat(n,d): return Tagged('rat', Fraction(n,d))
put('add', ['rat','rat'], lambda x,y: Tagged('rat', x+y))
put('mul', ['rat','rat'], lambda x,y: Tagged('rat', x*y))

print(f"3 + 4 = {add(make_num(3), make_num(4))}")
print(f"3 * 4 = {mul(make_num(3), make_num(4))}")
print(f"1/3 + 1/4 = {add(make_rat(1,3), make_rat(1,4))}")
print(f"1/3 * 1/4 = {mul(make_rat(1,3), make_rat(1,4))}")

Combining data of different types

What about (add 3 1/4)? The types don't match. Coercion converts one type to the other. A coercion table maps (from-type, to-type) to a conversion function. When apply-generic finds no direct match, it tries coercing one argument to the other's type.

Scheme

; Coercion: converting between types
; We'll simulate with a simple number + rational system

(define coercion-table '())
(define (put-coercion from to proc)
  (set! coercion-table (cons (list from to proc) coercion-table)))
(define (get-coercion from to)
  (define (lookup entries)
    (cond ((null? entries) #f)
          ((and (eq? (car (car entries)) from)
                (eq? (cadr (car entries)) to))
           (caddr (car entries)))
          (else (lookup (cdr entries)))))
  (lookup coercion-table))

; Coerce scheme-number to rational: n -> n/1
(put-coercion 'scheme-number 'rational
  (lambda (n) (cons 'rational (cons n 1))))

; Demonstrate coercion lookup
(define coerce (get-coercion 'scheme-number 'rational))
(define n (cons 'scheme-number 3))
(display "original: ") (display n) (newline)
(display "coerced:  ") (display (coerce n)) (newline)

; A smarter apply-generic would try:
; 1. Direct lookup (same types)
; 2. Coerce arg1 to type2, retry
; 3. Coerce arg2 to type1, retry
; 4. Give up
(display "Strategy: try direct, then coerce left, then coerce right")

; Coercion: converting between types
; We'll simulate with a simple number + rational system

(define coercion-table '())
(define (put-coercion from to proc)
  (set! coercion-table (cons (list from to proc) coercion-table)))
(define (get-coercion from to)
  (define (lookup entries)
    (cond ((null? entries) #f)
          ((and (eq? (car (car entries)) from)
                (eq? (cadr (car entries)) to))
           (caddr (car entries)))
          (else (lookup (cdr entries)))))
  (lookup coercion-table))

; Coerce scheme-number to rational: n -> n/1
(put-coercion 'scheme-number 'rational
  (lambda (n) (cons 'rational (cons n 1))))

; Demonstrate coercion lookup
(define coerce (get-coercion 'scheme-number 'rational))
(define n (cons 'scheme-number 3))
(display "original: ") (display n) (newline)
(display "coerced:  ") (display (coerce n)) (newline)

; A smarter apply-generic would try:
; 1. Direct lookup (same types)
; 2. Coerce arg1 to type2, retry
; 3. Coerce arg2 to type1, retry
; 4. Give up
(display "Strategy: try direct, then coerce left, then coerce right")

Type towers and hierarchies

Types form a tower: integer < rational < real < complex. Each type can be "raised" to the next level. When types don't match, raise the lower one until they do. This is simpler than explicit coercion between every pair: you only need n-1 raise functions instead of n(n-1) coercions.

Scheme

; Type tower: integer < rational < real < complex
; Each type knows how to raise itself one level

(define (raise-integer n)
  (list 'rational n 1))  ; n -> n/1

(define (raise-rational r)
  (list 'real (exact->inexact (/ (cadr r) (caddr r)))))

(define (raise-real x)
  (list 'complex (cadr x) 0))  ; x -> x + 0i

; Tower position
(define (tower-level type)
  (cond ((eq? type 'integer) 0)
        ((eq? type 'rational) 1)
        ((eq? type 'real) 2)
        ((eq? type 'complex) 3)))

; Raise a value to target level
(define (raise-to val target-type)
  (let ((current (car val)))
    (cond ((eq? current target-type) val)
          ((eq? current 'integer)
           (raise-to (raise-integer (cadr val)) target-type))
          ((eq? current 'rational)
           (raise-to (raise-rational val) target-type))
          ((eq? current 'real)
           (raise-to (raise-real val) target-type)))))

; Demo: raise integer 3 through the tower
(define n (list 'integer 3))
(display "integer:  ") (display n) (newline)
(display "rational: ") (display (raise-to n 'rational)) (newline)
(display "real:     ") (display (raise-to n 'real)) (newline)
(display "complex:  ") (display (raise-to n 'complex))

; Type tower: integer < rational < real < complex
; Each type knows how to raise itself one level

(define (raise-integer n)
  (list 'rational n 1))  ; n -> n/1

(define (raise-rational r)
  (list 'real (exact->inexact (/ (cadr r) (caddr r)))))

(define (raise-real x)
  (list 'complex (cadr x) 0))  ; x -> x + 0i

; Tower position
(define (tower-level type)
  (cond ((eq? type 'integer) 0)
        ((eq? type 'rational) 1)
        ((eq? type 'real) 2)
        ((eq? type 'complex) 3)))

; Raise a value to target level
(define (raise-to val target-type)
  (let ((current (car val)))
    (cond ((eq? current target-type) val)
          ((eq? current 'integer)
           (raise-to (raise-integer (cadr val)) target-type))
          ((eq? current 'rational)
           (raise-to (raise-rational val) target-type))
          ((eq? current 'real)
           (raise-to (raise-real val) target-type)))))

; Demo: raise integer 3 through the tower
(define n (list 'integer 3))
(display "integer:  ") (display n) (newline)
(display "rational: ") (display (raise-to n 'rational)) (newline)
(display "real:     ") (display (raise-to n 'real)) (newline)
(display "complex:  ") (display (raise-to n 'complex))

Polynomial arithmetic

The generic arithmetic system is extensible enough to add polynomials. A polynomial is a variable plus a list of terms. add-poly adds matching terms. Polynomial coefficients can themselves be polynomials (or rationals, or complex numbers), because the coefficient arithmetic uses the same generic add and mul.

Scheme

; Simplified polynomial arithmetic
; A poly is (variable . term-list)
; A term-list is ((order coeff) ...)

(define (make-poly var terms) (list 'poly var terms))
(define (poly-var p) (cadr p))
(define (poly-terms p) (caddr p))

; Add two term lists (same variable, ordered by descending order)
(define (add-terms L1 L2)
  (cond ((null? L1) L2)
        ((null? L2) L1)
        (else
         (let ((t1 (car L1)) (t2 (car L2)))
           (let ((o1 (car t1)) (o2 (car t2)))
             (cond ((> o1 o2)
                    (cons t1 (add-terms (cdr L1) L2)))
                   ((< o1 o2)
                    (cons t2 (add-terms L1 (cdr L2))))
                   (else
                    (cons (list o1 (+ (cadr t1) (cadr t2)))
                          (add-terms (cdr L1) (cdr L2))))))))))

(define (add-poly p1 p2)
  (make-poly (poly-var p1)
             (add-terms (poly-terms p1) (poly-terms p2))))

; Display a polynomial
(define (show-poly p)
  (define (show-term t)
    (let ((o (car t)) (c (cadr t)))
      (cond ((= o 0) (number->string c))
            ((= o 1) (string-append (number->string c) (symbol->string (poly-var p))))
            (else (string-append (number->string c)
                    (symbol->string (poly-var p)) "^"
                    (number->string o))))))
  (define (join terms)
    (if (null? (cdr terms))
        (show-term (car terms))
        (string-append (show-term (car terms)) " + " (join (cdr terms)))))
  (join (poly-terms p)))

; p1 = 2x^2 + 3x + 1
(define p1 (make-poly 'x '((2 2) (1 3) (0 1))))
; p2 = x^2 + 5
(define p2 (make-poly 'x '((2 1) (0 5))))

(display "p1:      ") (display (show-poly p1)) (newline)
(display "p2:      ") (display (show-poly p2)) (newline)
(display "p1 + p2: ") (display (show-poly (add-poly p1 p2)))

; Simplified polynomial arithmetic
; A poly is (variable . term-list)
; A term-list is ((order coeff) ...)

(define (make-poly var terms) (list 'poly var terms))
(define (poly-var p) (cadr p))
(define (poly-terms p) (caddr p))

; Add two term lists (same variable, ordered by descending order)
(define (add-terms L1 L2)
  (cond ((null? L1) L2)
        ((null? L2) L1)
        (else
         (let ((t1 (car L1)) (t2 (car L2)))
           (let ((o1 (car t1)) (o2 (car t2)))
             (cond ((> o1 o2)
                    (cons t1 (add-terms (cdr L1) L2)))
                   ((< o1 o2)
                    (cons t2 (add-terms L1 (cdr L2))))
                   (else
                    (cons (list o1 (+ (cadr t1) (cadr t2)))
                          (add-terms (cdr L1) (cdr L2))))))))))

(define (add-poly p1 p2)
  (make-poly (poly-var p1)
             (add-terms (poly-terms p1) (poly-terms p2))))

; Display a polynomial
(define (show-poly p)
  (define (show-term t)
    (let ((o (car t)) (c (cadr t)))
      (cond ((= o 0) (number->string c))
            ((= o 1) (string-append (number->string c) (symbol->string (poly-var p))))
            (else (string-append (number->string c)
                    (symbol->string (poly-var p)) "^"
                    (number->string o))))))
  (define (join terms)
    (if (null? (cdr terms))
        (show-term (car terms))
        (string-append (show-term (car terms)) " + " (join (cdr terms)))))
  (join (poly-terms p)))

; p1 = 2x^2 + 3x + 1
(define p1 (make-poly 'x '((2 2) (1 3) (0 1))))
; p2 = x^2 + 5
(define p2 (make-poly 'x '((2 1) (0 5))))

(display "p1:      ") (display (show-poly p1)) (newline)
(display "p2:      ") (display (show-poly p2)) (newline)
(display "p1 + p2: ") (display (show-poly (add-poly p1 p2)))

Notation reference

Scheme	Python	Meaning
(add x y)	add(x, y) / x + y	Generic addition
(apply-generic op . args)	apply_generic(op, *args)	Dispatch on all argument types
(put-coercion from to proc)	coercion[(from, to)] = fn	Register type conversion
(raise x)	raise_value(x, target)	Move up the type tower
(make-poly var terms)	Poly(var, terms)	Polynomial constructor
(add-poly p1 p2)	p1 + p2	Add polynomials

Translation notes

Python's __add__, __mul__ and friends are exactly SICP's generic operations, baked into the language. The dispatch table is the method resolution order (MRO). Coercion is __radd__ and __coerce__ (deprecated but instructive). The type tower is Python's numeric abstract base classes: Integral < Rational < Real < Complex in the numbers module.

The polynomial example shows the real payoff: because polynomial coefficients use the same generic arithmetic, you get polynomials over rationals, polynomials over complex numbers, and even polynomials over polynomials (multivariate) for free. This is the algebraic structure that type classes in Haskell and protocols in Swift formalize.

Neighbors

SICP chapters

🪄 Chapter 7 — Multiple Representations (dispatch tables introduced)
🪄 Chapter 9 — Assignment & State (mutation changes everything)

Category theory connections

🍞 Milewski Ch.4 — Kleisli categories: type lifting via monadic bind is the categorical version of coercion

Foundations (Wikipedia)

Type coercion — implicit conversion between types
Algebraic data type — the type theory behind tagged unions

Ready for the real thing? Read SICP §2.5.

← Multiple Representations by june.kim Assignment & State · 9 of 22 →