2.5.2 · Объединение данных разных типов

Приведение смешанных типов к общему представлению

Таблица приведения обрабатывает известную смешанную пару, а числовая башня поднимает целые числа до рациональных и рациональные до комплексных.

Вопрос для размышления

Как обобщенная арифметика может выбирать общий тип, не скрывая неудачные приведения типов и не зацикливаясь между равноправными представлениями?

Различение метода операции и процедуры приведения типа
Повторный запуск обобщенной операции после одного направленного приведения типа
Поднятие значений по явной иерархии целых, рациональных и комплексных чисел
Применение арифметического метода только после того, как оба аргумента получат общий тип
Сообщение об отсутствии общего типа вместо угадывания или бесконечной рекурсии

Первая программа содержит один арифметический метод для сложения двух рациональных значений. Для пары из целого и рационального числа прямого метода нет, поэтому apply-generic обращается к отдельной таблице приведения, преобразует целое число в рациональное со знаменателем 1 и повторяет попытку. Журнал приведения делает этот дополнительный шаг представления видимым. Он также предотвращает попытку приведения к тому же типу при отсутствии метода для одинаковых типов, что иначе привело бы к повторению без продвижения вперед.

Вторая программа заменяет попарный выбор приведения упорядоченной башней типов. Процедура rank определяет уровни integer, rational и complex. Процедура raise выполняет только следующий шаг преобразования вверх, а raise-to повторяет его до тех пор, пока оба значения не достигнут старшего входного ранга. Сложение целого и рационального числа поэтому использует рациональное сложение. Сложение рационального и комплексного числа использует комплексное сложение после одного вызова raise. Несвязанная метка polynomial не имеет ранга и возвращает no-common-type. Башня устраняет неоднозначность для этих упорядоченных типов, но это не означает, что любой тип данных принадлежит единой иерархии или что проекция вниз всегда проходит без потерь.

Код SICP2,373 из 1,048,576 байт UTF-8

(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)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Программа с таблицей приведения возвращает ((rational 7 2) ((integer rational))). Программа с башней типов возвращает ((rational 5 2) (complex #t #t) no-common-type).

На что обратить внимание в трассе

В первом запуске найдите неудавшийся поиск для смешанных типов, преобразование целого числа в рациональное и успешную повторную попытку для пары rational и rational. В запуске с башней типов сравните однократный подъем целого числа с подъемом рационального числа до комплексного, затем найдите ранний результат no-common-type перед вызовом любого арифметического метода для метки polynomial. Трасса выполнения фиксирует эти явные преобразования, а не каноническую иерархию для всех возможных систем типов.

Попробуйте сами

Измените программу и сравните результат.

Добавьте тип real между rational и complex. Поднимите рациональное значение до real перед комплексным, затем определите, сколько шагов raise потребуется для сложения целого и комплексного чисел.

Показать подсказку

Обновите rank и настройте каждый шаг raise на перемещение ровно на один уровень. Обобщенная операция не должна требовать нового попарного приведения между integer и complex.

Завершить этот урок

В этой главе пройдено 0 из 20 уроков0%