Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 45
Текст из файла (страница 45)
Элементарные процедуры вроде symbol? или number? определяют, относится ли объектк определенному типу. Измените определения type-tag, contents и attach-tag из раздела 2.4.2 так, чтобы наша обобщенная система использовала внутреннюю систему типов Scheme.То есть, система должна работать так же, как раньше, но только обычные числа должны бытьпредставлены просто в виде чисел языка Scheme, а не в виде пары, у которой первый элементсимвол scheme-number.Упражнение 2.79.Определите обобщенный предикат равенства equ?, который проверяет два числа на равенство,и вставьте его в пакет обобщенной арифметики.
Операция должна работать для обычных чисел,рациональных и комплексных.Упражнение 2.80.Определите обобщенный предикат =zero?, который проверяет, равен ли его аргумент нулю, ивставьте его в пакет обобщенной арифметики. Предикат должен работать для обычных, рациональных и комплексных чисел.2.5.2. Сочетание данных различных типовМы видели, как можно построить объединенную арифметическую систему, котораяохватывает обыкновенные числа, комплексные числа, рациональные числа и любые другие типы чисел, которые нам может потребоваться изобрести, но мы упустили важныймомент.
Операции, которые мы до сих пор определили, рассматривают различные типыданных как совершенно независимые. Таким образом, есть отдельные пакеты для сложения, например, двух обыкновенных чисел и двух комплексных чисел. Мы до сих порне учитывали того, что имеет смысл определять операции, которые пересекают границытипов, например, сложение комплексного числа с обычным.
Мы затратили немалые усилия, чтобы воздвигнуть барьеры между частями наших программ, так, чтобы их можнобыло разрабатывать и понимать по отдельности. Нам бы хотелось добавить операции сосмешанными типами по возможности аккуратно, так, чтобы мы их могли поддерживать,не нарушая всерьез границ модулей.Один из способов управления операциями со смешанными типами состоит в том,чтобы определить отдельную процедуру для каждого сочетания типов, для которых операция имеет смысл. Например, мы могли бы расширить пакет работы с комплекснымичислами и включить туда процедуру сложения комплексных чисел с обычными, заносяее в таблицу с меткой (complex scheme-number)49:;; включается в пакет комплексных чисел(define (add-complex-to-schemenum z x)(make-from-real-imag (+ (real-part z) x)(imag-part z)))(put ’add ’(complex scheme-number)(lambda (z x) (tag (add-complex-to-schemenum z x))))49 Придетсяк тому же написать почти такую же процедуру для типа (scheme-number complex).192Глава 2. Построение абстракций с помощью данныхЭтот метод работает, но он очень громоздок.
При такой системе стоимость введения нового типа не сводится к тому, чтобы построить пакет процедур для этого типа,но включает еще построение и установку процедур, осуществляющих операции со смешанными типами. Это запросто может потребовать больше кода, чем нужно, чтобыопределить операции над самим типом. Кроме того, этот метод подрывает нашу способность сочетать отдельные пакеты аддитивно, или, по крайней мере, ограничиватьстепень, в которой реализация отдельного пакета должна принимать другие пакеты врасчет.
Скажем, в вышеприведенном примере, кажется естественным, чтобы ответственность за обработку смешанных операций с обычными и комплексными числами лежалана комплексном пакете. Однако сочетание рациональных и комплексных чисел можетосуществляться комплексным пакетом, рациональным пакетом, или каким-нибудь третьим, который пользуется операциями, извлеченными из этих двух. Формулировка ясныхправил разделения ответственности между пакетами может стать непосильной задачейпри разработке систем с многими пакетами и многими смешанными операциями.Приведение типовВ ситуации общего вида, когда совершенно несвязанные друг с другом операции применяются к совершенно друг с другом не связанным типам, явное написание операцийсо смешанными типами, как бы это ни было громоздко, — все, на что мы можем рассчитывать.
К счастью, обычно мы можем воспользоваться дополнительной структурой,которая часто в скрытом виде присутствует в нашей системе типов. Часто различныетипы данных не совсем независимы, и каким-то образом объекты одного типа можно рассматривать как объекты другого. Такой процесс называется приведением типов(coercion). Например, если нас просят найти некоторую арифметическую комбинациюобычного числа и комплексного, то мы можем рассматривать обычное число как такоекомплексное, у которого мнимая часть равна нулю.
Это сводит нашу задачу к сочетанию двух комплексных чисел, а с этим может стандартным способом справиться пакеткомплексной арифметики.В общем случае мы можем реализовать эту идею, проектируя процедуры приведениятипа, которые переводят объект одного типа в эквивалентный ему объект другого типа.Вот типичная процедура приведения типов, которая преобразует данное обыкновенноечисло в комплексное, у которого есть действительная часть, а мнимая равна нулю:(define (scheme-number->complex n)(make-complex-from-real-imag (contents n) 0))Мы записываем процедуры приведения типа в специальную таблицу приведения типов,проиндексированную именами двух типов:(put-coercion ’scheme-number ’complex scheme-number->complex)(Предполагается, что для работы с этой таблицей существуют процедуры put-coercionи get-coercion.) Как правило, часть ячеек этой таблицы будет пуста, потому что вобщем случае невозможно привести произвольный объект произвольного типа ко всемостальным типам.
К примеру, нет способа привести произвольное комплексное число кобыкновенному, так что в таблице не появится общая процедура complex->schemenumber.2.5. Системы с обобщенными операциями193Когда таблица приведения типов построена, мы можем работать с приведением стандартным образом, приспособив для этого процедуру apply-generic из раздела 2.4.3.Когда нас просят применить операцию, мы первым делом, как и раньше, проверяем, неопределена ли уже операция для типов аргументов.
Если да, мы вызываем процедуру,найденную в таблице операций и типов. Если нет, мы пробуем применить приведениетипов. Для простоты мы рассматриваем только тот случай, когда аргументов два50 . Мыпроверяем таблицу преобразования типов и смотрим, можно ли объект первого типа привести ко второму типу. Если да, осуществляем приведение и снова пробуем операцию.Если объекты первого типа в общем случае ко второму не приводятся, мы пробуем приведение в обратном направлении и смотрим, нет ли способа привести второй аргументк типу первого. Наконец, если нет никакого известного способа привести один тип кдругому, мы сдаемся. Вот эта процедура:(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))(t2->t1(apply-generic op a1 (t2->t1 a2)))(else(error "Нет метода для этих типов"(list op type-tags))))))(error "Нет метода для этих типов"(list op type-tags)))))))Такая схема приведения типов имеет много преимуществ перед методом явного определения смешанных операций, как это описано выше.
Хотя нам по-прежнему требуетсяписать процедуры приведения для связи типов (возможно, n2 процедур для системы с nтипами), для каждой пары типов нам нужно написать только одну процедуру, а не попроцедуре на каждый набор типов и каждую обобщенную операцию51 . Здесь мы рассчитываем на то, что требуемая трансформация типов зависит только от самих типов, и независит от операции, которую требуется применить.50 Обобщениесм. в упражнении 2.82.мы умные, мы обычно можем обойтись меньше, чем n2 процедурами приведения типа.
Например,если мы знаем, как из типа 1 получить тип 2, а из типа 2 тип 3, то можно использовать это знание дляпреобразования из 1 в 3. Это может сильно уменьшить количество процедур, которые надо явно задавать привведении нового типа в систему. Если нам не страшно ввести в свою систему требуемый уровень изощренности,мы можем заставить ее искать по «графу» отношений между типами и автоматически порождать все процедурыприведения типов, которые можно вывести из тех, которые явно заданы.51 Если194Глава 2. Построение абстракций с помощью данныхкомплексные↑↑рациональные↑целыедействительныеРис.
2.25. Башня типовС другой стороны, могут существовать приложения, для которых наша схема приведения недостаточно обща. Даже когда ни один из объектов, которые требуется сочетать,не может быть приведен к типу другого, операция может оказаться применимой, еслипреобразовать оба объекта к третьему типу. Чтобы справиться с такой степенью сложности и по-прежнему сохранить модульность в наших программах, обычно необходимостроить такие системы, которые еще в большей степени используют структуру в отношениях между типами, как мы сейчас расскажем.Иерархии типовОписанная выше схема приведения типов опиралась на существование естественныхотношений между парами типов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
