Универсализация

Разбить на страницы

Показывать лекцию целиком

Горизонтальное и вертикальное обобщение типа

(рис 10.1) Размерности обобщения

Уже изученные механизмы позволяют написать класс, помещенный в центр рисунка - LIST_OF_BOOKS, экземпляр которого представляет список книг. У класса следующие компоненты: put для вставки элемента, remove для удаления элемента, count для подсчета числа элементов и т.д. Очевидны два пути обобщения понятия LIST_OF_BOOKS.

Списки являются специальным видом структур, представляющих контейнеры. Из многих других примеров контейнеров отметим деревья, стеки и массивы. В сравнение со списком LIST_OF_BOOKS, более абстрактным вариантом контейнера является класс SET_OF_BOOKS (множество книг). Более специализированным вариантом является класс LINKED_LIST_OF_BOOKS, определяющий связный список книг - специализированный вариант списка. Три класса задают вертикальную размерность на рисунке - размерность наследования.

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

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

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

Необходимость параметризованных классов

Универсализация уже рассматривалась в данной книге, но не применялась для классов. Мы столкнулись с ней при обзоре традиционных подходов к повторному использованию и при изучении математической модели класса - АТД, где была показана необходимость определения параметризированного АТД.

Родовые АТД

Наш работающий пример АТД, STACK, был объявлен с параметром, как STACK [G]. Любое его использование заставляет специфицировать "фактический родовой параметр", представляющий тип хранимого в стеке объекта. Имя G, используемое в спецификации АТД, - формальный родовой параметр класса. Оно указывает, что элементы стека могут иметь любой возможный тип. При таком подходе можно использовать одну спецификацию для всех возможных стеков. Альтернативой, вряд ли приемлемой, было бы введение множества классов: INTEGER_STACK, REAL_STACK и т.д.

Любые АТД, описывающие контейнеры: множества, списки, матрицы, массивы и многие другие, очевидно, также должны быть родовыми.

Это решение применимо к контейнерам классам, также как к контейнерам АТД.

Проблема

Рассмотрим пример стека, но уже не как АТД, а как класс. Мы знаем, как написать класс INTEGER_STACK, задающий стек объектов типа INTEGER. Компоненты будут включать count (число элементов), put (вталкивание элемента), item (элемент в вершине), remove (выталкивание элемента), empty (пустой ли стек?).

Тип INTEGER будет часто использоваться в объявлениях этого класса. Например, это тип аргумента для put и результата для item:

put (element: INTEGER) is
            -- Втолкнуть элемент (в вершину стека).
      do ... end
item: INTEGER is
            -- Элемент в вершине стека
      do ... end

Эти появления типа INTEGER следуют из правила явного объявления, используемого при разработке нотации: всякий раз при введении сущности, обозначающей возможные объекты времени выполнения, необходимо явное указание ее типа, такое как element: INTEGER. Здесь это означает, что необходимо указать тип для запроса item, для аргумента element процедуры put и для других сущностей, обозначающих возможные элементы стека.

Как следствие, придется писать различные классы для каждого сорта стека: INTEGER_STACK, REAL_STACK, POINT_STACK, BOOK_STACK... Все эти стековые классы будут одинаковыми за исключением объявления типов item, element и некоторых других сущностей. Основные операции над стеком не зависят от типа элементов стека и реализуются одинаково. Для всех, заинтересованных в повторном использовании, такое дублирование классов представляется мало привлекательным.

Проблема возникает из-за противоречия двух основных требований, предъявляемых к классам и сформулированных в начале этой книги.

Надежность: сохранение преимуществ безопасности типов с помощью явного объявления типа.

Повторное использование: возможность написать один программный элемент, покрывающий многие варианты одного понятия.

Роль типизации

Зачем настаивать на явном объявлении типов (первое из двух требований)? Это часть главного вопроса о типизации, которому в этой книге посвящена отдельная лекция (лекция 17). Но уже сейчас можно указать две основные причины, по которым ОО-программа должна быть статически типизирована.

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

Надежность: благодаря явному объявлению типов компилятор сможет найти ошибочные операции еще на этапе компиляции, не допуская их проявления при выполнении. В фундаментальных операциях ОО-вычислений вызов компонента имеет форму x.f (a,..), где х - некоего типа TX. Причины возникновения ошибок могут быть разными: соответствующий класс TX может не иметь метода f ; метод может существовать, но быть скрытым; количество аргументов при вызове может не совпадать с объявленным в описании класса; тип а или другого аргумента может не совпадать с ожидаемым. В языке Smalltalk, в котором отсутствует статическая типизация, любая такая ситуация приведет к краху на этапе выполнения с выдачей, например, сообщения: "Message not understood", в то время как компилятор языка с явной типизацией не пропустит ошибочной конструкции.

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

Без учета требований надежности явное объявление типов было бы не нужно так же как универсализация. Остаток этой лекции обращается к языкам со статической типизацией, т.е. языкам, которые требуют объявления каждой сущности и задают правила, позволяющие компиляторам обнаруживать несоответствие типов до выполнения. В не статически типизированных языках, таких как Smalltalk, универсализация не имеет смысла. Язык упрощается, но не защищает от схем вида:

my_stack.put (my_circle)
my_account := my_stack.item
my_account.withdraw (5000)

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

Статическая типизация защищает от подобных неудач. Совмещение типизации с требованием повторного использования приведет нас к механизму универсализации.

Родовые классы

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

Объявить тип каждой сущности, появляющейся в классе стека, включая сущности, представляющие элементы стека.

Написать класс так, чтобы он не содержал никаких намеков на тип элемента стека, и следовательно, мог использоваться для построения стеков с элементами произвольных типов.

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

Объявление родового класса

По соглашению родовой параметр обычно, использует имя G (от Generic ). Это неформальное правило. Если нужны еще родовые параметры, они будут названы H, I и т.д.

Согласно синтаксису, формальные родовые параметры заключаются в квадратные скобки, следующие за именем класса, подобно синтаксису параметризованного АТД в предыдущей лекции. Например:

indexing
      description: "Стек элементов произвольного класса G"
class STACK [G] feature
      count: INTEGER
            -- Количество элементов в стеке
      empty: BOOLEAN is
            -- Есть ли элементы?
         do ... end
      full: BOOLEAN is
            -- Стек заполнен?
         do ... end
      item: G is
            -- Вершина стека
         do ... end
      put (x: G) is
            -- Втолкнуть x в стек.
         do ... end
      remove is
            -- Вытолкнуть элемент из стека.
         do ... end
end -- class STACK

Формальный родовой параметр G можно использовать в объявлениях класса не только для результата функций (как в item ) и формальных аргументов подпрограмм (как в put ), но и для атрибутов и локальных сущностей класса.

Использование родового класса

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

sp: STACK [POINT]

Если у класса несколько родовых параметров, то соответственно столько же необходимо задать и фактических параметров.

Предоставление фактических родовых параметров родовому классу для создания типа называется родовым порождением (generic derivation), а полученный в результате класс, такой как STACK [POINT], называют параметрически порожденным классом.

Родовому порождению требуется тип, родовое порождение создает новый тип:

Результат порождения STACK [POINT] является типом.

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

Фактический параметр может быть произвольным типом. Ничто не мешает выбрать тип, который сам по себе параметрически порожден. Предположим, что мы определили другой родовой класс LIST [G], тогда можно определить стек, элементы которого являются списками точек:

slp: STACK [LIST [POINT]]

или, используя STACK [POINT] как фактический родовой параметр, - стек стеков точек:

ssp: STACK [STACK [POINT]]

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

Терминология

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

Процесс порождения нового типа, такого как STACK [POINT], из типов POINT и STACK, можно было бы называть созданием экземпляра типа "generic instantiation". Но этот термин мог бы ввести в заблуждение, поскольку в названии неявно предполагается процесс периода выполнения ПО. Заметьте, родовое порождение - статический механизм, действующий на текст программы, а не на ее выполнение.

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

Проверка типов

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

sc: STACK [CIRCLE]; sa: STACK [ACCOUNT]; c: CIRCLE; a: ACCOUNT.

Тогда в программах этого класса допустимы следующие инструкции:

sc.put (c) -- Втолкнуть круг в стек кругов
sa.put (a) -- Втолкнуть счет в стек счетов
c := sc.item -- Сущности круг присвоить вершину стека кругов.

Но каждая из следующих инструкций недопустима и будет отвергнута:

sc.put (a); -- Попытка: Втолкнуть счет в стек кругов.
sa.put (c); -- Попытка: Втолкнуть круг в стек счетов.
c:= sa.item -- Попытка: Дать кругу значение счета.

Это исключает ошибочные операции, подобные попытке вычитания денег из круга.

Правило типизации

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

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

f(a:T):U is ...

Тогда вызов вида x.f(d), появляющийся в произвольном классе B, где x типа C, будет корректен по типу, тогда и только тогда, когда:

f доступен классу B, - экспортирован всем классам или множеству классов, включающих B ;

d принадлежит типу T. Если учитывать возможность наследования, то d может принадлежать потомкам T.

Результат вызова имеет тип U. В этом примере предполагается, что компонент f является функцией.

Теперь предположим, что C родовой класс с формальным родовым параметром G имеет компонент:

h (a: G): G is...

Вызов h имеет вид y.h(e), где y сущность, объявленная как

y: C [V]

Тип V - некоторый ранее определенный тип. Теперь правило типизации - двойник неродового правила - требует, чтобы e имело тип V или при наследовании было потомком V. Аналогичное требование к результату выполнения функции h.

Требования правила понятны: V - фактический параметр, заменяющий формальный родовой параметр G параметризованного класса C, поэтому он заменяет все вхождения G при вызове компонент класса. Все предыдущие примеры следовали этой модели: вызов s.put(z) требует параметра z типа POINT, если s типа STACK [POINT] ; INTEGER если s типа STACK [INTEGER] ; и s.item возвращает результат типа POINT в первом случае и типа INTEGER во втором.

Операции над сущностями родового типа

В родовом классе C [G, H, ...] рассмотрим сущность, чей тип - один из формальных родовых параметров, например x типа G. Когда класс используется клиентом для объявления сущностей, G, разумеется, может представлять любой тип. Поэтому любая операция, которую выполняют подпрограммы C над x, должна быть применима ко всем типам. Это ограничение позволяет выполнять только пять видов операций:

Использование сущностей формального родового типа

Корректно использовать сущность x, чей тип задан формальным родовым параметром G, можно следующим образом.

Слева от оператора присваивания x := y, где выражение y также имеет тип G.

Справа от оператора присваивания y := x, где сущность y также типа G.

В логических выражениях вида x = y или x /= y, где y также типа G.

Как фактический аргумент в вызове подпрограммы на месте формальных параметров типа G, или типа ANY.

Как цель вызова компонента класса ANY.

В частности, инструкция создания вида create x неприменима, так как нам ничего неизвестно о процедурах создания, если таковые есть, для класса, определенного возможным фактическим родовым параметром, соответствующим G.

Случаи (4) и (5) ссылаются на класс ANY. Упомянутый уже несколько раз, этот класс содержит компоненты, наследуемые всеми классами. Поэтому можно быть уверенным, что независимо от фактического типа G при родовом порождении компоненты будут доступны. Компонентами класса ANY являются все основные операции копирования и сравнения объектов: clone, copy, equal, deep_clone, deep_equal и др. Поэтому для x и y формального родового типа G корректно использовать следующие инструкции:

x.copy (y)
x := clone (y)
if equal (x, y) then ...

Случай (4) разрешает вызов a.f(x) в родовом классе C [G], если f имеет формальный аргумент типа G. В частности, возможна ситуация, когда a может быть типа D [G], где D другой родовой класс. В классе D [G] объявлен компонент f, требующий аргумент типа G, обозначающий в этом случае формальный родовой параметр класса D, а не класса С. (Если предыдущая фраза не совсем понятна, перечитайте ее еще раз, и, надеюсь, она покажется столь же прозрачнойДля проверки прозрачности выполните упражнение У10.3. , как горный ручей.)

Типы и классы

Мы уже научились смотреть на класс - центральное понятие объектной технологии, - как на продукт слияния двух концепций: модуля и типа. До введения универсализации можно было говорить, что класс - это модуль, но это и тип данных.

С появлением универсализации второе утверждение перестало быть буквально истинным, хотя нюанс невелик. Родовой класс, объявленный как C [G], является не типом, а шаблоном типа, задающим бесконечное множество возможных типов. Любой тип из этого множества можно получить, предоставив фактический родовой параметр, который, в свою очередь, является типом.

Это приводит к более общему и гибкому понятию. Но за выигрыш в мощности приходится немного пожертвовать простотой: только при небольшом насилии над языком можно продолжать говорить о "компонентах класса T " или о "клиентах T ", если x объявлен, как имеющий тип T. Теперь T может быть параметрически порожденным типом C [U] из некоторого родового класса C и некоторого типа U. Конечно, основой типа остается родовой класс C, поэтому насилие над языком приемлемо.

Если требовать буквальной строгости, то терминология следующая. Любой тип T ассоциируется с базовым классом T, поэтому всегда можно говорить о компонентах и клиентах базового класса T. Если T неродовой класс, то он же является и базовым классом. Если T родовое порождение C [U, ...], то C является базовым классом T.

Базовые классы будут использоваться при введении еще одного вида типов, основанного также (как и все остальное в ОО-подходе) на классе, но косвенно: закрепленного типа (см. гл. 16.7).

Массивы

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

Массивы как объекты

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

ARRAY хороший пример родового класса. Рассмотрим первый набросок этого классаУлучшенная версия класса рассмотрена в лекции 11

indexing
      description: "Последовательность значений одного типа или согласуемых типов,%
               %доступных через целые индексы в заданном диапазоне"
class ARRAY [G] creation
      make
feature
      make (minindex, maxindex: INTEGER) is
            -- Размещение массива с границами minindex и maxindex
            -- (пустой, если minindex > maxindex)
         do ... end
      lower, upper, count: INTEGER
            -- Минимальный и максимальный допустимый индекс; размер массива.
      put (v: G; i: INTEGER) is
            -- Присвоить v элементу массива с индексом i
         do ... end
      infix "@", item (i: INTEGER): G is
            -- Элемент с индексом i
         do ... end
end -- класса ARRAY

Для создания массива a с границами m и n, тип объявления которого ARRAY [T] с заданным типом T, нужно выполнить инструкцию создания

create a.make (m, n)

Для задания значений элементов массива используется процедура put: вызов a.put(x, i) присваивает значение x i -ому элементу. Для доступа к элементам можно использовать функцию item (синоним инфиксной операции @, поясняемой позже), например:

x := a.item (i)
Вот схема того, как этот класс может быть использован клиентом:
pa: ARRAY [POINT]; p1: POINT; i, j: INTEGER
...
create pa.make (-32, 101) -- Разместить массив с указанными границами.
pa.put (p1, i) -- Присвоить значение p1 элементу с индексом i.
...
p1 := pa.item (j) -- Присвоить сущности p1 значение элемента с индексом j.

В обычной нотации (скажем, в Pascal) нужно писать:

pa [i] := p1 вместо pa.put (p1, i)

p1 := pa [i] вместо p1 := pa.item (i)

Свойства массива

Некоторые замечания о классе.

Подобные классы существуют для массивов большей размерности: ARRAY2 и т. д.

Компонент Count может быть реализован и как атрибут и как функция, поскольку count = upper - lower+1. В реальном классе это выражается инвариантом, как объясняется в следующей лекции.

Техника утверждений позволяет связывать точные условия согласования с put и item, отражая тот факт, что вызовы допустимы, только если индекс i лежит между lower и upper.

Идея описания массивов как объектов (и ARRAY как класс) - хороший пример мощности унификации и упрощения объектной технологии, позволяющей сократить нотацию до минимума и уменьшить количество узкоспециализированных конструкций. Здесь массив рассматривается как обычный пример контейнерной структуры с собственными методами доступа, представленными компонентами put и item.

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

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

Размышления об эффективности

Может ли элегантность и простота нанести удар по эффективности выполнения? Одна из причин широкого использования массивов состоит в том, что основные операции - доступ и изменение элемента - проходят быстро. Надо ли платить за каждый вызов подпрограммы при использовании item или put? Нет. То, что ARRAY для ничего не подозревающего разработчика выглядит как нормальный класс, не запрещает компилятору опираться на скрытую информацию. Она позволяет компилятору находить вызовы item и put и переопределять их так, чтобы сгенерировать такой же код, как сделает компилятор Fortran, Pascal или C для эквивалентных инструкций ( p1 := pa [i] и pa [i] := p1 в синтаксисе Pascal). Поэтому разработчик получит лучшее: универсальность, общность, упрощенность, простоту использования ОО-решения, сочетаемую с сохранением производительности традиционного решения.

Работа компилятора не тривиальна. Как выяснится при изучении наследования, для потомка класса ARRAY возможно переопределить любой компонент класса и эти переопределения могут быть косвенно вызваны через динамическое связывание. Поэтому компилятор должен выполнять тщательный анализ для проверки корректности изменений массива. Для научных приложений, интенсивно использующих массивы, современные компиляторы от ISE и других компаний сегодня могут генерировать код, столь же эффективный, как написанный вручную на C или Fortran.

Синонимичная инфиксная операция

Класс ARRAY предоставляет возможность, косвенно относящуюся к вопросам этой лекции, но полезную на практике. Объявление компонента item фактически определяет и его синоним - инфиксную операциюНотация инфиксных операций была введена в лекции 7 следующим образом:

infix "@", item (i: INTEGER): G is...

Здесь задаются два имени компонента: infix "@" и item как синонимы, обозначающие один и тот же компонент, заданный определением.

В общем, объявление компонентов в форме:

a, b, c... "Описание компонента"

рассматривается как краткая форма записи последовательности объявлений:

a "Описание компонента"
b "Описание компонента"
c "Описание компонента"
...

с одним и тем же "Описанием компонента".

Это применимо как для атрибутов (где "Описание компонента" имеет форму: некоторый_тип ), так и для подпрограмм ( is тело_программы ).

Нотация, применяемая в этом примере для доступа к массиву, достаточно проста. Она совместима с механизмами доступа для других структур, хотя, заметим, инструкция a.item(i) более многословна, чем традиционное a[i], встречающееся с некоторыми вариациями в Pascal, C, Fortran и других языках. Определяя " @ " как синоним item, можно превзойти традиционные языки в их собственной игре за краткость записи. Написав a @ i, реализуем мечту, - запись требует на одно нажатие клавиши меньше, чем даже С++!. Заметим снова, что это не специальный механизм языка, но прямое применение общей ОО-концепции, компонент-оператора, скомбинированного с нотацией синонима.

Стоимость универсализации

Как всегда нужно убедиться, что ОО-техника, введенная в интересах повторного использования, расширяемости и надежности, не влечет потерю производительности. Этот вопрос уже поднимался при рассмотрении массивов. Теперь необходимо с этих позиций проэкзаменовать механизм универсализации в целом. Какова цена универсализация?

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

Число создаваемых экземпляров шаблона - уже проблема для некоторых пользователей С++. Если пользователь создает List<int>, List<String>, List<Widget> и List<Blidget> (где Widget и Blidget классы, определенные пользователем) и вызывает head, tail и insert для всех четырех объектов, то каждая из этих функций будет создана в четырех экземплярах (из-за родового порождения). Вместо этого широко применимый класс List мог бы создать единственный экземпляр каждой функции применимый для различных типовMartin Carroll, Margaret Ellis, "Reducing Instantiation Time", in "C++ Report", vol. 6, no. 5, July-August 1994, pages 14, 16 and 64.

Авторы этого предупреждения (С++ эксперты из ATT, один из них соавтор официальной С++ документации [Ellis 1990]) продолжают предлагать различные способы, позволяющие избежать порождения шаблонов. Но универсализация не предполагает дублирование кода. При хорошо спроектированном языке и хорошем компиляторе можно генерировать единый код компонентов родового класса, так что последующие добавления потребуют минимальных затрат:

времени компиляции;

размера сгенерированного кода;

времени выполнения;

памяти, требуемой для выполнения.

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

Обсуждение: что все-таки не сделано

Основные идеи универсализации уже представлены, но как вы могли заметить, на два важных вопроса не даны ответы.

Первое: в наших усилиях гарантирования безопасности типов мы заняли чересчур консервативную позицию. Конечно, некорректно пытаться втолкнуть круг в стек банковских счетов. Трудно вообразить, какому приложению нужен стек, содержащий точки и банковские счета. Но рассмотрим графическое приложение, для которого вполне естественен стек, содержащий круги, прямоугольники, точки. Такая потребность кажется довольно разумной, но пока мы не можем удовлетворить ее. Система типов, определенная до сих пор, отвергнет вызов figure_stack.put(that_point) если тип figure_stack был объявлен как STACK [FIGURE], а that_point - тип, отличный от FIGURE. Дадим пока имя рассматриваемым структурам и назовем их полиморфными структурами данных (polymorphic data structure). Вызов, стоящий перед нами - как поддержать эти структуры без потери преимуществ безопасности типов.

Второе: родовые параметры представляют произвольные типы. Это хорошо для стеков и массивов, поскольку объекты любого типа по своей сути являются хранимыми в различных контейнерах. Но при работе, например, с векторами, хотелось бы иметь возможность складывать элементы векторов или сами векторы. При работе с классом, задающим хеш-таблицы, хотелось бы быть уверенным, что хеш-функция применима к любому элементу таблицы. Такая форма универсализации, где формальный родовой параметр уже не может быть произвольным типом, а является типом, гарантирующим предоставление ряда операций, называется ограниченной универсализацией (constrained genericity).

Для обеих этих проблем ОО-метод обеспечивает простые и элегантные решения, оба основанные на комбинировании универсализации и наследования.

Ключевые концепции

Классы могут иметь формальные родовые параметры, представляющие типы.

Родовые классы служат для описания общих контейнерных структур данных, реализуемых одинаково, независимо от элементов, которые они содержат.

Универсализация требуется только в типизированном языке, гарантирующем статически проверяемую безопасность типов.

Клиент родового класса должен предоставлять фактические типы для формальных параметров.

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

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

Более гибкое и продвинутое использование универсализации - полиморфные структуры данных и ограниченная универсализация - требует введения наследования.

Библиографические замечания

Один из первых языков, поддерживающий универсализацию - LPG [Bert 1983]. Язык Ada сделал эту концепцию широко известной введением механизма родовых пакетов.

Универсализация была также введена в языки формальной спецификации, такие как Z, CLEAR и OBJ-2, на которые были ссылки в лекции 6 по АТД. Родовой механизм, описанный здесь, был построен на основе механизма, представленного в ранней версии Z [Abrial 1980] [Abrial 1980a] и расширенного в [M 1985b].

Если не считать эту книгу, то одним из первых ОО-языков, поддерживающих универсализацию, был DEC's Trellis язык [Schaffert 1986].

Упражнения

У10.1 Ограниченная универсализация

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

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

У10.2 Двумерные массивы

Используя класс ARRAY как источник вдохновения и как основу реализации, напишите класс ARRAY2, описывающий двумерные массивы.

У10.3 Использование своего формального родового параметра фактически как чужого

Сконструируйте пример, в котором подпрограмма родового класса C [G] вызывает подпрограмму, объявленную в другом родовом классе D [G], имеющую формальный параметр типа G.

Страницы:

Горизонтальное и вертикальное обобщение типа

(рис 10.1) Размерности обобщения

Необходимость параметризованных классов

Родовые АТД

Это решение применимо к контейнерам классам, также как к контейнерам АТД.

Проблема

put (element: INTEGER) is
            -- Втолкнуть элемент (в вершину стека).
      do ... end
item: INTEGER is
            -- Элемент в вершине стека
      do ... end

Надежность: сохранение преимуществ безопасности типов с помощью явного объявления типа.

Роль типизации

my_stack.put (my_circle)
my_account := my_stack.item
my_account.withdraw (5000)

Родовые классы

Объявить тип каждой сущности, появляющейся в классе стека, включая сущности, представляющие элементы стека.

Объявление родового класса

indexing
      description: "Стек элементов произвольного класса G"
class STACK [G] feature
      count: INTEGER
            -- Количество элементов в стеке
      empty: BOOLEAN is
            -- Есть ли элементы?
         do ... end
      full: BOOLEAN is
            -- Стек заполнен?
         do ... end
      item: G is
            -- Вершина стека
         do ... end
      put (x: G) is
            -- Втолкнуть x в стек.
         do ... end
      remove is
            -- Вытолкнуть элемент из стека.
         do ... end
end -- class STACK

Использование родового класса

sp: STACK [POINT]

Родовому порождению требуется тип, родовое порождение создает новый тип:

Результат порождения STACK [POINT] является типом.

slp: STACK [LIST [POINT]]

или, используя STACK [POINT] как фактический родовой параметр, - стек стеков точек:

ssp: STACK [STACK [POINT]]

Терминология

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

Проверка типов

sc: STACK [CIRCLE]; sa: STACK [ACCOUNT]; c: CIRCLE; a: ACCOUNT.

Тогда в программах этого класса допустимы следующие инструкции:

sc.put (c) -- Втолкнуть круг в стек кругов
sa.put (a) -- Втолкнуть счет в стек счетов
c := sc.item -- Сущности круг присвоить вершину стека кругов.

Но каждая из следующих инструкций недопустима и будет отвергнута:

sc.put (a); -- Попытка: Втолкнуть счет в стек кругов.
sa.put (c); -- Попытка: Втолкнуть круг в стек счетов.
c:= sa.item -- Попытка: Дать кругу значение счета.

Это исключает ошибочные операции, подобные попытке вычитания денег из круга.

Правило типизации

f(a:T):U is ...

f доступен классу B, - экспортирован всем классам или множеству классов, включающих B ;

d принадлежит типу T. Если учитывать возможность наследования, то d может принадлежать потомкам T.

Результат вызова имеет тип U. В этом примере предполагается, что компонент f является функцией.

Теперь предположим, что C родовой класс с формальным родовым параметром G имеет компонент:

h (a: G): G is...

Вызов h имеет вид y.h(e), где y сущность, объявленная как

y: C [V]

Операции над сущностями родового типа

Использование сущностей формального родового типа

Корректно использовать сущность x, чей тип задан формальным родовым параметром G, можно следующим образом.

Слева от оператора присваивания x := y, где выражение y также имеет тип G.

Справа от оператора присваивания y := x, где сущность y также типа G.

В логических выражениях вида x = y или x /= y, где y также типа G.

Как фактический аргумент в вызове подпрограммы на месте формальных параметров типа G, или типа ANY.

Как цель вызова компонента класса ANY.

x.copy (y)
x := clone (y)
if equal (x, y) then ...

Типы и классы

Массивы

Массивы как объекты

indexing
      description: "Последовательность значений одного типа или согласуемых типов,%
               %доступных через целые индексы в заданном диапазоне"
class ARRAY [G] creation
      make
feature
      make (minindex, maxindex: INTEGER) is
            -- Размещение массива с границами minindex и maxindex
            -- (пустой, если minindex > maxindex)
         do ... end
      lower, upper, count: INTEGER
            -- Минимальный и максимальный допустимый индекс; размер массива.
      put (v: G; i: INTEGER) is
            -- Присвоить v элементу массива с индексом i
         do ... end
      infix "@", item (i: INTEGER): G is
            -- Элемент с индексом i
         do ... end
end -- класса ARRAY

create a.make (m, n)

x := a.item (i)
Вот схема того, как этот класс может быть использован клиентом:
pa: ARRAY [POINT]; p1: POINT; i, j: INTEGER
...
create pa.make (-32, 101) -- Разместить массив с указанными границами.
pa.put (p1, i) -- Присвоить значение p1 элементу с индексом i.
...
p1 := pa.item (j) -- Присвоить сущности p1 значение элемента с индексом j.

В обычной нотации (скажем, в Pascal) нужно писать:

pa [i] := p1 вместо pa.put (p1, i)

p1 := pa [i] вместо p1 := pa.item (i)

Свойства массива

Некоторые замечания о классе.

Подобные классы существуют для массивов большей размерности: ARRAY2 и т. д.

Размышления об эффективности

Синонимичная инфиксная операция

infix "@", item (i: INTEGER): G is...

В общем, объявление компонентов в форме:

a, b, c... "Описание компонента"

рассматривается как краткая форма записи последовательности объявлений:

a "Описание компонента"
b "Описание компонента"
c "Описание компонента"
...

с одним и тем же "Описанием компонента".

Стоимость универсализации

времени компиляции;

размера сгенерированного кода;

времени выполнения;

памяти, требуемой для выполнения.

Обсуждение: что все-таки не сделано

Ключевые концепции

Классы могут иметь формальные родовые параметры, представляющие типы.

Клиент родового класса должен предоставлять фактические типы для формальных параметров.

Библиографические замечания

Упражнения

У10.1 Ограниченная универсализация

У10.2 Двумерные массивы

У10.3 Использование своего формального родового параметра фактически как чужого

Занятие пройдено

Предыдущее занятие Занятие пройдено Следующее занятие

Вернуться к учебному плану

Горизонтальное и вертикальное обобщение типа

Необходимость параметризованных классов

Родовые АТД

Проблема

Роль типизации

Родовые классы

Объявление родового класса

Использование родового класса

Терминология

Проверка типов

Правило типизации

Операции над сущностями родового типа

Типы и классы

Массивы

Массивы как объекты

Свойства массива

Размышления об эффективности

Синонимичная инфиксная операция

Стоимость универсализации

Обсуждение: что все-таки не сделано

Ключевые концепции

Библиографические замечания

Упражнения

У10.1 Ограниченная универсализация

У10.2 Двумерные массивы

У10.3 Использование своего формального родового параметра фактически как чужого

Горизонтальное и вертикальное обобщение типа

Необходимость параметризованных классов

Родовые АТД

Проблема

Роль типизации

Родовые классы

Объявление родового класса

Использование родового класса

Терминология

Проверка типов

Правило типизации

Операции над сущностями родового типа

Типы и классы

Массивы

Массивы как объекты

Свойства массива

Размышления об эффективности

Синонимичная инфиксная операция

Стоимость универсализации

Обсуждение: что все-таки не сделано

Ключевые концепции

Библиографические замечания

Упражнения

У10.1 Ограниченная универсализация

У10.2 Двумерные массивы

У10.3 Использование своего формального родового параметра фактически как чужого

Купить дополнительную попытку

Вы действительно хотите купить ещё одну попытку для прохождения тестирования?

Успешно!

Напишите нам, если у вас есть вопросы

Уважаемые пользователи ИНТУИТ!

Уважаемые пользователи ИНТУИТ!

Добро пожаловать на обновлённый сайт НОУ «ИНТУИТ»!