комплексные

действительные

рациональные

целые

Рис. 2.25: Башня типов

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

Иерархии типов

Описанная выше схема приведения типов опиралась на существование естественных отношений между парами типов. Часто в отношениях типов между собой существует более «глобальная» структура. Предположим, например, что мы строим обобщенную арифметическую систему, которая должна работать с целыми, рациональными, действительными и комплексными числами. В такой системе вполне естественно будет рассматривать целое число как частный случай рационального, которое в свою очередь является частным случаем действительного числа, которое опять-таки частный случай комплексного числа. Здесь мы имеем так называемую иерархию типов (hierarchy of types) в которой, например, целые числа являются подтипом (subtype) рациональных чисел (то есть всякая операция, которую можно применить к рациональному числу, применима и к целым). Соответственно, мы говорим, что рациональные числа являются надтипом (supertype) целых. Та конкретная иерархия, с которой мы имеем дело здесь, имеет очень простой вид, а именно, у каждого типа не более одного надтипа и не более одного подтипа. Такая структура, называемая башня типов (tower), показана на рис. 2.25

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

Можно переопределить процедуру apply-generic следующим образом: для каждого типа требуется указать процедуру 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.26: Отношения между типами геометрических фигур.