2.5.2 · Combining data of different types

A generic operation can move values to a common representation.

A coercion table handles one known mixed pair, and a numeric tower raises integers to rationals and rationals to complex before a same-type operation.

Guiding question

How can generic arithmetic choose a common type without hiding failed coercions or looping between peer representations?

Distinguish an operation method from a coercion procedure
Retry a generic operation after one directed coercion
Raise values through an explicit integer–rational–complex hierarchy
Apply the arithmetic method only after both arguments share a type
Report a missing common type instead of guessing or recursing forever

The first program has one arithmetic method: add two rational contents. The integer–rational pair has no direct method, so apply-generic consults a separate coercion table, converts the integer to a rational with denominator 1, and retries. The coercion log makes that extra representation step visible. It also avoids attempting a same-type coercion when a same-type method is missing, which would otherwise repeat without making progress.

The second program replaces pairwise coercion choices with an ordered tower. rank identifies integer, rational, and complex levels. raise performs only the next upward conversion, and raise-to repeats it until both values reach the higher input rank. Integer plus rational therefore uses rational addition; rational plus complex uses complex addition after one raise; an unrelated polynomial tag has no rank and returns no-common-type. A tower reduces ambiguity for these ordered types, but it does not imply that every data type belongs in one hierarchy or that downward projection is always lossless.

SICP code2,373 of 1,048,576 UTF-8 bytes

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (make-integer value)
    (attach-tag 'integer value))
  (define (make-rational numerator denominator)
    (attach-tag 'rational (list numerator denominator)))
  (define (add-rational-contents left right)
    (make-rational
      (+ (* (car left) (cadr right))
         (* (car right) (cadr left)))
      (* (cadr left) (cadr right))))
  (define operation-table
    (list
      (cons (list 'add 'rational 'rational)
            add-rational-contents)))
  (define coercion-log '())
  (define (integer->rational object)
    (set! coercion-log
          (cons '(integer rational) coercion-log))
    (make-rational (contents object) 1))
  (define coercion-table
    (list
      (cons (list 'integer 'rational)
            integer->rational)))
  (define (apply-generic operation left right)
    (let* ((left-type (type-tag left))
           (right-type (type-tag right))
           (method
             (lookup-entry
               (list operation left-type right-type)
               operation-table)))
      (cond (method
             (method (contents left) (contents right)))
            ((eq? left-type right-type) 'no-method)
            (else
             (let ((left->right
                     (lookup-entry
                       (list left-type right-type)
                       coercion-table))
                   (right->left
                     (lookup-entry
                       (list right-type left-type)
                       coercion-table)))
               (cond (left->right
                      (apply-generic operation
                                     (left->right left)
                                     right))
                     (right->left
                      (apply-generic operation
                                     left
                                     (right->left right)))
                     (else 'no-method)))))))
  (define result
    (apply-generic 'add
                   (make-integer 3)
                   (make-rational 1 2)))
  (list result (reverse coercion-log)))

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (make-integer value)
    (attach-tag 'integer value))
  (define (make-rational numerator denominator)
    (attach-tag 'rational (list numerator denominator)))
  (define (add-rational-contents left right)
    (make-rational
      (+ (* (car left) (cadr right))
         (* (car right) (cadr left)))
      (* (cadr left) (cadr right))))
  (define operation-table
    (list
      (cons (list 'add 'rational 'rational)
            add-rational-contents)))
  (define coercion-log '())
  (define (integer->rational object)
    (set! coercion-log
          (cons '(integer rational) coercion-log))
    (make-rational (contents object) 1))
  (define coercion-table
    (list
      (cons (list 'integer 'rational)
            integer->rational)))
  (define (apply-generic operation left right)
    (let* ((left-type (type-tag left))
           (right-type (type-tag right))
           (method
             (lookup-entry
               (list operation left-type right-type)
               operation-table)))
      (cond (method
             (method (contents left) (contents right)))
            ((eq? left-type right-type) 'no-method)
            (else
             (let ((left->right
                     (lookup-entry
                       (list left-type right-type)
                       coercion-table))
                   (right->left
                     (lookup-entry
                       (list right-type left-type)
                       coercion-table)))
               (cond (left->right
                      (apply-generic operation
                                     (left->right left)
                                     right))
                     (right->left
                      (apply-generic operation
                                     left
                                     (right->left right)))
                     (else 'no-method)))))))
  (define result
    (apply-generic 'add
                   (make-integer 3)
                   (make-rational 1 2)))
  (list result (reverse coercion-log)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The coercion-table program returns ((rational 7 2) ((integer rational))). The tower program returns ((rational 5 2) (complex #t #t) no-common-type).

Trace focus

In the first run, find the failed mixed-type lookup, the integer-to-rational conversion, and the successful rational/rational retry. In the tower run, compare the one-step integer raise with the rational-to-complex raise, then locate the early no-common-type result before any arithmetic method runs for the polynomial tag. The trace records these explicit conversions, not a canonical hierarchy for every possible type system.

Try it yourself

Change the program and compare the result.

Add a real type between rational and complex. Raise a rational to real before complex, then predict how many raise steps integer plus complex requires.

Show hint

Update rank and make each raise move exactly one level. The generic operation should not need a new integer/complex pairwise coercion.

Complete this lesson

0 of 20 lessons complete in this chapter0%