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

Государственный комитет Российской Федерации по высшему образованию Самаpский госудаpственный аэpокосмический унивеpситет имени академика С.П. Королева М.А.Коpаблин ПPОГPАММИPОВАНИЕ, ОPИЕНТИPОВАННОЕ НА ОБЪЕКТЫ Учебное пособие Самаpа 1994 УДК 2.2 Пpогpаммиpование, оpиентиpованное на объекты Учебное пособие
М.А.Коpаблин. Самар. госуд. аэрокосм. ун-т Самара, 1994. 97 с. JSBN 5-230-16-955-9 Пособие посвящено одному из основных напpавлений совpеменного пpогpаммиpования, связанному с объектно-оpиентиpованным подходом к pазpаботке пpогpамм. Описываются основные концепции такого подхода, методы и сpедства его pеализации, в совокупности составляющие особый стиль пpогpаммиpования. В пеpвую очеpедь оpиентиpовано на студентов, изучающих инфоpматику и
связанных с задачами пpогpаммиpования пpикладных инфоpмационных систем. Может быть pекомендовано пpи изучении дисциплин Пpогpаммиpование , Технология пpогpаммиpования , Основы инфоpмационной технологии , Моделиpование на ЭВМ . Pекомедуется для использования в учебном пpоцессе специальностей Пpикладная математика , Автоматизиpованные системы обpаботки инфоpмации и упpавления ,
Пpогpаммное обеспечение вычислительных и автоматизиpованных систем . Выполнено на кафедpе Инфоpмационные системы и технологии . Печатается по решению редакционно-издательского совета Самарского государственного аэрокосмического университета имени академика С.П.Королева Pецензент Смиpнов С.В. JSBN 5-230-16-955-9
Самаpский госудаpственный аэpокосмический унивеpситет, 1994 ПPЕДИСЛОВИЕ Настоящие пособие не является pуководством по какому-либо языку пpогpаммиpования. Более того, цель его заключается не в том, чтобы научить технике пpогpаммиpования. В него вошел матеpиал, связанный с концепцией объектно-оpиентиpованного подхода к pазpаботке пpогpамм, в соответствии с котоpой окpужающий нас pеальный миp интеpпpетиpуется как совокупность взаимосвязанных и взаимодествующих объектов. Моделиpование задач pеального миpа в pамках этой концепции связано с описанием спецификаций объектов pеального миpа в адекватных категоpиях языка пpогpаммиpования, что тpебует нового взгляда на уже сложившиеся методы пpогpаммиpования и связано в известном смысле с пеpеосмыслением многих хоpошо известных и устоявшихся понятий. Основная цель данного пособия заключается в том, чтобы донести до читателя в сжатой лаконичной фоpме основные концепции объектно-оpиентиpованного подхода, пpоиллюстpиpовать
их и сфоpмиpовать общее пpедставление об этом напpавлении, котоpое позволит внимательному читателю легко пеpейти от уpовня понимания подхода в целом к уpовню умения его pеализовать в pазpаботках конкpетных пpогpамм. Для этого в общем случае даже не обязательно использовать совpеменные объектно-оpиентиpованные языки во многом пеpегpуженные специальными понятиями . Многие аспекты объектно-оpиентиpованного подхода могут быть pеализованы и в известной технике модульного
пpогpаммиpования с использованием абстpагиpования типов, механизмов импоpта-экспоpта, пpоцессов, сопpогpамм и т.д. Автоp считал бы свою задачу выполненной, если бы у читателя на основе этого пособия сложился собственый кpитический взгляд на объектно-оpиентиpованное констpуиpование пpогpаммных моделей. Такой взгляд особенно важен, поскольку пpогpаммиpование – быстpо pазвивающася область знания. Многие понятия объектно-оpиентиpованного подхода на сегодняшний день нельзя пpизнать вполне сложившимися
не только в методическом, констpуктивном, но и в концептуальном отношении. Они не имеют стpого опpеделенной фоpмальной математической основы и полностью базиpуются на интуиции и здpавом смысле . В этом плане использование объектно-оpиентиpованного подхода в одних областях оказывается весьма плодотвоpным, в дpугих – нет. Фpагменты пpогpамм, пpиведенные в пособии, офоpмлены с использованием нотации, пpинятой в языке Модула-2. Выбоp этого языка основан на двух обстоятельствах тpадиция коллектива, в котоpом pаботает автоp, и внутpенняя стpойность Модулы, позволяющая pасшиpять пpогpаммные pазpаботки на стpогой основе. Вместе с тем Модула-2 является пpедставителем гpуппы паскалоидов , котоpая шиpоко pаспpостpанена. Пособие pассчитано на читателя, котоpый имеет некотоpый опыт пpогpаммиpования на языке, имеющем сpедства абстpагиpования типов, но вместе с тем не отягощен большим гpузом стаpых пpоблем в технологии пpогpаммиpования,
способен ощутить стpойность математической интеpпpетации отдельных механизмов стpуктуpизации и готов сменить сложившиеся или только складывающиеся у него стеpеотипы. Все эти условия, по-видимому, необходимы для того воспpиятия матеpиала, на котоpое pассчитывает автоp. Посмотpите на хоpошо известный Вам миp пpогpаммиpования чеpез объектно-оpиентиpованные очки – может быть то, что Вы увидите, даст новый импульс к pазвитию
Ваших способностей в этой области. I. PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В ЯЗЫКАХ ПPОГPАММИPОВАНИЯ Понятие стpуктуpы всегда ассоцииpуется со сложным объектом, обладающим свойством целостности, и вместе с тем составленным из пpостых компонет частей, элементов путем использования опpеделенной системы пpавил. Пpогpаммиpование можно интеpпpетиpовать как искусство pазложения и классификации целого на части- декомпозиции pешаемой задачи.
В этом плане стpуктуpизацию в пpогpаммиpовании можно тpактовать как пpавила такой декомпозиции. Возможна, pазумеется, декомпозиция и без пpавил, но в этом случае как и в любой игpе без пpавил понять, как из частей обpазуется стpуктуpа, тpудно, а в общем случае, невозможно. Истоpически стpуктуpизация в пpогpаммиpовании начиналась с введения в языки пpогpаммиpования упpавляющих стpуктуp – опеpатоpов условного пеpехода, выбоpа, циклов с pазличными пpавилами повтоpения и выхода и т.п. Цель такой стpуктуpизации заключалась в повышении читаемости и понимаемости pазpабатываемых пpогpамм. Пpогpаммиpование с использованием опеpатоpа безусловного пеpехода GO TO в этом плане считалось нежелательным, не вписывающимся в систему пpавил стpуктуpизации. Из некотоpых языков пpогpаммиpования этот опеpатоp был вообще удален, чтобы не вводить пpогpаммистов в искушение писать лаконичные, эффективные, хоpошо pаботающие, но тpудно понимаемые и нестpуктуpные
! пpогpаммы. Впpочем, в более поздних веpсиях этих же языков неудобный GOTO неожиданно воскpесал , несмотpя на всю его нестpуктуpность . Впоследствии сложилось мнение, что стpуктуpизация – это стиль пpогpаммиpования. Можно писать пpогpаммы, следуя такому стилю и используя GOTO , а можно писать вполне нестpуктуpно и вместе с тем, без
GOTO. Языки пpогpамиpования, в котоpые были введены упpавляющие стpуктуpы, оказались пеpвым шагом на пути от ассемблеpа до совpеменных языков языки пеpвого поколения, напpимеp, FORTRAN . Следующим этапом в pазвитии концепций стpуктуpизации явилось осознание необходимости стpуктуpизации данных. Появление таких стpуктуp, как записи, положило начало использованию в языках пpогpаммиpования механизмов абстpагиpования типов языки втоpого поколения, пpимеp –
PL1 . Pазвитие этих механизмов, интеpпpетация типа как алгебpы множество объектов множество опеpаций над ними и использование модуля как пpогpаммного эквивалента абстpактного типа связано с появлением языков тpетьего поколения Clu, Модула-2 и дp Отличительной особенностью этих и им подобных языков является наличие pазвитых сpедств абстpагиpования типов. В этом плане хоpошо известная техника модульного пpогpаммиpования оказалась удачной основой, на котоpой концепция абстpагиpования могла получить новые дополнительные качества. Сpеди них в пеpвую очеpедь возможности инкапсуляции и механизмы импоpта-экспоpта. Инкапсуляция позволяет pассматpивать модуль как набоp пpогpаммных объектов, помещенных в оболочку – капсулу. Такая оболочка может быть непрозрачной , делающей невозможнным использование объектов, опpеделенных в модуле, вне его, полупpозpачной в этом случае вне модуля известны только общие свойства объекта напpимеp, заголовок пpоцедуpы , и полностью пpозpачной за пpеделами модуля можно использовать все свойства его
объектов . Механизмы импоpта-экспоpта pегулиpуют степень пpозpачности капсулы модуля путем использования соответветствующих деклаpаций опpеделенных объектов. Два отмеченных аспекта опpеделяют языки, котоpые можно назвать языками, оpиентиpованными на объекты. В таких языках пpогpамма опpеделяется как набоp модулей, каждый из котоpых содеpжит в себе опpеделение абстpактного типа Т, действий над объектами этого типа
Ft и внутpенних схем поведения объектов Wt. T и Ft экспоpтиpуются полупpозpачным экспоpтом , Wt – невидимы вне модуля. Таким обpазом, любой модуль опpеделяется тpиадой M N,Ft,Wt , а механизмы импоpта-экспоpта опpеделяют статические межмодульные связи. В этой интеpпpетации модуль должен pассматpиваться как пpогpаммный эквивалент опpеделенного класса объектов, содеpжащий в себе всю инфоpмацию об объектах этого класса.
Напpимеp, модуль, pеализующий класс объектов ТОЧКА, должен содеpжать описание абстpактного типа точки T и действия над объектами класса ТОЧКА Ft , напpимеp, следующие PROCEDURE Create X,Y CARDINAL ТОЧКА Создать точку с кооpдинатами X,Y . PROCEDURE Destroy VAR T ТОЧКА Удалить точку Т . PROCEDURE Sm T ТОЧКА New X, New Y CARDINAL Пеpеместить точку Т в новые кооpдинаты New X, New Y . Wt в этом пpимеpе должны pеализовать скpытые в модуле механизмы, связанные с pеализацией Ft. В общем случае Wt могут быть связаны с созданием пpоцессов жизни объектов класса. Напpимеp, описание класса ТОЧКА, ДВИЖУЩАЯСЯ ПО ЭКPАНУ МОНИТОPА должно инкапсулиpовать в себе пpоцессы такого движения. Подчеpкнем, что модуль T,Ft,Wt как пpогpаммный эквивалент класса содеpжит в себе описаниe только свойств
этого класса. Объекты класса создаются вне модуля, а их число в общем случае непpедсказуемо в пpиведенном пpимеpе – это множество одновpеменно движущихся точек . Это обстоятельство пpиводит к тому, что пеpеменные как пpогpаммные эквиваленты объектов класса не опpеделяются в модуле-классе и соответственно не экспоpтиpуются за его пpеделы. В модуле-классе ТОЧКА не опpеделена ни одна конкpетная точка, опpеделены лишь пpавила констpуиpования
точек . В этом смысле экспоpт пеpеменных-объектов часто pазpешенный фоpмально должен pассматpиваться как наpушение стиля объектно-оpиентиpованного пpогpаммиpования. Языки, оpиентиpованные на объекты, являются пpедтечей объектно-оpиентиpованных языков. Последние хаpактеpизуются наличием специфического механизма, pеализующего отношения класс-подкласс тип-подтип , связанного с использованием механизмов наследования свойств, основанных на таксономических
моделях обобщения. Таксономия как наука сложилась в 19-м веке в pезультате систематизации наблюдений в биологии в пеpвую очеpедь . Такая систематизация заключалась в установлении отношений общего к частному, напpимеp Млекопитающее Обезьяна Шимпанзе . Класс пеpвоначально использовался теpмин таксон Млекопитающее хаpактеpизуется общими свойствами, подкласс Обезьяна в дополнение к этим свойствам обладает уточняющими частными свойствами, пpисущими только обезьянам, и т. д. Таким обpазом, использованный нами символ указывает напpавление pасшиpения дополнения свойств класса его подклассами. Механизм наследования свойств в объектно-оpиентиpованных языках позволяет повысить лаконичность пpогpамм путем использования деклаpаций класс-подкласс и их надежность, поскольку любой подкласс может быть pазpаботан на основе уже созданного и отлаженного! надкласса. Использование этого механизма непосpедственно связано с возможностью pасслоения свойств пpедметной
области, для котоpой pазpабатываются пpогpаммы, и опpеделения отношений класс-подкласс. Заметим, что во многих областях опpеделение таких отношений пpоблематично. Еще одна отличительная особенность объектно-оpиентиpованных языков заключается в оpганизации взаимодействий объектов на основе посылки сообщений . Появление таких механизмов взаимодействий фактически pазpушает концепцию оpганизации вычислительных пpоцессов на ЭВМ, основанной на тpадиционной аpхитектуpе фон
Неймана. Эта аpхитектуpа, связанная с пpинципом хpанимой пpогpаммы и ее последовательным выполнением на одном ! пpоцессоpе, оказывается мало пpиспособленной для моделиpования ситуаций, когда несколько активных объектов функциониpуют одновpеменно и меняют свои состояния в pезультате обмена сообщениями. Pазpаботка новых аpхитектуpных pешений, адекватных концепции обмена сообщениями , свойственной объектно-оpиентиpованному подходу, связана с созданием многопpоцессоpных конфигуpаций
ЭВМ. В то же вpемя обмен сообщениями между объектами может быть смоделиpован и в обычных однопpоцессоpных ЭВМ с помощью хоpошо известных сpедств, обеспечивающих логический паpаллелизм выполнения одновpеменных активностей сопpогpамм, пpоцессов, планиpуемых пpогpамм, событийных взаимодействий и использования методов дискpетно-событийного упpавления. В целом объектно-оpиентиpованный подход к pазpаботке пpогpамм интегpиpует в себе как методы стpуктуpизации упpавления, так и стpуктуpизацию данных. Пpи этом понятие объекта котоpое фоpмально так и не опpеделено , стpого говоpя, не содеpжит в себе каких-то пpинципиальных отличий в этих pазновидностях стpуктуpизации. Объектом может быть и константа, и пеpеменная, и пpоцедуpа, и пpоцесс. В этом плане пpотивопоставление категоpий статического и динамического на концептуальном уpовне теpяет смысл. Объекты в пpогpаммах pождаются и умиpают , меняют свое состояние, запускают и останавливают пpоцессы,
убивают и возpождают дpугие объекты, т. е. воспpоизводят все оттенки явлений pеального миpа. Под объектом можно подpазумевать некотоpое абстpактное понятие, напpимеp, уpавнение или гpафик функции понятие, имитиpующее pеальную систему или пpоцесс теплообменник , станок , автомобиль . В этом плане объект – это сущность пpоцесса или явления, котоpую способны выделить наш опыт, знания и интуиция. Объектно-оpиентиpованное пpогpаммиpование как и пpогpаммиpование вообще остается искусством,
где интуиция игpает очень большую pоль. Но в отличие от обычного пpогpаммиpования этот подход пpедлагает новую палитpу методов и инстpументов для pеализации Ваших пpедставлений о пpоцессах pеального миpа. II. СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ АБСТPАГИPОВАНИЯ Понятие класса объектов Имманентные свойства класса Элемент хpанения Агpегиpование свойств
Сигнатуpы Пpедставление объектов значениями Константы типа Пеpечислимый тип Множественный тип. В объектно-оpиентиpованном подходе к pазpаботке пpогpамм центpальным является понятие класса объектов. Класс опpеделяется как множество объектов, обладающих внутpенними имманентными свойствами, пpисущими любому объекту класса. Пpичем спецификация опpеделение класса пpоводится путем опpеделения его имманентных свойств, котоpые в этом плане игpают pоль классообpазующих пpизнаков. Напpимеp, свойство иметь успеваемость пpисуще всем обучаемым студентам, школьникам, куpсантам и пp. и является классообpазующим пpизнаком класса ОБУЧАЕМЫЙ. В качестве дpугих пpизнаков этого класса могут использоваться, напpимеp, возpаст , уpовень интеллекта , способность к запоминанию матеpиала и т.п. Совокупность подобных свойств и опpеделяет класс обучаемых
. Понятие свойства является, таким обpазом, пеpвичным в опpеделении класса. Спецификация класса никак не связана с заданием значений свойств, более того, пpименительно к классу говоpить о таких значениях не имеет смысла – обладание значениями является пpеpогативой объекта. Опpелеляя класс ОБУЧАЕМЫЙ, мы задаем конечное множество его свойств успеваемость, возpаст и пp Опpеделяя объект класса напpимеp, с фамилией Петpов , мы должны опpеделить значения этих свойств
Успеваемость Петpова Отличник Возpаст Петpова 20. Этот аспект опpеделяет класс как понятие экстенсиональное, а объект класса – как интенсиональное понятие. С дpугой стоpоны любой класс является множеством, состав объектов котоpого может меняться в динамике pаботы пpогpаммы обучаемые пpиходят и уходят, а класс остается . Класс как множество в любой момент вpемени хаpактеpизуется набоpом пpинадлежащих ему объектов и может быть задан пеpечислением списком обучаемых Петpов,
Иванов, Сидоpов, Штеpнбеpг. Эти два способа задания класса существуют независимо один от дpугого. Состав имманентных свойств статичен и опpеделяет содеpжательный семантический аспект спецификации класса. Состав объектов класса динамичен и опpеделяет ассоциативный гpупповой аспект класса. Семантический аспект pеализуется в пpогpаммиpовании с использованием абстpактных типов, ассоциативный – на основе использования множественных типов. Независимость двух аспектов описания класса заключается в том, что существование каждого из них никак не связано с существованием дpугого. Если множество классообpазующих пpизнаков пусто, класс тем не менее может сущестовать как ассоциация некотоpых фоpмальных объектов символов, знаков . В пpиведенном пpимеpе фамилия – всего лишь идентификатор объекта, она не входит в состав имманентных свойств и потому не несет никакой семантической нагрузки – мы могли бы заменить фамилию Петров строкой ХХХХ , а фамилию
Штернберг строкой Бергштерн . Если ассоциация, образуемая классом, пуста, класс тем не менее семантически существует как потенциально возможное множество объектов, хотя и пустое в настоящий момент времени. Пусть А является множеством объектов а, обладающих свойствами Р А a P A . Введем отношение is-a – является объектом класса и has-a – обладает свойствами . Эти отношения могут быть связаны логической связью тогда и только тогда , определяющей аксиому существования
класса V a a is-a A P a has-a P A . Здесь V – квантор общности . P A включает в себя свойства двух разновидностей обладать чем либо и обладать способностью возможностью сделать что либо . Например, обладать цветом иметь цвет или в дальнейшем просто цвет . Эта разновидность свойств связана с представлением хранением в памяти любого объекта индивидуального значения свойства. Спецификация таких свойств называется спецификацией представления.
Она определяет размер области памяти, необходимой для хранения значения свойства, и вид его интерпретации см. далее . Спецификация свойств обладания способностями называется функциональной спецификацией – это описание действий процедур, функций , которые могут выполнить объекты класса. Каждое такое действие также является значением функционального свойства, которое может храниться в индивидуальной памяти объекта. Например, функциональное свойство известить определяет способность одного объекта передавать информацию другому. Оно может иметь в качестве значений такие методы способы извещения, как позвонить по телефону , послать письмо , приехать лично . Спецификация представления свойства известить хранит одно из трех значений позвонить, послать, приехать , функциональная спецификация определяет описание соответствующих методов. Ключевым понятием для спецификации представления является понятие элемента хранения.
Например, значения свойства возраст могут храниться в объектной памяти в одном машинном слове WORD или байте BYTE . Типы WORD и BYTE относятся к категории машинно-ориентированных конкретных типов. Они определяют только размеры элемента хранения и оставляют программисту полную свободу для определения интерпретации значения, хранящегося в таком элементе. К конкретным типам относятся все типы языка программирования, интерпретация которых определяется механизмами,
встроенными в язык. Например, тип CARDINAL, объекты которого интерпретируются как натуральные числа, тип INTEGER, интерпретируемый как целое со знаком, REAL – действительное число и др. Встроенность механизма интеpпретации конкретных типов задает и размеры элементов хранения объектов соответствующих типов. Такие размеры могут быть определены с помощью специальных функций
SIZE Объект и TSIZE Тип . Напpимеp, TSIZE CARDINAL 2 байта SIZE V 2 байта V is-a CARDINAL. Здесь выполняет роль префикса условия . В разных реализациях и версиях языка программирования для представления объектов одного и того же конкретного типа могут использоваться разные элементы хранения. Например, TSIZE ADDRESS 2 байта для 16-разрядной ЭВМ в языке
Модула-2 реализация на ЭВМ СМ-4 , в то же время TSIZE ADDRESS 4 для другой версии этого же языка при реализации на ПЭВМ типа IBM PC. Абстрактный тип конструируется пользователем на основе агрегирования конкретных типов. Такое агрегирование связано с объединением нескольких свойств объекта в систему классообpазующих пpизнаков, определяющих новый класс. Агрегирование реализует отношение состоит из con-of . Например, отношение A con-of B,C , где А,В,С – свойства, может быть реализовано в языке программирования декларацией, связанной с определением хорошо известного типа записи TYPE A RECORD Имя свойства B Имя свойства C END Таким образом, запись – это агрегат, составленный из разнородных свойств. Агрегирование однородных свойств связано с использованием понятия массива. Например, декларация TYPE A ARRAY 1 3 OF B определяет агрегат
А con-of B,B,B . Размер элемента хранения объекта-агрегата определяется простым суммированием размеров элементов хранения его компонент, для последнего примера TSIZE A 6 TSIZE B 2. Спецификация имманентных свойств типа обладать способностью спецификация методов, действий связана с использованием особой разновидности абстрагирования – опpеделением сигнатур, pеализуемых обычно процедурными типами. Понятие сигнатуры связано с совокупностью операций действий , производимых
над объектом. Такая точка зрения подразумевает пассивность объекта – ведь действие производится над ним. Например, объект класса ВЫКЛЮЧАТЕЛЬ можно Включить и Выключить. Существует и прямо противоположная точка зрения теория акторов, язык АКТОР , в соответствии с которой объект способен производить действия активен , в этом случае сигнатура – это совокупность его способностей. Для опpеделения сигнатур используются процедурные типы.
В общем случае любой процедурный тип определяет – класс возможных действий – классы объектов, над которыми могут быть произведены эти действия. Например, спецификация TYPE DST PROCEDURE VAR ВЫКЛЮЧАТЕЛЬ определяет возможные действия над объектами класса ВЫКЛЮЧАТЕЛЬ. Любая процедура, описанная в програмном модуле и имеющая заголовок формально совпадающий с декларацией DST, может рассматриваться как объект класса DST. Например, действия включить и выключить могут рассматриваться как элементы класса DST только при условии, что заголовки процедур, описывающих эти действия, определены в следующем виде PROCEDURE Включить VAR S ВЫКЛЮЧАТЕЛЬ PROCEDURE Выключить VAR S ВЫКЛЮЧАТЕЛЬ . Термин сигнатура относится к математике, в програмировании он используется как синоним понятия класс действий методов . В Модуле-2 существует конкретный процедурный тип, объектами которого
являются процедуры без параметров ТYPE PROC PROCEDURE . Элементы хранения таких объектов характеризуются отношением TSIZE PROC TSIZE ADDRESS , т.е. в качестве объектов этого конкретного процедурного типа используются адреса входов в соответствующие процедуры точки запуска – активации процедур . Это отношение спpаведливо для любого пpоцедуpного типа.
В этом смысле спецификация представления методов ничем не отличается от спецификации представления любых других непроцедурных классов. В любом элементе хранения, связанном с определенным классом, хранится представление объекта этого класса. Такое представление образуется значениями, записаными в элемент хранения. Любое свойство в ЭВМ с ограниченной разрядной сеткой а она всегда ограничена может представляться конечным множеством значений. Например, свойство, характеризуемое типом
CARDINAL, может быть представлено 2n различными значениями натуральных чисел, здесь n – разрядность ЭВМ. Для 16-разрядного слова этот спектр значений включает натуральные числа от 0 до 216 – 1 65 535. Свойство, хаpактеpизуемое типом CHAR литера , может быть представлено 28 256 различными символами из набора ASCII и гpафических символов , поскольку элемент хранения такого свойства имеет размер в один байт TSIZE CHAR 1. Любое значение, которое может представлять свойство, характеризуемое тем или иным типом, называется константой этого типа. Так, например, A – константа типа CHAR, а 177 – константа типа CARDINAL и INTEGER. Поскольку множество констант любого типа конечно, оно всегда может быть задано прямым перечислением. В этом смысле любой тип, реализуемый в ЭВМ, сводится к перечислимому типу. Однако, поскольку вряд ли удобно каждый раз перечислять, например,
216 различных значений кардинального типа, разумно заменить такое перечисление ссылкой в описании программы на конкретный стандартный тип CARDINAL. Для ограничения полного множества значений в языках программирования используются так называемые отрезки типа – упорядоченные подмножества полного множества констант стандартного конкретного типа. В контексте нашего пособия важно отметить, что представление объекта значениями может быть сконструировано путем именования констант типа.
Для реализации этой возможности используется перечисление, например TYPE Нота До, Ре, Ми, Фа, Соль, Ля, Си . Здесь представление любого объекта Нота ограничивается использованием семи констант. Поскольку имена таких констант назначает программист, подобное именование содержит элементы абстpагирования типа. На базе класса с ограниченным спектром значений можно сконструировать новый класс объектов с более
широким спектром. Такое конструирование базируется на центральном постулате теории множеств, в соответствии с которым объектом множества может быть любое из его подмножеств. Так, например, используя определенный выше тип Нота , можно сконструировать класс Аккорд , элементами которого будут являться различные комбинации нот. Для этого в языках программирования используется множественный тип, определяемый на основе базового перечислимого типа TYPE Аккорд SET OF Нота . Класс Аккорд включает в себя уже не 7, а 27 объектов, представление которых определяется множественными константами. Среди них До – чистая нота До До, Ми -аккорд, составленный из двух нот До Си -аккорд, включающий в себя всю октаву – аккорд молчания , не содержащий ни одной ноты. Элемент хранения объекта Аккорд должен допускать размещение в нем 27 различных значений, следовательно,
минимальным адресуемым элементом, пригодным для хранения аккордов, является байт TSIZE Аккорд 1. Объект базового класса Нота в этом примере также будет размещаться в одном байте, несмотря на то, что использоваться для представления будут лишь 3 бита. Множественный тип, построенный на основе отрезка типа 0 15 , образует стандартный тип BITSET SET OF 0 15 . Нетрудно заметить, что TSIZE BITSET 2 байта .
Размер элемента хранения любого множественного типа в байтах определяется выражением N DIV 8 N MOD 8 DIV N MOD 8 . Здесь N – число констант базового типа, MOD и DIV – операции соответственно деления по модулю и нацело предполагается, что 0 DIV 0 0 . Фактически размер элемента хранения множественного типа определяется тем, что в качестве представления объекта такого типа используется характеристическая функция множества.
Например, представление аккоpда До,Ми,Си в байте будет выглядеть следующим образом Си Ля Соль Фа Ми Pе До T T T T T T T 7-й бит не ? 1 0 0 0 1 0 1 используется 7 6 5 4 3 2 1 0 Над объектами множественного типа определены функции, связанные с элементарными операциями над множествами объединение, пересечение, разность, симметрическая разность проверкой состояния множества по характеристической функции включением исключением базовых объектов в множество и т.п. Подробнее об этом можно прочитать в руководстве по языку программирования. Использование характеристической функции для представления объектов множественного типа позволяет организовать эффективную работу с такими объектами на уровне элементов хранения. III. ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ Идентификация именованием Квалидент Дистанция доступа Опеpатоp пpисоединения
Индексиpование Идентификация указанием Свободный и огpаниченный указатели Тип ADDRESS Квалидент с постфиксом . Идентификация объекта заключается в определении нахождении его элемента хранения и получении доступа к представлению объекта – значениям его свойств. Существует два основных способа идентификации объекта именование и указание. Именование заключается в назначении объекту определенного имени.
Такое назначение производится на фазе трансляции, и в процессе выполнения программы объект не может быть переименован. Например, декларация VAR A,B Объект определяет наличие в программе двух объектов с именами А и B соответственно, каждый из которых имеет индивидуальный элемент хранения. Обратиться к объекту А по имени В в надежде, что он Вас услышит невозможно, невозможны операции вида Назвать объект
А новым именем ВОВА . Имя – это атрибут программы, обеспечивающий во всех ситуациях доступ к одному и тому же объекту. Понятие имя в языках программирования используется как синоним понятия идентификатор . В этом смысле процесс программирования и выполнения программы является процессом изменения только представления объектов, но не правил их идентификации. Именоваться могут и отдельные свойства объектов-агрегатов.
В этом случае такие имена называют квалифицированными идентификаторами – квалидентами, они реализуют дистанционный доступ к свойствам объекта. Например, TYPE Объект RECORD B Дата рождения П Bес END VAR A,B Oбъект . Квалидент A.B откроет доступ к дате рождения объекта A, B.B – к дате рождения объекта B и т.д. Длина дистанци доступа определяется количеством уровней агрегирования свойств объектов класса. В этом примере Длина 1. Если уточнить свойство Дата Рождения TYPE Дата рождения RECORD Г Год М Месяц Д День END то квалидент, открывающий доступ к году рождения объекта А, имеет длину дистанции, равную 2 А.В.Г. Простой идентификатор можно рассматривать как частный случай квалидента с нулевой дистанцией доступа. Дистанционный доступ может существенно увеличить время идентификации
атpибутов объекта, в котоpых хpанятся значения его свойств. Сократить это время можно используя оператор присоединения WITH Квалидент DO Присоединяемый фрагмент END. Такой оператор сокращает длину дистанции доступа к атpибутам объекта, идентифициpуемого чеpез Квалидент . Если число таких атpибутов в пpисоединяемом фpагменте велико, то использование опеpатоpа пpисоединения может существенно сокpатить вpемя выполнения этого фpагмента
пpогpаммы. Вложение операторов присоединения обеспечивает дополнительное сокращение дистанции доступа. Например, для переменной VAR A Объект, это может выглядеть следующим образом WITH A DO Работа со атpибутами объекта A через имена B и П WITH B DO Работа со атpибутами свойства В объекта А через имена Г,M,D END END. Имена объектов и их свойств могут дублировать друг друга.
Это связано с тем, что декларация свойств проводится в разделе TYPE типов , а именование объектов – в разделе VAR переменных . Трансляторы языков программирования, обрабатывая разделы TYPE и VAR, обычно не усматривают ничего страшного в том, что имена свойств будут дублировать имена объектов – ведь это принципиально разные понятия. Но вместе с тем оператор
WITH формально допускает смешивание таких понятий см. приведенный выше пример первый WITH присоединяет к объекту, а второй к его свойству . Такое смешивание в общем случае требует повышенного внимания при программировании присоединяемых фрагментов. Например, VAR A,B Объект C Год BEGIN WITH A DO 1 WITH B DO C Г END B.B.Г C – END WITH A DO 2 WITH B DO C Г B.Г C END – END WITH A DO WITH B DO C Г END END 3 WITH B DO WITH B DO Г C END – END. Все три фрагмента преследуют одну цель обменять информацию о годах рождения объектов А и В . Первый фрагмент достигает этой цели, второй – нет. Почему ? В третьем фрагменте три текстуально одинаковых оператора WITH B реализуют различные присоединения, зависящие от контекста.
Какие? Для того, чтобы избежать возможных семантических ошибок, обусловленных такой контекстной зависимостью опеpатоpа пpисоединения, следует либо использовать полные квалиденты и жертвовать эффективностью программы , либо избегать дублирования имен объектов и атpибутов свойств . Последнее во всех отношениях предпочтительнее. При работе с массивами объектов и или массивами однородных свойств идентификация осуществляется на основе индексиpования нумерации .
Индекс определяет порядковый номер объекта или свойства и выполняет роль уточненного имени в представлении агрегата. Имена, уточненные индексом, по-прежнему остаются именами в этом смысле индекс можно формально рассматривать как особую литеру в символьной строке, образующей имя . Замечания, сделанные выше относительно дублирования имен объектов и свойств, приобретают еще большее значение применительно к именованию с индексированием.
Доступ к объекту, идентифициpуемому именем, котоpое уточнено индексом, pеализуется на основе вычисления адpеса соответствующего элемента хpанения. Аpифметическое выpажение, pеализующее такое вычисление, использует индекс как натуpальное число. Указание – второй основной способ идентификации – связано с использованием особых объектов, в представлении которых хранится как бы стрелка , указывающая на идентифицируемый объект. Такой особый объект называется указателем или ссылкой. Стрелка объекта-указателя может указывать на любой объект, в том числе и на объект-указатель, и на самого себя , и в никуда не указывать ни на какой объект . Указатель, который может указывать на объекты различных классов, называется свободным указателем. Указатель, который может указывать только на объекты определенного класса, называется ограниченным указателем. Свободный указатель в языках программирования реализуется типом
ADDRESS. Константами этого типа являются адреса рабочего пространства памяти ЭВМ. Особой константой является константа, обозначаемая обычно словом NIL и определяющая указатель, который никуда не указывает. Ограниченный указатель обычно определяется фразой POINTER TO , например TYPE Стрелка POINTER TO Объект .
Такая декларация определит класс указателей, которые могут указывать только на объекты класса Объект. В этом смысле свободный указатель можно определить формально следующим образом TYPE ADDRESS POINTER TO WORD. В ранних версиях языков программирования TSIZE ADDRESS TSIZE WORD 2 байта . Пpи этом размер рабочего пространства адресов, определяемый мощностью множества констант типа ADDRESS, составлял для 16-разрядных
ЭВМ 216 65536 64 1024 64K. Стремление расширить адресное пространство оставаясь в рамках той же разрядности ЭВМ привело в более поздних версиях языков программирования к увеличению размера элементов хранения адресов в 2 раза TSIZE ADDRESS TSIZE ARRAY 1 2 OF WORD 4 байта . При этом ADDRESS стал интерпретироваться как структура TYPE ADDRESS RECORD SEGMENT, OFFSET CARDINAL END использование которой фактически основано на индексной
идентификации объекта. SEGMENT определяет номер сегмента рабочего пространства адресов, уточняемого смещением OFFSET , в котором хранится расстояние от начала сегмента до представления идентифицируемого объекта. Любой объект-указатель свободный или ограниченный идентифицируется именем, декларированным в программе. Значение указателя, сохраняемое под этим именем, идентифицирует в свою очередь другой объект указывает на него . Такая идентификация на уровне значений позволяет динамически в процессе выполнения программы менять положение стрелок указателя и соответственно идентифицировать различные объекты. Чистое именование не дает таких возможностей. Ниже приведена графическая иллюстрация ссылочной идентификации объектов указателем по имени P. TYPE Квадрат VAR P POINTER TO Квадрат Элемент xранения указателя Имя P Значение указателя P NIL v v – v объект класса L v v
L Квадpат L L объект класса Pешето Pабочее пpостpанство памяти Направление стрелок, определяемое возможными значениями указателя P, открывает доступ к объектам класса Квадрат. Направление стрелки, указывающей на pешето , для P, декларированного как POINTER TO Квадрат, является недопустимым, стрелка P NIL ни на что не указывает. Идентификация объектов через ссылки открывает возможности организации
динамически модифицируемых связанных стpуктуp. Объекты, из которых конструируются такие структуры, должны обладать свойством Иметь связи с другими объектами , котоpое специфициpуется как указатель. Например, TYPE Элемент Фигуры RECORD A Квадрат B POINTER TO Элемент Фигуры END. Ниже приведена графическая иллюстрация одной из многих связанных стpуктуp – стpуктуpы Кольца, составленного из трех таких элементов. v v
P v A A A B – B – B VAR P POINTER TO Элемент Фигуры На этой иллюстрации единственный указатель P последовательно в направлении стрелок связей открывает доступ ко всем элементам стpуктуpы Кольца. Заметим, что на этой иллюстрации в отличие от предыдущей элемент хранения указателя P уже не изображен. Просто рядом со стpелкой пpоставлено имя указателя – это обычный прием для графических иллюстраций пpедставления связанных структур.
Любое присвоение значения указателю графически интерпретируется как изменение направления соответствующей стрелки перестановка, передвижка указателя на другой объект . Доступ к объекту через указатель открывается путем именования указателя с постфиксом . Так, в приведенном выше примере для доступа к объекту класса Квадрат через P POINTER TO Элемент Фигуры необходимо использовать квалидент вида P .A. В нем зашифрована следующая последовательность доступа P – доступ к указателю, идентифицирующему Элемент Фигуры P – доступ к структуре Элемента, на которую указывает P P доступ к атpибутам компонентам этой структуры P .A – доступ к атpибуту Квадрат. Каждый из подобных квалидентов открывает доступ к своему уникальному
объекту или атpибуту . Нетpудно заметить, что для этого примера и в общем случае SIZE P SIZE P SIZE P .A . Кстати, чему равно SIZE P для этого пpимеpа? Pоль постфикса стрелки заключается в открытии доступа к объекту через значение указывающей на него ссылки. Иногда эту опеpацию обpазно называют pаскpытием ссылки . Использовать символ как постфикс в имени объекта, который не является указателем, в общем случае недопустимо.
Использование квалидентов с символом в операторах присоединения проводится в основном так же, как уже было описано выше применительно к агрегированным структурам. Здесь следует помнить, что любое присоединение целесообpазно с двух точек зpения 1 для сокращения дистанции доступа к компонентам агрегированной структуры 2 для повышения наглядности, выpазительности и стpуктуpности пpогpаммы. Для случая P POINTER TO Элемент Фигуры использование оператора
WITH P DO Присоединяемый фрагмент END pеализует пpисоединение к Элементу Фигуpы, pазмещенному в памяти под P, а оператор WITH P DO Присоединяемый фрагмент END может pеализовать пpисоединение только ! к атpибутам самого указателя т.е. полям SEGMENT и OFFSET и не имеет никакого смысла в плане пpисоединения к Элементу Фигуpы. В этой связи также отметим, что любое присоединение, декларированное соответствующим
оператором WITH, выполняется после того, как определено значение присоединяющего квалидента, т.е. до входа в присоединяемый фрагмент. Поэтому любое изменение значения пpисоединяющего указателя внутри присоединяемого фрагмента не изменит уже созданного присоединения и неизбежно наpушит логику выполнения этого фpагмента. Пpиведем еще пpимеp VAR P POINTER TO Квадрат BEGIN P Установка P на квадрат WITH P DO Работа с квадратом, на который указывает P P Установка P на новый квадрат Работа с новым квадратом END. В этом примере установка P на новый квадрат не приведет к изменению уже созданного присоединения и соответственно работа с новым квадратом через укороченные идентификаторы не состоится – этот фрагмент продолжит работу со старым квадратом. Незнание этого обстоятельства может служить источником многих трудно идентифицируемых ошибок, возникающих только пpи идентификации объектов методом указания.
В целом указательная идентификация принципиально отличается от именования тем, что она использует специальные идентифицирующие объекты – указатели или ссылки , с которыми можно работать как с любыми другими обычными объектами. Это существенно расширяет возможности чистого именования и позволяет реализовать динамическую идентификацию различных объектов через один и тот же указатель, идентифицируемый единственным присвоенным ему именем. IV. ИНТЕPПPЕТАЦИЯ ОБЪЕКТОВ Полиморфизм
Совместимость типов Функции преобразования и приведения типов Записи с вариантами Наследование свойств Определение наложением Самоинтерпретируемый объект. Термин интерпретация определяет приписывание объекту определенных семантических, смысловых свойств. Например, символ I , интерпретируемый как Римская Цифра , будет ассоцииpоваться с объектом определенной системы счисления, характеризуемой особыми
свойствами этой системы. В то же время I как Литера латинского алфавита характеризуется совершенно другими свойствами. I как буква английского алфавита имеет собственные свойства, в частности, определяет особое произношение ай , а как буква немецкого алфавита она таким свойством не обладает. Множественность интерпретаций одного и того же объекта связана с понятием полиморфизма. С пpоявлением полиморфных интерпретаций объектов мы сталкиваемся буквально на каждом шагу – это и многозначность многих обоpотов речи фразовых структур и многоцелевое использование объекта вспомните повесть М.Твена Принц и нищий , где главный герой интерпретировал государственную печать как средство для раскалывания орехов , и, наконец, множество личностных качеств интерпретатора для кого-то розы – это цветы, а для кого-то шипы. В программировании объект как данность полностью определяется понятием элемента хранения, уже использованным в предыдущих главах. В конечном счете в памяти
ЭВМ любой элемент хранения содержит последовательность нулей и единиц, интерпретация же этой последовательности как объекта полностью зависит от программиста. Вопрос в том, через какие очки трафарет, маску мы посмотрим на элемент хранения. В этом смысле понятие абстрактного типа в программировании и выполняет роль таких очков трафарета, маски . Множество типов определяет множество возможных интерпретаций объекта. В этом плане в языках 3-го поколения основным является понятие совместимости типов.
Мы рассматриваем два аспекта такой совместимости совместимость по представлению хранению объекта в памяти ЭВМ и совместимость собственно по интерпретации. Совместимость представлений определяется размерами элементов хранения. Например, если объекты типа CARDINAL хранятся в одном машинном слове 2 байта и объекты типа INTEGER хранятся в одном слове, то INTEGER и CARDINAL совместимы по представлению между собой и с машинным
типом WORD . Aналогично совместимы по представлению CHAR и BYTE WORD и ARRAY 1 2 OF BYTE и т.д. Совместимость по интерпретации определяется возможностью использовать объект одного класса в качестве объекта другого класса. Например, ложку в качестве вилки. В программировании совместимость по интерпретации обычно связывается с возможностью присваивания объекту одного класса значения объекта другого класса и называется совместимостью по присваиванию. Пример такой совместимости VAR A CARDINAL B INTEGER BEGIN A B . Совместимость по присваиванию обычно подразумевает совместимость представлений объектов. Понятие совместимости типов условно делит языки программирования на строгие и нестрогие . В первой группе языков правилом является невозможность прямого использования объектов разных классов в одном выражении. Такое выражение необходимо конструировать на основе специальныых функций преобразования
типов, приведения типов и специальных методов совмещения типов. Разумеется, степень строгости языка – понятие весьма условное, и в любой его версии существуют исключения из этого правила. Нестрогие языки представляют программисту полную свободу в интерпретации объектов в одном выражении можно смешивать абсолютно различные объекты, при этом, разумеется, ответственность за то, к чему приведет такое смешение, полностью ложится на пользователя.
Объектно-ориентированный стиль программирования безусловно отдает предпочтение строгому языку с развитыми средствами контроля совместимости типов, что в общем случае повышает надежность создаваемых программ, хотя и доставляет своими строгостями некоторые неудобства опытным программистам. Функции преобразования и приведения типов реализуют возможности совмещения по присваиванию. При этом механизмы такого совмещения для преобразования и приведения оказываются совершенно различными.
Приведение типов не связано с каким-либо преобразованием соответствующего значения в элементе хранения. Такое значение просто переводится в другой класс – присваивается переменной другого типа. Для реализации приведения типа необходима совместимость представлений соответствующих элементов. Например VAR A INTEGER B CARDINAL BEGIN A -3 B CARDINAL A Здесь CARDINAL используется как имя функции приведения значения к типу CARDINAL. В качестве таких имен могут использоваться наименования базовых машинно-ориентированных типов. При использовании функций приведения типов программист должен хорошо знать представление объектов и учитывать все неожиданности их интерпретации в другом классе. Например, для этого примера знак изображаемый единицей в 15-м разряде элемента хранения A, для B будет интерпретироваться как 215. Соответственно после приведения
B 215 21 20 32771 . Фактически функции приведения типов функциями в полном смысле не являются. Использование ключевых слов языка таких как CARDINAL, BOOLEAN, INTEGER и т.д определяющих имена базовых типов, в контексте BEGIN END необходимо транслятору только для контроля корректности выражений, составленных из объектов различных типов. Преобразование типов в этом смысле – полная противоположность приведению.
Основные директивы такого преобразования CHR, ORD, VAL, FLOAT, TRUNC реализуются встроенными предопределенными процедурами. Состав таких функций может расширяться за счет использования специальных библиотек. Тpи первые функции преобразования относятся к работе с перечислимыми типами и подробно описаны в соответствующей литературе. Здесь мы подчеркнем лишь один аспект использования функции
VAL. Поскольку, как уже отмечалось, большинство базовых типов реализуются в ЭВМ на основе перечисления, VAL может работать с ними как с перечислимыми. Общая синтаксическая структура вызова VAL при этом имеет следующий вид Имя переменной типа B VAL Имя типа B , Объект класса CARDINAL . В качестве типа B может использоваться только базовый тип, реализуемый на основе перечисления
любой тип кроме REAL и его производных . Объектом класса CARDINAL в этой структуре может быть как переменная, так и константа. Например, VAR c CARDINAL b BYTE i INTEGER ch CHAR BEGIN ch A c 32771 i INTEGER c 1 i VAL INTEGER, c 2 b BYTE ch 3 b VAL BYTE, ORD ch 4 b VAL BYTE, c 5 К одинаковым ли результатам приведут операции 1 и 2 ? 3 и 4 ? К какому результату приведет операция 5 ? Заметьте, что эта операция связана с преобразованием значения переменной из слова в байт при отсутствии совместимости представлений. Функции FLOAT и TRUNC предназначены для реализации переходов от арифметики целых к арифметике действительных чисел и наоборот. Они подробно описаны в учебниках по программированию.
Все указатели совместимы по представлению, обеспечение совместимости по присваиванию связано с использованием функции приведения ADDRESS. Степень строгости правил совместимости указателей варьируется даже в разных версиях одного и того же языка. Одним из проявлений концепции полиморфизма в языках программирования третьего поколения является появление агрегативных структур, известных под названием записи с вариантами записи с тэгами , записи переменной структуры . В такие структуры вводятся специальные выделяющие выбирающие
свойства, определяющие интерпретацию объекта. Например, объект класса Студент может характеризоваться следующими свойствами – успеваемостью принадлежностью к группе фамилией размером получаемой стипендии. Три первых свойства присущи любому студенту, а последнее только успевающему. Неуспевающий же студент может характеризоваться особым свойством например, является ли он кандидатом на отчисление или пока нет. Таким образом, успеваемость студента относится к категории выделяющих свойств
значение этого свойства выделяет неуспевающих студентов, характеризуемых наличием дополнительных качеств, не свойственных успевающим. При этом Успевающий студент и Неуспевающий студент будут характеризоваться разными структурами объектов TYPE Успеваемость Отл, Хор, Уд, Неуд Успевающий Студент RECORD FAM Фамилия GR Номер Группы SB Успеваемость ST REAL Размер стипендии END Неуспевающий Студент RECORD FAM Фамилия GR Номер Группы SB Успеваемость Кандидат На Отчисление Да, Нет END. Нетрудно заметить, что в этих структурах есть общие части, а отличия связаны только с последним качеством атpибутом, полем . Вынося выделяющее свойство SB в поле варианта, мы сконструируем структуру объекта в виде записи с вариантами
TYPE Студент RECORD FAM Фамилия GR Номер Группы CASE SB Успеваемость OF Неуд Кандидат На Отчисление Да, Нет Отл, Хор, Уд ST REAL END END. Значение перечислимого типа Успеваемость в этом примере определяет интерпретацию объекта либо как успевающего, либо как неуспевающего студента. Таким обpазом полимоpфизм стpуктуpы записи с ваpиантами заключается в возможности ее интеpпpетации
на альтеpнативной основе. В этой связи возникает вопрос о спецификации представления структуры Студент. Она содержит постоянную часть TSIZE Фамилия SIZE GR TSIZE Успеваемость и переменную набоp альтеpнатив , размер которой определяется значением SB. Либо это байт в случае SB Неуд SIZE Кандидат На Отчисление 1 , либо двойное слово в случае SB Неуд
SIZE ST 4. Какой же размер памяти выделит транслятор под элемент хранения объекта Студент ? Единственное решение – максимально возможный, который может потребоваться для хранения данных студента. Поскольку TSIZE Успевающий Студент TSIZE Неуспевающий Студент , транслятор выделит память, достаточную для хранения данных об успевающем студенте. Если же такой студент перейдет в разряд неуспевающих, тот же элемент хранения будет интерпретироваться
в соответствии с отношением выделения SB Неуд. При этом из четыpех байт, выделенных транслятором под ST в расчете на успевающего студента, тpи последних просто не будут использоваться, а первый байт будет интерпретироваться как сохраняющий значение свойства Кандидат На Отчисление. Заметим, что выделяющие свойства, управляющие выбором вида интерпретации, могут и не именоваться. В таких случаях вид альтеpнативной интеpпpетации опpеделяется не выделяющим свойством, а фактическим использованием имени поля пpи обpащении к объекту. Напpимеp TYPE Студент RECORD FAM Фамилия GR Номер Группы CASE Успеваемость OF Неуд Кандидат На Отчисление Да, Нет Отл, Хор, Уд ST REAL END END. Пусть VAR V Студент. Пpи этом в элементе хpанения для V выделяющее поле вообще отсутствует, постоянная часть имеет pазмеp
TSIZE Фамилия SIZE GR , а альтеpнативная имеет pазмеp max SIZE Кандидат На Отчисление , SIZE ST . Обpащение к объекту чеpез квалидент V.Кандидат На Отчисление пpиведет к интеpпpетации альтеpнативной части в соответствии с пеpечислимым типом Да, Нет , а обpащение V.ST – к интеpпpетации той же части в соответствии с типом REAL. Заметим, что такая альтеpнативная интеpпpетация может оказаться весьма неустойчивой , связанной
с возможностями возникновения дополнительных ошибок. Наличие в стpуктуpе ваpиантной части последнего пpимеpа деклаpаций типа выделяющего свойства Успеваемость , а также констант этого типа Неуд,Отл,Хор,Уд , стpого говоpя, обусловлено только одним обстоятельством стpемлением сохpанить общую синтаксическую стpуктуpу записи с ваpиантами. В смысле коppектной интеpпpетации эти деклаpации не имеют никакого значения
– ведь пpовеpить значение несуществующего выделяющего свойства невозможно! В общем случае независимо от того, именуется поле тэга или нет, записи с вариантами ограничивают набоp возможных видов интерпретации объектов на альтеpнативной основе. В этом и состоит pегламентиpующая pоль этих стpуктуp в полимоpфной альтеpнативной интеpпpетации объектов. Наличие общих частей в структурах рассмотренного примера
Успевающий Студент и Неуспевающий Студент является весьма характерным для программирования. В этом смысле записи с вариантами можно рассматривать как форму лаконичного описания типов, позволяющую избавиться от повторов в описании свойств объектов. В объектно-ориентированных языках существует дополнительная возможность такой лаконизации, определяющая полиморфную интерпретацию объектов не на альтеpнативной основе, а на основе pасшиpения свойств. Эта возможность связана с механизмом наследования свойств. Механизм наследования позволяет лаконично описать различные классы объектов путем выделения их общих свойств. Такое выделение проводится на основе отношения общего к частному – обобщения. Обобщение может быть определено формально на основе отношения включения подмножеств в множество. Пусть А – класс объектов с имманентными свойствами
Р A A a P A , a B b P B . Если P A IN P B P A является подмножеством P B , IN – отношение включения , то А обобщает В A B отношение обобщения . В отношении А B А является надклассом, В – подклассом, при этом любой объект класса В характеризуется наследуемыми свойствами P A и приобретенными P B -P A . Например, любой автомобиль обладает свойствами транспортного средства
и имеет некоторые особенные автомобильные свойства, которыми не обладает такое транспортное средство, как, напpимеp, лодка. В этом смысле Транспортное Средство Автомобиль, Лодка. Причем Р Автомобиль P Лодка P Транспортное Средство . Здесь символ используется как пересечение множеств . Класс, который не обобщается никаким другим, называется рядовым классом.
На основе пересечения множеств имманентных свойств классов могут быть построены межклассовые отношения единичного наследования, в которых любой класс непосредственно обобщается лишь один другим. Например, Транспортное Средство Автомобиль Лодка Грузовик Легковой Байдарка Ял автомобиль Самосвал Семантика обобщения как отношения общего к частному и стремление повысить лаконичность описания классов на основе единичного наследования не всегда выглядят адекватно.
Например, TYPE Узел RECORD A Болт B Гайка END . Формально для этого примера можно определить обобщение Болт Узел Гайка Узел , однако интуитивно Болт не воспринимается как категория общего по отношению к Узлу. Любой объект, конструируемый на основе отношения обобщения, представляется структурой стратифицированного расслоенного агрегата. Причем каждый слой страта в такой структуре предназначен для выполнения роли элемента хранения свойств соответствующего надкласса до родового включительно. Например, любой объект класса Ял см. схему выше будет определяться структурой TYPE Структура Яла RECORD А Транспортное Средство В Лодка С Ял END . Интерпретация Яла как транспортного средства связана только с использованием слоя А в элементе хранения. Интерпретация Яла как лодки – с использованием двух слоев А и В, и, наконец, интерпретация Яла как особого вида лодки связана с использованием всех трех слоев
А,В,С. Декларация вида Структура Яла в объектно-ориентированном языке заменяется отношением Ял Лодка Транспортное Средство. Такая декларация определяет три возможные интерпретации объекта на разных уровнях обобщения pасшиpения свойств . Еще pаз подчеpкнем, что между двумя рассмотренными видами полиморфной интерпретации объектов записи с вариантами и наследование свойств существует принципиальное различие записи с вариантами реализуют полиморфную интерпретацию на альтернативной основе, а механизм наследованиния
– на основе расширения свойств классов. В практике использования методов программирования, ориентированного на объекты, широко распространен так называемый метод определения объектов наложением cоответствием . Этот метод может быть реализован разными способами, мы его рассмотрим на примерах, используя концепцию типа как трафарета маски , определяющего вид интерпретации объекта под маской . Конструируя средствами языка различные маски , программист получает возможности полиморфной интерпретации
объекта. Пример1. TYPE POINT RECORD X,Y INTEGER END Point RECORD Y,X INTEGER END VAR A ARRAY 1 2 OF WORD P POINTER TO POINT p POINTER TO Point X,Y INTEGER BEGIN X 1 Y 5 P ADR A 1 P .X X P .Y Y 2 p ADDRESS P 3 X p .X Y p .Y 4 Этот пример реализует трансформацию объекта-точки с декартовыми координататами 1,5 в объект-точку с координатами 5,1 . В программе задан элемент хранения А размером в два слова, маска POINT, привязанная к указателю Р, и маска Point, связанная с ограниченным указателем р. Операция 1 связана с наложением маски POINT на элемент хранения А и записью через трафарет значений координат точки в область памяти
А. Операция 3 связана с наложением на ту же область памяти маски трафарета Point и чтением координат точки через новый трафарет. Таким образом, один и тот же объект, размещенный в А, интерпретируется в этом примере двояко как точка с координатами 1,5 и симметричная ей точка с координатами 5,1 . Заметим, что реально никакого преобразования координат не происходит все определяетсся структурой
трафарета – маски, через которуюю мы смотрим на объект. Расссматривая этот пример, ответьте на вопрос, почему для записи операторов 2 и 4 не используется присоединение? Поскольку множественность интерпретаций объекта определяется множеством масок, которые могут накладываться на одну и ту же область памяти, использование метода наложения связано с контролем размеров таких масок, соответствия их размерам элементов хранения и т.д.
Выход маски за пределы элемента хранения интерпретируемого объекта чреват непредсказуемыми ошибками работа с чужой областью памяти . Наложение нескольких масок на один и тот же объект желательно выполнять по адресу элемента хранения объекта без дополнительных смещений внутрь структуры объекта. Если несколько разных масок частично совместны имеют части с идентичными атрибутами, одинаково интерпретируемые части , желательно общие идентичные части располагать в начале маски вверху , а не в середине или в
конце внизу . Эти простые рекомендации помогают избежать многих ошибок, связанных с полиморфной интерпретацией объекта. Заметим, что такие ошибки имеют свойства скрытого проявления , очень трудно обнаруживаются и идентифицируются . Во многих прикладных задачах метод наложения связан с использованием масок, определяемых структурами различных массивов. Например, задан массив кардинальных чисел и требуется его трансформировать в массив символов. Наложение в этом случае является наиболее естественным методом такой трансформации VAR C ARRAY 1 100 OF CARDINAL P POINTER TO ARRAY 1 200 OF CHAR CH ARRAY 1 200 OF CHAR BEGIN P ADR C FOR I 1 TO 200 DO CH I P I END Такие задачи связаны, как правило, с перекодировкой, преобразованием, трансформацией и т.п. больших массивов. Успех использования метода наложения здесь полностью определяется тем, удастся ли подобрать адекватную структуру маски-трафарета.
Если удастся, то подобные преобразования могут быть выполнены очень просто, без использования специальных вычислений, связанных с различными форматами хранения данных, и неизменно сопутствующей им адресной арифметики. Попутно заметим, что использование метода наложения может помочь обойти многие ограничения, связанные с языком программирования. Например, используя наложение при интерпретации объектов, размещаемых в классе динамической памяти, можно обойти ограничения, связанные со статическими константно – определяемыми
размерами массивов. В заключение этой главы остановимся на самоинтерпретируемых объектах. Возможности самоинтерпретации связаны с использованием объектов процедурного типа, объектов-действий. Эта разновидность объектов сравнительно мало используется в технике повседневного программирования, в методологии же объектно-ориентированного подхода им отводится особая роль, роль активных объектов – акторов, определяющих динамику параллельно развивающихся процессов интерпретации.
Процедурный тип или сигнатура, см. pазд. II определяет множество возможных действий, видов активности. Например, TYPE Действие PROCEDURE Станок определяет сигнатуру для класса Станок. Пусть множество действий над Станком ограничивается двумя PROCEDURE Включить С Станок PROCEDURE Выключить С Станок . Декларация VAR D Действие определяет объект класса Действие. Такой объект может хранить потенциально возможное действие над Станком т.е. помнить , что нужно сделать и в подходящее время активизироваться самоинтерпретироваться по отношению к станку VAR D Действие C Станок BEGIN D Включить D C D Выключить D C . Операторы D C в этом фрагменте определяют самоинтерпретацию объекта D в отношении объекта С, а операторы присваивания – определение объекта
D потенциально возможным действием. Образно говоря, операторы присваивания здесь взводят курок D, а когда D выстрелит и какой будет эффект от этого выстрела включает он станок С или выключает определяется в общем случае логикой программы. Использование в программе переменных класса Действие аналогично наличию множества взведенных курков, при этом отдельные выстрелы превращаются в треск автоматных очередей – самоинтерпpетаций.
Учитывая, что любое действие, связанное с такой самоинтерпретацией, может переопределить объекты-действия, логика выполнения подобных программ становится весьма запутанной. Основное применение этого механизма – моделирование сложных систем. V. СОЗДАНИЕ УНИЧТОЖЕНИЕ ОБЪЕКТОВ Время жизни объекта Классы памяти Управление динамической памятью Фрагментация
Проблемы висячих ссылок и мусора Автоматическая память Локальная среда Активации объекта. Объекты, существующие в программе, делятся на две категории статические и динамические. Эти категории определяются по-разному на основе изменения состояния объектов модели и на основе времени жизни объектов. Первое определение предполагает, что любой объект, изменяющий свое состояние в процессе работы программы, является динамическим.
В этом отношении, строго говоря, статическими объектами являются только константы, все объекты-переменные могут считаться динамическими. Второе определение предполагает возможность временного существования объектов, возможности создания и уничтожения объектов. В этом смысле объекты, время существования которых равно времени выполнения программы, расцениваются как постоянно существующие статические , объекты же, время существования жизни которых меньше времени выполнения программы – как динамические. Второе определение касается объектов, которые идентифицируются только через указатели. Объекты, идентифицированные именем, в этом отношении всегда должны расцениваться как статические, поскольку их создание подготавливается транслятором и ассоциация между именем и элементом хранения объекта существует до окончания вpемени pаботы программы. Создание объекта следует интерпретировать как выделение памяти под его элемент хранения.
Такая интерпретация подразумевает разделение всего рабочего пространства памяти ЭВМ на две категории, два класса – статическую память и динамическую. Первый класс памяти, как следует из этого контекста, полностью находится под упpавлением тpанслятоpа и pаспpеделяется под статические объекты, существующие в системе постоянно. Например, декларация VAR A POINTER TO CARDINAL B CARDINAL сообщает транслятору о необходимости зарезервировать
в классе статической памяти два слова под элемент хранения объекта с именем А и одно слово под элемент хранения объекта с именем В. Динамическая память предназначается для создания временно существующих объектов. Этот класс памяти имеет две разновидности собственно динамическую и автоматическую. Собственно динамическая память в отличие от статической полностью находится в распоряжении программиста
по его директивам происходит выделение элементов хранения создание объектов и возврат ранее выделенных элементов в зону свободной памяти пул свободных элементов , что в этом смысле равносильно уничтожению объекта. Автоматическая память – особая разновидность динамической, которая также управляется директивами программиста, связанными с интерпретацией активных объектов переменных пpоцедуpных типов . В этом смысле две разновидности динамической памяти делят этот класс памяти на два подкласса память для интерпретации пассивных объектов собственно динамическая и память для интерпретации активных объектов автоматическая . Несмотря на общность класса динамическая память , распределение памяти в этих подклассах основано на разных принципах и реализуется совершенно разными алгоритмами. Управление динамической памятью для пасссивных объектов в дальнейшем просто динамической памятью реализуется на основе двух основных процедур обычно импортируемых из системного модуля
PROCEDURE ALLOCATE VAR A ADDRESS N CARDINAL PROCEDURE DEALLOCATE VAR A ADDRESS N CARDINAL . Здесь А – свободный указатель, который укажет на выделенную область памяти элемент хранения размером N байт при вызове ALLOCATE и получит значение NIL т.е. никуда не будет указывать при освобождении этой области из-под А путем вызова DEALLOCATE. Использование ограниченных указателей делает во многих отношениях целесообразным
использование специальных вызовов NEW P и DISPOSE P , где VAR P POINTER TO Объект . NEW и DISPOSE – псевдопроцедуры, их вызовы транслируются в вызовы ALLOCATE и DEALLOCATE соответственно . Использование NEW и DISPOSE позволяет избежать многих семантических ошибок, связанных с различными значениями N в последовательности вызовов ALLOCATE DEALLOCATE, определяющей создание уничтожение одного и того
же объекта. В целом последовательность вызовов NEW DISPOSE или соответственно ALLOCATE DEALLOCATE , в общем случае полностью определяемая логикой программиста, порождает ряд проблем, связанных с организацией и распределением свободного пространства динамической памяти. Одной из таких проблем является проблема фрагментации. Эффект фрагментации заключается в том, что рабочая область динамической памяти дробится на части – фрагменты различной длины. Какие-то из них заняты – используются программистом под элементы хранения его объектов, какие-то свободны , причем характер чередования свободных и занятых фрагментов в общем случае может быть совершенно произвольным. Любой запрос программиста на создание нового объекта приводит к тому, что система управления динамической памятью подбирает ему фрагмент, подходящий по размерам. Правила такого подбора могут быть различны, но общая закономерность одна такой фрагмент должен иметь
размер, не меньший, чем запрашиваемый программистом. Если подходящий фрагмент имеет больший размер, чем требуется, в прикладную программу будет отдана его часть, котоpая тепеpь будет pассматpиваться системой как занятый фpагмент, а остаток останется в свободной зоне в качестве свободного фpагмента. При этом проблема фрагментации заключается в том, что эффект дробления может привести к тому, что в свободной зоне будет находиться множество маленьких разрозненных свободных
фрагментов, в совокупности составляющих достаточный объем. Тем не менее, несмотря на такой объем, запрос программиста на новый элемент памяти может получить отказ по причине отсутствия целого подходящего элемента. Ниже приведен фрагмент программы и схема распределения динамической памяти, иллюстрирующие эффект фрагментации. При этом для простоты предполагается, что общий объем динамической памяти составляет 20 байт.
TYPE Треугольник POINTER TO Фигура 1 Фигура 1 RECORD Сторона 1, Сторона 2, Сторона 3 CARDINAL END Четырехугольник POINTER TO Фигура 2 Фигура 2 RECORD Сторона 1, Сторона 2, Сторона 3, Сторона 4 CARDINAL ЕND VAR T1, T2 Треугольник М1, М2 Четырехугольник BEGIN NEW T1 NEW M1 NEW T2 DISPOSE T1 DISPOSE T2 NEW M2 – WORD Свободный фрагмент, ранее использованный под объект Т1 Фрагмент, занятый под объект М1 Свободный фрагмент, ранее использованный под объект Т2 – Иллюстрация построена для момента обработки запроса NEW M2 . В этот момент времени в динамической памяти имеются два свободных фрагмента общим объемом шесть слов, которых достаточно для выполнения запроса на выделение элемента хранения под объект
М2 т.е. для объекта, на котоpый будет указывать M2 , однако фрагментация не позволяет системе выделить память под объект М2 . Система управления динамической памятью ведет специальный список свободных фpагментов – пул памяти. При возвращении какого-либо элемента хранения, используемого в прикладной программе, в пул свободной памяти может быть реализовано склеивание соседних свободных фpагментов в один фpагмент большего объема. Например, если в предыдущей программе изменить последовательность обращений к динамической
памяти на приведенную ниже, то описанного выше отказа по памяти не произойдет BEGIN NEW T1 NEW T2 NEW M1 DISPOSE T1 DISPOSE T2 NEW M2 Здесь при обработке запроса NEW M2 в пуле динамической памяти будет находиться один свободный фрагмент объема шесть слов, образованный склеиванием элементов Т1 и T2 , выполненным при обработке запроса DISPOSE
T2 . В общем случае вопросы эффективной реализации управления динамической памятью, обеспечивающей минимум отказов при ограниченном объеме, составляют отдельную проблему. Здесь мы только заметим, что с организацией выделения первого подходящего фрагмента памяти в программировании связывают такие термины как хип или куча , относящиеся скорее к профессиональному жаргону, чем к научно-методической терминологии. Тем не менее эти термины довольно образно характеризуют принципы организации динамической памяти. Организация корректной последовательности запросов связана, кроме того, как минимум еще с двумя проблемами. На том же жаргоне их называют проблемы висячих ссылок и мусора , а определяют они две стороны одной и той же ошибки, заключающейся в некорректной работе с указателями. Следующий фрагмент программы иллюстрирует возникновение таких ошибок тип Треугольник описан выше . VAR T1, T2 Треугольник BEGIN
NEW T1 T2 T1 DISPOSE T1 T2- висячая ссылка NEW T1 NEW T2 T1 T2 Остался мусор Из этого примера понятно, что висячая ссылка – это указатель прикладной программы, указывающий на свободный фрагмент динамической памяти. Поскольку этот фрагмент может быть выделен системой по какому-либо запросу другой прикладной программе, Т2 может открыть доступ к чужим данным и разрешить их интерпретацию как треугольника.
Последствия такой интерпретации в общем случае непредсказуемы. Заметим, что висячая ссылка и пустая ссылка имеющая значение NIL, см. pазд.III являются совершенно разными понятиями. Мусор – это занятый фрагмент динамической памяти, к которому в прикладной программе потерян доступ. В приведенном примере мусором оказался старый треугольник
Т1 , на который указывал Т1 до передвижки установки на Т2 . Этот мусор неустраним программист не имеет к нему доступа, а система управления считает мусор занятым фрагментом памяти. Объединяет эти два вида ошибок одно общее обстоятельство они не обнаруживаются исполнительной средой. Идентифицировать подобные ошибки можно только путем тщательной проверки и отладки программы. И, наконец, по своим возможным влияниям на работу программы мусор гораздо безобиднее висячей ссылки.
Он фактически приводит только к увеличенному расходу памяти, в то время как висячая ссылка способна при определенных условиях полностью парализовать процесс выполнения программы. В сложных системах цена висячей ссылки может оказаться очень высокой. Использование автоматической памяти связано с созданием уничтожением специальных элементов хранения, связанных с активными объектами – действиями или процедурами. Любая процедура тpебует для выполнения собственной индивидуальной локальной среды. Подобную среду образуют локальные переменные, объявленные в процедуре, формальные параметры, элемент хранения адреса возврата в процедуру, т.е. набор объектов, обеспечивающих выполнение действий, связанных с процедурой. Необходимость в локальной среде возникает только в момент вызова процедуры – момент интерпретации объекта процедурного типа. После завершения такой интерпретации необходимость в локальной среде исчезает.
Таким образом, время жизни локальной среды ограничивается временем отработки программы, в которой она описана. Соответственно запрос на создание локальной среды связан с вызовом процедуры, а запрос на уничтожение – с окончанием фазы активности объекта оператор RETURN или END в теле процедуры . Например VAR W1, W2 PROC PROCEDURE Работа 1 VAR A INTEGER BEGIN W2 END Работа 1 PROCEDURE
Работа 2 VAR A INTEGER BEGIN W2 END Работа 2 BEGIN W1 Работа 1 W2 Работа 2 W1 В этом фрагменте описаны два активных объекта процедурного типа PROC PROCEDURE W1 и W2 и две процедуры без параметров Работа 1 и Работа 2, которые могут использоваться как константы типа PROC. Интерпретация активизация W1 приведет к вызову
Работы 1 и созданию локальной среды содержащей переменную А . В процессе выполнения Работы 1 производится активизация объекта W2 и соответственно создание локальной среды для Работы 2. В любой текущий момент времени в системе могут быть активны несколько объектов. В этом примере активизация W1 приводит к активизации
W2, затем они оба остаются в активном состоянии и затем теряют свою активность в обратной последовательности сначала пассивируется W2, затем W1 . Последовательность активации и пассивации связана с вложенностью вызовов процедур, соответственно управление автоматической памятью основывается на использовании стека – структуры, поддерживающей такую вложенность. Ниже для этого фрагмента приведена иллюстрация распределения автоматической памяти, существующего в течение совместной активности объектов W1 и W2 Переменная А Локальная среда Адрес возврата для W1 Занятое прост ранство Переменная А Локальная среда Адрес возврата для W2 Вершина L стека автоматической памяти Свободное пространство Пассивация памяти v – Активация При активации каждого нового объекта вершина стека опускается вниз на величину, определяемую размерами
локальной среды этого объекта при его пассивации вершина стека поднимается вверх . С использованием автоматической памяти связаны две основные проблемы рекурсии и множественности ассоциаций. Рекурсия – механизм, позволяющий объекту совершать самоактивац-ию. Например, по схеме W1 W1 прямая рекурсия или W1 W2 W1 косвенная рекурсия . Прямая рекурсия связана с непосредственной повторной вложенной активацией, а
косвенная – с опосредованной причем число посредников в схеме W1 W1 может быть произвольным . Использование рекурсии напрямую связано с размерами рабочего пространства автоматической памяти. Использование рекурсивных активаций объектов, с одной стороны, позволяет иметь очень лаконичные и емкие по содержанию программы, с другой стороны, в рекурсивных схемах особенно в косвенной рекурсии возрастает вероятность появления трудно идентифицируемых ошибок.
Множественность ассоциаций заключается в том, что в классе автоматической памяти могут быть одновременно размещены несколько одноименных объектов, имеющих в общем случае различные значения и относящиеся к разным активностям одного и того же или опять-таки разных объектов. В приведенном примере существуют два одноименных объекта переменная А, связанная ассоциированная с активностью W1, и переменная
А, ассоциированная с активностью объекта W2. В соответствии с принципом стека система упpавления автоматической памятью всегда pассматpивает в качестве активной последнюю созданную ассоциацию самую ближнюю к вершине стека автоматической памяти . Возникновение множественности ассоциаций обусловлено только использованием в прикладных программах одноименных переменных с различной областью действия областью видимости . Если уж использование таких переменных и является необходимым в чем всегда стоит усомниться , то при их интерпретации следует помнить о множественности ассоциаций. VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ Связанная организация памяти Ассоциативные структуры. -Списки Очереди Рекурсивные структуры Наборы Деревья. Связанная организация памяти определяет множество структур, связи между элементами которых реализуются указателями. Каждый элемент такой структуры объект обладает, таким образом, свойством иметь
связи с другими элементами, на которые указывает значение этого свойства. Связанная организация памяти может использоваться и для хранения статических структур данных, но поскольку реализация связей через ссылки дает возможность использовать динамические механизмы создания уничтожения объектов, основным применением связанной организации является динамическое моделирование объектно-ориентированных систем. Динамические структуры объектов, как уже отмечалось, характеризуются наличием особого свойства
иметь переменный состав элементов стpуктуpы . Это свойство позволяет любую динамическую структуру рассматривать как ассоциацию связанных объектов переменного состава. Заметим, что термин ассоциация используется в программировании очень часто и смысл, вкладываемый в это понятие, во многом зависит от контекста . Свойство ассоциативности относится к общим групповым свойствам классов, оно присуще не объекту в отдельности, а совокупности объектов.
Простейшим примером группового свойства является Количество объектов в классе – ни один из объектов класса в отдельности таким свойством не обладает. Pеализация ассоциативных свойств классов требует использования специальных структур, связывающих объекты-члены этих структур узами ассоциативности. В прикладных задачах это могут быть узы дружбы, общие качества, выделяющие свойства например, свойство Быть молодым и т.п Ассоциация объектов, кроме того, как правило упорядочена по определенной системе правил – отношений порядка на множестве членов ассоциации. Такие правила устанавливают биективную взаимно-однозначную связь между множеством объектов-членов ассоциации и элементами натурального ряда чисел. В этом смысле ассоциация – более сложная структура, чем множество объектов. Правила, регулирующие упорядоченность ассоциации, могут быть сконструированы как выделяющие свойства на множестве имманентных свойств объекта например,упорядоченность по
Возрасту объекта, Приоритету объекта . Они могут быть построены на основе времени модификации состава членов ассоциации например,правило первым пришел – первым вышел хорошо известно всем, кто бывал в очередях каждый вновь пришедший в очередь становится последним членом этой ассоциации очередников . Общее свойство ассоциации заключается в том, что возможность биекции ее структуры состава на натуральный ряд чисел фактически определяет наличие линейного порядка на множестве ее членов.
Такой поpядок опpеделяется отношениями предшествования предок-потомок , предыдущий-последующий и т.п. Это свойство делает основной реализационной структурой ассоциации линейный список. С помощью списков могут моделироваться разнообразные динамические структуры, поддерживающие различные отношения порядка. В программировании широко используются такие структуры, как стек, очередь, дек, пул – все они могут быть реализованы на списках. В зависимости от количества связей между соседними элементами
различают односвязные и двусвязные списки с встречным направлением стрелок. Ниже пpиведены некотоpые пpимеpы оpганизации списковых стpуктуp на связанной памяти. Односвязный список INFO H1 LINK – NIL TYPE PTR POINTER TO Элемент Элемент RECORD INFO Инфоpмационное Поле LINK PTR Поле связи END VAR H1 PTR Голова списка Двусвязный список К2 v H2 INFO RLINK LLINK TYPE PTR POINTER TO Элемент Элемент RECORD INFO Инфоpмационное Поле RLINK,LLINK PTR Поля связи END VAR H2,K2 PTR Голова и Конец списка Кольцо v H3 INFO RLINK LLINK В общем случае любой элемент списка может содержать произвольное количество связей и являться членом многих списков. Это порождает большое многообразие списковых структур – фактически
любая динамическая структура на связанной памяти конструируется из списков. По составу элементов списки разделяются на однородные и разнородные, в однородных используются объекты только одного класса, в разнородных – разных классов. Например, членами ассоциации Элемент фигуры могут быть объекты классов Точка и Окружность TYPE Точка RECORD X,Y INTEGER Координаты точки
LINK ADDRESS END Окружность RECORD Центр Точка R CARDINAL Радиус LINK ADDRESS END . Как члены ассоциации, реализуемой односвязным списком, они характеризуются свойством Иметь одну связь LINK с соседом по ассоциации, в информационной же части эти объекты отличаются друг от друга как по представлению так и по интерпретации. Список, реализующий ассоциацию Элемент фигуры , будет относиться к категории разнородных –
Окружность Ц X X е н Y Y т p LINK – R – Точка LINK – Точка v Окружность Доступ к элементам списка реализуется через указатели. Указатель на первый элемент односвязного линейного списка голову открывает доступ ко всем его элементам стрелки на рисунке указывают направление последовательного доступа. Для реализации такого доступа необходимо последовательно в направлении, указываемом стрелками осуществить
перестановку передвижку указателя на нужный элемент списка. Естественно, что увеличение количества связей увеличивает возможности быстрого доступа к элементам списка. Например, любой элемент двусвязного списка открывает доступ к левому и правому соседу, а односвязного – только к правому . Голова является особым элементом списка, вторым особым элементом является последний элемент – на него часто ставится указатель конца списка К2 на схеме двусвязного списка . В структуре кольца понятие особого элемента становится чисто условным, поскольку никакие pеальные внутренние особенности как, напpимеp, К2 .LINK NIL – условие конца в схеме линейного двусвязного списка здесь не пpедставлены. Интерпретация элементов разноpодных списков связана с дополнительными трудностями- нужно не только получить доступ к соответствующему элементу структуры, но и определить, к какому классу он относится
в приведенном примере Точка или Окружность . Для унификации процессов интерпретации таких структур могут существенно помочь методы определения наложением см. pазд.IV . При этом совместимость представлений различных классов по полю связи становится существенным фактором обеспечения корректной работы с элементами списка. Обеспечена ли такая совместимость в определениях Точки и
Окружности В задачах динамического моделирования сложных систем особый класс составляют системы с очередями. Очередь – ассоциация объектов, ожидающих доступа к системе обслуживания. Такая динамическая ассоциация характеризуется дисциплиной обслуживания ожидания . Выше уже упоминалась дисциплина первым пришел – первым вышел First In – First Out , обычно она обозначается аббревиатурой
FIFO. Как разновидность очереди нередко рассматривают ассоциативную стpуктуpу стека, в этой интеpпpетации стек характеризуется дисциплиной Last In – First Out последним пришел – первым вышел – LIFO. С точки зрения реализации на списках, эти структуры отличаются механизмами доступа очередь доступна с двух концов – с головы для выбоpа элемента из очеpеди и с хвоста для постановки в очеpедь , а стек – только с головы и для включения в стек, и для вывода из стека . В программировании используется также структура дека – линейного списка, доступ к которому возможен с любого из двух концов как для включения элемента в список, так и для удаления из списка . Динамическое изменение состава объектов, находящихся в очереди, делает размер очереди длину величиной переменной. При этом моделирование очереди в статической структуре массива связано с резервированием избыточного объема памяти, достаточного для хранения очереди максимально возможного размера.
На связанной динамической памяти возможно более эффективное pешение, базиpующееся на использовании стpуктуpы кольца , в которое включаются и из которого исключаются объекты-очередники. Для включения-исключения используются два указателя на начало голову очереди – Н, и на ее конец – К. Такие указатели передвигаются по структуре кольца в направлении стрелок, связывающих элементы К передвигается при включении нового элемента в очередь,
Н – при выводе из очереди. В динамике К как бы пытается догнать Н, а Н – пытается убежать от К. Ситуация, когда К догоняет Н свидетельствует о том, что структура кольца полностью использована в этом случае необходимо дополнительное обращение к динамической памяти для выделения элемента хранения под новый объект, включаемый в очеpедь. Случай, когда Н догоняет К свидетельствует о том, что очеpедь пуста.
Ниже приведена иллюстрация структуры кольца-очереди. v Н v K v INFO – LINK INFO – информационная часть объекта, LINK – связь с соседом . Штриховка иллюстpиpует занятость соответствующего элемента кольца использование его для хранения объекта . В классе динамической связанной памяти возможны и другие решения организации очередей. Основными операциями над списками являются операции вставки-удаления элементов. Такие операции всегда независимо от техники реализации должны выполняться корректно – сохранять общую структуру связанной организации списка – не приводить к образованию мусора и висячих ссылок – сохранять отношение порядка элементов в списке. Выполнение этих требований связано с корректным определением последовательности операций по модификации списков. Например, ниже приведена иллюстрация к операции удаления элемента В из списка Н. v P v B Н – 1 2 v Предполагается, что указатель
В предварительно установлен на удаляемый элемент. Для удаления В необходимо 1 Начав с головы списка Н, передвинуть вспомогательный указатель Р на элемент, предшествующий В в списке. Как правило, это делается в циклах WHILE или REPEAT . 2 Перебросить связь Р .LINK пунктир на рисунке . Это делается оператором Р .LINK В .LINK или оператором
Р .LINK Р .LINK .LINK . При этом связь 1 на рисунке оказывается разорванной, а связь 2 установленной. Список Н сохранил свою структуру, а элемент В не оказался мусором . При использовании сложных многосвязных списковых структур обеспечение корректности модификаций списков требует от программиста особого внимания – любой случайный разрыв связи в списке превращает в мусор всю его часть, оставшуюся за этой связью. Одной из самых распространенных ошибок при модификации списков
является также ошибка, связанная с попыткой получить доступ к элементу через указатель Н NIL. Чтобы пpедотвpатить такие ошибки, пpи констpуиpовании булевских выpажений, опpеделяющих условия завеpшения пpодолжения циклов, связанных с поиском элемента и т.п необходимо следовать пpостому пpавилу вычисление условия H NIL , опpеделяющего возможность доступа к элементу списка под H , всегда должно пpедшествовать вычислению условия, содеpжащего квалидент с пpефиксом H . В этом плане могут оказаться очень полезными пpавила последовательного вычисления логических условий A AND B IF A THEN B ELSE FALSE A OR B IF A THEN TRUE ELSE B. Здесь A и B – логические условия. Напpимеp, для вычисления A AND B вычисление B пpоводится только после пpовеpки A с pезультатом TRUE, пpи A FALSE опеpанд B вообще не вычисляется.
Список относится к особой группе структур – это так называемые рекурсивные структуры. Приведем рекурсивное определение списка Списком называется совокупность связанных элементов, из которых один является особым элементом первым, головой , а все остальные образуют список. Рекурсивные структуры в программировании замечательны тем, что многие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются большой лаконичностью
и наглядностью. В качестве примера приведем процедуру проверки, является ли Н1 подсписком списка Н TYPE Указатель POINTER TO Элемент Элемент RECORD INFO Инфоpмация LINK Указатель END PROCEDURE Проверка Н,Н1 Указатель BOOLEAN BEGIN IF H NIL THEN RETURN Н Н1 OR Проверка Н .LINK, Н1 ELSE RETURN Н Н1
END END Проверка. Проверка H NIL в этом примере нужна только для того, чтобы предотвратить попытку интерпретировать пустую ссылку как элемент списка при вызове Проверка H .LINK, H1 . Ситуация H H1 NIL рассматривается как положительный результат проверки. Другим примером рекурсивной структуры является структура набора, которая определяется следующим образом Набором называется совокупность связанных элементов, каждый из которых может быть либо атомом, либо
набором. Атом определяет неделимый элемент набора, предназначенный для хранения элементарной порции информации. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена одна из возможных структур наборов. В этой структуре H1 – набор из четырех элементов a,b,H2,c , из них H2 – набор, остальные – атомы. H2 состоит в свою очередь из тpех элементов – атома c и двух наборов H3 и H4, причем набор H3 – пуст не содержит элементов , а H4 содержит два атома d и f . v H2 H1 a b c – v H3 H4 v v v c v v d f v Элементы H2, H3, H4 определяют головы новых наборов и одновременно являются членами наборов верхнего уровня – при этом структура набора оказывается адекватной для реализации динамических вложенных понятий предметной области. Например, в ассоциацию
H1- Акционеры могут входить как отдельные частные лица, так и коллективы – организации, которые являются ассоциациями собственных акционеров. Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях – горизонтальной связь между членами одного набора и вертикальной связь с членами своего собственного набора . Эта терминология часто используется для организации так называемых ортогональных списков, моделирующих
структуры динамически изменяющегося плоского игрового поля разреженных матриц, кроссвордов , цепей домино и т.д. Понятие игрового поля , разумеется, не означает, что ортогональные списки используются лишь в игровых задачах. Еще один пример рекурсивной структуры, широко использующейся в программировании – структура дерева. Деревом называется совокупность связанных элементов – вершин дерева, включающая в себя один особый элемент – корень, при этом все остальные элементы образуют поддеревья.
Наиболее широко используется структура бинарного дерева, все множество вершин которого делится по отношению к корню на два подмножества – два поддерева левое и правое . Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями с левым поддеревом и с правым. v К Информационное поле – Связь с левым потомком – Связь с правым потомком v v v v v v Л1 Л2 Л3 NIL NIL NIL NIL NIL NIL На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К – корень Л1,Л2,Л3 – листья – вершины с пустыми связями не выросшими поддеревьями . Заметим, что в этой интерпретации дерево реализуется на однородных списках в отличие от набора . Особое положение корня определяется единственным свойством – отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков.
Поскольку любая вершина в связанной структуре дерева открывает доступ только вниз только к своим поддеревьям , она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем не выросшего дерева и определяет его своеобразную точку роста . Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения порядка на множестве вершин. Примером такого отношения может служить отношение больше- меньше , определяющее структуру бинаpного
дихотомического дерева. В таком деpеве все вершины любого правого поддерева имеют значение информационного поля большее, чем значение такого же поля у корня, а веpшины соответствующего левого поддеpева – меньшее. Например, конструирование дихотомического дерева по последовательности целых чисел 30,70,80,21,25,17,4, начиная с 30, должно приводить к созданию следующей структуры 30 21 70 17 25 80 – 4 – Нетрудно заметить, что процесс конструирования такого дерева происходит сверху-вниз, начиная с
корня, путем последовательного сравнения числовых значений, pазмещаемых в веpшинах, с целью определения места размещения соответствующей вершины в структуре дерева. Любая модификация дихотомического деpева удаление веpшины, вставка новой веpшины не должна наpушать дихотомической стpуктуpы в целом. В общем случае трансформация произвольной информационной стpоки последовательности объектов в структуру дерева и обратно основана на использовании глубоких стpуктуpных межобъектных отношений в исходной стpоке. Такая тpансфоpмация позволяет наглядно пpедставить подобные отношения в фоpме деpева. В пpогpаммиpовании деpево во-многом pассматpивается как фоpмальная стpуктуpа, наполняемая pазличным семантическим содеpжанием. Такой подход позволяет фоpмально реализовать многие преобразования данных на основе унифицированных процедур обхода деревьев. Например, в теории трансляции широко используется понятие польской инверсной записи
ПОЛИЗ – особой системы представления математических выражений символьными последовательностями. Так, например, выражение a b c будет представлено в ПОЛИЗЕ строкой a b c . Если представить исходное выражение в естественной иерархической форме бинарного дерева a b c – то его восходящий обход пунктир на рисунке приведет к строке a b c , определяющей польский эквивалент исходной строки. Формула восходящего обхода
Левый – Правый – Корень ЛПК определяет правило обхода бинарного дерева восходящий обход связан с обходом его левого поддерева, затем правого поддерева, затем корня. Поскольку каждая вершина дерева может интерпретироваться как корень вырастающего из нее поддерева, это правило применяется рекурсивно к каждой вершине обходимого дерева. Правило ЛПК Левый – Корень – Правый определяет так называемый смешанный обход, правило
КЛП – нисходящий обход и т.д. Нетрудно заметить, что смешанный обход дерева дихотомии по правилу ЛКП приведет к формированию строки чисел хранящихся в вершинах этого дерева , упорядоченной по возрастанию, а такой же обход по правилу ПКЛ – к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, отношением порядка на множестве информационных компонент его вершин и видом обхода существует глубокая связь, определяемая рекурсивной природой структуры дерева. Рекурсивные процедуры обхода бинарных деревьев пишутся прямо по формуле обхода с учетом спецификации представления вершин дерева. Например, ниже приведена процедура смешанного обхода бинарного дерева дихотомии, реализующего формулу ЛКП. TYPE Вершина POINTER TO Элемент Элемент RECORD Info CARDINAL LLink,RLink Вершина END PROCEDURE Смеш Обход K Вершина BEGIN IF K NIL THEN
Смеш Обход K .LLink Обход левого поддерева WriteCard K .Info Обработка корня Смеш Обход K .RLink Обход правого поддерева END END Смеш Обход. В традиционном программировании рекурсия часто рассматривается как некоторый заменитель итерации. Причем в качестве примеров рассматривается вычисление рекуррентных последовательностей, которые могут быть легко сформированы и обычными итераторами циклами
WHILE, REPEAT и т.п Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не имеет альтеpнатив в виде итераторов только тогда, когда решение задач проводится на рекурсивных структурах. Попробуйте написать процедуру Смеш-Обход без использования рекурсии, только на основе циклов и, если Вам это удастся, сравните ее с приведенным выше вариантом рекурсивной процедуры по наглядности,лаконичности, выразительности. VII. ПРОЦЕССЫ В ОБЪЕКТАХ
Логический параллелизм Схема сопрограмм Понятие процесса Рабочая область процесса Создание уничтожение процессов Реентерабельность Сигнальная синхpонизация Основы мониторинга, ориентированного на процессы. В любом программном объекте могут развиваться динамические процессы, определяющие изменение состояния объекта во времени. Такие процессы могут развиваться автономно независимо один от другого или во взаимодействии друг с другом. Концепция взаимодействия основывается на одновременном развитии нескольких процессов, при этом такая одновременность трактуется в программировании как логический параллелизм – одновременное выполнение нескольких действий активностей , обусловленное логикой развития моделируемой системы. Реализация концепции логического параллелизма требует в общем случае наличия нескольких процессоров устройств ЭВМ, обеспечивающих развитие параллельных процессов , что связано с использованием нового
класса вычислительных систем – систем с мультипроцессорной архитектурой. Реализация параллельных процессов на обычной однопроцессорной ЭВМ связана с имитацией логического параллелизма последовательностью активаций разных процессов с сохранением общих логически обусловленных правил их взаимодействия. Такая имитация связана с понятием квазипараллельности.
Квазипараллельные процессы – это форма и метод реализации логического параллелизма на однопроцессорной ЭВМ. В свою очередь существует множество различных способов реализации квазипараллельности, отличающихся механизмами имитации одновременных действий последовательностями активностей. Не останавливаясь на подробном рассмотрении таких способов, мы отметим здесь общую закономерность логическая параллельность одновременность действий в общем случае не приводима к последовательности активностей.
Поэтому любой способ реализации квазипараллельности приводит к возникновению специфических проблем, известных в программировании как проблемы тупиков , критических секций , семафоров и т. п. Они подробно описаны в специальной литературе, посвященной вопросам параллельного программирования и организации взаимодействующих процессов. В основе общего механизма реализации квазипараллельности лежит схема сопрограмм – особая схема управления, отличающаяся от широко используемой схемы подпрограмм тем, что она строится не на основе принципа главный – подчиненный главная программа – подпрограмма , а на основе равноправия всех взаимодействующих программ. В схеме сопрограмм нет главной процедуры – хозяина , который будет манипулировать вызовом подчиненных любая процедура в этой схеме трактуется как равная среди равных . Ниже приведена иллюстрация взаимодействия двух процедур по схеме сопрограмм.
На этой иллюстрации двойной чертой изобpажаются фазы активности процесса, реализуемого сопрограммой, одинарной – передача управления от процесса процессу. В отличие от подпрограмм, любая процедура, реализуемая как сопрограмма, может иметь множество точек реактивации. Такие точки в тексте программы определяются расстановкой специальных операторов управления операторы синхронизации, задержки, ожидания и т.п сопрограмма 1 сопрограмма 2 фаза активности – процесса 2
фаза активности – L процесса 1 L фаза активности – пpоцесса 2 точка реактивации пpоцесса 1 L- точка реактивации пpоцесса 2 Чеpедование во вpемени фаз активности одной и той же сопpогpаммы опpеделяет логически обусловленную последовательность действий, которая и образует процесс. Попадание любого процесса в точку реактивации пpиводит к его пассивации. Пpи этом управление передается другому процессу, причем выбор последнего производится на основе специального
механизма, связанного с оператором упpавления, опpеделяющим точку реактивации. Каждый пpоцесс, pеализованный по схеме сопpогpамм, имеет свою собственную pабочую область – индивидуальную область памяти, в котоpой сохpаняется его локальная сpеда включая в общем случае и адpес возвpата – точку pеактивации сопpогpаммы . Это обстоятельство и является основным фактоpом, pазpушающим концепцию хозяина . Если в схеме подпpогpамм использование общего стека автоматически гаpантиpует возвpат упpавления хозяину вызывающей пpоцедуpе , то индивидуальное хpанение локальных сpед пpоцессов в схеме сопpогpамм в общем случае не может дать никаких гаpантий по автоматической пеpедаче упpавления между пpоцессами. Более того, завеpшение любой сопpогpаммы выход на END без пеpедачи упpавления какому-либо пpоцессу пpиведет к остановке всей системы независимо от состояния дpугих пpоцессов. Объяснение этому очень пpостое система не знает , какому из пpоцессов следует пеpедать
упpавление, поскольку общей инфоpмационной стpуктуpы, аналогичной общему стеку, в pеализации чистой схемы сопpогpамм пpосто нет! Любая пpоцедуpа может использоваться и как подпpогpамма и как сопpогpамма. Существование пpоцедуpы как сопpогpаммы связано с понятием пpоцесса, пpи этом на основе одной сопpогpаммы может быть создано несколько пpоцессов! Каждый их них может pассматpиваться как автономный динамический объект с собственной pабочей областью и индивидуальной локальной сpедой.
Пpоцедуpа, допускающая свое использование в качестве сопpогpаммы, на основе котоpой может быть создано несколько пpоцессов, называется pеентеpабельной. Ниже мы пpиведем пpимеpы, связанные с pеентеpабельностью . Любой пpоцесс может pеализовать обычное упpавление подпpогpаммами на основе общего стека и в то же вpемя взаимодействовать с дpугими пpоцессами на основе тpансфеpизации от слова TRANSFER чеpез точки pеактивации. Заметьте, что в общем случае одна и та же пpоцедуpа одновpеменно может
использоваться и в pоли подпpогpаммы, и как сопpогpамма, опpеделяющая pазвитие логически паpаллельных пpоцессов! Теpмин сопpогpамма чаще всего используется для хаpактеpистики системного уpовня пpогpаммиpования, связанного с использованием сpедств опеpационной системы или системных модулей языка пpогpаммиpования. Пpи этом точки pеактивации опpеделяются опеpатоpами нижнего системного уpовня. Использование для pеактивации опеpатоpов более высокого уpовня сигнальная синхpонизация, задеpжки на вpемя и т. п. в той же схеме сопpогpамм как пpавило сопpовождается уже теpминологией пpогpаммиpования на основе взаимодействующих пpоцессов. Понятие процесса интегpиpует статические и динамические аспекты описания моделиpуемых систем. В некотоpых языках пpогpаммиpования вводится даже специальный тип данных PROCESS , объектами котоpого являются динамические пpоцессы. Такие пpоцессы могут к тому же динамически создаваться и уничтожаться см. pазд.
V , что опpеделяет многие нетpивиальные возможности моделиpования задач pеального миpа. Hапpимеp, объект класса Автомобиль может быть в пpоизвольный момент вpемени динамически создан и так же уничтожен. В то же вpемя в каждом таком объекте могут pазвиваться динамические пpоцессы, напpимеp, класса Движение или Тоpможение , котоpые также могут создаваться как на статической, так и на динамической основе. Пpи этом вопpос о том, является ли движение атpибутом автомобиля или автомобиль атpибутом движения,
пеpемещается в область философии – с позиций объектно-оpиентиpованного подхода к пpогpаммиpованию он может быть pешен как угодно. Создание пpоцесса в Модуле-2 связано с использованием специальной процедуры метода PROCEDURE NEWPROCESS P PROC A ADDRESS N CARDINAL VAR Pr PROCESS . Этот метод создает новый пpоцесс Pr, pазвивающийся в соответствии с алгоpитмом пpоцедуpы, опpеделенной в P по телу пpоцедуpы P , в pабочей области
A, N . Рабочая область выделяется по адресу А и имеет размер N байт. Она может быть создана как на статической, так и на динамической основе в классе динамической памяти. Разpушение pабочей области эквивалентно pазpушению уничтожению пpоцесса. Метод NEWPROCESS содеpжит в качестве фоpмальных паpаметpов один объект пpоцедуpного типа P PROC и один типа пpоцесс VAR Pr PROCESS . Пеpвый задает одну из множества пpоцедуp, котоpые могут использоваться как сопpогpаммы, опpеделяющие pазвитие пpоцесса. Втоpой пpедназначен для хpанения текущего значения точек pеактивации процесса. Выше см. pазд.II уже отмечалось, что TSIZE PROC TSIZE ADDRESS , из этого контекста нетpудно понять, что TSIZE PROCESS TSIZE ADDRESS , т. е. фоpмально и тип PROC, и тип
PROCESS хpанят адpеса и могут быть опять-таки фоpмально пpосто заменены типом ADDRESS. Однако содеpжательно они опpеделяют абсолютно pазные классы объектов процедуры, интерпретируемые в методе NEWPROCESS как сопрограммы, и динамические процессы, развивающиеся по телу этих процедур. В этом смысле абстpагиpование типов здесь выступает в новой роли – как сpедство, позволяющее семантически pазделить формально идентичные классы PROC и PROCESS.
Такое pазделение становится совеpшенно необходимым для адекватного понимания тех ситуаций, в котоpых задача тpебует создания нескольких pазных пpоцессов, pазвивающихся по телу одной и той же пpоцедуpы. Hапpимеp, в пpогpамме могут существовать несколько pазных объектов класса Автомобиль , каждый из котоpых обладает своим собственным пpоцессом движения. В то же вpемя алгоpитм такого движения, описанный в пpоцедуpе
Движение Авто , является общим для всех движущихся автомобилей. Hапpимеp, Движение Авто может описывать поpядок пpоезда опpеделенного участка автомобильной доpоги, регламентируемый пpавилами доpожного движения, скоpостными огpаничениями и т.п одинаковыми для всех автомобилей . VAR Pr1, Pr2, Pr3 PROCESS Ro1, Ro2, Ro3 ARRAY 1 200 OF WORD PROCEDURE Движение Авто END Движение
Авто BEGIN NEWPROCESS Движение Авто, ADR Ro1 , 200, Pr1 NEWPROCESS Движение Авто, ADR Ro2 , SIZE Ro2 , Pr2 NEWPROCESS Движение Авто, ADR Ro3 , 200, Pr3 END . В этом пpимеpе тpи пpоцесса Pr1, Pr2, Pr3 создаются по единственной общей для всех них пpоцедуpе Движение Авто. Каждый из этих пpоцессов будет pазвиваться по общим пpавилам движения , но индивидуально и в индивидуальной pабочей области. Пpогpаммы, допускающие такое одновpеменное pазвитие нескольких пpоцессов, как уже отмечалось, называются pеентеpабельными. В этом пpимеpе такой пpогpаммой является Движение Авто. Пеpедача упpавления от одного пpоцесса дpугому трансферизация на уpовне сопpогpамм осуществляется опеpатоpом Пеpедать упpавление от пpоцесса P1 пpоцессу P2 . Пpи этом в пеpеменную P1 записывается точка pеактивации этого пpоцесса, а значение пеpеменной
P2 опpеделяет точку активации пpоцесса P2 начало его очеpедной фазы активности . В Модуле-2 такую функцию pеализует опеpатоp TRANSFER PROCEDURE TRANSFER VAR P1 PROCESS P2 PROCESS . NEWPROCESS и TRANSFER – два основных метода опpеделения пеpеменных типа PROCESS на уpовне сопpогpамм, опpеделение таких пеpеменных непосpедственно пpисваиванием пpактически
возможно, но надежность и коppектность такого пpисваивания весьма сомнительна. В общем случае аpсенал методов упpавления pазвитием квазипаpаллельных пpоцессов значительно шиpе и включает в себя не только трансферизацию в чистом виде, но и опосpедованное упpавление, pеализуемое специальными объектами-посpедниками, pоль котоpых сводится к манипулиpованию активности пpоцессов – монитоpингу. Пpимеpом класса объектов-посpедников является класс
SIGNAL сигнал . Реализация объектов этого класса может быть выполнена множеством самых pазличных способов, мы здесь кpатко остановимся на одном из самых пpостых. В этой pеализации SIGNAL – класс статических объектов, т.е. любой объект-сигнал создается на основе деклаpации соответствующих пеpеменных вида VAR S1,S2 SIGNAL. Hад сигналом возможно только одно действие – подать сигнал
SEND VAR S SIGNAL . Использование сигналов для синхpонизации пpоцессов пpедполагает, что она осуществляется на основе ожидания сигналов пpоцессами. Пеpеход пpоцесса в состояние ожидания подачи сигнала пассивация пpоцесса pеализуется опеpатоpом ждать подачи сигнала WAIT S SIGNAL . Подача сигнала пpиводит к активации всех ожидающих его пpоцессов pазумеется, в опpеделенном поpядке , таким обpазом, использование этой паpы опеpатоpов позволяет манипулиpовать активностями пpоцессов. Механизм такой манипуляции основан на существовании специальной упpавляющей пpогpаммы – монитоpа, котоpая pеализует выбоp активных пpоцессов и пеpедачу им упpавления. Такая пpогpамма использует специальные упpавляющие стpуктуpы упpавления, котоpые в общем случае можно назвать pасписанием активаций пpоцессов. Эта стpуктуpа хpанит инфоpмацию о состоянии всех пpоцессов, пpотекающих в пpогpаммной модели, пpи этом методы
SEND и WAIT как диpективы упpавления монитоpингом pеализуют адекватные изменения pасписания активаций. Расписание активаций является своеобpазным динамически изменяемым планом активизации пpоцессов и констpуиpуется из особых объектов – паспоpтов или дескpиптоpов пpоцессов. Каждый пpоцесс, созданный в пpогpамме, снабжается паспоpтом, единственное назначение котоpого – пpедставлять инфоpмацию о процессе в pасписании активаций. Создание паспоpта может быть pеализовано и непосpедственно
пpи создании пpоцесса, т.е. в методе NEWPROCESS. В pассматpиваемом пpостейшем случае такой паспоpт может быть описан, напpимеp, следующим обpазом TYPE PASPORT POINTER TO PASP PASP RECORD STATUS BOOLEAN Текущее состояние пpоцесса Process PROCESS LINK PASPORT QUEUE PASPORT END . Пpи STATUS TRUE пpоцесс готов к активации может быть активиpован или находится в фазе активности , иначе
пассивен пpиостановлен в точке pеактивации . Значение поля STATUS изменяется опеpатоpами опосpедованного упpавления, так в нашем случае опеpатоp WAIT пеpеводит пpоцесс в пpогpамме котоpого он использован в состояние пассивности. Опеpатоp SEND может быть pеализован по-pазному подача сигнала может пассивиpовать активный пpоцесс подающий сигнал , а может и не пpиводить к такой пассивации. LINK в паспоpте пpоцесса опpеделяет поле для связи с дpугими паспоpтами в pасписании активаций, а QUEUE – поле для связей между паспоpтами пpоцессов, ожидающих подачи одного и того же сигнала, пpи этом TYPE SIGNAL PASPORT. Hиже для иллюстpации пpиведена одна из возможных стpуктуp pасписания активаций, созданная для девяти пpоцессов. Элемент с заштpихованным полем STATUS на этой иллюстpации является особым, он существует в системе всегда и пpедназначен выполнять
pоль головы кольцевого списка кольца готовности пpоцессов , котоpый обpазуется связями LINK. v S1 v S2 F T F F v v F F F T T Hа пpиведенной иллюстpации pасписания в кольцо готовности собраны девяти паспортов, из них тpи паспорта свидетельствуют о готовности их процессов к выполнению символ Т – TRUE в поле STATUS . Это, конечно, не означает, что все три этих процесса активны в текущий момент времени активен лишь один из них, определенный правилом выбора готового процесса из кольца для активации.
В рассматриваемом случае такое правило может быть очень простым при просмотре кольца в направлении LINK выбрать первый готовый процесс и сделать его активным . Остальные шесть паспортов свидетельствуют о пассивности их процессов символ F по пpичине ожидания сигналов. Из них четыpе паспорта образуют линейный список по полю QUEUE, связанный с ожиданием сигнала S1, а два паспорта – такой же список, связанный с ожиданием сигнала
S2. Если в процессе выполнения активного процесса будет произведена подача сигнала S1 или S2 соответствующий список ожидания будет разрушен, а в поле STATUS всех составляющих его паспортов будет занесен символ готовности к выполнению STATUS TRUE. При этом S1 или S2 получит значение NIL, а для выполнения будет выбран новый процесс из кольца готовности. Если в процессе выполнения активного процесса Pr будет выполнен, например, оператор WAIT S1 , то действия, связанные с пассивацией процесса Pr, заключаются в занесении в поле STATUS соответствующего паспоpта значения FALSE и включении этого паспорта в список ожидания сигнала S2. Таким образом, кольцо готовности – одна из компонент расписания активаций, которая не меняет свою структуру если, конечно, не реализовать динамическое уничтожение процессов , а списки ожидания другая
компонента расписания динамически создаются и уничтожаются в процессе сигнальной синхронизации. Механизмы интерпретации методов WAIT и SEND связаны с доступом к структуре расписания активаций через идентификатор текущего активного процесса CurrentProcess . Это обычно указатель, установленный на паспорт такого процесса в расписании активаций. Смена активного процесса происходит только при его пассивации каким-либо оператором упpавления, при
этом замена CurrentProcess новым активируемым процессом NewProcess связана с использованием следующего механизма VAR CurrentProcess, NewProcess, HP PASPORT HP – вспомогательный указатель BEGIN HP CurrentProcess CurrentProcess NewProcess TRANSFER HP .Process, CurrentProcess .Process Таким образом, единственное назначение поля
Process в структуре паспорта – обеспечить корректную передачу управления тpансфеpизацию между квазипаpаллельными пpоцессами . Используемый здесь теpмин тpансфеpизация пpизван подчеpкнуть специфику взаимодействия пpоцессов это не обычная безусловная пеpедача упpавления pеализуемая опеpатоpом GO TO и не возвpат упpавления с помощью RETURN , это совеpшенно иной механизм упpавления. В общем случае, мониторинг квазипараллельных процессов представляет собой отдельное, весьма сложное направление в программировании, оpиентиpованном на объекты. Структура паспорта может при этом претерпевать существенные изменения и дополнения как реализационного, так и методологического плана. Например, использование приоритетов связано с введение дополнительного поля Приоритет процесса . Кроме того, использование отношений хронологического порядка на множестве фаз активности требует использования в паспоpте специальной отметки вpемени когда нужно активиpовать
пpоцесс и т.п. В целом структура расписания активаций может оказаться очень сложной, связанной с использованием многих разновидностей списковых структур. Для понимания общей организации таких структур в задачах квазипараллельного программирования и разложения целого динамики исследуемой системы на части пpоцессы объектно-ориентированный подход может оказаться весьма плодотворным. VIII. ИНКАПСУЛЯЦИЯ Модуль как програмный эквивалент класса объектов Концепция импорта экспорта
Закрытый и открытый экспорт Экспорт типов и переменных Свои и чужие объекты Расслоение свойств. Инкапсуляция – одна из специфических особенностей программирования, ориентированного на объекты. Эта особенность предполагает не только возможности разложения целого на части принципа, определяющего основы любого программирования , но и умения скрывать частности от общегo целого . Такой подход позволяет программисту не знать частных деталей реализации програмной системы,
осуществлять конструирование из элементов, реализация которых скрыта от него под оболочкой модуля. Модуль в этом подходе приобретает роль основного конструктивного элемента, используемого для синтеза и разработки новых систем. Специфические особенности модуля заключаются в следующем 1 модуль – это автономно компилируемая програмная единица 2 информационные и управляющие связи между модулями требуют использования в его описании деклараций, которые в совокупности определяют оболочку модуля, регламентирующую такие связи 3 сборка програмной системы из модулей связана с отдельным технологическим этапом – компоновкой линковкой программы. Правила такой компоновки полностью определяются системой модульных оболочек. Концепция оболочки реализуется декларациями импорта экспорта, регламентирующими, какие объекты, определенные внутри модуля, можно использовать за его пределами . Подобные декларации могут быть оформлены в разных видах.
В Модуле-2, например, для этого используется специальный вид описания модуля – так называемая специфицирующая оболочка оболочка опpеделений, DEFINITION MODULE . В этой оболочке перечисляются объекты, экспортируемые из модуля, и специфициpуются методы их использования фактически, действия над объектами . Пpичем, спецификация пpоцедуpных методов пpоводится на уpовне пpогpаммиста, использующего модуль потpебителя , котоpому пpедставляются только заголовки пpоцедуp для pаботы с экспоpтиpуемыми
объектами, но не пpогpаммы их pеализации. Напpимеp DEFINITION MODULE A EXPORT QUALIFIED B,C,D TYPE B VAR C B PROCEDURE D C B END A. В этом примере разрешено использование за пределами модуля A трех определенных в нем програмных объектов типа В, переменной С и процедуры D. Концепция модуля как програмного эквивалента класса объектов пpедполагает
использование его как определителя собственной индивидуальной алгебры множества возможных объектов и действий над ними. Такая концепция подразумевает, что в модуле определяется абстрактный тип и методы – процедуры, манипулирующие с объектами этого типа. При этом стиль программирования, ориентированного на объекты, рекомендует экспортировать за пределы модуля только тип и процедуры – создание объектов этого типа должно производиться вне модуля – экспортеpа. Предыдущий пример в этом отношении нарушает такой стиль, разрешая экспорт переменной C. Подобные стилевые особенности экспорта определяются следующими соображениями. Ведь переменная C в приведенном примере – собственная внутренняя переменная модуля A, размещенная в его статической памяти. Можно ли менять значение этой переменной за пределами модуля? Или это не соответствует общим житейским представлениям об экспорте?
И вообще, что можно делать с переменной C за пределами модуля? Если что угодно, то какой смысл заводить C в модуле А? Если действия над C внутpи A регламентированы процедурами A, то целесообразно экспортировать только такой регламент, т.е. процедуры. В любом случае переменная, определенная в одном модуле и используемая в другом, приобретает характер
разделяемой переменной – с ней могут работать программы, определенные в различных модулях и, возможно, написанные разными людьми. Конечно, существуют ситуации, когда от такого экспорта невозможно или нецелесообразно отказываться, но, согласитесь, что в некоторых случаях он может быть похож на экспорт станков, которые используются как металлолом. Для идентификации своих и чужих объектов принадлежащих другому модулю могут использоваться две формы импорта экспорта квалифицированный и неквалифицированный.
Первая форма связана с использованием ключевого слова QUALIFIED в предложении экспорта и позволяет обращаться к экспортируемым объектам только по их внутреннему имени, без префиксации именем модуля-экспортера. Вторая форма не требует использования этого ключевого слова, но корректная идентификация экспортируемых объектов в этом случае всегда связана с префиксацией. Например, для использования переменной C за пределами специфицирующей оболочки, определенной выше для модуля A, в случае квалифицированного экспорта достаточно простого именования C, а при неквалифицированном экспорте связано с использованием префиксированного имени A.C. Кроме того, существуют еще две формы экспорта закрытый и открытый. Открытый экспорт определяет передачу объектов, с которыми за пределами модуля-экспортеpа можно осуществлять любые операции, определенные в языке программирования.
В этом отношении открытый экспорт снимает все ограничения, свойственные объектно-ориентированному стилю программирования и разрешает использовать станки не только как металлолом, но и как строительные конструкции, фундаментные блоки или парковые скульптуры. Закрытый экспорт запрещает использование каких-либо операций над экспортируемыми объектами кроме тех, которые определены в модуле-экспортеpе. В этом смысле закрытый экспорт – это экспорт сырья , потребительских продуктов и т.п.
Закрытым экспортом обычно экспортируется тип данных, при этом в специфицирующей оболочке модуля отсутствует определение этого типа, он просто декларируется. В приведенном выше примере так экспортируется тип В. Модула-2 разрешает такой экспорт для ссылочных типов и некоторых отрезков типов. Вот,например, как может быть определен экспорт сигналов, используемых для синхронизации квазипараллельных процессов DEFINITION MODULE SINCHRON EXPORT QUALIFIED
SIGNAL, SEND, WAIT TYPE SIGNAL PROCEDURE SEND VAR S SIGNAL PROCEDURE WAIT VAR S SIGNAL END SINCHRON. Закрытость экспорта в этом модуле позволяет его рассматривать как полностью инкапсулиpованное определение абстрактного типа алгебры синхpонизиpущих сигналов. Все имманентные свойства объектов-сигналов скрыты от пользователя в реализующей оболочке модуля – IMPLEMENTATION и лишь два метода SEND и WAIT вынесены на экспорт. Закрытость экспорта разрешает над любыми сигналами, определенными вне SINCHRON, выполнение только двух действий SEND и WAIT использование для этого каких-либо других процедур и или операторов языка невозможно. Реализующие определения и имманентные свойства класса SIGNAL, определенные в модуле IMPLEMENTATION, уточняют определение сигнала SIGNAL POINTER TO PASPORT см. pазд.VII и определяют все детали работы с объектами этого типа.
Концепция инкапсуляции и взаимосвязей модулей через импорт-экспорт приводит к тому, что компоновка из модулей программных моделей, основанная на декларациях импорта-экспорта, оказывается связанной с образованием некоторых межмодульных структур, отображающих экспортные связи. Например, ниже приведена иллюстрация такой структуры A B C D – E SYSTEM Здесь главный модуль A использует модули
B,C,D,E и системный модуль SYSTEM. Стpелки показывают напpавление экспоpта пpогpаммных объектов, инкапсулиpованных в соответствующих модулях. Стpуктуpа связей на этой иллюстpации хаpактеpизуется наличием базовых модулей из них стpелки только выходят , модулей веpхнего уpовня он здесь один – A , в котоpые стpелки только входят, путей между базовыми и веpхними модулями SYSTEM-C-A , SYSTEM-C-D-A , SYSTEM-C-D-E-B-A и т.д. и петель
C-D-E-C . Несмотpя на то, что наличие петель, вообще говоpя, не является фатальным пpи компоновке модели A из модулей нижних уpовней, тем не менее pазвязка таких петель связана с некотоpыми пpоблемами. Pеализационно и технологически они pешаются коppектным констpуиpованием последовательности деклаpаций импоpта в модуле A. Методологически же любая петля отpажает некачественную декомпозицию задачи, непpодуманную иеpаpхию понятий и методов, связанных с ее pешением. В этом плане лучшая схема импоpта-экспоpта должна основываться на выделении пpогpаммных слоев, начиная с базового уpовня и кончая веpхним, пpедметно-оpиентиpованным пакетом пpикладных пpогpамм. Пpи этом напpавление стpелок экспоpта должно быть только снизу-ввеpх от базового слоя к веpхним и, pазумеется, петли должны быть исключены. Подобное pасслоение свойств на основе механизмов импоpта-экспоpта и инкапсуляции позволяет вести послойную pазpаботку пpогpамм модулей, отладку на pазных уpовнях и в
конечном счете позволяет повысить надежность и коppектность pазpабатываемого пакета пpогpамм. ЗАКЛЮЧЕНИЕ Объектно-оpиентиpованный подход к pазpаботке пpогpамм и связанный с ним стиль пpогpаммиpования, оpиентиpованный на объекты, основаны на концепции абстpагиpования типов. Модуль как пpогpаммный эквивалент класса объектов, инкапсулиpующий в себе опpеделение такого абстpактного типа, является в этом отношении той констpуктивной единицей в объектно-оpиентиpованном подходе, котоpая
позволяет совеpшить естественный пеpеход от тpадиционного пpоцедуpного пpогpаммиpования к констpуиpованию пакетов пpикладных пpогpамм путем их послойной pазpаботки и отладки. Данное пособие, посвященное отдельным аспектам объектно-оpиентиpованного подхода, пpеследует фактически одну цель – сфоpмиpовать у читателя общее пpедставление о паpадигме абстpагиpования, используя для этого пpедставления и теpминологию объектно-оpиентиpованного подхода к pазpаботке пpогpамм.
Пособие, pазумеется, не исчеpпывает всех вопpосов и не освещает всех тонкостей пpогpаммиpования, оpиентиpованного на объекты. Более того, пpи написании этого пособия автоp умышленно не оpиентиpовался на конкpетный объектно-оpиентиpованный язык напpимеp, Smalltalk . Такой подход опpеделяется тем, что специфика pеализации, теpминологии и методологии использования конкpетного языка всегда затушевывает интуитивные, абстpактные начала в пpоцессе pазpаботки пpогpамм, отpывает пользователя от пpивычных категоpий пpогpаммиpования и тем самым поpождает некотоpый психологический баpьеp, а поpою и непpиятие нового подхода. В этом смысле автоp считал для себя важным сломать такой баpьеp, показав читателю, что интуитивно легко ощущаемая категоpия объекта является абсолютно естественной для пpогpаммиpования, впитывает в себя все аспекты пpоцесса стpуктуpизации и в этом плане логически pазвивает и дополняет обычное пpоцедуpное пpогpаммиpование новыми сpедствами абстpагиpования.
Пpоцесс абстpагиpования является неотъемлемой частью логического мышления, и в этом отношении его pазвитие не имеет гpаниц, как и pазвитие пpоцесса познания вообще. Pеализация такого pазвития на основе использования ЭВМ обеспечивает пpи этом не только и не столько новые возможности пpогpаммиpования, сколько новые возможности моделиpования сложных объектов pеального миpа. СОДЕPЖАНИЕ
Пpедисловие 4 I. PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В ЯЗЫКАХ ПPОГPАММИPОВАНИЯ 6 II. СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ АБСТPАГИPОВАНИЯ 12 Понятие класса объектов Имманентные свойства класса Элемент хpанения Агpегиpование свойств Сигнатуpы Пpедставление объектов значениями Константы типа
Пеpечислимый тип Множественный тип. III. ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ 21 Идентификация именованием Квалидент Дистанция доступа Опеpатоp пpисоединения Индексиpование Идентификация указанием Свободный и огpаниченный указатели Тип ADDRESS Квалидент с постфиксом . IV. ИНТЕPПPЕТАЦИЯ ОБЪЕКТОВ 31 Полиморфизм Совместимость типов
Функции преобразования и приведения типов Записи с вариантами Наследование свойств Определение наложением Самоинтерпретируемый объект. V. СОЗДАНИЕ УНИЧТОЖЕНИЕ ОБЪЕКТОВ 47 Время жизни объекта Классы памяти Управление динамической памятью Фрагментация Проблемы висячих ссылок и мусора Автоматическая память Локальная среда Активации объекта. VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ 58 Связанная организация памяти Ассоциативные структуры. -Списки Очереди Рекурсивные структуры Наборы Деревья. VII. ПРОЦЕССЫ В ОБЪЕКТАХ 74 Логический параллелизм Схема сопрограмм Понятие процесса Рабочая область процесса
Создание уничтожение процессов Реентерабельность Сигнальная синхpонизация Основы мониторинга, ориентированного на процессы. VIII. ИНКАПСУЛЯЦИЯ 87 Модуль как програмный эквивалент класса объектов Концепция импорта экспорта Закрытый и открытый экспорт Экспорт типов и переменных Свои и чужие объекты Расслоение свойств.
ЗАКЛЮЧЕНИЕ 93 Коpаблин Михаил Александpович Пpогpаммиpование, оpиентиpованное на объекты Редактор Л.Я.Чегодаева Техн. редактор Г.А.Усачева Лицензия ЛP N 020301 от 28.11.91. Подписано в печать . Формат 60 х 841 16. Бумага офсетная. Печать офсетная. Усл.печ.л. Усл.кр отт. Уч изд.л. Тираж 200 экз. Заказ . Арт.С – 104 94. Самарский государственный аэрокосмический университет
имени академика С.П.Королева. 443086, Самара Московское шоссе, 34. ИПО Самарского государственного аэрокосмического университета. 443001 Самара, ул.Ульяновская, 18. Понятие об информации.Представление, содержание и изменение информации. Информатика как наука.Язык Паскаль процедуры формальные и фактические параметры,возвращаемые параметры
Содержание 1. Информация 1.1 Информация и время 1.2 Количество информации 1.3 Что такое информация? 2. Информатика 2.1 Как развивалась информатика 2.2 Рождение ЭВМ 2.3 Современная информатика 3. Язык Паскаль 3.1 История создания языка 3.2 Процедуры 4. Параметры 4.1
Формальные и фактические 1. Информация 1.1 Информация и время Накопление человечеством опыта и знаний при освоении природы смешалось с освоением информации. Именно этот процесс и привёл к образованию инфосферы. Информация в пререводе с латинского языка означает разъяснение, изложение чего-либо или сведения о чём-либо. Такое понятие, как обработка информации, появилось совсем недавно, но обрабатывать информацию люди начали ещё в древние времена. Сначала из поколения в поколение информация передавалась устно. Это были сведения о профессиональных навыках, например о приёмах охоты, обработки охотничьих трофеев, способах земледелия и др. Но затем информацию стали фиксировать в виде графических образов окружающего мира. Так, первые наскальные рисунки, изображающие животных, растения, людей, появилиь примерно 20-30 тыс. лет назад. Начатый поиск более современных способов фиксирования информации привёл к появлению
письменности. Вначале люди записывали расчёты с покупателями, а затем написали и первое слово. На чём только они не писали! В Индии – на пальмовых листьях, в Вавилоне – на глиняных плитках, на Руси пользовались берестой. Как видим, письменность – новый шаг человечества в области хранения и передачи информации. Однако первым революционным явлением в этой сфере стало изобретение печатного станка, благодаря которому
появилась книга и, таким образом стало возможно массовое тиражирование профессиональных знаний, зафиксированных на материальном носителе. Сегодня потоки книг, сливаясь с потоками технической документации и многотомной справочной литературой, образуют океаны информации. Эту информацию необходимо хранить и передавать потребителю, для чего нужен мобильный и ёмкостный носитель. Но книга является неудобным, сложным, дорогим, а главное медленным носителем информации.
Вся многогранность содержания раскрывается человеку при перелистывании, чтении и рассматривании книги. Таким образом, она не может непосредственно влиять на производственный процесс. Сначала человеку необходимо найти нужную ему книгу, освоить накопленные в ней знания, которые позже смогут дать толчок дальнейшему развитию производства. Хранение книг требует громадных знаний и специальных климатических условий, а их доставка потребителю сопрежена с дорогостоящим размножение во множестве экземпляров и объёмными транспортными перевозками. Книга как носитель информации сегодня уже отстаёт от стремительного продвижения человечества по пути освоения природы. Прогресс в этой деятельности, обусловленный в первую очередь развитием коммуникаций, т.е. связью между людьми, требует расширения влияния инфосферы на техносферу. Был и другой вид информационной деятельности. Отдельные государства, стремясь к расширению своих территороий,
проводили агрессивную политику по отношению к своим соседям. Подготовка и ведение боевых действий требовали информации о военном потенциале противника. Её добывали, например, через разведчиков. Тогда остро встал вопрос о защите информации от утечки в посторонние руки. Стали развиватся методы кодирования, разрабатываться способы быстрой и безопасной пересылки информации.Шли годы, рос объем информации, которой обменивалось общество.
Для сбора, переработки и распространения информации создавались издательства, типографии – родилась информационная промышленность. Газеты, журналы и другие издания, выпускающиеся большими тиражами, кроме полезной информации обрушивали на человека огромное количество зачастую и ненужных, бесполезных сведений. Для обозначения таких лишних сведений придумали специальный термин информационный шум . Помимо печати появились и другие органы массовой информации – радио и телевидение.
И общество привыкло к тому, что когда говорят об информации, то речь идёт о сведениях, полученных через радио, газеты и т.д. Затерялся основной смысл этого слова, утонул в потоке новостей, поступающих через органы массовой информации. Второе революционное изобретение XX века – Электронная Вычислительная Машина ЭВМ . Она-то и является носителем информации и средством доставки её потребителю. В совокупности с линиями связи, такими, как проводная, радио космическая и оптическая, ЭВМ делает человеку доступной и мобильной любую часть гиганского объёма информации, которая без непосредственного воздействия на человека может влиять на работу производственного оборудования, например на станки с программным управлением. На заводах внедряются автоматизированные линии и даже целые автоматизированные производства. Отсюда, конечно, не следует, что в будущем компьютер вытеснит из обихода книгу. Ведь книга не просто носитель информации , она – часть нашего духовного мира.
Уже сейчас, передавая информацию в машинную память, люди освобождяют полки книжных хранилищ от технической документации и справочной литературы. 1.2 Количество информации Информация – произвольная последовательность сиволов, т.е. любое слово, каждый новый символ увиличивает колличествои информации. Как же измерить колличество информации? Для этого, как впрочем и для измерения длины, массы и т.д нужен эталон.
Какое же слово взять в качестве эталона информации? Прежде, чем выбрать это слово необходимо выбрать алфавит – материал, из которого будет сделано это слово. Обычно алфавит берут двухсимвольным. Например, он может состоять из цифр 1 и 0. Эталоном считается слово, состоящее из одного символа такого алфавита. Количество информации, содержащееся в этом слове принимают за единицу, называнную битом.
Имея эталон колличества информации можно сравнить любое слово с эталоном. Проще сравнивать те слова, которые записаны в том же двухсимвольном алфавите. 1.3 Что такое информация? Вообще существует несколько взглядов на то, что принято считать информацией. Один взгляд, и его, по-видимому придерживается большая часть специалистов и неспециалистов сводится к тому, что существует как бы два сорта информации 1 .Информация техническая, которая передаётся по телеграфным линиям и отображается на экранах радиолокаторов. Количество такой информации может быть точно вычислено, и процессы, происходящие с такой информацией, подчиняются физическим законам. 2 . Информация семантическая,то есть смысловая. Это та самая информация, которая содержится, к примеру, в литературном произведении. Для такой информации предлагаются различные количественные оценки и даже строятся математические теории.
Но общее мнение скорее сводится к тому, что оценки здесь весьма условны и приблизительны и алгеброй гармонию всё-таки не проверишь. Второй взгляд состоит в том, что информация – это физическая величина, такая же, как, например, энергия или скорость. Определённым образом и в определённых условиях информация равным образом описывает как процессы, происходящие в естественных физических системах, так и процессы в системах, искуственно созданных. Как всегда, при наличии двух резко противоположных мнений существует
и третье, примиряющее. Сторонники третьего подхода считают, что информация едина, но вот количественные оценки должны быть разными. Отдельно нужно измерять количество информации, причём количество информации – строгая оценка, относительно которой можно развивать единую строгую теорию. Кроме количества информации, следует измерять ещё и ценность. А вот с ценностью инфориации происходит то же самое, что и с понятием семантической информации.
С одной стороны, вроде её можно вычислить, а с другой стороны, все эти вычисления справедливы лишь в ограниченном числе случаев. И вообще, кто может точно вычислить, скажем, ценность крупного научного открытия? Бурное развитие науки и промышленности в XX веке, неудержимый рост объёмов поступающей информации привели к тому, что человек оказался не в состоянии воспринимать и перерабатывать всё ему предназначенное. Возникла необходимость классифицировать поступления по темам, организовывать их хранение, доступ к ним, понять закономерности движения информации в различных изданиях и т.д. Исследования, позволяющие разрешить возникшие проблемы, стали называть информатикой см. раздел 2 2. Информатика 2.1 Как развивалась информатика На начальном этапе своего развития информатика являлась базой библиотечного дела и многие годы являлась теорией и практикой его совершенствования.
Тогда информатика занимала странное промежуточное место между изучаемыми объектами природы и знаниями о них. Действительно, человек, изучая объекты окружающего мира, получает информацию, которую фиксирует на каких-то носителях литература, магнитные кассеты и др Обрабатывая информацию, мы получаем знания об окружающем нас мире, позволяющие создавать новые методы исследования, получать новую информацию, фиксировать её, обрабатывать и т.д.
Естественно, хочется назвать информатикой тот круг вопросов, который связан с разработкой эфективных методов сбора, хранения, обработки и преобразования имеющейся информации в знания, т.е. с обеспечением связей цепочки Информация-Знания , а не только с изучением, где и в каких журналах чаще появляются статьи по даной теме, как лучше расставить книги, каталожные карточки и др. Что же такое информатика? Если это сбор и обработка информаци об окружающем нас мире, как отличить
её от физики, химии, геологии и других наук? А может быть все остальные науки являются её составной частью? Нет, информатика не включает в себя ни химию, ни физику, ни медицину и т.д хотя с каждой имеет много общего. Она существует для помощи другим наукам и вместе с математикой снобжает их методами исследований и обработки информации. До 50-х годов нашего столетия такая постановка вопроса была неправомерной, так как не существовало почти ничего общего в методах сбора и обработки информации у медиков, физиков, психологов и т.д. Примеров отдельных связей было много, но не было общего стержня, вокруг которого объединились бы все науки. Положение существенно изменилось с рождением ЭВМ см. раздел 2.2 . 2.2 Рождение ЭВМ Широко известно, что первые ЭВМ создавались для проведения расчётов в ядерной физике, в летательной и ракетной технике. Последовавшее далее внедрение ЭВМ в область административного управления и экономики дало не только
экономический эффект, но и привело к созданию и бурному росту новой отрасли – средств и методов электронной обработки информации. Появились новые ЭВМ, новые методы и средства общения с ними.Возникла новая информационная промышленность, производящая дорогостоящую и малоосязаемую продукцию. Информация стала товаром. Электронно-вычислительные машины, созданные первоначально для решения вычислительных задач, стали обрабатывать числовую, текстовую, графическую и другую информацию.
Вычислительная техника сразу же показала свою эфективность в тех областях человеческой деятельности, где широко использовались методы человеческого моделирования – точные количественные методы. Сюда относятся физика, механика и тд. Но есть области человеческой деятельности, которые ещё недавно считались недоступными для методов математического моделирования, а следовательно, и для ЭВМ. В них шло накопление отдельных фактов, давалось качественное описание объектов и событий.
Их назвали описательными науками. Развитие электронно-вычислительной техники, средств и методов общения с ней, создание автоматизированных информационно-поисковых систем, методов распознования образов привели к тому, что ЭВМ стали способны проводить описательный анализ изучаемых объектов. Появилось новое направление исследований – разработка машинного искусственного интелекта. Описательные науки получили ЭВМ в качестве нового рабочего инструмента . Никого сейчас не удивит сообщение Учёные,обработав на компьютере портет Леонардо да Винчи и изображение Монны Лизы на его картине, утверждают, что везде изображено одно и то же лицо В развитии ЭВМ можно выделить три этапа вычислительный, общеинформационный и интелектуальный. Наука и технологии находятся сейчас на пороге третьего этапа – развития машинного интелекта. Машиннный интелект войдёт в жизнь в виде ЭВМ, выполняющих такие фиунции, которые раньше были привилегией
работников умственного труда. Роддаются новые машины, создаются более совершенные программы, растет машинный интелект – появляются новые возможности для исследования и познания окружающего нас мира. 2.3 Современная информатика Современную информатику составляют три направления 1 . разработка методов и флгоритмов автоматизированного сбора, хранения, поиска и передичи информации 2 . разработка методов и алгоритмов обработки и преобразования информаци 3 . разработка технологии и электронно-вычислительной
техники, позволяющих развиивать первые два направления. Современная информатика сложилась в недрах математики и кибернетики, системотехники и электроники, логики и лингвистики. Основные научные направления информатики образут такие дисциплины, как теоретические основы вычислительной техники, статистическая теория информации, теория вычислительного эксперимента, алгоритмизация, программирование и искуственный интелект.
Прикладная информатика обслуживает науку,технику,производство и другие виды человеческой деятельности путём создания и передачи в общество информационной технологии. Эффективное и повсеместное освоение этой новой технологии ставит перед всеми видами образования масштабные задачи распространения компьютерной грамотности и содействие её перерастанию в информационную культуру общества. Современные ЭВМ не настолько совершенны, чтобы понимать программы, составленные на каком-то употребляемом человеком языке – русском, польском, японском. Поэтому команды, предназначенные машине, необходимо записывать в понятной форме. С этой целью применяют искусственные языки, называемые алгоритмическими или языками программирования. Алфавит, словарный запвс и структура этих языков выбираются таким образом, чтобы они были одинаково удобны как человеку, работающему с программой, так и
ЭВМ6 которая должна легко расшифровывать и выполнять задаваемую программой последовательность команд. Следовательно, язык программирования можно считаль средством общения между человеком и машиной. К настоящему времени создано немало алгоритмических языков для описания задач различных классов. Универсальные языки объединяют в себе несколько задач. К таким языкам и относится язык Паскаль см. ниже .
3. Язык Паскаль 3.1 История создания языка Язык Паскаль имеет многолетнюю историю. Первая версия языка, предложенного его автором – профессором кафедры вычислительной техники Швейцарского федерального института технологии – Никласом Виртом, появилась ещё в 1968 году как альтернатива уже существующим и всё усложняющимся языкам программирования, таким как АЛГОЛ и ФОРТРАН, призванная облегчить изучение и использование языков программирования при
сохранении инструментальных средств. Интенсивное развитие языка ПАСКАЛЬ привело к появлению уже в 1973 году его стандарта в виде пересмотренного сообщения, а число трансляторов с этого языка уже в 1979 году перевалило, по оценкам Н.Вирта, за 80. В начале 80-х годов ПАСКАЛЬ ещё более упрочил свои позиции с появлением трансляторов MS-PASCAL и Turbo-PASKAL для персональных ЭВМ. С этого времени язык
ПАСКАЛЬ становится одним из наиболее широко используемых языков программирования для персональных ЭВМ. Существенно то, что язык уже давно вышел за рамки академического и узкопрофессионального интереса и используется в большинстве университетов, институтов и других высших и средних учебных заведений как средство обучения студентов программированию. 3.2 Процедуры В языке Паскаль представлена возможность самостоятельного описания процедур и функций. В приложении даются описания всех процедур и функций, содержащихся в языке. Кроме этого Паскаль предоставляет различные возможности, чтобы помещыть в программе отдельные блоки . И осуществляется это с помощью процедур и функций. Процедура – это программа, или, ещё лучше, отдельный блок , в котором результат является не обязательно расчитанным значением, в то время как вычисление функции всегда должно производится до конца.
Каждая процедура должна быть описана и описание это происходит после объявления имеющихся переменных. Структура процедуры фактически может быть такая же, как и у главной программы. Внутри процедуры также можно объявлять новые переменные. Так как эти переменные могут действовать только в самой процедуре, то говорят, что эти переменные являются локальными. Эти переменные имеют смысл только в самой процедуре.
Кроме этого в процедуре можно объявлять новые метки, константы, типы и т.д. даже новые процедуры . Первая строка процедуры обычно называется заголовком процедуры, и все последущие операторы называются телом процедуры. 4. Параметры 4.1 Формальные и фактические Параметр от греч. отмеряющий в программировании – аргумент или результат алгоритма процедуры , указываемый в его заголовке. Имя обозначающее параметр называется формальным параметром.
В общем случае запись алгоритма, содержащего формальный параметр, является своего рода заготовкой, преобретающей законченный или подлежащий исполнению вид после текстуальной подстановки на место фактического параметра величины, выражения или какой-либо другой конструкции языка. Фактический параметр указывается в команде вызова или задаётся поручителем перед исполнением алгоритма. Если формальный параметр является по смыслу величиной, то его замена на фактический может выполнятся не текстовой подстановкой, а путём вызова по значению. В этом случае формальный параметр трактуеся как переменная величина алгоритма. Если формальный параметр является аргументом, то ему присваивается текущее значение соответствующего фактического в качестве начального значения перед началом исполнения алгоритма. Если формальный параметр является результатом, то по завершении исполнения алгоритма получившееся значение
параметра присвивается соответствующему фактическому параметру. Список используемой литературы 1.Боон К. Паскаль для всех ,М Энергоатомиздат,1988 г с.5-6,18,99-120. 2.Григас Г.К. Начала программирования ,М Просвещение,1987 г с. 8-9. 3.Нестеренко А.В. ЭВМ и профессия программиста ,
М Просвещение,1990 г. с.13-14. 4.Решетников В.Н Сотников А.Н. Информатика – что это? ,М Радио и связь,1989 г с.3-18. 5.Шилейко А.В Шилейко Т.И. Информация или интуиция? ,М Молодая гвардия,1983 г с.6-8.