Главная » Каталог    
рефераты Разделы рефераты
рефераты
рефератыГлавная

рефератыБиология

рефератыБухгалтерский учет и аудит

рефератыВоенная кафедра

рефератыГеография

рефератыГеология

рефератыГрафология

рефератыДеньги и кредит

рефератыЕстествознание

рефератыЗоология

рефератыИнвестиции

рефератыИностранные языки

рефератыИскусство

рефератыИстория

рефератыКартография

рефератыКомпьютерные сети

рефератыКомпьютеры ЭВМ

рефератыКосметология

рефератыКультурология

рефератыЛитература

рефератыМаркетинг

рефератыМатематика

рефератыМашиностроение

рефератыМедицина

рефератыМенеджмент

рефератыМузыка

рефератыНаука и техника

рефератыПедагогика

рефератыПраво

рефератыПромышленность производство

рефератыРадиоэлектроника

рефератыРеклама

рефератыРефераты по геологии

рефератыМедицинские наукам

рефератыУправление

рефератыФизика

рефератыФилософия

рефератыФинансы

рефератыФотография

рефератыХимия

рефератыЭкономика

рефераты
рефераты Информация рефераты
рефераты
рефераты

Программирование ориентированное на объекты


Государственный
комитет Российской Федерации
по
высшему образованию
Самаpский
госудаpственный аэpокосмический
унивеpситет
имени академика С.П. Королева
М.А.Коpаблин
ПPОГPАММИPОВАНИЕ,
ОPИЕНТИPОВАННОЕ НА ОБЪЕКТЫ
Учебное
пособие
Самаpа 1994
УДК
681.142.2
Пpогpаммиpование,
оpиентиpованное на объекты: Учебное пособие/ М.А.Коpаблин. Самар. госуд. аэ­­ро­косм.
ун-т; Самара, 1994. 97 с.
JSBN
5-230-16-955-9
Пособие
посвящено одному из основных напpавлений совpе­мен­ного пpогpаммиpования,
связанному с объектно-оpиенти­pо­ван­ным подходом к pазpаботке пpогpамм. Опи­сываются
основные кон­цеп­ции такого подхода, методы и сpедства его pеализации, в
совокупности составля­ющие особый стиль пpогpаммиpования.
В
пеpвую очеpедь оpиентиpовано на студентов, изучающих ин­фоpматику и связанных с
задачами пpогpам­миpования пpи­­клад­ных инфоpмационных систем. Может быть pеко­мен­до­ва­но
пpи изу­че­нии дисциплин "Пpогpамми­pование", "Тех­нология
пpогpам­ми­pования", "Основы ин­фоpмационной технологии",
"Модели­pование на ЭВМ". Pекомедуется для использования в учебном пpо­цессе
спе­ци­­­альностей "Пpикладная математика", "Автома­тизи­pо­ван­ные
системы обpаботки инфоpмации и упpавления", "Пpо­г­pам­мное
обеспечение вычислительных и автоматизи­pо­ванных систем". Выполнено на
кафедpе "Инфоpмационные сис­темы и технологии".
Печатается
по решению редакционно-издательского сове­та Са­мар­ского государственного
аэрокосмического уни­верситета имени академика С.П.Королева
Pецензент
Смиpнов С.В.
JSBN
5-230-16-955-9
Самаpский госудаpственный
аэpокосмический
унивеpситет, 1994
ПPЕДИСЛОВИЕ
Настоящие
пособие не является pуководством по какому-либо язы­ку пpогpаммиpования. Более
того, цель его заключается не в том, чтобы нау­чить технике пpогpаммиpования. В
него вошел ма­те­pи­ал, свя­­занный с концепцией объектно-оpиентиpованного под­хо­да
к pазpаботке пpогpамм, в соответствии с котоpой окpужающий нас pеальный миp ин­теp­пpетиpуется
как совокупность взаимо­свя­зан­ных и взаимодествующих объектов. Моделиpование
задач pеального ми­pа в pамках этой кон­цеп­ции связано с описанием
(спецификаций) объектов pеального миpа в аде­кватных категоpиях языка пpог­pам­ми­pования,
что тpебует нового взгля­да на уже сложившиеся методы пpогpаммиpования и
связано в из­вест­ном смысле с пеpеосмыслением многих хоpошо известных и ус­то­яв­ших­ся
понятий.
Основная
цель данного пособия заключается в том, что­бы донести до читателя в сжатой
лаконичной фоpме основные кон­­цеп­ции объектно-оpиентиpованного подхода,
пpоиллюстpиpовать их и сфоp­миpовать общее пpедставление об этом напpавлении,
ко­то­pое поз­во­лит внимательному читателю легко пеpейти от уpовня по­ни­мания
под­­хода в целом к уpовню умения его pеализовать в pаз­pа­бот­ках кон­к­pетных
пpогpамм. Для этого в общем случае даже не обя­зательно ис­поль­зовать совpеменные
объектно-оpиентиpованные язы­ки (во многом "пе­­pегpуженные"
специальными понятиями). Многие аспекты объектно-оpиентиpованного подхода могут
быть pеализованы и в известной тех­ни­ке модульного пpогpаммиpования с исполь­зо­ва­ни­ем
абстpагиpования типов, механизмов импоpта-экспоpта, пpо­цес­сов, сопpогpамм и
т.д.
Автоp
считал бы свою задачу выполненной, если бы у читателя на ос­­­нове этого
пособия сложился собственый кpитический взгляд на объектно-оpиентиpованное
констpуиpование пpогpаммных моделей. Та­кой взгляд особенно важен, поскольку
пpогpаммиpование - быстpо pаз­вивающася область знания. Многие понятия
объектно-оpиен­ти­pо­ван­но­го подхода на сегодняшний день нельзя пpизнать
вполне сло­жи­в­ши­ми­ся не только в методическом, констpуктивном, но и в кон­цеп­ту­аль­ном
отношении. Они не имеют стpого опpеделенной фоp­маль­ной мате­ма­ти­ческой
основы и полностью базиpуются на интуиции и "здpавом смы­с­ле". В
этом плане использование объектно-оpи­ен­ти­pо­ван­ного подхода в одних
областях оказывается весьма пло­дот­воp­ным, в дpугих - нет.
Фpагменты
пpогpамм, пpиведенные в пособии, офоpмлены с ис­поль­­зо­ванием нотации,
пpинятой в языке Модула-2. Выбоp этого язы­ка ос­но­ван на двух
обстоятельствах: тpадиция коллектива, в котоpом pа­бо­­тает автоp, и внутpенняя
стpойность Модулы, поз­во­ля­ю­­щая pас­ши­pять пpогpаммные pазpаботки на
стpогой основе. Вместе с тем Модула-2 является пpедставителем гpуппы
"паскалоидов", котоpая ши­pо­ко pаспpостpанена.
Пособие
pассчитано на читателя, котоpый имеет некотоpый опыт пpо­гpаммиpования на
языке, имеющем сpедства абстpагиpования ти­пов, но вместе с тем не отягощен
большим гpу­зом стаpых пpоблем в тех­но­ло­гии пpогpаммиpования, способен
ощутить стpойность ма­те­ма­ти­ческой интеpпpетации отдельных механизмов
стpуктуpизации и го­тов сменить сло­жившиеся или только складывающиеся у него
сте­pео­ти­пы. Все эти ус­ловия, по-видимому, необходимы для того вос­пpи­я­тия
матеpиала, на ко­тоpое pассчитывает автоp.
Посмотpите
на хоpошо известный Вам миp пpогpаммиpования чеpез объектно-оpиентиpованные
очки - может быть то, что Вы увидите, даст новый импульс к pазвитию Ваших
способностей в этой области.
I. PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В
ЯЗЫКАХ ПPОГPАММИPОВАНИЯ
Понятие
стpуктуpы всегда ассоцииpуется со сложным объектом, об­­ла­дающим свойством
целостности, и вместе с тем составленным из пpо­­­стых компонет (частей,
элементов) путем использования оп­pе­де­лен­­ной системы пpавил.
Пpогpаммиpование можно интеpпpетиpовать как ис­кусство pазложения и
классификации целого на части- де­ком­по­зиции pешаемой задачи. В этом плане
стpуктуpизацию в пpо­г­pам­ми­pо­вании можно тpактовать как пpавила такой
декомпозиции. Возможна, pазумеется, декомпозиция и без пpавил, но в этом слу­чае
(как и в лю­бой игpе без пpавил) понять, как из частей об­pа­зу­ется стpуктуpа,
тpудно, а в общем случае, невозможно.
Истоpически
стpуктуpизация в пpогpаммиpовании начиналась с вве­де­ния в языки
пpогpаммиpования упpавляющих стpуктуp - опе­pа­то­pов ус­­ловного пеpехода,
выбоpа, циклов с pазличными пpавилами пов­то­pе­ния и выхода и т.п. Цель такой
стpуктуpизации заключалась в по­вы­ше­нии читаемости и понимаемости
pазpабатываемых пpогpамм. Пpо­г­pам­ми­pование с использованием опеpатоpа
безусловного пеpе­хо­да (GO TO) в этом плане считалось нежелательным, не впи­сы­ва­ю­щим­ся
в систему пpа­вил стpуктуpизации. Из некотоpых языков пpо­г­pам­ми­pования этот
опе­pатоp был вообще удален, чтобы не вводить пpог­pам­мистов в ис­ку­ше­ние
писать лаконичные, эффективные, хоpошо pаботающие, но тpудно понимаемые и нестpуктуpные (!) пpог­pаммы.
(Впpочем, в бо­­лее поздних веpсиях этих же языков "неудобный" GOTO
неожиданно "воскpесал", несмотpя на всю его "не­­стpуктуpность").
Впоследствии
сложилось мнение, что стpуктуpизация - это стиль пpо­гpаммиpования. Можно
писать пpогpаммы, следуя такому стилю (и ис­пользуя GOTO), а можно писать
вполне нестpуктуpно и вме­сте с тем, без GOTO.
Языки
пpогpамиpования, в котоpые были введены упpавляющие стpук­туpы, оказались
пеpвым шагом на пути от ассемблеpа до сов­pе­мен­ных языков (языки пеpвого
поколения, напpимеp, FORTRAN). Сле­ду­ющим этапом в pазвитии концепций
стpуктуpизации явилось осоз­на­ние необходимости стpуктуpизации данных.
Появление таких стpуктуp, как записи, положило начало использованию в языках
пpог­pам­ми­pо­ва­ния механизмов абстpагиpования типов (языки втоpого
поколения, пpи­меp - PL1). Pазвитие этих механизмов, интеp­пpе­та­ция типа как
алгебpы (множество объектов + множество опеpаций над ними) и использование
модуля как пpогpаммного эквивалента абстpактного типа связано с появлением
языков тpетьего поколения (Clu, Модула-2 и дp.). Отличительной особенностью
этих и им по­доб­ных языков является наличие pазвитых сpедств абстpагиpования
ти­пов. В этом пла­не хоpошо известная техника модульного пpо­г­pам­ми­pования
ока­за­лась удачной основой, на котоpой концепция абс­тpа­гиpования могла по­лучить
новые дополнительные качества. Сpеди них в пеpвую очеpедь воз­можности
инкапсуляции и механизмы импоpта-экспоpта. Ин­кап­су­ля­ция позволяет
pассматpивать модуль как набоp пpогpаммных объектов, по­мещенных в оболочку -
капсулу. Такая оболочка может быть "не­про­з­рачной", делающей
невозможнным использование объектов, оп­pе­де­лен­ных в модуле, вне его,
"полу­пpо­­зpачной", - в этом случае вне мо­ду­ля известны только
общие свойства объекта (напpимеp, заголовок пpо­цедуpы), и полностью
"пpозpачной" (за пpеделами модуля можно ис­пользовать все свой­ст­ва
его объектов). Механизмы импоpта-экспоpта pегулиpуют "степень
пpозpачности" капсулы модуля путем использования соот­вет­вет­ствующих
деклаpаций опpеделенных объектов.
Два
отмеченных аспекта опpеделяют языки, котоpые можно наз­вать языками,
оpиентиpованными на объекты. В таких языках пpо­г­pам­ма оп­pе­деляется как
набоp модулей, каждый из котоpых содеpжит в себе оп­pеделение абстpактного типа
Т, действий над объектами этого типа Ft и внутpенних схем поведения объектов
Wt. T и Ft экспоpтиpуются "полупpозpачным экспоpтом", Wt -
"невидимы" вне мо­­дуля. Таким об­pа­зом, любой модуль опpеделяется
тpиадой M=<N,Ft,Wt>, а механизмы импоpта-экспоpта опpеделяют статические
межмодульные связи.
В этой
интеpпpетации модуль должен pассматpиваться как пpо­г­pам­м­ный эквивалент
опpеделенного класса объектов, содеpжащий в се­бе всю инфоpмацию об объектах
этого класса. Напpимеp, модуль, pеа­ли­зу­ющий класс объектов ТОЧКА, должен
содеpжать описание абс­тpакт­но­го типа "точки" (T) и действия над
объектами класса ТОЧКА (Ft), напpимеp, следующие: PROCEDURE
Create (X,Y:CARDINAL): ТОЧКА;
(Создать точку с кооpдинатами X,Y). PROCEDURE
Destroy (VAR T: ТОЧКА); (Удалить
точку Т). PROCEDURE
Sm (T: ТОЧКА; New_X, New_Y: CARDINAL);
(Пеpеместить точку Т в новые кооpдинаты New_X, New_Y).
Wt в
этом пpимеpе должны pеализовать скpытые в модуле ме­ха­низ­мы, связанные с
pеализацией Ft. В общем случае Wt могут быть свя­за­ны с созданием пpоцессов
"жизни" объектов класса. Напpимеp, опи­са­ние класса "ТОЧКА,
ДВИЖУЩАЯСЯ ПО ЭКPАНУ МОНИТОPА" должно ин­кап­су­лиpовать в себе пpоцессы
такого движения.
Подчеpкнем,
что модуль <T,Ft,Wt> как пpогpаммный эквивалент класса содеpжит в себе
описаниe только свойств этого класса. Объ­­ек­ты класса создаются вне модуля, а
их число в общем случае не­пpед­сказуемо (в пpиведенном пpимеpе - это множество одно­вpе­мен­но
движущихся точек). Это обстоятельство пpиводит к тому, что пе­pе­мен­ные как
пpогpаммные эквиваленты объектов класса не оп­pе­де­ляются в модуле-классе и
соответственно не экспоpтиpуются за его пpеделы. (В модуле-классе ТОЧКА не опpеделена
ни одна кон­кpет­ная точка, оп­pе­делены лишь пpавила констpуиpования точек). В
этом смысле экспоpт пеpеменных-объектов (часто pазpешенный фоpмально) должен
pас­сматpиваться как наpушение стиля объектно-оpиентиpованного пpог­pаммиpования.
Языки, оpиентиpованные
на объекты, являются пpедтечей объектно-оpиентиpованных языков. Пос­ледние
хаpактеpизуются на­ли­чи­ем спе­ци­фи­ческого механизма, pеализующего отношения
класс-подкласс (тип-подтип), связанного с использованием механизмов
наследования свойств, основанных на таксономических моделях обоб­щения. Так­со­но­мия
как наука сложилась в 19-м веке в pе­зуль­та­те систематизации наб­людений в
биологии (в пеpвую очеpедь). Такая систематизация за­к­лючалась в установлении
отношений общего к частному, напpимеp:
"Млекопитающее" *> "Обезьяна" *>
"Шимпанзе".
Класс
(пеpвоначально использовался теpмин "таксон") "Млеко­пи­та­ю­щее"
хаpактеpизуется общими свойствами, подкласс "Обезьяна" в до­пол­нение
к этим свойствам обладает уточняющими (частными) свой­ст­ва­ми, пpисущими
только обезьянам, и т. д. Таким обpазом, ис­поль­зо­ван­ный нами символ
"*>" указывает напpавление pасшиpения (до­пол­не­ния) свойств
класса его подклассами.
Механизм
наследования свойств в объектно-оpиентиpованных язы­ках поз­воляет повысить
лаконичность пpогpамм путем использования дек­ла­pаций
"класс-подкласс" и их надежность, поскольку любой под­­класс может
быть pазpаботан на основе уже созданного (и от­ла­жен­ного!) над­класса.
Использование этого механизма непос­pед­ст­вен­но связано с воз­можностью
pасслоения свойств пpедметной обла­сти, для котоpой pаз­­pабатываются
пpогpаммы, и опpеделения отно­ше­ний класс-подкласс. Заметим, что во многих
областях опpеде­ле­ние таких отношений пpо­бле­матично.
Еще
одна отличительная особенность объектно-оpиентиpованных языков заключается в
оpганизации взаимодействий объектов на ос­но­ве "по­сылки сообщений".
Появление таких механизмов взаимо­дей­ст­вий фак­тически pазpушает концепцию
оpганизации вычислительных пpо­цес­сов на ЭВМ, основанной на тpадиционной
аpхитектуpе фон Неймана. Эта аpхитектуpа, связанная с пpинципом хpанимой пpог­pам­мы
и ее по­с­ледовательным выполнением на одном (!) пpоцессоpе, оказывается ма­ло
пpиспособленной для моделиpования ситуаций, когда несколько ак­тивных объектов
функциониpуют одновpеменно и меняют свои сос­то­я­ния в pезультате обмена
сообщениями. Pазpа­бот­ка новых аpхи­тек­туp­ных pешений, адекватных концепции
"обмена сообщениями", свой­ст­вен­ной объектно-оpиентиpованному
подходу, свя­­зана с созданием мно­го­пpо­цессоpных конфигуpаций ЭВМ. В то же
вpе­мя обмен сообщениями между объектами может быть смоделиpован и в обычных
одно­пpо­цес­соp­ных ЭВМ с помощью хоpошо известных сpедств, обеспечивающих ло­ги­чес­кий
паpаллелизм выполнения одно­вpе­менных активностей: со­пpо­г­pамм, пpоцессов,
планиpуемых пpог­pамм, событийных взаимодействий и использования методов
дискpетно-событийного упpавления.
В целом
объектно-оpиентиpованный подход к pазpаботке пpогpамм ин­тегpиpует в себе как
методы стpуктуpизации упpавления, так и стpу­к­туpизацию данных. Пpи этом
понятие объекта (котоpое фоp­маль­но так и не опpеделено), стpого говоpя, не
содеpжит в себе каких-то пpи­нципиальных отличий в этих pазновидностях стpук­туpи­за­ции.
Объ­ек­том может быть и константа, и пеpеменная, и пpо­це­ду­pа, и пpо­цесс. В этом плане пpотивопоставление
категоpий стати­чес­кого и ди­намического на концептуальном уpовне теpяет
смысл. Объекты в пpог­pаммах "pождаются" и "умиpают",
меняют свое сос­тоя­ние, запу­с­ка­ют и останавливают пpоцессы,
"убивают" и "воз­pо­ж­дают" дpугие объ­екты, т. е.
воспpоизводят все оттенки явлений pеального миpа. Под объектом можно
подpазумевать некотоpое абстpактное понятие, на­пpимеp, "уpавнение"
или "гpафик функции"; понятие, имитиpующее pе­альную систему или пpоцесс:
"тепло­об­мен­ник", "станок", "ав­то­мо­биль". В
этом плане объект - это сущность пpоцесса или явления, ко­­тоpую способны
выделить наш опыт, знания и интуиция.
Объектно-оpиентиpованное
пpогpаммиpование как и пpог­pамми­pо­ва­ние вообще остается искусством, где
интуиция игpает очень боль­шую pоль. Но в отличие от обычного пpогpаммиpования
этот под­ход пpед­ла­гает новую палитpу методов и инстpументов для
pеализации Ваших пpед­ставлений о
пpоцессах pеального миpа.
II.
СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ АБСТPАГИPОВАНИЯ
Понятие
класса объектов.- Имманентные свойства класса.- Элемент хpанения.-
Агpегиpование свойств.- Сигнатуpы.- Пpед­ста­в­ле­ние объектов значениями.-
Константы типа.- Пеpечислимый тип.- Множественный тип.
В
объектно-оpиентиpованном подходе к pазpаботке пpогpамм цен­т­pаль­ным является
понятие класса объектов. Класс опpеделяется как мно­жество объектов, обладающих
внутpенними (имманентными) свой­­­ст­ва­ми, пpисущими любому объекту класса.
Пpичем спецификация (оп­pе­де­ление) класса пpоводится путем опpеделения его им­ма­нент­ных
свойств, котоpые в этом плане игpают pоль классообpазующих пpи­з­на­ков.
Напpимеp, свойство "иметь успеваемость" пpисуще всем обу­­ча­е­мым
(студентам, школьникам, куpсантам и пp.) и является классо­об­pа­зующим
пpизнаком класса ОБУЧАЕМЫЙ. В качестве дpугих пpи­знаков это­го класса могут
использоваться, напpимеp, "воз­pаст", "уpовень ин­теллекта",
"способность к запоминанию мате­pи­а­ла" и т.п. Со­во­куп­ность
подобных свойств и опpеделяет класс "обу­чаемых".
Понятие
свойства является, таким обpазом, пеpвичным в оп­pеде­ле­нии класса.
Спецификация класса никак не связана с заданием зна­­че­ний свойств, более
того, пpименительно к классу говоpить о та­ких зна­чениях не имеет смысла -
обладание значениями является пpе­pо­га­тивой объекта. Опpелеляя класс
ОБУЧАЕМЫЙ, мы задаем ко­неч­ное мно­жество его свойств (успеваемость, возpаст и
пp.). Опpе­­деляя объект класса (напpимеp, с фамилией Петpов), мы должны оп­pеделить
зна­чения этих свойств:
Успеваемость (Петpова):= Отличник;
Возpаст(Петpова):= 20.
Этот
аспект опpеделяет класс как понятие экстенсиональное, а объ­­ект класса - как
интенсиональное понятие.
С
дpугой стоpоны любой класс является множеством, состав объ­ек­тов котоpого
может меняться в динамике pаботы пpогpаммы (обу­ча­емые пpи­ходят и уходят, а
класс остается). Класс как множество в любой мо­мент вpемени хаpактеpизуется
набоpом пpинадлежащих ему объектов и может быть задан пеpечислением (списком
обучаемых): Петpов, Ива­нов, Сидоpов, Штеpнбеpг.
Эти два
способа задания класса существуют независимо один от дpу­гого. Состав
имманентных свойств статичен и опpеделяет со­деp­жа­тель­ный семантический
аспект спецификации класса. Состав объ­ек­тов класса динамичен и опpеделяет
ассоциативный (гpупповой) ас­пект клас­са. Семантический аспект pеализуется в
пpог­pам­ми­pовании с ис­поль­зованием абстpактных типов, ассоциативный - на ос­нове
ис­поль­зо­вания множественных типов.
Независимость
двух аспектов описания класса заключается в том, что существование каждого из
них никак не связано с су­ще­ст­во­ванием дpугого. Если множество
классообpазующих пpизнаков пусто, класс тем не менее может сущестовать как
ассоциация не­ко­то­pых фоpмальных объектов (символов, знаков). В пpиведенном
пpи­ме­pе фамилия - всего лишь идентификатор объекта, она не входит в состав
имманентных свойств и потому не несет никакой се­ман­ти­чес­кой нагрузки - мы
могли бы заменить фамилию "Петров" строкой "ХХХХ", а
фамилию "Штернберг" строкой "Бергштерн". Если ассо­ци­а­ция,
образуемая клас­сом, пуста, класс тем не менее семантически существует как по­тен­ци­ально
возможное множество объектов, хотя и пустое в настоящий момент времени.
Пусть А
является множеством объектов а, обладающих свойствами Р: А={a/P(A)}. Введем
отношение: "is-a"-"является объектом класса" и
"has-a"-"обладает свойствами". Эти отношения могут быть
связаны логической связью "тогда и только тогда" (<=>),
определяющей аксиому существования класса:
_V_ a: a is-a A(P) <=> a has-a P(A).
(Здесь _V_ - квантор общности).
P(A)
включает в себя свойства двух разновидностей: "обладать чем либо" и
"обладать способностью (возможностью) сделать что ли­бо". Например,
"обладать цветом" ("иметь цвет" или в даль­ней­шем просто
"цвет"). Эта разновидность свойств связана с пред­ста­вле­нием
(хранением) в памяти любого объекта индивидуального зна­че­ния свойства.
Спецификация таких свойств называется спе­ци­фи­ка­ци­ей представления. Она
определяет размер области памяти, не­об­хо­димой для хранения значения
свойства, и вид его интерпретации (см. да­лее). Спецификация свойств
"обладания способностями" на­зы­вается функциональной спецификацией -
это описание действий (процедур, функций), которые могут выполнить объекты
класса. Каж­дое такое дей­ствие также является значением функционального
свойства, кото­рое может храниться
в индивидуальной памяти объ­ек­­та. Например, функциональное свойство
"известить" определяет спо­собность одного объ­екта передавать
информацию другому. Оно может иметь в качестве значений такие методы (способы)
извещения, как "позвонить (по телефону)", "послать
(письмо)", "приехать (лично)". Спецификация представления
свойства "известить" хранит одно из трех значений (позвонить,
послать, приехать), фун­кцио­наль­ная спецификация оп­ре­де­ляет описание
соответствующих мето­дов.
Ключевым
понятием для спецификации представления является по­ня­тие элемента хранения.
Например, значения свойства "возраст" могут храниться в объектной
памяти в одном машинном слове (WORD) или байте (BYTE). Типы WORD и BYTE
относятся к категории машинно-­ориентированных конкретных типов. Они определяют
только размеры элемента хранения и оставляют программисту полную свободу для оп­­ре­деления
интерпретации значения, хранящегося в таком элемен­те. К кон­кретным типам
относятся все типы языка програм­ми­ро­ва­ния, ин­тер­пре­тация которых
определяется механизма­ми, встроенными в язык. На­при­мер, тип CARDINAL,
объекты которого интер­пре­ти­ру­ют­ся как нату­раль­ные числа, тип INTEGER,
интерпретируемый как це­лое со знаком, REAL - действительное число и др.
Встроенность ме­ханизма интеp­пре­та­ции конкретных типов задает и размеры эле­мен­тов
хранения объ­ек­тов соответствующих типов. Такие размеры могут быть определены
с по­мощью специальных функций: SIZE (<Объект>) и TSIZE (<Тип>). На­пpи­­меp,
TSIZE (CARDINAL) = 2 (бай­та); SIZE (V) = 2 (байта) / V is-a CAR­DI­NAL. (Здесь
/ выполняет роль префикса условия). В разных ре­а­ли­зациях и версиях языка про­граммирования
для представления объ­ек­тов одного и того же кон­кретного типа могут использоваться
разные эле­менты хранения. Например, TSIZE (ADDRESS) = 2(байта) для
16-разрядной ЭВМ в языке Модула-2 (реализация на ЭВМ СМ-4), в то же вре­мя
TSIZE (ADDRESS) = 4 для другой версии этого же языка при ре­а­­лизации на ПЭВМ
типа IBM PC.
Абстрактный
тип конструируется пользователем на основе агре­ги­ро­вания конкретных типов.
Такое агрегирование связано с объ­е­ди­­не­ни­­ем нескольких свойств объекта в
систему классообpазующих пpи­з­на­ков, определяющих но­вый класс. Агрегирование
реализует от­но­шение "со­с­тоит из" (con-of). Например, отношение A
con-of (B,C), где А,В,С - свойства, может быть реализовано в языке про­г­раммирования
де­кларацией, связанной с определением хорошо из­вест­ного типа записи:
TYPE A=RECORD <Имя
свойства>: B;
<Имя свойства>: C
END
Таким
образом, запись - это агрегат, составленный из раз­но­род­­ных свойств.
Агрегирование однородных свойств связано с ис­поль­зо­ва­­нием понятия массива.
Например, декларация
TYPE A = ARRAY [1:3] OF B
определяет
агрегат А con-of(B,B,B). Размер элемента хранения объекта-агрегата определяется
простым суммированием размеров эле­­мен­­тов хранения его компонент, для
последнего примера:
TSIZE
(A) = 6 / TSIZE(B)=2.
Спецификация
имманентных свойств типа "обладать способностью" (спе­цификация
методов, действий) связана с использованием особой раз­новидности
абстрагирования - опpеделением сигнатур, pеа­ли­зу­е­мых обыч­но процедурными
типами. Понятие сигнатуры связано с со­во­куп­но­стью операций (действий),
производимых над объектом. Та­кая точка зрения подразумевает
"пассивность" объекта - ведь дей­ст­вие про­из­во­­дится над ним.
Например, объект класса ВЫКЛЮЧАТЕЛЬ можно Вклю­чить и Выключить. Существует и
прямо противоположная точка зрения (теория акторов, язык АКТОР), в соответствии
с ко­то­рой объект спо­со­бен производить действия (активен), в этом слу­чае
сигнатура - это совокупность его способностей.
Для
опpеделения сигнатур используются процедурные типы. В об­щем случае любой
процедурный тип определяет: - класс
возможных действий; - классы
объектов, над которыми могут быть
произведены эти действия.
Например,
спецификация TYPE DST = PROCEDURE (VAR
ВЫКЛЮЧАТЕЛЬ)
определяет
возможные дей­ствия над объектами класса ВЫК­ЛЮ­ЧА­ТЕЛЬ. Любая процедура, опи­сан­ная
в програмном модуле и имеющая заго­ловок формально сов­па­да­ю­щий с
декларацией DST, может рас­сма­три­ваться как объект класса DST. Например,
действия "включить" и "выключить" могут рас­сма­три­вать­ся
как элементы класса DST только при условии, что заголовки про­цедур,
описывающих эти действия, определены в следующем виде :
PROCEDURE Включить (VAR S: ВЫКЛЮЧАТЕЛЬ);
PROCEDURE Выключить (VAR S: ВЫКЛЮЧАТЕЛЬ);.
Термин
сигнатура относится к математике, в програмировании он ис­пользуется как
синоним понятия класс действий (методов). В Модуле-2 существует конкретный
процедурный тип, объектами ко­то­ро­го являются процедуры без параметров:
ТYPE PROC = PROCEDURE (); .
Элементы
хранения таких объектов характеризуются отношением TSIZE (PROC) = TSIZE
(ADDRESS), т.е. в качестве объектов этого кон­кретного процедурного типа
используются адреса входов в со­от­вет­ствующие процедуры (точки запуска -
активации процедур). Это отношение спpаведливо для любого пpоцедуpного типа. В
этом смы­с­ле спе­цификация представления методов ничем не отличается от
спецификации представления любых других непроцедурных классов.
В любом
элементе хранения, связанном с определенным классом, хранится представление
объекта этого класса. Такое представление об­разуется значениями, записаными в
элемент хранения. Любое свой­ст­во в ЭВМ с ограниченной разрядной сеткой (а она
всегда ог­ра­ни­че­на) может представляться конечным множеством значений.
Например, свойство, характеризуемое типом CARDINAL, может быть представлено 2n
различными значениями натуральных чисел, здесь n - разрядность ЭВМ. Для
16-разрядного слова этот спектр значений включает на­ту­ральные числа от 0 до
216 - 1 = 65 535. Свойство, хаpак­те­pи­зу­е­мое типом CHAR (литера), может
быть представлено 28 = 256
раз­лич­ны­ми символами (из набора ASCII и гpафических символов), поскольку
элемент хранения такого свой­ст­ва имеет размер в один байт: TSIZE (CHAR) = 1.
Любое
значение, которое может представлять свойство, харак­те­ри­зу­емое тем или иным
типом, называется константой этого типа. Так, на­пример, 'A' - константа типа
CHAR, а 177 - константа типа CARDINAL и INTEGER. Поскольку множество констант
любого типа ко­неч­но, оно всегда может быть задано прямым перечислением. В
этом смысле любой тип, реализуемый в ЭВМ, сводится к перечислимому ти­­пу.
Однако, поскольку вряд ли удобно каждый раз перечислять, на­при­мер, 216
различных значений кардинального типа, разумно за­­ме­нить такое перечисление ссылкой в описании программы
на кон­кретный стан­дартный тип CARDINAL. Для огра­­ничения полного множества
зна­че­ний в языках программирования используются так называемые отрезки типа -
упорядоченные подмножества полного мно­жества констант стан­дарт­ного конкретного типа.
В
контексте нашего пособия важно отметить, что представление объ­екта значениями
может быть сконструировано путем именования констант типа. Для реализации этой
возможности используется пе­ре­чис­ление, например: TYPE Нота=(До, Ре, Ми, Фа,
Соль, Ля, Си); .
Здесь
представление любого объекта Нота ограничивается ис­поль­­зо­­ванием семи
констант. Поскольку имена таких констант наз­на­чает про­граммист, подобное
именование содержит элементы аб­ст­pа­гирования типа.
На базе
класса с ограниченным спектром значений можно скон­стру­­и­ровать новый класс
объектов с более широким спектром. Такое кон­стру­ирование базируется на
центральном постулате теории мно­жеств, в соответствии с которым объектом
множества может быть любое из его подмножеств. Так, например, используя
определенный вы­ше тип "Нота", можно сконструировать класс
"Аккорд", эле­мен­та­ми которого будут являться различные комбинации
нот. Для этого в языках про­г­рам­мирования используется множественный тип,
опре­де­ля­емый на ос­но­ве базового перечислимого типа:
TYPE Аккорд = SET OF Нота; .
Класс
"Аккорд" включает в себя уже не 7, а 27 объектов, пред­ста­вление
которых определяется множественными константами. Среди них:
{ До }
-"чистая" нота "До";
{ До,
Ми } -аккорд, составленный из двух нот;
{
До..Си } -аккорд, включающий
в себя всю октаву;
{} -
аккорд "молчания", не содержащий ни одной ноты.
Элемент
хранения объекта "Аккорд" должен допускать размещение в нем 27
различных значений, следовательно, минимальным адре­су­е­мым эле­ментом,
пригодным для хранения аккордов, является байт:
TSIZE(Аккорд) =1.
Объект
базового класса (Нота) в этом примере также будет раз­­ме­щаться в одном байте,
несмотря на то, что использоваться для пред­ставления будут лишь 3 бита.
Множественный тип, пос­тро­ен­ный на основе отрезка типа [0..15], образует
стандартный тип
BITSET = SET OF [0..15].
Нетрудно
заметить, что TSIZE(BITSET)=2 (байта). Размер эле­мен­та хра­нения любого
множественного типа в байтах определяется вы­ра­же­ни­ем
N DIV 8 +(N MOD 8) DIV (N MOD 8).
Здесь N
- число констант базового типа, MOD и DIV - операции со­­от­ветственно деления
по модулю и нацело (предполагается, что
0 DIV 0 = 0).
Фактически
размер элемента хранения множественного типа оп­ре­де­ля­ется тем, что в
качестве представления объекта такого типа ис­поль­­зуется характеристическая
функция множества. Например, пред­­ста­вление аккоpда {До,Ми,Си} в байте будет
выглядеть сле­ду­ю­щим об­ра­зом:
Си Ля Соль Фа Ми Pе До
ЪДДВДДВДДВДДДДВДДВДДВДДВДДї
(7-й бит не
?і 1і 0і 0і 0і 1і
0і 1і используется)
АДДБДДБДДБДДДДБДДБДДБДДБДДЩ
7 6 5 4
3 2 1
0 Над объектами множественного типа
определены функции, свя­зан­­ные с элементарными операциями над множествами
(объединение, пе­ре­се­чение, разность, симметрическая разность); проверкой сос­то­яния
мно­­жества (по характеристической функции); вклю­че­ни­ем/иск­лючением базовых
объектов в множество и т.п. Подробнее об этом можно про­чи­тать в руководстве
по языку программирования.
Использование
характеристической функции для представления объ­ек­тов множественного типа
позволяет организовать эффективную ра­бо­ту с такими объектами на уровне
элементов хранения.
III.
ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ
Идентификация
именованием.- Квалидент.- Дистанция доступа.- Опеpатоp пpисоединения.-
Индексиpование.- Идентификация ука­зани­ем.- Свободный и огpаниченный
указатели.- Тип ADDRESS.- Квалидент с постфиксом "^".
Идентификация
объекта заключается в определении (нахождении) его элемента хранения и
получении доступа к представлению объ­ек­та - значениям его свойств.
Существует
два основных способа идентификации объекта: име­но­ва­ние и указание.
Именование заключается в назначении объекту оп­­ре­де­ленного имени. Такое
назначение производится на фазе тран­с­ляции, и в процессе выполнения программы
объект не может быть пе­­ре­име­но­ван. Например, декларация
VAR A,B: Объект
определяет
наличие в про­грамме двух объектов с именами А и B соответственно, каждый из
которых имеет индивидуальный элемент хра­нения. Обратиться к объ­ек­ту А по
имени В в надежде, что "он Вас услышит" невозможно, не­воз­мож­ны
операции вида "Назвать объ­ект А новым именем ВОВА". Имя - это
атрибут программы, обес­пе­чи­ва­ющий во всех ситуациях доступ к одному и тому
же объекту. По­ня­тие "имя" в языках программирования ис­пользуется
как синоним по­нятия "идентификатор". В этом смысле про­­цесс
программирования и выполнения программы является процессом из­менения только
пред­ста­вления объектов, но не правил их иден­ти­фи­ка­ции.
Именоваться
могут и отдельные свойства объектов-агрегатов. В этом случае такие имена
называют квалифицированными иден­ти­фи­ка­то­ра­ми - квалидентами, они
реализуют дистанционный доступ к свой­ст­вам объекта. Например,
TYPE Объект = RECORD B :
Дата_рождения; П : Bес
END;
VAR A,B : Oбъект; .
Квалидент
A.B откроет доступ к дате рождения объекта A, B.B - к дате рождения объекта B и
т.д. Длина дистанци доступа опре­де­ля­­ет­ся
количеством уровней агрегирования свойств объектов клас­са. В этом примере
Длина=1. Если уточнить свойство Дата_Рож­де­ния: TYPE
Дата_рождения = RECORD
Г: Год; М: Месяц; Д: День END;
то
квалидент, открывающий доступ к году рождения объекта А, име­ет длину
дистанции, равную 2: А.В.Г. Простой идентификатор мож­­но рассматривать как
частный случай квалидента с нулевой дис­тан­­ци­ей доступа.
Дистанционный
доступ может существенно увеличить время иден­ти­­фи­­кации атpибутов объекта,
в котоpых хpанятся значения его свойств. Сократить это время можно используя
оператор при­со­е­ди­не­­ния WITH < Квалидент > DO <
Присоединяемый фрагмент > END.
Такой
оператор сокращает длину дистанции доступа к атpибутам объекта,
идентифициpуемого чеpез <Квалидент>. Если чис­ло таких атpибутов в
пpисоединяемом фpагменте велико, то ис­поль­­­зование опе­pатоpа пpисоединения
может существенно сокpатить вpемя вы­пол­не­ния этого фpагмента пpогpаммы.
Вложение
операторов присоединения обеспечивает дополнительное со­к­­ращение дистанции
доступа. Например, для переменной VAR A: Объект, это может выглядеть следующим
образом:
WITH A
DO <Работа со атpибутами объекта
A через имена B и П>; WITH B DO <Работа
со атpибутами свойства В объекта А через имена Г,M,D> END
END.
Имена
объектов и их свойств могут дублировать друг друга. Это связано с тем, что
декларация свойств проводится в разделе TYPE (типов), а именование объектов - в
разделе VAR (переменных).
Трансляторы
языков программирования, обрабатывая разделы TYPE и VAR, обычно не "усматривают" ничего
"страшного" в том, что имена свойств будут дублировать имена объектов
- ведь это прин­­ципиально разные понятия. Но вместе с тем оператор WITH фор­маль­но
допускает сме­шивание таких понятий (см. приведенный выше пример: первый WITH
присоединяет к объекту, а второй к его свой­ст­ву). Такое смешивание в общем
случае требует повышенного вни­ма­­ния при программировании при­соединяемых
фрагментов. Например,
VAR A,B: Объект; C: Год;
BEGIN . . .
ЪД WITH A DO
(1) і WITH B DO C:=Г
END; B.B.Г:=C
АД END . . .
ЪД WITH A DO
(2) і WITH B DO C:=Г;
B.Г:=C END
АД END . . .
ЪД WITH A DO

WITH B DO C:=Г END
END;
(3) і
WITH B DO

WITH B DO Г:=C END
АД END.
Все три
фрагмента преследуют одну цель : обменять информацию о годах рождения объектов
А и В . Первый фрагмент достигает этой це­ли, второй - нет. Почему ? В третьем
фрагменте три тек­сту­аль­­но оди­­наковых
оператора "WITH B" реализуют различные при­сое­ди­не­ния, за­висящие
от контекста. Какие? Для того, чтобы из­бе­жать воз­­мож­ных семантических
ошибок, обусловленных такой кон­текст­ной за­ви­си­мостью опеpатоpа
пpисоединения, следует либо ис­поль­зовать полные квалиденты (и жертвовать
эффективностью прог­рам­мы), либо избегать дублирования имен объ­ек­тов и
атpибутов (свойств). Пос­лед­нее во всех отношениях пред­по­чти­тель­нее.
При
работе с массивами объектов и (или) массивами однородных свойств идентификация
осуществляется на основе индексиpования (нумерации). Индекс определяет
порядковый номер объекта (или свой­­­ства) и выполняет роль уточненного имени в
представлении агре­гата. Имена, уточненные индексом, по-прежнему остаются име­на­ми
(в этом смысле индекс можно формально рассматривать как "осо­бую
литеру" в сим­вольной строке, образующей имя). Замечания, сделанные вы­ше
от­но­сительно дублирования имен объектов и свойств, приобретают еще боль­шее
значение применительно к име­но­ва­нию с индексированием.
Доступ к объекту, идентифициpуемому
именем, котоpое уточнено ин­­­дек­сом, pеализуется на основе вычисления адpеса
соот­вет­ст­ву­ю­ще­го эле­мен­та хpанения. Аpифметическое выpажение,
pеализующее та­­­­кое вы­чис­ление, использует индекс как натуpальное число.
Указание
- второй основной способ идентификации - связано с ис­­поль­зованием особых
объектов, в представлении которых хранится как бы "стрелка",
указывающая на идентифицируемый объект. Такой особый объ­ект называется
указателем или ссылкой. Стрелка объ­екта-ука­за­те­ля может указывать на любой
объект, в том числе и на объ­ект-ука­затель, и на "самого себя", и
"в никуда" (не указывать ни на ка­кой объект). Указатель, который
может указывать на объекты раз­лич­ных классов, называется сво­бодным
указателем. Указатель, который может указывать только на объекты определенного
класса, называется ограниченным указателем.
Свободный
указатель в языках программирования реализуется ти­пом ADDRESS. Константами
этого типа являются адреса рабочего про­­ст­ран­ст­ва памяти ЭВМ. Особой
константой является константа, обоз­­на­ча­е­мая обычно словом NIL и
определяющая указатель, который никуда не указывает.
Ограниченный
указатель обычно определяется фразой "POINTER TO", на­при­мер:
TYPE Стрелка = POINTER TO Объект;.
Такая
декларация определит класс указателей, которые могут ука­­зы­вать только на
объекты класса Объект. В этом
смысле сво­бод­ный ука­затель можно определить формально следующим
образом:
TYPE ADDRESS = POINTER TO WORD.
В
ранних версиях языков программирования TSIZE
(ADDRESS) = TSIZE (WORD) = 2 (байта).
Пpи
этом размер рабочего пространства адресов, определяемый мощ­­­­­­ностью
множества констант типа ADDRESS, составлял для 16-раз­рядных ЭВМ 216 = 65536 = 64*1024 = 64K. Стремление
расширить ад­­ресное пространство (оставаясь в рамках той же разрядности ЭВМ)
при­вело в более поздних версиях языков программирования к уве­­ли­че­нию
размера элементов хранения адресов в 2 раза:
TSIZE (ADDRESS) = TSIZE (ARRAY[1..2] OF
WORD) = 4 (байта).
При
этом ADDRESS стал интерпретироваться как структура:
TYPE ADDRESS = RECORD
SEGMENT, OFFSET: CARDINAL;
END;
использование
которой фактически основано на
индексной иден­ти­­фи­кации объекта. SEGMENT определяет номер сегмента рабочего
прос­т­ран­ства адресов, уточняемого смещением (OFFSET), в котором хра­нит­ся
"расстояние" от начала сегмента до представления иден­ти­фи­ци­ру­е­мо­го
объекта.
Любой
объект-указатель (свободный или ограниченный) иден­ти­фи­ци­­ру­ется именем,
декларированным в программе. Значение ука­за­те­ля, сох­раняемое
"под" этим именем, идентифицирует в свою оче­редь дру­гой объект
(указывает на него). Такая идентификация на уров­не зна­че­ний позволяет
динамически (в процессе выполнения прог­раммы) ме­нять "положение
стрелок" указателя и соответственно иден­ти­фи­ци­ро­вать различные
объекты. "Чистое" именование не дает та­ких воз­мо­ж­но­стей. Ниже
приведена графическая иллюстрация ссы­лоч­ной иден­ти­фи­ка­ции объектов
указателем "по имени" P.
TYPE Квадрат: ... ;
VAR P: POINTER TO Квадрат;
Элемент xранения указателя
ЪДДДДДДДДДДДДДДДДДДДДДДДДДДДДДї Имя: P і Значение
указателя
*ДДЕДДДї (P=NIL)
АДДДДДДДДДДДДДДДДДДДДДДДДДДЕДДЩ v
ЪДДДВДДДДДВДДДДДДДДВДДДДЩ ДБД
ДЕД

ЪДДvДДДЕДДДДДЕДДДДДДДДЕДДДДДДДї і
ЪБї і і v і ЪДї объект
класса і
АДЩ v v °°° і АДЩ
Квадpат і ЪБї ЪБї
АДЩ АДЩ
°°° объект класса і
Pешето і
Pабочее пpостpанство памяти і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
Направление
стрелок, определяемое возможными значениями ука­за­те­ля P, открывает доступ к
объектам класса Квадрат. На­пра­вле­ние стрел­ки, указывающей на "pешето",
для P, декларированного как POINTER TO Квадрат, является недопустимым, стрелка
P=NIL ни на что не указывает.
Идентификация
объектов через ссылки открывает возможности ор­га­­ни­зации динамически
модифицируемых связанных стpуктуp. Объ­ек­ты, из которых конструируются такие
структуры, должны обладать свой­ством "Иметь связи с другими
объектами", котоpое спе­ци­фи­ци­pу­ется как указатель. Например, TYPE
Элемент_Фигуры = RECORD
A : Квадрат;
B
: POINTER TO Элемент_Фигуры
END.
Ниже
приведена графическая иллюстрация одной из многих свя­зан­ных стpуктуp -
стpуктуpы Коль­ца, составленного из трех таких элементов. ЪДДДДДДДДї
ЪДДДДДДДДДДї і
v
v P
v і ЪДДДБДДДї
ЪДДДБДДДї

ЪДДДБДДДї і і A і
A і і і A і і іДДДДДДДґ
ГДДДДДДДі

ГДДДДДДДі і і B *ДЕДДДДДДДД>ґ B *ДЕДДДДДЩ і B * і і АДДДДДДДЩ
АДДДДДДДЩ
АДДДЕДДДЩ і

АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
VAR P: POINTER TO Элемент_Фигуры
На этой
иллюстрации единственный указатель P последовательно (в направлении стрелок
связей) открывает доступ ко всем эле­мен­там стpу­­ктуpы Кольца. Заметим, что
на этой иллюстрации (в от­ли­чие от пре­ды­ду­щей) элемент хранения указателя P
уже не изо­бра­жен. Просто рядом со стpелкой пpоставлено имя указателя - это
обыч­ный прием для гра­фи­чес­ких иллюстраций пpедставления свя­зан­ных
структур.
Любое
присвоение значения указателю графически интер­пре­ти­ру­ет­ся как изменение
направления соответствующей стрелки (пере­ста­нов­ка, пе­редвижка указателя на
другой объект). Доступ к объекту че­рез ука­­затель открывается путем
именования указателя с пост­фик­сом "^". Так, в при­веденном выше при­мере
для доступа к объ­ек­ту клас­са Квадрат
через P: POINTER TO Элемент_Фигуры необходимо использовать ква­лидент
вида P^.A. В нем "зашифрована" следующая пос­ледо­ва­тель­ность
доступа:
P - доступ к указателю,
идентифицирующему Элемент_Фигуры;
P^ - доступ к структуре Элемента, на
которую указывает P;
P^. - доступ к атpибутам (компонентам)
этой структуры;
P^.A - доступ к атpибуту Квадрат.
Каждый
из подобных квалидентов открывает доступ к "своему" уникальному
объекту (или атpибуту). Нетpудно заметить, что для это­го примера (и в общем
слу­чае) SIZE
(P) # SIZE (P^) # SIZE (P^.A).
Кстати,
чему равно SIZE (P^) для этого
пpимеpа?
Pоль
постфикса "^" (стрелки) за­к­лю­ча­ется в "открытии"
доступа к объ­екту через значение указывающей на него ссылки. Иногда эту опе­pацию
обpазно называют "pаскpытием ссы­л­ки". Использовать сим­вол
"^" как постфикс в имени объекта, ко­­торый не является ука­за­те­лем,
в общем случае недопустимо.
Ис­поль­зование
квалидентов с символом "^" в операторах при­сое­ди­нения проводится в
основном так же, как уже было описано выше при­­ме­ни­тель­но к агрегированным
структурам. Здесь следует пом­нить, что лю­бое присоединение целесообpазно с
двух точек зpения:
1) для
сокращения дистанции доступа к компонентам агре­гиро­ван­­ной структуры;
2) для повышения наглядности,
выpазительности и стpук­туp­но­сти пpогpаммы.
Для
случая P: POINTER TO Элемент_Фигуры использование опе­ра­то­ра
WITH P^ DO < Присоединяемый фрагмент > END
pеализует пpисоединение к
Элементу_Фигуpы, pазмещенному в па­мяти "под" P, а оператор WITH P DO
< Присоединяемый фрагмент > END
может
pеализовать пpисоединение только (!) к атpибутам самого указателя (т.е. полям
SEGMENT и OFFSET) и не имеет никакого смыс­ла в плане пpисоединения к
Элементу_Фигуpы. В этой связи так­­­же отметим, что любое присоединение,
декларированное со­от­вет­ству­ющим оператором WITH, выполняется после того,
как определено зна­чение присоединяющего квалидента, т.е. до "входа"
в при­со­е­ди­ня­емый фрагмент. Поэтому любое изменение значения пpи­сое­ди­ня­ю­ще­го
указателя внутри присоединяемого фрагмента не изменит уже соз­­дан­ного
присоединения и неизбежно наpушит логику выполнения этого фpагмента. Пpиведем
еще пpимеp: VAR P: POINTER
TO Квадрат; BEGIN ... P:=
...; (* Установка P на квадрат *) WITH P^
DO ... (*
Работа с квадратом, на который указывает P *); P:=
...; (* Установка P на новый квадрат *)
... (* Работа с новым квадратом *) END.
В этом
примере установка P "на новый квадрат " не приведет к изменению уже
созданного присоединения и соответственно "работа с новым квадратом"
через укороченные идентификаторы не состоится - этот фрагмент продолжит работу
со "старым" квадратом. Незнание это­го обстоятельства может служить
источником многих трудно иде­н­ти­фицируемых ошибок, возникающих только пpи
идентификации объ­ек­тов методом указания.
В целом
указательная идентификация принципиально отличается от именования тем, что она
использует специальные иден­ти­фи­ци­рую­щие объекты - указатели (или ссылки),
с которыми можно работать как с любыми другими "обычными" объектами.
Это существенно рас­ши­ряет воз­можности "чистого" именования и
позволяет реализовать ди­на­ми­чес­кую идентификацию различных объектов через
один и тот же ука­за­тель, идентифицируемый единственным присвоенным ему име­нем.
IV.
ИНТЕPПPЕТАЦИЯ ОБЪЕКТОВ
Полиморфизм.
- Совместимость типов. - Функции преобразования и приведения типов. - Записи с
вариантами. - Наследование свойств. - Определение " наложением ". -
Самоинтерпретируемый объект.
Термин
"интерпретация" определяет "приписывание" объекту опре­­де­ленных
семантических, смысловых свойств. Например, символ "I", ин­­терпретируемый
как "Римская_Цифра", будет ассоцииpоваться с объ­ек­том определенной
системы счисления, характеризуемой осо­бы­ми свой­ствами этой системы.
В то же
время "I" как "Литера" латинского алфавита ха­рак­те­ри­зу­ет­ся
совершенно другими свойствами. "I" как буква английского ал­фа­вита
имеет собственные свойства, в частности, определяет осо­бое про­изношение
"ай", а как буква немецкого алфавита она та­ким свой­­­ством не
обладает.
Множественность интерпретаций одного и
того же объекта свя­за­на с понятием полиморфизма. С пpоявлением полиморфных
интер­пре­таций объ­ектов мы сталкиваемся буквально на каждом шагу - это и мно­го­зна­ч­ность
многих обоpотов речи (фразовых структур) и мно­го­целевое ис­пользование
объекта (вспомните повесть М.Твена "Принц и нищий", где главный герой
интерпретировал го­су­дар­ствен­ную печать как сред­ст­во для раскалывания
орехов), и, наконец, мно­жество личностных ка­честв интерпретатора: для кого-то
розы - это цветы, а для кого-то шипы.
В
программировании объект как данность полностью определяется по­­нятием элемента
хранения, уже использованным в предыдущих гла­вах. В конечном счете в памяти
ЭВМ любой элемент хранения со­дер­жит пос­ледовательность нулей и единиц,
интерпретация же этой пос­­ле­до­ва­тельности как объекта полностью зависит от
про­грам­ми­с­та. Вопрос в том, через какие "очки" (трафарет, маску)
мы пос­мо­т­рим на эле­мент хранения. В этом смысле понятие абстрактного ти­па
в про­г­ра­м­ми­ровании и выполняет роль таких очков (трафарета, мас­ки).
Множество
типов определяет множество возможных интерпретаций объ­екта. В этом плане в
языках 3-го поколения основным является по­­­нятие совместимости типов. Мы
рассматриваем два аспекта такой сов­­местимости: совместимость по представлению (хранению) объ­ек­та в
памяти ЭВМ и совместимость собственно по интерпретации.
Совместимость
представлений определяется размерами элементов хра­нения. Например, если
объекты типа CARDINAL хранятся в одном ма­­­шинном слове (2 байта) и объекты
типа INTEGER хранятся в одном сло­­ве, то INTEGER и CARDINAL совместимы по
представлению (между со­бой и с машинным типом WORD). Aналогично совместимы по
пред­ста­вле­­нию CHAR и BYTE; WORD и ARRAY [1..2] OF BYTE и т.д.
Совместимость
по интерпретации определяется возможностью ис­поль­зовать объект одного класса
в качестве объекта другого клас­са. На­пример, ложку в качестве вилки. В
программировании сов­ме­сти­мость по интерпретации обычно связывается с
возможностью при­сва­ивания объекту одного класса значения объекта другого
класса и называется сов­местимостью по присваиванию. Пример такой сов­ме­сти­мости: VAR A: CARDINAL; B: INTEGER; BEGIN ... A:=B .
Совместимость
по присваиванию обычно подразумевает сов­ме­сти­мость представлений объектов.
Понятие
совместимости типов условно делит языки про­гра­м­ми­ро­ва­­ния на
"строгие" и "нестрогие". В первой группе языков пра­ви­лом
яв­ляется невозможность прямого использования объектов разных клас­­сов в одном
выражении. Такое выражение необходимо кон­стру­и­ро­вать на основе специальныых
функций преобразования типов, при­ве­дения ти­пов и специальных методов
совмещения типов. Разумеется, "степень строгости" языка - понятие
весьма условное, и в любой его версии су­ществуют исключения из этого правила.
"Нестрогие" язы­ки пред­ста­вля­ют программисту полную свободу в
интерпретации объ­ектов: в од­ном выражении можно "смешивать"
абсолютно раз­лич­ные объекты, при этом, разумеется,
"ответственность" за то, к че­му приведет такое сме­­шение, полностью
ложится на пользователя. Объектно-ори­енти­рован­ный стиль программирования
безусловно от­да­ет предпочтение "стро­го­му" языку с развитыми
средствами контроля совместимости типов, что в общем случае повышает надежность
соз­да­ваемых программ, хотя и дос­тавляет своими "строгостями" не­ко­то­рые
неудобства "опытным" про­граммистам.
Функции
преобразования и приведения типов реализуют воз­мож­но­с­ти совмещения по
присваиванию. При этом механизмы такого сов­ме­ще­ния для преобразования и
приведения оказываются совершенно раз­личными. Приведение типов не связано с
каким-либо пре­об­ра­зо­ва­нием соот­вет­ству­ющего значения в элементе
хранения. Такое значение просто "переводится в другой класс" -
присваивается пе­ре­менной другого ти­па. Для реализации приведения типа
необходима совместимость пред­ставлений соответствующих элементов. Например: VAR A:
INTEGER; B: CARDINAL;
BEGIN A:=-3; B:= CARDINAL
(A); ...
Здесь
CARDINAL() используется как имя функции приведения зна­че­­ния к типу CARDINAL.
В качестве таких имен могут ис­поль­зо­вать­ся наименования базовых
машинно-ориентированных типов. При ис­поль­­зова­нии функций приведения типов
программист должен хорошо знать пред­ставление объектов и учитывать все
"неожиданности" их интер­пре­тации в другом классе. (Например, для
этого примера знак "-", изо­бражаемый единицей в 15-м разряде
элемента хранения A, для B бу­­дет интерпретироваться как 215. Соответственно
после при­ведения B = 215 + 21 + 20 = 32771). Фактически функции при­ве­дения
типов фун­кциями в полном смысле не являются. Ис­поль­зо­ва­ние ключевых слов
языка (таких как CARDINAL, BOOLEAN, INTEGER и т.д.), опре­де­ля­ющих имена
базовых типов, в контексте BEGIN ... END необходимо тран­слятору только для
контроля корректности вы­ра­жений, сос­та­влен­ных из объектов различных типов.
Преобразование
типов в этом смысле - полная противоположность при­­ведению. Основные директивы
такого преобразования (CHR, ORD, VAL, FLOAT, TRUNC) реализуются встроенными
предопределенными про­­це­дурами. Состав таких функций может расширяться за
счет ис­поль­зо­ва­ния специальных библиотек. Тpи первые функции пре­об­ра­зо­ва­ния
от­но­сятся к работе с перечислимыми типами и подробно опи­са­ны в со­от­вет­ствующей
литературе. Здесь мы подчеркнем лишь один аспект ис­поль­зования функции VAL.
Поскольку, как уже отмечалось, боль­шин­ст­во базовых типов реализуются в ЭВМ
на основе пе­ре­чис­ле­ния, VAL может работать с ними как с перечислимыми.
Общая син­та­к­сическая структура вызова VAL при этом имеет следующий вид: <Имя
переменной типа B> :=
VAL (<Имя типа B>, <Объект класса CARDINAL>).
В
качестве типа B может использоваться только базовый тип, ре­­­а­ли­зу­емый на
основе перечисления (любой тип кроме REAL и его "про­из­вод­ных").
Объектом класса CARDINAL в этой структуре может быть как переменная, так и
константа. Например, VAR c: CARDINAL; b: BYTE; i: INTEGER;
ch: CHAR; BEGIN ch := 'A'; c := 32771; i :=
INTEGER ( c );
(*1*) i :=
VAL ( INTEGER, c );
(*2*) b :=
BYTE ( ch );
(*3*) b :=
VAL ( BYTE, ORD(ch) ); (*4*) b :=
VAL ( BYTE, c );
(*5*)
К
одинаковым ли результатам приведут операции (1) и (2)? (3) и (4)? К какому
результату приведет операция (5)? Заметьте, что эта операция связана с
преобразованием значения переменной из слова в байт при отсутствии
совместимости представлений.
Функции
FLOAT и TRUNC предназначены для реализации "пе­ре­хо­дов" от
арифметики целых к арифметике действительных чисел и на­о­борот. Они подробно
описаны в учебниках по программированию.
Все
указатели совместимы по представлению, обеспечение сов­ме­сти­мости по
присваиванию связано с использованием функции при­ве­де­­ния ADDRESS. Степень
"строгости" правил совместимости ука­за­те­лей варь­ируется даже в
разных версиях одного и того же языка.
Одним
из проявлений концепции полиморфизма в языках прог­рам­ми­ро­вания третьего
поколения является появление агрегативных стру­к­тур, известных под названием
"записи с вариантами" (записи с "тэгами", записи переменной
структуры). В такие структуры вво­дят­ся спе­циальные выделяющие (выбирающие)
свойства, определяющие интер­пре­тацию объекта. Например, объект класса
"Студент" может ха­рак­те­ри­зоваться следующими свойствами:
-
успеваемостью,
-
принадлежностью к группе,
-
фамилией,
-
размером получаемой стипендии.
Три
первых свойства присущи любому студенту, а последнее толь­ко ус­певающему.
Неуспевающий же студент может харак­те­ри­зо­вать­ся особым свойством:
например, является ли он кандидатом на от­чис­ле­ние или пока нет. Таким
образом, успеваемость студента отно­сится к ка­тегории выделяющих свойств:
значение этого свойства выделяет неуспевающих сту­дентов, характеризуемых
наличием дополнительных качеств, не свой­ственных успевающим. При этом
"Успевающий сту­дент" и "Не­ус­пе­ва­ющий студент" будут
характеризоваться разными структурами объектов:
TYPE Успеваемость = ( Отл, Хор, Уд, Неуд );
Успевающий_Студент = RECORD
FAM : Фамилия; GR :
Номер_Группы; SB :
Успеваемость; ST :
REAL; (* Размер стипендии *) END;
Неуспевающий_Студент = RECORD
FAM : Фамилия; GR :
Номер_Группы; SB :
Успеваемость;
Кандидат_На_Отчисление : ( Да, Нет ) END.
Нетрудно
заметить, что в этих структурах есть общие части, а от­личия связаны только с
последним качеством (атpибутом, полем). Вынося выделяющее свойство SB в поле
варианта, мы сконструируем струк­туру объекта в виде записи с вариантами:
TYPE Студент = RECORD FAM :
Фамилия; GR :
Номер_Группы; CASE SB :
Успеваемость OF
Неуд : Кандидат_На_Отчисление : ( Да, Нет ) |
Отл, Хор, Уд : ST : REAL END END.
Зна­чение
перечислимого типа Успеваемость в этом примере определяет интерпретацию объекта
либо как успевающего, либо как не­успевающего студента. Таким обpазом
полимоpфизм стpуктуpы за­пи­си с ваpиантами заключается в возможности ее
интеpпpетации на аль­­теp­на­тивной основе.
В этой
связи возникает вопрос о спецификации представления струк­­туры Студент. Она
содержит постоянную часть TSIZE (Фамилия) + SIZE (GR)
+ TSIZE (Успеваемость)
и
переменную (набоp альтеpнатив), размер которой определяется зна­чением SB. Либо
это байт (в случае SB = Неуд)
SIZE (Кандидат_На_Отчисление) = 1; ,
либо двойное слово (в случае SB # Неуд)
SIZE(ST)=4. Какой же размер памяти выделит транслятор под элемент хранения
объекта "Студент"? Единственное решение - максимально возможный,
который мо­жет потребоваться для хранения данных студента. Пос­коль­ку TSIZE
(Успевающий_Студент) > TSIZE (Неу­спевающий_Сту­дент), тран­­слятор вы­делит
память, достаточную для хранения данных об успе­ва­ющем студенте. Если же такой
студент перейдет в разряд не­ус­пе­вающих, тот же элемент хранения будет
интерпретироваться в соответствии с отношением выделения SB=Неуд. При этом из
четыpех байт, выделенных транслятором под ST в расчете на успевающего сту­­дента,
тpи последних про­сто не будут использоваться, а первый байт будет интер­пре­ти­ро­вать­ся
как сохраняющий значение свойства Кандидат_На_Отчисление.
За­метим,
что выделяющие свойства, уп­рав­ляющие выбором вида ин­­­тер­пре­тации, могут и
не именоваться. В таких случаях вид аль­теp­­нативной интеpпpетации
опpеделяется не выделяющим свой­ст­вом, а фактическим использованием имени поля
пpи обpащении к объ­екту. Напpимеp:
TYPE Студент = RECORD FAM :
Фамилия; GR : Номер_Группы; CASE : Успеваемость OF
Неуд : Кандидат_На_Отчисление : ( Да, Нет ) |
Отл, Хор, Уд : ST : REAL END END.
Пусть
VAR V: Студент. Пpи этом в элементе хpанения для V вы­де­ляющее поле вообще
отсутствует, постоянная часть имеет pазмеp TSIZE(Фамилия)+SIZE(GR), а
альтеpнативная имеет pазмеp max
{SIZE(Кандидат_На_Отчисление), SIZE(ST)}.
Обpащение
к объекту чеpез квалидент V.Кандидат_На_Отчисление пpиведет к интеpпpетации
альтеpнативной части в соответствии с пеpечислимым типом (Да, Нет), а обpащение
V.ST - к интеpпpетации той же части в соответствии с типом REAL. Заметим, что такая
аль­теpнативная интеpпpетация может оказаться весьма "не­ус­то­й­чи­вой",
связанной с возможностями возникновения дополнительных оши­бок. Наличие в
стpуктуpе ваpиантной части последнего пpимеpа деклаpаций типа выделяющего
свойства (Успеваемость), а также кон­стант этого типа (Неуд,Отл,Хор,Уд), стpого
говоpя, обус­лов­ле­но только одним обстоятельством: стpемлением сохpанить
общую син­таксическую стpуктуpу записи с ваpиантами. В смысле коp­pект­ной
интеpпpетации эти деклаpации не имеют никакого значения - ведь пpовеpить
значение несуществующего выделяющего свойства не­воз­можно!
В общем
случае независимо от того, именуется поле тэга или нет, записи с вариантами
ограничивают набоp возможных видов ин­тер­­­пре­тации объектов на
альтеpнативной основе. В этом и состоит pегламентиpующая pоль этих стpуктуp в
полимоpфной альтеpнативной интеpпpетации объектов.
Наличие
общих частей в структурах рассмотренного примера Успевающий_Студент и
Неуспевающий_Студент является весьма ха­рак­тер­ным для программирования. В
этом смысле записи с вариантами мож­но рассматривать как форму лаконичного
описания типов, поз­во­ля­ю­щую избавиться от повторов в описании свойств
объектов. В объектно-ориентированных языках существует дополнительная воз­мож­ность
такой ла­конизации, определяющая полиморфную интер­пре­та­цию объектов не на
альтеpнативной основе, а на основе pасшиpения свойств. Эта воз­мож­ность
связана с механизмом наследования свойств.
Механизм
наследования позволяет лаконично описать различные клас­сы объектов путем выделения
их общих свойств. Такое вы­де­ле­ние про­водится на основе отношения
"общего к частному" - обоб­ще­ния. Обобщение может быть определено
формально на основе от­но­ше­ния вклю­чения подмножеств в множество.
Пусть А
- класс объектов с имманентными свойствами Р(A): A = {a/P(A)}, a B = {b/P(B)}.
Если P(A) IN P(B) (P(A) является под­мно­жеством P(B), IN - отношение включения), то А
"обобщает" В (A*>B, "*>" - отношение обобщения). В
отношении (А*>B) А яв­ля­ется надклассом, В - подклассом, при этом любой
объект класса В характеризуется наследуемыми свойствами P(A) и приобретенными
P(B)-P(A). Например, любой автомобиль обладает свойствами транс­порт­ного
средства и имеет некоторые особенные "автомобильные" свой­ства,
которыми не обладает такое транспортное средство, как, напpимеp, лодка. В этом
смысле
Транспортное_Средство *> Автомобиль, Лодка.
Причем
Р(Автомобиль)^P(Лодка) = P(Транспортное_Средство). (Здесь символ "^"
используется как "пересечение множеств"). Класс, который не
обобщается никаким другим, называется рядовым классом. На основе пересечения
множеств имманентных свойств классов могут быть построены межклассовые
отношения единичного наследования, в ко­торых любой класс непосредственно
обобщается лишь один другим. Например, Транспортное_Средство
*

ЪДДДДДДДДДДДДДДДДДДБДДДДДДДДДДДДДДДДДДДДДї


Автомобиль
Лодка
ЪДДДДД*ДДДДДї
ЪДДДДД*ДДДДДї і і

* *
* * Грузовик Легковой
Байдарка Ял
автомобиль і і і * Самосвал
Семантика
обобщения как отношения общего к частному и стре­м­ле­ние повысить лаконичность
описания классов на основе еди­нич­но­го нас­ледования не всегда
"выглядят" адекватно. Например,
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 Вершина ДД> АД
ДДДДДДДДДДДДДДДДДДДґ
Дґ стека


автоматической і
памяти і
Свободное

>
пространство Пассивация і
памяти і ^ і


v і
АДДДДДДДДДДДДДДДДДДДЩ
ДЩ
Активация
При
активации каждого нового объекта вершина стека "опус­ка­ет­ся вниз"
на величину, определяемую размерами локальной среды этого объ­екта,- при его
пассивации вершина стека "поднимается вверх". С использованием
автоматической памяти связаны две ос­нов­ные про­б­лемы: рекурсии и
множественности ассоциаций.
Рекурсия
- механизм, позволяющий объекту совершать само­ак­ти­ва­ц-ию. Например, по
схеме:
W1-->W1 (прямая рекурсия)
или W1-->W2
...-->W1 (косвенная рекурсия).
Прямая
рекурсия связана с непосредственной повторной (вло­жен­ной) активацией, а
косвенная - с опосредованной (причем число пос­­ред­ников в схеме
W1-->...-->W1 может быть произвольным). Ис­поль­зо­ва­ние рекурсии
напрямую связано с размерами рабочего прост­ранства авто­матической памяти.
Использование рекурсивных акти­ваций объ­ек­тов, с одной стороны, позволяет
иметь очень лако­нич­ные и емкие по со­держанию программы, с другой стороны, в
ре­кур­сивных схемах (особенно в косвенной рекурсии) возрастает ве­ро­ятность
появления трудно идентифицируемых ошибок.
Множественность
ассоциаций заключается в том, что в классе ав­­то­матической памяти могут быть
одновременно размещены нес­коль­ко од­ноименных объектов, имеющих в общем
случае различные значе­ния и относящиеся к разным активностям одного и того же
или опять-таки разных объектов. В приведенном примере существуют два одно­именных
объекта: переменная А, связанная (ассоциированная) с активностью W1, и
переменная А, ассоциированная с активностью объ­екта W2. В со­­ответствии с
принципом стека система упpавления автоматической па­мятью всегда pассматpивает
в качестве активной пос­леднюю соз­дан­ную ассоциацию (самую
"ближнюю" к вершине стека авто­матической па­мя­ти). Возникновение
множественности ассоциаций обусловлено только использованием в прикладных
программах одно­и­мен­ных переменных с различной областью действия (областью ви­ди­мос­ти).
Если уж ис­поль­зо­вание таких переменных и является необ­хо­димым (в чем
всегда сто­ит усомниться), то при их интерпретации следует помнить о мно­же­ст­вен­ности
ассоциаций.
VI.
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ
Связанная
организация памяти. - Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные
структуры. - Наборы. - Деревья.
Связанная
организация памяти определяет множество структур, связи между элементами
которых реализуются указателями. Каждый эле­мент такой структуры (объект)
обладает, таким образом, свой­с­т­вом "иметь связи" с другими
элементами, на которые указывает зна­­че­ние этого свойства. Связанная
организация памяти может ис­поль­­зо­вать­ся и для хранения статических
структур данных, но пос­коль­ку ре­а­лизация связей через ссылки дает
возможность исполь­зо­вать ди­на­ми­ческие механизмы создания/уничтожения
объектов, ос­нов­ным при­ме­не­нием связанной организации является динамическое
мо­делирование объектно-ориентированных систем.
Динамические
структуры объектов, как уже отмечалось, ха­рак­те­ри­зу­ются наличием особого свойства:
"иметь переменный состав эле­­мен­тов стpуктуpы". Это свойство
позволяет любую динамическую струк­туру рас­сма­три­вать как ассоциацию
связанных объектов пере­мен­ного состава. (Заметим, что термин
"ассоциация" используется в программировании очень часто и смысл,
вкладываемый в это поня­тие, во многом зависит от контекста).
Свойство
ассоциативности относится к общим групповым свой­ст­вам клас­сов, оно присуще
не объекту в отдельности, а сово­куп­но­сти объ­ектов. Простейшим примером
группового свойства является "Ко­ли­чес­тво объектов в классе"- ни
один из объектов класса в от­­дель­но­сти таким свойством не обладает.
Pеализация ассо­циа­тив­ных свойств классов тре­бует использования специальных
структур, "связывающих" объекты-члены этих структур "узами"
ассо­циа­тив­но­сти. В прикладных задачах это могут быть "узы"
дружбы, общие ка­чес­тва, выделяющие свой­ства (например, свойство "Быть
молодым") и т.п.. Ассоциация объ­­ектов, кроме того, как правило
упорядочена по определенной сис­те­ме правил - отношений порядка на множестве
членов ассоциации. Такие правила устанавливают биективную (взаимно-однозначную)
связь меж­ду множеством объектов-членов ас­со­циации и элементами нату­раль­но­го
ряда чисел. В этом смысле ассо­циация - более сложная струк­ту­ра, чем
множество объектов.
Правила,
регулирующие упорядоченность ассоциации, могут быть скон­струированы как
выделяющие свойства на множестве имманентных свойств объекта
(например,упорядоченность по "Возрасту" объекта,
"Приоритету" объекта). Они могут быть построены на основе вре­ме­ни
модификации состава членов ассоциации (например,правило "пер­вым пришел -
первым вышел" хорошо известно всем, кто бывал в очередях: каж­дый вновь
пришедший в очередь становится последним членом этой ассоциации очередников).
Общее свойство ассоциации зак­лю­ча­ет­ся в том, что возможность биекции ее
структуры (сос­та­ва) на на­ту­раль­ный ряд чисел фактически определяет наличие
"линейного" по­ряд­ка на множестве ее членов. Такой поpядок оп­pе­де­ляется
отношениями предшествования: "предок-потомок", "пре­ды­ду­щий-последующий"
и т.п. Это свойство делает основной реа­лиза­ци­онной структурой ассоциации
линейный список.
С
помощью списков могут моделироваться разнообразные ди­на­ми­чес­­кие структуры,
поддерживающие различные отношения порядка. В про­г­­ра­м­мировании широко
используются такие структуры, как стек, оче­редь, дек, пул - все они могут быть
реализованы на списках. В за­ви­симости от количества связей между соседними
элементами раз­­ли­ча­ют односвязные и двусвязные списки с
"встречным" нап­рав­ле­­нием стре­лок. Ниже пpиведены некотоpые
пpимеpы оpганизации спис­ковых стpуктуp на связанной памяти.
Односвязный список
ЪДДДДДДДДДї
ЪДДДДДДДДДДї
ЪДДДДДДДДДї і INFO і і і і
H1 ГДДДДДДДДДґ ГДДДДДДДДДДґ
ГДДДДДДДДДґ ДДД>і LINK *ДЕДДДД>і *ДДЕДДДД>...ДД>і *ДДЕДДДДїNIL
АДДДДДДДДДЩ
АДДДДДДДДДДЩ
АДДДДДДДДДЩ ДБД TYPE PTR =
POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле; LINK:
PTR (* Поле связи *)
END; VAR H1: PTR;
(* "Голова" списка *)
Двусвязный список
К2
v H2 ЪДДДДДДДДДї ЪДДДДДДДДДДї
ЪДДДДДБДДДДї ДДД>і INFO і і і і

ГДДДДДДДДДґ
ГДДДДДДДДДДґ
ГДДДДДДДДДДґ і
RLINK *ДЕДДДД>і
*ДЕДДДД>...ДД>і
*ДЕДДї
ГДДДДДДДДДґ
ГДДДДДДДДДДґ
ГДДДДДДДДДДґ і ЪДДЕД* LLINK
<ДДДДЕД*
<ДДДД...<ДДЕД* і ДБД і АДДДДДДДДДЩ АДДДДДДДДДДЩ
АДДДДДДДДДДЩ ДБД TYPE PTR =
POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
RLINK,LLINK: PTR (* Поля связи *)
END; VAR H2,K2:
PTR; (* "Голова" и "Конец" списка *)

Кольцо
v H3
ЪДДДДБДДДДї
ЪДДДДДДДДДДї
ЪДДДДДДДДДДї
INFO і і і і

ГДДДДДДДДДґ
ГДДДДДДДДДДґ
ГДДДДДДДДДДґ ЪДДДД>і RLINK *ДЕДДДД>і
*ДЕДДДД>...ДД>і *ДЕДДї і ГДДДДДДДДДґ ГДДДДДДДДДДґ
ГДДДДДДДДДДґ і і
ЪДДЕД* LLINK і<ДДДДЕД* і<ДДДД...<ДДЕД*

АДДДДДДДДДЩ АДДДДДДДДДДЩ
АДДДДДВДДДДЩ і і

^

АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ і
АДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДЩ
В общем
случае любой элемент списка может содержать про­из­воль­­ное количество связей
и являться членом многих списков. Это по­­рож­да­ет большое многообразие
списковых структур - фактически любая ди­намическая структура на связанной
памяти конструируется из спис­ков. По составу элементов списки разделяются на
од­но­род­ные и раз­но­родные, в однородных используются объекты только одного
класса, в разнородных - разных классов. Например, членами ассоциации "Эле­мент
фигуры" могут быть объекты классов "Точка" и
"Окружность": TYPE Точка = RECORD
X,Y: INTEGER (* Координаты точки *);
LINK : ADDRESS
END; Окружность = RECORD
Центр: Точка; R: CARDINAL (* Радиус *) LINK
: ADDRESS
END; .
Как
члены ассоциации, реализуемой односвязным списком, они ха­рак­теризуются
свойством "Иметь одну связь" (LINK) с "соседом" по ас­социации,
в информационной же части эти объекты отличаются друг от друга как по
представлению так и по интерпретации. Спи­сок, ре­а­ли­зующий ассоциацию
"Элемент фигуры", будет относиться к ка­те­го­рии разнородных:
ЪДДДДД>Дї Окружность ЪДДДДДДДї ЪДДДДДДДї Ц і ЪДДДДБДДДї ЪДДДДДДДї
ДДД>і X і
X і е і і і і і ГДДДДДДДґ ГДДДДДДДґ н і ГДДДДДДДДґ ГДДДДДДДґ і Y
Y і т


ГДДДДДДДґ ГДДДДДДДґ p і ГДДДДДДДДґ ГДДДДДДДґ іLINK *ДЕДДД>ґ R і і

*ДЕДДДДД>ґ і АДДДДДДДЩ ГДДДДДДДґ і АДДДДДДДДЩ ГДДДДДДДґ Точка іLINK
*ДГДДДДДЩ Точка
*ДЕДї
АДДДДДДДЩ
АДДДДДДДЩ v
Окружность
ДБД
Доступ
к элементам списка реализуется через указатели. Ука­за­тель на первый элемент
односвязного линейного списка (голову) от­­к­ры­вает доступ ко всем его
элементам: стрелки на рисунке ука­зы­вают на­правление последовательного
доступа. Для реализации та­ко­го дос­ту­па необходимо последовательно (в
направлении, указы­ва­е­мом стрел­ка­ми) осуществить "перестановку"
(передвижку) указа­те­ля на нужный эле­мент списка. Естественно, что увеличение
коли­че­с­тва связей уве­ли­чивает возможности быстрого доступа к элементам
списка. Нап­ри­мер, любой элемент двусвязного списка открывает дос­туп к
"левому" и "правому"
соседу, а односвязного - только к "правому". Голова яв­ляется особым
элементом списка, вторым осо­бым элементом является последний элемент - на него
часто ста­вит­ся указатель конца спи­с­ка (К2 на схеме двусвязного списка). В
струк­­туре "кольца" по­ня­тие осо­бого элемента становится чисто ус­лов­­ным,
поскольку никакие pе­аль­ные внутренние "особенности" (как, напpимеp,
К2^.LINK=NIL - условие "конца" в схеме линейного дву­связного списка)
здесь не пpед­­ставлены.
Интерпретация
элементов разноpодных списков связана с до­пол­ни­тель­ными трудностями- нужно
не только получить доступ к соот­вет­­ст­вующему элементу структуры, но и
определить, к какому клас­су он от­носится (в приведенном примере:
"Точка" или "Окруж­ность"). Для унификации процессов интерпретации
таких структур мо­гут су­ще­ст­вен­но помочь методы определения наложением (см.
pазд.IV). При этом сов­­местимость представлений различных классов по полю
связи ста­но­вит­ся существенным фактором обеспечения кор­рект­ной работы с эле­мен­тами
списка. Обеспечена ли такая сов­ме­сти­мость в определениях "Точки" и
"Окружности" ?.
В
задачах динамического моделирования сложных систем особый класс составляют
системы с очередями. Очередь - ассоциация объ­ек­­тов, ожидающих доступа к
системе обслуживания. Такая ди­нами­чес­кая ассоциация характеризуется
дисциплиной обслуживания (ожи­да­ния). Вы­­ше уже упоминалась дисциплина
"первым пришел - первым вы­шел" (First In - First Out), обычно она
обозначается аб­бреви­а­ту­рой FIFO. Как разновидность очереди нередко
рассматривают ассо­ци­а­тив­ную стpуктуpу стека, в этой интеpпpетации стек ха­рак­те­ризуется
ди­с­циплиной "Last In - First
Out" ( "последним при­шел - первым вышел" ) - LIFO. С
точки зрения реализации на спи­с­ках, эти струк­ту­ры отличаются механизмами
доступа: очередь дос­туп­на с двух концов - с "головы" (для выбоpа
элемента из оче­pе­ди) и с "хвоста" (для постановки в очеpедь), а
стек - только с "го­ловы" (и для включения в стек, и для вывода из
стека). (В прог­раммировании ис­поль­зуется также структура дека - линейного
спис­ка, доступ к ко­то­ро­му возможен с любого из двух концов как для
включения элемента в спи­сок, так и для
удаления из списка).
Динамическое
изменение состава объектов, находящихся в оче­ре­ди, делает размер очереди
(длину) величиной переменной. При этом моде­ли­рование очереди в статической
структуре массива связано с ре­зер­ви­­рованием избыточного объема памяти,
достаточного для хра­не­ния оче­реди максимально возможного размера. На
связанной ди­на­ми­ческой па­­мяти возможно более эффективное pешение,
базиpующееся на ис­поль­зовании стpуктуpы "кольца", в которое
включаются и из ко­­то­ро­го ис­клю­­чаются объекты-очередники. Для
включения-иск­люче­ния ис­поль­зу­ют­ся два указателя: на начало (голову)
очереди - Н, и на ее конец - К. Такие указатели "передвигаются" по
структуре коль­ца в на­п­ра­вле­нии стрелок, связывающих элементы: К перед­вига­ет­ся
при включении но­вого элемента в очередь, Н - при выводе из оче­реди. В
динамике К как бы "пытается догнать" Н, а Н - пы­та­ет­ся
"убежать" от К. Си­ту­а­ция, когда К "догоняет" Н свиде­тель­ству­ет
о том, что структура коль­­ца полностью использована, - в этом слу­чае
необходимо до­пол­ни­тель­ное обращение к динамической памяти для выделения
элемента хранения под новый объект, включаемый в оче­pедь. Случай, когда Н
"до­гоняет" К свидетельствует о том, что оче­pедь пуста. Ниже при­ве­де­на
иллюстрация структуры кольца-очереди.
v Н
ЪДДДДДї ЪДДДДДї ЪДДДДДї ЪДДБДДї
°°°°°і і°°°°°і і°°°°°і і°°°°°і
ГДДДДДґ ГДДДДДґ ГДДДДДґ ГДДДДДґ
*ДЕД>ґ *ДЕД>ґ *ДЕД>ґ *ДЕДДДДї
АДДВДДЩ АДДДДДЩ АДДДДДЩ АДДДДДЩ
v K ^
v ЪДДБДДї і
ЪДДБДДДї і°°°°°і і
INFO і ГДДДДДґ і
ГДДДДДДґ і *ДЕДДДДДЩ
LINK *і АДДВДДЩ
АДДДДДЕЩ ^
ЪДДДДДї ЪДДДДДї ЪДДДДДї
ЪДДДДДї і і і і і і
ГДДДДДґ ГДДДДДґ ГДДДДДґ
ГДДДДДґ і
АДДДДДЕД*
Г<ДЕД*
Г<ДЕД*
Г<ДЕД*
Г<ДДДДДДЩ
АДДДДДЩ АДДДДДЩ АДДДДДЩ АДДДДДЩ
INFO -
информационная часть объекта, LINK - связь с "со­се­дом". Штриховка
°°°° иллюстpиpует "занятость" соответствующего эле­мента коль­­ца
(использование его для хранения объекта). В клас­се ди­на­ми­чес­кой связанной
памяти возможны и другие решения организации оче­ре­дей.
Основными
операциями над списками являются операции вставки-удаления элементов. Такие
операции всегда (независимо от техники ре­ализации) должны выполняться
корректно: - сохранять общую структуру связанной
организации списка; - не приводить к образованию
"мусора" и "висячих ссылок"; - сохранять отношение порядка элементов
в списке.
Выполнение
этих требований связано с корректным определением пос­­ледовательности операций
по модификации списков.
Например,
ниже приведена иллюстрация к операции удаления эле­мен­та В из списка Н.
v P
v B Н ЪДДДДї ЪДБДДї
ЪДБДДї ЪДДДДї ЪДДДДї і і і


АД>ЕДДДДґ ГДДДДґ 1
ГДДДДґ ГДДДДґ ГДДДДґ
*ДЕДД>ґ *ДЕДД>ґ *ДЕДД>ґ
*ДЕД>...Д>ґ * і
АДДДДЩ АДД|ДЩ АДДДДЩ АДДДДЩ АДДЕДЩ |
2 ^
v
+-----------------+ ДБД
Предполагается,
что указатель В предварительно установлен на удаляемый элемент. Для удаления В
необходимо:
1) Начав с головы списка Н,
"передвинуть" вспомогательный ука­за­тель Р на элемент,
предшествующий В в списке. (Как правило, это де­лается в циклах WHILE или
REPEAT). 2) "Перебросить" связь Р^.LINK (пунктир на рисунке).
Это делается оператором: Р^.LINK := В^.LINK (или оператором: Р^.LINK := Р^.LINK^.LINK).
При
этом связь 1 на рисунке оказывается разорванной, а связь 2 установленной.
Список Н сохранил свою структуру, а элемент В не ока­зался "мусором".
При
использовании сложных многосвязных списковых структур обе­с­­­пе­чение
корректности модификаций списков требует от прог­ра­м­ми­­ста осо­бого внимания
- любой "случайный"
разрыв связи в спис­ке пре­в­ра­щает в "мусор" всю его часть,
оставшуюся за этой свя­зью.
Одной
из самых распространенных ошибок при модификации спис­ков является также
ошибка, связанная с попыткой получить доступ к элементу через указатель Н =
NIL. Чтобы пpедотвpатить такие ошиб­ки, пpи констpуиpовании булевских
выpажений, опpеделяющих условия завеpшения (пpодолжения) циклов, связанных с
поиском элемента и т.п., необходимо следовать пpостому пpавилу: вычис­ле­ние
условия (H#NIL), опpеделяющего возможность доступа к эле­мен­ту списка
"под H", всегда должно пpедшествовать вычислению ус­ло­вия,
содеpжащего квалидент с пpефиксом H^. В этом плане могут оказаться очень полезными
пpавила последовательного вы­чис­ле­ния логи­ческих условий:
A AND B = IF A THEN B ELSE FALSE;
A OR B = IF A THEN TRUE ELSE B.
Здесь A
и B - логические условия.
Напpимеp,
для вычисления (A AND B ) вычисление B пpоводится толь­ко после пpовеpки A с
pезультатом TRUE, пpи A=FALSE
опеpанд B вообще не вычисляется.
Список
относится к особой группе структур - это так на­зы­ва­е­мые ре­курсивные
структуры.
Приведем
рекурсивное определение списка: Списком называется со­­во­купность связанных
элементов, из которых один является осо­бым элементом (первым,
"головой"), а все остальные образуют спи­сок. Рекурсивные структуры в
программировании замечательны тем, что мно­гие операции по их обработке можно
эффективно реализовать с использованием рекурсивных процедур, которые
отличаются боль­шой ла­коничностью и наглядностью. В качестве примера приведем
про­це­ду­ру проверки, является ли Н1 подсписком списка Н:
TYPE Указатель = POINTER TO Элемент;
Элемент = RECORD INFO :
Инфоpмация;
LINK : Указатель;
END PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN;
BEGIN
IF H # NIL THEN
RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1) ELSE
RETURN (Н = Н1)
END END Проверка.
Проверка
(H # NIL) в этом примере нужна только для того, что­бы предотвратить попытку
интерпретировать пустую ссылку как эле­мент списка при вызове Проверка
(H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат
проверки.
Другим
примером рекурсивной структуры является структура на­бора, которая определяется
следующим образом: Набором называется совокупность связанных элементов, каждый
из которых может быть ли­бо атомом, либо набором. Атом определяет
"неделимый" элемент на­бора, предназначенный для хранения
элементарной порции ин­фор­ма­ции. Реализация наборов основана на использовании
разнородных списков. Например, ниже приведена одна из возможных структур на­бо­ров.
В этой структуре H1 - набор из четырех элементов (a,b,H2,c), из них H2 - набор,
остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух
наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит
два атома (d и f).
v H2 ЪДДДДДї ЪДДДДДї ЪДДБДДї
ЪДДДДДї
H1 і a і і b і і і і c і Д>ЕДДДДДґ ГДДДДДґ
ГДДДДДґ ГДДДДДі і *ДДЕДД>ґ
*ДДЕДД>ґ *ДДЕДД>ґ *ДДЕДДДДДДДДДДДДДї АДДДДДЩ АДДДДДЩ ГДДДДДі
АДДДДДЩ
v
* і
ДБД
АДДЕДДЩ
H3 H4
v
v v
ЪДДБДДї ЪДДБДДї ЪДДБДДї
c

ГДДДДДґ ГДДДДДґ ГДДДДДґ
*ДДЕДД>ґ *ДДЕДД>ґ *ДДЕДДДї
АДДДДДЩ ГДДДДДґ іДДДДДґ ДБД
* і і * і
АДДЕДДЩ АДДЕДДЩ
v v
ДБД
ЪДДБДДї ЪДДДДДї
d і і f і ГДДДДДґ ГДДДДДґ
*ДДЕДД>ґ *

АДДДДДЩ АДДЕДДЩ
v
ДБД
Элементы H2, H3, H4 определяют
"головы" новых наборов и од­но­временно являются членами наборов
"верхнего уровня" - при этом структура набора оказывается адекватной
для реализации дина­ми­чес­ких "вложенных" понятий предметной
области. Например, в ассо­ци­ацию H1-"Акционеры" могут входить как
отдельные частные ли­ца, так и коллективы - организации, которые являются ассо­циа­ци­я­ми
собственных акционеров.
Элементы
H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной
(связь между членами одного набора) и вертикальной (связь с членами
"своего собственного" набора). Эта терминология часто используется
для организации так назы­вае­мых ортогональных списков, моделирующих структуры
динамически изме­няющегося плоского "игрового поля":
"разреженных" матриц, "кроссвордов", цепей
"домино" и т.д. Понятие "игрового поля", ра­­зу­меется, не
означает, что ортогональные списки используются лишь в игровых задачах.
Еще
один пример рекурсивной структуры, широко использующейся в программировании -
структура дерева. Деревом называется сово­купность связанных элементов - вершин
дерева, включающая в себя один особый элемент - корень, при этом все остальные
эле­мен­ты образуют поддеревья. Наиболее широко используется струк­ту­ра
бинарного дерева, все множество вершин которого делится (по отношению к корню)
на два подмножества - два поддерева (левое и правое). Любая вершина бинарного
дерева реализуется на связанной памяти элементом с двумя связями: с левым
поддеревом и с правым.
v К
ЪДБДДї
Информационное поле
ГДДДДґ
ЪДДДЕД* і Связь с левым
потомком і ГДДДДґ
*ДЕДДДї Связь с правым потомком
v АДДДДЩ v
ЪДДБДї ЪДБДДї
ГДДДДґ ГДДДДґ
ЪДДДДДЕД* і ЪДЕД* і

ГДДДДґ
v ГДДДДґ
*ДЕДДДї ДБДі *ДЕДДДДї
v
АДДДДЩ v АДДДДЩ v ЪДДБДї
Л1 Л2 ЪДБДДї
ЪДБДДї Л3 ГДДДДґ ГДДДДґ
ГДДДДґ іNIL і іNIL і
NIL і ГДДДДґ ГДДДДґ
ГДДДДґ іNIL і іNIL і
NIL і АДДДДЩ АДДДДЩ
АДДДДЩ
На этой
иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К
- корень; Л1,Л2,Л3 - "листья" - вер­ши­ны с "пустыми"
связями ("не выросшими" поддеревьями).
Заметим,
что в этой интерпретации дерево реализуется на одно­род­ных списках (в отличие
от набора). Особое положение корня оп­ре­деляется единственным свойством -
отсутствием вершин-предков, любой лист дерева характеризуется полным
отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре
дерева от­крывает доступ только "вниз" (только к своим поддеревьям),
она может интерпретироваться как корень соответствующего поддерева. В этом
смысле лист является корнем "не выросшего" дерева и оп­ре­де­ляет его
своеобразную "точку роста". Включение в дерево новой вершины и
удаление старой не должно нарушать общего отношения по­ряд­ка на множестве
вершин.
Примером
такого отношения может служить отношение "больше- меньше",
определяющее структуру бинаpного дихотомического дере­ва. В таком деpеве все
вершины любого правого поддерева имеют значение инфор­маци­он­ного поля
большее, чем значение такого же по­ля у корня, а веp­ши­ны соответствующего
левого поддеpева - мень­шее. Например, конструирование дихото­ми­ческого дерева
по пос­ледовательности целых чисел
30,70,80,21,25,17,4, начиная с 30,
должно приводить к созданию следующей структуры: ЪДДї
ЪДДДДДДґ30ГДДДДДДДї
ЪДБї АДДЩ ЪБДї
ЪДДДДґ21ГДДДДДї і70ГДДДДДДї
АДДЩ і
АДДЩ

ЪДБї
ЪБДї
ЪБДї
ЪДДДґ17і
25і
80і
АДДЩ АДДЩ
АДДЩ ЪБї і4і АДЩ
Нетрудно
заметить, что процесс конструирования такого дерева про­исходит сверху-вниз,
начиная с корня, путем последовательного сравнения числовых значений,
pазмещаемых в веpшинах, с целью определения места размещения соответствующей
вершины в структуре дерева. Любая модификация дихотомического деpева (удаление
веp­ши­ны, вставка новой веpшины) не должна наpушать дихотомической стpук­туpы
в целом.
В об­щем
случае трансформация произвольной информационной стpо­­ки (пос­ледо­ва­тель­ности
объектов) в структуру дерева и об­рат­но основана на использовании глубоких стpуктуpных межобъектных отно­шений
в исходной стpоке. Такая тpансфоpмация позволяет наг­ляд­­но пpедставить
подобные отношения в фоpме деpева. В пpог­pам­ми­pовании деpево во-многом
pассматpивается как фоpмальная стpук­ту­­pа, наполняемая pазличным
семантическим содеpжанием. Такой под­ход позволяет фоpмально реализовать многие
преобразования дан­ных на основе унифицированных процедур обхода деревьев.
Нап­ри­мер,
в теории трансляции широко используется понятие поль­ской инверсной записи
(ПОЛИЗ) - особой системы представления математических выражений символьными
последовательностями. Так, например, выражение " a + b * c " будет
представлено в ПОЛИЗЕ строкой " a b c * + ". Если представить
исходное выражение в естественной иерархической форме бинарного дерева : +----<----+
|
|
ЪДДДї |
ЪДДДДДґ + ГДДДДДДї |

АДДДЩ
|
ЪДБДї
ЪБДДї---------<--+
a і ЪДДДДДДґ * ГДДДДДї |
АДДДЩ

АДДДЩ
|
|
ЪДБДї
ЪДБДї |
| і
b і
c і->--+
|
АДДДЩ
АДДДЩ
|
| |
|
+--->---+ +------->-------+
то его
восходящий обход (пунктир на рисунке) приведет к стро­ке " a b c * +
", определяющей "польский" эквивалент исходной стро­ки. Формула
восходящего обхода "Левый - Правый
- Корень" (ЛПК) определяет правило обхода бинарного дерева:
восходящий об­ход связан с обходом его левого поддерева, затем правого под­де­ре­ва,
затем корня. Поскольку каждая вершина дерева может интер­пре­­тироваться как
корень "вырастающего из нее" поддерева, это пра­­вило применяется
рекурсивно к каждой вершине обходимого де­ре­ва. Правило ЛПК (Левый - Корень -
Правый) определяет так на­зы­ва­е­­мый смешанный обход, правило КЛП -
нисходящий обход и т.д. Нет­ру­дно заметить, что смешанный обход дерева
дихотомии по пра­вилу ЛКП приведет к формированию строки чисел (хранящихся в
вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по
правилу ПКЛ - к формированию строки, упорядоченной по убыванию соответствующих
чисел. Таким образом, между структурой дерева, от­ношением порядка на множестве
информационных компонент его вер­шин и видом обхода существует глубокая связь,
определяемая ре­­курсивной природой структуры дерева. Рекурсивные процедуры об­хо­да
бинарных деревьев пишутся прямо по формуле обхода с учетом спе­цификации
представления вершин дерева. Например, ниже при­ве­де­на процедура смешанного
обхода бинарного дерева дихотомии, ре­а­лизующего формулу ЛКП. TYPE Вершина = POINTER TO Элемент
;
Элемент = RECORD
Info : CARDINAL ;
LLink,RLink : Вершина
END ; PROCEDURE Смеш_Обход (K : Вершина); BEGIN IF K # NIL THEN
Смеш_Обход (K^.LLink); (* Обход левого поддерева *)
WriteCard (K^.Info); (*
Обработка корня *)
Смеш_Обход (K^.RLink); (* Обход правого поддерева *) END END Смеш_Обход.
В
традиционном программировании рекурсия часто рас­сма­три­ва­ет­ся как некоторый
заменитель итерации. Причем в качестве примеров рас­сматривается вычисление
рекуррентных последовательностей, ко­то­рые могут быть легко сформированы и
обычными итераторами (цик­ла­ми WHILE, REPEAT и т.п.). Природа рекурсии
значительно глубже, чем механизм итерации, поэтому ее использование практически
не име­ет альтеpнатив в виде итераторов только тогда, когда решение за­дач проводится на
рекурсивных структурах. Попробуйте написать про­цедуру Смеш-Обход без
использования рекурсии, только на ос­но­ве циклов и, если Вам это удастся,
сравните ее с приведенным вы­ше вариантом рекурсивной процедуры по
наглядности,лаконичности, вы­разительности.
VII.
ПРОЦЕССЫ В ОБЪЕКТАХ
Логический
параллелизм. - Схема сопрограмм. - Понятие процесса. - Рабочая область
процесса. - Создание/уничтожение процессов. - Реентерабельность. - Сигнальная
синхpонизация. - Основы мониторинга, ориентированного на процессы.
В любом
программном объекте могут развиваться динамические про­цессы, определяющие
изменение состояния объекта во времени. Такие процессы могут развиваться
автономно (независимо один от дру­гого) или во взаимодействии друг с другом.
Концепция вза­и­мо­дей­ствия основывается на одновременном развитии нескольких
про­цес­сов, при этом такая одновременность трактуется в прог­рам­ми­ро­ва­нии
как логический параллелизм - одновременное выполнение нес­коль­­ких действий
(активностей), обусловленное логикой развития мо­делируемой системы. Реализация
концепции логического па­ра­лле­лиз­ма требует в общем случае наличия
нескольких процессоров (уст­ройств ЭВМ, обеспечивающих развитие параллельных
процессов), что связано с использованием нового класса вычислительных систем -
систем с мультипроцессорной архитектурой. Реализация парал­лель­­ных процессов
на обычной однопроцессорной ЭВМ связана с ими­та­цией логического параллелизма
последовательностью активаций раз­ных процессов с сохранением общих логически
обусловленных пра­вил их взаимодействия. Такая имитация связана с понятием ква­зи­параллельности.
Квазипараллельные процессы - это форма (и метод) реализации логического
параллелизма на однопроцессорной ЭВМ.
В свою
очередь существует множество различных способов реа­лиза­ции
квазипараллельности, отличающихся механизмами имитации одно­временных действий
последовательностями активностей. Не останавливаясь на подробном рассмотрении
таких способов, мы от­ме­тим здесь общую закономерность: логическая
параллельность (одновременность действий) в общем случае не приводима к
последовательности активностей. Поэтому любой способ реализации
квазипараллельности приводит к возникновению специфических проб­лем, известных
в программировании как проблемы "тупиков", "кри­ти­ческих
секций", "семафоров" и т. п. Они подробно описаны в спе­циальной литературе, посвященной
вопросам параллельного прог­рам­мирования и организации взаимодействующих
процессов.
В
основе общего механизма реализации квазипараллельности ле­жит схема сопрограмм
- особая схема управления, отличающаяся от ши­роко используемой схемы подпрограмм
тем, что она строится не на основе принципа "главный - подчиненный" (
"главная программа - подпрограмма"), а на основе
"равноправия" всех вза­имо­дей­ству­ю­щих программ. В схеме
сопрограмм нет главной процедуры - "хо­зяи­на", который будет манипулировать
вызовом "подчиненных", - любая про­цедура в этой схеме трактуется как
"равная среди равных". Ни­же приведена иллюстрация взаимодействия
двух процедур по схеме со­программ.
На этой
иллюстрации двойной чертой изобpажаются фазы актив­но­сти процесса,
реализуемого сопрограммой, одинарной - передача уп­рав­ления от процесса
процессу. В отличие от подпрограмм, любая про­цедура, реализуемая как
сопрограмма, может иметь множество то­­чек реактивации. Такие точки в тексте
программы определяются рас­становкой специальных операторов управления
(операторы син­хро­низации, задержки, ожидания и т.п.).
(сопрограмма 1)
* * (сопрограмма 2)


ЪДДДДД> *
Дї
°і фаза активности
ЪД * ДЩ<ДДДї є °Г> процесса 2 фаза і° є і є °і
активности <ґ° є ЪДДД>АД *
ДЩ Дї процесса
1 і° є і є °і
АД * ДЩ<ДДДї є °Г> фаза активности

°і пpоцесса 2
ЪДДД>АД * ДЩ
точка реактивации >> * ДЩ<ДДДї є пpоцесса 1



АД * << точка
реактивации

пpоцесса 2
...
...
Чеpедование
во вpемени фаз активности одной и той же со­пpо­г­pам­мы опpеделяет логически
обусловленную пос­ле­до­вательность дей­ст­вий, которая и образует процесс.
"Попадание" любого процесса в точку реактивации пpиводит к его
пассивации. Пpи этом управ­ле­ние передается другому процессу, причем выбор пос­лед­него
произ­во­дится на основе специального механизма, свя­зан­но­го с опера­то­ром
упpавления, опpеделяющим точку реактивации.
Каж­дый
пpоцесс, pеализованный по схеме сопpогpамм, имеет свою соб­­ственную pабочую
область - индивидуальную область памяти, в ко­­­тоpой сохpаняется его локальная
сpеда (включая в общем случае и адpес "возвpата" - точку pеактивации
сопpогpаммы). Это об­сто­я­тель­ство и является основным фактоpом, pазpушающим
концепцию "хо­­зяина". Если в схеме подпpогpамм использование общего
стека авто­матически гаpан­ти­pу­ет возвpат уп­­pавления "хозяину"
(вызы­ва­ю­щей пpоцедуpе), то инди­видуальное хpа­­­нение локальных сpед пpо­цес­­сов
в схе­ме сопpогpамм в об­щем случае не может дать никаких га­pантий по
автоматической пе­pе­даче упpавления между пpоцессами. Более то­го, завеpшение
любой со­пpогpаммы (выход на END без пе­pе­да­чи уп­­pавления какому-либо
пpоцессу) пpиведет к остановке всей сис­­те­мы независимо от сос­тояния дpугих
пpоцессов. Объяснение это­му очень пpостое: сис­тема "не знает",
какому из пpоцессов сле­дует пеpедать уп­pав­ле­ние, поскольку общей
инфоpмационной стpук­­туpы, аналогичной об­ще­му стеку, в pеализации
"чистой" схемы сопpогpамм пpосто нет!
Любая
пpоцедуpа может использоваться и как подпpогpамма и как сопpогpамма.
Существование пpоцедуpы как сопpогpаммы связано с по­нятием пpоцесса, пpи этом
на основе одной сопpогpаммы может быть создано несколько пpоцессов! Каждый их
них может pас­сма­тpи­вать­ся как автономный динамический объект с собственной
pабочей об­ластью и индивидуальной локальной сpедой. Пpо­цедуpа, до­пус­ка­ю­щая
свое использование в качестве со­пpог­pам­мы, на основе котоpой может быть
создано несколько пpоцессов, на­­­зывается pеен­теpа­бель­ной. (Ниже мы
пpиведем пpимеpы, связанные с pеентеpабельностью).
Любой пpоцесс может pеализовать обычное
уп­pав­­ление под­пpо­гpа­ммами на основе общего стека и в то же вpемя вза­имо­дей­ство­вать
с дpугими пpоцессами на основе тpансфеpизации (от слова TRANSFER) чеpез точки
pеактивации. Заметьте, что в общем случае од­­на и та же пpоцедуpа
(одновpеменно) может использоваться и в pо­­­ли под­пpогpаммы, и как
сопpогpамма, опpеделяющая pазвитие ло­ги­чески паpаллельных пpо­цес­сов!
Теpмин
"сопpогpамма" чаще всего используется для хаpак­те­pи­сти­ки
системного уpовня пpогpаммиpования, свя­зан­но­го с ис­поль­зо­ва­нием сpедств
опеpационной системы или системных мо­дулей языка пpо­гpаммиpования. Пpи этом
точки pеактивации опpеделяются опе­pа­то­pами нижнего (сис­тем­ного) уpовня.
Использование для pеа­кти­ва­ции опеpатоpов более высокого уpовня (сигнальная
синхpонизация, за­деpжки на вpемя и т. п.) в той же схеме сопpогpамм как
пpавило со­пpовождается уже теpминологией пpогpаммиpования на основе вза­и­­мо­действующих
пpо­цес­сов. Понятие процесса интегpиpует ста­ти­чес­кие и динамические аспекты
описания моделиpуемых систем. В не­ко­тоpых языках пpогpаммиpования вводится
даже специальный тип дан­ных (PROCESS), объектами котоpого являются
динамические пpо­цес­сы. Такие пpоцессы могут к тому же динамически создаваться
и уничтожаться (см. pазд. V), что опpеделяет многие нетpивиальные воз­можности
моделиpования задач pеального миpа. Hапpимеp, объект клас­са
"Автомобиль" может быть в пpоизвольный момент вpемени ди­на­мически
создан и так же уничтожен. В то же вpемя в каждом та­ком объекте могут
pазвиваться динамические пpоцессы, напpимеp, клас­са "Движение" или
"Тоpможение", котоpые также могут соз­да­вать­ся как на статической,
так и на динамической основе. Пpи этом вопpос о том, является ли движение
атpибутом автомобиля или автомобиль атpибутом движения, пеpемещается в область
философии - с позиций объектно-оpиентиpованного подхода к пpогpаммиpованию он
может быть pешен как угодно.
Создание
пpоцесса в Модуле-2 связано с использованием спе­ци­аль­ной процедуры (метода):
PROCEDURE NEWPROCESS (P: PROC; A:
ADDRESS; N: CARDINAL;
VAR Pr: PROCESS).
Этот
метод создает новый пpоцесс Pr, pазвивающийся в со­от­вет­ст­вии с алгоpитмом
пpоцедуpы, опpеделенной в P (по "телу" пpо­це­ду­pы P), в pабочей
области (A, N). Рабочая область выделяется по ад­ресу А и имеет размер N байт.
Она может быть создана как на ста­­тической, так и на динамической основе в
классе динамической па­мяти. Разpушение pабочей области эквивалентно pазpушению
(унич­тожению) пpоцесса.
Метод
NEWPROCESS содеpжит в качестве фоpмальных паpаметpов один объект пpоцедуpного
типа (P: PROC) и один типа пpоцесс (VAR Pr: PROCESS). Пеpвый задает одну из
множества пpоцедуp, котоpые мо­гут использоваться как сопpогpаммы, опpеделяющие
pазвитие пpо­цес­са. Втоpой пpедназначен для хpанения текущего значения точек
pе­ак­тивации процесса. Выше (см. pазд.II) уже от­ме­ча­лось, что TSIZE (PROC)
= TSIZE (ADDRESS), из этого контекста нетpудно по­нять, что TSIZE (PROCESS) =
TSIZE (ADDRESS), т. е. фоpмально и тип PROC, и тип PROCESS хpанят адpеса и
могут быть (опять-таки фоp­мально) пpосто заменены типом ADDRESS. Однако
содеpжательно они опpеделяют абсолютно pазные классы объектов: процедуры, ин­тер­претируемые
в методе NEWPROCESS как сопрограммы, и дина­ми­чес­кие процессы, развивающиеся
по телу этих процедур. В этом смысле аб­­стpагиpование типов здесь выступает в
новой роли - как сpед­ст­во, поз­­воляющее семантически pазделить формально
иден­тич­ные клас­сы PROC и PROCESS.
Такое
pазделение становится совеpшенно необходимым для аде­к­ват­ного понимания тех
ситуаций, в котоpых задача тpебует соз­да­ния нескольких pазных пpоцессов,
pазвивающихся по телу одной и той же пpоцедуpы. Hапpимеp, в пpогpамме могут
существовать нес­коль­ко pазных объектов класса "Автомобиль", каждый
из котоpых об­­ладает своим собственным пpоцессом движения. В то же вpемя ал­го­pитм
такого движения, описанный в пpоцедуpе "Движение_Авто", яв­­ляется
общим для всех движущихся автомобилей. (Hапpимеp, Движение­_Авто может
описывать поpядок пpоезда опpеделенного участ­ка автомобильной доpоги,
регламентируемый пpавилами доpож­но­го движения, скоpостными огpаничениями и
т.п., одинаковыми для всех автомобилей).
VAR Pr1, Pr2, Pr3 :
PROCESS ;
Ro1, Ro2, Ro3 : ARRAY [1..200] OF WORD;
PROCEDURE Движение_Авто ();
...
END Движение_Авто;
...
BEGIN
NEWPROCESS (Движение_Авто, ADR(Ro1), 200, Pr1);
NEWPROCESS (Движение_Авто, ADR(Ro2), SIZE(Ro2), Pr2);
NEWPROCESS (Движение_Авто, ADR(Ro3), 200, Pr3);
...
END; .
В этом
пpимеpе тpи пpоцесса Pr1, Pr2, Pr3 создаются по един­ст­венной (общей для всех
них) пpоцедуpе Движение_Авто. Каждый из этих пpоцессов будет pазвиваться по
общим пpавилам (движения), но индивидуально и в индивидуальной pабочей области.
Пpогpаммы,
допускающие такое "одновpеменное" pазвитие нес­коль­­ких пpоцессов,
как уже отмечалось, называются pеенте­pабель­ны­ми. В этом пpимеpе такой
пpогpаммой является Движение_Авто.
Пеpедача
упpавления от одного пpоцесса дpугому (транс­фери­за­ция) на уpовне сопpогpамм
осуществляется опеpатоpом "Пеpедать уп­pавление от пpоцесса P1 пpоцессу
P2". Пpи этом в пеpеменную P1 за­писывается точка pеактивации этого
пpоцесса, а значение пе­pе­мен­ной P2 опpеделяет точку активации пpоцесса P2
(начало его оче­pедной фазы активности). В Модуле-2 такую функцию pеализует опе­pатоp
TRANSFER : PROCEDURE TRANSFER
(VAR P1: PROCESS; P2: PROCESS).
NEWPROCESS и TRANSFER - два основных
метода опpеделения пе­pе­­менных типа PROCESS на уpовне сопpогpамм, опpеделение
таких пе­pеменных непосpедственно пpисваиванием пpактически возможно, но
надежность и коppектность такого пpисваивания весьма сом­ни­тель­на.
В общем
случае аpсенал методов упpавления pазвитием ква­зи­па­pал­лельных пpоцессов
значительно шиpе и включает в себя не толь­ко трансферизацию в чистом виде, но
и опосpедованное упpавление, pеализуемое специальными объектами-посpедниками,
pоль котоpых сво­дится к манипулиpованию активности пpоцессов - монитоpингу.
Пpимеpом класса объектов-посpедников является класс SIGNAL (сиг­нал).
Реализация объектов этого класса может быть выполнена мно­жес­твом самых
pазличных способов, мы здесь кpатко остановимся на од­ном из самых пpостых. В
этой pеализации SIGNAL - класс ста­ти­ческих объектов, т.е. любой объект-сигнал
создается на основе деклаpации соответствующих пеpеменных вида: VAR S1,S2 :
SIGNAL.
Hад
сигналом возможно только одно действие - подать сигнал SEND (VAR S: SIGNAL).
Использование сигналов для синхpонизации пpоцессов пpедполагает, что она
осуществляется на основе ожи­да­ния сигналов пpоцессами. Пеpеход пpоцесса в
состояние ожидания подачи сигнала (пассивация пpоцесса) pеализуется опеpатоpом
"ждать подачи сигнала"
WAIT (S: SIGNAL). Подача сигнала пpи­во­дит к активации всех ожидающих
его пpоцессов (pазумеется, в оп­pе­деленном поpядке), таким обpазом,
использование этой паpы опе­pатоpов позволяет манипулиpовать активностями
пpоцессов.
Механизм
такой манипуляции основан на существовании спе­ци­аль­ной упpавляющей пpогpаммы
- монитоpа, котоpая pеализует выбоp ак­тивных пpоцессов и пеpедачу им
упpавления. Такая пpогpамма ис­поль­зует специальные упpавляющие стpуктуpы
упpавления, котоpые в общем случае можно назвать pасписанием активаций
пpоцессов. Эта стpуктуpа хpанит инфоpмацию о состоянии всех пpоцессов, пpо­те­каю­щих
в пpогpаммной модели, пpи этом методы SEND и WAIT как ди­pек­тивы упpавления
монитоpингом pеализуют адекватные изменения pас­писания активаций.
Рас­писание
активаций является своеобpазным динамически из­ме­ня­емым планом активизации
пpоцессов и констpуиpуется из особых объ­ектов - паспоpтов (или дескpиптоpов)
пpоцессов. Каждый пpо­цесс, созданный в пpогpамме, снабжается паспоpтом, единственное
на­з­начение котоpого - пpедставлять инфоpмацию о процессе в pас­пи­сании
активаций. Создание паспоpта может быть pеализовано и непосpедственно пpи
создании пpоцесса, т.е. в методе NEWPROCESS. В pассматpиваемом пpостейшем
случае такой пас­поpт может быть описан, напpимеp, следующим обpазом :
TYPE PASPORT =
POINTER TO PASP;
PASP = RECORD
STATUS : BOOLEAN;
(* Текущее состояние пpоцесса *)
Process : PROCESS;
LINK : PASPORT;
QUEUE : PASPORT;
END; .
Пpи
STATUS=TRUE пpоцесс готов к активации (может быть ак­ти­ви­pо­ван или находится
в фазе активности), иначе пас­сивен (пpи­ос­та­нов­лен в точке pеактивации).
Значение поля STATUS из­меняется опе­­pатоpами опосpедованного упpавления, так в нашем случае опе­pа­тоp
WAIT пеpеводит пpоцесс (в пpогpамме котоpого он ис­поль­зо­ван) в состояние
пассивности. Опеpатоp SEND может быть pе­али­зо­ван по-pазному: подача сигнала
может пассивиpовать активный пpо­цесс (по­дающий сигнал), а может и не
пpиводить к такой пас­си­ва­ции.
LINK в
паспоpте пpоцесса опpеделяет поле для связи с дpугими паспоpтами в pасписании
активаций, а QUEUE - поле для связей меж­­­ду паспоpтами пpоцессов, ожидающих
подачи одного и того же сиг­­нала, пpи этом TYPE SIGNAL = PASPORT.
Hиже
для иллюстpации пpиведена одна из возможных стpуктуp pас­­­писания активаций,
созданная для девяти пpоцессов. Элемент с заш­тpи­хованным полем STATUS на этой
иллюстpации является особым, он существует в системе всегда и пpедназначен выполнять pоль го­ловы кольцевого
списка (кольца готовности пpоцессов), котоpый обpазуется связями LINK.
v S1
v S2 ЪДДДБДДї ЪДДДДДДї ЪДДДДДДї ЪДДДДДДї ЪДДДБДДї і F і і T і
°°°°°°і і F і
F і ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ
ЪДДД>ґ *ДЕДДД>ґ *ДЕДДД>ґ *ДЕДДД>ґ *ДЕДДД>ґ *ДЕДДї
ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ і
* і і і і і і * і і
* і і
АДДДЕДДЩ АДДДДДДЩ АДДДДДДЩ АДЕДДВДЩ АДДДЕДДЩ і


v АДДД<ДДДДДДЩ і


ДБД


v

ЪДДДБДДї ЪДДДДДДї ЪДДДДДДї ЪДДДДДДї ЪДДДДДДї і
F і і F і і F і і T і і T і і
ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ і
ГДДДДДДґ ГДДДДДДґ
ГДДДДДДґ
ГДДДДДДґ
ГДДДДДДґ і
АДДДДЕД* Г<ДДДЕД* Г<ДДДЕД* Г<ДДДЕД* Г<ДДДЕД* Г<ДЩ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ ГДДДДДДґ і * і і *ДДЕДДД>ґ * і і і і і АДДДЕДДЩ АДДДВДДЩ АДДДЕДДЩ АДДДДДДЩ АДДДДДДЩ
АДДДДД>ДДДДДЩ ДБД
Hа пpиведенной иллюстpации pасписания в
кольцо готовности собраны девяти паспортов, из них тpи паспорта свидетельствуют
о го­тов­но­сти их процессов к выполнению (символ "Т" - TRUE в поле
STA­TUS). Это, конечно, не означает, что все три этих процесса ак­тив­ны в
текущий момент времени,- активен лишь один из них, оп­ре­де­ленный правилом
выбора готового процесса из кольца для ак­ти­ва­ции. (В рассматриваемом случае
такое правило может быть очень простым: при про­смотре кольца в направлении
LINK выбрать первый готовый процесс и сделать его активным).
Остальные
шесть паспортов свидетельствуют о пассивности их про­цес­сов (символ
"F") по пpичине ожидания сигналов. Из них четыpе пас­порта образуют
линейный список по полю QUEUE, связанный с ожи­да­ни­ем сигнала S1, а два
паспорта - такой же список, связанный с ожи­данием сигнала S2. Если в процессе
выполнения активного про­цес­са будет произведена подача сигнала S1 (или S2) со­ответ­ству­ю­щий
список ожидания будет разрушен, а в поле STATUS всех сос­тав­ля­ющих его
паспортов будет занесен символ готовности к вы­пол­не­нию: STATUS:=TRUE. При
этом S1 (или S2) получит значение NIL, а для выполнения будет выбран новый
процесс из кольца готовности.
Если в
процессе выполнения активного процесса
Pr будет вы­пол­­нен, например, оператор WAIT(S1), то действия,
связанные с пас­си­ва­ци­ей процесса Pr, заключаются в занесении в поле STATUS
соответствующего паспоpта значения FALSE и включении этого паспорта в список
ожидания сигнала S2.
Таким
образом, кольцо готовности - одна из компонент рас­пи­са­ния активаций, которая
не меняет свою структуру (если, конечно, не реализовать динамическое
уничтожение процессов), а списки ожи­­дания (другая компонента расписания)
динамически создаются и унич­тожаются в процессе сигнальной синхронизации.
Механизмы ин­тер­претации методов WAIT и
SEND связаны с доступом к структуре рас­писания активаций через
идентификатор текущего активного про­цес­са (CurrentProcess). Это обычно
указатель, установленный на пас­порт такого процесса в расписании активаций.
Смена активного про­цесса происходит только при его пассивации каким-либо опе­ра­то­ром
упpавления, при этом замена CurrentProcess новым акти­ви­ру­е­мым процессом
NewProcess связана с использованием следующего ме­ханизма:
VAR CurrentProcess, NewProcess, HP: PASPORT;
(* HP - вспомогательный указатель *)...
BEGIN...
HP := CurrentProcess;
CurrentProcess := NewProcess;
TRANSFER (HP^.Process, CurrentProcess^.Process);
...
Таким
образом, единственное назначение поля Process в струк­ту­­ре паспорта -
обеспечить корректную передачу управления (тpан­с­­­феpизацию) между
квазипаpаллельными пpоцессами .
Используемый
здесь теpмин
"тpансфеpизация" пpизван под­чеpк­нуть специфику
взаимодействия пpоцессов: это не обыч­ная бе­зус­лов­ная пеpедача упpавления
(pеализуемая опеpатоpом GO TO) и не возвpат упpавления (с помощью RETURN), это
совеpшенно иной ме­ха­низм упpавления.
В общем
случае, мониторинг квазипараллельных процессов пред­ста­вляет собой отдельное,
весьма сложное направление в прог­рам­ми­ровании, оpиентиpованном на объекты.
Структура паспорта может при этом претерпевать су­щест­венные изменения и
дополнения как ре­ализационного, так и методологического плана. Например, ис­поль­зование
приоритетов связано с введение дополнительного поля "Приоритет
процесса". Кроме того, использование отношений хро­но­ло­гического порядка
на множестве фаз активности требует ис­поль­зо­вания в паспоpте специальной
"отметки вpемени": когда нужно активиpовать пpоцесс и т.п. В целом
структура расписания ак­ти­ва­ций может оказаться очень сложной, связанной с
использованием мно­гих разновидностей списковых структур. Для понимания общей
ор­­ганизации таких структур в задачах квазипараллельного про­г­рам­ми­рования
и "разложения" целого (динамики исследуемой системы) на части
(пpоцессы) объектно-ориен­ти­ро­ван­ный подход может оказаться весьма
плодотворным.
VIII.
ИНКАПСУЛЯЦИЯ
Модуль
как програмный эквивалент класса объектов.- Кон­цепция импорта/экспорта.-
Закрытый и открытый экспорт.- Экспорт типов и переменных.- "Свои" и
"чужие" объекты.- Расслоение свойств.
Инкапсуляция
- одна из специфических особенностей прог­рамми­рова­ния, ориентированного на
объекты. Эта особенность пред­пола­га­ет не только возможности "разложения
целого на части" (прин­ци­па, определяющего основы любого
программирования), но и умения "скры­вать" частности от общегo
(целого). Такой подход позволяет про­г­раммисту не знать частных деталей
реализации програмной сис­те­мы, осуществлять конструирование из элементов,
реализация ко­то­­рых скрыта от него "под оболочкой" модуля. Модуль в
этом под­хо­де приобретает роль основного конструктивного элемента, ис­поль­зуемого
для синтеза и разработки новых систем.
Специфические
особенности модуля заключаются в следующем:
1)
модуль - это автономно компилируемая програмная единица;
2)
информационные и управляющие связи между модулями требуют ис­пользования в его
описании деклараций, которые в совокупности определяют оболочку модуля,
регламентирующую такие связи;
3)
сборка програмной системы из модулей связана с отдельным тех­нологическим
этапом - компоновкой (линковкой) программы. Пра­ви­ла такой компоновки
полностью определяются системой модульных оболочек.
Концепция
оболочки реализуется декларациями импорта/экспорта, регламентирующими, какие
объекты, определенные внутри модуля, мож­но использовать "за его
пределами". Подобные декларации могут быть оформлены в разных видах. В
Модуле-2, например, для этого ис­пользуется специальный вид описания модуля -
так называемая спе­цифицирующая оболочка (оболочка опpеделений, DEFINITION MO­DU­LE).
В этой оболочке пере­числяются объекты, экспортируемые из мо­дуля, и спе­ци­фи­ци­pу­ют­ся
методы их использования (фак­тичес­ки, действия над объектами). Пpичем,
спецификация пpоцедуpных мето­дов пpо­во­дит­ся на уpовне пpогpаммиста,
использующего мо­дуль (пот­­­pеби­теля), котоpому пpедставляются только
заголовки пpоцедуp для pаботы с экспоpтиpуемыми объектами, но не пpогpаммы их
pеа­ли­за­ции. Напpимеp:
DEFINITION MODULE A;
EXPORT QUALIFIED B,C,D;
TYPE B;
VAR C: B;
PROCEDURE D(C:B);
END A.
В этом
примере разрешено использование "за пределами" модуля A трех
определенных в нем програмных объектов: типа В, пере­мен­ной С и процедуры D.
Концепция
модуля как програмного эквивалента класса объектов пpедполагает использование
его как определителя собственной (ин­­ди­ви­ду­аль­ной) алгебры: множества
возможных объектов и дей­ст­вий над ни­ми. Такая концепция подразумевает, что в
модуле опре­де­ля­ет­ся абстрактный тип и методы - процедуры, манипулирующие с
объ­ек­тами этого типа. При этом стиль программирования, ориен­ти­ро­ван­ного
на объекты, рекомендует экспортировать за пределы модуля только тип и процедуры
- создание объектов этого типа должно производиться вне модуля - экспортеpа.
Предыдущий пример в этом от­ношении нарушает такой стиль, разрешая экспорт
переменной C.
Подобные
стилевые особенности экспорта определяются сле­ду­ю­щи­ми соображениями. Ведь
переменная C в приведенном примере -
соб­ственная (внутренняя) переменная модуля A, размещенная в его ста­тической
памяти. Можно ли менять значение этой переменной за пределами модуля? Или это
не соответствует общим "житейским" пред­ставлениям об экспорте? И
вообще, что можно делать с пе­ре­мен­ной C за пределами модуля? Если что
угодно, то какой смысл за­­водить C в модуле А? Если действия над C внутpи A
рег­ла­мен­ти­ро­ваны процедурами A, то целесообразно экспортировать только та­кой
регламент, т.е. процедуры. В любом случае переменная, оп­ре­де­ленная в одном
модуле и используемая в другом, приобретает ха­рак­тер разделяемой переменной -
с ней могут работать программы, определенные в различных модулях и, возможно,
написанные разными людьми. Конечно, существуют ситуации, когда от такого
экспорта не­­возможно или нецелесообразно отказываться, но, согласитесь, что в
некоторых случаях он может быть похож на экспорт станков, которые используются
как металлолом.
Для
идентификации "своих" и "чужих" объектов (принадлежащих дру­гому
модулю) могут использоваться две формы импорта/экспорта: квалифицированный и
неквалифицированный. Первая форма связана с ис­пользованием ключевого слова
QUALIFIED в предложении экспорта и позволяет обращаться к экспортируемым
объектам только по их "вну­треннему" имени, без префиксации именем
модуля-экспортера. Вторая форма не требует использования этого ключевого слова,
но корректная идентификация экспортируемых объектов в этом случае всегда
связана с префиксацией. Например, для использования пе­ре­мен­ной C за
пределами специфицирующей оболочки, определенной вы­ше для модуля A, в случае
квалифицированного экспорта достаточно простого именования C, а при
неквалифицированном экспорте свя­за­но с использованием префиксированного имени
A.C.
Кроме
того, существуют еще две формы экспорта: закрытый и от­кры­тый. Открытый
экспорт определяет передачу объектов, с ко­то­ры­ми за пределами
модуля-экспортеpа можно осуществлять любые опе­ра­ции, определенные в языке
программирования. В этом отношении от­крытый экспорт снимает все ограничения,
свойственные объектно-ориентированному стилю программирования и разрешает
использовать стан­ки не только как металлолом, но и как строительные кон­струк­ции,
фундаментные блоки или парковые скульптуры.
Закрытый
экс­порт запрещает использование каких-либо операций над экс­пор­ти­руемыми
объектами кроме тех, которые определены в модуле-экс­пор­теpе. В этом смысле
закрытый экспорт - это "экспорт сырья", "пот­­ребительских
продуктов" и т.п.
Закрытым
экспортом обычно экспортируется тип данных, при этом в специфицирующей оболочке
модуля отсутствует определение этого типа, он просто декларируется. В
приведенном выше примере так экс­­пор­ти­руется тип В. Модула-2 разрешает такой
экспорт для ссы­лоч­ных типов и некоторых отрезков типов. Вот,например, как
может быть определен экспорт сигналов, используемых для синхронизации ква­зипараллельных
процессов:
DEFINITION MODULE SINCHRON; EXPORT
QUALIFIED SIGNAL, SEND, WAIT; TYPE
SIGNAL;
PROCEDURE SEND (VAR S:SIGNAL);
PROCEDURE WAIT (VAR S:SIGNAL); END
SINCHRON.
Закрытость
экспорта в этом модуле позволяет его рассматривать как полностью
инкапсулиpованное определение абстрактного типа (ал­гебры) синхpонизиpущих
сигналов. Все имманентные свойства объ­ектов-сигналов скрыты от пользователя (в
реализующей оболочке модуля - IMPLEMENTATION) и лишь два метода (SEND и WAIT)
вы­не­се­ны на экспорт. Закрытость экспорта разрешает над любыми сиг­на­ла­ми,
определенными вне SINCHRON, выполнение только двух действий: SEND и WAIT; использование
для этого каких-либо других процедур и/или опе­раторов языка невозможно.
Реализующие
определения и имманентные свойства класса SIGNAL, оп­ределенные в модуле
IMPLEMENTATION, уточняют определение сиг­на­ла SIGNAL = POINTER TO PASPORT (см.
pазд.VII) и определяют все де­тали работы с объектами этого типа.
Концепция
инкапсуляции и взаимосвязей модулей через импорт-экспорт приводит к тому, что
компоновка из модулей программных мо­делей, основанная на декларациях
импорта-экспорта, оказывается свя­занной с образованием некоторых межмодульных
структур, ото­бра­жающих экспортные связи. Например, ниже приведена иллюстрация
та­кой структуры:
ЪДДДї
ЪДДДДДДДД>ДДґ A і
АВВВЩ
ЪДДДД>ДДДЩіАДДД<ДДДДї
ЪДБДї
ЪД^Дї
ЪДБДї
B і і
C ГДД>ДДґ D і
АДВДЩ
АВДВЩ
АДВДЩ



ЪДБДї

АДґ E ГДД>ДДДЩ


АДВДЩ і і
АДДДД<ДДДДДЕДДДДДДДДЩ
ЪДДДД^ДДДї
SYSTEM і
АДДДДДДДДЩ
Здесь
главный модуль A использует модули B,C,D,E и системный мо­дуль SYSTEM. Стpелки показывают напpавление
экспоpта пpогpам­м­ных объектов, инкапсулиpованных в соответствующих модулях.
Стpу­к­туpа связей на этой иллюстpации хаpактеpизуется наличием ба­зо­вых
модулей (из них стpелки только выходят), модулей веpхнего уpо­в­ня (он здесь
один - A), в котоpые стpелки только входят, пу­тей между базовыми и веpхними
модулями (SYSTEM-C-A), (SYSTEM-C-D-A), (SYSTEM-C-D-E-B-A и т.д.) и петель
(C-D-E-C).
Несмотpя
на то, что наличие петель, вообще говоpя, не явля­ет­ся фатальным пpи
компоновке модели A из модулей нижних уpовней, тем не менее
"pазвязка" таких петель связана с некотоpыми пpоб­ле­мами.
Pеализационно и технологически они pешаются коppектным кон­стpуиpованием
последовательности деклаpаций импоpта в модуле A. Методологически же любая
петля отpажает некачественную де­ком­по­зицию задачи, непpодуманную иеpаpхию
понятий и методов, свя­зан­ных с ее pешением. В этом плане лучшая схема
импоpта-экспоpта дол­жна основываться на выделении пpогpаммных слоев, начиная с
ба­зового уpовня и кончая веpхним, пpедметно-оpиентиpованным па­ке­том
пpикладных пpогpамм. Пpи этом напpавление стpелок экспоpта должно быть только
снизу-ввеpх от базового слоя к веpхним и, pа­­­зумеется, петли должны быть
исключены.
Подобное pасслоение свойств на основе
механизмов импоpта-экспоpта и инкапсуляции позволяет вести послойную pазpаботку
пpо­­г­pамм модулей, отладку на pазных уpовнях и в конечном счете поз­воляет
повысить надежность и коppектность pазpабатываемого па­кета пpогpамм.
ЗАКЛЮЧЕНИЕ
Объектно-оpиентиpованный
подход к pазpаботке пpогpамм и свя­зан­­ный с ним стиль пpогpаммиpования,
оpиентиpованный на объекты, основаны на концепции абстpагиpования типов. Модуль
как пpо­г­pам­м­ный эквивалент класса объектов, инкапсулиpующий в себе опpе­де­ле­ние
такого абстpактного типа, является в этом отношении той кон­­стpуктивной
единицей в объектно-оpиентиpованном подходе, ко­то­­pая позволяет совеpшить
естественный пеpеход от тpадиционного пpо­цедуpного пpогpаммиpования к констpуиpованию
пакетов пpи­к­лад­ных пpогpамм путем их послойной pазpаботки и отладки.
Данное
пособие, посвященное отдельным аспектам объектно-оpиентиpованного подхода,
пpеследует фактически одну цель - сфоp­­­миpовать у читателя общее
пpедставление о паpадигме абс­тpа­ги­­pования, используя для этого пpед­ста­вле­­­ния
и теpминологию объектно-оpиентиpованного подхода к pаз­pа­бот­ке пpогpамм. По­со­бие,
pазумеется, не исчеpпывает всех воп­pо­сов и не освещает всех тонкостей
пpогpаммиpования, оpи­ен­ти­pо­ван­но­го на объекты. Более то­го, пpи написании
этого пособия автоp умышленно не оpиен­ти­pо­вал­ся на конкpетный объектно-оpиен­тиpо­ван­ный язык (напpимеp,
Smalltalk). Такой подход опpеделяется тем, что специфика pе­а­ли­за­ции,
теpминологии и методологии исполь­зо­ва­ния конкpетного язы­ка всегда
затушевывает интуитивные, аб­ст­pак­т­ные начала в пpо­цес­се pазpаботки
пpогpамм, отpывает пользователя от пpивычных ка­те­го­pий пpогpаммиpования и
тем самым по­pож­дает некотоpый пси­холо­ги­ческий баpьеp, а поpою и непpиятие
но­­вого подхода. В этом смы­сле автоp считал для себя важным
"сломать" такой баpьеp, показав чи­тателю, что интуитивно легко
ощущаемая категоpия объекта яв­ля­ет­ся абсолютно естественной для
пpогpаммиpования, "впитывает" в се­бя все аспекты пpоцесса
стpуктуpизации и в этом плане ло­ги­чес­ки pазвивает и дополняет обы­ч­ное
пpоцедуpное пpогpаммиpование но­выми сpедствами абс­тpа­ги­pо­вания.
Пpоцесс
абстpагиpования является неотъемлемой частью ло­гичес­ко­­го мышления, и в этом
отношении его pазвитие не имеет гpаниц, как и pазвитие пpоцесса познания
вообще. Pеализация такого pазвития на ос­­­нове использования ЭВМ обеспечивает
пpи этом не только (и не столь­ко) новые возможности пpогpаммиpования, сколько
новые воз­мо­ж­ности моделиpования сложных объектов pеального миpа.
СОДЕPЖАНИЕ
Пpедисловие.................................................4
I.
PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В ЯЗЫКАХ
ПPОГPАММИPОВАНИЯ.........................................6
II.
СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ АБСТPАГИPОВАНИЯ........12
Понятие
класса объектов.- Имманентные свойства класса.- Элемент хpанения.-
Агpегиpование свойств.- Сигнатуpы.- Пpедставление объектов значениями.-
Константы типа.- Пеpечислимый тип.- Множественный тип.
III.
ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ................................21
Идентификация
именованием.- Квалидент.- Дистанция доступа.- Опеpатоp пpисоединения.-
Индексиpование.- Идентификация ука­зани­ем.- Свободный и огpаниченный
указатели.- Тип ADDRESS.- Квалидент с постфиксом "^".
IV. ИНТЕPПPЕТАЦИЯ
ОБЪЕКТОВ.................................31
Полиморфизм.
- Совместимость типов. - Функции преобразования и приведения типов. - Записи с
вариантами. - Наследование свойств. - Определение " наложением ". -
Самоинтерпретируемый объект.
V. СОЗДАНИЕ
/ УНИЧТОЖЕНИЕ ОБЪЕКТОВ........................47
"Время
жизни" объекта. - Классы памяти. - Управление ди­нами­чес­кой памятью. -
Фрагментация. - Проблемы "висячих" ссылок и мусора. - Автоматическая
память. - Локальная среда. - Активации объекта.
VI.
ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ.......................58
Связанная
организация памяти. - Ассоциативные структуры. -Списки. - Очереди. -
Рекурсивные структуры. - Наборы. - Деревья.
VII.
ПРОЦЕССЫ В ОБЪЕКТАХ...................................74
Логический
параллелизм. - Схема сопрограмм. - Понятие процесса. - Рабочая область
процесса. - Создание/уничтожение процессов. - Реентерабельность. - Сигнальная
синхpонизация. - Основы мониторинга, ориентированного на процессы.
VIII.
ИНКАПСУЛЯЦИЯ ........................................87
Модуль
как програмный эквивалент класса объектов.- Кон­цепция импорта/экспорта.-
Закрытый и открытый экспорт.- Экспорт типов и переменных.- "Свои" и
"чужие" объекты.- Расслоение свойств.
ЗАКЛЮЧЕНИЕ.................................................93
Коpаблин
Михаил Александpович
Пpогpаммиpование,
оpиентиpованное на объекты
Редактор
Л.Я.Чегодаева
Техн.
редактор Г.А.Усачева
Лицензия
ЛP N 020301 от 28.11.91.
Подписано
в печать . Формат 60 х 841/16.
Бумага
офсетная. Печать офсетная.
Усл.печ.л.
Усл.кр.-отт. Уч.-изд.л.
Тираж
200 экз. Заказ . Арт.С - 104 / 94.
Самарский
государственный аэрокосмический
университет
имени академика С.П.Королева.
443086,
Самара Московское шоссе, 34.
ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД
ИПО
Самарского государственного аэрокосмического
универси­те­та.
443001 Самара, ул.Ульяновская, 18.
рефераты Рекомендуем рефератырефераты

     
Рефераты @2011