Отдел программирования ВЦ СО АН СССР и языки

Берс А.А.

Начнём с ретроспективного взгляда на смену парадигм вычислительного дела с 1950–х годов по десятилетиям, выделяя в каждом из них главную парадигму (ведущий, или просто модный подход), определяющую содержание этого десятилетия.

Прогноз 2000 года о том, чем мы будем заниматься в этом тысячелетии, пока оправдывается. Развивается спецификация взаимодействия субъектов между собой в качестве нового способа описания проблем. В смешанном исполнении, когда трансляция и интерпретация переслаиваются так, как нам это надо, это хорошо подтверждается JIT–ерами. Есть достижения и в эффективности параллелизма. Все большую роль начинают играть виртуальные машины, которые я призываю называть Вирт–машинами, Никлаус Вирт этого заслуживает. А вот из диктовки машинам пока ничего не получается, хотя читать с листа они, как известно, уже научились.

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

Переход от составления программ для ЭВМ к выражению программ на языках высокого уровня – наЯВУ (1961 г.) практически совпал со временем, когда я приехал в Сибирское отделение, в Академгородок, и начал работать в Отделе программирования.

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

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

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

Достижению поставленной цели послужил богатый набор оптимизаций, реализованный в Альфатрансляторе. Была предложена смешанная стратегия программирования таких конструкций, как процедуры, циклы, индексные выражения. На основании анализа контекста выбирался способ генерации конструкций, наиболее эффективный из допустимого набора. В результате процедуры при всей мощности этого механизма программировались оптимальным образом (что стимулировало программистов активно их использовать). Существовавшая ранее оптимизация экономии выражений была существенно развита – полностью учитывались свойства коммутативности и ассоциативности; она уже стала квазилокальной. Впервые была реализована глобальная чистка циклов. Тщательной оптимизации подвергались операции над многомерными значениями – то, чего не было в стандартном Алголе, но активно использовалось вычислителями. Впервые была реализована глобальная экономия памяти, опирающаяся на теоретические работы А.П. Ершова и С.С. Лаврова.

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

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

Альфа-транслятор, несмотря на его достаточно широкое использование, носил черты экспериментального проекта: идейные решения были найдены верно, по реализационные решения были характерны скорее для пилотного решения, чем для производственного транслятора (большое число просмотров программы – 24, некоторое дублирование анализа контекста, не всегда оправданное усложнение оптимизирующих преобразований). Однако не нужно забывать, что этот транслятор был первым оптимизирующим транслятором с Алгола. Новый транслятор – Альфа-6 – был улучшенной версией оптимизирующего транслятора с Алгола. Ряд предыдущих решений был приведен к более чистому и эффективному виду. Более четко был выделен внутренний язык и этап потокового анализа программ на внутреннем языке. Общая схема трансляции уже могла рассматриваться как типовая схема оптимизирующей трансляции (для одноязыкового транслятора), она насчитывала всего 10 просмотров. Лучше была решена проблема взаимного влияния различных оптимизирующих преобразований. Идентификация и визуализация ошибок пользователя была более совершенной, что облегчало эксплуатацию. В результате Альфа-6 стала достаточно широко используемой системой у пользователей БЭСМ-6.

Отдел программирования ВЦ СО АН СССР быстро стал ведущей, мирового уровня, точкой роста и развития языкового программирования. Здесь языки создавались, исследовались и реализовывались как в практическом, так и в теоретическом планах.

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

Именно это побудило разработчиков системы Альфа М. Бежанову, Б. Загацкого и И. Поттосина взяться за создание языка для собственных нужд. Вместо какого-либо расширения Алгола (или Альфа-языка), которое включило бы удобные средства, решили пойти другим путем. Хотелось мыслить в терминах непосредственного исполнения машинного языка, в терминах двоичных кодировок, упаковки информации в машинные слова и пр., но только облекая все в более удобные одежды, отличные от синтаксиса машинного языка. Иначе говоря, от «нашего» языка разработчики хотели близкой к машинному языку семантики и удобной для человека синтаксисической формы. Заметим, что подобная же, по–видимому, идея была и у Никлауса Вирта, когда он создавал ориентированный на архитектуру ИБМ/360 язык ПЛ/360, ставший прототипом большого числа так называемых машинно-ориентированных языков. Второе, из чего исходили – это скорость трансляции при хорошем качестве получаемых программ. Не предполагалось практически никакой оптимизации и с самого начала считалось, что язык будет содержать только такие конструкции, о которых заведомо известно, как их эффективно реализовать. В каком–то смысле это привело к обеднению языка, и он–таки получился достаточно элементарным, так что его назвали с горделивой скромностью – «Эпсилон», что подчеркивало, что это заведомо «маленький» язык. В частности, это сказалось на наборе операторов управления: только операторы перехода и условного перехода. Выражения были только бинарными; язык был бестиповым: значение предполагалось двоичным, а его понимание зависело от операции; структурных значений всего два типа – машинное слово, разбитое на последовательность слогов, возможно различной длины, и вектор одноразмерных слогов, занимающий последовательность машинных слов и т.п.

Формирование языка происходило в жарких спорах, в поисках компромисса: пройти между Сциллой недостаточно хорошей выразительности и Харибдой неэффективной реализуемости. Решения принимались, потом отвергались, с изменениями и модификациями к ним возвращались снова. К первоначальному коллективу присоединился А. Рар с его хорошим чувством языков и В. Катков; много советов было получено от Г. Кожухина.

Система Эпсилон-М. Окончательную версию языка сделали к маю 1967 г. и сразу же приступили к созданию транслятора для М-220. Но поскольку реализация языка уже просматривалась при его разработке, на написание транслятора ушло меньше месяца. Сам транслятор был написан тоже на Эпсилон, т.е. была осуществлена раскрутка (bootstrapping), благодаря чему все дальнейшее развитие системы осуществлялось с помощью ее самой. С осени 1967 г. началась опытная эксплуатация системы, в которой активно участвовали Т. Панкевич и Г. Плотникова. Итак, система работала, доводилась, развивалась. Она использовалась и в ВЦ СО АН СССР, и в других организациях. С се помощью были написаны многие системы: и языковые процессоры, и системы компьютерной алгебры, и т.д. Особую роль она играла как основной инструмент написания программного обеспечения системы коллективного пользования АИСТ–0: все программное обеспечение размером в несколько сотен тысяч команд – и операционные системы, и трансляторы, и информационные системы, и системы компьютерной алгебры, и игровые программы – было написано на Эпсилон. Только ядро ОС, работавшее на Минске-22, было написано в мнемонике Минска.

К концу 1969 года была разработана система Эпсилон-М, она уже включала, помимо немного модернизированного транслятора, где был реализован во всей полноте механизм открытых процедур, отладочный редактор, который вставлял в исходный текст операторы, реализующие заданные операции отладки, контроль исходного текста, вставку библиотечных процедур. Все эти работы, как уже говорилось, использовали язык Эпсилон как инструмент. В 1969 А. Хоперсков начал работу над вариантом транслятора для БЭСМ-6. Хотя общие алгоритмы трансляции уже были опробованы в системе для М-220, но надо было их трансформировать для БЭСМ-6, а кроме того, доопределить семантику языка применительно к БЭСМ–6. Поскольку машинно– независимая семантика (так называемый эталонный уровень семантики) Эпсилон только частично покрывала семантику языка, то в полной семантике каждой конструкции языка сопоставлялся ее образ в машинном языке. Вот создание таких образов для БЭСМ-6 и было одной из задач А. Хоперскова, в начале 1970 года он уже завершил разработку и отладку системы Эпсилон-БЭСМ-6. Системы Эпсилон успешно эксплуатировались на разных компьютерах, пока они (кроме БЭСМ-6) не были вытеснены «отечественными» ЕС ЭВМ. Где-то году в 1974-м была предпринята попытка разработать систему Эпсилон для ЕС ЭВМ, но неудачный выбор разработчиков не дал осуществиться этому проекту. Язык Эпсилон ушел в прошлое вместе со старыми компьютерами, но сыграл большую и очень полезную роль в создании различных программных систем для них.

Языки разработки системного математического обеспечения – ЯРМО (последняя версия – ЯРМО-3) – были снабжены средствами, адекватными проблемной области применения. Главным следует считать наличие в ЯРМО системы типов, а также принятую концепцию разделения программы и средств управления ее реализацией, введенную как обособленная единица, факультативная по отношению к основному тексту программы. Среди особенностей ЯРМО-3 назовём также развитый механизм конструирования типов, позволяющий говорить о поддержке языком работы с абстрактными типами данных.

Структура языка подразумевает переносимость создаваемых программ, с этой целью проводится выделение языковых средств, входящих в «машинно–независимое ядро», которое содержит средства, отражающие фундаментальные концепции языка, поддерживаемые любой его реализацией. Это – встроенный набор типов, механизмы конструирования новых типов, процедурный механизм, управляющие конструкции, машинно– независимое управление реализацией. В машинно–зависимой части определяется базовый набор описаний. Такое разграничение позволяет компилятору анализировать степень зависимости текста на ЯРМО-3 от конкретной реализации, т.е. дает возможность определять, какие изменения в тексте программы необходимо сделать для того, чтобы осуществить ее перенос на новую вычислительную среду.

Принятая в ЯРМО-3 модель типа данных отражает строение типа как совокупности набора операций и множества значений; последнее разбито на подмножества, называемые «представления». Существенной особенностью типа в ЯРМО является множественность представлений. «Реальные» типы данных имеют в общем случае более одного представления, например, можно привести тип «комплексный», имеющий представление как в полярной системе координат, так и в виде пары вещественной и мнимой частей. Представления типов могут различаться не только на логическом уровне, но и на физическом: можно упомянуть различия в способе хранения массивов или в представлении вещественных чисел. Поэтому модель типа в ЯРМО-3 обладает тождественностью представлений как адекватным средством отображения «реальных» типов. Над значениями типа действуют операции, каждая из которых определена над некоторым декартовым произведением представлений. При этом результатом операции не обязательно является значение этого же типа.

Существуют приведения от обозначения к имени и далее к значению. Обозначение требуется лишь в позиции параметра встроенной операции, выдающей значение указательного типа, а также в позициях параметров атрибутов. Имя требуют: операнд присваивания (в левой части), выборки элемента из массива и выборки поля структуры, во всех остальных случаях производится считывание. ЯРМО-3 постулирует обязательное наличие у каждого типа следующего набора операций: генератор, присваивание, считывание и сравнения (на равенство и неравенство). Генератор может трактоваться как исполняемая статически (т.е. во время компиляции) операция создания объекта. Присваивание изменяет значение объекта; посредством присваивания осуществляется передача параметров подпрограммам. Операция присваивания требует, чтобы в левой ее части находилось либо выражение, выдающее имя, либо результат применения встроенной операции «косвенность» к значению указательного типа. Считывание выдает значение объекта по его имени, а операции сравнения на равенство и на неравенство устанавливают идентичность либо различие двух значений типа, отмечая этот факт соответствующим значением встроенного типа ЛОГ в качестве результата.

В язык встроен следующий набор типов, соответственно обозначенные «НИЧТО», «БИТ», «ЦЕЛ», «ЛОГ», «СТР» и «ВЕЩ», которые являются априорными по отношению к любой программе на ЯРМО-3. Тем не менее, не исключается возможность их переиспользования, что достигается организацией контекстов. Для каждой бинарной операции, определенной для встроенных типов, предопределена такая же операция, совмещенная с присваиванием.

На язык оказали влияние Алгол-68 и Ада. Первый повлиял на концепцию типа – в ЯРМО-3 есть, например, понятие «приведение», хотя оно и отличается от аналогичного понятия в Алголе-68, второй – на принятый в языке механизм ситуаций; оба – на стиль написания программ и модульность строения.

Следует сказать, что хотя ЯРМО-3 разрабатывался как язык, ориентированный на системное программирование, что, в частности, наложило отпечаток на требование «хорошей» реализуемости языковых конструкций, тем не менее, он обладал довольно высокой степенью универсальности, что можно отнести к его достоинствам.

Поддержка методологии абстрактных типов данных, разделение программы и средств управления ее реализацией, гибкость работы с объектами давали возможность «прикладным» программистам создавать проблемно– ориентированные контексты и работать как в рамках данных контекстов, так и в условиях их взаимодействия.

Функциональные языки и экспериментальные системы программирования. Для многих учеников А.П. Ершова типичной темой дипломной работы была реализация какого–либо нового, модного, недоступного у нас или свежесочинённого языка программирования. Некоторые разработки представляли собой интеллектуальный вызов мировым авторитетам. Другие возникали как элементы технологии программирования в наших реальных условиях.

В конце 1968 года в кабинете А. П. Ершова Джон Маккарти прочел серию лекций, посвященных языку Лисп. Возможность практичного применения такого языка даже на нашей лучшей ЭВМ БЭСМ–6 вызывала сомнения у специалистов. Версия экспериментальной реализации полного Lisp 1.5 в условиях ограниченного машинного времени потребовала изрядной изобретательности, поиска результативных проектных и технологических решений. Например, для представления интерпретатора был предложен специальный язык загрузчика, удачно сочетавший эффективность программирования в кодах с гибкостью символьной обработки. В результате за 5 минут удавалось пропускать более 5 колод по 1000 перфокарт. Протокол работы программы начинал печататься моментально, сразу вслед за завершением приема перфокарт. Это определило результативность отладки Лисп-интерпретатора.

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

Лисп-система на БЭСМ-6 упоминается в книге «Мир Лиспа», один из авторов которой бывал в Новосибирске и очень дотошно вникал во все детали. В Мюнхенском музее Лиспа хранится публикация о новосибирском Лисп-проекте. Основное применение системы – исследования в области верификации программ, эксперименты по организации недоопределенных вычислений и конструированию семантических моделей.

Советская разработка системы программирования и компилятора для языка Little на БЭСМ–6 была выполнена Л.В. Городней в 1976 году. При реализации этой системы па макроассемблере было предложено и экспериментально опробовано комплексное решение ряда технологических проблем для обеспечения машинно– зависимого переноса программ без кросс–трансляции. Решение основано на идеях вертикального расслоения программ, функциональной декомпозиции на простые классы семантических систем, синтаксическое и семантическое управление конфигурированием компилятора, виртуального кода программы и оптимизирующей кодогенерации. Опыт этой разработки дал материал для формализации реализационной семантики языков программирования в виде интерпретируемых сетей, допускающих сетевое определение правил их функционирования. Кроме того, была выполнена систематизация требований ЕСПД к программной документации, которые реализованы в форме, сходной с гипертекстом.

Теоретико-множественный язык Сетл был предложен и разработан в начале 70-х годов профессором НьюЙоркского университета Джекобом Шварцем. Это стало выдающимся событием: математик с мировым именем смело вошел в область программирования с радикальным практическим предложением, которое состояло в том, чтобы, базируясь на множествах как основных типах данных, писать программы в терминах высокоуровневых непроцедурных алгоритмов, широко использующих логико–предикатные средства. В 1972 году Дж. Шварц по пути из Китая сделал короткую остановку в Новосибирске и рассказал о Сетле на семинаре в Вычислительном центре. Организация этого выступления и последующего проекта Сетл в Новосибирске стали еще одним подтверждением выдающейся чуткости А.П. Ершова к фундаментальным тенденциям в программировании.

Появление Сетла обрадовало и заинтересовало А.А. Ляпунова, известного своими фундаментальными результатами в теории множеств, до такой степени, что он откомандировал только что вернувшегося из армии сотрудника своей лаборатории «заниматься Сетлом к Ершову». Высокий профессионализм, творческий энтузиазм, прекрасная атмосфера интеллигентного коллектива, интересная задача помогли Д. Левину быстро включиться в проект Сетл. Новосибирская Сетл-команда сформировалась естественным образом. Л.В. Городняя и Л.В. Черноброд к этому времени уже обладали огромным опытом работы с языком Лисп и его реализацией. Вкус к языку повышенного уровня, динамике данных, знание фундаментальных принципов и тонкостей этой области позволили им быстро оценить новый проект и энергично приступить к его реализации. Применение Лиспа для моделирования семантики Сетла имело свои преимущества и недостатки. С одной стороны, операции с подвижными и иерархическими множествами, включая необходимую для них сборку мусора (garbage collection), хорошо поддерживались базовыми механизмами Лиспа. С другой стороны, поскольку множества – это далеко не списки, то реализация ассоциативных выборок, построение теоретико-множественных объединений, пересечений, дополнений и др. в принципе не могли быть эффективно реализованы на Лиспе. Опыт Лиспреализации и полученные к тому времени результаты группы Дж. Шварца (версия Balm-Setl) показали, что продвижение к эффективной реализации нового языка лежит через построение специальной виртуальной машины, прицельно поддерживающей основные элементы теоретико–множественного программирования. Создание такой машины, версии входного языка, компилятора и окружения стало задачей разработчиков в 1973–75 годах.

Сравнительно быстрому получению практических результатов способствовал выбор в качестве средства реализации Сетла системы Эпсилон-БЭСМ-6. Роль Эпсилона оказалась тем более важна, что почти в то же самое время в группе Шварца началось применение аналогичного средства – языка Little. Реализация Сетл – Эпсилон имела свои плюсы и минусы, но эта быстрая, прагматичная, с изощренными алгоритмами реализация позволила почти сразу начать довольно широкое программирование на Сетле.

Это было прекрасное время безоглядной «игры мускулами» – возможностями очень быстро написать почти неалгоритмическую программу и наслаждаться ее работоспособностью. Было, например, проведено моделирование весьма модной в те годы fuzzy logic. Сделано это было на примере системы, которая по фразе вроде «Нарисуй небольшой круг в правом нижнем углу экрана, а над ним – маленький квадрат» действительно выдавала на АЦПУ похожую конфигурацию, очерченную звездочками. Это была лишь игрушечная иллюстрация, с одной стороны, фундаментальной лингвистической модели «Смысл – Текст», восходящей к известному советскому лингвисту И. Мельчуку, а с другой – глубокого проекта «Рисунок–Информация–Текст», выполнявшегося под руководством А. Нариньяни.

В это же время появились первые отечественные публикации о Сетле. Наряду со статьями о Сетл – Лисп и Сетл – Эпсилон большое значение имела работа В. Касьянова, посвященная оптимизации. Действительно, «повышенный» уровень языка Сетл, новые типы данных, операции и языковые конструкции могли стать серьезным вызовом для развития и применения оптимизационной техники. В 1974 году на Всесоюзной конференции в Бакуриани, при первом выходе Сетла «в свет», проявился явный и глубокий интерес профессионалов к этому проекту. Вообще, отношение к Сетлу было всегда заинтересованное и благожелательное. Наряду с А. П. Ершовым – А. Берс, В. Котов, С. Лавров, Э. Любимский, Э. Тыугу, И. Поттосин, А. Фуксман и другие сразу оценили стратегическое значение вклада, сделанного Дж. Шварцем, и постоянно проявляли живой интерес к отечественному проекту.

Особое влияние на судьбу новосибирского проекта Сетл оказал А.С. Нариньяни, который предложил широко использовать его для экспериментального программирования задач искусственного интеллекта (ИИ). Это был по–настоящему смелый и мудрый поступок, поскольку респектабельность в области ИИ предписывала пользоваться Прологом, а профессиональное программирование демонстрировало безнадежную неэффективность языков высокого уровня. Позиция Нариньяни была свободна от консерватизма: Пролог намертво фиксировал как раз то, что должно было составлять суть экспериментов в ИИ, а «неэффективность» давно следовало трезво оценивать с позиций требований конкретных приложений.

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

Первым заметным сибирским применением Сетла была реализация с его помощью прототипа системы общения с базой данных на естественном языке, выполненная в 1976 году. Прототип состоял из словаря, лингвистического процессора, переводящего естественно–языковые запросы к базе данных в стандартизованный язык СУБД, а также из собственно макета СУБД, включая наборы демонстрационных данных. Лингвистический процессор был построен как компилятор, осуществляющий несколько проходов и основанный на продукционных правилах, которые принимали во внимание главным образом лексико–синтаксическую информацию. Макет СУБД хорошо подтверждал исходное предположение Шварца о естественности применения Сетла для работы с базами данных.

У этой Сетл-программы, занимавшей не более двухсот строк и за 12 секунд отвечавшей на вопросы типа «Кто завлаб в лаборатории, где средняя зарплата не меньше 150 рублей?», оказалась хорошая история. Во-первых, ее многочисленные варианты эффектно демонстрировались затем лет десять применительно к дюжине языков и нескольким предметным областям. Во-вторых, она послужила зерном, из которого выросли развитые обстановки для создания процессоров естественного языка. В-третьих, из нее выросла система СТЕНД – интегрированный инструментальный комплекс программирования, который явился наивной, но благородной попыткой построить «полную» инструментальную среду, в которой программист не должен был опускаться ниже уровня Сетла. А выше Сетла были продукционные системы, СУБД, а самое главное – конструктор виртуальных процессоров. В идеале программы виделись как суперпозиции троек процессоров: данных, вычислений и интерфейсов. Заметное оживление Сетл–деятельности наблюдалось в ходе легендарного проекта СТАРТ (1985–1988 г.).

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

Вспомним, что исходной идеей Шварца был язык абстрактных алгоритмов. С одной стороны, абстрактные алгоритмы должны были реально исполняться и давать полноценную возможность прототипирования. Уже в 1976 году в наших проектах появились библиотеки представлений множеств и методов работы с ними. В чем– то этот подход даже опережал время, но в нем был и свой источник трудностей: отсутствие индустриальной базовой системы программирования и закрытость набора методов. Сегодня теоретико–множественная оболочка могла бы вполне продуктивно работать на основе С++ или Java.

Хорошим тоном в Отделе программирования ВЦ СО АН СССР считались отслеживание новейших работ по созданию языков программирования (например, PL/1 или Симулы–67), а также и непосредственное участие в разработках языков в международных командах. Это, главным образом, относится к работам по Алголу 68, поскольку А.П. Ершов был членом рабочей группы РГ.2.1 ИФИП по Алголу. Мы не только оперативно анализировали текущие материалы по языку, не только вносили свои замечания и предложения, но и создавали своё видение будущего «русского национального варианта» этого международного языка.

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

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

Алгол 68 позволял писать очень красивые и сложные выражения и программы связного характера. Язык получился довольно стройный и сыграл большую роль в упорядоченнии и ректификации свойств и понятий. Некоторой сложности ему добавляло, на мой взгляд, стандартное вступление, которое составляло четверть описания языка. Это был еще более сжато написанный на самом Алголе 68 программный текст с дополнительными надстройками макросного характера. Заметим, что в современных языках самого–то языка мало, преобладают большие описания библиотек, заголовки которых называются функциями, конечно, назло всем математикам. С этой точки зрения мне представляется, что Алгол 68 был академическим языком, он так и не стал производственным. Сейчас можно проследить, как много от него осталось идей. То, что типы можно описывать как угодно, какими угодно способами, переросло в понятие класса. Это было несколько иначе сделано в Симуле, и потом «перекочевало» в С++.

Языки программирования всегда тащили за собой английский жаргон, причем не язык, а именно жаргон. Поэтому в наших работах по Алголу 68 существенным было создание русского национального варианта Алгола 68. Мы с Ершовым стремились к тому, чтобы весь текст программы можно было напечатать без латинских букв и чтобы программы можно было бы практически читать вслух – вещь недоступная для предыдущих языков. В «Пересмотренном сообщениии об Алголе 68» удалось включить в текст правила, регламентирующие создание законных национальных вариантов этого международного языка. В 1979 году вышел мой перевод «Пересмотренного сообщения», и там удалось добиться того, что параллельно с оригиналом описания на развороте размещалось русское описание, в котором можно было все синтаксические правила читать как достаточно естественные предложения русского языка. А синтаксис вообще удалось перевести как стихи – все правила сохранили и семантический и мнемонический смысл, и точную форму. Один из эпиграфов был заменен цитатой из Платоновского «Кратила», которая явно подчеркивала намерения переводчика: «Сократ: Однако, если ... имена должны быть выражением чего–либо, знаешь ли ты иной, лучший способ создать эти выражения, нежели сделать их возможно более тождественными тому, что они должны выразить?».

Люди всегда будут думать на своем родном языке, хотя пока еще, к сожалению, не появилась …ская национальная версия для каждого языка программирования. Кстати, в самих языках программирования английский всё–таки превалирует, но вот что касается рабочих и операционных обстановок, то с ростом роли персональных компьютеров одноязычье не прошло и все привело нас к тому, что национальные версии систем программирования и операционных систем таки есть! – в конечном итоге не прошло и 35 лет.

Проект Бета. Накопленный в оптимизирующей трансляции опыт дал возможность перейти к следующему новосибирскому трансляторному проекту – многоязыковой транслирующей системе Бета. И мне кажется, что здесь прежде всего нужно упомянуть выдающийся прорыв, который сделал Андрей Петрович, придумавший одновременную реализацию трех языков.

Каждый из нас воспитывался в каком–то алгоритмическом языке, мы были в основном алголики, Курочкин был фортранец. Вдруг оказалось, что есть три больших языка, семантически достаточно похожих и достаточно разнообразных, и тем не менее их нужно реализовать все вместе. И в результате мы были «вытащены» в надъязыковую позицию, и с этой точки зрения хорошо сравнить нас и А. Терехова, который реализовал Алгол 68, но в его стиле и застрял надолго... Он за пределы идеологии Алгола 68 никак не мог выйти. И вот эта ситуация выхода в надъязыковое пространство представляется мне одним из выдающихся достижений А.П. Ершова. По крайней мере, в моей проектно–программной жизни выход этот сыграл очень большую роль.

Цели проекта БЕТА были весьма амбициозные, недаром название проекта расшифровывалось самим А.П. Ершовым в шутку как Большая Ершовская Трансляторная Авантюра. Предполагалось, что будет создана открытая транслирующая система с высоким уровнем глобальной оптимизации программ, охватывающая практически весь тогдашний класс императивных языков высокого уровня и ориентированная да получение программ для большинства существующих архитектур. Речь шла о создании мощной базовой системы трансляции, одноязыковые трансляторы в которой выглядели как частный случай. Забегая вперед, нужно сказать, что в принципиальном отношении задача была решена.

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

Начальный этап проекта в значительной мере определялся исследованиями по внутреннему языку, который мыслился как семантический базис, унифицирующий языковые средства входных языков, как основа оптимизации программ и как общее исходное представление программ для генерации кода. Окончательная версия внутреннего языка была создана как объединение абстракций общих понятий и конструкций широкого спектра входных языков с включением не полностью интерпретируемых языково–зависимых конструкций. Версия эта была построена на анализе большого числа существовавших тогда языков программирования – Алгола 60, ПЛ/1, Симулы-67, Алгола 68, Паскаля, на выделении общностей этих языков – в системе типов, в управляющих конструкциях, на построении абстракций, как отражающих эти общности, так и дающих простор для включения специфических средств данного языка. Вся эта работа была частью общемировых исследований по внутренним языкам и помимо своей конструктивной роли для БЕТА–проекта обогатила понимание общей содержательной семантики существующих языков программирования.

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

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

Таким образом, в системе БЕТА были развиты в сторону кристаллизации те понятия оптимизирующей трансляции, которые были найдены в Альфа–проектах: внутренний язык стал действительно единым, потоковый анализ был выделен как отдельный фрагмент, да и само выполнение языково–независимых оптимизаций было выделено в отдельный компонент транслирующей системы, который мог привлекаться по желанию пользователей.

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

Оптимизирующий процессор не зависел ни от входного, ни от выходного языка – языково–зависимые конструкции внутреннего языка снабжались нужными для оптимизации атрибутами и были в этом смысле частично интерпретируемы. Вначале предполагалось, что как получение абстрактной программы, так и генерация кода будут строиться специальными мета–процессорами по описанию входного и выходного языков соответственно, однако в окончательной версии победил модульный подход. Была сделана библиотека модулей декомпозиции, фактически вводящая обобщенные операции, в терминах которых строились лексический, синтаксический и контекстный анализ для конкретного языка. Точно также была создана библиотека генерации кода, включавшая модули общих для генерации действий – обхода программы на внутреннем языке, назначения регистров (с учетом конкретных параметров архитектуры) и пр. Как показал опыт, общая часть декомпозиции и генерации кода (оптимизация была универсальной) составляла, в зависимости от языка, от 40% (Ада) до 60% (Паскаль).

В целом этот проект был интересным экспериментом в трансляции программ, по своему размаху превосходящим другие опыты многоязыковой трансляции, существовавшие в мире. Были реализованы Симула 67, Паскаль, Ада и Модула–2, причем два последних языка, не участвовавшие в выработке схемы трансляции и внутреннего языка, хорошо вписались в систему, что свидетельствовало о надежности принятых в проекте решений. Целевыми машинами были столь разные архитектуры, как БЭСМ–6 и СМ–4. Область трансляции стала традиционной для новосибирцев. Было реализовано множество трансляторов для различных языков – от Сетла до Оберона, традиции многоязыковой трансляции были продолжены в биязыковой системе программирования ХDS.

Теперь посмотрим на значение перехода к языковой парадигме в целом. Мы перешли на знаковые формы, на тексты программ. Появилась возможность писать содержательные обозначения, появился, как у всяких текстов, синтаксис. Важно обратить внимание на то, что у программных текстов с самого начала имеются две семантики. Сама семантика текстов, которая позволяла использующие вхождения соотносить с определяющими вхождениями, делать идентификацию, организовывать движение по тексту и вызывать процедуры. С другой стороны – семантика исполнения, про то, что будет делаться, когда программу преобразуют и приведут к форме, пригодной для исполнения на машине. И вторых семантик изначально было несколько, например, императивная или дескриптивная и пр. Естественно, что появились все основные структуры, которые мы все прекрасно знаем: оисания, операции, выражения, операторы. Следование, переходы, ветвление, циклы, вызовы. Блоки, модули, файлы и т.д.

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

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

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

Далее имело место усиление выраженческого характера языка. Я считаю, что Алгол 68 был ведущим в этом отношении, потому что возможность написать сложное выражение и по дороге что–то там же оставить, присваивая значение этого выражения, и теперь хорошо используется. Это тот самый вариант, когда один раз мы значение выражения использовали, а оно нам еще будет нужно, вот мы его и спрятали. Раньше для этого надо было выходить в другую (рефлексивную) позицию рассуждений, не вычислений, а именно рассуждений, которые проводились. Сейчас в объектных языках всё очень хорошо: вы должны с помощью этого значения привести объект в определенное состояние. Приведя, вы можете из этого состояния вычитывать это значение столько раз, сколько вам надо, и получите, что оно обозначало.

Учет национальных особенностей и адаптация языков программирования к региональным алфавитам оказались проблемой. Естественно, что все программы, которые писались на Западе, писались по–английски. Против этого возражали активно только французы и весьма активно – наш Отдел программирования. Мы этим делом занимались всерьез, причем воевать приходилось не только с американцами, но и с нашими, например, со многими москвичами. Теперь–то это все не так сложно, так как появился Unicode. А если у вас есть Unicode, вы можете писать хоть китайские иероглифы в качестве идентификаторов.

Происходило последовательное, постепенное, но постоянное отчуждение исполнения программы от программиста, потому что между ними стоит транслятор, и не какой–нибудь, а оптимизирующий компилятор, и то, что вы написали, и то, что будет исполняться, совсем друг на друга не похоже. Именно языки программирования установили огромный барьер между сопоставлением текста программы и ходом ее исполнения: между тем, что написано, и тем, что делается. И повышение уровня языка программирования приводит к тому, что пишется одно, имеется в виду другое, а делается третье. А поскольку программисты чаще всего не принцессы, то семантические и реализационные «горошины» остаются незамеченными через «пятнадцать перин» трансляторов и операционных систем.

Появилось и некоторые другие трудностей, например, коллизия обозначений: поскольку количество слов, которые мы используем, не так велико, они начинают совпадать. Тогда были придуманы такие конструкции, как блок и модуль. А когда несколько человек делали части одной программы, оказывалось – то, что надо стыковать, называется по–разному, там тоже возникали соответствующие проблемы.

Вместе с процедурами появился побочный эффект, когда вы выполняете некоторое действие, а потом оказывается, что где–то что–то изменилось, хотя вы–то, вообще говоря, этого даже и не имели в виду. Поскольку появилась вычислимая адресация данных через указатели, возникла проблема висячих указателей, которая делает программу неработоспособной. Автоматически стали порождаться величины и занимать память. Ее надо было освобождать. Появилось понятие «мусора» и появились алгоритмы сборки «мусора». Кроме того, всегда была некоторая работа, когда либо на исходном уровне надо собрать куски и согласовать между собой, либо после некоторых преобразований надо состыковать рабочие подпрограммы.

Примером интерференции синтаксиса и семантики исполнения может служить «подстановка именем» в Алголе. Напомню, что надо строку, представляющую фактический параметр, подставить на то место текста тела процедуры, которое занимает формальный параметр, причем это делается во время исполнения. Но во время исполнения текста–то уже не существует. Поэтому возникает некая проблема, которую, конечно же, решили. Тем не менее, этот способ передачи параметров не прижился. Вместо него появилась подстановка по ссылке. В результате языковая парадигма дала нам в руки эффективные средства свертки действий в форме подпрограмм, процедур, модулей, появления стандартных библиотек и появления баз данных, в которых стан- дартным образом хранилась информация. Опыт глубокого изучения языков был применен выросшими в Отделе программирования людьми не только для создания языковых процессоров, но и в разработке и построении ре- альных программно–аппаратных комплексов, таких как АИСТ-0, рабочая станция «Кронос», архитектура кото- рой выросла вокруг идей языка Модула-2, семейство рабочих станций «МРАМОР» с несколькими созданными в ходе разработки его аппаратуры и ПО языками («ЯВА», «Фодула» и «Сидула»).

Большинство использованных источников можно найти на сайте ИСИ

1. http://pd.iis.nsk.su/
2. http://ershov.iis.nsk.su/russian/
3. http://db.iis.nsk.su/pottosin/40/win/booklet.html
4. http://start.iis.nsk.su/

Об авторе: Институт систем информатики им. А.П. Ершова СО РАН, Новосибирск
Материалы международной конференции SORUCOM 2011 (12–16 сентября 2011 года)
Статья помещена в музей 05.03.2012 с разрешения авторов