Барбара Лисков
«Абстракция данных и иерархия»

Аннотация

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

1. Введение

Важная цель проектирования — выявить такую структуру программы, которая облегчала бы как ее сопровождение, так и процесс внесения изменений, необходимых для поддержки меняющихся требований. Абстракции данных — хороший способ достижения этой цели. Они позволяют нам абстрагироваться от способа реализации структур данных, сосредоточившись на поведении, которое они предоставляют и на которое могут полагаться другие программы. Они позволяют локально изменять представление данных, не затрагивая программы, использующие эти данные. Они особенно важны, поскольку скрывают сложные элементы (структуры данных), которые, вероятно, изменятся в будущем. Они также упрощают структуру программ, которые их используют, поскольку предоставляют интерфейс более высокого уровня. Например, они сокращают число аргументов процедур, поскольку передаются абстрактные объекты, а не их представления.

Объектно-ориентированное программирование — это в первую очередь техника абстракции данных, и во многом его сила обусловлена именно этим. Однако оно дополняет эту технику понятием «наследования». Наследование можно использовать различными способами, некоторые из которых укрепляют силу абстракции данных. В таких случаях наследование представляет собой полезное дополнение к абстракции данных.

В этой статье обсуждается взаимосвязь между абстракцией данных и объектно-ориентированным программированием. В разделе 2 мы начнем с определения абстракции данных и ее роли в процессе разработки программ. Затем, в разделе 3, мы обсудим наследование и выделим два способа его использования: для иерархии реализации и для иерархии типов. Из двух этих способов именно иерархия типов действительно вносит нечто новое в абстракцию данных, поэтому в разделе 4 мы рассмотрим использование иерархии типов при проектировании и разработке программ. Далее мы обсудим некоторые вопросы, возникающие при реализации иерархии типов. И, наконец, в заключение мы приведем краткое изложение полученных результатов.

1. Абстракция данных

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

Процедуры — полезный механизм абстракции, однако в начале 1970-х некоторые исследователи осознали, что одних процедур недостаточно [15, 16, 7], и предложили новый способ организации программ вокруг «связей» между модулями. Из этих идей возникло понятие абстракции данных, или абстрактного типа данных [5, 12].

Абстракции данных предоставляют те же преимущества, что и процедуры, но для данных. Напомним, что основная идея здесь — отделить то, чем является абстракция, от того, как она реализована, чтобы реализации одной и той же абстракции можно было свободно заменять. Реализация объекта данных связана с тем, как этот объект представлен в памяти компьютера; эта информация называется представлением (representation, или rep для краткости). Чтобы можно было заменять реализации, не затрагивая пользователей, нужен способ изменять представление без необходимости изменения всех использующих его программ. Это достигается инкапсуляцией представления вместе с набором операций, которые им манипулируют, и ограничением использующих программ так, чтобы они не могли манипулировать представлением напрямую, а должны были вызывать операции. Затем, чтобы реализовать или изменить абстракцию данных, необходимо определить представление и реализовать операции на основе этого представления; при этом использующий код не затрагивается изменениями.

Таким образом, абстракция данных — это набор объектов, которыми можно напрямую манипулировать лишь через набор операций. Пример абстракции данных — целые числа: объектами являются 1, 2, 3 и т.д., и есть операции для сложения двух целых чисел, проверки их на равенство и т.д. Программы, использующие целые числа, манипулируют ими с помощью своих операций, а детали реализации, например, является ли представление дополнением до двух, от них скрыты. Другой пример — символьные строки с объектами “a” и “xyz” и операциями для выбора символа из строки и конкатенации строк. Последний пример — множества целых чисел с объектами вроде { } (пустое множество) и {3, 7} и операциями вставки элемента в множество и проверки, принадлежит ли целое число множеству. Следует отметить, что в большинстве языков программирования целые числа и строки являются встроенными типами данных, в то время как множества и другие ориентированные на приложения абстракции данных, такие как стеки и таблицы символов, — нет. Языковые механизмы, позволяющие реализовывать определяемые пользователем абстрактные типы данных, обсуждаются в разделе 2.2.

Абстракция данных или процедуры определяется спецификацией и реализуется программным модулем, написанным на некотором языке программирования. Спецификация описывает, что делает абстракция, но опускает все сведения о том, как она реализована. Опуская такие детали, мы допускаем множество различных реализаций. Реализация является корректной, если она обеспечивает поведение, заданное спецификацией. Корректность можно доказать математически, если спецификация записана на языке с точной семантикой; в противном случае мы устанавливаем корректность с помощью неформальных рассуждений или, что менее удовлетворительно, с помощью техники тестирования. Корректные реализации отличаются друг от друга тем, как они работают, то есть какими алгоритмами пользуются, и поэтому могут иметь разную производительность. Любая корректная реализация приемлема для вызывающего кода, если она удовлетворяет его требованиям к производительности. Следует отметить, что корректные реализации не обязаны быть идентичными; весь смысл в том, чтобы реализации могли различаться, оставаясь при этом одинаковыми там, где это важно. А что именно важно — описывается спецификацией.

Чтобы абстракция работала, реализации должны быть инкапсулированы. Если реализация инкапсулирована, то ни один другой модуль не может зависеть ее деталей. Инкапсуляция гарантирует, что модули можно реализовывать и изменять независимо друг от друга; это связано с принципом «сокрытия информации», который отстаивал Парнас [15].

2.1. Локальность

Абстракция, поддерживаемая спецификациями и инкапсуляцией, обеспечивает локальность в рамках программы. Локальность позволяет реализовывать, понимать или изменять программу помодульно:

1. Тот, кто реализует абстракцию, знает, что от него требуется, — это описано в спецификации. Следовательно, ему не нужно взаимодействовать с разработчиками других модулей (или, по крайней мере, это взаимодействие можно свести к минимуму).

2. Аналогично, тот, кто реализует использующий модуль, знает, чего можно ожидать от абстракции — а именно поведения, описанного в спецификации.

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

4. Наконец, изменение программы может осуществляться помодульно. Если нужно изменить реализацию конкретной абстракции, чтобы улучшить производительность, исправить ошибку или расширить функционал, старый модуль реализации можно заменить новым, не затрагивая другие модули.

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

Локальность также способствует эволюции программы. Абстракции могут использоваться для инкапсуляции потенциальных изменений. Предположим, мы хотим, чтобы программа запускалась на разных машинах. Мы можем добиться этого, создав абстракции, которые скрывают различия между машинами, и тогда для переноса программы на другую машину потребуется заново реализовать только эти абстракции. Хороший принцип проектирования — заранее подумать об ожидаемых изменениях и организовать проект с использованием абстракций, инкапсулирующих эти изменения.

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

2.2. Языковая поддержка абстракции данных

Абстракции данных поддерживаются механизмами, предоставляемыми языками программирования. Самым ранним из таких языков был Simula 67 [3]. Ниже обсуждаются два основных варианта — в CLU и Smalltalk.

Для реализации абстрактных типов CLU [8, 11] предоставляет механизм под названием кластер (cluster). Шаблон кластера показан на рис. 2-1. Заголовок определяет реализуемый тип данных, а также список операций этого типа; в нем указывается, какие определения процедур внутри кластера могут быть вызваны извне. Строка “rep =” определяет, каким образом будут представлены объекты типа; в приведенном примере множества реализуются в виде связных списков. Остальная часть кластера состоит из процедур; каждой операции должна соответствовать своя процедура, а также могут быть определены некоторые процедуры, предназначенные для использования только внутри кластера.

int_set = cluster is create, insert, is_in, size, …
rep = int_list
create = proc … end create
insert = proc … end insert
…
end int_set

Рис. 2-1. Шаблон кластера в CLU

В Smalltalk [4] абстракции данных реализуются классами. Классы могут быть организованы иерархически, но сейчас мы это опустим. Класс реализует абстракцию данных аналогично кластеру. Вместо строки “rep =” представление описывается последовательностью объявлений переменных; их называют переменными экземпляра [1]. Остальная часть класса состоит из методов, которые являются определениями процедур. Для каждой операции типа данных, реализуемого классом, существует метод. (В классах Smalltalk не может быть внутренних методов, поскольку невозможно предотвратить их использование извне.) Методы вызываются посредством «отправки сообщений», что аналогично вызову операций в CLU.

И CLU, и Smalltalk обеспечивают инкапсуляцию, но CLU использует проверку типов на этапе компиляции, а Smalltalk — проверку во время выполнения. Проверка на этапе компиляции лучше, поскольку позволяет выявлять целый класс ошибок до запуска программы, а также позволяет компилятору генерировать более эффективный код. (Проверка на этапе компиляции может ограничивать выразительность, если язык программирования не имеет мощной системы типов; этот вопрос обсуждается далее в разделе 5.) Другие объектно-ориентированные языки, например, [1, 13], вообще не обеспечивают инкапсуляцию. Конечно, при отсутствии языковой поддержки инкапсуляцию можно гарантировать с помощью ручных методов, таких как чтение кода, однако эти методы ненадежны, и хотя для только что реализованной программы такой подход может быть приемлемым, по мере внесения изменений ситуация будет быстро ухудшаться. На автоматическую проверку — как во время выполнения, так и на этапе компиляции — можно положиться с уверенностью и без необходимости читать код.

Другое отличие между CLU и Smalltalk касается семантики объектов данных. В Smalltalk операции являются частью объекта и имеют доступ к переменным экземпляра, составляющим представление объекта, поскольку эти переменные также являются частью объекта. В CLU операции принадлежат не объекту, а типу. Это дает им особые привилегии по отношению к объектам своего типа — привилегии, которых нет у других частей программы, а именно они могут видеть представления этих объектов. (Такой подход был впервые описан Моррисом [14].) Подход CLU лучше работает для операций, одновременно манипулирующих несколькими объектами данного типа, поскольку операция может видеть представления сразу нескольких объектов. Примеры таких операций — сложение двух целых чисел или объединение двух множеств. Подход Smalltalk не столь хорошо поддерживает такие операции, поскольку операция может находиться лишь внутри одного объекта. С другой стороны, подход Smalltalk лучше работает, когда нам нужно, чтобы несколько реализаций одного типа использовались в рамках одной программы. В CLU операция может видеть представление любого объекта своего типа, а значит должна быть явно реализована для работы с несколькими представлениями. Smalltalk обходит эту проблему, поскольку операция может видеть представление лишь одного объекта.

3. Наследование и иерархия

В этом разделе рассматриваются наследование и его роль в поддержке иерархии. Сначала мы обсудим, что означает строить программу с использованием наследования. Затем мы обсудим два основных способа использования наследования — иерархию реализации и иерархию типов (аналогичное обсуждение см. в [18]). Только один из них — иерархия типов — действительно вносит нечто новое в абстракцию данных.

3.1. Наследование

В языке с наследованием абстракцию данных можно реализовать в виде нескольких связанных друг с другом частей. Хотя разные языки предоставляют различные механизмы для объединения этих частей, все эти механизмы сходны. Поэтому мы можем проиллюстрировать их, рассмотрев один единственный механизм — механизм подклассов в Smalltalk.

В Smalltalk класс можно объявить подклассом другого класса [2*], который будет его суперклассом. Первое, что следует понять в этом механизме, — это какой код является результатом такого объявления. Этот вопрос важен для понимания того, что делает подкласс. Например, если бы мы рассуждали о его корректности, нам пришлось бы заглянуть в этот код.

С точки зрения итогового кода, говорить, что один класс является подклассом другого, — это просто краткая форма записи для построения программ. Какая именно программа строится, зависит от правил языка, например, от того, какие методы подкласса переопределяют методы суперкласса. Конкретные детали этих правил не важны для нашего обсуждения (хотя они, очевидно, важны, если язык должен быть осмысленным и полезным). Суть в том, что результат эквивалентен прямой реализации класса, содержащего переменные экземпляра и методы, получаемые в результате применения этих правил.

Например, предположим, что класс T имеет операции o₁ и o₂, переменную экземпляра v₁, а также класс S, который объявлен подклассом T и имеет операции o₁ и o₃ и переменную экземпляра v₂. В Smalltalk мы по итогу получим класс с двумя переменными экземпляра, v₁ и v₂, и тремя операциями, o₁, o₂, o₃, где код o₂ предоставлен T, а код двух других операций предоставлен S. Именно этот код предстоит понять или изменить, если мы решим заново реализовать S, если только S не будет ограничен, как это обсуждается ниже.

Одна из проблем, присущих почти всем механизмам наследования, состоит в том, что они в некоторой степени нарушают абстракцию данных. В языках с наследованием реализация абстракции данных (то есть класс) имеет две категории пользователей. Есть «посторонние», которые просто используют объекты, вызывая операции. Но кроме них есть и «свои». Это подклассы, которым, как правило, разрешено нарушать инкапсуляцию. Существует три способа нарушения инкапсуляции [18]: подкласс может получить доступ к переменной экземпляра суперкласса, вызвать приватную операцию суперкласса или обратиться напрямую к суперклассам своего суперкласса. (В Smalltalk последнее нарушение невозможно.)

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

Нарушение инкапсуляции может быть полезным при быстром построении прототипов, поскольку позволяет создавать новый код путем расширения и изменения уже существующего. Однако нереалистично ожидать, что изменения реализации суперкласса будут автоматически распространяться на подкласс. Такое распространение полезно лишь в том случае, если итоговый код работает, а это значит, что все ожидания подкласса относительно суперкласса должны удовлетворяться новой реализацией. Эти ожидания можно отразить в дополнительной спецификации для суперкласса; это спецификация, отличная от той, что предназначена для посторонних, поскольку она содержит дополнительные ограничения. Используя эту дополнительную спецификацию, программист может определить, получится ли осмысленно перенести предлагаемое изменение суперкласса на подкласс. Стоит отметить, что чем больше дополнительная спецификация опирается на детали предыдущей реализации суперкласса, тем меньше шансов, что новая реализация суперкласса удовлетворит ее требованиям. Кроме того, ситуация станет неуправляемой, если каждый подкласс будет опираться на свою собственную спецификацию суперкласса. Один из возможных подходов — определить единую спецификацию для использования всеми подклассами, которая содержала бы больше деталей, чем спецификация для посторонних, но при этом все же абстрагировалась бы от большинства деталей реализации. Некоторые наработки в этом направлении описаны в [17].

3.2. Иерархия реализации

В первом случае наследование используется просто как техника для реализации типов данных, похожих на другие уже существующие типы. Например, предположим, что мы хотим реализовать множество целых чисел с операциями (среди прочих) для проверки, принадлежит ли элемент множеству, и для определения текущего размера множества. Предположим далее, что списочный тип данных уже реализован и предоставляет операции member и size, а также удобный способ представления множества. Тогда мы могли бы реализовать множество как подкласс списка; мы могли бы хранить элементы множества в списке без дублирования, то есть если элемент добавляется в множество дважды, в списке он появляется только один раз. Тогда нам не понадобится реализовывать операции member и size, но потребуется реализовать другие операции, например, вставку нового элемента в множество. Кроме того, следует подавить некоторые другие операции, такие как car, чтобы сделать их недоступными, поскольку они не имеют смысла для множеств. (В Smalltalk это можно сделать, предоставив в подклассе реализации для подавляемых операций; такая реализация при вызове будет сообщать об исключении.)

Другой способ сделать то же самое — использовать один (абстрактный) тип как представление другого. Например, мы можем реализовать множество, используя в качестве представления список. В этом случае нам пришлось бы реализовать операции size и member; каждая из них просто вызывала бы соответствующие операции списка. Написание реализаций для этих двух операций, даже несмотря на то, что код будет очень простым, — это все равно больше работы, чем вообще ничего не писать. С другой стороны, нам ничего не нужно делать, чтобы убрать нежелательные операции вроде car.

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

3.3. Иерархия типов

Иерархия типов состоит из подтипов и супертипов. Интуитивная идея подтипа заключается в том, что это тип, объекты которого предоставляют все поведение объектов другого типа (супертипа) плюс нечто дополнительное. Здесь требуется нечто вроде следующего свойства подстановки [6]: если для каждого объекта o₁ типа S существует такой объект o₂ типа T, что для всех программ P, определенных на основе T, поведение P не изменяется при замене o₁ на o₂, то S является подтипом T. (Другие работы по этой теме см. [2, 17].)

Мы используем здесь слова «подтип» и «супертип», чтобы подчеркнуть, что сейчас мы говорим о семантическом различии. Напротив, «подкласс» и «суперкласс» — это просто понятия из языков программирования, позволяющие строить программы определенным образом. Их можно использовать не только для реализации подтипов, но и, как упоминалось выше, в других целях.

Начнем с нескольких примеров типов, которые не являются подтипами друг друга. Во-первых, множество не является подтипом списка, и наоборот. Если один и тот же элемент добавляется в множество дважды, результат будет таким же, как если бы он был добавлен всего один раз, и при вычислении размера множества этот элемент учитывается лишь один раз. Однако если один и тот же элемент добавляется в список дважды, он оказывается в списке дважды. Таким образом, программа, ожидающая список, может работать некорректно, если ей передать множество; аналогично программа, ожидающая множество, может не сработать, если ей передать список. Другой пример типов, не являющихся подтипами, — стеки и очереди. Стеки работают по принципу LIFO: при удалении элемента из стека удаляется последний добавленный (помещенный) туда элемент. Очереди же, напротив, работают по принципу FIFO. Использующая программа, вероятно, заметит разницу между ними.

Приведенный выше пример не учитывал простого различия между парами типов, а именно связанных с ними операций. Подтип должен иметь все операции [3*] своего супертипа, поскольку иначе использующая программа не сможет вызвать операцию, от которой зависит. Однако одного лишь наличия операций с правильными именами и сигнатурами недостаточно. (Сигнатура операции определяет количество и типы входных и выходных аргументов.) Операции также должны иметь одинаковое поведение. Например, стеки и очереди могут иметь операции с одинаковыми именами, такие как add_el (для помещения элемента в стек или в очередь) и rem_el (для извлечения элемента из стека или из очереди). Тем не менее они не являются подтипами друг друга, поскольку смысл этих операций для них различен.

Теперь приведем несколько примеров иерархий подтипов. Первый — это индексированные коллекции, у которых есть операции для доступа к элементам по индексу; например, они предоставляют операцию fetch для получения i-го элемента коллекции. У всех подтипов также есть эти операции, но, кроме того, каждый из них предоставляет дополнительные операции. Примеры подтипов — массивы, последовательности и индексированные множества; например, последовательности можно конкатенировать, а массивы можно изменять, записывая в элементы новые объекты.

Второй пример — абстрактные устройства, которые объединяют различные устройства ввода и вывода. Конкретные устройства могут предоставлять дополнительные операции. В этом случае операции абстрактного устройства — это те, которые поддерживаются всеми устройствами, например проверка конца файла, а операции подтипов являются специфическими для конкретных устройств. Например, у принтера будут операции записи, такие как put_char, но не будет операций чтения, таких как get_char. Другой вариант: абстрактные устройства могут иметь все возможные операции, например и put_char, и get_char, и тогда все подтипы будут иметь один и тот же набор операций. В таком случае операции, которые могут быть реализованы не на всех реальных устройствах, должны быть описаны в общем виде, допускающем сообщения об исключениях. Например, get_char будет сообщать об исключении при вызове на принтере.

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

4. Преимущества иерархии типов

Абстракция данных сама по себе является мощным инструментом. Иерархия типов — полезное дополнение к абстракции данных. В этом разделе обсуждается, как можно использовать подтипы при проектировании программы. (Подробное обсуждение проектирования, основанного на абстракции данных, можно найти в [11].) Также в этом разделе рассматривается использование подтипов при организации библиотеки программ.

4.1. Инкрементное проектирование

Как правило, абстракции данных разрабатываются инкреметно по мере продвижения проектирования. На ранних этапах проектирования нам известны лишь некоторые операции абстракции данных и часть ее поведения. Такой этап проектирования изображен на рис. 4-1а. Проектное решение представлено в виде графа, иллюстрирующего, каким образом программа подразделяется на модули. Существует два типа узлов: узел с одной линией сверху представляет абстракцию процедуры, а узел с двумя линиями сверху — абстракцию данных. Стрелка, направленная от одного узла к другому, означает, что абстракция первого узла будет реализована с использованием абстракции второго узла. Таким образом, рисунок показывает две процедуры, P и Q, и одну абстракцию данных, T. P будет реализована с использованием Q (то есть ее код вызывает Q) и T (то есть ее код использует объекты типа T). (Рекурсия обозначается циклами в графе. Так, если бы мы предполагали, что реализация P вызывает P, то на графе существовала бы стрелка от P к P.)

Этот рисунок представляет ранний этап проектирования, на котором проектировщик продумывал реализацию P и ввел Q и T. На этом этапе некоторые операции T уже определены, и проектировщик решил, что объект типа T будет использоваться для взаимодействия между P и Q.

Следующий этап проектирования — выяснить, как реализовать Q. (Пока смотреть на реализацию T не имеет смысла, поскольку нам еще не известны все его операции.) Изучая Q, мы, скорее всего, определим дополнительные операции для T. Это можно рассматривать как доработку T до подтипа S, как показано на рис. 4-2. Здесь двойная стрелка указывает от супертипа к подтипу; двойные стрелки могут соединять только абстракции данных (и при этом циклы, состоящие только из двойных стрелок, невозможны).

Подобная доработка, проиллюстрированная на рисунках, может выполняться несколько раз; например, S, в свою очередь, может иметь подтип R и т.д. Кроме того, один тип может иметь несколько подтипов, отражающих потребности различных частей программы.

Есть несколько причин, по которым отслеживать эти различия через подтипы лучше, чем рассматривать группу типов как один тип. Во-первых, это может ограничить влияние ошибок проектирования. Например, предположим, что дальнейшая работа выявляет проблему с интерфейсом S. Когда возникает проблема такого рода, необходимо проанализировать каждую абстракцию, использующую измененную абстракцию. На рисунке это означает, что мы должны рассмотреть Q. Однако при условии, что интерфейс T не затронут, нам не пришлось бы проверять P. Если бы S и T рассматривались как один тип, тогда пришлось бы проверить и P.

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

Наконец, такое различение может быть полезным в процессе реализации, например, если нужно заменить реализацию S, но не T. Однако возможно, что в реализации иерархия типов не сохранится. Зачастую итогом проектирования будет один тип — последний созданный подтип, поскольку реализовать один модуль удобнее, чем иметь несколько отдельных модулей для супертипов и подтипов. Но даже при этом указанное различение остается полезным и после реализации, поскольку последствия изменений спецификации все еще можно локализовать, даже если это уже нельзя сделать с изменениями реализации. Например, изменение спецификации S, но не T, означает, что нам нужно заново реализовать Q, но не P. Однако если S и T реализованы как единый модуль, нам придется заново реализовать и тот, и другой, а не просто заменить реализацию S.

4.2. Связанные типы

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

Связанные типы появляются двумя способами. Иногда взаимосвязь определяется заранее, до того как будут созданы какие-либо типы; такую ситуацию мы уже обсуждали выше. С другой стороны, взаимосвязь может быть выявлена, когда несколько связанных типов уже существуют. Такая ситуация возникает из-за желания определить модуль, который работает с каждым из связанных типов, но зависит лишь от их небольшой общей части. Например, модуль может представлять собой подпрограмму сортировки, которая полагается на свой аргумент — «коллекцию», позволяющую получать элементы, а также на сам тип элемента, который должен предоставлять операцию “<”.

Когда взаимосвязь определена заранее, иерархия — хороший способ ее описать, и, возможно, мы действительно захотим использовать наследование в качестве механизма реализации. Это позволяет нам реализовать один раз (в супертипе) все, что можно сделать независимо от подтипа. Модуль подтипа имеет дело лишь со специфическим поведением этого подтипа и не зависит от модулей, реализующих другие подтипы. Наличие отдельных модулей для супертипа и подтипов дает лучшую модульность, чем использование единого модуля для реализации их всех. Кроме того, если позднее будет добавлен новый подтип, никакой существующий код изменять не придется.

Когда взаимосвязь выявляется уже после того, как типы были определены, иерархия может оказаться не лучшим способом организации программы. Этот вопрос обсуждается в разделе 5.1.

4.3. Организации библиотеки типов

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

Иерархия позволяет группировать схожие типы. Таким образом, если пользователю нужна определенная абстракция «коллекции», велика вероятность, что ее, если она вообще существует, можно будет найти среди других коллекций. Используемая иерархия будет либо иерархией подтипов, либо почти иерархией подтипов (то есть подтип довольно слабо отличается от расширения супертипа). Суть в том, что типы группируются скорее на основе поведения, чем на основе того, как они используются для реализации друг друга.

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

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

5. Иерархия типов и наследование

Не все способы использования иерархии требуют языковой поддержки. Библиотеке программ поддержка не требуется; все, что здесь нужно, — это использовать понятие иерархии типов как организующий принцип. Поддержка, как правило, также не требуется, если использовать иерархию как технику доработки. Как уже упоминалось, наиболее вероятный результат применения такой техники проектирования — получить в итоге один тип (последний созданный подтип), который удобнее всего реализовать как единый модуль. Таким образом, здесь подойдет любой язык, поддерживающий абстракцию данных, хотя наследование может быть полезным для добавления дополнительных операций, выявленных позже.

Однако для связанных типов специальная языковая поддержка может понадобиться. Эта поддержка рассматривается в разделе 5.1. В разделе 5.2 обсуждается отношение наследования к множественным реализациям типа.

5.1. Полиморфизм

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

Когда в программе присутствуют связанные типы, скорее всего, будет иметь место и полиморфизм. Это особенно верно, если на эту взаимосвязь указывает необходимость полиморфного модуля. Даже когда эта взаимосвязь определена заранее, полиморфизм все равно весьма вероятен. В таком случае супертип зачастую оказывается виртуальным: у него нет собственных объектов, а он служит лишь для обозначения места в иерархии для семейства связанных типов. В таком случае любой модуль, использующий этот супертип, будет полиморфным. С другой стороны, если супертип имеет собственные объекты, некоторые модули могут использовать только его, не используя ни один из его подтипов.

Использование иерархии для поддержки полиморфизма означает, что полиморфный модуль задумывается для использования супертипа, а каждый тип, который должен использоваться этим модулем, объявляется подтипом этого супертипа. Когда супертипы вводятся до подтипов, иерархия — хороший способ отразить эти отношения. Супертип добавляется в пространство типов в момент своего создания, а подтипы добавляются позже — ниже него.

Если типы существуют до установления взаимосвязи, иерархия работает не так хорошо. В таком случае введение супертипа усложняет пространство типов: новый тип (супертип) должен быть добавлен, все типы, используемые полиморфным модулем, должны быть подчинены ему, а классы, реализующие эти подтипы, должны быть изменены для отражения иерархии (и перекомпилированы, если система использует компиляцию). Например, нам пришлось бы добавить в пространство новый тип — «сортируемый» — и сделать каждый тип элемента его подтипом. Следует учитывать каждый такой супертип при создании нового типа: каждый новый тип должен быть объявлен подтипом этого супертипа, если есть хоть какая-то вероятность, что нам понадобится использовать его объекты в полиморфном модуле. Кроме того, супертип может оказаться бесполезным с точки зрения совместного использования кода, поскольку в нем, возможно, нечего и реализовывать.

Альтернативный подход — просто разрешить полиморфному модулю использовать любой тип, предоставляющий необходимые операции. В этом случае не предпринимается никаких попыток связать типы. Вместо этого объект, принадлежащий любому из связанных типов, может быть передан в качестве аргумента полиморфному модулю. Таким образом, мы получаем тот же результат, но без необходимости усложнять пространство типов. Мы будем называть это подходом группировки.

Два подхода различаются требованиями к рассуждениям о корректности программы. В обоих случаях необходимо, чтобы объекты-аргументы имели операции с правильными сигнатурой и поведением. Требования к сигнатурам могут быть удовлетворены проверкой типов, которая может происходить как во время выполнения, так и на этапе компиляции. Проверка во время выполнения не требует специальных механизмов: объекты просто передаются в полиморфный модуль, и ошибки типов будут выявлены при отсутствии необходимой операции. Проверка на этапе компиляции требует адекватной системы типов. При использовании подхода с иерархией язык должен сочетать проверку типов на этапе компиляции с наследованием; пример такого языка обсуждается в [17]. При использовании подхода группировки необходим способ выражения ограничений на операции на этапе компиляции. Например, на это способны и CLU, и Ada [19]. В CLU заголовок процедуры sort может выглядеть так:

sort = proc [T: type] (a: array[T])
where T has lt: proctype (T, T) returns (bool)

Этот заголовок ограничивает параметр T типом, имеющим операцию с именем lt и указанной сигнатурой; спецификация sort объясняет, что lt должна быть проверкой на «меньше чем» (less than). Пример вызова sort:

sort[int](x)

При компиляции такого вызова компилятор проверяет, что тип x — это array[int], а также что int имеет операцию lt с требуемой сигнатурой. В CLU можно определить еще более полиморфную подпрограмму сортировки, которая работала бы с любыми «массивоподобными» коллекциями, то есть такими, элементы которых можно получать и изменять по индексу.

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

И группировка, и иерархия имеют свои ограничения. При использовании полиморфного модуля желательно иметь больше гибкости. Например, если sort вызывается с операцией проверки на «больше чем», это приведет к иному порядку сортировки массива, но этот иной порядок может быть именно тем, что нужно. Кроме того, могут возникать конфликты между типами, предназначенными для использования в полиморфном модуле:

1. Не все типы предоставляют требуемую операцию.

2. Типы используют разные имена для этой операции.

3. Некоторые типы используют имя требуемой операции для какой-то другой операции; например, имя lt используется в типе T для обозначения операции «длина» (length).

Один из способов достичь большей обобщенности — просто передавать требуемые операции в качестве аргументов процедуры; например, sort принимает два аргумента: массив и подпрограмму, определяющую порядок сортировки [4*]. Этот метод универсален, но может оказаться неудобным. В Argus [10] и Ada существуют методы, которые в сочетании с подходом группировки позволяют избежать этого неудобства.

Таким образом, когда связанные типы выявляются на раннем этапе проектирования, иерархия — хороший способ выражения взаимосвязи. В ином случае лучше подойдет либо подход с группировкой (при соответствующей языковой поддержке), либо использование процедур в качестве аргументов.

5.2. Множественные реализации

Часто полезно иметь несколько реализаций одного типа. Например, для одних матриц мы используем разреженное представление, а для других — неразреженное. Кроме того, иногда желательно использовать объекты одного типа, но с разными представлениями, в рамках одной программы.

Объектно-ориентированные языки, по-видимому, позволяют пользователям имитировать множественные реализации с помощью наследования. Каждая реализация была бы подклассом некоторого другого класса, реализующего этот тип. Этот класс, вероятно, был бы виртуальным; например, существовал бы виртуальный класс, реализующий матрицы, и подклассы, реализующие разреженные и неразреженные матрицы.

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

Проблема возникает из-за того, что наследование используется для двух разных целей: для реализации типа и для указания, что один тип является подтипом другого. Эти подходы следует разделять. Тогда мы сможем получить именно то, что хотим: два типа (матрица и расширенная матрица), один — подтип другого, у каждого есть несколько реализаций, а также возможность по-разному сочетать реализации подтипа с реализациями супертипа.

6. Выводы

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

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

Наследование можно использовать для реализации иерархии подтипов. Оно необходимо главным образом в случае связанных типов, когда супертип создается первым, поскольку здесь удобно реализовать общий функционал один раз в суперклассе, а затем реализовывать расширения отдельно для каждого подтипа.

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

Благодарности

Многие люди высказывали замечания и предложения, которые улучшили содержание этой статьи. Автор с благодарностью признает эту помощь и особенно усилия Тоби Блума и Гэри Ливинса.

Примечания

[1*] Мы не рассматриваем переменные класса, поскольку они не имеют значения для тех различий, которые мы пытаемся провести. В CLU есть аналогичный механизм: у кластера могут быть «собственные» переменные [9].

[2*] Мы не рассматриваем здесь множественное наследование, чтобы упростить изложение.

[3*] Ему нужны методы экземпляра, но не методы класса.

[4*] Такое решение, конечно же, не будет нормально работать в Smalltalk, поскольку в нем нет удобного способа определять процедуры как отдельные сущности или рассматривать их как объекты.

Источники

[1] Bobrow В. et al. CommonLoops: Merging Common Lisp and Object-Oriented Programming // Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications, ACM SIGPLAN Notices, vol. 21, № 11, November 1986.

[2] Bruce K., Wegner P. An Algebraic Model of Subtypes in Object-Oriented Languages (Draft) // ACM SIGPLAN Notices, vol. 21, № 10, October 1986.

[3] Дал У.-И., Хоор К. Иерархические структуры программ // Дал У.-И., Дейкстра Э., Хоор К. Структурное программирование. М.: Издательство «Мир», 1975.

[4] Goldberg A., Robson D. Smalltalk-80: The Language and its Implementation. Reading: Addison-Wesley, 1983.

[5] Hoare C.A.R. Proof of Correctness of Data Representations // Acta Informatica, vol. 1, № 4, 1972

[6] Leavens G. Subtyping and Generic Invocation: Semantics and Language Design. Ph.D. Th., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science (готовится к публикации).

[7] Liskov B. A Design Methodology for Reliable Software Systems // Freeman P., Wasserman A. (eds.) Tutorial on Software Design Techniques. Long Beach: IEEE Computer Society, 1977. Также опубликовано в: Proceedings of the Fall Joint Computer Conference, 1972.

[8] Liskov B., Snyder A., Atkinson R.R., Schaffert J.C. Abstraction Mechanisms in CLU // Communications of the ACM, vol. 20, № 8, August 1977.

[9] Liskov B. et al. CLU Reference Manual. Springer-Verlag, 1984.

[10] Liskov B. et al. Argus Reference Manual. Technical Report MIT/LCS/TR-400, M.I.T. Laboratory for Computer Science, Cambridge, Massachusetts, 1987.

[11] Лисков Б., Гатэг Д. Использование абстракций и спецификаций при разработке программ. М.: Издательство «Мир», 1989.

[12] Liskov B., Zilles S. Programming with Abstract Data Types // Proceedings of ACM SIGPLAN Conference on Very High Level Languages, ACM SIGPLAN Notices, vol. 9, № 4, 1974.

[13] Moon D.A. Object-Oriented Programming with Flavors // Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications, ACM SIGPLAN Notices, vol. 21, № 11, November 1986.

[14] Morris J.H. Protection in Programming Languages // Communications of the ACM, vol. 16, № 1, January 1973.

[15] Parnas D. Information Distribution Aspects of Design Methodology // Freiman C.V., Griffith J.E., Rosenfeld J.L. (eds.) Information Processing 71: Proceedings of the IFIP Congress. North Holland Publishing Co., 1971.

[16] Парнас Д. О критериях для разбиения систем на модули // https://habr.com/ru/articles/957968/.

[17] Schaffert C. et al. An Introduction to Trellis/Owl // Conference Proceedings on Object-Oriented Programming Systems, Languages and Applications, ACM SIGPLAN Notices, vol. 21, № 11, November 1986.

[18] Снайдер А. Инкапсуляция и наследование в объектно-ориентированных языках программирования // https://habr.com/ru/articles/1047584/.

[19] U.S. Department of Defense. Reference Manual for the Ada Programming Language, 1983. ANSI Standard Ada.