Смешанные вычисления в Новосибирске
[1]
М. А. Бульонков
В этих заметках я хочу рассказать о том, как развивались смешанные вычисления в новосибирском Вычислительном центре и позднее в ИСИ СО РАН. Вполне возможно, и даже почти наверное, я не смогу упомянуть обо всех событиях и людях, которые были причастны к работам в этой области, но ни в коем случае не с целью преуменьшить их значимость. Несмотря на определенный «мемуарный» характер того, что я скажу далее, я постараюсь определить основные понятия и процессы смешанных вычислений достаточно формально. Но все же основная моя задача сейчас — рассказать о людях и развитии проблематики.
Для начала под смешанными вычислениями можно понимать процесс совместного преобразования программ и данных в частично заданной обстановке их использования с целью повышения эффективности. Под такое определение можно без особой натяжки подвести практически все процессы системного программирования.
Андрей Петрович Ершов — проекции Футамуры
К идее смешанных вычислений А. П. Ершов пришел на основе работ в области разработки трансляторов, оптимизации и преобразования программ. В первых работах формальное определение имело следующий вид: смешанный вычислитель определялся как программный процессор, который получает на вход некоторое представление программы и часть входных данных и получает на выходе преобразованную программу, часть результата и данные, которые требуют дополнительной обработки. Формально, если данные программы p могут быть разбиты на две части x и y, то
mix(p, x) = (px, d, r),
где
p(x, y) = (px(d, y), r).
Часть данных x программы p, которые доступны смешанному вычислителю, назывались доступными данными, остальная часть данных — задержанными, программа px — остаточной программой или проекцией p на x, r — частичным результатом.
Хотя это явно и не следует из определения, предполагалось, что смешанный вычислитель обладает определенной полнотой в том смысле, что если задержанных данных нет, то остаточная программа будет пустой, а частичный результат — совпадать со всем результатом программы p. В этом смысле смешанное вычисление программы представлялось как расширение обычного вычисления: операции собственно программы по получению результата чередуются (то есть смешиваются) с действиями по формированию остаточной программы.
Далее Андрей Петрович заметил, что поведение транслятора очень напоминает поведение смешанного вычислителя: точно так же действия по анализу транслируемой программы чередуются с генерацией объектного кода. Кульминацией этих рассуждений стало открытие соотношений, которые связывают интерпретацию программы и ее трансляцию в объектный код. Для этого смешанный вычислитель трактовался в более узком смысле: без промежуточных данных и частичного результата:
mix(p, x) = px,
где
p(x, y) = px(y).
Назовем последнее равенство уравнением смешанного вычислителя. Пусть далее имеется интерпретатор int некоторого языка L, записанный в языке, программы которого может обрабатывать mix. Тогда
int(p, d) = p(d)
для любой программы p в языке L и ее данных d. Тогда, подставляя int в уравнение смешанного вычислителя, получаем
int(p, d) = intp(d),
откуда
intp(d) = p(d).
То есть программы intp и p эквивалентны, но заметим, что записаны они в разных языках: p — в языке L, а intp — в языке интерпретатора. Иными словами, смешанные вычисления в применении к интерпретатору реализуют трансляцию, а intp является объектным кодом p.
Продолжая такие игры с формулами, наиболее интересные соотношения можно получить, если предположить, что смешанный вычислитель обладает свойством самоприменимости. Для этого он, по крайней мере, должен быть записан в том же языке, для которого и предназначен. Оставляем читателю самому доказать, что
mixint(p) = intp
и
mixmix(int) = mixint.
Таким образом mixint преобразует программу в объектный код и, следовательно, реализует функцию транслятора, а mixmix преобразует семантику языка, заданную в виде интерпретатора, в транслятор и, следовательно, является генератором трансляторов.
Всякий, кто имел хоть приблизительное представление о трансляторах и интерпретаторах и узнавал эти соотношения, вначале не верил, что такое возможно, и искал какой-то подвох, а затем приходил в восхищение от красоты, ясности и глубины заложенного в них смысла[2]. Сейчас я могу представить себе, какое разочарование должен был испытать Андрей Петрович, когда отыскал статью японского ученого Ёсихико Футамуры, опубликовавшего эти соотношения еще в 1971 году. Примером профессиональной этики является тот факт, что Андрей Петрович назвал независимо открытые им соотношения проекциями Футамуры, несмотря на то, что последней проекции в той статье не было.
Именно благодаря энергии и настойчивости Андрея Петровича идея смешанных вычислений стала чрезвычайно популярной. Не последнюю роль здесь сыграло то, что был предложен простой пример, на котором можно было демонстрировать различные методы реализации смешанных вычислений — программа возведения x в степень n:
read x;
read n;
y := 1;
while n > 0 do
if even(n) then
n :=n/2;
x := x * x
fi;
n := n – 1;
y := y * x
od;
write y
Для этой программы характерно то, что все вычисления над n никак не зависят от вычислений над x и y. Таким образом, если n доступно, то все вычисления можно сделать на этапе смешанного вычисления.
Уже в первых работах были предложены основные методы реализации смешанных вычислений:
1. Частичные вычисления, при которых все инструкции исходной программы, которые зависят только от доступных данных, выполнялись непосредственно, а остальные — редуцировались и помещались в остаточную программу. Для программы возведения в степень при доступном n = 5 остаточная программа будет иметь вид
read x;
y := 1 * x
x := x * x
x := x * x
y := y * x;
write y
2. Генерирующее расширение разбивает процесс построения остаточной программы на два этапа. На первом этапе все действия программы классифицируются на доступные и задержанные, и порождается программа, которая получает на вход доступные данные исходной программы и генерирует остаточную. В нашем случае генерирующее расширение имеет следующий вид:
write “read x;”
read n;
write “y := 1;”
while n > 0 do
if even(n) then
n := n/2;
write “x := x * x”
fi;
n := n – 1;
write “y := y * x”
od;
write “write y”
Важность статической классификации действий программы на доступные и задержанные будет осознана значительно позже и названа анализом периода связывания (binding time analysis, BTA). Даже в этом простом примере есть «мелкие» неясности. Например, в операторе y := y * x на первой итерации цикла значение y доступно, а на всех последующих — задержано. Здесь проблема была решена тем, что без ясного обоснования была сделана задержанной инициализация
y := 1.
3. Трансформационный подход, при котором остаточная программа получается из исходной путем применения последовательности так называемых редуцирующих преобразований. К ним относятся, например, протяжка констант, редукция выражений, редукции условного с константным условием, раскрутка цикла, удаление неиспользуемых вычислений и т. п. Одно из промежуточных состояний в процессе преобразования для нашего примера может иметь следующий вид:
read x;
y := 1;
y := y * x;
x := x * x;
n := 2;
if 2 > 0 then
if even(2) then
n :=1;
x := x * x
fi;
n := 0;
y := y * x;
while n > 0 do
if even(n) then
n := n/2;
x := x * x
fi;
n := n – 1;
y := y * x
od;
fi;
write y
Даже при поверхностном рассмотрении этих примеров можно заметить достаточно большое количество проблем, основные из которых — проблема задержанного управления и связанная с ней проблема остановки смешанных вычислений. Пример возведения в степень обладает «приятным» свойством: не только все вычисления над доступными данными не зависят от задержанных, но и все условия и циклы определяются исключительно доступными данными. Рассмотрим пример, в котором это не так:
read x;
read y;
if y > 0 then
x := x * 2;
y := y / 2
else
x := x + 1;
y := y – 1
fi;
write y + x * x
Предполагая доступным x и задержанным y, мы не можем во время смешанного вычисления определить значение условия y > 0, а значит, не можем определить, как изменится состояние доступной памяти после выполнения всего условного оператора. Таким образом задерживаются и вычисления над x, и смешанный вычислитель заканчивает работу с остаточной программой, практически не отличимой от исходной.
С другой стороны, понятно, что если поставить целью вычислить максимум возможного при известном значении x (равном, скажем, 2), то «идеальная» остаточная программа должна бы иметь следующий вид:
read y;
if y > 0 then
y := y/2;
write y + 16
else
y := y – 1;
write y + 9
fi
Андрей Петрович искусно замаскировал эти проблемы в своих первых работах по смешанным вычислениям и признавал это, когда я допытывался у него ответов на конкретные вопросы. Потребовалось еще много лет исследований и экспериментов, чтобы от наброска идеи придти к практической реализации, но в тот момент основная задача состояла во внедрении идеи перспективности смешанных вычислений в сознание программистского сообщества, и с этой задачей Андрей Петрович справился просто блестяще. Десятки раз, на всевозможных конференциях и семинарах, в статьях и неформальных беседах он рассказывал о проекциях Футамуры и методах смешанных вычислений, формируя новое направление в системном программировании. Наглядным примером может служить развернутая, с большим количеством цветных иллюстраций статья в популярном, но не специализированном на программировании журнале «В мире науки» [Ерш84] [3].
Именно за работы в области смешанных вычислений Андрей Петрович был удостоен престижной премии им. А. Н. Крылова Академии наук СССР.
Владимир Иткин — алгебра смешанных вычислений
Другие исходные позиции и иной подход к исследованиям смешанных вычислений был свойствен работам Владимира Эммануиловича Иткина. Он производил впечатление замкнутого, отрешенного от окружающего мира ученого, для которого строгость доказательства и теоретическая сила результатов значительно важнее их практической применимости — типичный пример «теоретика» [4]. Несколько первых его работ были совместными с
А. П. Ершовым, но впоследствии их сотрудничество стало не таким тесным. Причиной этого стало высказывание Андрея Петровича о том, что в совместных работах ему принадлежит основная идея, а технические детали прорабатывает Иткин, и даже последовавшее уточнение — лишь основная идея и все технические детали, — по-видимому, не удовлетворило Владимира Эммануиловича. Несмотря на то, что работал он изолированно, результаты этих работ давали прочную теоретическую и понятийную базу для других исследователей.
Отправной точкой в исследованиях В. Э. Иткина была теория схем программ, с ориентацией в первую очередь на императивные операторные программы над общей памятью. Наиболее активно использовалось понятие экспликатора — оператора, обеспечивающего требуемое состояние части памяти программы. В простейшем случае экспликатор выражается присваиванием переменным заданных значений.
Роль экспликаторов была двоякой: с одной стороны, будучи обычными операторами, они являлись частью программы, так что в любой момент можно было прекратить процесс смешанного вычисления и объявить текущую программу остаточной, а с другой — они рассматривались как текущие точки вычислений. В. Э. Иткин исследовал и обосновал различные схемы организации смешанных вычислений — сквозную, пунктирную, поливариантную и др. Так, например, в поливариантной схеме допускалось размножение экспликаторов, что приводило к появлению нескольких экземпляров вычислений над одной программой. Рассмотрим приведенный выше пример более подробно. На первом шаге оператор ввода x редуцируется к экспликатору [x := 2]:
[x := 2]
read y;
if y > 0 then
…
fi;
write y + x * x
Далее, вычисление ввода read y оставляет его без изменений, а экспликатор перемещается к условному оператору. Поскольку условие ветвления задержано, то экспликатор дублируется на каждой из ветвей:
read y;
if y > 0 then
[x := 2]
x := x * 2;
y := y / 2
else
[x := 2]
x := x + 1;
y := y – 1
fi;
write y + x * x
На первой ветви оператор x := x * 2 может быть полностью вычислен — он исчезает из программы, а экспликатор заменяется на [x := 4], после чего обрабатывается задержанный оператор y := y/2 и экспликатор достигает конца ветви. Вторая ветвь обрабатывается аналогично и независимо, что приводит к следующему состоянию вычислений:
read y;
if y > 0 then
y := y / 2
[x := 4]
else
y := y – 1
[x := 3]
fi;
write y + x * x
Поскольку теперь вычисления разных ветвей привели к разным состояниям доступной памяти, мы вынуждены произвести их слияние, выделив одинаковую часть и поместив соответствующий экспликатор вслед за условным, «бросив» затем различающиеся части в виде пассивных операторов присваивания в конце каждой ветви:
read y;
if y > 0 then
y := y / 2;
x := 4
else
y := y – 1;
x := 3
fi;
[]
write y + x * x
В нашем случае, поскольку в экспликаторах разных ветвей нет ничего общего, то вычисления продолжаются с оператора вывода с пустым состоянием доступной памяти.
Существенную часть в описанном процессе составляет манипуляция с экспликаторами: «применение» операторов программы, слияние и т. п.
В. Э. Иткин сумел абстрагировать эти операции, введя набор аксиом, которым они должны удовлетворять. Это привело к так называемой алгебре смешанных вычислений [Itkin88].
Очевидно, что мы не смогли добиться «идеальной» остаточной программы, поскольку для этого потребовалось бы раскопировать оператор печати на каждой из ветвей. Если в данном случае это еще можно сделать достаточно безопасно, то в общем случае копирование приведет к неконтролируемому росту количества экспликаторов и зацикливанию процесса смешанных вычислений. В качестве примера можно рассмотреть тот же фрагмент, но с оператором цикла вместо условного:
while y > 0 do
…
od [5]
Как предугадать и избежать появления бесконечного количества экземпляров вычислений и копирования задержанных операторов? Примечательно, что именно такое поведение свойственно интерпретаторам, где выбор очередной инструкции исполняемой программы (которая должна быть доступной, если мы хотим добиться нетривиального результата) находится под задержанным условием интерпретации ветвления.
Последние работы В. Э. Иткина носили философский характер: частичные вычисления интересовали его как фундаментальный процесс перехода от общего к частному.
Владимир Иткин трагически погиб в 1991 году — замерз зимой по дороге в церковь.
Борис Островский — специализация синтаксических анализаторов
Для того чтобы сделать идею смешанных вычислений жизнеспособной, нужно было найти ей практическое применение. Именно такую тему Андрей Петрович предложил в качестве диссертационной своему аспиранту Борису Наумовичу Островскому. Задача состояла в автоматическом преобразовании универсального синтаксического анализатора для некоторого класса грамматик в анализатор, специализированный для конкретной грамматики [Остр87]. Формально, пусть имеется универсальный синтаксический анализатор synt, получающий на вход некоторое представление грамматики G и строку s и проверяющий, выводима ли строка s в этой грамматике. Если требуется многократно выполнить synt для одной и той же грамматики, но разных строк, то имеет смысл построить специализированный анализатор syntG для этой грамматики.
Очевидно, что специализация синтаксических анализаторов, хотя и имела самостоятельную ценность, была лишь первым шагом на пути к реализации проекций Футамуры, поскольку универсальный синтаксический анализатор вполне можно рассматривать как интерпретатор, грамматику — как интерпретируемую программу, а входную строку — как ее данные. С этой точки зрения, речь шла лишь о первой проекции и задача достижения самоприменимости смешанных вычислений не ставилась.
Смешанный вычислитель Островского был основан на трансформационном подходе. Более точно, смешанного вычислителя как такового не существовало, скорее речь шла о трансформационной машине со специально подобранным набором преобразований. Процесс применения преобразований был аналогичен процессу исполнения нормальных алгорифмов Маркова. Текст универсального анализатора размечался маркерами преобразований. Обычно в начале процесса имелся единственный маркер — начального преобразования, — помещенный перед первой инструкцией программы. Далее недетерминированно повторялась итерация выбора маркера и применения преобразования к помеченной ею конструкции. Результатом преобразования являлась модификация программы и расстановка новых маркеров. Так повторялось до тех пор, пока оставался хотя бы один маркер.
Набор преобразований разрабатывался для каждого универсального синтаксического анализатора заново. Фактически получался отдельный смешанный вычислитель для каждого класса грамматик. Но даже такой подход технологически оправдан. Во-первых, переиспользуется набор базовых преобразований, что гарантирует корректность специализированного анализатора. Во-вторых, для данного класса грамматик требуется только один смешанный вычислитель, который, будучи один раз «отлажен», может применяться к большому количеству грамматик. Наконец, в-третьих, система содержала развитые средства преобразования грамматик, такие, например, как выделение регулярной части, и средства постобработки, применяемые к остаточным программам.
Первая защита Б. Н. Островского закончилась полным провалом. Какую-то роль в этом играло очевидное нездоровое внимание ученого совета к национальному вопросу, но и выступление диссертанта было ниже всякой критики. И даже выступления Андрея Петровича и Геннадия Дмитриевича Чинина, однозначно поддерживавших диссертацию, не смогли исправить положение[6].
Следующий вариант диссертации Б. Н. Островский готовил, уже работая в Барнаульском политехническом институте. Периодически он приезжал в Новосибирск, показывал Андрею Петровичу очередную версию и уезжал обратно исправлять замечания. Поскольку не только компьютеры, но даже и просто средства машинописи ему были недоступны, то каждый раз он переписывал весь текст от руки, включая фрагменты программ. У меня до сих пор хранится один из промежуточных вариантов текста диссертации Бориса Островского — полторы сотни страниц, написанных без помарок каллиграфическим почерком. Вторая защита Б. Н. Островского прошла успешно.
Система смешанных вычислений, разработанная Б. Н. Островским, была в свое время одной из самых, если не самой, развитой. К сожалению, рутина преподавательской работы в провинциальном вузе не позволила ему продолжить активную работу в этой области.
Летняя школа по смешанным вычислениям в Лиманчике
Думаю, что всесоюзный уровень исследования в области смешанных вычислений получили после конференции по смешанным вычислениям, прошедшей на спортивной базе «Лиманчик» Ростовского госуниверситета. Конференция прошла несомненно успешно — она дала возможность встретиться и завязать рабочие контакты всем активным исследователям в этой области. Видимо, не имеет смысла, да и возможности, обсуждать сейчас программу конференции — отмечу только два запомнившихся «рабочих» момента.
Виктор Николаевич Касьянов представил доклад, посвященный редуцирующим преобразованиям программ. Достаточно широкий набор этих трансформаций составлял существенную часть системы СОКРАТ, нацеленную на обработку Фортран-программ. Интересным аспектом системы являлось то, что преобразования опирались не только на собственно текст программы, но и на пользовательские аннотации — утверждения о программе, которые считались априорно верными и потенциально могли как уменьшить сложность необходимого анализа, так и увеличить применимость преобразований. В дискуссии по докладу слово взял Николай Николаевич Непейвода и в свойственной ему манере безапелляционно заявил, что не найдется ни одной программы, к которой описанные преобразования можно было бы применить. Позже выяснилось, что он хотел сказать, что ни один программист сознательно не напишет ветвление с тождественно истинным условием, но к автоматически порожденным программам применение подобных преобразований может быть весьма перспективно.
В дискуссии Святослав Сергеевич Лавров высказал сомнение в практической полезности проекций Футамуры для реализации промышленных трансляторов, поскольку они покрывают самую простую и хорошо проработанную синтаксически управляемую часть процесса. Наиболее интересные задачи трансляторной проблематики, такие как экономия регистров или исключение общих подвыражений, не имеют истоков ни в смешанном вычислителе, ни в интерпретаторе и, значит, не могут появиться в автоматически получаемом трансляторе[7].
Михаил Бульонков — поливариантные смешанные вычисления
Идею того, как избежать зацикливания при специализации интерпретатора, подсказала еще одна аспирантка Андрея Петровича — Татьяна Шапошникова. Она пришла в очную аспирантуру Вычислительного центра СО АН, будучи преподавателем программирования в НЭТИ (ныне НГТУ). Когда она в первый раз рассказала мне о своей идее, я был совершенно не готов ее воспринять, поскольку ее предложение приводило к использованию неструктурированных переходов goto. Опасность этого я видел в том, что использовавшиеся схемы смешанных вычислений существенно опирались на структурированность программ, например, для «пронесения» доступной информации через задержанные условные операторы. Для того чтобы продемонстрировать идею Татьяны Шапошниковой, рассмотрим простейший интерпретатор конечных автоматов[8].
Пусть конечный автомат задается двумя таблицами: T — двумерная таблица перехода, сопоставляющая каждому состоянию и входному символу следующее состояние, Accept — определяющая, является ли состояние допускающим. Тогда интерпретатор может иметь следующий вид:
S := 1;
while not eof do
read c;
S := T[S, c]
od;
write Accept[S]
В этом интерпретаторе мы сталкиваемся с тем, что текущее состояние автомата S, которое хотелось бы сделать доступным, оказывается зависящим от задержанной переменной с в присваивании S := T[S, c]. Избежать этого можно, например, за счет знания о конечности входного алфавита. Если алфавит состоит только из двух символов {a, b}, то таблицу T можно разбить на две — Ta и Tb и добавить в интерпретатор разбор случаев для возможных значений переменной с:
S := 1;
while not eof do
read c;
if c = ‘a’ then
S := Ta[S]
else
S := Tb[S]
fi;
od;
write Accept[S]
Пусть далее для определенности Ta = {2, 3, 3}, Tb = {3, 1,3}, Accept = {True, False, False}.
Условия not eof и с = ’a’ задержаны, и если применить поливариантную схему вычислений Иткина в сочетании с внесением операторов в ветви задержанного условия, то на некотором шаге мы можем придти к следующему состоянию:
if not eof do
read c;
if c = ‘a’ then
if not eof do
read c;
if c = ‘a’ then
[S := 1]
while not eof do … od;
write Accept[S]
else
[S := 3]
while not eof do … od;
write Accept[S]
fi;
fi;
write False
else
if not eof do
read c;
if c = ‘a’ then
[S := 3]
while not eof do … od;
write Accept[S]
else
[S := 3]
while not eof do … od;
write Accept[S]
fi;
fi;
fi;
else
write True
fi;
Здесь можно заметить, что мы начинали вычисления с S = 1 и продолжение вычисления экспликатора [S := 1] будет приводить вновь и вновь к тем же результатам и порождать один и тот же остаточный код. В общем случае, если мы замечаем, что некоторый оператор обрабатывается повторно при одном и том же состоянии памяти, то можно завершить вычисление одной из копий вычислений вставкой оператора перехода на уже обработанную копию. Систематическое применение этого приема может привести, например, к следующей остаточной программе:
L1: if not eof do
read c;
if c = ‘a’ then
if not eof do
read c;
if c = ‘a’ then goto L1
else goto L3
fi;
else
write False
fi
else
L3: if not eof do
read c;
if c = ‘a’ then goto L3
else goto L3
fi
else
write False
fi
fi
else
write True
fi;
Мне удалось сформулировать достаточные условия остановки этого процесса: если, во-первых, анализ периода связывания классифицирует переменные и, следовательно, инструкции программы статически (то есть так, что если переменная объявлена доступной, то она является таковой в любой момент специализации) и, во-вторых, множество значений, принимаемое доступными переменными, конечно, то любая ветвь поливариантной специализации неизбежно приведет к уже пройденному состоянию. В определенном смысле вычисления оказываются «запертыми» в матрице, строки которой соответствуют инструкциям исходной программы, а столбцы — состояниям доступной памяти. В каждой клетке этой матрицы находится соответствующая редуцированная инструкция. В нашем случае множество значений доступной переменной S ограничено значениями 1, 2 и 3, а матрица остаточной программы имеет вид
S = 1 |
S = 2 |
S = 3 |
|
L: |
L1: if not eof then |
L2: if not eof then |
L3: if not eof then |
Андрей Петрович с энтузиазмом воспринял идею этого метода[9] — она явилась ключевой в реализации самоприменимого смешанного вычислителя Mix, пригодного для выполнения всех трех проекций Футамуры. Для уменьшения «технических» проблем реализация была проведена для специально разработанного императивного языка программирования ЯР, среди базовых операций которого была, например, операция редукции выражения. Методологическому осмыслению полученных результатов посвящена наша совместная статья [БулЕрш86][10].
К сожалению, оказалось, что мы опять немного опоздали. Независимо, буквально на несколько месяцев раньше, успешная реализация всех проекций Футамуры для небольшого подмножества функционального языка LISP была выполнена Петером Сестофтом (Peter Sestoft) под руководством профессора Нила Джоунса (Neil Jones) из Института информатики университета Копенгагена (DIKU). В свою очередь для них оказалось сюрпризом с запозданием обнаружить статью [Bul84], где описывалась техника, которую они независимо изобрели при реализации частичного вычислителя. Это стало началом длительного сотрудничества, взаимных визитов и здорового соперничества DIKU и новосибирской группы. Одним из наиболее значимых результатов этого сотрудничества стала прошедшая в Дании историческая конференция по частичным и смешанным вычислениям PEMC, об организации которой можно прочитать в статье А. В. Замулина в этой книге.
Гунтис Барздинь — частичные вычисления и фазы трансляции
Гунтис Барздинь приехал в Новосибирск поступать в аспирантуру к Андрею Петровичу. Точнее, поступал он в аспирантуру ВЦ Латвийского университета, но хотел, чтобы Андрей Петрович был у него научным руководителем. Первое же появление Гунтиса в Вычислительном центре вызвало переполох среди женского населения нашего кофе-клуба. По длинному коридору приближался высокий молодой человек в элегантном черном пальто, с непокрытой головой и в небрежно повязанном белом кашне. Вскоре выяснилось, что роль кашне исполняло гостиничное полотенце, которым Гунтис пытался спастись от сибирского мороза за 30 градусов[11].
Устроив свои аспирантские дела, Гунтис зашел ко мне и был весьма удивлен, узнав, что я лишь на несколько лет старше его. Еще до приезда в Новосибирск он читал мои статьи и представлял меня солидным ученым-теоретиком, что на поверку не соответствовало действительности. В ходе наших обсуждений смешанных вычислений и проекций Футамуры Гунтис заметил, что в них используется только специализация программ и игнорируется возможность получения промежуточных данных. Было бы интересно посмотреть, как могли бы выглядеть проекции в более общей трактовке смешанных вычислений.
Пусть для простоты формального изложения смешанные вычисления представляются двумя процессорами: специализатора spec, порождающего остаточную программу px, и частичного вычислителя peval, формирующего промежуточные данные xp:
spec(p, x) = px,
peval(p, x) = xp,
такие что
p(x, y) = px(xp, y)
для любого y. С одной стороны, если peval — тривиальный процессор и xp всегда пусто, то эти соотношения вырождаются в обычное уравнение смешанных вычислений. С другой стороны, если результат доступных вычислений находит свое выражение в промежуточных данных, то можно считать, что задача смешанных вычислений заключается в переводе данных x в некоторое, в каком-то смысле более эффективное, представление xp.
Подставляя в указанные соотношения интерпретатор int вместо p, программу p вместо x и данные d программы p вместо y, получим
spec(int, p) = intp,
peval(int, p) = pint,
такие что
int(p, d) = intp(pint, d).
Таким образом, кроме перевода программы в некоторое промежуточное представление смешанные вычисления порождают интерпретатор этого представления. В вырожденном случае порождение интерпретатора intp вообще не зависит от программы p, а только от результатов анализа периода связывания. Такой интерпретатор отличается от исходного тем, что там, где исходный интерпретатор производил вычисления над исходными данными, остаточный интерпретатор извлекает результаты этих вычислений из структуры данных px. Естественно, что в остаточном интерпретаторе должны появиться вспомогательные переменные, которые служат для указания текущего элемента данных px.
Разработанный нами алгоритм частичного вычисления был зеркальным отражением поливариантной специализации: там, где при специализации порождался очередной фрагмент остаточной программы, частичный вычислитель порождал элемент промежуточных данных, помещая в него значения доступных выражений этого фрагмента. Так, при частичном вычислении интерпретатора конечных автоматов порождались следующий остаточный интерпретатор и промежуточное представление автомата, заданного константами S0, S1, S2:
type pdata =
record
Final_S, Accept_S : Boolean;
Ta_S, Tb_S : ^ pdata
end;
const S0 : pdata := (true, true, addr(S1), addr(S2));
S1 : pdata := (false, false, addr(S0), addr(S2));
S2 : pdata := (false, false, addr(S2), addr(S2));
p : ^ pdata;
p := addr(S0);
while not p^.Final_S do
read c;
if c = ‘a’ then
p := p^.Ta_S
else
p := p^.Tb_S
fi;
od;
write p^.Accept_S
В случае, когда доступные переменные могут быть разбиты на достаточно независимые части, появляется возможность смешанной стратегии, при которой одна часть доступных вычислений выражается в остаточной программе, а другая — в промежуточных данных. Получаемая в этом случае остаточная программа может быть при необходимости в свою очередь специализирована относительно промежуточных данных. В приложении к проблематике трансляции такая стратегия соответствует последовательным фазам трансляции.
Основное преимущество частичного вычисления заключается в том, что при том же самом, что и при специализации, объеме доступных вычислений результат получается более компактным, поскольку исчезает необходимость «декорировать» вычисленные значения фрагментами исходной программы. С другой стороны, платой за это стали расходы на остаточную интерпретацию [БарзБул88].
Мы не довели идею поливариантного частичного вычисления даже до экспериментальной реализации. Позже ее выполнила Каролина Малкмьяр из Копенгагенского университета.
Диссертацию Гунтис Барздинь писал по тематике индуктивного синтеза программ и успешно защитил ее уже после кончины Андрея Петровича.
Дмитрий Кочетов — M2Mix
Научным руководителем Дмитрия Кочетова я стал по рекомендации Игоря Васильевича Поттосина. Из нашего первого с ним разговора выяснилось, что ему довольно безразлично, чем заниматься, про смешанные вычисления он немного слышал, и главное для него — защитить диссертацию. Как-то сразу определилась тема диссертации — смешанный вычислитель для реального языка программирования. Весьма поверхностные в тот момент знания Дмитрия о смешанных вычислениях не позволяли ему даже представить, за сколь сложную задачу он берется. В качестве входного языка была выбрана Модула-2, которая в то время была не просто весьма популярным в ИСИ СО РАН языком, но и являлась языком системы программирования, разрабатываемой под руководством И. В. Поттосина в рамках договора с большой промышленной организацией. Появлялась реальная перспектива действительно практического использования смешанного вычислителя[12].
Проект M2Mix потребовал разработки нетривиальных теоретических и реализационных решений. В частности, наличие в языке указателей и массивов потребовало нетривиального анализа периода связывания и, как его составной части, анализа синонимов.
Во избежание избыточного дублирования кода был разработан оригинальный анализ конфигураций, цель которого состояла в определении для каждой точки программы той части переменных, которые существенны для специализации. Несмотря на то, что деление переменных на доступные и задержанные не меняется во время специализации, тривиальное решение, состоящее в хранении и сравнении активных и достигнутых состояний памяти целиком, делает смешанный вычислитель практически неработоспособным как по времени, так и по памяти. Оптимизировать процесс работы смешанного вычислителя можно, удалив из рассмотрения:
- переменные, которые не изменяются в рассматриваемом фрагменте программы. Такой переменной является, например, внутреннее представление программы при специализации интерпретатора;
- переменные, которые можно вычислить на основе значений существенных переменных;
- переменные, которые не используются в рассматриваемом фрагменте, например, «мертвые» переменные[13].
Аналогично, бесперспективной будет попытка сравнивать состояния в каждой точке исходной программы. Для того чтобы избежать зацикливания процесса специализации, достаточно рассматривать, например, только множество точек, «разрезающее» все циклы программы, в которых изменяется доступная память. Это решение, очевидно, не оптимально: проблема заключается в том, что малое количество контрольных точек может привести к дублированию кода, а большое — к увеличению накладных расходов.
В отличие от большинства предыдущих проектов, М2Mix был реализован как генерирующий расширитель. Такое решение было принято не в последнюю очередь из соображений эффективности. Но основная причина носила более фундаментальный характер: такая реализация позволяла гораздо проще обеспечить то, что выполнение операций программы в процессе специализации в точности совпадало с их нормальным выполнением. Поскольку у нас не было другого способа выполнить программу, кроме как путем трансляции ее имеющимся компилятором, то точно так же должны были выполняться как специализация, так и остаточная программа.[14]
Одной из специфических черт языка Модула-2 является то, что в нем нет неструктурированной передачи управления goto. С точки зрения формального определения методов анализа это обстоятельство было несомненным плюсом, но для генерации остаточной программы оно вызвало определенные затруднения. Был использован «стандартный» прием, моделирующий метки и переходы глобальным циклом с вложенным переключателем. В случае интерпретатора конечных автоматов остаточная программа могла бы принять следующий вид:
PC := 1;
while PC <> 0 do
case PC
1 : if not eof then
read c;
if c = ‘a’ then
PC := 2
else
PC := 3
fi
else
write True
PC := 0
fi;
2 : if not eof then
read c;
if c = ‘a’ then
PC := 3
else
PC := 1
fi
else
write False
PC := 0
fi;
3 : if not eof then
read c;
if c = ‘a’ then
PC := 3
else
PC := 3
fi
else
write False
PC := 0
fi
end
od
Неожиданно оказалось, что несмотря на то, что в остаточной программе остался минимум интерпретации, она работала в несколько раз медленнее, чем исходная. Проблема опять оказалась в том, что эффективность программы определяется не только количеством выполняемых операций языка высокого уровня, но и тем, насколько эффективно сумел реализовать эти операции компилятор. И в этом смысле компактная и ясная программа исходного интерпретатора оказывается значительно лучше оптимизируема, нежели остаточная программа с нелокальными передачами управления и запутанными зависимостями по данным. На решение этой проблемы нацелена постоптимизация, улучшающая программу как с помощью традиционных оптимизирующих преобразований, так и специальными трансформациями, которые учитывают информацию, следующую из того, что программа была порождена смешанным вычислителем, например — знание о природе переменной PC. После постоптимизации результирующая программа могла бы принять вид
PC := 1;
while PC <> 0 do
case PC
1: if not eof then
read c;
if c = ‘a’ then
if not eof then
read c;
if c = ‘a’ then
PC:= 3;
else
write False;
PC := 0
fi;
else
PC:= 3;
fi
else
write True;
PC := 0
fi;
fi;
3: while not eof do read c od;
write False;
PC := 0
end
od
M2Mix был опробован на стандартном наборе примеров, таких как быстрое преобразование Фурье и универсальный лексический анализатор Lex. Последний устроен следующим образом. Описание лексики, заданное набором регулярных выражений, переводится в табличную форму, служащую инициализацией переменных-массивов в интерпретаторе, который не зависит от грамматики и всегда просто «дописывается» в конец анализатора. Переписав интерпретатор с языка С на язык Модула-2, мы получили идеального кандидата для специализации. Если не учитывать небольшого количества «технических» деталей, специализация лексического анализатора принципиально не отличается от рассмотренной выше специализации интерпретатора конечных автоматов. Специализированный анализатор работал в 1,5—2 раза быстрее исходного. Правда, для того чтобы добиться этого, нам пришлось немного преобразовать исходный универсальный анализатор, чтобы улучшить его «специализируемость»[15].
По результатам этих работ Дмитрий Викторович Кочетов в 1995 году успешно защитил диссертацию «Эффективная специализация алголоподобных программ». В настоящее время он работает в компании Microsoft.
Улучшение специализируемости
Таким образом, в определенном смысле сбылось предсказание Н. Н. Непейводы: у нас имелся один из самых мощных смешанных вычислителей, но не было программ, к которым его можно было бы успешно применить, поскольку, даже разрабатывая универсальную программу, программист не задумывается о том, насколько она пригодна для специализации.
Хорошим дополнением к дальнейшему усилению смешанного вычислителя могут стать средства, которые модифицируют исходную программу, улучшая ее специализируемость. Достаточно большой набор таких преобразований ввел Б. Н. Островский. В дипломной работе Юрия Александровича Баннова номенклатура таких преобразований была существенно расширена и, более того, были сформулированы условия целесообразности их применения. Как и Б. Н. Островский, Ю. А. Баннов занимался применением смешанных вычислений к синтаксическим анализаторам, но у последнего свобода маневра была ограничена фиксированным смешанным вычислителем M2Mix и фиксированным универсальным анализатором Yacc[16].
Также на повышение специализируемости программ была нацелена дипломная работа Владимира Яковлевича Курляндчика «Поливариантный анализ периода связывания для функций высших порядков». В отличие от традиционной для новосибирской школы ориентированности на императивные языки программирования здесь предметом исследования были функциональные программы. Общая идея состояла в следующем: при обычном моновариантном анализе периода связывания некоторая переменная объявляется задержанной, если она задерживается хотя бы при одном вычислении. Хотелось бы преобразовать исходную программу так, чтобы сделать больше вычислений доступными, раскопировав при необходимости как код программы, так и данные. Характерный пример — фрагмент интерпретатора, вычисляющего выражения [Bul93]:
function Eval(Expr, Mem)
case Expr.sort
sOp :
Eval := ApplyOp(Expr.Op,
Eval(Expr.left, Mem), Eval(Expr.right, Mem))
sVar:
Eval := Mem(Expr.name)
sConst:
Eval := Expr.value
end
Здесь Expr — доступное представление интерпретируемого выражения,
Mem — задержанная функция состояния памяти. При моновариантном анализе периода связывания мы вынуждены считать значение функции Eval всегда задержанным, поскольку в варианте sVar ей присваивается значение задержанной функции Mem. По этой причине фрагмент объектного кода, полученный из такого интерпретатора для выражения (x + 3) * (7 – 2), будет иметь вид
ApplyOp(‘*’,ApplyOp(‘+’,Mem(‘x’),3), ApplyOp(‘-’,7,2)).
Таким образом, получалась парадоксальная ситуация: смешанный вычислитель, по сути нацеленный на выполнение константных вычислений, не дает возможности выполнять константные вычисления в порождаемом компиляторе!
Разработанные методы позволяли автоматически преобразовать функцию Eval к следующему виду, произведя на ее основе функцию EvalBT для определения доступности выражения и функцию EvalStatic для вычисления полностью доступного выражения:
function Eval(Expr, Mem)
case Expr.sort
sOp :
if EvalBT(Expr) then
Eval := ApplyOp(Expr.Op,
Eval(Expr.left, Mem), Eval(Expr.right, Mem))
else
Eval := ApplyOp(Expr.Op,
EvalStatic(Expr.left, Mem), EvalStatic(Expr.right, Mem))
fi
sVar:
Eval := Mem(Expr.name)
sConst:
Eval := Expr.value
End
function EvalStatic(Expr)
case Expr.sort
sOp :
EvalStatic := ApplyOp(Expr.Op,
EvalStatic(Expr.left, Mem), EvalStatic(Expr.right, Mem))
sVar:
EvalStatic := void
sConst:
EvalStatic := Expr.value
end
function EvalBT(Expr)
case Expr.sort
sOp :
EvalBT := EvalBT(Expr.left, Mem) And EvalBT(Expr.right, Mem)
sVar:
EvalBT := False
sConst:
EvalBT := True
end
Несмотря на то, что этот фрагмент значительно больше исходного по размеру, а функция Eval выполняет проверки, не влияющие на получение результата, функции EvalBT и EvalStatic полностью доступны и редуцируются в процессе специализации, давая для того же примера лучший объектный код:
ApplyOp(‘*’,ApplyOp(‘+’,Mem(‘x’),3), 5)
Дипломные работы В. Я. Курляндчика и Ю. А. Баннова были признаны лучшими в соответствующие годы. В настоящее время они оба работают менеджерами в компаниях, занимающихся разработкой программного обеспечения.
Постскриптум
В 1992 году в ИСИ СО РАН была образована научно-исследовательская группа смешанных вычислений, преобразованная в 1997 году в лабораторию смешанных вычислений. Непростые девяностые годы сильно повлияли на характер исследований, поскольку приоритет сместился к обеспечению финансирования. Экспериментальные работы, которые не могли быть непосредственно использованы в промышленных проектах, приходилось замораживать либо выполнять силами студентов. Это происходило на фоне стремительного развития вычислительных средств: менялись парадигмы и технологии программирования, в десятки и сотни раз повышалась производительность машин, совершенствовалась техника компиляции. Многие вещи, которые ранее казались характерными для смешанных вычислений, такие как поливариантность, раскрутка циклов, открытая подстановка процедур, сейчас являются общепринятыми в развитых компиляторах.
Однако нельзя сказать, что накопленный опыт в области специализации программ бесполезен вовсе. В качестве примера приведу совместный проект, который выполняется в настоящее время лабораторией смешанных вычислений, петербургской компанией ТЕРКОМ и американской компанией Relativity Technologies [Терком01]. Целью этого проекта является разработка средств для реинжиниринга и модернизации устаревшего программного обеспечения. Одной из ключевых задач в этом процессе является так называемое извлечение бизнес-логики. Среди разных подходов к решению этой задачи примечателен один, называемый domain-based slicing, который по сути состоит в специализации программы для конкретных значений переменных. Хотя этот метод наверняка непригоден для получения объектного кода из интерпретатора, он дает удовлетворительное решение для многих нетривиальных задач, возникающих из реального применения системы и которые вряд ли могли возникнуть в чисто «академических» постановках. Например,
- допущение не одного, а множества или диапазона значений, которые могут поступать на вход программе;
- возможность негативной специализации — задания множества значений, которые не может принимать некоторая переменная;
- задание значений не на входе программы, а в некоторой точке, например, там, где значения считываются из базы данных;
- специализация программ, состоящих из многих компонент и др.
Список литературы
- [БулЕрш86] Бульонков М. А., Ершов А. П. Как специальные конструкции трансляции могут порождаться универсальными процессами смешанных вычислений// Вычислительные системы. — Новосибирск, 1986. — Вып. 116: Прикладная логика. — С. 47—66.
- [Bul84] Bulyonkov M. A. Polyvariant mixed computation for analyzer programs// Acta Informatica. — 1984. — Vоl. 21, Fasc. 5. — P. 473—484.
- [Ерш84] Ершов А. П. Смешанные вычисления// В мире науки. — 1984. — № 6. —
C. 28—42. - [Itkin88] Itkin V. E. An Algebra and Axiomatization System of Mixed Computation// Partial Evaluation and Mixed Computation. — North-Holland, 1988. — P. 209—224.
- [Остр87] Островский Б. Н. Управляемые смешанные вычисления и их применение к систематическому получению языково-ориентированных синтаксических анализаторов// Программирование. — 1987. — Т. 2. — C. 56—67.
- [Самоч82] Самочадин А. В. Опитимизатор структурированных микрокомпьютерных ассемблерных программ// Программирование микропроцессоров. — Валгус, Таллин, 1982. — C. 89—99.
- [Jones88] Jones N. D. Challenging Problems in Partial Evaluation and Mixed Computation// Partial Evaluation and Mixed Computation ( D. Bjørner, A. Ershov, and N. Jones, eds.). — Elsevier Science Publishers B.V. IFIP World Congress Proceedings. North-Holland. 1988. — P. 1—14.
- [БарзБул88] Барздинь Г. Я., Бульонков М. А. Смешанные вычисления как средство выделения фаз трансляции// Методы трансляции и конструирования программ. (Тез. докл. / Всесоюз. конф.; Ч. 1). — Новосибирск, 1988. — С. 21—23.
- [Ром95] Романовский А. В. Применение смешанных вычислений для решения задач трехмерной машинной графики. — Автореферат диссертации на соискание ученой степени кандидата технических наук. — Новосибирск, 1995.
- [Терком01] Автоматизированный реинжиниринг программ/ Под ред. А. Н. Терехова и А. А. Терехова. — Санкт-Петербург: СПбГУ, 2001.
- [Bul93] Bulyonkov M. A. Polyvariant binding time analysis// Proc. of the AC Sympos. on partial evaluation and Semantics Based Program Manipulation, Copenhagen, 1993. —
P. 59—65.
Примечание
[1] © М. А. Бульонков, 2005. Статья написана специально для настоящего сборника.
[2] Говорят, что Андрей Петрович несколько часов рассказывал сыну Василию о своем открытии по междугородному телефону. Аналогичную историю я слышал и про Валентина Федоровича Турчина, который также независимо открыл эти соотношения.
[3] Русская версия американского журнала «Scientific American».
[4] Меня всегда поражала технология написания статей, которую использовал В. Э. Иткин, — своего рода Cut&Paste в бумажном варианте. Если ему требовалось вставить или переставить пару предложений в рукописном тексте, то он делал это не редакторскими пометками или текстом на обратной стороне страницы, а буквально вырезал и вклеивал кусок страницы с написанным текстом в нужное место. В результате получалась длинная бумажная лента, которая живописно занимала весь его кабинет. По завершении работы над рукописью оставалось только разрезать ее на части стандартного размера и отнести машинистке для перепечатки.
[5] Гунтис Барздинь предложил другой интересный пример: та же программа возведения в степень, но при доступном x и задержанном n. Здесь также вычисления над x и y явно не зависят от n, но находятся под задержанными условиями. Хотя на первый взгляд кажется, что такая классификация входных данных вообще не имеет смысла, в некоторых случаях, например при x = 0, 1 и –1, можно представить себе очень эффективные «идеальные» остаточные программы.
[6]Один из членов совета, специалист в области методов оптимизации, услышав про оптимизацию грамматик, задал диссертанту вопрос о том, как здесь используется динамическое программирование. Б. Н. Островский совершенно смешался и не смог сказать ничего внятного. На вопрос пришлось отвечать Андрею Петровичу в своем выступлении, где он объяснил, что речь идет о методах, аналогичных оптимизации конечных автоматов, которые никакого отношения к динамическому программированию не имеют.
[7] В более теоретической постановке близкую проблему позже сформулировал и исследовал Н. Джоунс [Jones88]: «Может ли специализация программ давать более чем линейное ускорение?» Здесь предполагается, что измерение сложности учитывает только размер задержанной части данных, а размер доступных данных — константа.
[8] Подобно программе вычисления степени, пример интерпретатора конечных автоматов впоследствии многократно «перекочевывал» из одной статьи в другую.
[9] Именно Андрей Петрович перевел на английский язык (а честнее сказать — переписал на английском языке) мою статью [Bul84], которая потом многократно цитировалась.
[10] Эта статья публикуется и в данной книге.
[11] Вскоре Гунтис открыл для себя меховые шапки-ушанки и валенки.
[12] Тут надо заметить, что смешанные вычисления применялись в промышленных проектах. В качестве примера можно привести работы Самочадина [Самоч82] из Ленинградского политехнического института по специализации низкоуровневых управляющих программ, работы Романовского [Ром95] из Института автоматики СО РАН по оптимизации программ машинной графики. Но в нашем случае цель была более амбициозная — сделать практически применимым универсальный смешанный вычислитель, который, подобно транслятору, «знает» не о конкретной области использования, а только о входном языке.
[13] Указанные условия неточны и служат лишь для демонстрации идеи. Например, переменная может не использоваться в данном фрагменте, но ее следует считать существенной, поскольку необходимо транзитивно передавать ее значение в другой фрагмент, где она используется.
[14] Однажды мы долго пытались выяснить разницу в результатах некоторой вычислительной программы и ее специализированной версии. Оказалось, проблема заключалась в том, что опции компилятора, которые были установлены при трансляции генерирующего расширения, отличались от тех опций, с которыми транслировалась остаточная программа.
[15] Нас это не сильно смущало — по образному выражению А. П. Ершова, специализируемую программу можно сравнить с племенным жеребцом, поскольку нас интересуют рабочие качества не его самого, а его потомства.
[16] В ходе выполнения работы был выполнен любопытный эксперимент, который еще раз наглядно убедил нас в работоспособности концепции. Надо было получить два специализированных анализатора: один получить автоматически из универсального, а другой — написать с нуля вручную. Не говоря уже о том, что в написанном вручную так и не удалось искоренить все ошибки, он был просто менее эффективен, чем полученный автоматически.
Из сборника «Андрей Петрович Ершов — ученый и человек». Новосибирск, 2006 г.
Перепечатываются с разрешения редакции.
