автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Реализация управляющих структур современных языков программирования на МВК "Эльбрус"

1. Введение

2. Управление в МБК "Эльбрус".

2.1. Структура программы и данных

2.2. Управление работой программы

2.3. Обработка исключительных ситуаций 12 2Л. Задержанные вычисления

3. Общее описание трансляторов с языков АБВ, Паскаль и Клу

4. Процедуры

4.1. Передача параметров в вычислитель АБВ

4.2. Процедурный механизм в Клу

4.3. 4.2.1. Реализация вызова процедур

4.2.2. Параметризация

4.2.3. Кластеры

5. Оператор выбора

6. Обработка записей

7. Управление циклами в Клу

8. Обработка исключительных ситуаций

Данная работа посвящена вопросам трансляции управляющих конструкций в языках АБВ [28], Паскаль [21} и Клу [48], представляющих различные классы современных языков программирования в коды ЭВМ с развитой архитектурой - МВК "Эльбрус" [4].

В настоящее время задача написания транслятора с нового языка для новой ЭВМ остается весьма актуальной, несмотря на то, что основные методы анализа языков и синтеза программ были созданы и систематизированы в таких широко известных работах, как £2,-34, 41], Несмотря на значительный успех, достигнутый в области создания систем построения трансляторов [14, 15,40], трансляторы,.написанные вручную, продолжают сохранять ведущую роль в математическом обеспечении ЭВМ. Но мнению автора основными причинами этого являются следующие.

1). Появление языков программирования с новыми способами организации данных и управления, не сводящихся к организации данных и управления в ранее созданных языках программирования. Заметную роль в развитии этих идей сыграли, например, концепция квазипараллельного исполнения в Симуле [19], управление циклами с помощью итераторов в Клу, мониторы Хоара [45], динамические структурные переходы по ситуации в Эль 76 [31] и Аде [43] и т.д. В области организации данных в последнее время большое внимание уделяется концепции абстрактного типа данных [16], представленного аппататом модулей в языках Эль 76 и Аде, кластерами в языке Клу и т.д.

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

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

4).-Удешевление производства и сопровождения трансляторов, вызванное как повышением уровня организации ЭВМ и ее системного обеспечения, так и повышением уровня организации программирования, выразившееся, в частности, в широком распространении идей и методов структурного программирования [18].

Усложнение управления в современных языках программирования требует повышенного внимания к качеству трансляции управляющих конструкций. Аппарат управления в современных языках программирования все время развивается и совершенствуется, причем это направление развития остается в центре внимания разработчиков новых алгоритмических языков [31,4-7,51], Это не случайно, так как выразительность и эффективность управляющих конструкций во многом определяет качество программ, написанных на языке программирования. Часто, однако, требования наглядности' исходной программы и эффективности объектной программы противоречат друг другу,.так как многие удобные и естественные с точки зрения разработчика языка конструкции (например, рекурсивный вызов процедур, структурный переход по ситуации и т.п.) требуют для реализации на ЭВМ создания сложной административной системы. Многие программы, написанные на языке высокого уровня, требуют применения нетривиальных преобразований для получения более эффективного кода ; часто используются оптимизирующие трансляторы, разработка которых требует значительных затрат времени и средств.

Аппаратура и операционная система (ОС) МБК "Эльбрус" предлагают пользователям набор встроенных средств управления, позволяющих приблизить уровень объектной программы к уровню современных алгоритмических языков. Аппаратная поддержка МБК состоит в организации стека для хранения локальных данных процедур и их связи в статическую и динамическую цепочки согласно классической стековой административной системе транслятора с языка Алгол 60 [35^ разделении адресного пространства объектного кода и массивов данных на сегменты с контекстной защитой и т.д. Операционная система, кроме того,.совместно с аппаратурой поддерживает создание произвольной структуры областей локальных данных процедур, в частности, допускается .размещение этих .областей вне стека вызовов. Обеспечивается организация обработки программных прерываний и программируемых исключительных ситуаций и т.д. В целом можно сказать,, что пользователю МВК "Эльбрус" предоставлена в распоряжение мощная административная система с развитыми структурами управления, по своим возможностям превосходящая административную систему[з5]. Это существенно облегчает трансляцию большинства конструкций управления современных языков программирования, причем получающийся при трансляции объектный код хорошо соответствует исходной программе, а это, в свою очередь,позволяет отказаться от сложных оптимизирующих алгоритмов при трансляции, увеличивает возможности динамической диагностики при отладке программ.

Б то же время, при реализации нетрадиционных конструкций управления возникает ряд проблем, так как предлагая свою административную систему, архитектура МВК исключает возможность создания своей собственной системы, ориентированной на специфические конструкции управления реализуемого языка программирования. Таким образом, механизмы аппаратуры и ОС должны служить базой для реализации любых конструкций алгоритмических языков. Несмотря на то, что аппарат процедур достаточно гибок для выражения самых разнообразных конструкций управления (см., например, [I]), в практической реализации существенное значение имеет эффективность такого выражения. В применении к МВК "Эльбрус" это, в частности, означает, что при реализации надо стремиться к

- минимизации общего числа обращений к процедурам (в том числе, процедурам ОС);

- сокращению размеров объектного кода, так как большие программные сегменты (или частые вызовы большого количества маленьких сегментов) могут создать "толкотню в памяти" [42],

Кроме эффективности реализации в МВК "Эльбрус" существенное значение имеет "естественность" реализации, т.е.» соблюдение соответствия между понятиями языка программирования и соответствующими понятиями системы программирования Эльбрус. Так, например, процедуре языка должна соответствовать процедура МВК "Эльбрус", представление массива в языке должно соответствовать представлению аппаратно поддерживаемого массива МВК, локальные данные разных процедур должны храниться в различных секциях данных, соответствующих этим процедурам и т.п.

Соблюдение таких соглашений позволяет естественным образом включить реализацию в весь комплекс системных средств, таких как система динамической диагностики и отладки, многоязыковая комплексация программ, система архивов и файлов [12,13].

Б данной работе рассматриваются вопросы адекватного и эффективного отображения разнообразных управляющих конструкций современных языков программирования в систему управляющих конструкций МВК "Эльбрус". Её результаты, полученные при участии в разработке трех трансляторов с языков АБВ, Паскаль и Клу для МВК "Эльбрус", опубликованы в работах[7-П,25,26,30] Основные результаты работ по оозданию этих трансляторов содержатся также в [6,36-38].

Далее в главе 2 кратко описаны основные управляющие структуры МВК "Эльбрус", непосредственно использовавшиеся в описываемых трансляторах. В главах 3-8 содержатся соответственно общая характеристика описываемых трансляторов и анализ процедурного механизма, конструкций ветвления, циклических конструкций и механизма обработки исключительных ситуаций в рассматриваемых языках. Описывается их реализация на МВК "Эльбрус". В заключении перечислены основные научные и практические результаты работы, указана возможная область их применения.

2. УПРАВЛЕНИЕ В МВК "ЭЛЬБРУС"

Многопроцессорный вычислительный комплекс "Эльбрус" воспроизводит в аппаратуре многие черты современных языков программирования. Такая архитектура способствует более быстрой отладке программ по сравнению с традиционной ЭВМ, высокой надежности программного обеспечения, повышает скорость трансляции и способствует порождению эффективной рабочей программы (см. также [4,6,10]). Рассмотрим более подробно некоторые аспекты архитектуры МВК "Эльбрус".

- 102 -9. ЗАКЛЮЧЕНИЕ

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

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

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

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

4). Реализован механизм параметризации модулей, включая параметризацию абстрактным типом данных языка Клу.

5). Реализована эффективная схема вызова процедурных и итераторных подпрограмм Клу с возвратом произвольного числа результатов.

6). Разработана схема реализации операторов выбора в различных языках программирования в случае разреженного множества меток альтернатив. Разработанная схема используется в трансляторе с языка Паскаль для МВК "Эльбрус11.

7). Реализован присоединяющий оператор в трансляторе

Паскаль-Эльбрус и исследована эффективность его работы.

8). Реализована схема управления работой циклов с помощью итераторов в Клу.

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

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

Эти результаты использованы при написании трансляторов с языков АББ, Паскаль и Клу для МБК пЭльбрус-1" группой сотрудников ВЦ ЛГУ им.А.А.Жданова под руководством член-корр. АН СССР С.С.Лаврова. Б настоящее время язык АББ полностью реализован и используется в ИТМ и ВТ им.С.А.Лебедева АН СССР. Автором работы-реализована часть языка (вычислитель) и передача значений из базы в вычислитель АББ. Транслятор с языка Паскаль прошел межведомственные испытания и находится в опытной эксплуатации в ИТМ и ВТ. Этот транслятор превосходит по скорости работы трансляторы с языков Эль 76, Фортран и Алгол 60, входящие в состав стандартного математического обеспечения МВК "Эльбрус", и не уступает им по эффективности получаемой рабочей программы. Автором работы реализованы все управляющие конструкции языка и файловая система. Транслятор с языка Клу включен в программу договорных работ, выполняемых в ЛГУ для ИТМ и ВТ, и находится в стадии разработки. В настоящее время разработана схема транслятора и реализован генератор кода управляющих структур языка. Полностью работу над транслятором планируется завершить в 1985 году.

Методы трансляции, описанные в работе, и их исследование могут быть использованы в трансляторах и других программных системах, проектирующихся для МВК "Эльбрус". Техника, использующая задержанные вычисления и близкая к описанной в работе, использована в работе над транслятором с языка Снобол 4ко торый проектируется в ВЦ ЛГУ. Результаты работы планируется перенести в трансляторы с языков АБВ, Паскаль и Клу для МВК пЭльбрус-2и.

1. Агамирвян И.Р., Иванов A.C. Процедурные механизмы абстракции. - Зап.науч.сем.ЛОМИ, т.Ш, Л.: Наука, 1981, с.5-30.

2. Ахо А.-, Ульман Дж. Теория синтаксического анализа, перевода и компиляции, т.1. Синтаксический анализ. М.: Мир, 1978, 612 с.

3. Бабаев И.О., Новиков Ф.А., Петрушина Т.Й. Язык Декарт -входной язык системы СПОРА. Прикладная информатика, вып.1, 1980, с.27-76.

4. Бабаян Б.А., Сахин Ю.Х. Система Эльбрус. Программирование, 1980, №3, с.72-86.

5. Ван Вейнгаартен А. и др. Пересмотренное сообщение об Алголе 68. М.: Мир, 1979, 533 с.

6. Вдовкин C.B. Эффективный синтех рабочей программы в трансляторе Паскаль-Эльбрус. Тез.докл.всес.конф. по методам трансляции. Новосибирск : ВЦ СОАН СССР, .1981, с.118-120.

7. Вдовкин C.B., Кубенский A.A. Особенности реализации модулей языка Клу на МВК "Эльбрус". Вестник ЛГУ. Депонировано ВИНИТИ, № 3288-84 от 22 мая 1984 г., 28 с.

8. Вдовкин C.B., Кубенский A.A. Язык модульного программирования Клу и принципы его реализации для МВК "Эльбрус". -Аппаратные и программные средства применения ЭВМ в учебном процессе. Л.: ЛГУ, 1984, с.53-54.

9. Вдовкин C.B., Кубенский A.A., Лавров С.С., Сафонов В.О. Реализация языка Паскаль для МВК "Эльбрус". Программирование, 1981, № 3, с.62-64.

10. Вдовкин C.B., Кубенский A.A., Сафонов В.О. Архитектура МВК "Эльбрус" как основа для оптимизаций в Паскаль трансляторе. Трансляция и оптимизация программ/под ред. И.В.Поттосина.Новосибирск: ВЦ СОАН СССР,1983,с.44-50.

11. Вдовкин C.B.,Кубенский А.А.,Сафонов В.О. Реализация языка Клу. Прикладная информатика, вып.2, 1984-, с. 127-130.

12. Волконский В.Ю.,Еремин М.В.,Пентковский М.В.,Петровский С.Ю. Структурные модели программ и памяти для систем программирования. Тез. докл. П всес. конф. "Автоматическое производство пакетов прикладных программ и трансляторов". Таллин, 1983, с.112-114.

13. Волконский В.Ю.,Пентковский В.М. Универсальный интерфейс компонентов системы программирования МВК "Эльбрус". -Препринт ЙТМ и ВТ № 28, M.i HTM и ВТ, 1980, 39 с.

14. Вооглайд А.0.,Лепп М.В.,Лийб Д.Б. Входные языки системы ELMA. Труды ТПИ, të 524, Таллин, 1982, с.79-96.

15. Гололобов В.И. Программная поддержка разработки трансляторов для традиционно описанных языков. Прикладные методы информации. Новосибирск : ВЦ СОАН СССР,1980,с.5-16.

16. Григас Г.,Купчюнас Г. Абстрактные типы данных. Программирование ЭВМ : системное программирование, вып.З, Вильнюс, 1980, с.9-46.

17. Грогоно П. Программирование на языке Паскаль. М.:Мир, 1982,382с.

18. Дал У.,Дейкстра Э.Доар К. Структурное программирование. M.î Мир, 1975, 247 с.

19. Дал У.,Мюрхауг Б.,Нюгорд К. Симула 67 универсальный язык программирования. М.: Мир, 1969, 99 с.

20. Ершов А.П. О сущности трансляции. Программирование, 1977, Ш 5, с.21-39.

21. Йенсен К.,Вирт Н. Паскаль» Руководство для пользователяи описание языка. М.: Финансы и статистика, 1982, 151 с.

22. Капустина E.H., Лавров С.С., Селюн М.И. Схема расширений и основные принципы реализации аппарата процедур языка Паскаль в языке АБВ. Обработка символьной информации, вып.4, М.: ВЦ АН СССР, 1978, с.5-10.

23. Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). М.: Финансы и статистика, 1981, 157 с.

24. Кнут Д. О переводе (трансляции) языков слева направо. -Языки и автоматы. М.: Мир, 1975, с.9-42.

25. Кубенский A.A. Управление в языке CLU и его аппаратная поддержка в МВК "Эльбрус". Тез. докл. П всес. конф. "Автоматическое производство пакетов прикладных программ и трансляторов". Таллин, 1983, с.132-134.

26. Кубенский A.A., Сафонов В.О. Возможности языка АБВ и его реализация. Программирование, 1982, № 3, с.64-72.

27. Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971, 160 с.

28. Лавров С.С., Капустина E.H., Селюн М.И. Расширяемый алгоритмический язык АБВ. Обработка символьной информации, вып.З, М,: ВЦ АН СССР, 1976, с.5-53.

29. Лавров С.С. Универсальный язык программирования (Алгол 60). М.: Наука, 1972, 183 с.

30. Кубенский A.A. О реализации управления в современных языках программирования. Программирование, 1984, № 5,с.47-55.

31. Пентковский В.М. Автокод Эльбрус "Эль 76". М.: Наука, 1982, 350 с.разработку системы программирования. Тез.докл.всес. конф. по методам трансляции. Новосибирск : ВЦ СОАН СССР, 1981, с»59-60.

32. Пирин С.И. Язык Паскаль-монитор и его использование. M.J ВЦ АН СССР, 1978, 55 с. • 34, Пратт Т.В. Языки программирования : разработка и реализация. М.: Мир, 1979, 574 с.

33. Ренделл Р., Рассел Б. Реализация Алгола 60. М.: Мир, 1967, 475 с.

34. Сафонов В.О. Вычисление семантических атрибутов системы определений за один просмотр. Тез.докл. всес. конф. по методам трансляции. Новосибирск, ВЦ СОАН СССР, 1981,с.106-108.

35. Сафонов В.О. Некоторые способы организации структур данных в трансляторах. Дисс. на соискание ученой степени к.ф.-м.н. Л.: ЛГУ, I98X, 117 с.

36. Сафонов В.О, Реализация типов в Паскаль-трансляторе. -Языки и системы программирования. Новосибирск : ВЦ СОАН СССР, 1981, с.21-31.

37. Турский В. Методология программирования. М.: Мир, 198Г, 265 с.

38. Фелдман Дж.А., Грис Д. Система написания трансляторов. -Алгоритмы и алгоритмические языки, вып.5. М.: ВЦ АН СССР, 1971, с.105-214.

39. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика, 1984, 232 с.

40. Цикритзис Д., Бернстайн Ф. Операционные системы. М.: Мир-, 1977, 336 с.

41. Язык программирования Ада (предварительное описание).

42. M.: Финансы и статистика, 1981, 190 с,

43. Охкегъшь UB.fJ)e*mLs gß, Ш-а. Vaâue Orlele¿ CLtcjoritkmic Language Preâùnlnary Refereлее /?7аяио£

44. MIT/iCS /77?. -2i8> MIT, /ffass., J9?<?.

45. Hoare C. fj.fi. Monitors: an Operating System Structuring

46. Concept Co»?*?, fíCM, /97^ V/4 />/>■ SM - SS z46 • Li-ndsQy С. H. Specification of Partiaê Para^etrization,

47. Proposât. OBgot ßutt, V39; />/>. 6-9.47. ¿isMoï В. et.aâ, abstraction Mechanisms in CLLL

48. Comm. ДСМ, 20, ¿9771 ¿8, pp. Ш-576. 48 • Lisk0* Ä а*. С LU tieferen ce /71 aunt. Lecture

49. H otes in. Computer Science> ¿¿43 ¿90p bUkoP В., ZLttes S. Programming vitk Oistnct %pes. fíCM SICPm l/otices., $ ¿974, ^ ^50 • Sade flJ.H. ß 6700/ 7700 ßifscaä fíeferencQ /7?мт£

50. Яер. of information Science Report â 77-3; ¿fc/fc of üismanU, J97/.51. fl.> ¿Onaíon, ß. Ь.Л Siw M. ¿¿¿straction, as?aLruficcctiori Ui CtôpAasd. flew directions U Qlgoritkrnic ¿angles, ¿970, pp. ¿i?- 2Q5.