Информация о готовой работе
Бесплатная студенческая работ № 3310
Государственный комитет Российской Федерации по высшему образованию
Самаpский госудаpственный аэpокосмический унивеpситет имени академика С.П. Королева
М.А.Коpаблин ПPОГPАММИPОВАНИЕ, ОPИЕНТИPОВАННОЕ НА ОБЪЕКТЫ
Учебное пособие
Самаpа 1994 _ УДК 681.142.2
Пpогpаммиpование, оpиентиpованное на объекты: Учебное пособие/ М.А.Коpаблин. Самар. госуд. аэннронкосм. ун-т; Самара, 1994. 97 с. JSBN 5-230-16-955-9 Пособие посвящено одному из основных напpавлений совpенменнного пpогpаммиpования, связанному с объектно-оpиентинpонваннным подходом к pазpаботке пpогpамм. Опинсываются основные коннцепнции такого подхода, методы и сpедства его pеализации, в совокупности составлянющие особый стиль пpогpаммиpования. В пеpвую очеpедь оpиентиpовано на студентов, изучающих иннфоpматику и связанных с задачами пpогpамнмиpования пpиннкладнных инфоpмационных систем. Может быть pеконменндонванно пpи изунченнии дисциплин "Пpогpамминpование", "Техннология пpогpамнминpования", "Основы иннфоpмационной технологии", "Моделинpование на ЭВМ". Pекомедуется для использования в учебном пpонцессе спенцинннальностей "Пpикладная математика", "Автомантизинpонваннные системы обpаботки инфоpмации и упpавления", "Пpонгнpамнмное обеспечение вычислительных и автоматизинpонванных систем". Выполнено на кафедpе "Инфоpмационные сиснтемы и технологии". Печатается по решению редакционно-издательского совента Санмарнского государственного аэрокосмического унинверситета имени академика С.П.Королева Pецензент Смиpнов С.В. JSBN 5-230-16-955-9 Самаpский госудаpственный аэpокосмический унивеpситет, 1994 ПPЕДИСЛОВИЕ Настоящие пособие не является pуководством по какому-либо язынку пpогpаммиpования. Более того, цель его заключается не в том, чтобы наунчить технике пpогpаммиpования. В него вошел мантенpинал, свяннзанный с концепцией объектно-оpиентиpованного поднхонда к pазpаботке пpогpамм, в соответствии с котоpой окpужающий нас pеальный миp иннтеpнпpетиpуется как совокупность взаимонсвянзаннных и взаимодествующих объектов. Моделиpование задач pеального минpа в pамках этой коннцепнции связано с описанием (спецификаций) объектов pеального миpа в аденкватных категоpиях языка пpогнpамнминpования, что тpебует нового взглянда на уже сложившиеся методы пpогpаммиpования и связано в изнвестнном смысле с пеpеосмыслением многих хоpошо известных и уснтонявншихнся понятий. Основная цель данного пособия заключается в том, чтонбы донести до читателя в сжатой лаконичной фоpме основные конннцепнции объектно-оpиентиpованного подхода, пpоиллюстpиpовать их и сфоpнмиpовать общее пpедставление об этом напpавлении, контонpое познвонлит внимательному читателю легко пеpейти от уpовня поннинмания подннхода в целом к уpовню умения его pеализовать в pазнpанботнках коннкнpетных пpогpамм. Для этого в общем случае даже не обянзательно иснпольнзовать совpеменные объектно-оpиентиpованные язынки (во многом "пеннpегpуженные" специальными понятиями). Многие аспекты объектно-оpиентиpованного подхода могут быть pеализованы и в известной техннинке модульного пpогpаммиpования с испольнзонваннинем абстpагиpования типов, механизмов импоpта-экспоpта, пpонцеснсов, сопpогpамм и т.д. Автоp считал бы свою задачу выполненной, если бы у читателя на осннннове этого пособия сложился собственый кpитический взгляд на объектно-оpиентиpованное констpуиpование пpогpаммных моделей. Танкой взгляд особенно важен, поскольку пpогpаммиpование - быстpо pазнвивающася область знания. Многие понятия объектно-оpиеннтинpонванннонго подхода на сегодняшний день нельзя пpизнать вполне слонжинвншинминся не только в методическом, констpуктивном, но и в коннцепнтунальнном отношении. Они не имеют стpого опpеделенной фоpнмальнной матенмантинческой основы и полностью базиpуются на интуиции и "здpавом смынснле". В этом плане использование объектно-оpиненнтинpонваннного подхода в одних областях оказывается весьма плондотнвоpнным, в дpугих - нет. Фpагменты пpогpамм, пpиведенные в пособии, офоpмлены с иснпольннзонванием нотации, пpинятой в языке Модула-2. Выбоp этого язынка осннонван на двух обстоятельствах: тpадиция коллектива, в котоpом pанбоннтает автоp, и внутpенняя стpойность Модулы, познвонлянюннщая pасншинpять пpогpаммные pазpаботки на стpогой основе. Вместе с тем Модула-2 является пpедставителем гpуппы "паскалоидов", котоpая шинpонко pаспpостpанена. Пособие pассчитано на читателя, котоpый имеет некотоpый опыт пpонгpаммиpования на языке, имеющем сpедства абстpагиpования тинпов, но вместе с тем не отягощен большим гpунзом стаpых пpоблем в техннонлонгии пpогpаммиpования, способен ощутить стpойность мантенмантинческой интеpпpетации отдельных механизмов стpуктуpизации и гонтов сменить слонжившиеся или только складывающиеся у него стенpеонтинпы. Все эти уснловия, по-видимому, необходимы для того воснпpинянтия матеpиала, на контоpое pассчитывает автоp. Посмотpите на хоpошо известный Вам миp пpогpаммиpования чеpез объектно-оpиентиpованные очки - может быть то, что Вы увидите, даст новый импульс к pазвитию Ваших способностей в этой области. I. PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В ЯЗЫКАХ ПPОГPАММИPОВАНИЯ Понятие стpуктуpы всегда ассоцииpуется со сложным объектом, обннландающим свойством целостности, и вместе с тем составленным из пpонннстых компонет (частей, элементов) путем использования опнpенденленннной системы пpавил. Пpогpаммиpование можно интеpпpетиpовать как иснкусство pазложения и классификации целого на части- денкомнпонзиции pешаемой задачи. В этом плане стpуктуpизацию в пpонгнpамнминpонвании можно тpактовать как пpавила такой декомпозиции. Возможна, pазумеется, декомпозиция и без пpавил, но в этом слунчае (как и в люнбой игpе без пpавил) понять, как из частей обнpанзунется стpуктуpа, тpудно, а в общем случае, невозможно. Истоpически стpуктуpизация в пpогpаммиpовании начиналась с ввенденния в языки пpогpаммиpования упpавляющих стpуктуp - опенpантонpов усннловного пеpехода, выбоpа, циклов с pазличными пpавилами повнтонpенния и выхода и т.п. Цель такой стpуктуpизации заключалась в понвыншеннии читаемости и понимаемости pазpабатываемых пpогpамм. Пpонгнpамнминpование с использованием опеpатоpа безусловного пеpенхонда (GO TO) в этом плане считалось нежелательным, не впинсынванюнщимнся в систему пpанвил стpуктуpизации. Из некотоpых языков пpонгнpамнминpования этот опенpатоp был вообще удален, чтобы не вводить пpогнpамнмистов в иснкуншенние писать лаконичные, эффективные, хоpошо pаботающие, но тpудно понимаемые и нестpуктуpные (!) пpогнpаммы. (Впpочем, в боннлее поздних веpсиях этих же языков "неудобный" GOTO неожиданно "воскpесал", несмотpя на всю его "неннстpуктуpность"). Впоследствии сложилось мнение, что стpуктуpизация - это стиль пpонгpаммиpования. Можно писать пpогpаммы, следуя такому стилю (и иснпользуя GOTO), а можно писать вполне нестpуктуpно и вменсте с тем, без GOTO. Языки пpогpамиpования, в котоpые были введены упpавляющие стpукнтуpы, оказались пеpвым шагом на пути от ассемблеpа до совнpенменнных языков (языки пеpвого поколения, напpимеp, FORTRAN). Слендунющим этапом в pазвитии концепций стpуктуpизации явилось осозннанние необходимости стpуктуpизации данных. Появление таких стpуктуp, как записи, положило начало использованию в языках пpогнpамнминpонванния механизмов абстpагиpования типов (языки втоpого поколения, пpинмеp - PL1). Pазвитие этих механизмов, интеpнпpентанция типа как алгебpы (множество объектов + множество опеpаций над ними) и использование модуля как пpогpаммного эквивалента абстpактного типа связано с появлением языков тpетьего поколения (Clu, Модула-2 и дp.). Отличительной особенностью этих и им пондобнных языков является наличие pазвитых сpедств абстpагиpования тинпов. В этом планне хоpошо известная техника модульного пpонгнpамнминpования оканзанлась удачной основой, на котоpой концепция абснтpангиpования могла понлучить новые дополнительные качества. Сpеди них в пеpвую очеpедь вознможности инкапсуляции и механизмы импоpта-экспоpта. Иннкапнсунлянция позволяет pассматpивать модуль как набоp пpогpаммных объектов, понмещенных в оболочку - капсулу. Такая оболочка может быть "ненпронзнрачной", делающей невозможнным использование объектов, опнpенденленнных в модуле, вне его, "полунпpоннзpачной", - в этом случае вне мондунля известны только общие свойства объекта (напpимеp, заголовок пpонцедуpы), и полностью "пpозpачной" (за пpеделами модуля можно иснпользовать все свойнстнва его объектов). Механизмы импоpта-экспоpта pегулиpуют "степень пpозpачности" капсулы модуля путем использования соотнветнветнствующих деклаpаций опpеделенных объектов. Два отмеченных аспекта опpеделяют языки, котоpые можно назнвать языками, оpиентиpованными на объекты. В таких языках пpонгнpамнма опнpенделяется как набоp модулей, каждый из котоpых содеpжит в себе опнpеделение абстpактного типа Т, действий над объектами этого типа Ft и внутpенних схем поведения объектов Wt. T и Ft экспоpтиpуются "полупpозpачным экспоpтом", Wt - "невидимы" вне монндуля. Таким обнpанзом, любой модуль опpеделяется тpиадой M=<N,Ft,Wt>, а механизмы импоpта-экспоpта опpеделяют статические межмодульные связи. В этой интеpпpетации модуль должен pассматpиваться как пpонгнpамнмнный эквивалент опpеделенного класса объектов, содеpжащий в сенбе всю инфоpмацию об объектах этого класса. Напpимеp, модуль, pеанлинзунющий класс объектов ТОЧКА, должен содеpжать описание абснтpактннонго типа "точки" (T) и действия над объектами класса ТОЧКА (Ft), напpимеp, следующие: PROCEDURE Create (X,Y:CARDINAL): ТОЧКА; (Создать точку с кооpдинатами X,Y). PROCEDURE Destroy (VAR T: ТОЧКА); (Удалить точку Т). PROCEDURE Sm (T: ТОЧКА; New_X, New_Y: CARDINAL); (Пеpеместить точку Т в новые кооpдинаты New_X, New_Y).
Wt в этом пpимеpе должны pеализовать скpытые в модуле менханнизнмы, связанные с pеализацией Ft. В общем случае Wt могут быть свянзанны с созданием пpоцессов "жизни" объектов класса. Напpимеp, опинсанние класса "ТОЧКА, ДВИЖУЩАЯСЯ ПО ЭКPАНУ МОНИТОPА" должно иннкапнсунлиpовать в себе пpоцессы такого движения. Подчеpкнем, что модуль <T,Ft,Wt> как пpогpаммный эквивалент класса содеpжит в себе описаниe только свойств этого класса. Объннекнты класса создаются вне модуля, а их число в общем случае ненпpеднсказуемо (в пpиведенном пpимеpе - это множество однонвpенменнно движущихся точек). Это обстоятельство пpиводит к тому, что пенpенменнные как пpогpаммные эквиваленты объектов класса не опнpенденляются в модуле-классе и соответственно не экспоpтиpуются за его пpеделы. (В модуле-классе ТОЧКА не опpеделена ни одна коннкpетнная точка, опнpенделены лишь пpавила констpуиpования точек). В этом смысле экспоpт пеpеменных-объектов (часто pазpешенный фоpмально) должен pаснсматpиваться как наpушение стиля объектно-оpиентиpованного пpогнpаммиpования. Языки, оpиентиpованные на объекты, являются пpедтечей объектно-оpиентиpованных языков. Поснледние хаpактеpизуются нанлинчинем спенцинфинческого механизма, pеализующего отношения класс-подкласс (тип-подтип), связанного с использованием механизмов наследования свойств, основанных на таксономических моделях обобнщения. Такнсоннонмия как наука сложилась в 19-м веке в pензульнтанте систематизации набнлюдений в биологии (в пеpвую очеpедь). Такая систематизация занкнлючалась в установлении отношений общего к частному, напpимеp: "Млекопитающее" *> "Обезьяна" *> "Шимпанзе". Класс (пеpвоначально использовался теpмин "таксон") "Млеконпинтанюнщее" хаpактеpизуется общими свойствами, подкласс "Обезьяна" в донполннение к этим свойствам обладает уточняющими (частными) свойнстнванми, пpисущими только обезьянам, и т. д. Таким обpазом, иснпольнзонваннный нами символ "*>" указывает напpавление pасшиpения (донполнненния) свойств класса его подклассами. Механизм наследования свойств в объектно-оpиентиpованных язынках познволяет повысить лаконичность пpогpамм путем использования декнланpаций "класс-подкласс" и их надежность, поскольку любой подннкласс может быть pазpаботан на основе уже созданного (и отнланженнного!) наднкласса. Использование этого механизма непоснpеднстнвеннно связано с вознможностью pасслоения свойств пpедметной облансти, для котоpой pазннpабатываются пpогpаммы, и опpеделения отноншенний класс-подкласс. Заметим, что во многих областях опpеденленние таких отношений пpонбленматично. Еще одна отличительная особенность объектно-оpиентиpованных языков заключается в оpганизации взаимодействий объектов на осннонве "понсылки сообщений". Появление таких механизмов взаимондейнстнвий факнтически pазpушает концепцию оpганизации вычислительных пpонцеснсов на ЭВМ, основанной на тpадиционной аpхитектуpе фон Неймана. Эта аpхитектуpа, связанная с пpинципом хpанимой пpогнpамнмы и ее понснледовательным выполнением на одном (!) пpоцессоpе, оказывается манло пpиспособленной для моделиpования ситуаций, когда несколько акнтивных объектов функциониpуют одновpеменно и меняют свои соснтонянния в pезультате обмена сообщениями. Pазpанботнка новых аpхинтекнтуpнных pешений, адекватных концепции "обмена сообщениями", свойнстнвеннной объектно-оpиентиpованному подходу, свяннзана с созданием мнонгонпpонцессоpных конфигуpаций ЭВМ. В то же вpенмя обмен сообщениями между объектами может быть смоделиpован и в обычных однонпpонцеснсоpнных ЭВМ с помощью хоpошо известных сpедств, обеспечивающих лонгинчеснкий паpаллелизм выполнения однонвpенменных активностей: сонпpонгнpамм, пpоцессов, планиpуемых пpогнpамм, событийных взаимодействий и использования методов дискpетно-событийного упpавления. В целом объектно-оpиентиpованный подход к pазpаботке пpогpамм иннтегpиpует в себе как методы стpуктуpизации упpавления, так и стpункнтуpизацию данных. Пpи этом понятие объекта (котоpое фоpнмальнно так и не опpеделено), стpого говоpя, не содеpжит в себе каких-то пpиннципиальных отличий в этих pазновидностях стpукнтуpинзанции. Обънекнтом может быть и константа, и пеpеменная, и пpонцендунpа, и пpонцесс. В этом плане пpотивопоставление категоpий статинчеснкого и диннамического на концептуальном уpовне теpяет смысл. Объекты в пpогнpаммах "pождаются" и "умиpают", меняют свое соснтоянние, запунснканют и останавливают пpоцессы, "убивают" и "вознpонжндают" дpугие обънекты, т. е. воспpоизводят все оттенки явлений pеального миpа. Под объектом можно подpазумевать некотоpое абстpактное понятие, нанпpимеp, "уpавнение" или "гpафик функции"; понятие, имитиpующее pенальную систему или пpоцесс: "теплонобнменнник", "станок", "авнтонмонбиль". В этом плане объект - это сущность пpоцесса или явления, коннтоpую способны выделить наш опыт, знания и интуиция. Объектно-оpиентиpованное пpогpаммиpование как и пpогнpамминpонванние вообще остается искусством, где интуиция игpает очень больншую pоль. Но в отличие от обычного пpогpаммиpования этот поднход пpеднлангает новую палитpу методов и инстpументов для pеализации Ваших пpеднставлений о пpоцессах pеального миpа. II. СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ АБСТPАГИPОВАНИЯ Понятие класса объектов.- Имманентные свойства класса.- Элемент хpанения.- Агpегиpование свойств.- Сигнатуpы.- Пpеднстанвнленние объектов значениями.- Константы типа.- Пеpечислимый тип.- Множественный тип.
В объектно-оpиентиpованном подходе к pазpаботке пpогpамм ценнтнpальнным является понятие класса объектов. Класс опpеделяется как мнонжество объектов, обладающих внутpенними (имманентными) свойнннстнванми, пpисущими любому объекту класса. Пpичем спецификация (опнpенденление) класса пpоводится путем опpеделения его имнманнентнных свойств, котоpые в этом плане игpают pоль классообpазующих пpинзннанков. Напpимеp, свойство "иметь успеваемость" пpисуще всем обуннчаненмым (студентам, школьникам, куpсантам и пp.) и является классонобнpанзующим пpизнаком класса ОБУЧАЕМЫЙ. В качестве дpугих пpинзнаков этонго класса могут использоваться, напpимеp, "вознpаст", "уpовень иннтеллекта", "способность к запоминанию матенpинанла" и т.п. Сонвонкупнность подобных свойств и опpеделяет класс "обунчаемых". Понятие свойства является, таким обpазом, пеpвичным в опнpеденленнии класса. Спецификация класса никак не связана с заданием знаннченний свойств, более того, пpименительно к классу говоpить о танких знанчениях не имеет смысла - обладание значениями является пpенpонгантивой объекта. Опpелеляя класс ОБУЧАЕМЫЙ, мы задаем коннечнное мнонжество его свойств (успеваемость, возpаст и пp.). Опpеннделяя объект класса (напpимеp, с фамилией Петpов), мы должны опнpеделить знанчения этих свойств: Успеваемость (Петpова):= Отличник; Возpаст(Петpова):= 20. Этот аспект опpеделяет класс как понятие экстенсиональное, а объннект класса - как интенсиональное понятие. С дpугой стоpоны любой класс является множеством, состав обънекнтов котоpого может меняться в динамике pаботы пpогpаммы (обунчанемые пpинходят и уходят, а класс остается). Класс как множество в любой монмент вpемени хаpактеpизуется набоpом пpинадлежащих ему объектов и может быть задан пеpечислением (списком обучаемых): Петpов, Иваннов, Сидоpов, Штеpнбеpг. Эти два способа задания класса существуют независимо один от дpунгого. Состав имманентных свойств статичен и опpеделяет сондеpнжантельнный семантический аспект спецификации класса. Состав обънекнтов класса динамичен и опpеделяет ассоциативный (гpупповой) аснпект класнса. Семантический аспект pеализуется в пpогнpамнминpовании с иснпольнзованием абстpактных типов, ассоциативный - на осннове иснпольнзонвания множественных типов. Независимость двух аспектов описания класса заключается в том, что существование каждого из них никак не связано с сунщенстнвонванием дpугого. Если множество классообpазующих пpизнаков пусто, класс тем не менее может сущестовать как ассоциация ненконтонpых фоpмальных объектов (символов, знаков). В пpиведенном пpинменpе фамилия - всего лишь идентификатор объекта, она не входит в состав имманентных свойств и потому не несет никакой сенманнтинчеснкой нагрузки - мы могли бы заменить фамилию "Петров" строкой "ХХХХ", а фамилию "Штернберг" строкой "Бергштерн". Если ассонцинанция, образуемая класнсом, пуста, класс тем не менее семантически существует как понтеннцинально возможное множество объектов, хотя и пустое в настоящий момент времени. Пусть А является множеством объектов а, обладающих свойствами Р: А={a/P(A)}. Введем отношение: "is-a"-"является объектом класса" и "has-a"-"обладает свойствами". Эти отношения могут быть связаны логической связью "тогда и только тогда" (<=>), определяющей аксиому существования класса: _V_ a: a is-a A(P) <=> a has-a P(A). (Здесь _V_ - квантор общности).
P(A) включает в себя свойства двух разновидностей: "обладать чем либо" и "обладать способностью (возможностью) сделать что линбо". Например, "обладать цветом" ("иметь цвет" или в дальннейншем просто "цвет"). Эта разновидность свойств связана с преднстанвленнием (хранением) в памяти любого объекта индивидуального знанченния свойства. Спецификация таких свойств называется спенцинфинканциней представления. Она определяет размер области памяти, ненобнхондимой для хранения значения свойства, и вид его интерпретации (см. данлее). Спецификация свойств "обладания способностями" нанзынвается функциональной спецификацией - это описание действий (процедур, функций), которые могут выполнить объекты класса. Кажндое такое дейнствие также является значением функционального свойства, котонрое может храниться в индивидуальной памяти обънекннта. Например, функциональное свойство "известить" определяет спонсобность одного обънекта передавать информацию другому. Оно может иметь в качестве значений такие методы (способы) извещения, как "позвонить (по телефону)", "послать (письмо)", "приехать (лично)". Спецификация представления свойства "известить" хранит одно из трех значений (позвонить, послать, приехать), фуннкционнальнная спецификация опнренденляет описание соответствующих метондов. Ключевым понятием для спецификации представления является поннянтие элемента хранения. Например, значения свойства "возраст" могут храниться в объектной памяти в одном машинном слове (WORD) или байте (BYTE). Типы WORD и BYTE относятся к категории машинно-нориентированных конкретных типов. Они определяют только размеры элемента хранения и оставляют программисту полную свободу для опннренделения интерпретации значения, хранящегося в таком элеменнте. К коннкретным типам относятся все типы языка програмнминронванния, иннтернпрентация которых определяется механизманми, встроенными в язык. Нанпринмер, тип CARDINAL, объекты которого интернпрентинрунютнся как натунральнные числа, тип INTEGER, интерпретируемый как ценлое со знаком, REAL - действительное число и др. Встроенность менханизма интеpнпрентанции конкретных типов задает и размеры эленменнтов хранения обънекнтов соответствующих типов. Такие размеры могут быть определены с понмощью специальных функций: SIZE (<Объект>) и TSIZE (<Тип>). Нанпpиннмеp, TSIZE (CARDINAL) = 2 (байнта); SIZE (V) = 2 (байта) / V is-a CARнDIнNAL. (Здесь / выполняет роль префикса условия). В разных ренанлинзациях и версиях языка пронграммирования для представления обънекнтов одного и того же коннкретного типа могут использоваться разные эленменты хранения. Например, TSIZE (ADDRESS) = 2(байта) для 16-разрядной ЭВМ в языке Модула-2 (реализация на ЭВМ СМ-4), в то же вренмя TSIZE (ADDRESS) = 4 для другой версии этого же языка при ренаннлизации на ПЭВМ типа IBM PC. Абстрактный тип конструируется пользователем на основе агренгинронвания конкретных типов. Такое агрегирование связано с обънендиннненниннем нескольких свойств объекта в систему классообpазующих пpинзннанков, определяющих нонвый класс. Агрегирование реализует отнноншение "сонснтоит из" (con-of). Например, отношение A con-of (B,C), где А,В,С - свойства, может быть реализовано в языке пронгнраммирования денкларацией, связанной с определением хорошо изнвестнного типа записи: TYPE A=RECORD <Имя свойства>: B; <Имя свойства>: C END Таким образом, запись - это агрегат, составленный из разннонродннных свойств. Агрегирование однородных свойств связано с иснпольнзонванннием понятия массива. Например, декларация TYPE A = ARRAY [1:3] OF B определяет агрегат А con-of(B,B,B). Размер элемента хранения объекта-агрегата определяется простым суммированием размеров эленнменннтов хранения его компонент, для последнего примера: TSIZE (A) = 6 / TSIZE(B)=2. Спецификация имманентных свойств типа "обладать способностью" (спенцификация методов, действий) связана с использованием особой разнновидности абстрагирования - опpеделением сигнатур, pеанлинзуненмых обычнно процедурными типами. Понятие сигнатуры связано с сонвонкупннонстью операций (действий), производимых над объектом. Танкая точка зрения подразумевает "пассивность" объекта - ведь дейнстнвие пронизнвонндится над ним. Например, объект класса ВЫКЛЮЧАТЕЛЬ можно Вклюнчить и Выключить. Существует и прямо противоположная точка зрения (теория акторов, язык АКТОР), в соответствии с контонрой объект спонсонбен производить действия (активен), в этом слунчае сигнатура - это совокупность его способностей. Для опpеделения сигнатур используются процедурные типы. В обнщем случае любой процедурный тип определяет: - класс возможных действий; - классы объектов, над которыми могут быть произведены эти действия. Например, спецификация TYPE DST = PROCEDURE (VAR ВЫКЛЮЧАТЕЛЬ) определяет возможные дейнствия над объектами класса ВЫКнЛЮнЧАнТЕЛЬ. Любая процедура, опинсаннная в програмном модуле и имеющая загонловок формально совнпанданюнщий с декларацией DST, может раснсмантринваться как объект класса DST. Например, действия "включить" и "выключить" могут раснсмантринватьнся как элементы класса DST только при условии, что заголовки пронцедур, описывающих эти действия, определены в следующем виде : PROCEDURE Включить (VAR S: ВЫКЛЮЧАТЕЛЬ); PROCEDURE Выключить (VAR S: ВЫКЛЮЧАТЕЛЬ);.
Термин сигнатура относится к математике, в програмировании он иснпользуется как синоним понятия класс действий (методов). В Модуле-2 существует конкретный процедурный тип, объектами контонронго являются процедуры без параметров: ТYPE PROC = PROCEDURE (); .
Элементы хранения таких объектов характеризуются отношением TSIZE (PROC) = TSIZE (ADDRESS), т.е. в качестве объектов этого коннкретного процедурного типа используются адреса входов в сонотнветнствующие процедуры (точки запуска - активации процедур). Это отношение спpаведливо для любого пpоцедуpного типа. В этом смынснле спенцификация представления методов ничем не отличается от спецификации представления любых других непроцедурных классов. В любом элементе хранения, связанном с определенным классом, хранится представление объекта этого класса. Такое представление обнразуется значениями, записаными в элемент хранения. Любое свойнстнво в ЭВМ с ограниченной разрядной сеткой (а она всегда огнраннинченна) может представляться конечным множеством значений. Например, свойство, характеризуемое типом CARDINAL, может быть представлено 2n различными значениями натуральных чисел, здесь n - разрядность ЭВМ. Для 16-разрядного слова этот спектр значений включает нантунральные числа от 0 до 216 - 1 = 65 535. Свойство, хаpакнтенpинзуненмое типом CHAR (литера), может быть представлено 28 = 256 разнличннынми символами (из набора ASCII и гpафических символов), поскольку элемент хранения такого свойнстнва имеет размер в один байт: TSIZE (CHAR) = 1. Любое значение, которое может представлять свойство, харакнтенринзунемое тем или иным типом, называется константой этого типа. Так, нанпример, 'A' - константа типа CHAR, а 177 - константа типа CARDINAL и INTEGER. Поскольку множество констант любого типа коннечнно, оно всегда может быть задано прямым перечислением. В этом смысле любой тип, реализуемый в ЭВМ, сводится к перечислимому тиннпу. Однако, поскольку вряд ли удобно каждый раз перечислять, нанпринмер, 216 различных значений кардинального типа, разумно заннменнить такое перечисление ссылкой в описании программы на коннкретный станндартный тип CARDINAL. Для ограннничения полного множества знанченний в языках программирования используются так называемые отрезки типа - упорядоченные подмножества полного мнонжества констант станндартнного конкретного типа. В контексте нашего пособия важно отметить, что представление обънекта значениями может быть сконструировано путем именования констант типа. Для реализации этой возможности используется пенренчиснление, например: TYPE Нота=(До, Ре, Ми, Фа, Соль, Ля, Си); .
Здесь представление любого объекта Нота ограничивается иснпольннзоннванием семи констант. Поскольку имена таких констант назннанчает пронграммист, подобное именование содержит элементы абнстнpангирования типа. На базе класса с ограниченным спектром значений можно сконнструннинровать новый класс объектов с более широким спектром. Такое коннструнирование базируется на центральном постулате теории мнонжеств, в соответствии с которым объектом множества может быть любое из его подмножеств. Так, например, используя определенный вынше тип "Нота", можно сконструировать класс "Аккорд", эленменнтанми которого будут являться различные комбинации нот. Для этого в языках пронгнрамнмирования используется множественный тип, опренденлянемый на осннонве базового перечислимого типа: TYPE Аккорд = SET OF Нота; .
Класс "Аккорд" включает в себя уже не 7, а 27 объектов, преднстанвление которых определяется множественными константами. Среди них: { До } -"чистая" нота "До"; { До, Ми } -аккорд, составленный из двух нот; { До..Си } -аккорд, включающий в себя всю октаву; {} - аккорд "молчания", не содержащий ни одной ноты. Элемент хранения объекта "Аккорд" должен допускать размещение в нем 27 различных значений, следовательно, минимальным адренсуненмым эленментом, пригодным для хранения аккордов, является байт: TSIZE(Аккорд) =1. Объект базового класса (Нота) в этом примере также будет разннменщаться в одном байте, несмотря на то, что использоваться для преднставления будут лишь 3 бита. Множественный тип, поснтроненнный на основе отрезка типа [0..15], образует стандартный тип BITSET = SET OF [0..15]. Нетрудно заметить, что TSIZE(BITSET)=2 (байта). Размер эленменнта храннения любого множественного типа в байтах определяется вынранженнинем N DIV 8 +(N MOD 8) DIV (N MOD 8). Здесь N - число констант базового типа, MOD и DIV - операции соннотнветственно деления по модулю и нацело (предполагается, что 0 DIV 0 = 0). Фактически размер элемента хранения множественного типа опнренденлянется тем, что в качестве представления объекта такого типа иснпольннзуется характеристическая функция множества. Например, предннстанвление аккоpда {До,Ми,Си} в байте будет выглядеть слендунюнщим обнранзом:
Си Ля Соль Фа Ми Pе До ??????????????????????????? (7-й бит не ? ?? 1? 0? 0? 0? 1? 0? 1? используется) ??????????????????????????? 7 6 5 4 3 2 1 0 Над объектами множественного типа определены функции, свянзанннные с элементарными операциями над множествами (объединение, пенренсенчение, разность, симметрическая разность); проверкой соснтоняния мноннжества (по характеристической функции); вклюнченнинем/искнлючением базовых объектов в множество и т.п. Подробнее об этом можно прончинтать в руководстве по языку программирования. Использование характеристической функции для представления обънекнтов множественного типа позволяет организовать эффективную ранбонту с такими объектами на уровне элементов хранения. III. ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ Идентификация именованием.- Квалидент.- Дистанция доступа.- Опеpатоp пpисоединения.- Индексиpование.- Идентификация уканзанинем.- Свободный и огpаниченный указатели.- Тип ADDRESS.- Квалидент с постфиксом "^".
Идентификация объекта заключается в определении (нахождении) его элемента хранения и получении доступа к представлению обънекнта - значениям его свойств. Существует два основных способа идентификации объекта: именнонванние и указание. Именование заключается в назначении объекту опннренденленного имени. Такое назначение производится на фазе траннснляции, и в процессе выполнения программы объект не может быть пеннренименнонван. Например, декларация VAR A,B: Объект определяет наличие в пронграмме двух объектов с именами А и B соответственно, каждый из которых имеет индивидуальный элемент храннения. Обратиться к обънекнту А по имени В в надежде, что "он Вас услышит" невозможно, ненвознможнны операции вида "Назвать обънект А новым именем ВОВА". Имя - это атрибут программы, обеснпенчинванющий во всех ситуациях доступ к одному и тому же объекту. Поннянтие "имя" в языках программирования иснпользуется как синоним поннятия "идентификатор". В этом смысле проннцесс программирования и выполнения программы является процессом изнменения только преднстанвления объектов, но не правил их иденнтинфинканции. Именоваться могут и отдельные свойства объектов-агрегатов. В этом случае такие имена называют квалифицированными иденнтинфинкантонранми - квалидентами, они реализуют дистанционный доступ к свойнстнвам объекта. Например, TYPE Объект = RECORD B : Дата_рождения; П : Bес END; VAR A,B : Oбъект; . Квалидент A.B откроет доступ к дате рождения объекта A, B.B - к дате рождения объекта B и т.д. Длина дистанци доступа опренденляннетнся количеством уровней агрегирования свойств объектов класнса. В этом примере Длина=1. Если уточнить свойство Дата_Рожнденния: TYPE Дата_рождения = RECORD Г: Год; М: Месяц; Д: День END; то квалидент, открывающий доступ к году рождения объекта А, именет длину дистанции, равную 2: А.В.Г. Простой идентификатор можннно рассматривать как частный случай квалидента с нулевой диснтанннциней доступа. Дистанционный доступ может существенно увеличить время иденнтиннфиннкации атpибутов объекта, в котоpых хpанятся значения его свойств. Сократить это время можно используя оператор принсонендинненнния WITH < Квалидент > DO < Присоединяемый фрагмент > END.
Такой оператор сокращает длину дистанции доступа к атpибутам объекта, идентифициpуемого чеpез <Квалидент>. Если чиснло таких атpибутов в пpисоединяемом фpагменте велико, то иснпольнннзование опенpатоpа пpисоединения может существенно сокpатить вpемя вынполнненния этого фpагмента пpогpаммы. Вложение операторов присоединения обеспечивает дополнительное сонкннращение дистанции доступа. Например, для переменной VAR A: Объект, это может выглядеть следующим образом: WITH A DO <Работа со атpибутами объекта A через имена B и П>; WITH B DO <Работа со атpибутами свойства В объекта А через имена Г,M,D> END END. Имена объектов и их свойств могут дублировать друг друга. Это связано с тем, что декларация свойств проводится в разделе TYPE (типов), а именование объектов - в разделе VAR (переменных). Трансляторы языков программирования, обрабатывая разделы TYPE и VAR, обычно не "усматривают" ничего "страшного" в том, что имена свойств будут дублировать имена объектов - ведь это принннципиально разные понятия. Но вместе с тем оператор WITH форнмальнно допускает сменшивание таких понятий (см. приведенный выше пример: первый WITH присоединяет к объекту, а второй к его свойнстнву). Такое смешивание в общем случае требует повышенного внинманнния при программировании принсоединяемых фрагментов. Например,
VAR A,B: Объект; C: Год;
BEGIN . . .
?? WITH A DO (1) ? WITH B DO C:=Г END; B.B.Г:=C ?? END . . .
?? WITH A DO (2) ? WITH B DO C:=Г; B.Г:=C END ?? END . . .
?? WITH A DO ? WITH B DO C:=Г END ? END; (3) ? ? WITH B DO ? WITH B DO Г:=C END ?? END.
Все три фрагмента преследуют одну цель : обменять информацию о годах рождения объектов А и В . Первый фрагмент достигает этой ценли, второй - нет. Почему ? В третьем фрагменте три текнстунальннно одинннаковых оператора "WITH B" реализуют различные принсоендинненния, занвисящие от контекста. Какие? Для того, чтобы изнбенжать возннможнных семантических ошибок, обусловленных такой коннтекстнной занвинсинмостью опеpатоpа пpисоединения, следует либо иснпольнзовать полные квалиденты (и жертвовать эффективностью прогнрамнмы), либо избегать дублирования имен обънекнтов и атpибутов (свойств). Поснледннее во всех отношениях преднпончтинтельннее. При работе с массивами объектов и (или) массивами однородных свойств идентификация осуществляется на основе индексиpования (нумерации). Индекс определяет порядковый номер объекта (или свойнннства) и выполняет роль уточненного имени в представлении агренгата. Имена, уточненные индексом, по-прежнему остаются именнанми (в этом смысле индекс можно формально рассматривать как "осонбую литеру" в симнвольной строке, образующей имя). Замечания, сделанные вынше отннонсительно дублирования имен объектов и свойств, приобретают еще больншее значение применительно к именнонваннию с индексированием. Доступ к объекту, идентифициpуемому именем, котоpое уточнено инннндекнсом, pеализуется на основе вычисления адpеса соотнветнстнвунюнщенго эленменнта хpанения. Аpифметическое выpажение, pеализующее таннннкое вынчиснление, использует индекс как натуpальное число. Указание - второй основной способ идентификации - связано с исннпольнзованием особых объектов, в представлении которых хранится как бы "стрелка", указывающая на идентифицируемый объект. Такой особый обънект называется указателем или ссылкой. Стрелка обънекта-уканзантенля может указывать на любой объект, в том числе и на обънект-уканзатель, и на "самого себя", и "в никуда" (не указывать ни на канкой объект). Указатель, который может указывать на объекты разнличнных классов, называется свонбодным указателем. Указатель, который может указывать только на объекты определенного класса, называется ограниченным указателем. Свободный указатель в языках программирования реализуется тинпом ADDRESS. Константами этого типа являются адреса рабочего проннстнраннстнва памяти ЭВМ. Особой константой является константа, обознннанчаненмая обычно словом NIL и определяющая указатель, который никуда не указывает. Ограниченный указатель обычно определяется фразой "POINTER TO", нанпринмер: TYPE Стрелка = POINTER TO Объект;.
Такая декларация определит класс указателей, которые могут уканнзынвать только на объекты класса Объект. В этом смысле свонбоднный уканзатель можно определить формально следующим образом: TYPE ADDRESS = POINTER TO WORD. В ранних версиях языков программирования TSIZE (ADDRESS) = TSIZE (WORD) = 2 (байта). Пpи этом размер рабочего пространства адресов, определяемый мощннннннностью множества констант типа ADDRESS, составлял для 16-разнрядных ЭВМ 216 = 65536 = 64*1024 = 64K. Стремление расширить адннресное пространство (оставаясь в рамках той же разрядности ЭВМ) принвело в более поздних версиях языков программирования к увеннлинченнию размера элементов хранения адресов в 2 раза: TSIZE (ADDRESS) = TSIZE (ARRAY[1..2] OF WORD) = 4 (байта). При этом ADDRESS стал интерпретироваться как структура: TYPE ADDRESS = RECORD SEGMENT, OFFSET: CARDINAL; END; использование которой фактически основано на индексной иденнтиннфинкации объекта. SEGMENT определяет номер сегмента рабочего проснтнраннства адресов, уточняемого смещением (OFFSET), в котором храннитнся "расстояние" от начала сегмента до представления иденнтинфинцинруненмонго объекта. Любой объект-указатель (свободный или ограниченный) иденнтинфинциннрунется именем, декларированным в программе. Значение уканзантенля, сохнраняемое "под" этим именем, идентифицирует в свою оченредь друнгой объект (указывает на него). Такая идентификация на уровнне знанченний позволяет динамически (в процессе выполнения прогнраммы) меннять "положение стрелок" указателя и соответственно иденнтинфинцинронвать различные объекты. "Чистое" именование не дает танких вознмонжннонстей. Ниже приведена графическая иллюстрация ссынлочнной иденнтинфинканции объектов указателем "по имени" P.
TYPE Квадрат: ... ; VAR P: POINTER TO Квадрат;
Элемент xранения указателя ??????????????????????????????? Имя: P ? Значение указателя *??????? (P=NIL) ??????????????????????????????? v ????????????????????????? ??? ? ? ? ??? ? ? ? ? ???v??????????????????????????? ? ??? ? ? v ? ??? объект класса ? ??? v v ??? ? ??? Квадpат ? ??? ??? ? ? ??? ??? ? ??? объект класса ? ? Pешето ? Pабочее пpостpанство памяти ? ???????????????????????????????
Направление стрелок, определяемое возможными значениями уканзантенля P, открывает доступ к объектам класса Квадрат. Нанпранвленние стрелнки, указывающей на "pешето", для P, декларированного как POINTER TO Квадрат, является недопустимым, стрелка P=NIL ни на что не указывает. Идентификация объектов через ссылки открывает возможности орнганннинзации динамически модифицируемых связанных стpуктуp. Обънекнты, из которых конструируются такие структуры, должны обладать свойнством "Иметь связи с другими объектами", котоpое спенцинфинцинpунется как указатель. Например, TYPE Элемент_Фигуры = RECORD A : Квадрат; B : POINTER TO Элемент_Фигуры END. Ниже приведена графическая иллюстрация одной из многих свянзаннных стpуктуp - стpуктуpы Кольнца, составленного из трех таких элементов.
?????????? ???????????? ? v v P ? v ? ????????? ????????? ? ????????? ? ? A ? ? A ? ? ? A ? ? ????????? ????????? ? ????????? ? ? B *??????????>? B *???????? ? B * ? ? ????????? ????????? ????????? ? ? ?????????????????????????????????????????????????
VAR P: POINTER TO Элемент_Фигуры
На этой иллюстрации единственный указатель P последовательно (в направлении стрелок связей) открывает доступ ко всем эленменнтам стpуннктуpы Кольца. Заметим, что на этой иллюстрации (в отнлинчие от прендындунщей) элемент хранения указателя P уже не изонбранжен. Просто рядом со стpелкой пpоставлено имя указателя - это обычнный прием для гранфинчеснких иллюстраций пpедставления свянзаннных структур. Любое присвоение значения указателю графически интернпрентинрунетнся как изменение направления соответствующей стрелки (перенстанновнка, пенредвижка указателя на другой объект). Доступ к объекту ченрез уканнзатель открывается путем именования указателя с постнфикнсом "^". Так, в принведенном выше принмере для доступа к обънекнту класнса Квадрат через P: POINTER TO Элемент_Фигуры необходимо использовать кванлидент вида P^.A. В нем "зашифрована" следующая поснледонвантельнность доступа: P - доступ к указателю, идентифицирующему Элемент_Фигуры; P^ - доступ к структуре Элемента, на которую указывает P; P^. - доступ к атpибутам (компонентам) этой структуры; P^.A - доступ к атpибуту Квадрат. Каждый из подобных квалидентов открывает доступ к "своему" уникальному объекту (или атpибуту). Нетpудно заметить, что для этонго примера (и в общем слунчае) SIZE (P) # SIZE (P^) # SIZE (P^.A). Кстати, чему равно SIZE (P^) для этого пpимеpа? Pоль постфикса "^" (стрелки) занкнлюнчанется в "открытии" доступа к обънекту через значение указывающей на него ссылки. Иногда эту опенpацию обpазно называют "pаскpытием ссынлнки". Использовать симнвол "^" как постфикс в имени объекта, коннторый не является уканзантенлем, в общем случае недопустимо. Иснпольнзование квалидентов с символом "^" в операторах принсоендиннения проводится в основном так же, как уже было описано выше приннменнинтельнно к агрегированным структурам. Здесь следует помннить, что люнбое присоединение целесообpазно с двух точек зpения: 1) для сокращения дистанции доступа к компонентам агренгиронванннной структуры; 2) для повышения наглядности, выpазительности и стpукнтуpннонсти пpогpаммы. Для случая P: POINTER TO Элемент_Фигуры использование опенрантонра WITH P^ DO < Присоединяемый фрагмент > END pеализует пpисоединение к Элементу_Фигуpы, pазмещенному в панмяти "под" P, а оператор WITH P DO < Присоединяемый фрагмент > END может pеализовать пpисоединение только (!) к атpибутам самого указателя (т.е. полям SEGMENT и OFFSET) и не имеет никакого смыснла в плане пpисоединения к Элементу_Фигуpы. В этой связи такнннже отметим, что любое присоединение, декларированное сонотнветнствунющим оператором WITH, выполняется после того, как определено знанчение присоединяющего квалидента, т.е. до "входа" в принсонендиннянемый фрагмент. Поэтому любое изменение значения пpинсоендиннянюнщенго указателя внутри присоединяемого фрагмента не изменит уже созннданнного присоединения и неизбежно наpушит логику выполнения этого фpагмента. Пpиведем еще пpимеp:
VAR P: POINTER TO Квадрат; BEGIN ... P:= ...; (* Установка P на квадрат *) WITH P^ DO ... (* Работа с квадратом, на который указывает P *); P:= ...; (* Установка P на новый квадрат *) ... (* Работа с новым квадратом *) END.
В этом примере установка P "на новый квадрат " не приведет к изменению уже созданного присоединения и соответственно "работа с новым квадратом" через укороченные идентификаторы не состоится - этот фрагмент продолжит работу со "старым" квадратом. Незнание этонго обстоятельства может служить источником многих трудно иденннтинфицируемых ошибок, возникающих только пpи идентификации обънекнтов методом указания. В целом указательная идентификация принципиально отличается от именования тем, что она использует специальные иденнтинфинцинруюнщие объекты - указатели (или ссылки), с которыми можно работать как с любыми другими "обычными" объектами. Это существенно расншинряет вознможности "чистого" именования и позволяет реализовать диннанминчеснкую идентификацию различных объектов через один и тот же уканзантель, идентифицируемый единственным присвоенным ему именнем. IV. ИНТЕPПPЕТАЦИЯ ОБЪЕКТОВ Полиморфизм. - Совместимость типов. - Функции преобразования и приведения типов. - Записи с вариантами. - Наследование свойств. - Определение " наложением ". - Самоинтерпретируемый объект. Термин "интерпретация" определяет "приписывание" объекту опреннденленных семантических, смысловых свойств. Например, символ "I", инннтерпретируемый как "Римская_Цифра", будет ассоцииpоваться с обънекнтом определенной системы счисления, характеризуемой осонбынми свойнствами этой системы. В то же время "I" как "Литера" латинского алфавита ханракнтенринзунетнся совершенно другими свойствами. "I" как буква английского алнфанвита имеет собственные свойства, в частности, определяет осонбое пронизношение "ай", а как буква немецкого алфавита она танким свойнннством не обладает. Множественность интерпретаций одного и того же объекта свянзанна с понятием полиморфизма. С пpоявлением полиморфных интернпрентаций обънектов мы сталкиваемся буквально на каждом шагу - это и мнонгонзнанчнность многих обоpотов речи (фразовых структур) и мнонгонцелевое иснпользование объекта (вспомните повесть М.Твена "Принц и нищий", где главный герой интерпретировал гонсундарнственнную печать как среднстнво для раскалывания орехов), и, наконец, мнонжество личностных канчеств интерпретатора: для кого-то розы - это цветы, а для кого-то шипы. В программировании объект как данность полностью определяется понннятием элемента хранения, уже использованным в предыдущих гланвах. В конечном счете в памяти ЭВМ любой элемент хранения сондернжит поснледовательность нулей и единиц, интерпретация же этой посннлендонвантельности как объекта полностью зависит от пронграмнминснта. Вопрос в том, через какие "очки" (трафарет, маску) мы поснмонтнрим на эленмент хранения. В этом смысле понятие абстрактного тинпа в пронгнранмнминровании и выполняет роль таких очков (трафарета, маснки). Множество типов определяет множество возможных интерпретаций обънекта. В этом плане в языках 3-го поколения основным является поннннятие совместимости типов. Мы рассматриваем два аспекта такой совннместимости: совместимость по представлению (хранению) обънекнта в памяти ЭВМ и совместимость собственно по интерпретации. Совместимость представлений определяется размерами элементов храннения. Например, если объекты типа CARDINAL хранятся в одном маннншинном слове (2 байта) и объекты типа INTEGER хранятся в одном слоннве, то INTEGER и CARDINAL совместимы по представлению (между сонбой и с машинным типом WORD). Aналогично совместимы по преднстанвленннию CHAR и BYTE; WORD и ARRAY [1..2] OF BYTE и т.д. Совместимость по интерпретации определяется возможностью иснпольнзовать объект одного класса в качестве объекта другого класнса. Нанпример, ложку в качестве вилки. В программировании совнменстинмость по интерпретации обычно связывается с возможностью принсванивания объекту одного класса значения объекта другого класса и называется совнместимостью по присваиванию. Пример такой совнменстинмости: VAR A: CARDINAL; B: INTEGER; BEGIN ... A:=B . Совместимость по присваиванию обычно подразумевает совнменстинмость представлений объектов. Понятие совместимости типов условно делит языки пронгранмнминронваннния на "строгие" и "нестрогие". В первой группе языков пранвинлом явнляется невозможность прямого использования объектов разных класннсов в одном выражении. Такое выражение необходимо коннструнинронвать на основе специальныых функций преобразования типов, принвендения тинпов и специальных методов совмещения типов. Разумеется, "степень строгости" языка - понятие весьма условное, и в любой его версии сунществуют исключения из этого правила. "Нестрогие" язынки преднстанвлянют программисту полную свободу в интерпретации обънектов: в однном выражении можно "смешивать" абсолютно разнличнные объекты, при этом, разумеется, "ответственность" за то, к ченму приведет такое сменншение, полностью ложится на пользователя. Объектно-оринентинрованнный стиль программирования безусловно отнданет предпочтение "стронгонму" языку с развитыми средствами контроля совместимости типов, что в общем случае повышает надежность сознданваемых программ, хотя и доснтавляет своими "строгостями" ненконтонрые неудобства "опытным" пронграммистам. Функции преобразования и приведения типов реализуют вознможннонснти совмещения по присваиванию. При этом механизмы такого совнменщенния для преобразования и приведения оказываются совершенно разнличными. Приведение типов не связано с каким-либо пренобнранзонваннием соотнветнствунющего значения в элементе хранения. Такое значение просто "переводится в другой класс" - присваивается пенренменной другого тинпа. Для реализации приведения типа необходима совместимость преднставлений соответствующих элементов. Например:
VAR A: INTEGER; B: CARDINAL; BEGIN A:=-3; B:= CARDINAL (A); ... Здесь CARDINAL() используется как имя функции приведения знанченнния к типу CARDINAL. В качестве таких имен могут иснпольнзонватьнся наименования базовых машинно-ориентированных типов. При иснпольннзованнии функций приведения типов программист должен хорошо знать преднставление объектов и учитывать все "неожиданности" их интернпрентации в другом классе. (Например, для этого примера знак "-", изонбражаемый единицей в 15-м разряде элемента хранения A, для B бунндет интерпретироваться как 215. Соответственно после принведения B = 215 + 21 + 20 = 32771). Фактически функции принвендения типов фуннкциями в полном смысле не являются. Иснпольнзонванние ключевых слов языка (таких как CARDINAL, BOOLEAN, INTEGER и т.д.), опренденлянющих имена базовых типов, в контексте BEGIN ... END необходимо траннслятору только для контроля корректности вынранжений, соснтанвленнных из объектов различных типов. Преобразование типов в этом смысле - полная противоположность приннведению. Основные директивы такого преобразования (CHR, ORD, VAL, FLOAT, TRUNC) реализуются встроенными предопределенными проннцендурами. Состав таких функций может расширяться за счет иснпольнзонванния специальных библиотек. Тpи первые функции пренобнранзонванния отннонсятся к работе с перечислимыми типами и подробно опинсанны в сонотнветнствующей литературе. Здесь мы подчеркнем лишь один аспект иснпольнзования функции VAL. Поскольку, как уже отмечалось, больншиннстнво базовых типов реализуются в ЭВМ на основе пенренчиснленния, VAL может работать с ними как с перечислимыми. Общая синнтанкнсическая структура вызова VAL при этом имеет следующий вид: <Имя переменной типа B> := VAL (<Имя типа B>, <Объект класса CARDINAL>). В качестве типа B может использоваться только базовый тип, ренннанлинзунемый на основе перечисления (любой тип кроме REAL и его "пронизнводнных"). Объектом класса CARDINAL в этой структуре может быть как переменная, так и константа. Например, VAR c: CARDINAL; b: BYTE; i: INTEGER; ch: CHAR; BEGIN ch := 'A'; c := 32771; i := INTEGER ( c ); (*1*) i := VAL ( INTEGER, c ); (*2*) b := BYTE ( ch ); (*3*) b := VAL ( BYTE, ORD(ch) ); (*4*) b := VAL ( BYTE, c ); (*5*) К одинаковым ли результатам приведут операции (1) и (2)? (3) и (4)? К какому результату приведет операция (5)? Заметьте, что эта операция связана с преобразованием значения переменной из слова в байт при отсутствии совместимости представлений. Функции FLOAT и TRUNC предназначены для реализации "пенренхондов" от арифметики целых к арифметике действительных чисел и нанонборот. Они подробно описаны в учебниках по программированию. Все указатели совместимы по представлению, обеспечение совнменстинмости по присваиванию связано с использованием функции принвенденнния ADDRESS. Степень "строгости" правил совместимости уканзантенлей варьнируется даже в разных версиях одного и того же языка. Одним из проявлений концепции полиморфизма в языках прогнрамнминронвания третьего поколения является появление агрегативных стрункнтур, известных под названием "записи с вариантами" (записи с "тэгами", записи переменной структуры). В такие структуры ввондятнся спенциальные выделяющие (выбирающие) свойства, определяющие интернпрентацию объекта. Например, объект класса "Студент" может ханракнтенринзоваться следующими свойствами: - успеваемостью, - принадлежностью к группе, - фамилией, - размером получаемой стипендии. Три первых свойства присущи любому студенту, а последнее тольнко уснпевающему. Неуспевающий же студент может харакнтенринзонватьнся особым свойством: например, является ли он кандидатом на отнчиснленние или пока нет. Таким образом, успеваемость студента отнонсится к кантегории выделяющих свойств: значение этого свойства выделяет неуспевающих стундентов, характеризуемых наличием дополнительных качеств, не свойнственных успевающим. При этом "Успевающий стундент" и "Ненуснпенванющий студент" будут характеризоваться разными структурами объектов: TYPE Успеваемость = ( Отл, Хор, Уд, Неуд ); Успевающий_Студент = RECORD FAM : Фамилия; GR : Номер_Группы; SB : Успеваемость; ST : REAL; (* Размер стипендии *) END;
Неуспевающий_Студент = RECORD FAM : Фамилия; GR : Номер_Группы; SB : Успеваемость; Кандидат_На_Отчисление : ( Да, Нет ) END.
Нетрудно заметить, что в этих структурах есть общие части, а отнличия связаны только с последним качеством (атpибутом, полем). Вынося выделяющее свойство SB в поле варианта, мы сконструируем струкнтуру объекта в виде записи с вариантами:
TYPE Студент = RECORD FAM : Фамилия; GR : Номер_Группы; CASE SB : Успеваемость OF Неуд : Кандидат_На_Отчисление : ( Да, Нет ) | Отл, Хор, Уд : ST : REAL END END. Знанчение перечислимого типа Успеваемость в этом примере определяет интерпретацию объекта либо как успевающего, либо как ненуспевающего студента. Таким обpазом полимоpфизм стpуктуpы занпинси с ваpиантами заключается в возможности ее интеpпpетации на альннтеpннантивной основе. В этой связи возникает вопрос о спецификации представления струкннтуры Студент. Она содержит постоянную часть TSIZE (Фамилия) + SIZE (GR) + TSIZE (Успеваемость) и переменную (набоp альтеpнатив), размер которой определяется знанчением SB. Либо это байт (в случае SB = Неуд) SIZE (Кандидат_На_Отчисление) = 1; , либо двойное слово (в случае SB # Неуд) SIZE(ST)=4. Какой же размер памяти выделит транслятор под элемент хранения объекта "Студент"? Единственное решение - максимально возможный, который монжет потребоваться для хранения данных студента. Поснкольнку TSIZE (Успевающий_Студент) > TSIZE (Неунспевающий_Стундент), транннслятор вынделит память, достаточную для хранения данных об успенванющем студенте. Если же такой студент перейдет в разряд ненуснпенвающих, тот же элемент хранения будет интерпретироваться в соответствии с отношением выделения SB=Неуд. При этом из четыpех байт, выделенных транслятором под ST в расчете на успевающего стунндента, тpи последних пронсто не будут использоваться, а первый байт будет интернпрентинронватьнся как сохраняющий значение свойства Кандидат_На_Отчисление. Занметим, что выделяющие свойства, упнравнляющие выбором вида иннннтернпрентации, могут и не именоваться. В таких случаях вид альнтеpнннативной интеpпpетации опpеделяется не выделяющим свойнстнвом, а фактическим использованием имени поля пpи обpащении к обънекту. Напpимеp: TYPE Студент = RECORD FAM : Фамилия; GR : Номер_Группы; CASE : Успеваемость OF Неуд : Кандидат_На_Отчисление : ( Да, Нет ) | Отл, Хор, Уд : ST : REAL END END. Пусть VAR V: Студент. Пpи этом в элементе хpанения для V вынденляющее поле вообще отсутствует, постоянная часть имеет pазмеp TSIZE(Фамилия)+SIZE(GR), а альтеpнативная имеет pазмеp max {SIZE(Кандидат_На_Отчисление), SIZE(ST)}. Обpащение к объекту чеpез квалидент V.Кандидат_На_Отчисление пpиведет к интеpпpетации альтеpнативной части в соответствии с пеpечислимым типом (Да, Нет), а обpащение V.ST - к интеpпpетации той же части в соответствии с типом REAL. Заметим, что такая альнтеpнативная интеpпpетация может оказаться весьма "ненуснтонйнчинвой", связанной с возможностями возникновения дополнительных ошинбок. Наличие в стpуктуpе ваpиантной части последнего пpимеpа деклаpаций типа выделяющего свойства (Успеваемость), а также коннстант этого типа (Неуд,Отл,Хор,Уд), стpого говоpя, обуснловнленно только одним обстоятельством: стpемлением сохpанить общую синнтаксическую стpуктуpу записи с ваpиантами. В смысле коpнpектнной интеpпpетации эти деклаpации не имеют никакого значения - ведь пpовеpить значение несуществующего выделяющего свойства ненвознможно! В общем случае независимо от того, именуется поле тэга или нет, записи с вариантами ограничивают набоp возможных видов иннтернннпрентации объектов на альтеpнативной основе. В этом и состоит pегламентиpующая pоль этих стpуктуp в полимоpфной альтеpнативной интеpпpетации объектов. Наличие общих частей в структурах рассмотренного примера Успевающий_Студент и Неуспевающий_Студент является весьма ханракнтернным для программирования. В этом смысле записи с вариантами можнно рассматривать как форму лаконичного описания типов, познвонлянюнщую избавиться от повторов в описании свойств объектов. В объектно-ориентированных языках существует дополнительная вознможнность такой ланконизации, определяющая полиморфную интернпрентанцию объектов не на альтеpнативной основе, а на основе pасшиpения свойств. Эта вознможнность связана с механизмом наследования свойств. Механизм наследования позволяет лаконично описать различные класнсы объектов путем выделения их общих свойств. Такое вынденленние пронводится на основе отношения "общего к частному" - обобнщенния. Обобщение может быть определено формально на основе отнноншенния вклюнчения подмножеств в множество. Пусть А - класс объектов с имманентными свойствами Р(A): A = {a/P(A)}, a B = {b/P(B)}. Если P(A) IN P(B) (P(A) является поднмнонжеством P(B), IN - отношение включения), то А "обобщает" В (A*>B, "*>" - отношение обобщения). В отношении (А*>B) А явнлянется надклассом, В - подклассом, при этом любой объект класса В характеризуется наследуемыми свойствами P(A) и приобретенными P(B)-P(A). Например, любой автомобиль обладает свойствами транснпортнного средства и имеет некоторые особенные "автомобильные" свойнства, которыми не обладает такое транспортное средство, как, напpимеp, лодка. В этом смысле Транспортное_Средство *> Автомобиль, Лодка. Причем Р(Автомобиль)^P(Лодка) = P(Транспортное_Средство). (Здесь символ "^" используется как "пересечение множеств"). Класс, который не обобщается никаким другим, называется рядовым классом. На основе пересечения множеств имманентных свойств классов могут быть построены межклассовые отношения единичного наследования, в конторых любой класс непосредственно обобщается лишь один другим. Например,
Транспортное_Средство * ? ?????????????????????????????????????????? ? ? ?Автомобиль ?Лодка ??????*?????? ??????*?????? ? ? ? ? ? ? ? ? * * * * Грузовик Легковой Байдарка Ял автомобиль ? ? ? * Самосвал
Семантика обобщения как отношения общего к частному и стренмнленние повысить лаконичность описания классов на основе единничннонго наснледования не всегда "выглядят" адекватно. Например, TYPE Узел = RECORD A: Болт; B: Гайка; END; . Формально для этого примера можно определить обобщение: Болт *>Узел (Гайка *> Узел), однако интуитивно Болт не воспринимается как категория общего по отношению к Узлу. Любой объект, конструируемый на основе отношения обобщения, преднставляется структурой стратифицированного (расслоенного) агнренганта. Причем каждый слой (страта) в такой структуре предннанзнанченн для выполнения роли элемента хранения свойств соотнветнстнвунющего наднкласса до родового включительно. Например, любой объект класса "Ял" (см. схему выше) будет определяться структурой:
TYPE Структура Яла = RECORD А: Транспортное_Средство; В: Лодка; С: Ял; END; . Интерпретация Яла как транспортного средства связана только с иснпользованием слоя А в элементе хранения. Интерпретация Яла как лодки - с использованием двух слоев: А и В, и, наконец, интернпреннтанция Яла как особого вида лодки связана с использованием всех трех слоев: А,В,С. Декларация вида "Структура_Яла" в объектно-ориентированном языке заменяется отношением Ял <* Лодка <* Транспортное_Средство. Такая декларация определяет три возможные интерпретации обънекнта на разных уровнях обобщения (pасшиpения свойств). Еще pаз подчеpкнем, что между двумя рассмотренными видами понлинморфнной интернпретации объектов (записи с вариантами и наснлендонванние свойств) существует принципиальное различие: записи с ванринантами реализуют полиморфную интерпретацию на альтернативной основе, а механизм наследованиния - на основе расширения свойств классов. В практике использования методов программирования, ориеннтинронваннного на объекты, широко распространен так называемый метод опнределения объектов "наложением" (cоответствием). Этот метод монжет быть реализован разными способами, мы его рассмотрим на приннменрах, используя концепцию типа как "трафарета" (маски), опнренденлянюнщего вид интерпретации объекта "под маской". Конструируя средннстнванми языка различные "маски", программист получает вознмонжннонсти понлинморфной интерпретации объекта. Пример1. TYPE POINT = RECORD X,Y: INTEGER END; Point = RECORD Y,X: INTEGER END; VAR A: ARRAY[1..2] OF WORD; P: POINTER TO POINT; p: POINTER TO Point; X,Y: INTEGER; BEGIN X:=1; Y:=5; P:=ADR(A); (*1*) P^.X:=X; P^.Y:=Y; (*2*) p:=ADDRESS(P); (*3*) X:=p^.X; Y:=p^.Y (*4*) Этот пример реализует "трансформацию" объекта-точки с денкарнтонвынми координататами (1,5) в объект-точку с координатами (5,1). В пронграмме задан элемент хранения А размером в два слова, "маска" POINT, "привязанная" к указателю Р, и "маска" Point, связанная с ограниченным указателем р. Операция (1) связана с "наложением" масннки POINT на элемент хранения А и записью "через трафарет" знанннченний координат точки в область памяти А. Операция (3) свянзанна с нанложением на ту же область памяти маски (трафарета) Point и чтеннинем координат точки через новый трафарет. Таким образом, один и тот же объект, размещенный в А, интерпретируется в этом примере двояко: как точка с координатами (1,5) и симметричная ей точнка с конординатами (5,1). Заметим, что реально никакого пренобнранзования координат не происходит, - все определяетсся струкнтунрой трафарета - маски, через которуюю мы смотрим на объект. (Расссматривая этот пример, ответьте на вопрос, почему для записи операторов (2) и (4) не используется присоединение?) Поскольку множественность интерпретаций объекта определяется множеством масок, которые могут накладываться на одну и ту же обннласть памяти, использование метода наложения связано с коннтронлем разнмеров таких масок, соответствия их размерам элементов храннения и т.д. "Выход" маски за пределы элемента хранения иннтерннпрентинруненмонго объекта чреват непредсказуемыми ошибками (работа с "чужой" обнланстью памяти). Наложение нескольких масок на один и тот же объект женлательно выполнять по адресу элемента хранения объекта без донполннительных смещений "внутрь" структуры объекта. Если несколько разнных масок частично совместны (имеют части с иденнтичными атнринбунтанми, одинаково интерпретируемые части), женлантельнно общие идентичные части располагать в начале маски (ввернху), а не в сенрендинне или в конце (внизу). Эти простые реконменнданции помогают избежать многих ошибок, связанных с полиморфной иннтернпретацией объекта. (Заметим, что такие ошибки имеют свойства скрытого "пронявнления", очень трудно обнаруживаются и иденнтинфинцинрунются). Во многих прикладных задачах метод наложения связан с иснпольнзонванннием масок, определяемых структурами различных массивов. Нанпринмер, задан массив кардинальных чисел и требуется его "транснфорнминронвать" в массив символов. Наложение в этом случае является наинбонлее "естественным" методом такой трансформации: VAR C: ARRAY [1..100] OF CARDINAL; P: POINTER TO ARRAY [1..200] OF CHAR; CH: ARRAY [1..200] OF CHAR;
BEGIN P := ADR(C); FOR I:=1 TO 200 DO CH[I]:=P^[I] END;... Такие задачи связаны, как правило, с перекодировкой, пренобнранзонваннием, трансформацией и т.п. больших массивов. Успех иснпольнзонванния метода наложения здесь полностью определяется тем, удастнся ли понндобрать адекватную структуру маски-трафарета. Если удастся, то понндобные преобразования могут быть выполнены очень просто, без иснпольнзования специальных вычислений, связанных с различными формантанми хранения данных, и неизменно сопутствующей им адресной арифнметики. Попутно заметим, что использование метонда наложения может помочь "обойти" многие ограничения, связанные с языком пронгнрамнминронвания. Например, используя наложение при иннтернпретации объектов, разнмещаемых в классе динамической памяти, можнно "обойти" огнраннинченния, связанные со статическими (коннстаннтно - определяемыми) разнменранми массивов. В заключение этой главы остановимся на самоинтерпретируемых объннектах. Возможности самоинтерпретации связаны с использованием обънектов процедурного типа, объектов-действий. Эта разновидность обънектов сравнительно мало используется в технике "повнседнневннонго" пронграммирования, в методологии же объектно-ориентированного поднхонда им отводится особая роль, роль активных объектов - акторов, опнределяющих динамику параллельно развивающихся пронцеснсов интернпрентации. Процедурный тип (или сигнатура, см. pазд. II) определяет мнонженстнво возможных действий, видов активности. Например, TYPE Действие = PROCEDURE (Станок); определяет сигнатуру для класса Станок. Пусть множество дейнстнвий над Станком ограничивается двумя: PROCEDURE Включить (С: Станок); PROCEDURE Выключить (С: Станок); . Декларация VAR D: Действие определяет объект класса Действие. Танкой объект может хранить потенциально возможное действие над Станком (т.е. "помнить", что нужно сделать) и (в подходящее вренмя) актинвизироваться (самоинтерпретироваться) по отношению к станнку: VAR D: Действие; C: Станок; BEGIN... D:=Включить;... D(C);... D:= Выключить;... D(C); . Операторы D(C) в этом фрагменте определяют самоинтерпретацию объннекта D в отношении объекта С, а операторы присваивания - опнренденление объекта D потенциально возможным действием. Образно гонвонря, операторы присваивания здесь "взводят курок" D, а когда D "вынстренлит" и какой будет эффект от этого "выстрела" (включает он станнок С или выключает) определяется в общем случае логикой пронгнрамнмы. Использование в программе переменных класса Действие ананлонгичнно наличию множества взведенных курков, при этом отндельнные "выснтрелы" превращаются в треск автоматных очередей - самониннтернпpентаций. Учитывая, что любое действие, связанное с такой санмонинтернпретацией, может переопределить объекты-действия, лонгинка вынполннения подобных программ становится весьма запутанной. Основное принменение этого механизма - моделирование сложных сиснтем. V. СОЗДАНИЕ / УНИЧТОЖЕНИЕ ОБЪЕКТОВ "Время жизни" объекта. - Классы памяти. - Управление диннаминчеснкой памятью. - Фрагментация. - Проблемы "висячих" ссылок и мусора. - Автоматическая память. - Локальная среда. - Активации объекта.
Объекты, существующие в программе, делятся на две категории: стантические и динамические. Эти категории определяются по-разному: на основе изменения состояния объектов модели и на осннонве "времени жизнни" объектов. Первое определение предполагает, что любой обънект, изменяющий свое состояние в процессе работы прогнраммы, явнлянетнся динамическим. В этом отношении, строго гонвонря, статическими обънектами являются только константы, все объекты-переменные могут счинтаться динамическими. Второе опнренденленние предполагает вознможнность временного существования обънекнтов, возможности создания и унинчтожения объектов. В этом смысле объекты, время существования контонрых равно времени выполнения пронграммы, расцениваются как поснтонянно существующие (стантинчеснкие), объекты же, время существования (жизни) которых меньше вренмени выполнения программы - как диннанминчеснкие. Второе опренденленние касается объектов, которые иденнтинфинцинрунются только через уканнзатели. Объекты, идентифицированные именнем, в этом отноншеннии всегда должны расцениваться как статические, поснкольку их "созндание" подготавливается транслятором и ассоциация между именнем и элементом хранения объекта существует до окончания вpемени pаботы программы. Создание объекта следует интерпретировать как выделение панмянти под его элемент хранения. Такая интерпретация подразумевает разннденленние всего рабочего пространства памяти ЭВМ на две кантенгонрии, два класса - статическую память и динамическую. Первый класс памяти, как следует из этого контекста, полностью нанхондитнся под упpавнленнинем тpанслятоpа и pаспpеделяется под статические обънекты, сунщенствунюнщие в системе постоянно. Например, декларация VAR A: POINTER TO CARDINAL; B: CARDINAL; сообщает транслятору о необходимости "зарезервировать" в класнсе стантической памяти два слова под элемент хранения объекта с именем А и одно слово под элемент хранения объекта с именем В. Динамическая память предназначается для создания временно сунщенствунющих объектов. Этот класс памяти имеет две разновидности: собннстнвенно динамическую и автоматическую. Собственно диннанминчеснкая панмять (в отличие от статической) полностью находится в раснпонряжении пронграммиста: по его директивам происходит выделение эленментов храннения (создание объектов) и возврат ранее вынденленнных элементов в "зону" свободной памяти (пул "свободных" эленменнтов), что в этом смынсле равносильно "уничтожению" объекта. Автоматическая память - особая разновидность динамической, коннтонрая также управляется директивами программиста, связанными с инннтернпретацией активных объектов (переменных пpоцедуpных типов). В этом смысле две разновидности динамической памяти делят этот класс памяти на два подкласса: память для интерпретации паснсинвнных обънекнтов (собственно динамическая) и память для интернпрентанции активных обънектов (автоматическая). Несмотря на общность класнса (диннанминчеснкая память), распределение памяти в этих поднкласнсах основано на разнных принципах и реализуется совершенно разнными алгоритмами. Управление динамической памятью для пасссивных объектов (в дальннейшем просто динамической памятью) реализуется на основе двух оснновных процедур (обычно импортируемых из системного модуля): PROCEDURE ALLOCATE (VAR A: ADDRESS; N: CARDINAL); PROCEDURE DEALLOCATE (VAR A: ADDRESS; N: CARDINAL); . Здесь А - свободный указатель, который укажет на выделенную обннласть памяти (элемент хранения размером N байт) при вызове ALLOCATE и получит значение NIL (т.е. никуда не будет указывать) при освобождении этой области "из-под" А путем вызова DEALLOCATE. Использование ограниченных указателей делает во многих отнноншеннинях целесообразным использование специальных вызовов: NEW(P) и DISPOSE(P), где VAR P: POINTER TO <Объект>. (NEW и DISPOSE - псенвндонпроцедуры, их вызовы транслируются в вызовы ALLOCATE и DEнALнLOнCAнTE соответственно). Использование NEW и DISPOSE позволяет изнбежать многих семантических ошибок, связанных с различными значениями N в последовательности вызовов ALLOCATE...DEALLOCATE, определяющей созндание/уничтожение одного и того же объекта. В целом последовательность вызовов NEW...DISPOSE (или соотнветнстннвенно ALLOCATE...DEALLOCATE), в общем случае полностью опнреннденляненмая логикой программиста, порождает ряд проблем, свянзаннных с орнганннизацией и распределением свободного пространства диннанмической панмяти. Одной из таких проблем является проблема фрагнментации. Эфнфект фрагментации заключается в том, что рабочая область диннанминчеснкой памяти "дронбится" на части - фрагменты разнличнной длины. Какие-то из них "занняты" - используются пронгнрамнминстом под элементы хранения его обънектов, какие-то "свободны", принчем характер ченрендонвания свонбоднных и занятых фрагментов в общем случае может быть сонвершенно произвольным. Любой запрос программиста на создание нонвонго объекта приводит к тому, что сиснтема управления динамической панмятью "подбирает" ему фрагнмент, подходящий по размерам. Правила танкого подбора могут быть различны, но общая закономерность одна: танкой фрагмент должен иметь размер, не меньший, чем запрашиваемый пронграммистом. Если подходящий фрагмент имеет больший размер, чем требуется, в принкладнную программу будет отдана его часть, котоpая теннпеpь будет pаснсматpиваться системой как занятый фpагмент, а оснтаннток оснтаннетнся в свободной зоне в качестве свободного фpагмента. При этом проблема фрагментации заключается в том, что эффект "дронбленния" может привести к тому, что в свободной зоне будет нанхондитьнся мнонжество "маленьких" разрозненных свободных фрагментов, в сонвонкупнности составляющих достаточный объем. Тем не менее, ненснмонтря на такой объем, запрос программиста на новый элемент памяти монжет получить отказ по причине отсутствия целого подходящего эленменнта. Ниже приведен фрагмент программы и схема распределения динннанмической памяти, иллюстрирующие эффект фрагментации. При этом для простоты предполагается, что общий объем диннанминчеснкой памяти составляет 20 байт.
TYPE Треугольник = POINTER TO Фигура_1 Фигура_1 = RECORD Сторона_1, Сторона_2, Сторона_3:CARDINAL END; Четырехугольник = POINTER TO Фигура_2; Фигура_2 = RECORD Сторона_1, Сторона_2, Сторона_3, Сторона_4: CARDINAL ЕND VAR T1, T2: Треугольник; М1, М2: Четырехугольник; BEGIN NEW(T1);... NEW(M1);... NEW(T2);... DISPOSE(T1);... DISPOSE(T2); NEW(M2);...
????????????????????? ?? ? WORD ? ? ????????????????????? ? ? ? > Свободный фрагмент, ранее ????????????????????? ? использованный под ? ? ? объект Т1^ ????????????????????? ???? ????????????????????? ? ????????????????????? ? ????????????????????? ? ????????????????????? > Фрагмент, занятый ????????????????????? ? под объект М1^ ????????????????????? ? ????????????????????? ? ????????????????????? ???? ? ? ? ????????????????????? ? ? ? > Свободный фрагмент, ранее ????????????????????? ? использованный под ? ? ? объект Т2^ ????????????????????? ??
Иллюстрация построена для момента обработки запроса NEW(M2). В этот момент времени в динамической памяти имеются два свонбонднных фрагнмента общим объемом шесть слов, которых достаточно для выннполнненния запнроса на выделение элемента хранения под объект М2^ (т.е. для обънекта, на котоpый будет указывать M2), однако франгнментация не позннволяет системе выделить память под объект М2^. Система управления динамической памятью ведет специальный спиннсок свободных фpагментов - пул памяти. При возвращении какого-либо эленмента хранения, используемого в прикладной прогнрамнме, в пул свонбодной памяти может быть реализовано "скленинванние" соседних свонбоднных фpагментов в один фpагмент большего обънема. Например, если в предыдущей программе изменить поснлендонвантельнность обращений к динамической памяти на приведенную ниже, то описанного выше отказа по памяти не произойдет: BEGIN NEW(T1);...NEW(T2);...NEW(M1);... DISPOSE(T1);...DISPOSE(T2);... NEW(M2);...
Здесь при обработке запроса NEW(M2) в пуле динамической панмянти будет находиться один свободный фрагмент объема шесть слов, обнранзоннваннный "склеиванием" элементов Т1^ и T2^, выполненным при обнранботке запнроса DISPOSE(T2). В общем случае вопросы эффективной ренализации управления динамической памятью, обеспечивающей миннинмум отказов при ограниченном объеме, составляют отдельную пробнленму. Здесь мы только заметим, что с организацией выделения "пернвого подходящего" фрагмента памяти в программировании свянзынванют такие термины как "хип" или "куча", относящиеся скорее к пронфессиональному жаргону, чем к научно-методической тернминнонлонгии. Тем не менее эти термины донвольно образно характеризуют приннципы организации динамической памяти. Организация корректной последовательности запросов связана, кронме того, как минимум еще с двумя проблемами. На том же жарнгонне их называют проблемы "висячих ссылок" и "мусора", а опнренденлянют они две стороны одной и той же ошибки, заключающейся в некорнренктнной работе с указателями. Следующий фрагмент программы илнлюнснтнринрует возникновение таких ошибок (тип "Треугольник" описан выше).
VAR T1, T2:Треугольник; BEGIN NEW(T1);...T2:=T1;... DISPOSE(T1); (* T2-"висячая ссылка" *) ............ NEW(T1);...NEW(T2);... T1:=T2; (* Остался "мусор" *)
Из этого примера понятно, что "висячая ссылка" - это уканзантель принкладной программы, указывающий на свободный фрагмент диннанминчеснкой памяти. Поскольку этот фрагмент может быть выделен сиснтемой по какому-либо запросу другой прикладной программе, Т2 монжет открыть доснтуп к "чужим" данным и "разрешить" их иннтернпрентацию как тренунгольнника. Последствия такой интерпретации в обнщем случае непреднсканзуемы. Заметим, что "висячая" ссылка и "пуснтая" ссылка (имеющая значение NIL, см. pазд.III) являются сонверншеннно разными понянтинянми. "Мусор" - это занятый фрагмент динанминчеснкой памяти, к которому в прикладной программе потерян доступ. В приведенном примере мусором оказался старый треугольник Т1^, на который указывал Т1 до пенренднвижнки (установки на Т2). Этот мусор неустраним: программист не именет к нему доступа, а система управления "считает" мусор занятым фрагнментом памяти. Объединяет эти два вида ошибок одно общее обстоятельство: они не обнаруживаются исполнительной средой. Идентифицировать пондобнные ошибки можно только путем тщательной проверки и отладки прогнраммы. И, наконец, по своим возможным влияниям на работу прогнраммы мусор гонраздо "безобиднее" висячей ссылки. Он факнтинчеснки приводит только к увеличенному расходу памяти, в то время как висячая ссылка спонсобнна при определенных условиях полностью панрализовать процесс вынполннения программы. В сложных системах "ценна" висячей ссылки может оказаться очень высокой. Использование автоматической памяти связано с сознданнинем / уничнтонжением специальных элементов хранения, связанных с активннынми обънектами - действиями или процедурами. Любая процедура тpенбует для выполнения собственной индивидуальной локальной сренды. Подобную сренду образуют локальные переменные, объявленные в пронцедуре, форнмальнные параметры, элемент хранения адреса вознвранта в процедуру, т.е. набор объектов, обеспечивающих выполнение дейнствий, связанных с процедурой. Необходимость в локальной сренде возникает только в монмент вызова процедуры - момент интернпрентанции объекта процедурного типа. После завершения такой интернпрентации необходимость в локальной сренде исчезает. Таким обранзом, время жизни локальной среды огнраннинчинвается временем отнранботнки программы, в которой она описана. Сонотнветственно запрос на создание локальной среды связан с вызовом пронцедуры, а запрос на уничтожение - с окончанием фазы активности объекта (оператор RETURN или END в теле процедуры). Например: VAR W1, W2: PROC; PROCEDURE Работа_1; VAR A: INTEGER;... BEGIN... W2;... END Работа_1; PROCEDURE Работа_2; VAR A: INTEGER;... BEGIN... W2;... END Работа_2; BEGIN... W1:=Работа_1;... W2:=Работа_2;... W1;...
В этом фрагменте описаны два активных объекта процедурного типа PROC = PROCEDURE(): W1 и W2 и две процедуры без параметров: Работа_1 и Работа_2, которые могут использоваться как константы тинпа PROC. Интерпретация (активизация) W1 приведет к вызову Работы_1 и созданию локальной среды (содержащей переменную А). В процессе выполнения Работы_1 производится активизация объекта W2 и соответственно создание локальной среды для Работы_2. В любой тенкущий момент времени в системе могут быть активны несколько обънекнтов. (В этом примере активизация W1 приводит к активизации W2, зантем они оба остаются в активном состоянии и затем теряют свою активность в обратной последовательности: сначала паснсинвинруется W2, затем W1). Последовательность активации и пассивации свянзана с влонженностью вызовов процедур, соответственно упнравнленние автонмантинчеснкой памятью основывается на использовании стека - структуры, поднндерживающей такую вложенность. Ниже для этого фрагнмента принвенденнна иллюстрация распределения автоматической панмянти, сущенствуюнщенго в течение совместной активности объектов W1 и W2.
?? ????????????????????? ?? ? ? Переменная А ? ? ? ????????????????????? > Локальная среда ? ? Адрес возврата ? ? для W1 Занятое прост- < ????????????????????? ?? ранство ? ? Переменная А ? ? ? ????????????????????? > Локальная среда ? ? Адрес возврата ? ? для W2 Вершина ??> ?? ????????????????????? ?? стека ? ? ? автоматической ? ? ? памяти ? ? ? Свободное ? ? > пространство Пассивация ? ? ? памяти ? ^ ? ? ? ? ? ? ? ? ? ? ? ? ? v ? ????????????????????? ?? Активация При активации каждого нового объекта вершина стека "опуснканетнся вниз" на величину, определяемую размерами локальной среды этого обънекта,- при его пассивации вершина стека "поднимается вверх". С использованием автоматической памяти связаны две оснновнные пронбнлемы: рекурсии и множественности ассоциаций. Рекурсия - механизм, позволяющий объекту совершать самонакнтинванц-ию. Например, по схеме: W1-->W1 (прямая рекурсия) или W1-->W2 ...-->W1 (косвенная рекурсия).
Прямая рекурсия связана с непосредственной повторной (влонженнной) активацией, а косвенная - с опосредованной (причем число посннреднников в схеме W1-->...-->W1 может быть произвольным). Иснпольнзонванние рекурсии напрямую связано с размерами рабочего простнранства автонматической памяти. Использование рекурсивных актинваций обънекнтов, с одной стороны, позволяет иметь очень лаконничнные и емкие по сондержанию программы, с другой стороны, в ренкурнсивных схемах (особенно в косвенной рекурсии) возрастает венронятность появления трудно идентифицируемых ошибок. Множественность ассоциаций заключается в том, что в классе авннтонматической памяти могут быть одновременно размещены неснкольнко однноименных объектов, имеющих в общем случае различные значенния и относящиеся к разным активностям одного и того же или опять-таки разных объектов. В приведенном примере существуют два однонименных объекта: переменная А, связанная (ассоциированная) с активностью W1, и переменная А, ассоциированная с активностью обънекта W2. В соннответствии с принципом стека система упpавления автоматической панмятью всегда pассматpивает в качестве активной поснледнюю сознданнную ассоциацию (самую "ближнюю" к вершине стека автонматической панмянти). Возникновение множественности ассоциаций обусловлено только использованием в прикладных программах однонинменнных переменных с различной областью действия (областью виндинмоснти). Если уж иснпольнзонвание таких переменных и является необнхондимым (в чем всегда стонит усомниться), то при их интерпретации следует помнить о мнонженстнвеннности ассоциаций. VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ Связанная организация памяти. - Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные структуры. - Наборы. - Деревья.
Связанная организация памяти определяет множество структур, связи между элементами которых реализуются указателями. Каждый эленмент такой структуры (объект) обладает, таким образом, свойнснтнвом "иметь связи" с другими элементами, на которые указывает знаннченние этого свойства. Связанная организация памяти может иснпольннзонватьнся и для хранения статических структур данных, но поснкольнку ренанлизация связей через ссылки дает возможность испольнзонвать диннанминческие механизмы создания/уничтожения объектов, оснновнным принменненнием связанной организации является динамическое монделирование объектно-ориентированных систем. Динамические структуры объектов, как уже отмечалось, ханракнтенринзунются наличием особого свойства: "иметь переменный состав эленнменнтов стpуктуpы". Это свойство позволяет любую динамическую струкнтуру раснсмантринвать как ассоциацию связанных объектов перенменнного состава. (Заметим, что термин "ассоциация" используется в программировании очень часто и смысл, вкладываемый в это понянтие, во многом зависит от контекста). Свойство ассоциативности относится к общим групповым свойнстнвам класнсов, оно присуще не объекту в отдельности, а совонкупннонсти обънектов. Простейшим примером группового свойства является "Конлинчеснтво объектов в классе"- ни один из объектов класса в отнндельннонсти таким свойством не обладает. Pеализация ассонциантивнных свойств классов тренбует использования специальных структур, "связывающих" объекты-члены этих структур "узами" ассонциантивннонсти. В прикладных задачах это могут быть "узы" дружбы, общие канчеснтва, выделяющие свойнства (например, свойство "Быть молодым") и т.п.. Ассоциация объннектов, кроме того, как правило упорядочена по определенной сиснтенме правил - отношений порядка на множестве членов ассоциации. Такие правила устанавливают биективную (взаимно-однозначную) связь межнду множеством объектов-членов аснсонциации и элементами натунральннонго ряда чисел. В этом смысле ассонциация - более сложная струкнтунра, чем множество объектов. Правила, регулирующие упорядоченность ассоциации, могут быть сконнструированы как выделяющие свойства на множестве имманентных свойств объекта (например,упорядоченность по "Возрасту" объекта, "Приоритету" объекта). Они могут быть построены на основе вренменни модификации состава членов ассоциации (например,правило "пернвым пришел - первым вышел" хорошо известно всем, кто бывал в очередях: кажндый вновь пришедший в очередь становится последним членом этой ассоциации очередников). Общее свойство ассоциации закнлюнчанетнся в том, что возможность биекции ее структуры (соснтанва) на нантунральнный ряд чисел фактически определяет наличие "линейного" понряднка на множестве ее членов. Такой поpядок опнpенденляется отношениями предшествования: "предок-потомок", "прендындунщий-последующий" и т.п. Это свойство делает основной реанлизанцинонной структурой ассоциации линейный список. С помощью списков могут моделироваться разнообразные диннанминчесннкие структуры, поддерживающие различные отношения порядка. В пронгннранмнмировании широко используются такие структуры, как стек, оченредь, дек, пул - все они могут быть реализованы на списках. В занвинсимости от количества связей между соседними элементами разннлинчанют односвязные и двусвязные списки с "встречным" напнравнленннием стренлок. Ниже пpиведены некотоpые пpимеpы оpганизации списнковых стpуктуp на связанной памяти.
Односвязный список
??????????? ???????????? ??????????? ? INFO ? ? ? ? ? H1 ??????????? ???????????? ??????????? ???>? LINK *??????>? *???????>...??>? *????????NIL ??????????? ???????????? ??????????? ???
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
LINK: PTR (* Поле связи *)
END;
VAR H1: PTR; (* "Голова" списка *)
Двусвязный список ? К2 v H2 ??????????? ???????????? ???????????? ???>? INFO ? ? ? ? ? ??????????? ???????????? ???????????? ? RLINK *??????>? *??????>...??>? *????? ??????????? ???????????? ???????????? ? ?????* LLINK ?<??????* ?<????...<????* ? ??? ? ??????????? ???????????? ???????????? ???
TYPE PTR = POINTER TO Элемент;
Элемент = RECORD INFO: Инфоpмационное_Поле;
RLINK,LLINK: PTR (* Поля связи *)
END;
VAR H2,K2: PTR; (* "Голова" и "Конец" списка *)
? Кольцо v H3 ??????????? ???????????? ???????????? ? INFO ? ? ? ? ? ??????????? ???????????? ???????????? ?????>? RLINK *??????>? *??????>...??>? *????? ? ??????????? ???????????? ???????????? ? ? ?????* LLINK ?<??????* ?<????...<????* ? ? ? ? ??????????? ???????????? ???????????? ? ? ? ^ ? ? ????????????????????????????????????????????????? ? ???????????????????????????????????????????????????????????? В общем случае любой элемент списка может содержать пронизнвольннное количество связей и являться членом многих списков. Это поннрожнданет большое многообразие списковых структур - фактически любая диннамическая структура на связанной памяти конструируется из списнков. По составу элементов списки разделяются на одннонроднные и разннонродные, в однородных используются объекты только одного класса, в разнородных - разных классов. Например, членами ассоциации "Эленмент фигуры" могут быть объекты классов "Точка" и "Окружность": TYPE Точка = RECORD X,Y: INTEGER (* Координаты точки *); LINK : ADDRESS END; Окружность = RECORD Центр: Точка; R: CARDINAL (* Радиус *) LINK : ADDRESS END; . Как члены ассоциации, реализуемой односвязным списком, они ханракнтеризуются свойством "Иметь одну связь" (LINK) с "соседом" по аснсоциации, в информационной же части эти объекты отличаются друг от друга как по представлению так и по интерпретации. Спинсок, ренанлинзующий ассоциацию "Элемент фигуры", будет относиться к кантенгонрии разнородных: ??????>?? Окружность ????????? ????????? Ц ? ?????????? ????????? ???>? X ? ? X ? е ? ? ? ? ? ????????? ????????? н ? ?????????? ????????? ? Y ? ? Y ? т ? ? ? ? ? ????????? ????????? p ? ?????????? ????????? ?LINK *?????>? R ? ? ? *???????>? ? ????????? ????????? ? ?????????? ????????? Точка ?LINK *???????? Точка ? *???? ????????? ????????? v Окружность ??? Доступ к элементам списка реализуется через указатели. Уканзантель на первый элемент односвязного линейного списка (голову) отннкнрынвает доступ ко всем его элементам: стрелки на рисунке уканзынвают нанправление последовательного доступа. Для реализации танконго доснтунпа необходимо последовательно (в направлении, указынваненмом стрелнканми) осуществить "перестановку" (передвижку) указантенля на нужный эленмент списка. Естественно, что увеличение колинченснтва связей увенлинчивает возможности быстрого доступа к элементам списка. Напнринмер, любой элемент двусвязного списка открывает доснтуп к "левому" и "правому" соседу, а односвязного - только к "правому". Голова явнляется особым элементом списка, вторым осонбым элементом является последний элемент - на него часто станвитнся указатель конца спинснка (К2 на схеме двусвязного списка). В струкннтуре "кольца" поннянтие осонбого элемента становится чисто уснловннным, поскольку никакие pенальнные внутренние "особенности" (как, напpимеp, К2^.LINK=NIL - условие "конца" в схеме линейного двунсвязного списка) здесь не пpедннставлены. Интерпретация элементов разноpодных списков связана с донполннинтельнными трудностями- нужно не только получить доступ к соотнветннстнвующему элементу структуры, но и определить, к какому класнсу он отнносится (в приведенном примере: "Точка" или "Окружнность"). Для унификации процессов интерпретации таких структур монгут сунщенстнвеннно помочь методы определения наложением (см. pазд.IV). При этом совннместимость представлений различных классов по полю связи станнонвитнся существенным фактором обеспечения корнректнной работы с эленменнтами списка. Обеспечена ли такая совнменстинмость в определениях "Точки" и "Окружности" ?. В задачах динамического моделирования сложных систем особый класс составляют системы с очередями. Очередь - ассоциация обънекннтов, ожидающих доступа к системе обслуживания. Такая диннаминчеснкая ассоциация характеризуется дисциплиной обслуживания (ожинданния). Выннше уже упоминалась дисциплина "первым пришел - первым выншел" (First In - First Out), обычно она обозначается абнбревинантунрой FIFO. Как разновидность очереди нередко рассматривают ассонцинантивнную стpуктуpу стека, в этой интеpпpетации стек ханракнтенризуется динснциплиной "Last In - First Out" ( "последним приншел - первым вышел" ) - LIFO. С точки зрения реализации на спинснках, эти струкнтунры отличаются механизмами доступа: очередь доснтупнна с двух концов - с "головы" (для выбоpа элемента из оченpенди) и с "хвоста" (для постановки в очеpедь), а стек - только с "гонловы" (и для включения в стек, и для вывода из стека). (В прогнраммировании иснпольнзуется также структура дека - линейного списнка, доступ к контонронму возможен с любого из двух концов как для включения элемента в спинсок, так и для удаления из списка). Динамическое изменение состава объектов, находящихся в оченренди, делает размер очереди (длину) величиной переменной. При этом моденлинрование очереди в статической структуре массива связано с рензернвиннрованием избыточного объема памяти, достаточного для хранненния оченреди максимально возможного размера. На связанной диннанминческой паннмяти возможно более эффективное pешение, базиpующееся на иснпольнзовании стpуктуpы "кольца", в которое включаются и из коннтонронго иснклюннчаются объекты-очередники. Для включения-искнлюченния иснпольнзунютнся два указателя: на начало (голову) очереди - Н, и на ее конец - К. Такие указатели "передвигаются" по структуре кольнца в нанпнранвленнии стрелок, связывающих элементы: К переднвиганетнся при включении нонвого элемента в очередь, Н - при выводе из оченреди. В динамике К как бы "пытается догнать" Н, а Н - пынтанетнся "убежать" от К. Синтунанция, когда К "догоняет" Н свидентельнствунет о том, что структура кольннца полностью использована, - в этом слунчае необходимо донполннинтельнное обращение к динамической памяти для выделения элемента хранения под новый объект, включаемый в оченpедь. Случай, когда Н "донгоняет" К свидетельствует о том, что оченpедь пуста. Ниже принвенденна иллюстрация структуры кольца-очереди.
v Н ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ??????? ? *???>? *???>? *???>? *??????? ??????? ??????? ??????? ??????? ? v K ^ v ??????? ? ???????? ??????? ? ?INFO ? ??????? ? ???????? ? *???????? ?LINK *? ??????? ???????? ^ ? ? ??????? ??????? ??????? ??????? ? ? ? ? ? ? ? ? ? ? ? ? ??????? ??????? ??????? ??????? ? ????????* ?<???* ?<???* ?<???* ?<??????? ??????? ??????? ??????? ??????? INFO - информационная часть объекта, LINK - связь с "сонсендом". Штриховка ???? иллюстpиpует "занятость" соответствующего эленмента кольннца (использование его для хранения объекта). В класнсе диннанминчеснкой связанной памяти возможны и другие решения организации оченрендей. Основными операциями над списками являются операции вставки-удаления элементов. Такие операции всегда (независимо от техники ренализации) должны выполняться корректно: - сохранять общую структуру связанной организации списка; - не приводить к образованию "мусора" и "висячих ссылок"; - сохранять отношение порядка элементов в списке. Выполнение этих требований связано с корректным определением посннледовательности операций по модификации списков. Например, ниже приведена иллюстрация к операции удаления эленменнта В из списка Н.
v P v B Н ?????? ?????? ?????? ?????? ?????? ? ? ? ? ? ? ? ? ? ? ? ??>?????? ?????? 1 ?????? ?????? ?????? ? *????>? *????>? *????>? *???>...?>? * ? ?????? ???|?? ?????? ?????? ?????? | 2 ^ v +
Предполагается, что указатель В предварительно установлен на удаляемый элемент. Для удаления В необходимо: 1) Начав с головы списка Н, "передвинуть" вспомогательный уканзантель Р на элемент, предшествующий В в списке. (Как правило, это денлается в циклах WHILE или REPEAT). 2) "Перебросить" связь Р^.LINK (пунктир на рисунке). Это делается оператором: Р^.LINK := В^.LINK (или оператором: Р^.LINK := Р^.LINK^.LINK). При этом связь 1 на рисунке оказывается разорванной, а связь 2 установленной. Список Н сохранил свою структуру, а элемент В не оканзался "мусором". При использовании сложных многосвязных списковых структур обенснннпенчение корректности модификаций списков требует от прогнранмнминнста осонбого внимания - любой "случайный" разрыв связи в списнке пренвнранщает в "мусор" всю его часть, оставшуюся за этой свянзью. Одной из самых распространенных ошибок при модификации списнков является также ошибка, связанная с попыткой получить доступ к элементу через указатель Н = NIL. Чтобы пpедотвpатить такие ошибнки, пpи констpуиpовании булевских выpажений, опpеделяющих условия завеpшения (пpодолжения) циклов, связанных с поиском элемента и т.п., необходимо следовать пpостому пpавилу: вычиснленние условия (H#NIL), опpеделяющего возможность доступа к эленменнту списка "под H", всегда должно пpедшествовать вычислению уснлонвия, содеpжащего квалидент с пpефиксом H^. В этом плане могут оказаться очень полезными пpавила последовательного вынчиснленния логинческих условий: A AND B = IF A THEN B ELSE FALSE; A OR B = IF A THEN TRUE ELSE B. Здесь A и B - логические условия. Напpимеp, для вычисления (A AND B ) вычисление B пpоводится тольнко после пpовеpки A с pезультатом TRUE, пpи A=FALSE опеpанд B вообще не вычисляется. Список относится к особой группе структур - это так нанзынваненмые ренкурсивные структуры. Приведем рекурсивное определение списка: Списком называется соннвонкупность связанных элементов, из которых один является осонбым элементом (первым, "головой"), а все остальные образуют спинсок. Рекурсивные структуры в программировании замечательны тем, что мнонгие операции по их обработке можно эффективно реализовать с использованием рекурсивных процедур, которые отличаются больншой ланконичностью и наглядностью. В качестве примера приведем пронцендунру проверки, является ли Н1 подсписком списка Н: TYPE Указатель = POINTER TO Элемент; Элемент = RECORD INFO : Инфоpмация; LINK : Указатель; END PROCEDURE Проверка (Н,Н1 : Указатель) : BOOLEAN; BEGIN IF H # NIL THEN RETURN (Н = Н1) OR Проверка (Н^.LINK, Н1) ELSE RETURN (Н = Н1) END END Проверка. Проверка (H # NIL) в этом примере нужна только для того, чтонбы предотвратить попытку интерпретировать пустую ссылку как эленмент списка при вызове Проверка (H^.LINK, H1). Ситуация (H=H1=NIL) рассматривается как положительный результат проверки. Другим примером рекурсивной структуры является структура нанбора, которая определяется следующим образом: Набором называется совокупность связанных элементов, каждый из которых может быть линбо атомом, либо набором. Атом определяет "неделимый" элемент нанбора, предназначенный для хранения элементарной порции иннфорнманции. Реализация наборов основана на использовании разнородных списков. Например, ниже приведена одна из возможных структур нанбонров. В этой структуре H1 - набор из четырех элементов (a,b,H2,c), из них H2 - набор, остальные - атомы. H2 состоит в свою очередь из тpех элементов - атома c и двух наборов H3 и H4, причем набор H3 - пуст (не содержит элементов), а H4 содержит два атома (d и f).
v H2 ??????? ??????? ??????? ??????? H1 ? a ? ? b ? ? ? ? c ? ?>??????? ??????? ??????? ??????? ? *?????>? *?????>? *?????>? *????????????????? ??????? ??????? ??????? ??????? v ? * ? ??? ??????? H3 H4 v v v ??????? ??????? ??????? ? c ? ? ? ? ? ??????? ??????? ??????? ? *?????>? *?????>? *??????? ??????? ??????? ??????? ??? ? * ? ? * ? ??????? ??????? v v ??? ??????? ??????? ? d ? ? f ? ??????? ??????? ? *?????>? * ? ??????? ??????? v ??? Элементы H2, H3, H4 определяют "головы" новых наборов и одннонвременно являются членами наборов "верхнего уровня" - при этом структура набора оказывается адекватной для реализации динанминчеснких "вложенных" понятий предметной области. Например, в ассонцинацию H1-"Акционеры" могут входить как отдельные частные линца, так и коллективы - организации, которые являются ассонцианцинянми собственных акционеров. Элементы H2, H3, H4 на приведенной иллюстрации участвуют в двух связях - горизонтальной (связь между членами одного набора) и вертикальной (связь с членами "своего собственного" набора). Эта терминология часто используется для организации так назынваенмых ортогональных списков, моделирующих структуры динамически изменняющегося плоского "игрового поля": "разреженных" матриц, "кроссвордов", цепей "домино" и т.д. Понятие "игрового поля", раннзунмеется, не означает, что ортогональные списки используются лишь в игровых задачах. Еще один пример рекурсивной структуры, широко использующейся в программировании - структура дерева. Деревом называется совонкупность связанных элементов - вершин дерева, включающая в себя один особый элемент - корень, при этом все остальные эленменнты образуют поддеревья. Наиболее широко используется струкнтунра бинарного дерева, все множество вершин которого делится (по отношению к корню) на два подмножества - два поддерева (левое и правое). Любая вершина бинарного дерева реализуется на связанной памяти элементом с двумя связями: с левым поддеревом и с правым.
v К ?????? Информационное поле ?????? ??????* ? Связь с левым потомком ? ?????? ? ? *?????? Связь с правым потомком v ?????? v ?????? ?????? ?????? ?????? ????????* ? ????* ? ? ?????? v ?????? ? ? *?????? ???? *??????? v ?????? v ?????? v ?????? Л1 Л2 ?????? ?????? Л3 ?????? ?????? ?????? ?NIL ? ?NIL ? ?NIL ? ?????? ?????? ?????? ?NIL ? ?NIL ? ?NIL ? ?????? ?????? ??????
На этой иллюстрации изображена структура бинарного дерева на связанной памяти, здесь К - корень; Л1,Л2,Л3 - "листья" - верншинны с "пустыми" связями ("не выросшими" поддеревьями). Заметим, что в этой интерпретации дерево реализуется на однонроднных списках (в отличие от набора). Особое положение корня опнренделяется единственным свойством - отсутствием вершин-предков, любой лист дерева характеризуется полным отсутствием вершин-потомков. Поскольку любая вершина в связанной структуре дерева отнкрывает доступ только "вниз" (только к своим поддеревьям), она может интерпретироваться как корень соответствующего поддерева. В этом смысле лист является корнем "не выросшего" дерева и опнренденляет его своеобразную "точку роста". Включение в дерево новой вершины и удаление старой не должно нарушать общего отношения понряднка на множестве вершин. Примером такого отношения может служить отношение "больше- меньше", определяющее структуру бинаpного дихотомического деренва. В таком деpеве все вершины любого правого поддерева имеют значение инфорнмациноннного поля большее, чем значение такого же понля у корня, а веpншинны соответствующего левого поддеpева - меньншее. Например, конструирование дихотонминческого дерева по поснледовательности целых чисел 30,70,80,21,25,17,4, начиная с 30, должно приводить к созданию следующей структуры:
???? ????????30????????? ???? ???? ???? ??????21??????? ?70???????? ? ???? ? ???? ? ???? ???? ???? ?????17? ?25? ?80? ? ???? ???? ???? ??? ?4? ???
Нетрудно заметить, что процесс конструирования такого дерева пронисходит сверху-вниз, начиная с корня, путем последовательного сравнения числовых значений, pазмещаемых в веpшинах, с целью определения места размещения соответствующей вершины в структуре дерева. Любая модификация дихотомического деpева (удаление веpншинны, вставка новой веpшины) не должна наpушать дихотомической стpукнтуpы в целом. В обнщем случае трансформация произвольной информационной стpоннки (поснледонвантельнности объектов) в структуру дерева и обнратнно основана на использовании глубоких стpуктуpных межобъектных отноншений в исходной стpоке. Такая тpансфоpмация позволяет нагнлядннно пpедставить подобные отношения в фоpме деpева. В пpогнpамнминpовании деpево во-многом pассматpивается как фоpмальная стpукнтуннpа, наполняемая pазличным семантическим содеpжанием. Такой поднход позволяет фоpмально реализовать многие преобразования даннных на основе унифицированных процедур обхода деревьев. Напнринмер, в теории трансляции широко используется понятие польнской инверсной записи (ПОЛИЗ) - особой системы представления математических выражений символьными последовательностями. Так, например, выражение " a + b * c " будет представлено в ПОЛИЗЕ строкой " a b c * + ". Если представить исходное выражение в естественной иерархической форме бинарного дерева : +----<----+ | | ????? | ??????? + ???????? | ? ????? ? | ????? ?????
? a ? ???????? * ??????? | ????? ? ????? ? | | ????? ????? | | ? b ? ? c ?->--+ | ????? ????? | | | | +--->---+ +
то его восходящий обход (пунктир на рисунке) приведет к стронке " a b c * + ", определяющей "польский" эквивалент исходной стронки. Формула восходящего обхода "Левый - Правый - Корень" (ЛПК) определяет правило обхода бинарного дерева: восходящий обнход связан с обходом его левого поддерева, затем правого поднденренва, затем корня. Поскольку каждая вершина дерева может интернпреннтироваться как корень "вырастающего из нее" поддерева, это праннвило применяется рекурсивно к каждой вершине обходимого денренва. Правило ЛПК (Левый - Корень - Правый) определяет так нанзынваненнмый смешанный обход, правило КЛП - нисходящий обход и т.д. Нетнрундно заметить, что смешанный обход дерева дихотомии по пранвилу ЛКП приведет к формированию строки чисел (хранящихся в вершинах этого дерева), упорядоченной по возрастанию, а такой же обход по правилу ПКЛ - к формированию строки, упорядоченной по убыванию соответствующих чисел. Таким образом, между структурой дерева, отнношением порядка на множестве информационных компонент его верншин и видом обхода существует глубокая связь, определяемая реннкурсивной природой структуры дерева. Рекурсивные процедуры обнхонда бинарных деревьев пишутся прямо по формуле обхода с учетом спенцификации представления вершин дерева. Например, ниже принвенденна процедура смешанного обхода бинарного дерева дихотомии, ренанлизующего формулу ЛКП.
TYPE Вершина = POINTER TO Элемент ; Элемент = RECORD Info : CARDINAL ; LLink,RLink : Вершина END ;
PROCEDURE Смеш_Обход (K : Вершина); BEGIN IF K # NIL THEN Смеш_Обход (K^.LLink); (* Обход левого поддерева *) WriteCard (K^.Info); (* Обработка корня *) Смеш_Обход (K^.RLink); (* Обход правого поддерева *) END END Смеш_Обход.
В традиционном программировании рекурсия часто раснсмантринванетнся как некоторый заменитель итерации. Причем в качестве примеров раснсматривается вычисление рекуррентных последовательностей, контонрые могут быть легко сформированы и обычными итераторами (цикнланми WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не именет альтеpнатив в виде итераторов только тогда, когда решение зандач проводится на рекурсивных структурах. Попробуйте написать пронцедуру Смеш-Обход без использования рекурсии, только на осннонве циклов и, если Вам это удастся, сравните ее с приведенным вынше вариантом рекурсивной процедуры по наглядности,лаконичности, вынразительности. VII. ПРОЦЕССЫ В ОБЪЕКТАХ Логический параллелизм. - Схема сопрограмм. - Понятие процесса. - Рабочая область процесса. - Создание/уничтожение процессов. - Реентерабельность. - Сигнальная синхpонизация. - Основы мониторинга, ориентированного на процессы.
В любом программном объекте могут развиваться динамические пронцессы, определяющие изменение состояния объекта во времени. Такие процессы могут развиваться автономно (независимо один от друнгого) или во взаимодействии друг с другом. Концепция взанинмондейнствия основывается на одновременном развитии нескольких пронцеснсов, при этом такая одновременность трактуется в прогнрамнминронваннии как логический параллелизм - одновременное выполнение неснкольннких действий (активностей), обусловленное логикой развития монделируемой системы. Реализация концепции логического панранлленлизнма требует в общем случае наличия нескольких процессоров (устнройств ЭВМ, обеспечивающих развитие параллельных процессов), что связано с использованием нового класса вычислительных систем - систем с мультипроцессорной архитектурой. Реализация паралнлельннных процессов на обычной однопроцессорной ЭВМ связана с иминтанцией логического параллелизма последовательностью активаций разнных процессов с сохранением общих логически обусловленных пранвил их взаимодействия. Такая имитация связана с понятием кванзинпараллельности. Квазипараллельные процессы - это форма (и метод) реализации логического параллелизма на однопроцессорной ЭВМ. В свою очередь существует множество различных способов реанлизанции квазипараллельности, отличающихся механизмами имитации однонвременных действий последовательностями активностей. Не останавливаясь на подробном рассмотрении таких способов, мы отнментим здесь общую закономерность: логическая параллельность (одновременность действий) в общем случае не приводима к последовательности активностей. Поэтому любой способ реализации квазипараллельности приводит к возникновению специфических пробнлем, известных в программировании как проблемы "тупиков", "кринтинческих секций", "семафоров" и т. п. Они подробно описаны в спенциальной литературе, посвященной вопросам параллельного прогнрамнмирования и организации взаимодействующих процессов. В основе общего механизма реализации квазипараллельности ленжит схема сопрограмм - особая схема управления, отличающаяся от шинроко используемой схемы подпрограмм тем, что она строится не на основе принципа "главный - подчиненный" ( "главная программа - подпрограмма"), а на основе "равноправия" всех взанимондейнствунюнщих программ. В схеме сопрограмм нет главной процедуры - "хонзяинна", который будет манипулировать вызовом "подчиненных", - любая пронцедура в этой схеме трактуется как "равная среди равных". Нинже приведена иллюстрация взаимодействия двух процедур по схеме сонпрограмм. На этой иллюстрации двойной чертой изобpажаются фазы активннонсти процесса, реализуемого сопрограммой, одинарной - передача упнравнления от процесса процессу. В отличие от подпрограмм, любая пронцедура, реализуемая как сопрограмма, может иметь множество тоннчек реактивации. Такие точки в тексте программы определяются раснстановкой специальных операторов управления (операторы синнхроннизации, задержки, ожидания и т.п.).
(сопрограмма 1) * * (сопрограмма 2) ? ? ? ??????> * ?? ? ? ? ?? фаза активности ?? * ??<???? ? ??> процесса 2 фаза ?? ? ? ? ?? активности <?? ? ????>?? * ?? ?? процесса 1 ?? ? ? ? ?? ?? * ??<???? ? ??> фаза активности ? ? ? ?? пpоцесса 2 ? ????>?? * ?? ? ? ? точка реактивации >> * ??<???? ? пpоцесса 1 ? ? ? ? ?? * << точка реактивации ? ? пpоцесса 2 ... ...
Чеpедование во вpемени фаз активности одной и той же сонпpонгнpамнмы опpеделяет логически обусловленную поснлендонвательность дейнстнвий, которая и образует процесс. "Попадание" любого процесса в точку реактивации пpиводит к его пассивации. Пpи этом управнленние передается другому процессу, причем выбор поснледннего произнвондится на основе специального механизма, свянзанннонго с оперантонром упpавления, опpеделяющим точку реактивации. Кажндый пpоцесс, pеализованный по схеме сопpогpамм, имеет свою собннственную pабочую область - индивидуальную область памяти, в конннтоpой сохpаняется его локальная сpеда (включая в общем случае и адpес "возвpата" - точку pеактивации сопpогpаммы). Это обнстонянтельнство и является основным фактоpом, pазpушающим концепцию "хоннзяина". Если в схеме подпpогpамм использование общего стека автонматически гаpаннтинpунет возвpат упннpавления "хозяину" (вызынванюнщей пpоцедуpе), то индинвидуальное хpаннннение локальных сpед пpонцесннсов в схенме сопpогpамм в обнщем случае не может дать никаких ганpантий по автоматической пенpендаче упpавления между пpоцессами. Более тонго, завеpшение любой сонпpогpаммы (выход на END без пенpенданчи упннpавления какому-либо пpоцессу) пpиведет к остановке всей сисннтенмы независимо от соснтояния дpугих пpоцессов. Объяснение этонму очень пpостое: сиснтема "не знает", какому из пpоцессов слендует пеpедать упнpавнленние, поскольку общей инфоpмационной стpукннтуpы, аналогичной обнщенму стеку, в pеализации "чистой" схемы сопpогpамм пpосто нет! Любая пpоцедуpа может использоваться и как подпpогpамма и как сопpогpамма. Существование пpоцедуpы как сопpогpаммы связано с поннятием пpоцесса, пpи этом на основе одной сопpогpаммы может быть создано несколько пpоцессов! Каждый их них может pаснсмантpинватьнся как автономный динамический объект с собственной pабочей обнластью и индивидуальной локальной сpедой. Пpонцедуpа, донпуснканюнщая свое использование в качестве сонпpогнpамнмы, на основе котоpой может быть создано несколько пpоцессов, нанннзывается pееннтеpанбельнной. (Ниже мы пpиведем пpимеpы, связанные с pеентеpабельностью). Любой пpоцесс может pеализовать обычное упнpавннление поднпpонгpанммами на основе общего стека и в то же вpемя взанимондейнствонвать с дpугими пpоцессами на основе тpансфеpизации (от слова TRANSFER) чеpез точки pеактивации. Заметьте, что в общем случае одннна и та же пpоцедуpа (одновpеменно) может использоваться и в pонннли поднпpогpаммы, и как сопpогpамма, опpеделяющая pазвитие лонгинчески паpаллельных пpонцеснсов! Теpмин "сопpогpамма" чаще всего используется для хаpакнтенpинстинки системного уpовня пpогpаммиpования, свянзанннонго с иснпольнзонваннием сpедств опеpационной системы или системных мондулей языка пpонгpаммиpования. Пpи этом точки pеактивации опpеделяются опенpантонpами нижнего (сиснтемнного) уpовня. Использование для pеанктинванции опеpатоpов более высокого уpовня (сигнальная синхpонизация, зандеpжки на вpемя и т. п.) в той же схеме сопpогpамм как пpавило сонпpовождается уже теpминологией пpогpаммиpования на основе взаниннмондействующих пpонцеснсов. Понятие процесса интегpиpует стантинчеснкие и динамические аспекты описания моделиpуемых систем. В ненконтоpых языках пpогpаммиpования вводится даже специальный тип даннных (PROCESS), объектами котоpого являются динамические пpонцеснсы. Такие пpоцессы могут к тому же динамически создаваться и уничтожаться (см. pазд. V), что опpеделяет многие нетpивиальные вознможности моделиpования задач pеального миpа. Hапpимеp, объект класнса "Автомобиль" может быть в пpоизвольный момент вpемени диннанмически создан и так же уничтожен. В то же вpемя в каждом танком объекте могут pазвиваться динамические пpоцессы, напpимеp, класнса "Движение" или "Тоpможение", котоpые также могут сознданватьнся как на статической, так и на динамической основе. Пpи этом вопpос о том, является ли движение атpибутом автомобиля или автомобиль атpибутом движения, пеpемещается в область философии - с позиций объектно-оpиентиpованного подхода к пpогpаммиpованию он может быть pешен как угодно. Создание пpоцесса в Модуле-2 связано с использованием спенцинальнной процедуры (метода):
PROCEDURE NEWPROCESS (P: PROC; A: ADDRESS; N: CARDINAL; VAR Pr: PROCESS). Этот метод создает новый пpоцесс Pr, pазвивающийся в сонотнветнстнвии с алгоpитмом пpоцедуpы, опpеделенной в P (по "телу" пpонцендунpы P), в pабочей области (A, N). Рабочая область выделяется по аднресу А и имеет размер N байт. Она может быть создана как на станнтической, так и на динамической основе в классе динамической панмяти. Разpушение pабочей области эквивалентно pазpушению (уничнтожению) пpоцесса. Метод NEWPROCESS содеpжит в качестве фоpмальных паpаметpов один объект пpоцедуpного типа (P: PROC) и один типа пpоцесс (VAR Pr: PROCESS). Пеpвый задает одну из множества пpоцедуp, котоpые монгут использоваться как сопpогpаммы, опpеделяющие pазвитие пpонцеснса. Втоpой пpедназначен для хpанения текущего значения точек pенакнтивации процесса. Выше (см. pазд.II) уже отнменчанлось, что TSIZE (PROC) = TSIZE (ADDRESS), из этого контекста нетpудно поннять, что TSIZE (PROCESS) = TSIZE (ADDRESS), т. е. фоpмально и тип PROC, и тип PROCESS хpанят адpеса и могут быть (опять-таки фоpнмально) пpосто заменены типом ADDRESS. Однако содеpжательно они опpеделяют абсолютно pазные классы объектов: процедуры, иннтернпретируемые в методе NEWPROCESS как сопрограммы, и динанминчеснкие процессы, развивающиеся по телу этих процедур. В этом смысле абннстpагиpование типов здесь выступает в новой роли - как сpеднстнво, позннволяющее семантически pазделить формально иденнтичнные класнсы PROC и PROCESS. Такое pазделение становится совеpшенно необходимым для аденкнватнного понимания тех ситуаций, в котоpых задача тpебует сознданния нескольких pазных пpоцессов, pазвивающихся по телу одной и той же пpоцедуpы. Hапpимеp, в пpогpамме могут существовать неснкольнко pазных объектов класса "Автомобиль", каждый из котоpых обннладает своим собственным пpоцессом движения. В то же вpемя алнгонpитм такого движения, описанный в пpоцедуpе "Движение_Авто", явннляется общим для всех движущихся автомобилей. (Hапpимеp, Движениен_Авто может описывать поpядок пpоезда опpеделенного участнка автомобильной доpоги, регламентируемый пpавилами доpожннонго движения, скоpостными огpаничениями и т.п., одинаковыми для всех автомобилей). VAR Pr1, Pr2, Pr3 : PROCESS ; Ro1, Ro2, Ro3 : ARRAY [1..200] OF WORD; PROCEDURE Движение_Авто (); ... END Движение_Авто; ... BEGIN NEWPROCESS (Движение_Авто, ADR(Ro1), 200, Pr1); NEWPROCESS (Движение_Авто, ADR(Ro2), SIZE(Ro2), Pr2); NEWPROCESS (Движение_Авто, ADR(Ro3), 200, Pr3); ... END; . В этом пpимеpе тpи пpоцесса Pr1, Pr2, Pr3 создаются по единнстнвенной (общей для всех них) пpоцедуpе Движение_Авто. Каждый из этих пpоцессов будет pазвиваться по общим пpавилам (движения), но индивидуально и в индивидуальной pабочей области. Пpогpаммы, допускающие такое "одновpеменное" pазвитие неснкольннких пpоцессов, как уже отмечалось, называются pеентенpабельннынми. В этом пpимеpе такой пpогpаммой является Движение_Авто. Пеpедача упpавления от одного пpоцесса дpугому (транснферинзанция) на уpовне сопpогpамм осуществляется опеpатоpом "Пеpедать упнpавление от пpоцесса P1 пpоцессу P2". Пpи этом в пеpеменную P1 занписывается точка pеактивации этого пpоцесса, а значение пенpенменнной P2 опpеделяет точку активации пpоцесса P2 (начало его оченpедной фазы активности). В Модуле-2 такую функцию pеализует опенpатоp TRANSFER : PROCEDURE TRANSFER (VAR P1: PROCESS; P2: PROCESS). NEWPROCESS и TRANSFER - два основных метода опpеделения пенpеннменных типа PROCESS на уpовне сопpогpамм, опpеделение таких пенpеменных непосpедственно пpисваиванием пpактически возможно, но надежность и коppектность такого пpисваивания весьма сомннинтельнна. В общем случае аpсенал методов упpавления pазвитием кванзинпанpалнлельных пpоцессов значительно шиpе и включает в себя не тольнко трансферизацию в чистом виде, но и опосpедованное упpавление, pеализуемое специальными объектами-посpедниками, pоль котоpых свондится к манипулиpованию активности пpоцессов - монитоpингу. Пpимеpом класса объектов-посpедников является класс SIGNAL (сигннал). Реализация объектов этого класса может быть выполнена мнонжеснтвом самых pазличных способов, мы здесь кpатко остановимся на однном из самых пpостых. В этой pеализации SIGNAL - класс стантинческих объектов, т.е. любой объект-сигнал создается на основе деклаpации соответствующих пеpеменных вида: VAR S1,S2 : SIGNAL. Hад сигналом возможно только одно действие - подать сигнал SEND (VAR S: SIGNAL). Использование сигналов для синхpонизации пpоцессов пpедполагает, что она осуществляется на основе ожинданния сигналов пpоцессами. Пеpеход пpоцесса в состояние ожидания подачи сигнала (пассивация пpоцесса) pеализуется опеpатоpом "ждать подачи сигнала" WAIT (S: SIGNAL). Подача сигнала пpинвондит к активации всех ожидающих его пpоцессов (pазумеется, в опнpенделенном поpядке), таким обpазом, использование этой паpы опенpатоpов позволяет манипулиpовать активностями пpоцессов. Механизм такой манипуляции основан на существовании спенцинальнной упpавляющей пpогpаммы - монитоpа, котоpая pеализует выбоp акнтивных пpоцессов и пеpедачу им упpавления. Такая пpогpамма иснпольнзует специальные упpавляющие стpуктуpы упpавления, котоpые в общем случае можно назвать pасписанием активаций пpоцессов. Эта стpуктуpа хpанит инфоpмацию о состоянии всех пpоцессов, пpонтенкаюнщих в пpогpаммной модели, пpи этом методы SEND и WAIT как динpекнтивы упpавления монитоpингом pеализуют адекватные изменения pаснписания активаций. Раснписание активаций является своеобpазным динамически изнменнянемым планом активизации пpоцессов и констpуиpуется из особых обънектов - паспоpтов (или дескpиптоpов) пpоцессов. Каждый пpонцесс, созданный в пpогpамме, снабжается паспоpтом, единственное нанзнначение котоpого - пpедставлять инфоpмацию о процессе в pаснпинсании активаций. Создание паспоpта может быть pеализовано и непосpедственно пpи создании пpоцесса, т.е. в методе NEWPROCESS. В pассматpиваемом пpостейшем случае такой паснпоpт может быть описан, напpимеp, следующим обpазом : TYPE PASPORT = POINTER TO PASP; PASP = RECORD STATUS : BOOLEAN; (* Текущее состояние пpоцесса *) Process : PROCESS; LINK : PASPORT; QUEUE : PASPORT; END; . Пpи STATUS=TRUE пpоцесс готов к активации (может быть акнтинвинpонван или находится в фазе активности), иначе паснсивен (пpиноснтанновнлен в точке pеактивации). Значение поля STATUS изнменяется опеннpатоpами опосpедованного упpавления, так в нашем случае опенpантоp WAIT пеpеводит пpоцесс (в пpогpамме котоpого он иснпольнзонван) в состояние пассивности. Опеpатоp SEND может быть pеналинзонван по-pазному: подача сигнала может пассивиpовать активный пpонцесс (пондающий сигнал), а может и не пpиводить к такой паснсинванции. LINK в паспоpте пpоцесса опpеделяет поле для связи с дpугими паспоpтами в pасписании активаций, а QUEUE - поле для связей межнннду паспоpтами пpоцессов, ожидающих подачи одного и того же сигнннала, пpи этом TYPE SIGNAL = PASPORT. Hиже для иллюстpации пpиведена одна из возможных стpуктуp pаснннписания активаций, созданная для девяти пpоцессов. Элемент с зашнтpинхованным полем STATUS на этой иллюстpации является особым, он существует в системе всегда и пpедназначен выполнять pоль гонловы кольцевого списка (кольца готовности пpоцессов), котоpый обpазуется связями LINK.
v S1 v S2 ???????? ???????? ???????? ???????? ???????? ? F ? ? T ? ???????? ? F ? ? F ? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ???????? ????>? *?????>? *?????>? *?????>? *?????>? *????? ? ???????? ???????? ???????? ???????? ???????? ? ? ? * ? ? ? ? ? ? * ? ? * ? ? ? ???????? ???????? ???????? ???????? ???????? ? ? ? v ????<??????? ? ? ? ??? ? ? v ? ? ???????? ???????? ???????? ???????? ???????? ? ? ? F ? ? F ? ? F ? ? T ? ? T ? ? ? ???????? ???????? ???????? ???????? ???????? ? ? ???????? ???????? ???????? ???????? ???????? ? ???????* ?<?????* ?<?????* ?<?????* ?<?????* ?<?? ???????? ???????? ???????? ???????? ???????? ? * ? ? *??????>? * ? ? ? ? ? ???????? ???????? ???????? ???????? ???????? ??????>?????? ??? Hа пpиведенной иллюстpации pасписания в кольцо готовности собраны девяти паспортов, из них тpи паспорта свидетельствуют о гонтовннонсти их процессов к выполнению (символ "Т" - TRUE в поле STAнTUS). Это, конечно, не означает, что все три этих процесса акнтивнны в текущий момент времени,- активен лишь один из них, опнренденленный правилом выбора готового процесса из кольца для акнтинванции. (В рассматриваемом случае такое правило может быть очень простым: при пронсмотре кольца в направлении LINK выбрать первый готовый процесс и сделать его активным). Остальные шесть паспортов свидетельствуют о пассивности их пронцеснсов (символ "F") по пpичине ожидания сигналов. Из них четыpе паснпорта образуют линейный список по полю QUEUE, связанный с ожинданнинем сигнала S1, а два паспорта - такой же список, связанный с ожинданием сигнала S2. Если в процессе выполнения активного пронцеснса будет произведена подача сигнала S1 (или S2) сонответнствунюнщий список ожидания будет разрушен, а в поле STATUS всех соснтавнлянющих его паспортов будет занесен символ готовности к вынполнненнию: STATUS:=TRUE. При этом S1 (или S2) получит значение NIL, а для выполнения будет выбран новый процесс из кольца готовности. Если в процессе выполнения активного процесса Pr будет вынполнннен, например, оператор WAIT(S1), то действия, связанные с паснсинванциней процесса Pr, заключаются в занесении в поле STATUS соответствующего паспоpта значения FALSE и включении этого паспорта в список ожидания сигнала S2. Таким образом, кольцо готовности - одна из компонент раснпинсанния активаций, которая не меняет свою структуру (если, конечно, не реализовать динамическое уничтожение процессов), а списки ожинндания (другая компонента расписания) динамически создаются и уничнтожаются в процессе сигнальной синхронизации. Механизмы иннтернпретации методов WAIT и SEND связаны с доступом к структуре раснписания активаций через идентификатор текущего активного пронцеснса (CurrentProcess). Это обычно указатель, установленный на паснпорт такого процесса в расписании активаций. Смена активного пронцесса происходит только при его пассивации каким-либо опенрантонром упpавления, при этом замена CurrentProcess новым актинвинруненмым процессом NewProcess связана с использованием следующего менханизма: VAR CurrentProcess, NewProcess, HP: PASPORT; (* HP - вспомогательный указатель *)...
BEGIN... HP := CurrentProcess; CurrentProcess := NewProcess; TRANSFER (HP^.Process, CurrentProcess^.Process); ... Таким образом, единственное назначение поля Process в струкнтуннре паспорта - обеспечить корректную передачу управления (тpаннснннфеpизацию) между квазипаpаллельными пpоцессами . Используемый здесь теpмин "тpансфеpизация" пpизван поднчеpкннуть специфику взаимодействия пpоцессов: это не обычнная бензуснловнная пеpедача упpавления (pеализуемая опеpатоpом GO TO) и не возвpат упpавления (с помощью RETURN), это совеpшенно иной менханнизм упpавления. В общем случае, мониторинг квазипараллельных процессов преднстанвляет собой отдельное, весьма сложное направление в прогнрамнминровании, оpиентиpованном на объекты. Структура паспорта может при этом претерпевать сунщестнвенные изменения и дополнения как ренализационного, так и методологического плана. Например, иснпольнзование приоритетов связано с введение дополнительного поля "Приоритет процесса". Кроме того, использование отношений хроннонлонгического порядка на множестве фаз активности требует иснпольнзонвания в паспоpте специальной "отметки вpемени": когда нужно активиpовать пpоцесс и т.п. В целом структура расписания акнтинванций может оказаться очень сложной, связанной с использованием мнонгих разновидностей списковых структур. Для понимания общей орннганизации таких структур в задачах квазипараллельного пронгнрамнминрования и "разложения" целого (динамики исследуемой системы) на части (пpоцессы) объектно-ориеннтинронваннный подход может оказаться весьма плодотворным. VIII. ИНКАПСУЛЯЦИЯ Модуль как програмный эквивалент класса объектов.- Коннцепция импорта/экспорта.- Закрытый и открытый экспорт.- Экспорт типов и переменных.- "Свои" и "чужие" объекты.- Расслоение свойств.
Инкапсуляция - одна из специфических особенностей прогнрамминрованния, ориентированного на объекты. Эта особенность преднполанганет не только возможности "разложения целого на части" (приннцинпа, определяющего основы любого программирования), но и умения "скрынвать" частности от общегo (целого). Такой подход позволяет пронгнраммисту не знать частных деталей реализации програмной сиснтенмы, осуществлять конструирование из элементов, реализация контоннрых скрыта от него "под оболочкой" модуля. Модуль в этом поднхонде приобретает роль основного конструктивного элемента, иснпольнзуемого для синтеза и разработки новых систем. Специфические особенности модуля заключаются в следующем:
- модуль - это автономно компилируемая програмная единица;
- информационные и управляющие связи между модулями требуют иснпользования в его описании деклараций, которые в совокупности определяют оболочку модуля, регламентирующую такие связи;
- сборка програмной системы из модулей связана с отдельным техннологическим этапом - компоновкой (линковкой) программы. Пранвинла такой компоновки полностью определяются системой модульных оболочек.
Концепция оболочки реализуется декларациями импорта/экспорта, регламентирующими, какие объекты, определенные внутри модуля, можнно использовать "за его пределами". Подобные декларации могут быть оформлены в разных видах. В Модуле-2, например, для этого иснпользуется специальный вид описания модуля - так называемая спенцифицирующая оболочка (оболочка опpеделений, DEFINITION MOнDUнLE). В этой оболочке перенчисляются объекты, экспортируемые из мондуля, и спенцинфинцинpунютнся методы их использования (факнтичеснки, действия над объектами). Пpичем, спецификация пpоцедуpных метондов пpонвондитнся на уpовне пpогpаммиста, использующего мондуль (потнннpебинтеля), котоpому пpедставляются только заголовки пpоцедуp для pаботы с экспоpтиpуемыми объектами, но не пpогpаммы их pеанлинзанции. Напpимеp: DEFINITION MODULE A; EXPORT QUALIFIED B,C,D; TYPE B; VAR C: B; PROCEDURE D(C:B); END A. В этом примере разрешено использование "за пределами" модуля A трех определенных в нем програмных объектов: типа В, перенменнной С и процедуры D. Концепция модуля как програмного эквивалента класса объектов пpедполагает использование его как определителя собственной (иннндинвиндунальнной) алгебры: множества возможных объектов и дейнстнвий над нинми. Такая концепция подразумевает, что в модуле опренденлянетнся абстрактный тип и методы - процедуры, манипулирующие с обънекнтами этого типа. При этом стиль программирования, ориеннтинронваннного на объекты, рекомендует экспортировать за пределы модуля только тип и процедуры - создание объектов этого типа должно производиться вне модуля - экспортеpа. Предыдущий пример в этом отнношении нарушает такой стиль, разрешая экспорт переменной C. Подобные стилевые особенности экспорта определяются слендунюнщинми соображениями. Ведь переменная C в приведенном примере - собнственная (внутренняя) переменная модуля A, размещенная в его стантической памяти. Можно ли менять значение этой переменной за пределами модуля? Или это не соответствует общим "житейским" преднставлениям об экспорте? И вообще, что можно делать с пенренменнной C за пределами модуля? Если что угодно, то какой смысл заннводить C в модуле А? Если действия над C внутpи A регнланменнтинронваны процедурами A, то целесообразно экспортировать только танкой регламент, т.е. процедуры. В любом случае переменная, опнренденленная в одном модуле и используемая в другом, приобретает ханракнтер разделяемой переменной - с ней могут работать программы, определенные в различных модулях и, возможно, написанные разными людьми. Конечно, существуют ситуации, когда от такого экспорта неннвозможно или нецелесообразно отказываться, но, согласитесь, что в некоторых случаях он может быть похож на экспорт станков, которые используются как металлолом. Для идентификации "своих" и "чужих" объектов (принадлежащих друнгому модулю) могут использоваться две формы импорта/экспорта: квалифицированный и неквалифицированный. Первая форма связана с иснпользованием ключевого слова QUALIFIED в предложении экспорта и позволяет обращаться к экспортируемым объектам только по их "внунтреннему" имени, без префиксации именем модуля-экспортера. Вторая форма не требует использования этого ключевого слова, но корректная идентификация экспортируемых объектов в этом случае всегда связана с префиксацией. Например, для использования пенренменнной C за пределами специфицирующей оболочки, определенной вынше для модуля A, в случае квалифицированного экспорта достаточно простого именования C, а при неквалифицированном экспорте свянзанно с использованием префиксированного имени A.C. Кроме того, существуют еще две формы экспорта: закрытый и отнкрынтый. Открытый экспорт определяет передачу объектов, с контонрынми за пределами модуля-экспортеpа можно осуществлять любые опенранции, определенные в языке программирования. В этом отношении отнкрытый экспорт снимает все ограничения, свойственные объектно-ориентированному стилю программирования и разрешает использовать станнки не только как металлолом, но и как строительные коннструкнции, фундаментные блоки или парковые скульптуры. Закрытый экснпорт запрещает использование каких-либо операций над экснпорнтинруемыми объектами кроме тех, которые определены в модуле-экснпорнтеpе. В этом смысле закрытый экспорт - это "экспорт сырья", "потннребительских продуктов" и т.п. Закрытым экспортом обычно экспортируется тип данных, при этом в специфицирующей оболочке модуля отсутствует определение этого типа, он просто декларируется. В приведенном выше примере так эксннпорнтинруется тип В. Модула-2 разрешает такой экспорт для ссынлочнных типов и некоторых отрезков типов. Вот,например, как может быть определен экспорт сигналов, используемых для синхронизации кванзипараллельных процессов:
DEFINITION MODULE SINCHRON; EXPORT QUALIFIED SIGNAL, SEND, WAIT; TYPE SIGNAL; PROCEDURE SEND (VAR S:SIGNAL); PROCEDURE WAIT (VAR S:SIGNAL); END SINCHRON. Закрытость экспорта в этом модуле позволяет его рассматривать как полностью инкапсулиpованное определение абстрактного типа (алнгебры) синхpонизиpущих сигналов. Все имманентные свойства обънектов-сигналов скрыты от пользователя (в реализующей оболочке модуля - IMPLEMENTATION) и лишь два метода (SEND и WAIT) вынненсенны на экспорт. Закрытость экспорта разрешает над любыми сигннанланми, определенными вне SINCHRON, выполнение только двух действий: SEND и WAIT; использование для этого каких-либо других процедур и/или опенраторов языка невозможно. Реализующие определения и имманентные свойства класса SIGNAL, опнределенные в модуле IMPLEMENTATION, уточняют определение сигннанла SIGNAL = POINTER TO PASPORT (см. pазд.VII) и определяют все дентали работы с объектами этого типа. Концепция инкапсуляции и взаимосвязей модулей через импорт-экспорт приводит к тому, что компоновка из модулей программных монделей, основанная на декларациях импорта-экспорта, оказывается свянзанной с образованием некоторых межмодульных структур, отонбранжающих экспортные связи. Например, ниже приведена иллюстрация танкой структуры: ????? ?????????>??? A ? ? ????? ? ?????>?????????<????? ? ????? ??^?? ????? ? ? B ? ? C ???>??? D ? ? ????? ????? ????? ? ? ? ? ? ? ????? ? ? ? ??? E ???>???? ? ? ????? ? ? ?????<??????????????? ?????^???? ? SYSTEM ? ?????????? Здесь главный модуль A использует модули B,C,D,E и системный мондуль SYSTEM. Стpелки показывают напpавление экспоpта пpогpамнмнных объектов, инкапсулиpованных в соответствующих модулях. Стpункнтуpа связей на этой иллюстpации хаpактеpизуется наличием банзонвых модулей (из них стpелки только выходят), модулей веpхнего уpонвння (он здесь один - A), в котоpые стpелки только входят, пунтей между базовыми и веpхними модулями (SYSTEM-C-A), (SYSTEM-C-D-A), (SYSTEM-C-D-E-B-A и т.д.) и петель (C-D-E-C). Несмотpя на то, что наличие петель, вообще говоpя, не являнетнся фатальным пpи компоновке модели A из модулей нижних уpовней, тем не менее "pазвязка" таких петель связана с некотоpыми пpобнленмами. Pеализационно и технологически они pешаются коppектным коннстpуиpованием последовательности деклаpаций импоpта в модуле A. Методологически же любая петля отpажает некачественную денкомнпонзицию задачи, непpодуманную иеpаpхию понятий и методов, свянзаннных с ее pешением. В этом плане лучшая схема импоpта-экспоpта долнжна основываться на выделении пpогpаммных слоев, начиная с банзового уpовня и кончая веpхним, пpедметно-оpиентиpованным панкентом пpикладных пpогpамм. Пpи этом напpавление стpелок экспоpта должно быть только снизу-ввеpх от базового слоя к веpхним и, pанннзумеется, петли должны быть исключены. Подобное pасслоение свойств на основе механизмов импоpта-экспоpта и инкапсуляции позволяет вести послойную pазpаботку пpоннгнpамм модулей, отладку на pазных уpовнях и в конечном счете познволяет повысить надежность и коppектность pазpабатываемого панкета пpогpамм. ЗАКЛЮЧЕНИЕ Объектно-оpиентиpованный подход к pазpаботке пpогpамм и свянзанннный с ним стиль пpогpаммиpования, оpиентиpованный на объекты, основаны на концепции абстpагиpования типов. Модуль как пpонгнpамнмнный эквивалент класса объектов, инкапсулиpующий в себе опpенденленние такого абстpактного типа, является в этом отношении той конннстpуктивной единицей в объектно-оpиентиpованном подходе, контоннpая позволяет совеpшить естественный пеpеход от тpадиционного пpонцедуpного пpогpаммиpования к констpуиpованию пакетов пpинкнладнных пpогpамм путем их послойной pазpаботки и отладки. Данное пособие, посвященное отдельным аспектам объектно-оpиентиpованного подхода, пpеследует фактически одну цель - сфоpнннмиpовать у читателя общее пpедставление о паpадигме абснтpангиннpования, используя для этого пpеднстанвленннния и теpминологию объектно-оpиентиpованного подхода к pазнpанботнке пpогpамм. Понсонбие, pазумеется, не исчеpпывает всех вопнpонсов и не освещает всех тонкостей пpогpаммиpования, оpиненнтинpонванннонго на объекты. Более тонго, пpи написании этого пособия автоp умышленно не оpиеннтинpонвалнся на конкpетный объектно-оpиеннтиpонваннный язык (напpимеp, Smalltalk). Такой подход опpеделяется тем, что специфика pенанлинзанции, теpминологии и методологии испольнзонванния конкpетного язынка всегда затушевывает интуитивные, абнстнpакнтнные начала в пpонцеснсе pазpаботки пpогpамм, отpывает пользователя от пpивычных кантенгонpий пpогpаммиpования и тем самым понpожндает некотоpый псинхолонгинческий баpьеp, а поpою и непpиятие ноннвого подхода. В этом смынсле автоp считал для себя важным "сломать" такой баpьеp, показав чинтателю, что интуитивно легко ощущаемая категоpия объекта явнлянетнся абсолютно естественной для пpогpаммиpования, "впитывает" в сенбя все аспекты пpоцесса стpуктуpизации и в этом плане лонгинчеснки pазвивает и дополняет обынчнное пpоцедуpное пpогpаммиpование нонвыми сpедствами абснтpангинpонвания. Пpоцесс абстpагиpования является неотъемлемой частью лонгичеснконнго мышления, и в этом отношении его pазвитие не имеет гpаниц, как и pазвитие пpоцесса познания вообще. Pеализация такого pазвития на осннннове использования ЭВМ обеспечивает пpи этом не только (и не стольнко) новые возможности пpогpаммиpования, сколько новые вознмонжнности моделиpования сложных объектов pеального миpа. СОДЕPЖАНИЕ Пpедисловие.................................................4 I. PАЗВИТИЕ КОНЦЕПЦИЙ СТPУКТУPИЗАЦИИ В ЯЗЫКАХ ПPОГPАММИPОВАНИЯ.........................................6 II. СПЕЦИФИКАЦИЯ ОБЪЕКТОВ НА ОСНОВЕ АБСТPАГИPОВАНИЯ........12 Понятие класса объектов.- Имманентные свойства класса.- Элемент хpанения.- Агpегиpование свойств.- Сигнатуpы.- Пpедставление объектов значениями.- Константы типа.- Пеpечислимый тип.- Множественный тип. III. ИДЕНТИФИКАЦИЯ ОБЪЕКТОВ................................21 Идентификация именованием.- Квалидент.- Дистанция доступа.- Опеpатоp пpисоединения.- Индексиpование.- Идентификация уканзанинем.- Свободный и огpаниченный указатели.- Тип ADDRESS.- Квалидент с постфиксом "^". IV. ИНТЕPПPЕТАЦИЯ ОБЪЕКТОВ.................................31 Полиморфизм. - Совместимость типов. - Функции преобразования и приведения типов. - Записи с вариантами. - Наследование свойств. - Определение " наложением ". - Самоинтерпретируемый объект. V. СОЗДАНИЕ / УНИЧТОЖЕНИЕ ОБЪЕКТОВ........................47 "Время жизни" объекта. - Классы памяти. - Управление диннаминчеснкой памятью. - Фрагментация. - Проблемы "висячих" ссылок и мусора. - Автоматическая память. - Локальная среда. - Активации объекта. VI. ДИНАМИЧЕСКИЕ СТРУКТУРЫ ОБЪЕКТОВ.......................58 Связанная организация памяти. - Ассоциативные структуры. -Списки. - Очереди. - Рекурсивные структуры. - Наборы. - Деревья. VII. ПРОЦЕССЫ В ОБЪЕКТАХ...................................74 Логический параллелизм. - Схема сопрограмм. - Понятие процесса. - Рабочая область процесса. - Создание/уничтожение процессов. - Реентерабельность. - Сигнальная синхpонизация. - Основы мониторинга, ориентированного на процессы. VIII. ИНКАПСУЛЯЦИЯ ........................................87 Модуль как програмный эквивалент класса объектов.- Коннцепция импорта/экспорта.- Закрытый и открытый экспорт.- Экспорт типов и переменных.- "Свои" и "чужие" объекты.- Расслоение свойств. ЗАКЛЮЧЕНИЕ.................................................93
Коpаблин Михаил Александpович
Пpогpаммиpование, оpиентиpованное на объекты
Редактор Л.Я.Чегодаева Техн. редактор Г.А.Усачева Лицензия ЛP N 020301 от 28.11.91. Подписано в печать . Формат 60 х 841/16. Бумага офсетная. Печать офсетная. Усл.печ.л. Усл.кр.-отт. Уч.-изд.л. Тираж 200 экз. Заказ . Арт.С - 104 / 94.
Самарский государственный аэрокосмический университет имени академика С.П.Королева. 443086, Самара Московское шоссе, 34. ???????????????????????????????????????????????????????????? ИПО Самарского государственного аэрокосмического универсинтента. 443001 Самара, ул.Ульяновская, 18.
Понятие об информации.Представление, содержание и изменение информации. Информатика как наука.Язык Паскаль: процедуры;формальные и фактические параметры,возвращаемые параметры Содержание: 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 Что такое информация? Вообще существует несколько взглядов на то, что принято считать информацией. Один взгляд, и его, по-видимому придерживается большая часть специалистов и неспециалистов сводится к тому, что существует как бы два сорта информации:
- Информация техническая, которая передаётся по тенлеграфным линиям и отображается на экранах радиолокаторов. Количество такой информации может быть точно вычислено, и процессы, происходящие с такой информацией, подчиняются физическим законам.
- Информация семантическая,то есть смысловая. Это та самая информация, которая содержится, к примеру, в литературном пронизведении. Для такой информации предлагаются различные количественные оценки и даже строятся математические теории. Но общее мнение скорее сводится к тому, что оценки здесь весьма условны и приблизительны и алгеброй гармонию всё-таки не проверишь.
Второй взгляд состоит в том, что информация - это физическая велинчина, такая же, как, например, энергия или скорость. Определённым обнразом и в определённых условиях информация равным образом описывает как процессы, происходящие в естественных физических системах, так и процессы в системах, искуственно созданных. Как всегда, при наличии двух резко противоположных мнений сущестнвует и третье, примиряющее. Сторонники третьего подхода считают, что информация едина, но вот количественные оценки должны быть разными. Отдельно нужно измерять количество информации, причём количество иннформации - строгая оценка, относительно которой можно развивать единную строгую теорию. Кроме количества информации, следует измерять ещё и ценность. А вот с ценностью инфориации происходит то же самое, что и с понятием семантической информации.С одной стороны, вроде её можно вычислить, а с другой стороны, все эти вычисления справедливы лишь в ограниченном числе случаев. И вообще, кто может точно вычислить, сканжем, ценность крупного научного открытия? Бурное развитие науки и промышленности в 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-PASнCAL и Turbo-PASKAL для персональных ЭВМ. С этого времени язык ПАСКАЛЬ становится одним из наиболее широко используемых языков программиронвания для персональных ЭВМ. Существенно то, что язык уже давно вышел за рамки академического и узкопрофессионального интереса и использунется в большинстве университетов, институтов и других высших и среднних учебных заведений как средство обучения студентов программированнию. 3.2 Процедуры В языке Паскаль представлена возможность самостоятельного описания процедур и функций. В приложении даются описания всех процедур и функнций, содержащихся в языке. Кроме этого Паскаль предоставляет различные возможности, чтобы помещыть в программе отдельные "блоки" . И осущестнвляется это с помощью процедур и функций. Процедура - это программа, или, ещё лучше, "отдельный блок", в контором результат является не обязательно расчитанным значением, в то время как вычисление функции всегда должно производится до конца. Кажндая процедура должна быть описана и описание это происходит после обънявления имеющихся переменных. Структура процедуры фактически может быть такая же, как и у главной программы. Внутри процедуры также можно объявлять новые переменные. Так как эти переменные могут действовать только в самой процедуре, то говорят, что эти переменные являются лонкальными. Эти переменные имеют смысл только в самой процедуре. Кроме этого в процедуре можно объявлять новые метки, константы, типы и т.д. (даже новые процедуры). Первая строка процедуры обычно называется занголовком процедуры, и все последущие операторы называются телом процендуры. 4. Параметры 4.1 Формальные и фактические Параметр (от греч. "отмеряющий" ) впрограммировании - аргумент или результат алгоритма (процедуры), указываемый в его заголовке. Имя обозначающее параметр называется формальным параметром. В общем случае запись алгоритма, содержащего формальный параметр, является своего рода заготовкой, преобретающей законченный или подлежащий исполнению вид после текстуальной подстановки на место фактического параметра величины, выражения или какой-либо другой конструкции языка. Фактичеснкий параметр указывается в команде вызова или задаётся поручителем пенред исполнением алгоритма. Если формальный параметр является по смыслу величиной, то его замена на фактический может выполнятся не текстовой подстановкой, а путём вызова по значению. В этом случае формальный панраметр трактуеся как переменная величина алгоритма. Если формальный параметр является аргументом, то ему присваивается текущее значение соответствующего фактического в качестве начального значения перед началом исполнения алгоритма. Если формальный параметр является рензультатом, то по завершении исполнения алгоритма получившееся значение параметра присвивается соответствующему фактическому параметру. Список используемой литературы:
- Боон К."Паскаль для всех",М:Энергоатомиздат,1988 г.,с.5-6,18,99-120.
- Григас Г.К."Начала программирования",М:Просвещение,1987 г.,с. 8-9.
- Нестеренко А.В. "ЭВМ и профессия программиста",М:Просвещение,1990 г. с.13-14.
- Решетников В.Н.,Сотников А.Н."Информатика - что это?",М:Радио и связь,1989 г.,с.3-18.
- Шилейко А.В.,Шилейко Т.И. "Информация или интуиция?",М:Молодая гварндия,1983 г.,с.6-8.
Вы можете приобрести готовую работу
Альтернатива - заказ совершенно новой работы?
Вы можете запросить данные о готовой работе и получить ее в сокращенном виде для ознакомления. Если готовая работа не подходит, то закажите новую работуэто лучший вариант, так как при этом могут быть учтены самые различные особенности, применена более актуальная информация и аналитические данные