автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Система программ динамической поддержки для транслятора с алгола 68

АКАДЕМИЯ НАУК СССР Ордена Лепииа Сибирское отделение Институт систем информатики

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

РУХЛИН Алексей Павлович

УДК 681.3

СИСТЕМА ПРОГРАММ ДИНАМИЧЕСКОЙ ПОДДЕРЖКИ ДЛЯ ТРАНСЛЯТОРА С АЛГОЛА 68

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

) '

I

'л" > - '

/ Новсс-Ибирск 1991

Работа выполнена в НИИ Математики и Механики им. академика В.И. Смирнова Ленинградского государственного университета

Официальные оппоненты : доктор физико-математических наук

В.Н. Касьянов,

кандидат физико-математических наук В.И. Гололобов

Ведущая организация - Вычислительный центр АН СССР

Защита состоится ■ж-. 1001 года в 14 часов на

заседании Специализированного Совета при Институте

систем информатики СО АН СССР по адресу:

630090, Новосибирск, 90,проспект академика Лаврентьев, '6.

С диссертацией можно ознакомиться в читальном зале ГПНТБ СО АН СССР (пр. академика Лаврентьев, 6).

Автореферат разослан 1001 г.

Ученый секретарь специализированного совета

канд. физ.-мат. наук Сабельфельд В.К.

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

АКТУАЛЬНОСТЬ темы исследования.

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

программно-аппаратных сиситем, имеющих большое

народно-хозяйственное значение. Это oneделило выбор языка Алгол 68 в качестве основы помышленной технологии раэаботки больших программных систем реального времени,

математического обеспечения управляющих встроенных ЭВМ.

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

По сравнению с другими языками аналогичного уровня, такими как ПЛ/I, Ада, Модула 2, Паскаль, в Алголе 68

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

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

МЕТОДИКА исследований.

Большое разнообразие типов универсальных и

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

ЦЕЛЬ работы.

Цель работы состоит в разработке методов распределения динамической памяти для сложных значений и переносимой системы программ динамической поддержки г для новой многоцелевой (многомашинной) системы программирования на базе языка высокого уровня (АЯВУ) Алгол 68, разрабатываемой в НИИ Математики и Механики им.В.И.Смирнова в рамках госбюджетной НИР "Инструментальные средства промышленных методов разработки программного обеспечения" (Б.02.08).

НАУЧНАЯ НОВИЗНА результатов.

Разработана модель организации рабочей памяти программы на Алголе 68, единая для всех типов целевых ЭВМ, способ представления значений языка в памяти и структура трафаретов вида этих значений, общая для всех подпрограмм динамичесгсй поддержки и для всех типов ЭВМ, на которые рассчитана система программирования УЛЗС.

Проведена классификация основных подпрограмм

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

выстраивание, определене области действия, сборку мусора.

Предложена методика создания мобильных (переносимых) программ с использованием средств параметризации алгоритмов, присущих стандартному языку Алгол 68 (подмена описаний констант и видов, текстов операций и процедур), и особенностей используемой системы программирования №ВС (константные вычисления, условная генерация).

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

ПРАКТИЧЕСКАЯ ЗНАЧИМОСТЬ.

1.Реализованы полпрограммы генерации трафаретов видов значений Алгола 68, используемые в составе фазы синтеза ряда трансляторов с Алгола 68 коды различных ЭВМ.

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

3•Реализованы подпрограммы работы со слохноустроенными значениями Алгола 68.

й.Все подпрограммы перенесены с инструментальной ЕС ЭВМ на ЭБМ других типов (СМ ЭВМ, ПС-1001, IBM PC, "Самсон" и ряд специализированных управляющих ЭВМ),

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

6. Просмотр генерации объектного кода программ для ЕС ЭВМ является яэыковонезависимым пакетом процедур, его применение возмохноии осудествляется в ряде трансляторов с других языков, например FORTRAN 77, С, Pascal.

ОБОСНОВАННОСТЬ положений работы.

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

Сравнение времени исполнения рабочих программ, полученных различными трансляторами, подтверждает

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

АПРБАЦИЯ.

Результаты диссертации доложены II Всесоюзной конференции по методам трансляции (Новосибирск, 1981 г.), Всесоюзной конференции "Методы трансляции и конструирования программ" (Новосибирск, 1988 г.). Семинарам ИСИ, ВЦ СО АН СССР, НФ ИТМ и ВТ и кафедры вычислительной математики НГУ (Новосибирск. 1989 г., 1990 г.).

ПУБЛИКАЦИИ.

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

работы.

СТРУКТУРА ДИССЕРТАЦИИ.

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

СОЦЕРЖАНИЕ РАБОТЫ

Во введении приведен обзор систем управления динамической памятью для программ на Алголе 68. Рассматриваются последовательно три реализации языка: Брюссельская и две реализация Ленинградского университета. Проводится анализ сходства и различия подходов, принятых в этих реализациях, влияние принятых в этих реализациях решений на характеристики практических задач.

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

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

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

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

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

В этой же части диссертации 'описывается структура трафаретов зида единая для всех типов ЭВМ, на которые

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

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

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

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

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

поддержки, что существенно повышает быстродействие рабочей программы для этой ЭВМ.

В приложениях приведено описание системы генерации объектных модулей прошрамм для ЕС ЭВМ и классификация частных случаев программ динамической поддержки.

с*

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1.Разработана модель организации рабочей памяти программы на Алголе 68, единая для всех типов целевых ЭВМ, способ представления значений языка в памяти и структура трафаретов вида этих значений, общая для всех подпрограмм динамической поддержки и для всех типов ЭВМ, на которые рассчитана система программирования ДОВС.

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

3.Предложена методика создания мобильных (переносимых) программ с использованием средств параметризации алгоритмов, присущих стандартному языку Алгол 68 (подмена описаний констант и видов, текстов операций и процедур), и особенностей используемой системы программирования МВС (константные вычисления, условная генерация).

й.Показана возможность и эффективность использования такого мощного языка как Алгол 68 (при минимальных расширениях за счет специализированного пакета подпрограмм.

видов и опреаций) в качестве языка разработки системного математического обеспечения.

5. Реализованы подпрограммы генерации трафаретов видов значений Алгола 68, используемые в составе фазы синтеза ряда трансляторов с Алгола 68 коды различных ЭВМ.

6.Реализованы эффективные алгоритмы работы со сложно-устроенными значениями Алгола 68. Все подпрограммы перенесены с инструментальной ЕС ЭВМ на ЭВМ других типов (СМ ЭВМ, ПС-1001, IBM PC, "Самсон" и ряд специализированных управляющих ЭВМ).

7. Разработаны и реализованы методы упрощенной работы со строковыми значениями, что существенно повышает скорость обработки.

8. Разработаны просмотры генерации объектного кода для различных ЭВМ в рамках многомашинной системы программирования WBC. Просмотр генерации объектного кода программ для ЕС ЭВМ является языковонезависимым пакетом процедур, его применение возможно и осуществляется в ряде трансляторов с других языков, например FORTRAN 77. С, Pascal.

9. Разработан метод включения в язык Алгол 68 механизма исключительных ситуаций. Предложено расширение традиционного варианта этого механизма.

10.Разработаны рекомендации по аппаратной (микропрограммной) реализации части программ системы динамической поддержки транслятора с Алгола 68.