Институт

Любимский Э.З., Поттосин И.В., Шура-Бура М.Р. От программирующих программ к системам программирования (российский опыт)

Начало

Трансляция — это область, с которой начиналось системное программирование. Первыми программами, принадлежащими системному программному обеспечению, были те или иные трансляторы — ассемблеры и автокоды на Западе, программирующие программы (ПП) у нас.

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

Начальные идеи по трансляции были выдвинуты в 1952 году, на самом раннем этапе развития программирования. В этом году Рутисхаузер опубликовал работу [1], в которой изложил идею о том, что по естественной записи арифметического выражения можно построить эквивалентный ей фрагмент машинного кода. Соответствующий алгоритм (многопроходный) был сформулирован. Эта работа дала толчок к возникновению процессоров, в своем входном языке допускающих естественную запись выражений. А.А.Ляпунов в те же годы атаковал проблему с другой стороны. Он заметил, что структура программы включает в себя операторы из небольшого набора типовых операторов и может быть представлена формально в виде строки, соответствующей последовательности операторов программы. На языке операторных схем программа представляется как схема, соответствующая управляющему графу программы, и совокупность спецификаций каждого оператора. Эти идеи А.А.Ляпунов положил в основу курса по программированию, читавшегося им в Московском Университете. Понятие программы как некоторой операторной структуры, взгляд на программу сверху, было революционной идеей, которая практически сразу же легла в основу первых отечественных трансляторов. К сожалению, из-за специфики организаций, в которых работал А.А.Ляпунов, развернутая публикация этого подхода была осуществлена только в 1958 г. [2].

Программирующие программы

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

1: А1; 2:А2; 3:А3; 4:А4; 5:F1; 6:P1(3, 7); 7: О1.

со спецификацией операторов:

А1 : S:=0
A2 : i:=1
A3 : S:=S+ai
A4 : i:=i+1
F1 : переадресация A3 по i
P1 : если i@n, то на оператор 3, иначе — на 7
О1 : восстановление A3 в начальном виде.

Типы операторов соответствовали подавляющему большинству решаемых тогда задач, а именно - вычислительным задачам. Выделялись арифметические операторы Аi , ведущие вычисление по формулам, логические операторы Рi , осуществляющие управление счетом, операторы переадресации Fi , позволяющие переходить к следующему значению индекса (и обратные им операторы восстановления), все же неарифметические вычисления объединялись в так называемые нестандартные операторы Hi , для которых спецификацией был их машинный код. Специального подъязыка описания данных, зачатки которого появились в более поздних ФОРТРАНе и Алголе, не существовало.

Начиналось все с ПП-1. Молодые тогда программисты С.С.Камынин и Э.З.Любимский исследовали реализуемость операторных схем и возможность автоматического построения соответствующих машинных программ. Это было самое начало, и то, что стало очевидным и даже тривиальным сейчас, считалось тогда проблематичным. Законченная в 1954 году программирующая программа ПП-1 [14] являлась одним из первых в мировой практике трансляторов и, по-видимому, имела самый высокий уровень входного языка.

Успешное решение проблемы реализуемости операторных схем как входного языка программирующих программ, осуществленное в ПП-1, дало толчок для двух проектов, разработанных для двух основных тогда отечественных машин — Стрела и БЭСМ.

Программирующая программа ПП-2 [3], созданная под руководством М.Р.Шура-Буры в 1955 г. для машины Стрела-1, основывалась на ПП-1 как прототипе. Разработчиками были И.Б.Задыхайло, С.С.Камынин, Э.С.Луховицкая, Э.З.Любимский и В.С.Штаркман. В ПП-2 были усовершенствованы алгоритмы трансляции и было уделено заметное внимание оптимизации программ — экономии выражений, оптимальному сочетанию переадресации и восстановления (иначе говоря, наилучшей реализации вычисления индексных выражений), оптимальному отведению памяти для так называемых рабочих ячеек. Это был, по-видимому, первый оптимизирующий транслятор.

ПП для БЭСМ [4], разработанная А.П.Ершовым, Л.Н.Королевым, В.М.Курочкиным, Л.Д.Паниной и В.Д.Поддерюгиным, развивала входной язык программирующих программ. Во-первых, она объединяла схему и спецификацию операторов в одном тексте, во-вторых, был введен первый структурный оператор, а именно — столь существенный оператор цикла (соответствующий современным циклам с параметром).

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

Следующие программирующие программы создавались в 1957 — 58 гг. для различных модификаций ЭВМ Стрела. Надо вспомнить, что серийного производства ЭВМ как такового тогда не существовало, и все производимые экземпляры Стрелы расходились в деталях архитектуры.

ПП-2 послужила идейной основой двух проектов — ПП для Стрелы 4 [5] (разработчики Н.М.Ершова, Е.А.Жоголев, Т.С.Росляков, Н.П.Трифонов и др. при идейном руководстве М.Р.Шура-Буры) и ПП для Стрелы 7 [6] (разработчики А.М.Бухтияров, Л.В.Войтишек, Н.А.Криницкий, А.А.Левина, И.В.Поттосин, Г.Д.Фролов). Важно отметить, что первая из них представляла собой зачаток настоящей системы программирования: помимо собственно транслятора она содержала систему сборки модулей и некоторые средства отладки. Транслятор получал такие фрагменты объектной программы, которые потом назовут модулями, а система сборки создавала программу из оттранслированных модулей и библиотечных программ.

ПП для Стрелы 3 [7] (разработчики Т.М.Великанова, А.П.Ершов, К.В.Ким, В.М.Курочкин, Ю.А.Олейник-Овод, В.Д.Поддерюгин) создавалась под идейным влиянием ПП БЭСМ. В ней был реализован ряд идей, новых тогда, но ставших классическими сейчас — табличный подход к синтаксическому анализу, оптимальное (по числу рабочих переменных) программирование арифметических выражений. А.П.Ершовым был независимо (и практически одновременно с Петерсеном) изобретен метод хеширования [8] , который применялся к экономии арифметических выражений.

Итак, как и обычно при становлении нового направления одновременно с созданием первых российских трансляторов — программирующих программ — шел процесс кристаллизации и оформления базовых идей и подходов и одновременно процесс создания коллективов квалифицированных исследователей, сказавших свое слово и на последующих этапах развития этого направления. Как некоторый итог этого начального этапа представляется вышедшая в 1958 г. первая в мировой науке монография А.П.Ершова [9], посвященная проблемам трансляции. Монография практически сразу была переведена и издана за рубежом [10].

Нужно заметить, что с трансляции начиналось не только системное, но и теоретическое программирование. Именно работы по входным языкам (операторным схемам) и трансляторам (программирующим программам) послужили толчком к созданию первой математической модели программ — схемам Янова [11]. Начальным толчком к появлению такой известной модели, как стандартные схемы стала работа А.П.Ершова, одного из создателей первых трансляторов по операторным алгоритмам [12].

Алголовские трансляторы

Советские работы 1953 — 58 гг. развивались независимо от мирового опыта. Практически параллельно с отечественными работами появились серьезные труды по трансляции и в США. Сопоставимый по уровню входного языка известный транслятор с ФОРТРАНа был описан в статье Дж.Бэкуса [12], появившейся в 1957г. Реальное привлечение мирового опыта к отечественным разработкам по трансляторам началось с возникновением Алгола, точнее — Алгола-58.

Параллельно с работами по программирующим программам развивался и подход к автоматизации программирования с помощью библиотек стандартных программ. Е.А.Жоголевым была разработана стандартная составляющая программа — ССП [15], которая осуществляла статическую загрузку и связывание стандартных программ из достаточно обширной библиотеки, был предложен достаточно амбициозный проект организации библиотеки и подключения подпрограмм [16]. По-видимому, кульминацией этого подхода было создание М.Р.Шура-Бурой интерпретирующей системы (ИС) ИС-2 [17], которая использовалась повсеместно на новых машинах М-20 и учитывалась всеми трансляторами нового поколения. В ИС-2 был весьма эффективно реализован способ динамического подключения библиотечных подпрограмм. ИС-2 реализовывала некоторые функции будущих операционных систем, осуществляя динамическое связывание, подкачку и смену используемых подпрограмм, причем все это делалось с небольшими накладными расходами и весьма скромными запросами на память. Высокая эффективность ИС-2 и хорошо продуманный интерфейс с основной программой сделали ее (как и положено операционной системе) неотъемлемой частьюкомплекта поставки ЭВМ.

Существенно новым шагом в развитии направления трансляции стало создание совокупности алголовских трансляторов для появившейся массовой (и уже серийно производившейся) машины М-20. Хотя язык операторных схем имел уже достаточно высокий уровень, вполне сопоставимый с уровнем тогдашней версии ФОРТРАНа, но Алгол-60 был качественно новым языком, ставившим ряд новых важных задач. Вместе с тем в стране уже был накоплен багаж базовых идей и созданы коллективы высокопрофессиональных специалистов в области трансляции, что привело к возникновению оригинальных и широко использовавшихся систем программирования.

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

Работы над этими трансляторами (ТА-2 [18] , ТА-1 [19] и АЛЬФА [20] ) начались практически сразу после публикации завершенного международной рабочей группой описания языка. Хотя, по-видимому, первым алголовским транслятором стал транслятор Айронса [21], но и ТА-1, и ТА-2 были завершены в 1963г., т.е. практически одновременно с другими известными западными работами — П.Наура [22] и Э.Дейкстры [23]. Транслятор АЛЬФА ввиду объемности реализации был завершен годом позже.

Транслятор ТА-2 (разработчики И.Х.Зусман, С.С.Камынин, Д.А.Корягин, А.С.Луховицкая, В.В.Луцикович, Э.З.Любимский, В.Б.Мартынюк, Г.М.Олейник-Овод, В.И.Собельман под руководством М.Р.Шура-Буры) встретил вызов Алгола-60 грудью, не вводя практически ограничений ни на язык, ни на размеры входных программ. В трансляторе был разработан оригинальный алгоритм программирования процедур (понимаемых как потенциально рекурсивные), мощные механизмы управления математической памятью как единства оперативной и внешней, систематически применялся метод таблично-управляемой генерации кода. В мае 1963 г. первым из всех трех этот транслятор уже демонстрировался на международной конференции по автоматизации программирования в Киеве.

Транслятор ТА-1 (разработчики В.Н.Попов, В.А.Степанов, А.Г.Стишева, И.А.Травникова под руководством С.С.Лаврова) основывался на быстрой и простой схеме трансляции (в частности, был разработан стековый подход к программированию выражений). Для достижения такой схемы авторы отказались от ряда средств Алгола-60: рекурсивности процедур, наличия статических (собственных - own) объектов в блоках, от возможности введения параметров процедур без их типизации и пр. Вместе с тем, что существенно для современных систем, особое внимание было уделено простоте и удобству эксплуатации.

В АЛЬФА-трансляторе (разработчики Г.И.Бабецкий, М.М.Бежанова, Ю.М.Волошин, Б.А.Загацкий, Л.Л.Змиевская, Г.И.Кожухин, С.К.Кожухина, Ю.И.Михалевич, Р.Д.Мишкович, И.В.Поттосин, Л.К.Трохан под руководством А.П.Ершова) особое внимание уделялось эффективности получаемых программ. Большой набор оптимизирующих возможностей (квазилокальная экономия выражений, оптимальное и весьма изощренное программирование процедур, циклов и индексных вычислений, глобальная экономия памяти и пр.) давал возможность получать объектные программы, мало отличающиеся по времени исполнения от созданных вручную программ. Платить за это приходилось большим объемом транслятора, большим числом проходов (24 прохода), отказом от некоторых средств Алгола, оптимальная реализация которых не была найдена (в частности, как и в ТА-1, рекурсивность была запрещена). Вместе с тем входной язык являлся расширением Алгола (точнее, его подмножества), включавшим ряд таких типичных для современных языков средств, как операции над многомерными значениями, комплексный тип, начальные значения переменных и пр. В целом в АЛЬФА-трансляторе начала складываться современная методология оптимизирующей трансляции с такими ее понятиями, как внутренний язык, многопроходная реализация оптимизирующих преобразований, потоковый анализ.

В целом, как уже говорилось, эта совокупность трансляторов покрывала разнообразные запросы пользователей. Для большого потока сравнительно небольших программ без особых требований к эффективности подходил ТА-1, программистам, которые хотели воспользоваться всеми возможностями Алгола, в том числе и возможностями транслировать большие задачи, был пригоден ТА-2, а для тех, кому надо было программировать задачи с большим счетом и, значит, обязательно иметь эффективный код, существовал АЛЬФА-транслятор.

В отличии от программирующих программ все алголовские системы были уже настоящими системами программирования, близкими к тому, что сейчас называется так: они включали в себя не только собственно транслятор, но также отладочные и некоторые редактирующие средства. В ТА-1и АЛЬФА-систему входили отладочные редакторы, которые по заданию на отладку создавали отладочную версию программ. Говоря по-современному, платформой для всех систем была ИС-2, все системы включали ее средства в свой входной язык и строили программы, ориентированные на ИС-2.

Языки системного программирования

Инициированное созданием трансляторов появление системного программирования поставило задачу создания адекватных языков программирования. Все языки, появившиеся к началу 60-х годов — Фортран, Кобол, Алгол-60 и др. — не учитывали этой области программистской деятельности, и алголовские системы, будучи достаточно большими программными системами, писались еще в машинных кодах вручную. Адекватные языки нужны были не только для трансляторов, но и для всей возникающей области системного программирования: начали появляться и другие языковые процессоры, и первые операционные системы, и информационные системы — все то, что потом назовут базовым программным обеспечением.

В связи с этим и у нас, и на Западе начали появляться специальные языки, предназначенные для системного программирования. Характерной для первого поколения этих языков (связанной с необходимостью хорошо учитывать архитектуру и машинное представление данных) была машинная ориентированность. Разрабатывались эти языки, как правило, в коллективах, имевших большой опыт в создании системных программ — а таковыми в тот период были системы программирования. Отечественные языки Алмо[24], Эпсилон [25], Сигма [26], которые были одними из первых в мире языков системного программирования, создавались поэтому в коллективах трансляторщиков, только что завершивших большие программные проекты и почувствовавших, каково сапожнику обходиться без сапог.

Язык Алмо имел в своей основе некоторую абстрактную машину, отражавшую особенность существовавшего тогда класса машин, и в этом отношении Алмо-подход предвосхищал появившиеся позже Р-код, М-код и прочие подобные подходы. Помимо того, что этот язык был языком реализации для системного программирования, он предназначался быть языком-посредником при трансляции с различных языков. Идея была в том, чтобы заменить трансляцию с m входных языков в n машинных языков трансляцией "из m в один" и "из одного в n". Важно заметить, что в языке существовали средства определения многопроцессности (типа fork и joint). Машинная ориентированность явно прослеживалась в языке — регистровые объекты, постфиксная запись выражений, оперирование с битами машинных слов и т.п. Были созданы реализации языка для основных отечественных машин того времени (М-20, БЭСМ-6, Минск 2, Урал 11) и трансляторы с Алгола-60 и ФОРТРАНа в Алмо, причем все трансляторы также были написаны на Алмо и "раскручены" на всех этих машинах.

Язык Эпсилон трактовал машинную ориентированность иначе. В этом отношении его идеология совпадала с одновременно появившимся языком Н.Вирта ПЛ360, ставшим прототипом большого числа языков системного программирования того времени: средства высокого уровня необходимы для естественного (для программиста) одевания конструкций машинного языка. Семантика каждой конструкции языка определялась сопоставленным ей образом — последовательностью операций машинного языка. При этом, конечно, рекомендовалось, чтобы образы для разных машинных языков были бы в определенной мере аналогичны, однако переносимость не обеспечивалась, за ней надо было следить. Типы данных языка тоже следовали за назначением языка и его машинной ориентированностью — допускались целые (но не вещественные), классы двоичных значений, слоги машинных слов или их последовательности. Эпсилон тоже был реализован для большого числа архитектур — М-20, БЭСМ-6, Минск 2. Существенно, что при создании многопроцессорной архитектуры АИСТ-0, Эпсилон играл такую же роль, как впоследствии Си для Юникса или Эль-76 для Эльбруса — был базовым системным языком, на котором писалось все многочисленное системное обеспечение, от ядра ОС до системных программ, ориентированных на пользователя.

Язык Сигма обладал двумя важными и в то время новыми особенностями. Синтаксически ограничиваемый макросами, он, как и более поздний Форт, допускал генеральную линию создания программ — подстановку описанных макросов. Язык содержал средства формального описания конкретной архитектуры: была разработана система параметров, в терминах которой фиксировалось представление языка для конкретной ЭВМ. Таким образом, общая Сигма-программа вместе с описанием архитектуры ЭВМ транслировалась на данную ЭВМ. Параметрами архитектуры были как такие, как длина слова, представление значений типов в машинном слове и т.п., так и правила заполнения шаблонов машинных команд.

Заключение

Таким образом, вспоминая славные дни становления у нас в стране трансляции как области исследований и разработок , авторы, как кажется, сумели показать, что российские коллективы всегда находились на высоком научном уровне. Подходы и системы, о которых здесь рассказывалось, были выбраны в качестве той линии, к которой авторы имели непосредственное отношение. Часть российских работ, лежащая вне этой линии, здесь не рассматривалась — более широкое рассмотрение всех работ тех лет можно найти в обзоре [28, 29], а языки системного программирования тех и более поздних лет рассматриваются более подробно в [30].

Цитируемые источники

  1. H.Rutishauser. Automatishe Rechenplanfertigung bei programmgesteuerten Rechenmaschinen / Miff. Inst. fur Angew. Math. dec ETH Zurich. — N 3. — 1952.
  2. А.А.Ляпунов. О логических схемах программ // Проблемы кибернетики. — вып. 1. — М.:Физматгиз, 1958. — С. 46-74.
  3. С.С.Камынин, Э.З.Любимский, М.Р.Шура-Бура. Об автоматизации программирования с помощью программирующей программы // Проблемы кибернетики. — вып. 1. — М.:Физматгиз, 1958. — С.135-171.
  4. А.П.Ершов. Программирующая программа для БЭСМ АН СССР // Тр. конф. "Пути развития советского математического машиностроения и приборостроения". — ч.3. — М.:ВИНИТИ, 1956. — С.18-29.
  5. Система автоматизации программирования // Под ред. Н.П.Трифонова и М.Р.Шуры-Буры. — М.:Физматгиз, 1961. —- 187 с.
  6. А.М.Бухтияров, Л.В.Войтишек, А.А.Левина, Н.А.Криницкий и др. Программирующая программа ПП-С // Сб. научных трудов № 1. — МО СССР. — М., 1959.
  7. Т.В.Великанова, А.П.Ершов, К.В.Ким, В.М.Курочкин и др. Программирующая программа для машины "Стрела" // Тез.докл. сов. по вычисл.матем. и прим. средств выч.техники. — Изд-во АН АзССР. — Баку, 1958.
  8. А.П.Ершов О программировании арифметических операторов // Докл. АН СССР. — 1958. — ч.118. — № 3. —С.427-430.
  9. А.П.Ершов. Программирующая программа для быстродействующей электронной счетной машины // Изд-во АН СССР. — М, 1958. — 116 с.
  10. A.P. Ershov. Programming program for the BESM computer / Pergamon Press. — London, 1959. — 158 p.
  11. Ю.И.Янов. О логических схемах алгоритмов // Проблемы кибернетики. — вып. 1. — М.:Физматгиз, 1958. — С.75-127.
  12. А.П.Ершов. Об операторных алгорифмах // Докл. АН СССР. — 1958. — т. 122. — № 6. — С.67-970.
  13. J.W.Backus. The FORTRAN automatic coding system / WJCC. — 1957. —- P.188-198.
  14. С.С.Камынин, Э.З.Любимский. Автоматизация программирования // Тр.конф. "Пути развития советского математического машиностроения и приборостроения". — ч. 3. — М., 1956. — С.9-17.
  15. Е.А.Жоголев, Г.С.Росляков, Н.П.Трифонов, М.Р.Шура-Бура. Система стандартных подпрограмм // М.:Физматгиз,1958. — 231 с.
  16. Г.И.Кожухин, Н.М.Нагорный, И.В.Поттосин. Принцип организации и использования библиотеки программ // Сб. "Вычислительная математика". — Изд-во АН СССР. — М. — 1961.
  17. М.Р.Шура-Бура. Система интерпретации ИС-2 // Сб. "Библиотека стандартных программ". — М.:Изд-во ЦБТИ, 1961.
  18. М.Р.Шура-Бура, Э.З.Любимский. Транслятор АЛГОЛ 60 // ЖВМиМФ, 4. — № 1. — М. — С.96-112.
  19. В.Р.Попов, В.А.Степанов, А.Г.Стишева, Н.А.Травникова. Программирующая программа // ЖВМиМФ, 4. — № 1. —- М., 1964. — С.78-95.
  20. Г.И.Бабецкий, М.М.Бежанова, Ю.М.Волошин, А.П.Ершов и др. Система автоматизации программирования АЛЬФА // ЖВМиМФ. — 1965. — Т.5. — № 2. — С.317-325.
  21. E.T.Irons. A sintax directed compiler for ALGOL 60 // CACM, /№4. — Jan. 1961. — P. 51-55.
  22. P.Naur. The design of the GIER ALGOL compiler // BIT. — №3. — 1963. — P.124-140.
  23. E.W. Dijkstra. An ALGOL 60 translator for the X1 // Ann.R. — №3. — 1963. — P.329-356.
  24. C.С.Камынин, Э.З.Любимский. Алгоритмический машинно-ориентированный язык АЛМО // Сб. "Алгоритмы и алгоритмические языки". — Изд-во ВЦ АН СССР. — 1967. — вып.1.
  25. И.В.Поттосин, А.Ф.Рар, В.Л.Катков. ЭПСИЛОН - система автоматизации программирования для задач символьной обработки // Тр. 1-ой Всесоюзной конф. по программированию. — Киев, 1968.
  26. A.P.Ershov, A.F.Rar. SYGMA, a symbolic generator and macroassembler // In "Symbol manipulation languages and technique". — North-Holland Publ. Co., 1968.
  27. N.Wirth. PL 360, Programming Language for the 360 Computers // JACM. — v.15. — № 1. — 1968.
  28. А.П.Ершов, М.Р.Шура-Бура. Становление программирования в СССР // Кибернетика. — 1976. — №6. — С.141-160.
  29. A.P.Erschov, М.R.Shura-Bura. The Early Development of Programming in the USSR // A History of Computing in the Twentieth Century, Academic Press. — 1980. — P.137-196.
  30. И.В.Поттосин. Языки реализации для системного программирования // Новосибирск, 1979. —24 с. —(Препринт/Сиб. Отд-ние АН СССР. ВЦ; №179)