Рухлин Алексей Павлович

"Система программ динамической поддержки для транслятора с Алгола 68"                                                                                    

Официальные оппоненты:
                                                д. ф.-м. н. Касьянов В. Н.
                                                к. ф.-м. н.  Гололобов В. И.

Ведущая организация - ВЦ АН СССР

Новосибирск, 1991г.                                                                         

                                                      

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

 

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

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

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

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

По, сравнению с другими языками аналогичного уровня, такими как ПЛ/1, Ада, Модула 2, Паскаль, в Алголе 68 значения, создаваемые программистом, могут иметь гораздо более разнообразную и сложную структуру, по-этому, разработка элективных программ распределения памяти для таких значений, их присваивания, копирования, вычтраивания и другой обработки является нетривиальной задачей. Существенная доля трудоемкости работ по созданию транслятора падает на разработку вопросов, связянных с определением структуры рабочей программы, используемой модели распределения памяти, созданию библиотеки подпрограмм динамической поддержки, реализующух работу основных конструкций языка, манипулирования значениями.

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

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

ЦЕЛЬ работы.

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

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

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

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

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

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

 

 

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

Практическая значимость.

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

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

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

 

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

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

6.Просмотр генерации объектного кода программ для ЕС ЭВМ является языковонезависимым пакетом процедур, его применение возможноии осуществляется в ряде трансляторов с других языков, например РОКТКАН 77. С, Равса!.

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

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

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

Апробация.

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

ПУБЛИКАЦИИ.

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

работы.

Структура диссертации.

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

 

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

Во введении приведен обзор систем управления динамической памятью для программ на Алголе 68. Рассматриваются последовательно три реализации языка;

Брюссельская и две реализации Ленинградского университета. Проводится анализ сходства и различия подходов, принятых в этих реализация^, влияние принятых в этих реализациях решений на характеристики практических задач.

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

 

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

 

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

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

Далее проводится классификация основных подпрограмм манипулирования значениями в зависимости от сложности их видов для наиболее трудоемких конструкций языка Алгол 68:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8.Разработаны просмотры генерации объектного кода для различных ЭВМ в рамках многомашинной системы программирования ИВС. Просмотр генерации объектного кода программ для ЕС ЭВМ является языковонеэависимым пакетом процедур, его применение возможно и осуществляется в ряде трансляторов с других языков, например РОКТКАМ 77. С, Разса!.

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

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

 

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

1. А.П.Рухлин. Распределение памяти для объектов изменяющихся размеров. // Тезисы доклада, всесоюзная конференция по методам трансляции. - Новосибирск. 1981.

2. А.П.Рухлин. Система генерации объектных модулей программ для ЕС ЭВМ. // Сб. Информатика.Технологические аспекты. - Новосибирск, 1987.

3. А.П.Рухлин. Организация работы со сложноустроенными в трансляторе с Алгола 68 // Информационный листок 859-88 ЛенЦНТИ. - Ленинград, 1988.

и. А.П.Рухлин. Сравнение систем динамического распределения памяти для Алгола 68 // Сб. Адаптируемые средства программирования. Методы оценки трансляторов. Материалы школы-семинара, 5-7 июня 1989 г. в гор. Фрунзе. - Кишинев, 1989.

5. А.П.Рухлин. Управление динамической памятью для программ на Алголе 68 // Сбоник Информатика и программирование. - Новосибирск, 1989.