Теоретическое и системное программирование
А.П.Ершов - один из тех ведущих мировых ученых, благодаря деятельности которых выделились и оформились такие научные направления современного программирования, как теоретическое и системное программирование. Его творческое наследие обширно, оно включает более 200 книг, статей, препринтов, не считая большого числа предисловий, редакционных статей, отзывов и т.п., а также газетных публикаций, стихов (и хороших стихов!) и пр. Объем этой статьи не позволяет дать достаточно подробный обзор всех работ Ершова, и здесь мы ограничимся изложением основных идей и ведущих публикаций.
А.П.Ершов был одним из первых советских программистов, внесшим определяющий вклад в отечественное программирование, поэтому естественно, что становление и развитие его научных интересов в большей степени соответствует становлению и развитию как советского, так и мирового программирования.
Как и большинство программистов 50-х гг., А.П.Ершов начинал с создания алгоритмов численных методов и стандартных программ. Первая его работа («Об одном методе обращения матриц» - доклад АН СССР, 1955) была посвящена разработанному им методу обращения матриц, относящемуся к классу методов пополнения. Хорошая алгоритмичность метода - компактность алгоритма, удобные рекуррентные соотношения - позволила этому методу быть основой для стандартных программ для ряда первых советских ЭВМ (для одной из них - БЭСМ - такая программа была разработана Ершовым). Середина 50-х гг. была временем становления теоретического и системного программирования. Системное программирование начиналось с направления, названного тогда автоматизаций программирования и связанного с разработкой языков программирования и методов их трансляции. Начальный толчок этому направлению дали работы Рутисхаузера и Ляпунова. Первые советские языки программирования были связаны с операторными схемами, предложенными А.А.Ляпуновым. Эти схемы задавали структуру программы в терминах операторов некоторых фиксированных классов с последующим заданием представления этих операторов. А.П.Ершов был руководителем и создателем одних из первых советских программирующих программ для ЭВМ БЭСМ и "Стрела" (программирующими программами тогда назывались интегральные разработки языка и системы программирования). На основе данных работ им была написана монография («О понятии вычислительного алгорифма» - тезис доклада совещания по вычислительной математике и применению средств вычислительной техники, 1958), первая в мировой литературе монография по автоматизации программирования, практически немедленно переведенная и изданная за рубежом, а также ряд работ о вычислительной технике и реализации алгоритмов на ней в 1956-1958 гг. В монографии и этих работах А.П.Ершовым был впервые предложен ряд понятий, подходов и методов, вошедших в классический багаж языков и систем программирования. Здесь и понятие цикла как фундаментальной конструкции языков программирования, и триадное внутреннее представление выражений, и метод функции расстановки для поиска совпадающих фрагментов (имен), и алгоритм оптимального распределения рабочих ячеек (регистров), и начальные идеи потокового анализа, и пр.
АЛЬФА- и БЕТА- языки
Первым большим проектом, с которого начиналась новосибирская школа, был трансляторный проект "Альфа". В отличие от предыдущих проектов программирующих программ проект Альфа был хорошо, практически по-современному специфицирован: было подготовлено формальное описание входного языка, была создана развернутая функциональная спецификация системы.
Отправной точкой проекта была публикация начальной версии нового языка программирования, суммировавшего накопившийся программистский опыт и создаваемого международной рабочей группой - так называемого Алгола 58. Группа, руководимая А.П.Ершовым, стала готовить на основе Алгола 58 новый проект языка - параллельно с работавшей международной группой. Во многом направления развития языка оказались совпадающими, но в новосибирском проекте появился ряд существенно новых механизмов, поэтому, в конце концов, язык был сформулирован как правильное расширение окончательной версии международного языка - Алгола 60. В Альфа-языке впервые были разработана средства, характерные для последующих за Алголом 60 языков. Было определено столь важное для вычислительных алгоритмов понятие многомерных значений, определены операции над ними, в том числе, их конструирование. Были введены свойственные современным языкам концепции, такие, как разнообразие видов циклов, задание начальных значений и т.п. В формальном определении языка впервые была сделана попытка выйти за пределы контекстно-свободных грамматик.
Сама работа над транслятором была в большой мере и исследовательской, и пионерской. Именно в этой работе начались складываться принципы современной оптимизирующей трансляции. Дело в том, что сам Алгол 60 был определенным вызовом для существовавших методов трансляции. Его существенно рекурсивная структура, мощность механизма процедур, возможная их вложенность и потенциальная рекурсивность, общность циклов и индексных выражений - все это требовало заметной модификации и развития техники трансляции, а самое главное - ставило вопрос о возможности получения эффективного кода. По последнему поводу высказывалось ряд сомнений, и Альфа-транслятор стал действительно первым конструктивным доказательством того, что для языков, сопоставимых по мощности с Алголом, можно построить транслятор, дающий сравнимый с ручным программированием код.
Достижению поставленной цели послужил богатый набор оптимизаций, реализованный в Альфа-трансляторе. Была предложена смешанная стратегия программирования (то, что позднее на Западе было названо "casing") таких конструкций, как процедуры, циклы, индексные выражения, когда на основании анализа контекста выбирался наиболее эффективный из допустимых способов генерации конструкций. Особенно изощренно программировались процедуры и подстановка параметров для них: выбор осуществлялся среди 11 способов. В результате алголовские процедуры при всей мощности механизма программировались оптимальным образом (что стимулировало программистов активно использовать это средство). Существовавшая ранее оптимизация экономии выражений была существенно развита - полностью учитывались свойства коммутативности и ассоциативности; если это преобразование не стало глобальным, то оно уже было квазилокальным. Впервые была реализована глобальная чистка циклов. Тщательной оптимизации подвергались операции над многомерными значениями - то, что не было в стандартном Алголе, но активно использовалось вычислителями. Впервые была реализована глобальная экономия памяти, опирающаяся на теоретические работы А.П.Ершова и С.С.Лаврова.
Альфа-транслятор стал первым в мире транслятором с Алгола с большими оптимизирующими возможностями. Похожий английский проект Хоукинса и Хакстебла, который разрабатывался в это время, так и не был до конца завершен из-за сложности задачи. Конечно, успеху способствовало не только механическое соединение многих оптимизаций, но и существенное развитие существовавшей методологии оптимизации программ. Была выдвинута идея внутреннего языка, к программе на котором и применяются оптимизации, которая, хотя и не совсем в чистом виде, была реализована. Был реализован практически глобальный анализ контекста, хотя и разрозненно для различных оптимизаций, учет которого существенно увеличил мощность оптимизаций - зародыш современного потокового анализа. Стремление практически всегда получать эффективный код привело к отказу от некоторых средств Алгола, важнейшим из которых была рекурсивность процедур.
Альфа-транслятор активно использовался в большом числе организаций страны. Хотя его интерфейсы с пользователем и простота эксплуатации желали много лучшего, но высокая эффективность получаемого кода обеспечила хороший интерес пользователей к этой системе. Поэтому когда на смену М-20 пришла существенно более высокопроизводительная машина БЭСМ-6, организации, связанные с большими задачами, стимулировали создание версии Альфа-транслятора для БЭСМ-6. Самым быстрым решением была простая переделка Альфа-транслятора, при которой та его часть, которая отвечала за генерацию кода, была заменена генератором кода для БЭСМ-6. Возник транслятор Алгибр (“Альфа гибридный”), который был одним из первых отечественных кросс-трансляторов. Такое решение имело ряд недостатков, но зато оно было реализовано быстро, и транслятор Алгибр стал первым транслятором для новой машины БЭСМ-6. Решение существенно облегчалось тем, что в Альфе-трансляторе уже существовал внутренний язык, хотя и не до конца единый для всех оптимизирующих преобразований.
Основным затруднением при Алгибр-трансляции была передача оттранслированного кода с М-20 на БЭСМ-6. В ВЦ СО АН СССР был даже разработан специальный канал передачи информации между инструментальной и объектной ЭВМ, однако это не могло быть серийным решением при массовой трансляции. Возникла необходимость "родного" транслятора для БЭСМ-6.
У разработчиков Альфа-транслятора возникала и внутренняя потребность модифицировать и улучшить как схему трансляции, так и пользовательские свойства транслятора, в первую очередь, его интерфейс с пользователем. Альфа-транслятор, несмотря на его достаточно широкую используемость, носил черты эксперимента и поиска - хотя идейные решения были найдены верно, но реализационные решения были характерны скорее для экспериментального, чем производственного транслятора (большое число просмотров программы - 24, некоторое дублирование анализа контекста, не всегда оправданное усложнение оптимизирующих преобразований). Не нужно забывать, что этот транслятор был первым оптимизирующим транслятором с Алгола. Дополнительный опыт - транслятор Алгибр, незавершенный проект Альфа-транслятора для ЭВМ Урал-14 (проект ТАУ) - давал основу для новых решений.