Л. В. Городняя

Введение

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

Известно, что при повторном издании своей знаменитой книги Фр. Брукс отметил поразительную устойчивость основной проблематики. Что же в этом видели и до сих пор видим мы?

Особенно интересен в этом плане обзор подходов к реализации языков программирования по материалам конференции 1975 года, подготовленный для журнала «Программирование» в начале 1976 года, отредактированный А.П. Ершовым и прорецензированный А.А. Берсом.

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

Но вернемся мысленно почти на тридцать лет назад. Конференция «Методы реализации алгоритмических языков» вполне заслуживала название «Сумма технологий». Каждый подход был представлен в разных вариантах, можно было сравнить и оценить методы, языки и системы с разных точек зрения. Подготовленный в феврале 1976 года обзор отражает лишь часть круга идей, «носившихся в воздухе» тех времен.

С 10 по 13 сентября 1975 г. в городе Новосибирске состоялся симпозиум по методам реализации алгоритмических языков, организованный Вычислительным центром СО АН СССР. Работой оргкомитета и симпозиума руководил член-корреспондент АН СССР А.П. Ершов. 59 участников симпозиума, представители 23 организаций из 10 городов СССР, и 11 гостей из 7 стран провели серию заседаний, завершившуюся оживленной дискуссией о системах построения трансляторов (СПТ). (Труды симпозиума, публикуемые в издании ВЦ СО АН СССР, были доступны к пересылке наложенным платежом по гарантийным письмам.)

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

Выделены следующие тематические разделы.
• Методика. Методология.
• Общие схемы реализации языков.
• Выбор языка реализации.
• Грамматический анализ.
• Практичность систем программирования.
• 5.1. Независимость от машины.
• 5.2. Оптимизация в программировании.
• Структура данных.
• Расширяемость. Макротехника.
• Диагностика ошибок.
• Генерация тестов.

1. Методика. Методология

Полезность программных (идейных) документов в больших проектах и четкого разграничения научно-исследовательской и опытно-конструкторской работ [4], целесообразность выделения так называемого Внутреннего языка, обеспечивающего стабильный уровень языково-независимого анализа программ и их оптимизации [7] и унифицирующего класс алгоритмических языков, показывает анализ развития проекта БЕТА [4].

Сформулированы некоторые требования к методике построения больших программ: «Методика должна быть императивной, целенаправленной, всепоглощающей и развивающейся», и предложена «операционная сеть» как модель программной поддержки такой методики [11].

Для многих проектов характерно стремление описывать трансляторы, модифицируя описания синтаксиса исходного языка [1, 3, 10–13, 17, 30].

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

2. Общие схемы реализации языков

1. Программирование на специальном языке транслятора с исходного языка на язык команд абстрактной машины предлагается в многоязыковой транслирующей системе T-SEMOL [15]. Описаны типичные схемы трансляции, выполняемые в системе T-SEMOL. Язык команд абстрактной машины похож на систему команд ЭВМ типа М-20.

2. Использование одного специального языка в качестве как языка программирования транслятора, так и промежуточного языка в двухступенчатой схеме трансляции [С.С. Камынин. Э.З. Любимский. Алгоритмический машино-ориентированный язык как средство разработки машинно-незави­си­мого обеспечения].

3. Задание множества процедур, выполняющих частные действия, необходимых для трансляции с исходного языка, и описание вывода транслятора в исчислении трансляции, по которым система МАСОН строит на промежуточном языке высокого уровня транслятор с исходного языка [14].

4. Описание задачи множеством отношений и множеством используемых в отношениях процедур в системе программирования ПРИЗ, по которому строится вычислительная модель. Метод применим к построению проблемно-ориентированных расширений языка [21].

5. Представление транслятора в виде последовательности преобразований текста исходного языка в текст эталонного языка на автоматно-ориентированном R-метаязыке [10].

6. Синтаксически управляемая трансляция на основе программы, транслирующей текст по метаописанию языка, и правил вывода объектного кода [12].

7. Получение транслятора с исходного языка на базовый по описанию синтаксиса исходного языка в виде формул над словами и семантики языка в виде эквивалентных текстов на базовом языке в системе DEPOT [1].

8. Интегрированное описание синтаксиса и семантики языка на расширении Паскаля, которое система построения трансляторов [3] преобразует в написанный на Паскале транслятор с исходного языка на Паскаль. Паскаль обеспечивает переносимость, практичность и изучаемость полученного транслятора [3].

9. Тщательное отделение языково-зависимых и машинно-зависимых черт транслятора в системе БЕТА [6]. Новый язык погружается в систему описанием языково-зависимых черт транслятора [5]. Выход на новую машину описывается конкретизацией машинно-зависимых черт [6]. Принципиальная возможность языково-независимого анализа и преобразований программ [7, 9] определяет практичность системы [7, 8].

10. Динамическое взаимодействие языково-зависимой и машинно-зави­си­мой фаз трансляции [С.С.Камынин, Э.З.Любимский].

11. Получение транслятора с исходного языка по описанию синтаксиса языка модифицированными БНФ, семантики языка в терминах атрибутов Кнута и прагматики языка на специальном языке PRA в системе COPS [30]. Описание машинно-зависимых черт на языке описания прагматики обеспечивает выход системы на разные машины.

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

13. Представление языка в виде макрорасширения базового языка позволяет реализовывать новый язык с помощью макрогенератора [28].

3. Выбор языка реализации

Отмечено две тенденции в выборе языков реализации [1]. Универсальные языки типа Алгол-68 используются для описания фазы синтеза объектного кода [31] и для обеспечения независимости описания от машины [23]. Алгол-68 — любимый пробный камень многих разработок [2, 5, 16, 20, 23, 31, 32]. Но для задачи построения транслятора универсальный алгоритмический язык слишком богат и имеет бесполезные конструкции. Транслятор с такого языка велик, эффективность объектного кода низка [31].

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

CDL — язык реализации трансляторов, по целям и функциям похож на СПТ, основан на типе грамматик, удобном для описания языков [32].

МИДЛ — гибридный язык промежуточного уровня, создан с целью описания оптимизатора для языка весьма высокого уровня Сетл [25].

Язык L2 предназначен для решения задач, возникающих при построении больших и содержательных программ [27].

Ярмо — машинно-ориентированный язык высокого уровня, спроектирован для реализации матобеспечения [26].

S emol — язык представления трансляторов [15].

Система МАСОН основывается на трех специализированных языках: метаязык для описания процессов трансляции, промежуточный язык, обеспечивающий независимость объектного кода от машины, и язык заданий, описывающий вывод формулы в исчислении трансляций [14].

4. Грамматический анализ

Использование формализованного синтаксиса для управления процессом трансляции позволяет свести проблему синтаксического анализа к проблеме построения синтаксического дерева, а проблему трансляции — к проблеме обхода дерева [13].

Изучаются соотношения между классами грамматик [29, В.Н.Редько. Проблемы построения многоязыковых процессоров] и преобразований
КС-грамматики для построения автомата, анализирующего порождаемый КС-грамматикой язык [17].

Введение новой синтаксической концепции «позиция» [4, 5] позволяет регуляризировать КС-грамматику, перейти от синтаксической структуры к грамматической [5], содержащей описание понятий с помощью атрибутов. Синтаксическая структура не зависит от набора понятий. Отмечается удобство метода атрибутов Кнута для описаний семантических действий [2].

Атрибуты синтезируют информацию, по которой проверяются некоторые условия согласованности [2, 5].

Метод описания семантики с помощью атрибутов используется в ряде систем [3, 5, 16, 30], хотя он не прост [16].

5. Практичность систем программирования.

Большинство проектов ориентируется на обеспечение производства больших программ.

Эта ориентация определяет заботу о независимости проектов от машин, операционных систем и алгоритмических языков [3]. Раздельная трансляция [32, 9, 16], трансляция на промежуточный язык [14, 16, 3], оптимизации программ [7, 8, 9, 16, 32] отражают стремление к практичности систем.

5.1. Независимость от машин.

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

Прежде всего это отражено в стремлении к отсутствию машинно-зависимых черт в структуре данных [26, 32], в поиске машинно-незави­симых схем обработки [15, 16] и описания [23] программ.

Выделение прагматики в определении исходного языка делают возможной генерацию на любом объектном коде. Прагматика — способ преобразования атрибутного дерева разборов для получения результирующего кода [30].

Вариантом такого подхода является выделение промежуточного языка как дополнительного этапа трансляции [16, 14]. Промежуточный язык позволяет решить и проблему раздельной трансляции частей программы [16].

Другое решение проблемы предложено в системе БЕТА. Внутренний язык этой системы — язык высокого уровня, не имеющий внешнего представления. Этот язык пригоден для решения машинно-независимых проблем, возникающих при трансляции [4, 6, 7, 8, 9]. Но генерация рабочей программы происходит машинно-зависимо [6].

5.2. Оптимизация в программировании.

Подробно исследованы проблемы анализа программ и оптимизирующих преобразований в проекте БЕТА [9, 7, 8].

Выбор внутреннего языка как уровня анализа и преобразований программы придает этому исследованию независимость и от алгоритмических языков, и от вычислительных машин. Оптимизация объектного кода — одна из целей создания внутреннего языка [1, 6].

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

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

Более широкий подход к этой проблеме предлагается в системе CDL: оптимизация всего процесса проектирования и реализации программы [32]. Инструменты такой оптимизации: редактор, обеспечивающий взаимодействие частей транслятора, библиотека с возможностью претрансляции и раздельной трансляции, механизм отладки, возможность получать текущий файл транслятора и оптимизатор, повышающий эффективность результирующего транслятора. Признано, что первая цель оптимизации — «умиротворить» программиста, который или откажется от недостаточно удобной и эффективной системы, или будет заботиться об оптимальности исходной программы в ущерб ее выполнимости, если ему не докажут, что автоматическая оптимизация программы ничуть не хуже [32].

Программист должен заботиться лишь о правильности, удобочитаемости, переносимости и адаптируемости программы. Эффективность должна гарантировать система [32].

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

Для языка Сетл создан большой оптимизатор, значение которого подчеркивается созданием специального языка Мидл для реализации оптимизатора [25].

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

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

6. Структура данных

Создатели языка L2, языка для обработки структур данных, приняли за основу алгебраический подход, дающий формализм для построения строгой базы языка. Основной тип данных — «останов» и работа с указателями — основа методики доступа к элементам составного. Сложные преобразования структур данных представляются в виде операторов применения соотношений [27].

В языке Ярмо представлены средства описания структур памяти, состоящей из последовательности ячеек, с возможность организации эффективного доступа к элементам структуры подстановкой шаблонов операций чтения и записи [26].

Система ПОПЛАН использует стек, организованный в виде списка небольших порций, в надежде на более эффективное распределение памяти [24].

Системы на базе языка Сетл представляют отображения с помощью расширяемых расстановочных полей [22, 25].

Язык Мидл содержит аппарат описания доступа к чужим переменным [25].

При реализации Алгола-68 к типичным видам памяти «стек» и «куча» добавлен вид памяти «пузырь», характеризуемый сравнительно простым способом освобождения памяти. Описана реализация семафоров на однопроцессорной машине [19].

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

В R-метаязыке для формального задания семантики языков программирования используются абстрактные виды памяти: счетчиковая, вагонная, регистровая, табличная. Этот набор считается пополняемым, хотя язык описания новых видов памяти не предлагается. Определен лишь внешний вид операторов доступа к памяти [10]. Автоматно-ориентированный R-метаязык предназначен для задания отображений исходного, определяемого класса объектов в другие, эталонные, известные [10].

7. Расширяемость. Макротехника

7.1. Расширяемость

Расширяемость — желанная черта современных систем программирования. Для ее реализации в систему включают макроязык [14] или язык, обладающий возможностями макроаппарата [6, 22, 25, 27].

В системе на базе языка L2 расширяемость используется для ввода новых операций и типов данных. Выполняют расширение переводящие подпрограммы, макрогенератор, а на уровне входного языка — операторы загрузки синтаксиса и семантики [27].

7.2. Макротехника

«Часть математического обеспечения, разработанная для того, чтобы позволить пользователю добавлять новые средства его собственной конструкции к существующей части математического обеспечения» П. Браун называет макрогенератором [28].

Макрогенератор используется в системе на базе языка L2 [27] как инструмент для расширения системы, в системе УТОПИСТ [21] — как генератор вычислительной модели, в реализации транслятора с Алгола-68 [31] — как генератор рабочей программы.

В системе БЕТА макросы используются как запросы к обстановке машинно-зависимых рабочих программ [6].

Разработчики языка Ярмо предлагают макроподстановку как способ описания доступа к данным [26].

Макрорасширяемы языки Сетл [22, 25], Балм [22], Мидл и Литтл [25]. Макроаппарат обеспечивает локализацию машино-зависимых черт программ на этих языках, что существенно облегчает перенос алгоритмов на новые машины.

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

Язык Метамакр [28] — попытка уточнить понятие макрогенерации и применить полученное уточнение для макрорасширения языков программирования.

8. Диагностика ошибок

В системе, обрабатывающей описание грамматики, имеет смысл проверка корректности описания [2].

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

Применяется метод маркеров в трансляторах для продолжения анализа после обнаружения синтаксически — правильной программы. [С.П. Криц­кий. Методика создания транслятора, устойчивого к синтаксическим ошибкам]

9. Генерация тестов

Система на основе R-метаязыка [10] содержит дедуктор, используемый в режиме порождения контрольных тестов.

Возможность генерации минимального набора правильных программ, использующих все правила грамматики языка, отмечается в описании СПТ [3].

* * *

Труды всесоюзного симпозиума по методам реализации новых алгоритмических языков: Сб. науч. тр. / Под ред. В.Л. Каткова. — Новосибирск: ВЦ СО АН СССР, 1975. — Т. 1–2.

Содержание

1. И. Леман. Проблемно-ориентированные языки и система реализации DEPOT. Дрезден. ГДР
2. Б. Лоро. Метод семантических атрибутов в системе DELTA. Роконкур. Франция.
3. О. Лекарм. Практичность и переносимость системы построения трансляторов. Ницца. Франция.
4. А. П. Ершов. Система БЕТА — сравнение постановки задачи с пробной реализацией. Новосибирск.
5. В. В. Грушецкий. Декомпозиция входных программ в многоязыковом трансляторе. Новосибирск.
6. С. Б. Покровский. Семантическая унификация в многоязыковом трансляторе. Новосибирск.
7. И. В. Поттосин. Глобальная оптимизация, практический подход. Новосибирск.
8. В. К. Сабельфельд. Реализация процедур в многоязыковом трансляторе. Новосибирск.
9. В. Н. Касьянов, М. Б. Трахтенброт. Анализ структур программ в глобальной оптимизации. Новосибирск.
10. И. В. Вельбицкий. Метаязык для формального задания семантики языков программирования. Киев.
11. А. Л. Фуксман. Некоторые принципы проектирования трансляторов. Ростов-на-Дону.
12. В. М. Курочкин. Обобщенная схема синтаксически управляемой трансляции. Москва.
13. Я. Крал. Почти нисходящий анализ обобщенных грамматик (на английском языке). Прага. ЧССР.
14. В. Л. Темов. Металингвистическая система общего назначения (МАСОН). Ленинград.
15. М. Г. Гонца. Подход к автоматизации построения многоязыковых транслирующих систем. Кишенев.
16. Р. Бранкар, Дж. Р. Кардинал, Дж. Леви, Дж. Р. Делескай, М. Ван Бегин. Простой транслирующий автомат, позволяющий генерировать оптимальный код. Брюссель. Бельгия.
17. Р. Штробель. Автоматические преобразования КС-грамматик. Берлин. ГДР.
18. Г. Е. Цейтлин, Е. Л. Ющенко. Некоторые вопросы теории параметрических моделей языков и параллельный синтаксический анализ. Киев.
19. Г. С. Цейтин. Реализация параллельного исполнения и гибких имен в АЛГОЛе-68. Ленинград.
20. И. О. Кернер. Один подъязык АЛГОЛа-68 и его реализация. Росток. ГДР.
21. Э. Х. Тыугу. Система программирования с автоматическим синтезом алгоритмов. Таллин.
22. Д. Я. Левин. Экспериментальная реализация языка СЕТЛ. Новосибирск.
23. М. Р. Левинсон. Метареализация АЛГОЛа-68. Москва.
24. Ю. М. Баяковский, Н. И. Вьюнова, В. А. Галантенко, А. Б. Ходуев. Некоторые особенности реализации языка РОР-2. Москва.
25. Е. Дик, М. Шимасаки, Дж. Шварц. МИДЛ: гибридный язык промежуточного уровня. Нью-Йорк. США.
26. Б. Г. Чеблаков. Представление структур данных в машинно-ориентированном языке высокого уровня. Новосибирск.
27. С. С. Гороховский, Ю. В. Капитонова, А. А. Летичевский. L2 — язык для обработки структур данных и его реализация. Киев.
28. В. Ш. Кауфман. О макрорасширении языков программирования. Москва.
29. А. Н. Маслов. Использование расширения индексных грамматик для синтаксического анализа. Москва.
30. Я. Боровец. Прагматика в системе построения компиляторов. Варшава. Польша.
31. А. Н. Терехов, Г. С. Цейтин. Язык синтез объектной программы с учетом последующего контекста. Ленинград.
32. К. Костер. CDL — язык реализации трансляторов (на английском языке). Западный Берлин.

Следующая статья сборника

Из сборника "Новосибирская школа программирования. Перекличка времен". Новосибирск, 2004 г.
Перепечатываются с разрешения редакции.