Глава 2. Построение абстракций с помощью данных Программы, использующие комплексные числа

add-complex sub-complex mul-complex div-complex

Пакет комплексной арифметики

Списковая структура и элементарная машинная арифметика

Рис. 2.21: Структура обобщенной системы комплексной арифметики.

Поскольку каждый объект данных помечен своим типом, селекторы работают с данными обобщенным образом. Это означает, что каждый селектор по определению обладает поведением, которое зависит от того, к какому типу данных он применяется. Следует обратить внимание на общий механизм доступа к отдельным представлениям: внутри любой данной реализации представления (скажем, внутри полярного пакета Лизы) комплексное число представляется нетипизированной парой (модуль, аргумент). Когда обобщенный селектор обращается к данным полярного типа, он отрывает метку и передает содержимое Лизиному коду. И наоборот, когда Лиза строит число для общего пользования, она помечает его тип, чтобы процедуры более высокого уровня могли его должным образом распознать. Такая дисциплина снятия и добавления меток при передаче объектов данных с уровня на уровень может быть ценной стратегией организации данных и программ, как мы увидим в разделе 2.5.

2.4.3 Программирование, управляемое данными, и аддитивность

Общая стратегия проверки типа данных и вызова соответствующей процедуры называется диспетчеризацией по типу (dispatching on type). Это хороший способ добиться модульности при проектировании системы. С другой стороны, такая реализация диспетчеризации, как в разделе 2.4.2, имеет два существенных недостатка. Один заключается в том, что обобщенные процедуры интерфейса (real-part, imag-part, magnitude и angle) обязаны знать про все имеющиеся способы представления. Предположим, к примеру, что нам хочется ввести в нашу систему комплексных чисел еще одно представление. Нам нужно будет сопоставить этому представлению тип, а затем добавить в каждую из обобщенных процедур интерфейса по варианту для проверки на этот новый тип и вызова селектора, соответствующего его представлению.

Второй недостаток этого метода диспетчеризации состоит в том, что, хотя отдельные представления могут проектироваться раздельно, нам нужно гарантировать, что никакие две процедуры во всей системе не называются одинаково. Вот почему Бену и Лизе пришлось изменить имена своих первоначальных процедур из раздела 2.4.1.

Оба эти недостатка являются следствием того, что наш метод реализации

Рис. 2.22: Таблица операций в системе комплексных чисел.

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

Нам нужен способ еще более модуляризовать устройство системы. Это позволяет сделать метод программирования, который называется программирование, управляемое данными (data-directed programming). Чтобы понять, как работает этот метод, начнем с наблюдения, что каждый раз, когда нам приходится работать с набором обобщенных операций, общих для множества различных типов, мы, в сущности, работаем с двумерной таблицей, где по одной оси расположены возможные операции, а по другой всевозможные типы. Клеткам таблицы соответствуют процедуры, которые реализуют каждую операцию для каждого типа ее аргумента. В системе комплексной арифметики из предыдущего раздела соответствие между именем операции, типом данных и собственно процедурой было размазано по условным предложениям в обобщенных процедурах интерфейса. Но ту же самую информацию можно было бы организовать в виде таблицы, как показано на рисунке 2.22.

Программирование, управляемое данными, - метод проектирования программ, позволяющий им напрямую работать с такого рода таблицей. Механизм, который связывает код комплексных арифметических операций с двумя пакетами представлений, мы ранее реализовали в виде набора процедур, которые явно осуществляют диспетчеризацию по типу. Здесь мы реализуем этот интерфейс через одну процедуру, которая ищет сочетание имени операции и типа аргумента в таблице, чтобы определить, какую процедуру требуется применить, а затем применяет ее к содержимому аргумента. Если мы так сделаем, то, чтобы добавить к системе пакет с новым представлением, нам не потребуется изменять существующие процедуры; понадобится только добавить новые клетки в таблицу.

Чтобы реализовать этот план, предположим, что у нас есть две процедуры put и get, для манипуляции с таблицей операций и типов:

•(put (оп) (шип) (элемент)) вносит (элемент) в таблицу, в клетку, индексом которой служат операция (оп) и тип (тип).

•(get (оп) (тип)) ищет в таблице ячейку с индексом (оп),(тип) и возвращает ее содержимое. Если ячейки нет, get возвращает ложь.

Пока что мы предположим, что get и put входят в наш язык. В главе 3 (раздел 3.3.3) мы увидим, как реализовать эти и другие операции для работы с таблицами.

Программирование, управляемое данными, в системе с комплексными числами можно использовать так: Бен, который разрабатывает декартово представление, пишет код в точности как он это делал сначала. Он определяет набор процедур, или пакет (package), и привязывает эти процедуры к остальной системе, добавляя в таблицу ячейки, которые сообщают системе, как работать с декартовыми числами. Это происходит при вызове следующей процедуры:

(define (install-rectangular-package) ;; внутренние процедуры (define (real-part z) (car z)) (define (imag-part z) (cdr z)) (define (make-from-real-imag x y) (cons x y)) (define (magnitude z)

(sqrt (+ (square (real-part z))

(square (imag-part z))))) (define (angle z)

(atan (imag-part z) (real-part z))) (define (make-from-mag-ang r a)

(cons (* r (cos a)) (* r (sin a))))

;; интерфейс к остальной системе (define (tag x) (attach-tag rectangular x)) (put real-part (rectangular) real-part) (put imag-part (rectangular) imag-part) (put magnitude (rectangular) magnitude) (put angle (rectangular) angle) (put make-from-real-imag rectangular

(lambda (x y) (tag (make-from-real-imag x y)))) (put make-from-mag-ang rectangular

(lambda (r a) (tag (make-from-mag-ang r a)))) done)

Обратите внимание, что внутренние процедуры - те самые, которые Бен писал, когда он, в разделе 2.4.1, работал сам по себе. Никаких изменений, чтобы связать их с остальной системой, не требуется. Более того, поскольку определения процедур содержатся внутри процедуры установки, Бену незачем беспокоиться о конфликтах имен с другими процедурами вне декартова пакета. Чтобы связать их с остальной системой, Бен устанавливает свою процедуру real-part под именем операции real-part и типом (rectangular) , и то же самое он проделывает с другими селекторами.45 Его интерфейс также определяет конструкторы, которые может использовать внешняя система.46 Они

45Мы используем список (rectangular), а не символ rectangular, чтобы предусмотреть возможность операций с несколькими аргументами, не все из которых одинакового типа.

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