Пратт Т. Языки программирования. Разработка и реализация

Подождите немного. Документ загружается.

305

7.1. Повторное рассмотрение абстрактных типов данных

типа даны в конце пакета в компоненте private. Только подпрограммы, определен"

ные в самом пакете, имеют доступ к этим закрытым данным. Так, например, про"

цедуры AssignStudent и CreateSection могут обращаться к массиву ClassRoll, кото"

рый является одним из компонентов типа Section. Но никакие другие процедуры,

внешние по отношению к пакету, не имеют доступа к этому компоненту, хотя мо"

гут объявлять переменные как объекты типа Section (и указывать значение пара"

метра, задающего максимальное количество студентов в группе).

Реализация. Определение абстрактных типов данных в виде пакетов Ada не

затрагивает никаких новых идей, относящихся к их реализации. Пакет обеспечи"

вает инкапсуляцию для множества определений типов и подпрограмм. Таким об"

разом, его основное достижение заключается в ограничении видимости имен, объяв"

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

доступа ко внутренним элементам определения. Если же компилятор определяет,

что некоторая процедура имеет доступ к определению типа, то применяются алго"

ритмы размещения объектов данных в памяти и доступа к ним, описанные в пре"

дыдущих главах.

Хотя, как только что было сказано, реализация пакетов языка Ada не использу"

ет новые идеи реализации, все же стоит рассмотреть концепцию пакетов более

подробно. Каждый пакет состоит из двух частей: спецификации и реализации. Как

видно из листинга 7.1, спецификация пакета

SectionType определяет все данные,

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

в других пакетах. Реализация процедур, объявленных в спецификации пакета, за"

дается в компоненте package body (тело пакета). В тело пакета могут входить также

дополнительные объекты и типы данных, которые не должны быть видны из дру"

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

дур AssignStudent и CreateSection, и ее имя просто неизвестно вне данного пакета.

Листинг 7.1. Определение абстрактного типа данных Section в языке Ada

package SectionType is

type StudentID is integer;

type Section(MaxSize: integer) is private;

procedure AssignStudent(Sect: in out Section;

Stud in StudentID);

procedure CreateSection(Sect: in out Section;

Instr in integer;

Room in integer);

private

type Section(MaxSize: integer) is

record

Room:integer;

Instructor: integer;

ClassSize: integer range 0..MaxSize := 0;

ClassRoll: array (1..MaxSize) of StudentID;

end record;

end;

package body SectionType is

procedure AssignStudent(¼) is

— Îïåðàòîðû, âñòàâëÿþùèå îáúåêò student â ClassRoll

end;

procedure CreateSection(¼) is

продолжение ®

306 Глава 7. Наследование

Листинг 7.1 (продолжение)

— Îïåðàòîðû, èíèöèàëèçèðóþùèå êîìïîíåíòû çàïèñè Section

end;

procedure SheduleRoom(¼) is

— Îïåðàòîðû, îïðåäåëÿþùèå ðàñïèñàíèå ëåêöèé â àóäèòîðèè

end;

Необходимость указания имени процедуры в спецификации пакета объясняется

достаточно просто: компилятору нужно знать сигнатуру процедуры, если она вы"

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

задаются именно в спецификации пакета. Например, при вызове процедуры Assign-

Student

из подпрограммы какого"либо другого пакета необходима информация о том,

что у данной процедуры имеются два фактических параметра: один типа Section

(являющийся одновременно входным и выходным in out) и второй параметр типа

StudentID (являющийся только входным in ).

Но почему же определения закрытых данных, которые используются только

в теле данного пакета и неизвестны за его пределами, также помещаются в его

спецификации? Казалось бы, проще ограничиться помещением их в тело пакета.

Чтобы понять, почему в языке Ada пакеты определены именно таким образом,

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

На рис. 7.1 представлены две модели реализации инкапсулированных объек"

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

ции. В этом случае структура абстрактного типа данных определяется специфика"

цией пакета A. Фактическое местоположение объекта P задается и контролируется

в записи активации для пакета A. В записи активации пакета B, который объявляет

и использует объект P, содержится указатель на фактическое местоположение

объекта.

Рис. 7.1. Две модели реализации абстрактных типов данных: а — непрямая инкапсуляция

объекта P; б — прямая инкапсуляция объекта P

Альтернативная реализация, называемая прямой инкапсуляцией, схематически

изображена на рис. 7.1, б. Как и в случае непрямой инкапсуляции, структура объекта

данных абстрактного типа определена в спецификации для пакета A. Но теперь

фактическое местоположение объекта P контролируется записью активации для

пакета B.

307

В чем же разница между этими двумя способами? В случае непрямой инкапсу"

ляции реализация абстрактного типа данных действительно не зависит от его ис"

пользования. Если потребуется изменить внутреннюю структуру объекта

P, то при"

дется менять только пакет A. Пакету B только необходимо «знать», что объект P

является просто указателем, а формат данных, на который указывает P, для пакета B

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

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

вать каждый модуль, где используется объект, определение которого поменялось;

за счет этого можно значительно сэкономить время.

Но, с другой стороны, при использовании этого способа дополнительное время

тратится на доступ к инкапсулированным объектам при выполнении программы.

Доступ к объекту P каждый раз подразумевает обращение к указателю на этот

объект. Хотя само по себе это действие не связано со значительными затратами

времени, многократное обращение к объекту через указатель может оказаться до"

вольно дорогостоящим.

Прямая инкапсуляция характеризуется прямо противоположными свойства"

ми. В данном случае объект данных

P хранится в записи активации пакета B. До"

ступ к компонентам объекта P теперь может быть осуществлен быстрее, поскольку

в пределах локальной записи активации можно применить стандартную технику

доступа к объектам данных по формуле áàçîâûé àäðåñ + ñäâèã; в данном случае не

требуется никаких промежуточных указателей. Но если представление объекта

данных меняется, то все пакеты (например, пакет B), в которых этот объект ис"

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

компиляцию, но ускоряет выполнение программы.

В языке Ada используется прямая модель инкапсуляции, которая обеспечива"

ет максимальную эффективность выполнения программы. При трансляции исполь"

зуемого в пакете объекта абстрактного типа (например, объекта P в пакете B на

рис. 7.1, б) требуется информация о деталях представления объекта. Этим и объяс"

няется необходимость раздела private в спецификации пакета.

Заметим, однако, что и прямая, и непрямая модели инкапсуляции могут ис"

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

от модели, реализованной как часть программной архитектуры используемого язы"

ка программирования. Хотя в реализации самого языка Ada предпочтение отдано

модели прямой инкапсуляции, которая и используется в нем по умолчанию, не"

прямая инкапсуляция может быть реализована самим программистом. В листин"

гах 7.2 и 7.3 приведены фрагменты пакетов Ada, демонстрирующие применение

обеих стратегий реализации инкапсуляции. Листинг 7.2 соответствует модели, схе"

матически изображенной на рис. 7.1, а (access — переменная"указатель в языке Ada),

а листинг 7.3 — модели, представленной на рис. 7.1, б.

Листинг 7.2. Пример непрямой инкапсуляции данных в языке Ada

package A is

type MyStack is private;

procedure NewStack(S: out MyStack);

…

private

type MyStackRep;

продолжение ®

7.1. Повторное рассмотрение абстрактных типов данных

308 Глава 7. Наследование

Листинг 7.2 (продолжение)

— Ñêðûòûå äåòàëè ïðåäñòàâëåíèÿ MyStack

type Mystack is access MyStackRep;

— Â ïàêåòå B ñîäåðæèòñÿ òîëüêî óêàçàòåëü íà ñòåê

end;

Листинг 7.3. Пример прямой инкапсуляции данных в языке Ada

package A is

type MyStack is private;

procedure NewStack(S: out MyStack);

…

private

type MyStack is record;

Top: integer;

A: array (1..100) of integer;

end record;

— Â ïàêåòå B ñîäåðæèòñÿ èíôîðìàöèÿ î ñòðóêòóðå ñòåêà

end;

Некоторая разновидность прямой инкапсуляции, пример которой приведен

в листинге 7.3, дается следующим определением типа:

package A is

type MyStack is record

Top: integer;

A: array (1..100) of integer;

end record;

В данном случае организация записи активации совпадает с моделью прямой

инкапсуляции; тем не менее все имена переменных из пакета B видны. Этот меха"

низм характерен для языков типа Pascal, в которых типы данных реализованы без

инкапсуляции.

Общие абстрактные типы данных

Элементарные типы данных, встроенные в язык, часто позволяют программисту

объявлять базовый тип для нового класса объектов данных и затем уточнять неко"

торые атрибуты последних. Это простая форма полиморфизма, который более под"

робно обсуждается в разделе 7.3. Например, в языке Java имеется базовый тип

данных массив, для которого определены некоторые элементарные операции, на"

пример операция индексации. Однако в определении класса Vect (в нижеследую"

щем примере) в Java задается определение массива Vect.X, который содержит объек"

ты целого типа:

class Vect {int [] X = new int [10]}

Здесь X является массивом из десяти компонентов целого типа, доступ к кото"

рым осуществляется при помощи индексов 0, 1, 2, …, 9. Можно написать подпро"

граммы, которые будут манипулировать объектами класса Vect, но те операции,

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

массивов), будут также оставаться доступными.

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

подобную структуру. Например, в языке Ada определение нового абстрактного типа

данных стек с операциями push и pop, которые вставляют и удаляют элементы сте"

ка, можно реализовать в форме пакета, текст которого приведен в листинге 7.4.

309

Отметим возникающую здесь проблему: определение типа элемента стека являет"

ся частью общего определения стека, поэтому наше определение является опреде"

лением только стека целых чисел. Для стека вещественных чисел или объектов

типа

Section требуется отдельное определение в другом пакете, хотя представле"

ние стека и операций push и pop может быть определено точно таким же образом.

Листинг 7.4. Определение стека целых чисел как абстрактного типа данных

в языке Ada

package IntStackType is

type Stack(Size: Positive) is private;

procedure Push(I: in integer; S: in out Stack);

procedure Pop(I: out integer; S: in out Stack);

private

type Stack(Size: Positive) is record

StkStorage: array (1..Size) of integer;

Top: integer range 0..Size := 0;

end record;

end IntStackType;

package body IntStackType is

procedure Push(I: in integer; S: in out Stack)is

begin

— Òåëî ïðîöåäóðû Push

end;

procedure Pop(I: out integer; S: in out Stack)is

begin

— Òåëî ïðîöåäóðû Pop

end;

end IntStackType;

Определение общих абстрактных типов данных позволяет такой атрибут типа

задавать отдельно, для того чтобы дать определение одного базового типа с атри"

бутами в виде параметров с последующим созданием нескольких специализиро"

ванных типов, выведенных из одного и того же базового типа. Эта структура похо"

жа на структуру определения типа с параметрами, за исключением того, что в ней

параметры могут влиять не только на определение самого типа, но и на определе"

ние операций в определении абстрактного типа, а параметрами могут быть не только

числовые значения, но и имена типов. Пакет Ada, приведенный в листинге 7.5, дает

пример такого определения общего типа для типа общий стек, в котором и тип

хранимого в стеке элемента, и максимальный размер стека определены как пара"

метры этого общего типа.

Листинг 7.5. Абстракция общего стека в языке Ada

generic

type Elem is private;

package AnyStackType is

type Stack(Size: Pozitive) is private;

procedure Push(I: in Elem; S: in out Stack);

procedure Pop(I: out Elem; S: in out Stack);

private

type Stack(Size: Pozitive) is record

StkStorage: array (1.. Size) of Elem;

Top: integer range 0..Size := 0;

end record;

продолжение ®

7.1. Повторное рассмотрение абстрактных типов данных

310 Глава 7. Наследование

Листинг 7.5 (продолжение)

end AnyStackType;

package body AnyStackType is

procedure Push(I: in Elem; S: in out Stack)is

begin

— Òåëî ïðîöåäóðû Push

end;

procedure Pop(I: out Elem; S: in out Stack)is

begin

— Òåëî ïðîöåäóðû Pop

end;

end AnyStackType;

Порождение конкретного типа из определения общего типа. Определение

общего пакета представляет собой шаблон, который можно использовать для соз"

дания определения конкретного типа данных. Процесс конструирования конкрет"

ного определения типа из общего определения для заданного набора параметров

называется порождением (instantiation), или созданием, типа. Например, из обще"

го определения стека, приведенного в листинге 7.5, можно создать определение

стека целых чисел, эквивалентного тому, который определен в пакете

IntStackType

(см. листинг 7.4), при помощи объявления

package IntStackType is

new AnyStackType(elem => integer);

Стек, содержащий данные типа Section, можно определить при помощи следу"

ющего порождения:

package SetStackType is

new AnyStackType(elem => Section);

Далее можно определять стеки целых чисел, имеющие различные максималь"

ные размеры:

Stk1: IntStackType.Stack(100);

NewStk: IntStackType.Stak(20);

Аналогично можно задавать размеры стеков, содержащих объекты типа Section:

SecStack: SetStackType.Stack(10);

Отметим, что общий тип AnyStackType можно использовать для порождения кон"

кретных типов много раз с различными значениями параметров, и каждый раз мы

будем получать другое определение типа с именем Stack в соответствующем пакете.

Таким образом, при ссылке на тип Stack в каком"либо объявлении программы может

возникнуть неоднозначность. Для ее разрешения язык Ada требует, чтобы имя паке"

та предшествовало имени типа, например IntStackType.Stack или SetStackType.Stack.

В C++ имеется аналогичное понятие шаблон (template), который используется

для определения общих классов, например:

template <class èìÿ_òèïà> class èìÿ_êëàññà îïðåäåëåíèå_êëàññà

Здесь задается неограниченное множество определений классов для всех пара"

метров имя_типа.

Реализация. Реализация общих типов данных, в принципе, осуществляется

непосредственно. Когда в программе создается определение типа, требуется пере"

дать в пакет с определением общего типа конкретные значения параметров. Ком"

пилятор использует определение общего типа как шаблон, вставляя в него задан"

311

ные значения параметров и компилируя затем определение так же, как если бы

оно было обычным пакетным определением без параметров. Этот способ можно

сравнить с макроопределениями

#define в языке C. В процессе выполнения про"

граммы появляются только объекты данных и подпрограммы; определение пакета

служит в первую очередь для того, чтобы ограничить область видимости этих объек"

тов данных и подпрограмм. Сами пакеты не являются частью структуры исполня"

емого кода программы.

Если в программе на основе определения общего порождается много кон"

кретных типов (как могло бы случиться, если бы пакет с определениями общих

типов поставлялся в виде библиотеки), то такая непосредственная реализация

может оказаться слишком неэффективной, так как каждое порождение нового

конкретного типа требует включения в программу копии всего пакета вместе со

всеми определенными в нем подпрограммами, которые затем должны быть зано"

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

создания новой копии каждой подпрограммы, а также полной перекомпиляции

всего пакета. Эта тема подробнее обсуждается в разделе 7.3, посвященном поли"

морфизму.

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

Информация, известная в одной части программы, часто должна использоваться

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

щей подпрограммы в качестве формальных параметров некоторой вызываемой под"

программы представляет собой механизм передачи значений фактических пара"

метров вызывающей подпрограммы в вызываемую подпрограмму. В данном случае

эта связь между различными частями программы осуществляется явным образом —

ее формирует конкретный вызов подпрограммы.

Тем не менее довольно часто информация от одного компонента программы

к другому передается неявным образом. Такая передача информации называется

наследованием. Наследование можно определить как получение каким"либо ком"

понентом подпрограммы свойств или характеристик некоторого другого компо"

нента в соответствии со специальными отношениями, существующими между эти"

ми компонентами. Концепция наследования часто применяется при разработке

языков программирования.

Раннюю форму наследования можно обнаружить в правилах определения об"

ласти видимости для структурированных блоков данных. Имена, используемые

во внутреннем блоке, могут быть унаследованы из внешнего блока. Рассмотрим,

например, следующий блок данных:

{int i, j;

{float j, k;

k = i + j;}

}

В операторе присваивания k = i + j и k, и j являются локальными веществен"

ными переменными, объявленными во внутреннем блоке. Но переменная i уна"

следована из внешнего блока, а наследование объявления int j блокируется во

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

312 Глава 7. Наследование

внутреннем блоке благодаря переопределению типа переменной j как веществен"

ного.

Хотя правила определения области видимости в языках Ada, C и Pascal явля"

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

на передачу данных и функций между независимыми модулями программы. При"

мером этого является конструкция class в языке C++. Если между классами A и B

установлено отношение, которые можно записать как A ⇒ B, то некоторые объек"

ты класса A будут неявным образом унаследованы и могут быть использованы

в классе B. Если некоторый объект X объявлен в классе A и не переопределен в клас"

се B, то любая ссылка на объект X внутри класса B в силу наследования фактически

является ссылкой на объект X из класса A, что аналогично ссылке на переменную i

в приведенном выше примере из языка C.

Если между классами A и B определено отношение A ⇒ B, то говорят, что класс A

является родительским классом, или суперклассом, а класс B— зависимым, или до

черним, классом, или подклассом. Класс

A является прямым предком, или родите

лем класса B. На рис. 7.2, а класс A является прямым предком для классов B и C,

которые друг для друга являются ближайшими родственниками одного «поколе"

ния». Классы B и Ñ являются прямыми потомками класса A, тогда как класс D явля"

ется просто потомком класса A. Если некоторый класс имеет только одного роди"

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

родителей, то такая форма наследования называется множественной.

Рис. 7.2. Наследование: а — простое; б — множественное

Множественное наследование допустимо в C++, но не в Java. В языке Ada 95

добавлены помеченные (tagged) типы, реализующие форму наследования, при

которой объекты, объявленные как tagged private, могут быть использованы в но"

вом пакете с дополнительными компонентами. Ниже приводится несколько при"

меров:

type Calendar is tagged private;

…

private

type Calendar is tagged record

Day: integer;

Month: integer;

end record

313

type AnnualCalendar is new Calendar with record

Year: integer;

end record

7.2.1. Производные классы

Классы в языках, подобных C++, Java и Smalltalk, тесно связаны с концепцией

инкапсуляции. Обычно класс состоит из двух частей: одна может быть унаследо"

вана каким"либо другим классом, а другая остается скрытой от внешних воздей"

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

в Ada (см. листинг 7.4) могут быть представлены в C++ как

class intstack

{private:

int size;

int storage(100); }

или в Java

class intstack

{private int size;

int [] storage = new int[100]; }

Имя intstack — это имя класса, известное за его пределами, в то время как объяв"

ления переменных size и storage, следующие за модификатором переменных private,

как и в языке Ada, представляют собой компоненты класса intstack, которые изве"

стны только внутри класса.

В понятие абстракции типа данных, как говорилось выше, входят и описания

данных, и функции, которые могут оперировать данными этого типа. Такие функ"

ции часто называются методами. Более полное описание класса intstack, в кото"

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

class intstack

{public:

intstack() {size=0;}

void push(int i) { storage[size++]=i;}

int pop …

private:

int size;

int storage(100);

}

Модификатор public означает, что соответствующие имена видимы за предела"

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

в определение класса функция intstack(), имя которой совпадает с именем класса,

является специальной функцией, называемой конструктором, и вызывается каж"

дый раз, когда создается объект этого класса. В данном случае эта функция иници"

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

циализации, необходимый для создания объектов этого класса. В этом примере

функции push и pop могут быть вызваны и использованы за пределами определе"

ния класса как методы объектов класса intstack, например b.push(7) или j = b.pop()

для стека b. Имена size и storage, напротив, известны только в пределах определе"

ния класса.

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

314 Глава 7. Наследование

Для уничтожения объекта класса intstack и высвобождения занимаемого им

места в памяти следовало бы определить специальную функцию ~intstack, кото"

рая называется деструктором. В приведенном примере деструктор не нужен. Но

если бы конструктор отводил в памяти какое"то дополнительное место, требуемое

для объектов класса, то деструктор был бы необходим для его освобождения впо"

следствии.

Запись b.push(7) не так уж необычна, как может показаться на первый взгляд.

Определения классов похожи на определения типов в языке C, за тем исключени"

ем, что в определение класса входят еще и компоненты"функции, манипулирую"

щие объектами этого класса. Таким образом, b.push — это компонент"функция push

объекта b. Сходство между понятием класса в C++ и Java и конструкцией sruct

в языке C не является случайным. Объявление в языке C

srtuct A {int B} —

это просто сокращенная запись объявления C++

class A {public: int B}

В определение класса, таким образом, могут входить и определения функций,

и определения данных.

Наследование в Java и С++ происходит при помощи производных классов. На"

пример, один класс может содержать объекты типа elem, а в другом классе эти

объекты могут использоваться для создания стеков, как показано в листинге 7.6.

Имя ElemStack, которое следует за ключевым словом class, представляет произ"

водный класс, а имя, непосредственно следующее за двоеточием после имени класса

ElemStack, обозначает базовый класс (имя elem). (В языке Java для указания базо"

вого класса вместо двоеточия используется ключевое слово extends.) Если рассмат"

ривать операции класса просто как компоненты определения объектов этого клас"

са, то понять синтаксис достаточно легко. Запись x.ToElem(…) становится ссылкой

на метод, определенный в классе elem, в результате которой вызывается процедура

ToElem, неявным аргументом которой является объект x.

Листинг 7.6. Производные классы в C++

class elem {

public:

elem() { v=0;}

void ToElem(int b) { v = b;}

int FromElem() { return v; }

private:

int v; }

class ElemStack: elem {

public:

ElemStack() { size=0;}

void push(elem i)

{ size=size+1; storage[size]=i;}

elem pop()

{ size=size-1; return storage[size+1]}

private:

int size;

elem storage[100]; }

{ elem x;

ElemStack y;