Spring 97 - Michael Elhadad

Principles of Programming Languages (201-1289101)

Notes on Class 14 -- Coercion

The basis of the implementation of a system supporting generic functions is:
  1. To explicitly represent the types of the parameters. We use the functions attach-tag, tag-type and contents for this purpose. When a function has several parameters, the list of the types of its parameters is called its signature.
  2. To explicitly encode the table linking a generic functions to its specific instances for each combination of types. We use the functions (put op signature specific-function) and (get op signature) for this purpose.
The center of the generic function implementation is the function apply-generic which dispatches a call to a generic function to the specific instance that matches its parameters:
(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 for these types -- APPLY GENERIC"
               (list op type-tags))))))
If a system includes types with no relation among them, the best we can do to define generic operations that work on combinations of different types is to define a specific instance of the generic operation for each possible signature and to insert it into the table.

This is achieved using entries of the following form:

(define (add-complex-to-number z x)
  (make-complex-rect (+ (complex-x z) x) (complex-y z)))

It is, however, often the case that relations among types exist. The basic relation is that a type is a supertype of another. In this case we want to exploit the relation to reduce the number of specific operations to implement.

This is done using the mechanism of coercion also known as type casting.

In general, this can be solved by using a table of coercion procedures, that explicitly indicates how an element of type T1 can be converted to be an element of type T2 for every pair of types (T1, T2). Thus, we may need as many as n2-n coercion functions to be able to convert from any type to any other type in a system including n distinct types.

Assuming the existence of the functions (put-coercion t1 t2 coercion-function) and (get-coercion t1 t2) to manage the coercion table, we can now extend apply-generic to make it try to manage coercion automatically: if the two parameters of a generic function are of different types, and no specific instance of the function is found for this signature, apply-generic tries to coerce the two parameters to be of the same type:

(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))
        (if (= (length args) 2)
          (let ((type1 (car type-tags))
                (type2 (cadr type-tags))
                (a1 (car args))
                (a2 (cadr args)))
            (let ((t1->t2 (get-coercion type1 type2))
                  (t2->t1 (get-coercion type2 type1)))
              (cond (t1->t2
                      (apply-generic op (t1->t2 a1) a2))
                      (apply-generic op a1 (t2->t1 a2)))
                      (error "No method for these types" 
                             (list op type-tags))))))
          (error "No method for these types" (list op type-tags)))))))
Then, let us examine the simplest case where a chain of super-type relations exist among all types in the system. For example, complex is a supertype of real is a supertype of rational is a supertype of integer. In this case, we can reduce the number of coercion functions required in the system.


  1. Make the system additive
  2. Work also when generic functions are not only defined for 2 arguments or for 2 arguments of the same type.

Last modified Apr 9th, 1997 Michael Elhadad