Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 46
Текст из файла (страница 46)
Часто в отношениях типов между собой существует более «глобальная» структура. Предположим, например, что мы строим обобщеннуюарифметическую систему, которая должна работать с целыми, рациональными, действительными и комплексными числами. В такой системе вполне естественно будет рассматривать целое число как частный случай рационального, которое в свою очередь являетсячастным случаем действительного числа, которое опять-таки частный случай комплексного числа.
Здесь мы имеем так называемую иерархию типов (hierarchy of types) вкоторой, например, целые числа являются подтипом (subtype) рациональных чисел (тоесть всякая операция, которую можно применить к рациональному числу, применима ик целым). Соответственно, мы говорим, что рациональные числа являются надтипом(supertype) целых. Та конкретная иерархия, с которой мы имеем дело здесь, имеет оченьпростой вид, а именно, у каждого типа не более одного надтипа и не более одногоподтипа. Такая структура, называемая башня типов (tower), показана на рис. 2.25.Если у нас имеется башня типов, то задача добавления нового типа в систему сильноупрощается, поскольку требуется указать только то, каким образом новый тип включается в ближайший надтип сверху и то, каким образом он является надтипом типа,который находится прямо под ним. Например, если мы хотим к комплексному числу добавить целое, нам не нужно специально определять процедуру приведения типаinteger->complex.
Вместо этого мы определяем, как можно перевести целое число врациональное, рациональное в действительное, и как действительное число переводитсяв комплексное. Потом мы позволяем системе преобразовать целое число в комплексноечерез все эти промежуточные шаги и складываем два комплексных числа.Можно переопределить процедуру apply-generic следующим образом: для каж-2.5. Системы с обобщенными операциями195дого типа требуется указать процедуру raise, которая «поднимает» объекты этого типана один уровень в башне. В таком случае, когда системе требуется обработать объектыразличных типов, она может последовательно поднимать объекты более низких типов,пока все объекты не окажутся на одном и том же уровне башни.
(Упражнения 2.83 и2.84 касаются деталей реализации такой стратегии.)Еще одно преимущество башни состоит в том, что легко реализуется представлениео том, что всякий тип «наследует» операции своего надтипа. Например, если мы не даемособой процедуры для нахождения действительной части целого числа, мы все равноможем ожидать, что real-part будет для них определена в силу того, что целые числаявляются подтипом комплексных. В случае башни мы можем устроить так, чтобы этопроисходило само собой, модифицировав apply-generic. Если требуемая операция неопределена непосредственно для типа данного объекта, мы поднимаем его до надтипаи пробуем еще раз.
Так мы ползем вверх по башне, преобразуя по пути свой аргумент,пока мы либо не найдем уровень, на котором требуемую операцию можно произвести,либо не доберемся до вершины (и в таком случае мы сдаемся).Еще одно преимущество башни над иерархией более общего типа состоит в том, чтоона дает нам простой способ «опустить» объект данных до его простейшего представления. Например, если мы складываем 2 + 3i с 4 − 3i, было бы приятно в качестве ответаполучить целое 6, а не комплексное 6 + 0i.
В упражнении 2.85 обсуждается способ,которым такую понижающую операцию можно реализовать. (Сложность в том, что намнужен общий способ отличить объекты, которые можно понизить, вроде 6 + 0i, от тех,которые понизить нельзя, например 6 + 2i.)Неадекватность иерархийЕсли типы данных в нашей системе естественным образом выстраиваются в башню, это сильно упрощает задачу работы с обобщенными операциями над различнымитипами, как мы только что видели. К сожалению, обычно это не так.
На рисунке 2.26показано более сложное устройство набора типов, а именно отношения между различными типами геометрических фигур. Мы видим, что в общем случае у типа может бытьболее одного подтипа. Например, и треугольники, и четырехугольники являются разновидностями многоугольников. В дополнение к этому, у типа может быть более одногонадтипа. Например, равнобедренный прямоугольный треугольник можно рассматриватьи как равнобедренный, и как прямоугольный. Вопрос с множественными надтипами особенно болезнен, поскольку из-за него теряется единый способ «поднять» тип по иерархии. Нахождение «правильного» надтипа, в котором требуется применить операцию кобъекту, может потребовать долгого поиска по всей сети типов внутри процедуры вродеapply-generic. Поскольку в общем случае у типа несколько подтипов, существуетподобная проблема и в сдвиге значения «вниз» по иерархии.
Работа с большим количеством связанных типов без потери модульности при разработке больших систем – задачаочень трудная, и в этой области сейчас ведется много исследований52 .52 Данное утверждение, которое присутствует и в первом издании этой книги, сейчас столь же верно, каки двенадцать лет назад. Разработка удобного, достаточно общего способа выражать отношения между различными типами сущностей (то, что философы называют «онтологией»), оказывается невероятно сложнымделом. Основная разница между той путаницей, которая была десять лет назад, и той, которая есть сейчас, состоит в том, что теперь множество неадекватных онтологических теорий оказалось воплощено в массе соответственно неадекватных языков программирования.
Например, львиная доля сложности объектно-Глава 2. Построение абстракций с помощью данных196многоугольникчетырехугольниктрапециятреугольникчетырехугольникс перпендикулярными диагоналямипараллелограммравнобедренныйтреугольникпрямоугольныйтреугольникпрямоугольникравностороннийтреугольникравнобедренныйпрямоугольныйтреугольникромбквадратРис.
2.26. Отношения между типами геометрических фигур.2.5. Системы с обобщенными операциями197Упражнение 2.81.Хьюго Дум заметил, что apply-generic может пытаться привести аргументы к типу друг другадаже тогда, когда их типы и так совпадают. Следовательно, решает он, нам нужно вставитьв таблицу приведения процедуры, которые «приводят» аргументы каждого типа к нему самому.Например, в дополнение к приведению scheme-number->complex, описанному выше, он бынаписал еще:(define (scheme-number->scheme-number n) n)(define (complex->complex z) z)(put-coercion ’scheme-number ’scheme-numberscheme-number->scheme-number)(put-coercion ’complex ’complex complex->complex)а.
Если установлены процедуры приведения типов, написанные Хьюго, что произойдет, когдаapply-generic будет вызвана с двумя аргументами типа scheme-number или двумя аргументами типа complex для операции, которая не находится в таблице для этих типов? Допустим,например, что мы определили обобщенную процедуру возведения в степень:(define (exp x y) (apply-generic ’exp x y))и добавили процедуру возведения в степень в пакет чисел Scheme и ни в какой другой:;; Следующие строки добавляются в пакет scheme-number(put ’exp ’(scheme-number scheme-number)(lambda (x y) (tag (expt x y)))) ;используется;элементарная exptЧто произойдет, если мы позовем exp с двумя комплексными числами в качестве аргументов?б.
Прав ли Хьюго, что нужно что-то сделать с приведением однотипных аргументов, или все итак работает правильно?в. Измените apply-generic так, чтобы она не пыталась применить приведение, если у обоихаргументов один и тот же тип.Упражнение 2.82.Покажите, как обобщить apply-generic так, чтобы она обрабатывала приведение в общемслучае с несколькими аргументами. Один из способов состоит в том, чтобы попытаться сначалапривести все аргументы к типу первого, потом к типу второго, и так далее. Приведите пример,когда эта стратегия (а также двухаргументная версия, описанная выше) недостаточно обща.
(Подсказка: рассмотрите случай, когда в таблице есть какие-то подходящие операции со смешаннымитипами, но обращения к ним не произойдет.)Упражнение 2.83.Предположим, что Вы разрабатываете обобщенную арифметическую систему для работы с башнейтипов, показанной на рис. 2.25: целые, рациональные, действительные, комплексные. Для каждогоориентированных языков программирования — и мелких невразумительных различий между современнымиобъектно-ориентированными языками, — сосредоточена в том, как рассматриваются обобщенные операции надвзаимосвязанными типами. Наше собственное описание вычислительных объектов в главе 3 полностью избегает этих вопросов.
Читатели, знакомые с объектно-ориентированным программированием, заметят, что наместь, что сказать в главе 3 о локальном состоянии, но мы ни разу не упоминаем «классы» или «наследование».Мы подозреваем, что на самом деле эти проблемы нельзя рассматривать только в терминах проектированияязыков программирования, без обращения к работам по представлению знаний и автоматическому логическомувыводу.198Глава 2. Построение абстракций с помощью данныхиз типов (кроме комплексного), разработайте процедуру, поднимающую объект на один уровеньв башне. Покажите, как ввести обобщенную операцию raise, которая будет работать для всехтипов (кроме комплексных чисел).Упражнение 2.84.Используя операцию raise из упражнения 2.83, измените процедуру apply-generic так, чтобы она приводила аргументы к одному типу путем последовательного подъема, как описано вэтом разделе.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
