автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы оптимизации при реализации объектно-ориентированных языков

о

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи

ПЛИСС Олег Анатольевич

МЕТОДЫ ОПТИМИЗАЦИИ ПРИ РЕАЛИЗАЦИИ ОБЪЕКТНО-ОРИЕНТИРОВАННЫ? ЯЗЫКОВ

¡пециальность 05.13.11 - Математическое и программное обеспечение

вычислительных машин, комплексов, систем и сетей

АВТОРЕФЕРАТ диссертации ва соискание ученой степени кандидата физико-математических наук

САНКТ-ПЕТЕРБУРГ 1992

Работа шголненз на кафедре математического обеспечения Э-математико-механического факультета Санкт-Петербургского университета.

Научный руководитель: доктор физико-математических наук Цейтин Г.С.

Официальные оппоненты: доктор физико-математических наук Баранов С.Н. кандидат физико-математических наук Кириллин В.А.

Ведущая организация: Санкт-Петербургский государственный технический университет.

¿о'

Защита состоится апреля 1992 г. в часов на заседали специализированного совета К 063.57.54 то присуждении ученой сте пени кандидата физико-математических наук в Санкт-Петербургско университете то адресу:

198904, Санкт-Петербург, Старый Петергоф, Библиотечная пл., д.2.

О диссертацией можно ознакомиться в Научной библиотеке им Горького Санкт-Петербургского университета.

Автореферат разослан "{£' 1992 г.

:,ешй секретарь специализированного физико-математических наук, доцент.

совета, квндиде Кубенский А .У

.. .-ежа»

-Ч - 3 -

«М1 ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

)Т*ЦИЙ _

—~ЧАктувльность проблемы. В настоящее время объектно-ориентированный подход является одним из наиболее перспективных направлений в программировании. К числу преимуществ данного подхода относят естественную методологию программирования, формулировку решений в терминах, близких области приложения, гармоничное включение развитого дружественного интерфейса с пользователем, концептуальное единство и небольшое число основных конструкций, абстракции данных, открытость, легкую расширяемость, универсальность и высокую повторную используемость создаваемых модулей. В числе недостатков современных систем объвктно-ориентиро.ванного программирования обычно отмечают сравнительно низкую эффективность получаемых программ, трудности отделения конечного программного продукта от системы разработки и значительные требования, предьлдля-емые к инструментальному оборудованию.

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

При реализации объектно-ориентированных языков возникает ряд специфических трудностей, в т.ч. представление объектов, синтез структур данных, разделение кода наследованных операций, динамическое связывание и т.п. В разных системах предлагаются различные пути их преодоления. Имеется необходимость сравнительного исследования различных подходов в зависимости от требований, предъявляемых к системе разработки и конечному программному продукту, особенностей оборудования, сильной или слабой типизации языка и использования наследования, мультинаследования, делегирования ли-Зо мулътиделегирования.

Цель настоящей диссертационной работы состояла в разработке штодики эффективной реализации объектно-ориентированных языков, основанной на оригинальном подходе к извлечению статгческой информации из объектно-ориентированных программ, использовании ее

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

Методика исследования. Для достижения поставленной цели необходимо было исследовать методологические особенности объектно-ориентированного подхода, препятствующие применении полной статической типизации и обусловливающие специфические требования, предъявляемые к реализациям объектно-ориентированных языков. При втом учитывался опыт существующих систем. Теоретические разработки проверялись посредством реализации в модельной системе на базе Форта. '

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

система МЕОШМ.

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

Апробация работа. Результаты работы докладывались на заседаниях и научных семинарах кафедры математического обеспечения ЭВМ математико-механического факультета СПбУ.

Публикации. По теме диссертации опубликованы 3 научные статьи.

. Объем и структура диссертации. Диссертационная работа состоит из введения, пяти глав, разделенных на параграф!, заключения, включающих в себя 35 рисунков и одну таблицу, списка литература из 91 наименования и двух приложений. Объем основной части диссертации (без приложений) составляет 146 страниц- машинописного текста.

СОДЕРЖАНИЕ РАБОЙ

Во введении дан краткий обзор состояния дел в области объек-гш-орзентированного программирования, проанализированы проблемы, юзникающие при реализации объектно-ориентированных языков и дос-игнутые успехи в их разрешении. Сформулированы цели и перечислв-ы основные результаты диссертационной работа в соответствии с ее [елением по главам.

- б -

Первая глава посвящена подробному изложению основных концепций и анализу проблем реализации объектно-ориентированных языков.

Объектно-ориентированный подход базируется на представлении аадачи как ситуации в мире дискретных взаимодействующих объектов. Каждой объект характеризуется набором свойств - реакций на внешнее воздейстр*'.е. Для того, чтобы подействовать на объект, нужно послать ему соответствующее сообщение, задаваемое именем (селектором) и, если это необходимо, набором объектов-параметров. Имя определяет воздействие качественно, параметры варьируют его количественно. Объект может быть либо атомарным (неделимым с точки зрения системы), либо композитным (состоящим из набора объектов-компонент). Прямой доступ к компонентам возможен лишь со стороны включающего их в себя объекта. В ответ на корректную посылку сообщения активируется соответствующая реакция (метод) объекта-получателя, который может изменить свое внутреннее состояние, послать сообщения себе, своим компонентам, параметрам либо известным ему по имени глобальным объектам, воспользоваться результатами этих сообщений и выдать полученный таким образом результат.

Для обработки не известных объекту-получателю сообщений вводится механизм передачи полномочий - делегирования. Каждый объект может иметь одного или нескольких предков, которым в случае собственного затруднения передает сообщение для ответа. Ситуация, в которой ни один из прямых или дальних предков не оказывается в состоянии ответить на сообщение, рассматривается как ошибочная.

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

Для организации посылки сообщений с каждым объектом связывается описатель, определяющий полный набор воспринимаемых данным объектом сообщений вместе с соответствующими операциями и, возможно, разнообразные системные данные - размер и структуру памяти и т.п. Если система обладает рефлексивными свойствами, описатель также является объектом.

Заметим, что объект в течение своей жизни может менять своих предков, но не описатель. В большинстве объектно-ориенти- рован-ных систем предполагается, что описатель константен - объект не меняет набора собственных сообщений и системных характеристик.

Таким образом, объект представляется некоторым количеством памяти для хранения изменяемых параметров своего поведения и неизменным описателем. В том случае, если два объекта имеют одинаковые описатели, имеет смысл их объединить. Объекты, связанные с одним и тем же описателем, называются однородными.

Альтернативный подход базируется н» на одиночных объектах, а на классах однородных объектов. Над множеством классов вводится отношение типа "многие к одному", определяющее преемстзенность свойств. Класс, из которого наследует свойства данный класс, называется надклассом данного класса. При этом данный класс является подклассом своего надкласса. Объекты, принадлежащие одному классу, именуются экземплярами этого класса. Класс, который не может иметь своих экземпляров, называется абстрактным. Классы, связанные отношением наследования, образуют древовидную иерархическую структуру. Самый старший класс обычно является абстрактным и задает минимальный набор свойств, которыми должны обладать все объекты в системе.

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

В рефлексивных системах классы также являются объектами. Классы классов обычно называют метаклассами.

. Мультинаследование вводится как обобщение наследования на случай нескольких надклассов. Непрямое мультинаследование, однако, в некоторых ситуациях поровдает ряд семантических неоднозначностей и реализационных трудностей.

Деление на классы и наследование имеют технологический, концептуальный и реализационный аспекта, связанные соответственно с выделением модулей, классификацией понятий предметной области синтезом структур данных и реализаций операций по декларациям, содержащимся в определяемом классе и всех его надклассах.

Обсуждаются методологические основы определения системы классст, взаимосвязь классов и абстрактных типов танных, различные стороны взаимоотношений наследования и делегирования.

В том случае, если обеспечен полный статический контроль типов, при реализации объектно-ориентированных языков пс сравнению с языками АТД не возникает дополнительных трудностей, кроме обес-

печения применимости операций к расширенным структурам данных. Однако объектно-ориентированное программирование с самого начала (Смолток) ассоциируется с инкрементным подходом и рефлексией.

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

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

При реализации объектно-ориентированных систем возникают следующие специфические трудности.

1.Выбор представления объекта

Каадая из переменных может содержать значения произвольных классов, вследствие чего все объекты вместе с информацией об их классах должны быть представлены идентификаторами заведомо ограниченного размера.

2.Воссоздание структуры объекта данного класса по его собственным и наследованным из цепочки надклассов описаниям.

3.Организация разделения кода наследованных операций

4.Отложенное связывание

5.Интенсивное использование "кучи"

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

производительности труда программиста. Требование слабой машинной зависимости обусловлено доступностью структуры порождаемого кода.

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

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

Каждая отдельно взятая объектно-ориентированная программа может быть статически типизирована, если в качестве типов использовать наборы классов. В том случэе, если этот подход осуществляется непосредственно программистом, он крайне трудоемок, опасен труднообнаружимыми ошибками и неустойчив по отношению к внесению изменений в систему классов и наборы методов в них. Предлагается во время отделения конечного программного продукта автоматически вычислять типы на основе информации, извлекаемой из программы и дсполнительных ограничений, указываемых по желанию программиста. Вместо того, чтобы каждому объекту сопоставлять единственную исчерпывающую декларацию, с объектом ассоциируется лишь частичное описание его свойств, остальная же часть его поведения специфицируется контекстами его использования. Здесь мы имеем ¿чло с большим числом слабых контекстно зависимых ограничений, которые в

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

Обсувдаются проблемы проверки внутренней непротиворечивости ограничений и их соответствия программе и требования, которым должна удовлетворять реализация типового анализа.

Для корректного описания предложенного подхода вводится вычислительная модель, объемлпцдя достаточно широкий класс языков, включая Смолток и различные варианты объектно-ориентированного Форта.

Для указания ограничений предлагается несложный язык, описанный в БШ. Имеется возможность накладывать ограничения на значения переменных и параметров, эффекты посылки сообщения с заданным селектором, эффекты конкретного метода, промежуточные результаты и эффект отдельного вызова. В качестве ограничений для каждого из элементов могут использоваться принадлежность набору классов или подклассов, применимость нескольких указанных операций и эквивалентность известному элементу. Последнее применяется для определения классов выходных параметров через классы входных. Отсутствие ограничения трактуется как принадлежность произвольному классу, совпадение типов - как принадлежность одному и тому же набору классов, эквивалентность - принадлежность соответствующих элементов одному и тому же классу в любой момент исполнения программы.

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

Типовой анализ объектно-ориентированной программы произво-

дится в четыре этагГа, первые два из которых могут быть совмещены во времени.

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

Динамическое связывание осложняет нахождение минимального набора необходимых программных единиц. Корректное, но довольно грубое приближение может быть получено следующим образом: по тексту основной программы определяется набор селекторов вызываемых процедур, этот процесс повторяется рекурсивно для всех процедур с данными селекторами. Качество выбора влияет на время и память, требуемые для трансляции.

Ограничения, играющие роль типовых выражений, переводятся в термины множеств классов. По окончании этого процесса вплоть до стадии генерации кода особенности наследования не используются.

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

На второй стадии набор эффектов каждого из селекторов заменяется на объединение эффектов всех методов с данным селектором. За счет этого может быть получено уточнение эффектов селектора.

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

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

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

Показано, что время, требуемое для типового анализа, растет пропорционально не более чем квадрату длины программы.

Традиционным применением мягкого типового анализа является обнаружение во время компиляции ошибок несогласования типов при передаче параметров.

Часто контекст вызова позволяет однозначно идентифицировать процедуру по ее имени. Таким образом, большая часть динамических связываний может быть заменена на статические.

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

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

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

1) Удаление недоступных ветвей. В случае типовых ветвлений недоступные фрагменты программы не включаются ни в одну из траекторий и, соответственно, исключаются автоматически на этапе генерации кода.

2) Расщепление. Полученные для каждой программной единицы траектории не содержат в себе типовых ветвлений и могут считаться строго типизированными. По каждой из них может быть сгенерирован

код с применением традиционных методов оптимизации. Универсальная процедура. заменяется на минимально необходимое для данной программы семейство специализированных процедур, которые выбираются в зависимости от контекста вызова.

3) Склейка. В тех случаях, когда траектории отличаются незначительно, может быть осуществлена их склейка в одну. В результате за счет введения небольшого числа типовых ветвлений может быть исключен значительный объем дублирующего кода.

Менее очевидно влияние типовой информации на оптимальность представления даш. лс. Если класс всех представителей некоторого класса может быть определен во время трансляции, предназначенные для динамической идентификации теги могут быть исключены. Например, статическая типизация целых приводит к значительному упрощению системы тегов.

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

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

Исследованы проблемы экономичного и эффективного синтеза структур данных и обеспечения разделения кода наследованных операций с учетом особенностей наследования, мультинаследования, делегирования и мультиделегирования. Для наследования разработаны простые механизмы, при использовании которых исключаются программные издержки. Ыультинаследование часто приводит к более сложным структурам дянтогг с менее аффективным доступом. Предлагаются пути цреодоления этих трудностей. При мультиделегировании возникают проблемы при связывании селектора с конкретным методом.

На основе критериев эффективности, затрат памяти, влияния добавления и исключения методов и изменения надклассов теорети-46 лш исследованы наиболее распространенные подходы к организации словарей и поиска в них - линейные списки, хеш-списки с фиксиро-

ванным числом нитей, частичные, и полные хеш-таблицы, полные и раскрашенные индексы, ассоциирование словарей методов с селекторами. Учтено влияние замещения и отвержения методов. По интегральному критерию (эффективность » затраты памяти) для системы разработки при одноклассовом наследовании лучшими являются хеш-списки и частичные хеш-таблицы. Для конечного программного продукта при использовании наследования и мультинаследования по критерию эффективности наиболее подходят полные хеш-таблицы, полные и раскрашенные индексы. В случае проведения строгого статического либо мягкого анализа раскрашенные индексы по всем существенным показателям часто оказываются лучшими, причем стоимость динамического связывания сводится к единственному обращению к памяти.

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

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

В пятой главе описана объектно-ориентированнёя система MEDIUM, построенная на базе Форта-83. Производится сравнение с аналогичными разработками.

В заключении обсуждаются полученные результаты и пути дальнейшего развития исследований в области повышения эффективности объектно-ориентированных систем.

В работе получены следующие основные результаты:

- предложен новый подход к типизации объектно-ориентированного языка;

- разработаны соответствующие алгоритмы типового анализа и методы использования полученной информации для раннего обнаружения ошибок несоответствия типов при передаче параметров, автоматического отделения конечного программного продукта и оптимизирующих преобразований программ;

- разработаны' экономичные схемы динамической идентификации объектов для широко распространенных ЭВМ о прямо адресуемой и сегментированной памятью;

- разработаны методы синтеза структур данных и разделения кода наследованных операций для систем о одно- и многоклассовым наследованием;

- дан сравнительный анализ различных способов динамического связывания на основе критериев еффективности, экономичности и устойчивости к внесению изменений для систем о наследованием, муль-тина следованием, делегированием и мультиделегированием.

- разработана отруктура компактного эффективно исполняемого ' олабо машинно-зависимого' кода;

- на основе ягыхз Форт создана .объектно-ориентированная система KEDBIK.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1.Плиоо O.A. Объектно-ориентированная система- MEDIUM // Инструментальные средства поддержки программирования. Л., 1968. 0.108-122.

г.Плиоо O.A.'Реализационные аспекты объектно-ориентированного

програм»»чрования / Деп. в ВИНИТИ, 1991. З.Плисо O.A. Мягкий типовой аналиа / Деп. в ВИНИТИ, 1991.