Ершов и графы в программировании

[1]

В. Н. Касьянов

Современное состояние программирования нельзя представить себе без графов и графовых алгоритмов. Хорошо известно, что многие задачи повышения качества трансляции с точки зрения улучшения рабочих характеристик транслятора и повышения качества получаемых машинных программ формулируются и решаются как задачи на графах и графовых моделях. К ним относятся, в первую очередь, задачи, связанные с представлением программ в виде схем программ и синтаксических деревьев. Кроме того, необходимо указать на такие области применения граф-моделей, как эффективное использование ресурсов вычислительной системы (оптимизация использования регистров, уменьшение обменов между оперативной и внешней памятью и т. д.), организация больших массивов информации (деревья и, вообще, графы данных для повышения эффективности информационного поиска), увеличение степени параллелизма программы, повышение эффективности работы многопроцессорных и многомашинных систем (распределение загрузки процессоров, обмен сообщениями между процессами, синхронизация, конфигурация сетей связи между процессорами и т. д.). Решение этих и подобных задач привело к появлению множества граф-моделей, связанных как с программами и структурами данных, так и с вычислительными системами, в том числе параллельными (см., например, [1]).

Широкая применимость графов связана с тем, что они являются естественным средством объяснения сложных ситуаций на интуитивном уровне. Эти преимущества представления сложных структур и процессов графами становятся более ощутимыми при наличии хороших средств их визуализации. Поэтому неслучайно в последнее время в мире растет интерес к методам и системам рисования и визуальной обработки графов и графовых моделей [5]. Многие программные системы, особенно те, которые используют информационные модели, включают элементы визуальной обработки графовых объектов. Среди них — системы и окружения программирования, инструменты CASE-технологии, системы автоматизации проектирования и многие другие. Теория графов из академической дисциплины все более превращается в средство, владение которым становится решающим для успешного применения компьютеров во многих прикладных областях.

Среди первых работ, существенно использующих теоретико-графовые методы в решении задач программирования, можно отметить широко известные работы А. П. Ершова по организации вычисления арифметических выражений (1958 г.), граф-схемной модели для императивных программ в виде операторных алгоритмов (1958—1962 гг.), теории схем Янова с использованием их графового представления и концепции так называемой разметки (1963—1966 гг.) и граф-схемной теории экономии памяти (1961—1966, 1972 гг.).

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

Понятие схемы программ принадлежит А. А. Ляпунову и было введено им в 1953 г., исходя из общей концепции необходимости и возможности формализации процесса программирования. В опубликованных в 1958 и
1959 гг. статьях Ершова об операторных алгоритмах предлагалась модель программы, которая была основой такой известной модели, как стандартные схемы. Понятие операторного алгоритма исходило из предложенного Ляпуновым операторного метода программирования и ставило целью создание системы понятий, по возможности адекватной основным конструкциям, применяемым в программировании. Здесь же была установлена связь предложенного формализма с такими известными понятиями алгоритма, как частично-рекурсивные функции и нормальные алгоритмы Маркова. В последующей работе, опубликованной в 1962 г., Ершовым были рассмотрены возможности операторных алгоритмов для представления программ и логических схем программ, показана возможность построения инвариантов, общих как для некоторого машинного языка, так и для фрагмента проблемно-ориентированного языка и позволивших строго определить отношение эквивалентности в обоих языках. Эти работы Ершова были одним из основных источников современной теории схем программ.

Первой работой, посвященной общей теории преобразований программ, явилась ставшая классической статья Ю. И. Янова [3], в которой для моделей программ, введенных в литературу Ляпуновым и Яновым, был найден алгоритм распознавания эквивалентности двух схем и построена полная система преобразований. В 1968 г. Ершов публикует статью, в которой придает результатам Янова ту форму, которая и является для схем Янова принятой в современной теории схем программ. Здесь он применяет для схем Янова графовое представление, уже использованное им в работах по операторным алгорифмам. Оказалось, что графовое определение является более адекватным рассматриваемой проблеме. Это нашло свое отражение в упрощении аксиоматики преобразований (14 аксиом заменились на шесть), а также в эффективизации правила вывода, использующего понятие логической подчиненности, которое вместо сложного алгоритма преобразований средствами, лежащими вне аксиоматики, стало опираться на четыре аксиомы, задающие стационарную разметку дуг управляющего графа логическими функциями. Введенная Ершовым методика разметки активно использовалась во многих последующих работах по схемам Янова; она оказалась удобным средством для формализации преобразований, требующих для своего применения предварительного сбора некоторой информации о схеме в целом.

Принципиальный вклад в решение задачи о минимизации числа переменных в программе (задачи об экономии памяти) внес С. С. Лавров своей работой [2], опубликованной в 1961 г. В ней он ввел понятие операторной схемы, моделирующей программы со скалярными величинами, рассмотрел различные варианты распределения памяти как эквивалентные преобразования, состоящие в переобозначении величин, ввел понятия маршрута, канонического распределения памяти и графа несовместимости. Схемы Лаврова нашли свое применение для решения широкого класса прикладных задач теории программирования — главным образом, для алгоритмов оптимизации программ. Сведение задачи распределения памяти для схем Лаврова к известной задаче раскраски графа, опубликованное Ершовым в 1962 г., привлекло внимание программистов к классическим задачам теории графов. В результате появилась совместная работа А. П. Ершова и Г. И. Кожухина об оценках хроматического числа связных графов (1962 г.), ставшая основой разработанного ими эвристического алгоритма близкой к оптимальной раскраски графа.

В 1968 г. Ершов публикует статью об операторных схемах над общей и распределенной памятью. В ней он вводит понятие информационного графа и вариант схем Лаврова, так называемые схемы с распределенной памятью, в которых элементами памяти являются не переменные, а входы операторов и информационные связи между выходами и входами операторов задаются не с помощью переменных, составляющих общую память, а явно — в виде дуг информационного графа. Это позволило построить теорию, не зависящую от различных вариантов распределения памяти и получившую широкое применение в различных приложениях, таких как оптимизирующая трансляция и распараллеливание программ. Например, в последние годы в теории и практике оптимизирующей трансляции активно используется так называемая SSA-форма (Static Single-Assignment) представления программы, существенно упрощающая алгоритмы анализа и преобразования программ [4]. По существу, SSA-форма является таким представлением программы в виде схемы над распределенной памятью, в котором каждому входу любого оператора сопоставлен ровно один выход.

Создание общей теории распределения памяти было завершено работой по аксиоматике распределения памяти, опубликованной Ершовым в
1972 г. В ней методика разметки, впервые примененная Ершовым для схем Янова, была использована им для построения корректной и полной системы преобразований, позволяющей для любой схемы программы систематически строить любые допустимые распределения памяти для аргументов и результатов ее операторов. В дальнейшем данная методика в общей постановке глобальной оптимизации программ была описана Килделлом [9] и получила существенное развитие как отдельное направление в системном и теоретическом программировании по анализу потока данных в работах Кэма и Ульмана [7, 8], Грэхама и Вегмана [6] и многих других [10].

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

Первой книгой, посвященной применению графов в программировании, была монография А. П. Ершова «Введение в теоретическое программирование (беседы о методе)», изданная в 1977 г. В ней Ершовым рассмотрены две классические задачи теоретического программирования, решения которых и развитые на этих решениях методы привели к созданию теоретического программирования как самостоятельной математической дисциплины. Это  задача экономии памяти в операторных схемах Лаврова и задача построения полной системы преобразований в схемах Янова. В данной книге, написанной в виде беседы с читателем, Ершов внимательно анализирует этапы содержательного анализа и постановки этих задач и приводит объяснения хода мысли при их решении, делая читателя активным свидетелем творческого процесса и демонстрируя применение графовых методов к решению задач программирования в действии, начиная с элементарной постановки задачи и кончая полным решением проблемы во всей ее сложности.

В этой интересной и методически богатой книге проявился характер Ершова как ученого, всегда объединявшего в своей деятельности теорию, методологию и практику программирования. Под руководством Ершова и по его идейным проектам был создан широкий набор инструментальных и прикладных программных систем, в том числе целый ряд трансляторов и языковых процессоров. Это — программирующая программа для БЭСМ-6 (1955—1957 гг.), транслятор ППС для «Стрелы» (1957—1959 гг.), расширение Алгола-58, впоследствии модифицированное в язык Альфа (1958—1960 гг.), и его реализация для ЭВМ М-20 в виде Альфа-системы (1960—1964 гг.), система программирования для системных программистов, так называемая Эпсилон-система (1965—1968 гг.), экспериментальный макропроцессор, получивший название Сигма-система (1966—1969, 1985 гг.), две реализации Альфа-языка для БЭСМ-6, так называемые системы Алгибр (1966 гг.) и Альфа-6 (1970—1974 гг.), БЕТА-проект (1970—1985 гг.). Многие из них успешно использовали и развивали графовые методы.

Созданная под руководством Ершова система Альфа (1960—1964 гг.) была первой в мировой практике оптимизирующей системой программирования, практически доказавшей возможность создания трансляторов с приемлемой эффективностью рабочих программ для языков, более сложных, чем язык Фортран. Впервые в практику трансляции были введены промежуточные схемные представления транслируемых программ, ориентированные на оптимизацию, в частности, в Альфа-трансляторе существовал специальный просмотр, на котором по программе строилась схема Лаврова для анализа информационных связей в интересах глобальной экономии памяти. Работы по системе Альфа с ее многопроходной схемой трансляции и оптимизирующими преобразованиями промежуточных представлений программ внесли крупный вклад в методологию оптимизирующей трансляции. Сам Ершов называл Альфа-транслятор «грандиозным 24-проходным прокатным станом, протягивающим транслируемую программу и перековывающим ее в эффективный объектный код через игольное ушко всего 4К слов памяти».

В 1971 г. Ершов публикует статьи по универсальному программирующему процессору и многоязыковой системе программирования, ориентированной на описание языков и универсальную оптимизацию, которые положили начало работе по проекту БЕТА. Работы по проекту включали в себя исследования и эксперименты (они осуществлялись в  70-х гг.), а также собственно создание многоязыковой транслирующей системы (оно заняло первую половину 80-х гг.). Одной из центральных концепций типовой схемы трансляции, разработанной и реализованной в рамках проекта БЕТА, является концепция внутреннего (или промежуточного) языка, позволяющего с помощью универсальных алгоритмов оптимизации, выполняемых на уровне внутреннего языка, обеспечить получение качественной рабочей программы безотносительно к ее происхождению.

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

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

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

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

Органичное объединение теоретических исследований с созданием экспериментальных и прикладных программных систем, воплощающих и практически проверяющих разработанные идеи и подходы, — характерная черта таких работ. Эти работы охватывают широкий спектр областей системного программирования: трансляторы и транслирующие системы (Альфа, Алгибр, Альфа-6 и др.), языки и системы программирования (Эпсилон, Барс, Лисп, Сетл, БЕТА и др.), операционные системы и системное наполнение прикладных систем (АИСТ-0, СОФИСТ, ЭКСЕЛЬСИОР и др.), системы анализа и преобразования программ (ТМ, ТРАП, АС, СКАТ, СПЕКТР и др.), инструментальные окружения программирования (СОКРАТ). Особенностью реализованных систем, помимо производственных возможностей, является их принципиальная новизна. Ряд созданных систем закладывал новые направления системного программирования.

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

Список литературы

1. Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003. — 1104 с.
2. Лавров С. С. Об экономии памяти в замкнутых операторных схемах// Журн. вычисл. математики и мат. физики. — 1961. — Т. 1, № 4. — С. 687—701.
3. Янов Ю. И. О логических схемах алгоритмов// Проблемы кибернетики. — М.: Физматгиз, 1958. — Вып. 1. — С. 75—127.
4. Cytron R. K., Ferrante J., Rosen B. K., Wegman M. N., Zadeck F. K. Efficiently computing static single assignment form and the control dependence graph// ACM Trans. on Programming Languages and Systems.— 1991. — Vol. 13, N 4. — P. 451—490.
5. Di Battista G., Eades P., Tamassia R., Tollis I. G. Graph Drawing: Algorithms for Vizualization of Graphs. — Upper Saddle River, NJ: Prentice Hall, 1999. — 397 p.
6. Graham S., Wegman M. A fast and usually linear algorithm for global data flow analysis// J. ACM. — 1976. — Vol. 23. — P. 172—202.
7. Kam J. B., Ullman J. D. Global data flow analysis and iterative algorithms// J. ACM. — 1976. — Vol. 23. — P. 158—171.
8. Kam J. B., Ullman J. D. Monotone data flow analysis frameworks// Acta Informatica. — 1977. — Vol. 7. — P. 305—317.
9. Kildall G. A unified approach to global program optimization// Conference Record of the ACM Symposium on Principles of Programming Languages.— 1973. — P. 194—206.
10. Program Flow Analysis: Theory and Applications. — Englewood Cliffs, NJ: Prentice Hall, 1981. — 418 p.
11. Sethi R., Ullman J. D. The generation of optimal code for arithmetic expressions// J. ACM. — 1970. — Vol. 17,  N 4. — P. 715—728.

Примечание

[1] © В. Н. Касьянов, 2005.  Статья написана специально для настоящего сборника.

Из сборника «Андрей Петрович Ершов — ученый и человек». Новосибирск, 2006 г.
Перепечатываются с разрешения редакции.