Введение к работе
:. . }
АКТУАЛЬНОСТЬ темы исследования.
Алгол 68 является современным мощным языком программирования. Полный статический контроль типов и тщательно определенный синтаксис конструкций языка позволяет создавать с его помощью высоконадежные и эффективные рабочие прогаммы. Он используется для программирования в различных областях науки и промышленности. На Алголе 68 разрабатывается программное обеспечение сложных программно-аппаратных сиситем, имеющих большое народно-хозяйственное значение. Это oneделило выбор языка Алгол 68 в качестве основы помышленной технологии раэаботки больших программных систем реального времени, математического обеспечения управляющих встроенных ЭВМ.
Одним иэ главных принципов, используемых в такой технологии программирования, является стремление провести программирование и возможно большую часть отладки разрабатываемого математического обеспечения на мощной инструментальной ЭВМ. Затем программное обеспечение переносится на целевую ЭВМ при помощи кросс-транслятора. Боьшое количество и разнооборазие типов инструментальных ЭВМ и, особенно, целевых ЭВМ делает весьма актуальными работы по созданию трансляторов с Алгола 68 в коды этих ЭВМ. Причем требуется совпадение спецификаций входного языка (его возможности, ограничения) инструментального транслятора и вновь разрабатываемых кроес-трансляторов.
По сравнению с другими языками аналогичного уровня, такими как ПЛ/І, Ада, Модула 2, Паскаль, в Алголе 68
значения, создаваемые программистом, могут иметь гораздо более разнообразную и сложную структуру, по-этому, разработка эффективных программ распределения памяти для таких значений, их присваивания, копирования, вычтраивания и другой обработки является нетривиальной задачей. Существенная доля трудоемкости работ по созданию транслятора падает на разработку вопросов, связянных с определением структуры рабочей программы, используемой модели распределения памяти, созданию библиотеки подпрограмм динамической поддержки, реализующух работу основных конструкций языка, манипулирования значениями.
МЕТОДИКА исследований.
Большое разнообразие типов универсальных и специализированных ЭВМ, используемых в настоящее время в отечественной практике, требует разработки методов быстрого создания и унификации программ динамической поддержки системы программирования. Если в первых опытах раэваботки трансляторов с Алгола-68 в основном интересовались принципиальной возможностью реализации всего богатства выразительных средств языка, то в последнее время акцент делается на создание промышленных реализаций, удобных для пользователя и ориентированных на повседневную практику программирования. Методика исследований основана на выделении основных, часто используемых в практическом программировании конструкций языка и их оптимизированной реализации. Общие механизмы сложных конструкций реализуются видоэовисимыми подпрограммами на основании единых трафаретов вида.
5 ЦЕЛЬ работы.
Цель работы состоит в разработке методов распределения динамической памяти для сложных значений и переносимой системы программ динамической поддержки ' для новой многоцелевой (многомашинной) системы программирования на базе языка высокого уровня (АЯВУ ) Алгол 68, разрабатываемой в НИИ Математики и Механики им.В.И.Смирнова в рамках госбюджетной НИР "Инструментальные средства промышленных методов разработки программного обеспечения" (Б.0 2.08).
НАУЧНАЯ НОВИЗНА результатов.
Разработана модель организации рабочей памяти программы на Алголе 68, единая для всех типов целевых ЭВМ, способ представления значений языка в памяти и структура трафаретов вида этих значений, общая для всех подпрограмм динамичесгсй поддержки и для всех типов ЭВМ, на которые рассчитана система программирования WBC.
Проведена классификация основных подпрограмм манипулирования значениями в зависимости от сложности их видов. Разработаны и реализованы алгоритмы подпрограмм, поддерживающих наиболее трудоемкие конструкции языка: генерацию, присваивание, копирование, уплотнение, выстраивание, определене области действия, сборку мусора.
Предложена методика создания мобильных (переносимых) программ с использованием средств параметризации алгоритмов, присущих стандартному языку Алгол 68 (подмена описаний констант и видов, текстов операций и процедур). и особенностей используемой системы программирования WBC (константные вычисления, условная генерация).
Показана возможность и эффективность использования такого модного языка как Алгол 68 (при минимальных расширениях эя счет специализированного пакета подпрограмм, видов и опреаций) в качестве языка разработки системного математического обеспечения,
1.Реализованы подпрограммы генерации трафаретов видов значений Алгола 68, используемые в составе фазы синтеза ряда трансляторов с Алгола 68 коды различных ЭВМ.
2.Реализованы эффективные подпрограммы вызова процедур и управления динамической памятью для рабочих программ, полученных трансляцией с Алгола 68.
3.Реализованы подпрограммы работы со сложно/строенными значениями Алгола 68.
й.Все подпрограммы перенесены с инструментальной ЕС ЭВМ на ЭВМ других типов (СМ ЭВМ, ПС-1001, IBM PC, "Самсон" и ряд специализированных управляющих ЭВМ),
5.Разработаны просмотры генерации объектного кода для различных ЭВМ в рамках многомашинной системы программирования WBC, разработанной в НИИ Математики и Механики им.В.И.Смирнова и эксплуатирующейся в ряде организаций.
6. Просмотр генерации объектного кода программ для ЕС ЭВМ является яэыковонеэависиыым пакетом процедур, его применение воэможноии осудествляется в ряде трансляторов с других языков, например FORTRAN 77, С, Pascal.
7 ОБОСНОВАННОСТЬ положений работы.
Проведены статистические эксперименты, подтверждающие возможность испольэовавния созданной модели динамической првмяти. Сравнительный анализ ряда предыдущих реализаций системы управления памятью выявляет их недостатки и обосновывает принятые решения.
Сравнение времени исполнения рабочих программ, полученных различными трансляторами, подтверждает справедливость принятых критериев классификации и эффективность реализации подпрограмм динамической поддержки.
Результаты диссертации доложены II Всесоюзной конференции по методам трансляции (Новосибирск, 1981 г.), Всесоюзной конференции "Методы трансляции и конструирования программ" (Новосибирск, 1988 г.). Семинарам ИСИ, ВЦ СО АН СССР, Н* ИТМ и ВТ и кафедры вычислительной математики НГУ (Новосибирск, 1989 г., 1990 г.).
По теме диссертации опубликовано .. ( ) печатных
работы.
Диссертация состоит иэ введения, трух частей, разбитых на 15 параграфов, заключения, списка литературы (2U наименования) и 2 приложений. Основной текст занимает ... страниц, общий объем диссертации ... страниц.
Во введении приведен обзор систем управления динамической памятью для программ на Алголе 68. Рассматриваются последовательно три реализации языка: Брюссельская и две реализации Ленинградского университета. Проводится анализ сходства и различия подходов, принятых в этих реализациях, влияние принятых в этих реализациях решений на характеристики практических задач.
Первая часть состоит из двух параграфов. В них приводится описание предлагаемого метода распределения рабочей памяти и описываются основные способы представления значений Алгола 68 в памяти ЭВМ. Динамическая память распределяется в виде клеток (блоков) по модифицированному методу первого подходящего, а освобождается с использовнием граничных признаков, что позволяет избегать внешней фрагментации в динамической памяти. Для учета областей действия значений, создаваемых в Алгол-программе все клетки динамической памяти, имеющие одинаковое время жизни, прошиваются в единый список области действия соответствующего блока.
Для того, чтобы иметь возможность унифицировать алгоритмы работы подпрограмм динамической поддержки для различных ЭВМ и создавать переносимую реализацию этих подпрограмм, проведена унификация внутреннего машинного представления значений, обрабатываемых в Алгол-программе. Вместе с тем оставлена достаточная свобода в выборе конкретного представления простых значений, чтобы каждая реализация могла максимально эффективно использовать особенности архитектуры целевой ЭВМ, ибо неэффективность
9 работы с элементарными данными самым катастрофическим образом сказывается на производительности всей системы в целом. Это сделать удалось, так как сложные алгоритмы работы программ динамической поддержки в основном связаны со слохноустроенными значениями, а о простых значениях им требуются минимальная информация.
Вторая часть посвящена работе со слохноустроенными занчениями языка Алгол 68 и состоит иэ 9 параграфов. Вначале описываются два способа работы со сложноустроенными значениями - генерация видовых подпрограмм для всех используемых в единице компиляции видов и универсальных видозависимых подпрограмм, работающих по трафаретам вида, приводится обоснование выбора второго способа для системы программирования WBC. Такая реализация дает существенное сокращение длины объектного кода без заметного замедления вычислений. Здесь же рассматриваются основные принципы разработки видоз'ависимымых подпрограмм, способы их работы.
Далее проводится классификация основных подпрограмм манипулирования значениями в зависимости от сложности их видов для наиболее трудоемких конструкций языка Алгол 68: генерация (описание переменной), присваивание, копирование, уплотнение, выстраивание (ввод-вывод), определение области действия, сборка мусора, описываются алгоритмы их работы. Для всех подпрограмм определяются специальные частные случаи структуры значений, в которых возможна упрощенная или более оптимальная обработка, определены алгоритмы работы в этих ситуациях.
В этой же части диссертации 'описывается структура трафаретов вида единая для всех типов ЭВМ, на которые
10 рассчитана система программирования WBC, и для всех видозависимых процедур, п также универсальным по отношению к типу ЭВМ образом определенные состав и структура информации о программе, предоставляемой транслятором для программ сборки мусора.
Третья часть диссертации включает в себя 3 параграфа и посвящена специфическим вопросам реализации системы программирования WBC. К ним относятся специальная, оптимиэированная реализация работы со строками, включение в язык механизма задания реакции на возникновение исключительных ситуаций, аппаратная реализация отдельных конструкций языка. В связи с этим:
-
Проведен анализ операций обработки сивольных данных в современных программах. В связи с этим выбраны специальные формы прояставления объектов вида STRING, и также определены упрощенные алгоритмы работы с ними для всех типов конструкций языка.
-
Предложен оригинальный способ реализации новой возможности языка - обработки исключительных ситуаций, основанный на выбранном методе распределения, учета и освобождения динамической памяти. Предложено расширение языка, вводящее покятее пометки, идентификатора блока и дающее возможность определять реакцию на исключительную ситуацию не только для текущего, но и для любого помеченного блока по его идентификатору.
3.Рассмотрены вопросы аппаратной поддержки конструкций языка в микропрограммируемом вычислительном комплексе "Самсон". Предложен и реализован в микропрограммах специальный способ вызова подпрограмм динамической
поддерхки, что существенно повышает быстродействие рабочей программы для этой ЭВМ.
В приложениях приведено описание системы генерации объектных модулей прошрамм для ЕС ЭВМ и классификация частных случаев программ динамической поддерхки.
