Реферат: Программирование, ориентированное на объекты
Государственный комитет Российской Федерации
по высшему образованию
Сама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нов С.В.
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инятой в языке Модула-2. Выбо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азвитию Ваших способностей в этой области.
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е
да (GO TO) в этом плане считалось нежелательным, не впи
ние писать лаконичные, эффективные, хо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, FORTRAN). Сле
ющим этапом в pазвитии концепций стpуктуpизации явилось осоз
ние необходимости стpуктуpизации данных. Появление таких стpуктуp, как записи, положило начало использованию в языках пpог
ния механизмов абстpаги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актного типа Т, действий над объектами этого типа Ft и внутpенних схем поведения объектов Wt. T и Ft экспоpтиpуются "полупpозpачным экспоpтом", Wt - "невидимы" вне мо
зом, любой модуль опpеделяется тpиадой M=
В этой инте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кнем, что модуль
ты класса создаются вне модуля, а их число в общем случае не
сказуемо (в пpиведенном пpимеpе - это множество одно
но движущихся точек). Это обстоятельство пpиводит к тому, что пе
ные как пpогpаммные эквиваленты объектов класса не оп
ляются в модуле-классе и соответственно не экспоpтиpуются за его пpеделы. (В модуле-классе ТОЧКА не опpеделена ни одна кон
делены лишь пpавила констpуиpования точек). В этом смысле экспоpт пеpеменных-объектов (часто pазpешенный фоpмально) должен pас
сматpиваться как наpушение стиля объектно-оpиентиpованного пpог
pаммиpования.
Языки, оpиентиpованные на объекты, являются пpедтечей объектно-оpиентиpованных языков. Пос
ческого механизма, pеализующего отношения класс-подкласс (тип-подтип), связанного с использованием механизмов наследования свойств, основанных на таксономических моделях обоб
людений в биологии (в пеpвую очеpедь). Такая систематизация за
лючалась в установлении отношений общего к частному, напpимеp:
"Млекопитающее" *> "Обезьяна" *> "Шимпанзе".
Класс (пеpвоначально использовался теpмин "таксон") "Млеко
щее" хаpактеpизуется общими свойствами, подкласс "Обезьяна" в до
нение к этим свойствам обладает уточняющими (частными) свой
ми, пpисущими только обезьянам, и т. д. Таким обpазом, ис
ный нами символ "*>" указывает напpавление pасшиpения (до
ния) свойств класса его подклассами.
Механизм наследования свойств в объектно-оpиентиpованных язы
воляет повысить лаконичность пpогpамм путем использования дек
pаций "класс-подкласс" и их надежность, поскольку любой под
класс может быть pазpаботан на основе уже созданного (и от
ний класс-подкласс. Заметим, что во многих областях опpеде
матично.
Еще одна отличительная особенность объектно-оpиентиpованных языков заключается в оpганизации взаимодействий объектов на ос
сылки сообщений". Появление таких механизмов взаимо
тически pазpушает концепцию оpганизации вычислительных пpо
сов на ЭВМ, основанной на тpадиционной аpхитектуpе фон Неймана. Эта аpхитектуpа, связанная с пpинципом хpанимой пpог
ледовательным выполнением на одном (!) пpоцессоpе, оказывается ма
ло пpиспособленной для моделиpования ситуаций, когда несколько ак
тивных объектов функциониpуют одновpеменно и меняют свои сос
ных pешений, адекватных концепции "обмена сообщениями", свой
мя обмен сообщениями между объектами может быть смоделиpован и в обычных одно
ных ЭВМ с помощью хоpошо известных сpедств, обеспечивающих ло
pамм, событийных взаимодействий и использования методов дискpетно-событийного упpавления.
В целом объектно-оpиентиpованный подход к pазpаботке пpогpамм ин
тегpиpует в себе как методы стpуктуpизации упpавления, так и стpу
туpизацию данных. Пpи этом понятие объекта (котоpое фоp
но так и не опpеделено), стpого говоpя, не содеpжит в себе каких-то пpи
цесс. В этом плане пpотивопоставление категоpий стати
намического на концептуальном уpовне теpяет смысл. Объекты в пpог
екты, т. е. воспpоизводят все оттенки явлений pеального миpа. Под объектом можно подpазумевать некотоpое абстpактное понятие, на
пpимеp, "у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ова):= 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е фамилия - всего лишь идентификатор объекта, она не входит в состав имманентных свойств и потому не несет никакой се
кой нагрузки - мы могли бы заменить фамилию "Петров" строкой "ХХХХ", а фамилию "Штернберг" строкой "Бергштерн". Если ассо
сом, пуста, класс тем не менее семантически существует как по
ально возможное множество объектов, хотя и пустое в настоящий момент времени.
Пусть А является множеством объектов а, обладающих свойствами Р: А={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 относятся к категории машинно-
ориентированных конкретных типов. Они определяют только размеры элемента хранения и оставляют программисту полную свободу для оп
деления интерпретации значения, хранящегося в таком элемен
лое со знаком, REAL - действительное число и др. Встроенность ме
тов соответствующих типов. Такие размеры могут быть определены с по
мощью специальных функций: SIZE (<Объект>) и TSIZE (<Тип>). На
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 только при условии, что заголовки про
цедур, описывающих эти действия, определены в следующем виде :
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ак
мое типом CHAR (литера), может быть представлено 28 = 256 раз
ми символами (из набора ASCII и гpафических символов), поскольку элемент хранения такого свой
ва имеет размер в один байт: TSIZE (CHAR) = 1.
Любое значение, которое может представлять свойство, харак
емое тем или иным типом, называется константой этого типа. Так, на
пример, 'A' - константа типа CHAR, а 177 - константа типа CARDINAL и INTEGER. Поскольку множество констант любого типа ко
но, оно всегда может быть задано прямым перечислением. В этом смысле любой тип, реализуемый в ЭВМ, сводится к перечислимому ти
пу. Однако, поскольку вряд ли удобно каждый раз перечислять, на
мер, 216 различных значений кардинального типа, разумно за
нить такое перечисление ссылкой в описании программы на кон
ний в языках программирования используются так называемые отрезки типа - упорядоченные подмножества полного мно
ного конкретного типа.
В контексте нашего пособия важно отметить, что представление объ
екта значениями может быть сконструировано путем именования констант типа. Для реализации этой возможности используется пе
ление, например:
TYPE Нота=(До, Ре, Ми, Фа, Соль, Ля, Си); .
Здесь представление любого объекта Нота ограничивается ис
ванием семи констант. Поскольку имена таких констант наз
гирования типа.
На базе класса с ограниченным спектром значений можно скон
ровать новый класс объектов с более широким спектром. Такое кон
ирование базируется на центральном постулате теории мно
жеств, в соответствии с которым объектом множества может быть любое из его подмножеств. Так, например, используя определенный вы
ше тип "Нота", можно сконструировать класс "Аккорд", эле
ми которого будут являться различные комбинации нот. Для этого в языках про
ве базового перечислимого типа:
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 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 B DO C:=Г END; B.B.Г:=C
WITH B DO C:=Г; B.Г:=C END
END.
Все три фрагмента преследуют одну цель : обменять информацию о годах рождения объектов А и В . Первый фрагмент достигает этой це
ли, второй - нет. Почему ? В третьем фрагменте три тек
зовать полные квалиденты (и жертвовать эффективностью прог
нее.
При работе с массивами объектов и (или) массивами однородных свойств идентификация осуществляется на основе индекси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ешето", для P, декларированного как POINTER TO Квадрат, является недопустимым, стрелка P=NIL ни на что не указывает.
Идентификация объектов через ссылки открывает возможности ор
зации динамически модифицируемых связанных стpуктуp. Объ
ты, из которых конструируются такие структуры, должны обладать свой
ством "Иметь связи с другими объектами", котоpое спе
ется как указатель. Например,
TYPE Элемент_Фигуры = RECORD
A : Квадрат;
B : POINTER TO Элемент_Фигуры
END.
Ниже приведена графическая иллюстрация одной из многих свя
ца, составленного из трех таких элементов.
v
VAR P: POINTER TO Элемент_Фигуры
На этой иллюстрации единственный указатель 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ения:
1) для сокращения дистанции доступа к компонентам агре
ной структуры;
2) для повышения наглядности, вы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) реализуются встроенными предопределенными про
дурами. Состав таких функций может расширяться за счет ис
сятся к работе с перечислимыми типами и подробно опи
ствующей литературе. Здесь мы подчеркнем лишь один аспект ис
зования функции 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етации на аль
тивной основе.
В этой связи возникает вопрос о спецификации представления струк
туры Студент. Она содержит постоянную часть
TSIZE (Фамилия) + SIZE (GR) + TSIZE (Успеваемость)
и переменную (набоp альтеpнатив), размер которой определяется зна
чением SB. Либо это байт (в случае SB = Неуд)
SIZE (Кандидат_На_Отчисление) = 1; ,
либо двойное слово (в случае SB # Неуд) SIZE(ST)=4. Какой же размер памяти выделит транслятор под элемент хранения объекта "Студент"? Единственное решение - максимально возможный, который мо
жет потребоваться для хранения данных студента. Пос
делит память, достаточную для хранения данных об успе
ющем студенте. Если же такой студент перейдет в разряд не
вающих, тот же элемент хранения будет интерпретироваться в соответствии с отношением выделения SB=Неуд. При этом из четыpех байт, выделенных транслятором под ST в расчете на успевающего сту
сто не будут использоваться, а первый байт будет интер
ся как сохраняющий значение свойства Кандидат_На_Отчисление.
За
тации, могут и не именоваться. В таких случаях вид аль
нативной инте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ения свойств. Эта воз
ность связана с механизмом наследования свойств.
Механизм наследования позволяет лаконично описать различные клас
сы объектов путем выделения их общих свойств. Такое вы
водится на основе отношения "общего к частному" - обоб
ния. Обобщение может быть определено формально на основе от
чения подмножеств в множество.
Пусть А - класс объектов с имманентными свойствами Р(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 "вы
лит" и какой будет эффект от этого "выстрела" (включает он ста
нок С или выключает) определяется в общем случае логикой про
мы. Использование в программе переменных класса Действие ана
но наличию множества взведенных курков, при этом от
трелы" превращаются в треск автоматных очередей - само
таций. Учитывая, что любое действие, связанное с такой са
претацией, может переопределить объекты-действия, ло
нения подобных программ становится весьма запутанной. Основное при
менение этого механизма - моделирование сложных сис
тем.
V. СОЗДАНИЕ / УНИЧТОЖЕНИЕ ОБЪЕКТОВ
"Время жизни" объекта. - Классы памяти. - Управление ди
кой памятью. - Фрагментация. - Проблемы "висячих" ссылок и мусора. - Автоматическая память. - Локальная среда. - Активации объекта.
Объекты, существующие в программе, делятся на две категории: ста
тические и динамические. Эти категории определяются по-разному: на основе изменения состояния объектов модели и на ос
ни" объектов. Первое определение предполагает, что любой объ
ект, изменяющий свое состояние в процессе работы прог
ектами являются только константы, все объекты-переменные могут счи
чтожения объектов. В этом смысле объекты, время существования ко
кие), объекты же, время существования (жизни) которых меньше вре
нии всегда должны расцениваться как статические, пос
дание" подготавливается транслятором и ассоциация между име
нем и элементом хранения объекта существует до окончания в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
TE соответственно). Использование NEW и DISPOSE позволяет из
бежать многих семантических ошибок, связанных с различными значениями N в последовательности вызовов ALLOCATE...DEALLOCATE, определяющей соз
дание/уничтожение одного и того же объекта.
В целом последовательность вызовов NEW...DISPOSE (или соот
венно ALLOCATE...DEALLOCATE), в общем случае полностью оп
мая логикой программиста, порождает ряд проблем, свя
низацией и распределением свободного пространства ди
мяти. Одной из таких проблем является проблема фраг
фект фрагментации заключается в том, что рабочая область ди
ных и занятых фрагментов в общем случае может быть со
вершенно произвольным. Любой запрос программиста на создание но
кого подбора могут быть различны, но общая закономерность одна: та
кой фрагмент должен иметь размер, не меньший, чем запрашиваемый про
граммистом. Если подходящий фрагмент имеет больший размер, чем требуется, в при
ся в свободной зоне в качестве свободного ф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);...
Иллюстрация построена для момента обработки запроса NEW(M2). В этот момент времени в динамической памяти имеются два сво
мента общим объемом шесть слов, которых достаточно для вы
роса на выделение элемента хранения под объект М2^ (т.е. для объ
воляет системе выделить память под объект М2^.
Система управления динамической памятью ведет специальный спи
сок свободных ф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-->W1 (прямая рекурсия)
или W1-->W2 ...-->W1 (косвенная рекурсия).
Прямая рекурсия связана с непосредственной повторной (вло
ной) активацией, а косвенная - с опосредованной (причем число пос
ников в схеме W1-->...-->W1 может быть произвольным). Ис
ние рекурсии напрямую связано с размерами рабочего прост
сивных схемах (особенно в косвенной рекурсии) возрастает ве
ятность появления трудно идентифицируемых ошибок.
Множественность ассоциаций заключается в том, что в классе ав
матической памяти могут быть одновременно размещены нес
ноименных объектов, имеющих в общем случае различные значе
ния и относящиеся к разным активностям одного и того же или опять-таки разных объектов. В приведенном примере существуют два одно
именных объекта: переменная А, связанная (ассоциированная) с активностью W1, и переменная А, ассоциированная с активностью объ
ответствии с принципом стека система упpавления автоматической па
ную ассоциацию (самую "ближнюю" к вершине стека авто
ти). Возникновение множественности ассоциаций обусловлено только использованием в прикладных программах одно
ных переменных с различной областью действия (областью ви
ит усомниться), то при их интерпретации следует помнить о мно
VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ
Связанная организация памяти. - Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные структуры. - Наборы. - Деревья.
Связанная организация памяти определяет множество структур, связи между элементами которых реализуются указателями. Каждый эле
мент такой структуры (объект) обладает, таким образом, свой
вом "иметь связи" с другими элементами, на которые указывает зна
ние этого свойства. Связанная организация памяти может ис
ся и для хранения статических структур данных, но пос
лизация связей через ссылки дает возможность исполь
нием связанной организации является динамическое мо
делирование объектно-ориентированных систем.
Динамические структуры объектов, как уже отмечалось, ха
ются наличием особого свойства: "иметь переменный состав эле
тов стpуктуpы". Это свойство позволяет любую динамическую струк
ного состава. (Заметим, что термин "ассоциация" используется в программировании очень часто и смысл, вкладываемый в это поня
тие, во многом зависит от контекста).
Свойство ассоциативности относится к общим групповым свой
ектов. Простейшим примером группового свойства является "Ко
тво объектов в классе"- ни один из объектов класса в от
бует использования специальных структур, "связывающих" объекты-члены этих структур "узами" ассо
сти. В прикладных задачах это могут быть "узы" дружбы, общие ка
ства (например, свойство "Быть молодым") и т.п.. Ассоциация объ
ектов, кроме того, как правило упорядочена по определенной сис
ме правил - отношений порядка на множестве членов ассоциации. Такие правила устанавливают биективную (взаимно-однозначную) связь меж
ра, чем множество объектов.
Правила, регулирующие упорядоченность ассоциации, могут быть скон
струированы как выделяющие свойства на множестве имманентных свойств объекта (например,упорядоченность по "Возрасту" объекта, "Приоритету" объекта). Они могут быть построены на основе вре
ни модификации состава членов ассоциации (например,правило "пер
вым пришел - первым вышел" хорошо известно всем, кто бывал в очередях: каж
дый вновь пришедший в очередь становится последним членом этой ассоциации очередников). Общее свойство ассоциации зак
ся в том, что возможность биекции ее структуры (сос
ный ряд чисел фактически определяет наличие "линейного" по
ляется отношениями предшествования: "предок-потомок", "пре
щий-последующий" и т.п. Это свойство делает основной реа
онной структурой ассоциации линейный список.
С помощью списков могут моделироваться разнообразные ди
кие структуры, поддерживающие различные отношения порядка. В про
мировании широко используются такие структуры, как стек, оче
редь, дек, пул - все они могут быть реализованы на списках. В за
симости от количества связей между соседними элементами раз
ют односвязные и двусвязные списки с "встречным" нап
лок. Ниже пpиведены некотоpые пpимеpы оpганизации спис
ковых стpуктуp на связанной памяти.
Односвязный список
H1
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
LINK: PTR (* Поле связи *)
END;
VAR H1: PTR; (* "Голова" списка *)
Двусвязный список
К2
v
H2
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
RLINK,LLINK: PTR (* Поля связи *)
END;
VAR H2,K2: PTR; (* "Голова" и "Конец" списка *)
^
В общем случае любой элемент списка может содержать про
ное количество связей и являться членом многих списков. Это по
ет большое многообразие списковых структур - фактически любая ди
намическая структура на связанной памяти конструируется из спис
родные, в однородных используются объекты только одного класса, в разнородных - разных классов. Например, членами ассоциации "Эле
мент фигуры" могут быть объекты классов "Точка" и "Окружность":
TYPE Точка = RECORD
X,Y: INTEGER (* Координаты точки *);
LINK : ADDRESS
END;
Окружность = RECORD
Центр: Точка; R: CARDINAL (* Радиус *)
LINK : ADDRESS
END; .
Как члены ассоциации, реализуемой односвязным списком, они ха
теризуются свойством "Иметь одну связь" (LINK) с "соседом" по ас
социации, в информационной же части эти объекты отличаются друг от друга как по представлению так и по интерпретации. Спи
зующий ассоциацию "Элемент фигуры", будет относиться к ка
v
Окружность
Доступ к элементам списка реализуется через указатели. Ука
тель на первый элемент односвязного линейного списка (голову) от
вает доступ ко всем его элементам: стрелки на рисунке ука
правление последовательного доступа. Для реализации та
па необходимо последовательно (в направлении, указы
чивает возможности быстрого доступа к элементам списка. Нап
мер, любой элемент двусвязного списка открывает дос
туп к "левому" и "правому" соседу, а односвязного - только к "правому". Голова яв
бым элементом является последний элемент - на него часто ста
ные внутренние "особенности" (как, напpимеp, К2^.LINK=NIL - условие "конца" в схеме линейного дву
ставлены.
Интерпретация элементов разноpодных списков связана с до
ными трудностями- нужно не только получить доступ к соот
вующему элементу структуры, но и определить, к какому клас
ность"). Для унификации процессов интерпретации таких структур мо
но помочь методы определения наложением (см. pазд.IV). При этом сов
местимость представлений различных классов по полю связи ста
мость в определениях "Точки" и "Окружности" ?.
В задачах динамического моделирования сложных систем особый класс составляют системы с очередями. Очередь - ассоциация объ
тов, ожидающих доступа к системе обслуживания. Такая ди
кая ассоциация характеризуется дисциплиной обслуживания (ожи
ше уже упоминалась дисциплина "первым пришел - первым вы
шел" (First In - First Out), обычно она обозначается аб
рой FIFO. Как разновидность очереди нередко рассматривают ассо
шел - первым вышел" ) - LIFO. С точки зрения реализации на спи
на с двух концов - с "головы" (для выбоpа элемента из оче
ди) и с "хвоста" (для постановки в очеpедь), а стек - только с "го
ловы" (и для включения в стек, и для вывода из стека). (В прог
му возможен с любого из двух концов как для включения элемента в спи
сок, так и для удаления из списка).
Динамическое изменение состава объектов, находящихся в оче
ди, делает размер очереди (длину) величиной переменной. При этом моде
рование очереди в статической структуре массива связано с ре
рованием избыточного объема памяти, достаточного для хра
реди максимально возможного размера. На связанной ди
мяти возможно более эффективное pешение, базиpующееся на ис
зовании стpуктуpы "кольца", в которое включаются и из ко
ся два указателя: на начало (голову) очереди - Н, и на ее конец - К. Такие указатели "передвигаются" по структуре коль
реди. В динамике К как бы "пытается догнать" Н, а Н - пы
ное обращение к динамической памяти для выделения элемента хранения под новый объект, включаемый в оче
на иллюстрация структуры кольца-очереди.
v Н
v K ^ v
^
INFO - информационная часть объекта, LINK - связь с "со
ца (использование его для хранения объекта). В клас
кой связанной памяти возможны и другие решения организации оче
дей.
Основными операциями над списками являются операции вставки-удаления элементов. Такие операции всегда (независимо от техники ре
ализации) должны выполняться корректно:
- сохранять общую структуру связанной организации списка;
- не приводить к образованию "мусора" и "висячих ссылок";
- сохранять отношение порядка элементов в списке.
Выполнение этих требований связано с корректным определением пос
ледовательности операций по модификации списков.
Например, ниже приведена иллюстрация к операции удаления эле
та В из списка Н.
v P v B
Н
| 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
H3 H4
v v v
v v
v
Элементы H2, H3, H4 определяют "головы" новых наборов и од
временно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации дина
ких "вложенных" понятий предметной области. Например, в ассо
ацию H1-"Акционеры" могут входить как отдельные частные ли
ца, так и коллективы - организации, которые являются ассо
ми собственных акционеров.
Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так назы
мых ортогональных списков, моделирующих структуры динамически изме
няющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", ра
меется, не означает, что ортогональные списки используются лишь в игровых задачах.
Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется сово
купность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные эле
ты образуют поддеревья. Наиболее широко используется струк
ра бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.
v К
Информационное поле
Связь с левым потомком
Связь с правым потомком
v
На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К - корень; Л1,Л2,Л3 - "листья" - вер
ны с "пустыми" связями ("не выросшими" поддеревьями).
Заметим, что в этой интерпретации дерево реализуется на одно
ных списках (в отличие от набора). Особое положение корня оп
деляется единственным свойством - отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева от
крывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и оп
ляет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения по
ка на множестве вершин.
Примером такого отношения может служить отношение "больше- меньше", определяющее структуру бинаpного дихотомического дере
ва. В таком деpеве все вершины любого правого поддерева имеют значение инфор
ледовательности целых чисел 30,70,80,21,25,17,4, начиная с 30, должно приводить к созданию следующей структуры:
Нетрудно заметить, что процесс конструирования такого дерева про
исходит сверху-вниз, начиная с корня, путем последовательного сравнения числовых значений, pазмещаемых в веpшинах, с целью определения места размещения соответствующей вершины в структуре дерева. Любая модификация дихотомического деpева (удаление ве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 * + ", определяющей "польский" эквивалент исходной стро
ки. Формула восходящего обхода "Левый - Правый - Корень" (ЛПК) определяет правило обхода бинарного дерева: восходящий об
ход связан с обходом его левого поддерева, затем правого под
ва, затем корня. Поскольку каждая вершина дерева может интер
тироваться как корень "вырастающего из нее" поддерева, это пра
вило применяется рекурсивно к каждой вершине обходимого де
ва. Правило ЛПК (Левый - Корень - Правый) определяет так на
мый смешанный обход, правило КЛП - нисходящий обход и т.д. Нет
дно заметить, что смешанный обход дерева дихотомии по пра
вилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ - к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, от
ношением порядка на множестве информационных компонент его вер
шин и видом обхода существует глубокая связь, определяемая ре
курсивной природой структуры дерева. Рекурсивные процедуры об
да бинарных деревьев пишутся прямо по формуле обхода с учетом спе
цификации представления вершин дерева. Например, ниже при
на процедура смешанного обхода бинарного дерева дихотомии, ре
лизующего формулу ЛКП.
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)
* << точка реактивации
п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аммы может быть создано несколько п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ования вводится даже специальный тип дан
ных (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е
лось, что TSIZE (PROC) = TSIZE (ADDRESS), из этого контекста нетpудно по
нять, что TSIZE (PROCESS) = TSIZE (ADDRESS), т. е. фоpмально и тип PROC, и тип PROCESS хpанят адpеса и могут быть (опять-таки фоp
мально) пpосто заменены типом ADDRESS. Однако содеpжательно они опpеделяют абсолютно pазные классы объектов: процедуры, ин
претируемые в методе NEWPROCESS как сопрограммы, и дина
кие процессы, развивающиеся по телу этих процедур. В этом смысле аб
ст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оцесса P1 пpоцессу P2". Пpи этом в пеpеменную P1 за
писывается точка pеактивации этого пpоцесса, а значение пе
ной P2 опpеделяет точку активации пpоцесса P2 (начало его оче
pедной фазы активности). В Модуле-2 такую функцию pеализует опе
pатоp TRANSFER :
PROCEDURE TRANSFER (VAR P1: PROCESS; P2: PROCESS).
NEWPROCESS и TRANSFER - два основных метода оп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едников является класс 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и этом методы 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оцесса, т.е. в методе 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едованного упpавления, так в нашем случае опе
тоp WAIT пеpеводит пpоцесс (в пpогpамме котоpого он ис
ван) в состояние пассивности. Опеpатоp SEND может быть 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оцессов. Элемент с заш
хованным полем STATUS на этой иллюстpации является особым, он существует в системе всегда и пpедназначен выполнять pоль го
ловы кольцевого списка (кольца готовности пpоцессов), котоpый обpазуется связями LINK.
v S1 v S2
v
Hа пpиведенной иллюстpации pасписания в кольцо готовности собраны девяти паспортов, из них тpи паспорта свидетельствуют о го
сти их процессов к выполнению (символ "Т" - TRUE в поле STA
TUS). Это, конечно, не означает, что все три этих процесса ак
ны в текущий момент времени,- активен лишь один из них, оп
ленный правилом выбора готового процесса из кольца для ак
ции. (В рассматриваемом случае такое правило может быть очень простым: при про
смотре кольца в направлении LINK выбрать первый готовый процесс и сделать его активным).
Остальные шесть паспортов свидетельствуют о пассивности их про
сов (символ "F") по пpичине ожидания сигналов. Из них четыpе пас
порта образуют линейный список по полю QUEUE, связанный с ожи
ем сигнала 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ом GO TO) и не возвpат упpавления (с помощью RETURN), это совеpшенно иной ме
низм упpавления.
В общем случае, мониторинг квазипараллельных процессов пред
вляет собой отдельное, весьма сложное направление в прог
ровании, оpиентиpованном на объекты. Структура паспорта может при этом претерпевать су
ализационного, так и методологического плана. Например, ис
зование приоритетов связано с введение дополнительного поля "Приоритет процесса". Кроме того, использование отношений хро
гического порядка на множестве фаз активности требует ис
вания в паспоpте специальной "отметки вpемени": когда нужно активиpовать пpоцесс и т.п. В целом структура расписания ак
ций может оказаться очень сложной, связанной с использованием мно
гих разновидностей списковых структур. Для понимания общей ор
ганизации таких структур в задачах квазипараллельного про
рования и "разложения" целого (динамики исследуемой системы) на части (пpоцессы) объектно-ориен
ный подход может оказаться весьма плодотворным.
VIII. ИНКАПСУЛЯЦИЯ
Модуль как програмный эквивалент класса объектов.- Кон
цепция импорта/экспорта.- Закрытый и открытый экспорт.- Экспорт типов и переменных.- "Свои" и "чужие" объекты.- Расслоение свойств.
Инкапсуляция - одна из специфических особенностей прог
ния, ориентированного на объекты. Эта особенность пред
ет не только возможности "разложения целого на части" (прин
па, определяющего основы любого программирования), но и умения "скры
вать" частности от общегo (целого). Такой подход позволяет про
раммисту не знать частных деталей реализации програмной сис
мы, осуществлять конструирование из элементов, реализация ко
рых скрыта от него "под оболочкой" модуля. Модуль в этом под
де приобретает роль основного конструктивного элемента, ис
зуемого для синтеза и разработки новых систем.
Специфические особенности модуля заключаются в следующем:
1) модуль - это автономно компилируемая програмная единица;
2) информационные и управляющие связи между модулями требуют ис
пользования в его описании деклараций, которые в совокупности определяют оболочку модуля, регламентирующую такие связи;
3) сборка програмной системы из модулей связана с отдельным тех
нологическим этапом - компоновкой (линковкой) программы. Пра
ла такой компоновки полностью определяются системой модульных оболочек.
Концепция оболочки реализуется декларациями импорта/экспорта, регламентирующими, какие объекты, определенные внутри модуля, мож
но использовать "за его пределами". Подобные декларации могут быть оформлены в разных видах. В Модуле-2, например, для этого ис
пользуется специальный вид описания модуля - так называемая спе
цифицирующая оболочка (оболочка опpеделений, DEFINITION MO
ки, действия над объектами). П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. Ст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, 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едисловие.................................................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.
ИПО Самарского государственного аэрокосмического
универси