45992 (665299), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

│Автомобиль │Лодка

┌─────*─────┐ ┌─────*─────┐

│ │ │ │

│ │ │ │

* * * *

Грузовик Легковой Байдарка Ял

автомобиль

│

│

│

*

Самосвал

Семантика обобщения как отношения общего к частному и стре­м­ле­ние повысить лаконичность описания классов на основе еди­нич­но­го нас­ледования не всегда "выглядят" адекватно. Например,

TYPE Узел = RECORD

A: Болт; B: Гайка;

END; .

Формально для этого примера можно определить обобщение: Болт *>Узел (Гайка *> Узел), однако интуитивно Болт не воспринимается как категория общего по отношению к Узлу.

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

TYPE Структура Яла = RECORD

А: Транспортное_Средство;

В: Лодка;

С: Ял;

END; .

Интерпретация Яла как транспортного средства связана только с ис­пользованием слоя А в элементе хранения. Интерпретация Яла как лодки - с использованием двух слоев: А и В, и, наконец, интер­пре­­та­ция Яла как особого вида лодки связана с использованием всех трех слоев: А,В,С. Декларация вида "Структура_Яла" в объектно-ориентированном языке заменяется отношением

Ял <* Лодка <* Транспортное_Средство.

Такая декларация определяет три возможные интерпретации объ­ек­та на разных уровнях обобщения (pасшиpения свойств).

Еще pаз подчеpкнем, что между двумя рассмотренными видами по­ли­морф­ной интер­претации объектов (записи с вариантами и нас­ле­до­ва­ние свойств) существует принципиальное различие: записи с ва­ри­антами реализуют полиморфную интерпретацию на альтернативной основе, а механизм наследованиния - на основе расширения свойств классов.

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

Пример1.

TYPE POINT = RECORD X,Y: INTEGER END;

Point = RECORD Y,X: INTEGER END;

VAR A: ARRAY[1..2] OF WORD;

P: POINTER TO POINT;

p: POINTER TO Point;

X,Y: INTEGER;

BEGIN X:=1; Y:=5;

P:=ADR(A); (*1*)

P^.X:=X; P^.Y:=Y; (*2*)

p:=ADDRESS(P); (*3*)

X:=p^.X; Y:=p^.Y (*4*)

Этот пример реализует "трансформацию" объекта-точки с де­кар­то­вы­ми координататами (1,5) в объект-точку с координатами (5,1). В про­грамме задан элемент хранения А размером в два слова, "маска" POINT, "привязанная" к указателю Р, и "маска" Point, связанная с ограниченным указателем р. Операция (1) связана с "наложением" мас­­ки POINT на элемент хранения А и записью "через трафарет" зна­­­че­ний координат точки в область памяти А. Операция (3) свя­за­на с на­ложением на ту же область памяти маски (трафарета) Point и чте­ни­ем координат точки через новый трафарет. Таким образом, один и тот же объект, размещенный в А, интерпретируется в этом примере двояко: как точка с координатами (1,5) и симметричная ей точ­ка с ко­ординатами (5,1). Заметим, что реально никакого пре­об­ра­зования координат не происходит, - все определяетсся струк­ту­рой трафарета - маски, через которуюю мы смотрим на объект. (Расссматривая этот пример, ответьте на вопрос, почему для записи операторов (2) и (4) не используется присоединение?)

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

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

VAR C: ARRAY [1..100] OF CARDINAL;

P: POINTER TO ARRAY [1..200] OF CHAR;

CH: ARRAY [1..200] OF CHAR;

BEGIN

P := ADR(C); FOR I:=1 TO 200 DO CH[I]:=P^[I] END;...

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

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

Процедурный тип (или сигнатура, см. pазд. II) определяет мно­же­ст­во возможных действий, видов активности. Например,

TYPE Действие = PROCEDURE (Станок);

определяет сигнатуру для класса Станок. Пусть множество дей­ст­вий над Станком ограничивается двумя:

PROCEDURE Включить (С: Станок);

PROCEDURE Выключить (С: Станок); .

Декларация VAR D: Действие определяет объект класса Действие. Та­кой объект может хранить потенциально возможное действие над Станком (т.е. "помнить", что нужно сделать) и (в подходящее вре­мя) акти­визироваться (самоинтерпретироваться) по отношению к стан­ку:

VAR D: Действие; C: Станок;

BEGIN...

D:=Включить;...

D(C);... D:= Выключить;... D(C); .

Операторы D(C) в этом фрагменте определяют самоинтерпретацию объ­­екта D в отношении объекта С, а операторы присваивания - оп­ре­де­ление объекта D потенциально возможным действием. Образно го­во­ря, операторы присваивания здесь "взводят курок" D, а когда D "вы­стре­лит" и какой будет эффект от этого "выстрела" (включает он ста­нок С или выключает) определяется в общем случае логикой про­г­рам­мы. Использование в программе переменных класса Действие ана­ло­гич­но наличию множества взведенных курков, при этом от­дель­ные "выс­трелы" превращаются в треск автоматных очередей - само­ин­тер­пpе­таций. Учитывая, что любое действие, связанное с такой са­мо­интер­претацией, может переопределить объекты-действия, ло­ги­ка вы­пол­нения подобных программ становится весьма запутанной. Основное при­менение этого механизма - моделирование сложных сис­тем.

V. СОЗДАНИЕ / УНИЧТОЖЕНИЕ ОБЪЕКТОВ

"Время жизни" объекта. - Классы памяти. - Управление ди­нами­чес­кой памятью. - Фрагментация. - Проблемы "висячих" ссылок и мусора. - Автоматическая память. - Локальная среда. - Активации объекта.

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

Создание объекта следует интерпретировать как выделение па­мя­ти под его элемент хранения. Такая интерпретация подразумевает раз­­де­ле­ние всего рабочего пространства памяти ЭВМ на две ка­те­го­рии, два класса - статическую память и динамическую. Первый класс памяти, как следует из этого контекста, полностью на­хо­дит­ся под упpав­ле­ни­ем тpанслятоpа и pаспpеделяется под статические объ­екты, су­ще­ству­ю­щие в системе постоянно. Например, декларация

VAR A: POINTER TO CARDINAL;

B: CARDINAL;

сообщает транслятору о необходимости "зарезервировать" в клас­се ста­тической памяти два слова под элемент хранения объекта с именем А и одно слово под элемент хранения объекта с именем В.

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

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

Управление динамической памятью для пасссивных объектов (в даль­нейшем просто динамической памятью) реализуется на основе двух ос­новных процедур (обычно импортируемых из системного модуля):

PROCEDURE ALLOCATE (VAR A: ADDRESS; N: CARDINAL);

PROCEDURE DEALLOCATE (VAR A: ADDRESS; N: CARDINAL); .

Здесь А - свободный указатель, который укажет на выделенную об­­ласть памяти (элемент хранения размером N байт) при вызове ALLOCATE и получит значение NIL (т.е. никуда не будет указывать) при освобождении этой области "из-под" А путем вызова DEALLOCATE.

Использование ограниченных указателей делает во многих от­но­ше­ни­ях целесообразным использование специальных вызовов: NEW(P) и DISPOSE(P), где VAR P: POINTER TO . (NEW и DISPOSE - псе­в­до­процедуры, их вызовы транслируются в вызовы ALLOCATE и DE­AL­LO­CA­TE соответственно). Использование NEW и DISPOSE позволяет из­бежать многих семантических ошибок, связанных с различными значениями N в последовательности вызовов ALLOCATE...DEALLOCATE, определяющей соз­дание/уничтожение одного и того же объекта.

В целом последовательность вызовов NEW...DISPOSE (или соот­вет­ст­­венно ALLOCATE...DEALLOCATE), в общем случае полностью оп­ре­­де­ля­е­мая логикой программиста, порождает ряд проблем, свя­зан­ных с ор­га­­низацией и распределением свободного пространства ди­на­мической па­мяти. Одной из таких проблем является проблема фраг­ментации. Эф­фект фрагментации заключается в том, что рабочая область ди­на­ми­чес­кой памяти "дро­бится" на части - фрагменты раз­лич­ной длины. Какие-то из них "за­няты" - используются про­г­рам­ми­стом под элементы хранения его объ­ектов, какие-то "свободны", при­чем характер че­ре­до­вания сво­бод­ных и занятых фрагментов в общем случае может быть со­вершенно произвольным. Любой запрос программиста на создание но­во­го объекта приводит к тому, что сис­тема управления динамической па­мятью "подбирает" ему фраг­мент, подходящий по размерам. Правила та­кого подбора могут быть различны, но общая закономерность одна: та­кой фрагмент должен иметь размер, не меньший, чем запрашиваемый про­граммистом. Если подходящий фрагмент имеет больший размер, чем требуется, в при­клад­ную программу будет отдана его часть, котоpая те­­пеpь будет pас­сматpиваться системой как занятый фpагмент, а ос­та­­ток ос­та­нет­ся в свободной зоне в качестве свободного фpагмента. При этом проблема фрагментации заключается в том, что эффект "дро­бле­ния" может привести к тому, что в свободной зоне будет на­хо­дить­ся мно­жество "маленьких" разрозненных свободных фрагментов, в со­во­куп­ности составляющих достаточный объем. Тем не менее, не­с­мо­тря на такой объем, запрос программиста на новый элемент памяти мо­жет получить отказ по причине отсутствия целого подходящего эле­мен­та. Ниже приведен фрагмент программы и схема распределения ди­­на­мической памяти, иллюстрирующие эффект фрагментации. При этом для простоты предполагается, что общий объем ди­на­ми­чес­кой памяти составляет 20 байт.

TYPE Треугольник = POINTER TO Фигура_1

Фигура_1 = RECORD

Сторона_1, Сторона_2, Сторона_3:CARDINAL

END;

Четырехугольник = POINTER TO Фигура_2;

Фигура_2 = RECORD

Сторона_1, Сторона_2, Сторона_3, Сторона_4:

CARDINAL

ЕND

VAR T1, T2: Треугольник; М1, М2: Четырехугольник;

BEGIN NEW(T1);... NEW(M1);... NEW(T2);...

DISPOSE(T1);... DISPOSE(T2); NEW(M2);...

┌───────────────────┐ ─┐

│ WORD │ │

├───────────────────┤ │

│ │ > Свободный фрагмент, ранее

├───────────────────┤ │ использованный под

│ │ │ объект Т1^

├───────────────────┤ ─┘─┐

│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒│ │

├───────────────────┤ │

│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒│ │

├───────────────────┤ > Фрагмент, занятый

│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒│ │ под объект М1^

├───────────────────┤ │

│▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒│ │

├───────────────────┤ ─┐─┘

│ │ │

├───────────────────┤ │

│ │ > Свободный фрагмент, ранее

├───────────────────┤ │ использованный под

│ │ │ объект Т2^

└───────────────────┘ ─┘

Иллюстрация построена для момента обработки запроса NEW(M2). В этот момент времени в динамической памяти имеются два сво­бо­д­ных фраг­мента общим объемом шесть слов, которых достаточно для вы­­пол­не­ния зап­роса на выделение элемента хранения под объект М2^ (т.е. для объ­екта, на котоpый будет указывать M2), однако фра­г­ментация не поз­­воляет системе выделить память под объект М2^.

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

BEGIN NEW(T1);...NEW(T2);...NEW(M1);...

DISPOSE(T1);...DISPOSE(T2);... NEW(M2);...

Здесь при обработке запроса NEW(M2) в пуле динамической па­мя­ти будет находиться один свободный фрагмент объема шесть слов, об­ра­зо­­ван­ный "склеиванием" элементов Т1^ и T2^, выполненным при об­ра­ботке зап­роса DISPOSE(T2). В общем случае вопросы эффективной ре­ализации управления динамической памятью, обеспечивающей ми­ни­мум отказов при ограниченном объеме, составляют отдельную проб­ле­му. Здесь мы только заметим, что с организацией выделения "пер­вого подходящего" фрагмента памяти в программировании свя­зы­ва­ют такие термины как "хип" или "куча", относящиеся скорее к про­фессиональному жаргону, чем к научно-методической тер­ми­но­ло­гии. Тем не менее эти термины до­вольно образно характеризуют прин­ципы организации динамической памяти.

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

VAR T1, T2:Треугольник;

BEGIN NEW(T1);...T2:=T1;...

DISPOSE(T1); (* T2-"висячая ссылка" *)

............

NEW(T1);...NEW(T2);...

T1:=T2; (* Остался "мусор" *)

Из этого примера понятно, что "висячая ссылка" - это ука­за­тель при­кладной программы, указывающий на свободный фрагмент ди­на­ми­чес­кой памяти. Поскольку этот фрагмент может быть выделен сис­темой по какому-либо запросу другой прикладной программе, Т2 мо­жет открыть дос­туп к "чужим" данным и "разрешить" их ин­тер­пре­тацию как тре­у­голь­ника. Последствия такой интерпретации в об­щем случае непред­ска­зуемы. Заметим, что "висячая" ссылка и "пус­тая" ссылка (имеющая значение NIL, см. pазд.III) являются со­вер­шен­но разными поня­ти­я­ми. "Мусор" - это занятый фрагмент дина­ми­чес­кой памяти, к которому в прикладной программе потерян доступ. В приведенном примере мусором оказался старый треугольник Т1^, на который указывал Т1 до пе­ре­д­виж­ки (установки на Т2). Этот мусор неустраним: программист не име­ет к нему доступа, а система управления "считает" мусор занятым фраг­ментом памяти.

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

Использование автоматической памяти связано с соз­да­ни­ем / унич­то­жением специальных элементов хранения, связанных с актив­ны­ми объ­ектами - действиями или процедурами. Любая процедура тpе­бует для выполнения собственной индивидуальной локальной сре­ды. Подобную сре­ду образуют локальные переменные, объявленные в про­цедуре, фор­маль­ные параметры, элемент хранения адреса воз­вра­та в процедуру, т.е. набор объектов, обеспечивающих выполнение дей­ствий, связанных с процедурой. Необходимость в локальной сре­де возникает только в мо­мент вызова процедуры - момент интер­пре­та­ции объекта процедурного типа. После завершения такой интер­пре­тации необходимость в локальной сре­де исчезает. Таким обра­зом, время жизни локальной среды ог­ра­ни­чи­вается временем от­ра­бот­ки программы, в которой она описана. Со­от­ветственно запрос на создание локальной среды связан с вызовом про­цедуры, а запрос на уничтожение - с окончанием фазы активности объекта (оператор RETURN или END в теле процедуры). Например:

VAR W1, W2: PROC;

PROCEDURE Работа_1;

VAR A: INTEGER;... BEGIN... W2;...

END Работа_1;

PROCEDURE Работа_2;

VAR A: INTEGER;... BEGIN... W2;...

END Работа_2;

BEGIN... W1:=Работа_1;... W2:=Работа_2;... W1;...

В этом фрагменте описаны два активных объекта процедурного типа PROC = PROCEDURE(): W1 и W2 и две процедуры без параметров: Работа_1 и Работа_2, которые могут использоваться как константы ти­па PROC. Интерпретация (активизация) W1 приведет к вызову Работы_1 и созданию локальной среды (содержащей переменную А). В процессе выполнения Работы_1 производится активизация объекта W2 и соответственно создание локальной среды для Работы_2. В любой те­кущий момент времени в системе могут быть активны несколько объ­ек­тов. (В этом примере активизация W1 приводит к активизации W2, за­тем они оба остаются в активном состоянии и затем теряют свою активность в обратной последовательности: сначала пас­си­ви­руется W2, затем W1). Последовательность активации и пассивации свя­зана с вло­женностью вызовов процедур, соответственно уп­рав­ле­ние авто­ма­ти­чес­кой памятью основывается на использовании стека - структуры, под­­держивающей такую вложенность. Ниже для этого фраг­мента при­ве­де­­на иллюстрация распределения автоматической па­мя­ти, суще­ствую­ще­го в течение совместной активности объектов W1 и W2.

┌─ ┌───────────────────┐ ─┐

│ │ Переменная А │ │

│ ├───────────────────┤ > Локальная среда

│ │ Адрес возврата │ │ для W1

Занятое прост- < ├───────────────────┤ ─┤

ранство │ │ Переменная А │ │

│ ├───────────────────┤ > Локальная среда

│ │ Адрес возврата │ │ для W2

Вершина ──> └─ │───────────────────┤ ─┤

Характеристики

Список файлов реферата