Какой язык лучше суперкомпилировать: "строгий" или "ленивый"?

Как объяснялось в заметках

• Что такое суперкомпиляция?

• Обобщение конфигураций при суперкомпиляции

• Ранняя история суперкомпиляции

• С чем едят "гомеоморфное вложение".

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

Логика получается такая. Выбираем язык, программы на котором собираемся преобразовывать. Выбираем какой-то вариант семантики этого языка. При этом понятно, что удобнее всего исходить из операционной семантики, ибо метавычисления - это ведь тоже "вычисления", и операционная семантика к ним находится ближе всего.

А из разных вариантов операционной семантики, ближе всего к суперкомпиляции находится семантика, основанная на последовательном преобразовании выражений ("упрощении" или "редукции" этих выражений).

При этом, в случае семантики, основанной на редукции, большинство языков разделяется на две группы:

• "Строгие" языки. При вычислении вызова функции, функция не начинает работать до тех пор, пока не вычислятся все её аргументы. Такой тип вычислений известен ещё как "вычисление изнутри наружу" или "передача параметров по значению" (call-by-value).

• "Ленивые" языки. При вычислении вызова функции её аргументы вычисляются ровно настолько, насколько они нужны для вычисления вызова самой функции. Такой тип вычислений известен ещё как "вычисление снаружи внутрь" или "передача параметров по имени" (call-by-name). Точнее, между "ленивостью" и "вызовом по имени" есть тонкое различие, но в данный момент оно для нас несущественно.

С каким языком удобнее иметь дело в суперкомпиляторе: "строгим" или "ленивым"?

Предположим, что входной язык суперкомпилятора - "строгий". Рассмотрим следующую программу:

а(A(x)) = B(a(x));
a(Stop) = Stop;
b(B(x)) = C(b(x));
b(Stop) = Stop;
f(u) = b(a(u));

Раз язык "строгий" язык, то прежде чем вызывать функцию, нужно полностью вычислить её аргументы. Допустим, на вход функции f подали A(A(Stop)). Тогда вычисление происходит так:

f(A(A(Stop))) --> b(a(A(A(Stop)))

Теперь видим, что внутри аргумента функции b находится вызов функции a. Значит, функцию b пока не вызываем, и вычисляем вызов функции a. Получается:

b(a(A(A(Stop))) --> b(B(a(A(Stop)))) --> b(B(B(a(Stop)))) --> b(B(B(Stop)))

Ну вот, теперь аргумент функции b принял вид B(B(Stop)). Вызовов функций в нём больше нет. Поэтому, начинает "работать" вызов функции b:

b(B(B(Stop))) --> C(b(B(Stop))) --> C(C(b(Stop))) --> C(C(Stop))

Теперь обрабатываемое выражение больше не содержит вызовов функций, и окончательным результатом вычислений считается C(C(Stop)).

Теперь, допустим, нам захотелось изучить процесс вычисления "в общем виде", когда аргумент неизвестен. Т.е., "вычислить" f(u), где значение u - неизвестно. Если мы хотим действовать "честно", т.е. так, чтобы метавычисление происходило "точно так же", как и обычное вычисление, мы должны и в суперкомпиляторе вычислять выражения "изнутри наружу".

Берём f(u) и начинаем делать прогонку.

f(u) --> b(a(u))

Теперь надо рассмотреть два случая: когда u=Stop и когда u=A(u1), где u1 - свежая переменная. Случаи, когда появляется Stop не очень интересные, поэтому сосредоточимся только на одной ветви в дереве конфигураций. Получается:

b(a(u)) --{u=A(u1)}--> b(B(a(u1))) --{u1=A(u2)}--> b(B(B(a(u2))))

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

Надо сказать, что "свисток", основанный на отношении гомеоморфного вложения в данном случае срабатывает вполне адекватно. Сравним выражения

b(a(u)) b(B(a(u1)))

Если присмотреться, то видно, что верхнее выражение вложено в нижнее: если из нижнего выражения вымарать конструктор B, то получается выражение b(a(u1)), которое совпадает с b(a(u)) с точностью до имён переменных.

При этом, b(B(a(u1))) не является частным случаем b(a(u)), поскольку на что переменную u ни заменяй, выражение b(B(a(u1))) получить невозможно. Проклятый конструктор B мешает!

Поэтому, суперкомпилятор сравнивает b(a(u)) и b(B(a(u1))), и находит их максимальную общую часть b(v), т.е. такое выражение, что b(a(u)) и b(B(a(u1))) являются его частными случаями. Заменяем v на a(u) - получаем первое выражение. Заменяем v на B(a(u1)) - получаем второе выражение.

После этого суперкомпилятор уничтожает всё поддерево, которое "выросло" из b(a(u)) и "обобщает" выражение b(a(u)), заменяя его на let v=a(u) in b(v). В результате получается такой граф конфигураций

которому соответствует остаточная программа, которая, по-сути, совпадает с исходной программой. Другими словами, суперкомпиляция ничего интересного не даёт.

Но тут возникает такая "хулиганская" идея: а зачем во время метавычислений строго следовать тому порядку, который установлен для обычных вычислений. Вот, допустим, у нас в процессе метавычислений получилось выражение b(B(a(u1))). Т.е. внутренняя функция a поработала-поработала и вытолкнула готовую часть своего результата наружу (в виде конструктора B). А почему-бы сразу не воспользоваться этой информацией? А то функция b торчит снаружи, ничего не делает и скучает. А можно ведь и не дожидаться, пока внутренний вызов функции вычислит результат до конца, а сразу начинать обрабатывать ту часть результата, которая "вылезла" наружу. Поэтому, попробуем воспользоваться правилом

b(B(x)) = C(b(x));

из определения функции b, и выполним такое преобразование:

b(B(a(u1))) --> С(b(a(u1)))

Теперь вынимаем из конструктора его аргумент b(a(u1)) и видим, что это выражение совпадает с выражением b(a(u1)), которое уже встречалось раньше. Значит, можно "зациклить", добавив к графу обратную ссылку. Получается такой граф конфигураций:

Это уже кое-что! Если из этого графа построить остаточную программу, получается

g(Stop) = Stop; g(A(x)) = C(g(x)); f(u) = g(u);

Видно, что эта программа существенно отличается от исходной! Исходная программа реализовывала двухпроходный алгоритм: во время первого прохода все A заменяются на B, а во время второго прохода все B заменяются на C. А после суперкомпиляции получается программа, которая делает только один проход по исходным данным, сразу же заменяя A на C. (Именно такой результат выдаёт суперкомпилятор SPSC: Compose.)

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

Однако же, сразу возникают и разные нехорошие сомнения и подозрения. Если во время метавычислений придерживаться той же логики, на которой основаны обычные вычисления, то естественно надеяться на то, что суперкомпилятор сгенерирует остаточную программу, эквивалентную исходной. (Хотя, вобще говоря, кто ж его знает? Вопрос тонкий, и, по-хорошему, для каждого конкретного суперкомпилятора необходимо какое-то доказательство того, что он "всё делает правильно".)

Но если обычные вычисления следуют одной логике, а метавычисления - совсем другой, то не получиться ли из-за этого какой-нибудь гадости? Например, рассмотрим программу:

omega(x) = omega(x); erase(x) = Stop; f(u) = erase(omega(Nil));

Если обычное вычисление работает по принципу "изнутри наружу", то программа зацикливается:

erase(omega(Nil)) --> erase(omega(Nil)) --> erase(omega(Nil)) --> ...

Если суперкомпилятор тоже работает по принципу "изнутри наружу", то он изготовит остаточную программу, эквивалентную исходной. А что будет, если суперкомпилятор начнёт выполнять метавычисления "снаружи внутрь"? Тогда во время вычисления получается такая последовательность выражений:

f(u) --> erase(omega(Nil)) --> Stop

Ведь функция erase не использует какую-либо информацию о своём аргументе: просто выкидывает его - и всё. А если аргумент не нужен, так зачем его и вычислять?

Логика, вроде, и хорошая, но она приводит к тому, что суперкомпилятор генерирует остаточную программу, которая, мягко говоря (и грубо выражаясь), не совсем эквивалентна исходной. Исходная программа для любых исходных данных зацикливалась, а в результате суперкомпиляции получилась программа, которая для любых исходных данных завершается и выдаёт Stop.

Тем не менее, многие суперкомпиляторы работают именно так. Например, суперкомпилятор SCP4 обрабатывает программы на языке Рефал (Refal). Рефал - это "строгий" язык, т.е. вызовы функций в нём выполняются "изнутри наружу". Но метавычисления (прогонку) SCP4 выполняет "снаружи внутрь". И остаточная программа не всегда эквивалентна исходной.

Однако, дела обстоят не так уж и плохо. Можно доказать, что если суперкомпилятор обрабатывает программу на "строгом" языке используя стратегию "снаружи внутрь", то остаточная программа всё же эквивалентна исходной на области определения исходной программы. Другими словами, если для некоторых входных данных X исходная программа не зацикливается и выдаёт некий результат R, то и остаточная программа для исходных данных X не зацикливается и выдаёт тот же результат R. Но если для некоторых входных данных X исходная программа зацикливается, то остаточная программа может сделать всё что угодно: либо тоже зациклиться, либо "упасть" (аварийно завершиться), либо выдать какой-нибудь бред.

Считать ли такое поведение суперкомпилятора "хорошим" или "плохим" - зависит от того, каким способом и для чего мы собираемся использовать суперкомпилятор. Упрощённо говоря, суперкомпиляция может использоваться для двух совершенно разных целей:

• Оптимизации программ (повышение скорости работы и уменьшение размера программ).

• Анализа формальных систем, представленных в виде программ (через выявление и доказательство свойств программ).

Если суперкомпилятор предполагается использовать для оптимизации программ, то

• Нет возможности выбирать или изменять входной язык суперкомпилятора. Есть некий язык и требуется программы на этом языке оптимизировать.

• Можно не сохранять поведение исходной программы для тех случаев, когда исходная программа "падает" или зацикливается (если предполагать, что перед запуском остаточной программы есть возможность проверить допустимость данных, подаваемых на вход).

Если суперкомпилятор предполагается использовать для анализа формальных систем, то ситуация меняется.

• Нет необходимости работать с входным языком, который навязан извне ("по историческим причинам" или потому, что "много людей на нём программируют").Вместо этого, можно использовать входной язык, который (1) обладает большой изобразительной силой и (2) для которого легко и приятно делать суперкомпилятор.

• Желательно, чтобы суперкомпилятор строго сохранял семантику программ.

С первым пунктом всё более или менее понятно. А пункт второй попробую пояснить с помощью конкретного примера.

Допустим, у нас возникло желание доказать эквивалентность двух выражений A и B. Как это сделать? Можно применить такой "ломовой" способ. Пусть sc(A) и sc(B) - результат суперкомпиляции выражений A и B соответственно. И вот, мы сравниваем sc(A) и sc(B) и видим, что они совпадают! (Ну, не совсем, а с точностью до "тривиальных различий" вроде переименования переменных.) Отсюда строим цепочку заключений:

A "эквивалентно" sc(A),
sc(A) "то же самое, что и" sc(B),
sc(B) "эквивалентно" B.

Стало быть, A эквивалентно B!

Подробнее об этом способе доказательства эквивалентности можно почитать в статье:

Ilya Klyuchnikov and Sergei Romanenko. Proving the Equivalence of Higher-Order Terms by Means of Supercompilation. Accepted for PSI'09: Seventh International Andrei Ershov Memorial Conference "PERSPECTIVES OF SYSTEM INFORMATICS", 15 - 19 June, 2009, Novosibirsk, Akademgorodok, Russia. PDF

Способ - ясный и простой. Но он основант на допущении, что при суперкомпиляции остаточная программа строго эквивалентна исходной. А если она "эквивалентна, но не совсем", вся вышеприведённая цепочка рассуждений рассыпается в пыль.

Как же можно преодолеть противоречие между логикой, по которой работают обычные вычисления, и логикой, по которой работает суперкомпилятор? Да очень просто: взять и устранить это различие! Пусть и обычные вычисления выполняются по принципу "снаружи внутрь". (Так и сделано в случае суперкомпиляторов SPSC и HOSC.) Зачем преодолевать противоречие, если можно сделать так, чтобы оно просто-напросто исчезло? Как говорили остряки конца 18 века: "Лучшее средство от перхоти - гильотина!".

Однако же, такой подход легко осуществим только в том случае, если мы хотим использовать суперкомпиялтор не для оптимизации, а для анализа формальных систем. Если же суперкомпилятор предназначен для оптимизации, приходится работать с тем входным языком, который дан "от Бога", и семантику которого "подкрутить" уже невозможно.

Например, суперкомпилятор SCP4 предназначен для обработки программ на Рефале, а в Рефале вызовы функций вычисляются изнутри наружу. Так уж устроен Рефал, а когда появился Рефал, до суперкомпиляции (и связанных с нею проблем) ещё никто не додумался.

Читать дальше...

С чем едят "гомеоморфное вложение"

При "прогонке" (символическом/обобщённом исполнении программы) в общем случае получается бесконечное дерево конфигураций. Задача суперкомпиляции - превратить это дерево в конечный граф.

В заметке Что такое суперкомпиляция? был рассмотрено такое простейшее "правило зацикливания". Допустим, в дереве встретился такой узел, который содержит конфигурацию X2, и при этому среди предков этого узла в дереве есть конфигурация X1, такая, что X1 и X2 совпадают (с точностью до переименования переменных). Понятно, что при таких условиях нет смысла строить поддерево для X2, поскольку оно будет выглядеть точно так же, как и поддерево, подвешенное к X1.

Поэтому выполнялась следующая операция. К графу добавлялась обратная стрелка из X2 в X1, а поддерево, подвешенное к X2 удалялось из графа. Точнее, оно не удалялось, а вообще не строилось!

Вот так и получался конечный граф. Правда, только для некоторых "особенно хороших" исходных программ.

В заметке Обобщение конфигураций при суперкомпиляции рассматривалось более сложное "правило зацикливания". Допустим, что X2 и X1 - действительно разные (X1 нельзя превратить в X2 простым переименованием переменных), но X2 является "частным случаем" X1. В том смысле, что применив к переменным в X1 некоторую подстановку, можно превратить X1 в X2. Тогда можно преобразовать X2 таким образом, чтобы она совпала с X1 (с точностью до переименования переменных). Это делается так: выдумываем новые, уникальные имена переменных v1, ..., vk и X2 приводится к виду

let v1 = E1,..., vk = Ek in E0

где E0 уже совпадает с X1 (с точностью до переименования переменных). На следующем шаге, let-выражение разбирается на части E0, E1,..., Ek, каждая из которых обрабатывается отдельно. При этом уже можно добавить к графу обратную стрелку из E0 в X1.

Переход от X2 к let-выражению, содержащему E0, называется "обобщением", поскольку X2 является "частным случаем" E0.

Благодаря обобщению конфигураций, класс программ, для которых получался конечных граф конфигураций, - расширился.

И способ борьбы с разрастанием дерева - понятен. Если встретилась конфигурация, которая является частным случаем уже рассмотренной конфигурации - сводим более специфическую конфигурацию к более общей. Возникает вопрос: достаточно ли этого правила, чтобы получить конечный граф конфигураций для любой исходной программы? Ответ на это - отрицательный... (Видимо, Судьба так распорядилась, чтобы авторам суперкомпиляторов жизнь мёдом не казалась. :-) )

Рассмотрим следующих (простой - но коварный) пример программы. Определим функцию умножения mult через уже нам известную функция сложения add.

add(Z, y) = y;
add(S(x), y) = S(add(x, y));
mult(Z, y) = Z;
mult(S(x), y) = add(mult(x, y), y);

При этом, натуральные числа 0, 1, 2, 3 представлены в виде Z, S(Z), S(S(Z)), S(S(S(Z))),... , а определения функций основаны на следующих свойствах натуральных чисел:

0+y = y
(x+1)+y = (x+y)+1
0*y = 0
(x+1)*y =x*y+y

Возьмём начальную конфигурацию mult(a, b) и попробуем построить из неё граф конфигураций. Получается такое дерево:

Видно, что если пойти по правой ветви этого дерева, то получается такая последовательность конфигураций:

mult(a, b)
add(mult(a1, b), b)
add(add(mult(a2, b), b), b)
add(add(add(mult(a3, b), b), b), b)

Получается так, что ни одна из конфигураций не является "частным случаем" какой-либо из предыдущих конфигураций! Так получается из-за того, что с каждым шагом снаружи добавляется новый вызов функции add.

Что делать? Здравый смысл подсказывает, что у всех этих конфигураций всё же есть общая часть: подвыражение вида mult(ak, b). В частности, можно свести add(mult(a1, b), b) к mult(a, b) с помощью "обобщения", использовав конструкцию let:

let v1 = mult(a1, b), v2 = b in add(v1, v2)

после чего уже можно добавить к графу обратную стрелку от mult(a1, b) к mult(a, b). В результате получается такой (незаконченный) граф конфигураций:

Cуперкомпилятор SPSC действительно разделывается с этой программой именно так: mult(a,b)! Правда, результат суперкомпиляции какой-то неинтересный: остаточная программа, по существу, совпадает с исходной... Ну так ведь и программа такова, что непонятно, что можно было бы сделать с ней интересного? Вот если бы начальная конфигурация была не mult(a, b), а какого-то более специального вида... Но об этом - позже.

А сейчас попытаемся сформулировать "правило зацикливания", которое было бы обобщением правила, описанного в заметке Обобщение конфигураций при суперкомпиляции. Там мы просто проверяли, является ли X2 "частным случаем" X1. А только что мы столкнулись с ситуацией, когда X2 не является частным случаем X1, но внутри X2 "зарыто" подвыражение Y, которое является-таки частным случаем выражения X1. Тогда можно, с помощью конструкции let "вытащить" Y из X2 "на поверхность":

let v = Y in E

где E{v:=Y} = X2. После этого можно разобрать let на части и добавить обратную стрелку от Y к X1.

Всегда ли это помогает? Как и следовало ожидать - не всегда. Рассмотрим опять фунцию сложения add и попробуем просуперкомпилировать конфигурацию начальную add(a, a). Когда мы суперкомпилировали add(a, b), всё получалось хорошо. Но в случае add(a, a) различие заключается в том, что переменная a повторяется 2 раза! Казалось бы, ну чего в этом плохого? А вот сейчас и увидим!

В результате прогонки получается такое дерево:

Видно, что порождается такая последовательность конфигураций:

add(a, a)
add(a1, S(a1))
add(a2, S(S(a2)))
add(a3, S(S(S(a3))))

Плохо дело! Конфигурации всё раздуваются и раздуваются! И ни одна из них не является частным случаем предыдущий. Попробуем, например, найти подстановку, такую, чтобы add(a, a) совпало c add(a1, S(a1)). По сути, надо решить уравнение

add(a, a) = add(a1, S(a1))

подобрав для a такую подстановку, чтобы левая часть совпала с правой. Такого значения для a подобрать невозможно. (В этом месте я написал длинное и нудное объяснение, почему невозможно, но потом его вымарал. Как известно, очевидные вещи гораздо труднее объяснять, чем неочевидные. :-))

Чтобы получился конечный граф, нужно сделать обобщение (с помощью всё той же конструкции let). В данном случае, беда произошла из-за того, что переменная a входит в add(a, a) два раза. Так сделаем из одной переменной две разные:

let v1 = a, v2 = a in add(v1, v2)

теперь конфигурация add(a, a) превратилась в add(v1, v2). А как суперкомпилируется такая конфигурация - мы уже разбирали в заметке Что такое суперкомпиляция?: получается конечное дерево конфигураций.

Сразу следует отметить одну тонкость. До сих пор мы делали обобщение таким способом: сравнивали "верхнюю" конфигурацию X1 с "нижней" конфигурацией X2 и "обобщали" X2 таким образом, чтобы она совпала с X1 (с точностью до имён переменных). Например, сравнивали add(a, b) и add(a1, S(b)) и обобщали add(a1, S(b)) до add(v1, v2). При этом, "прогресс" при построении графа конфигураций был непрерывным и "поступательным": к уже существующим узлам пристраивались дополнительные узлы и стрелки.

Но при сравнении add(a, a) и add(a1, S(a1)) мы столкнулись с принципиально другим случаем! add(a1, S(a1)) невозможно обобщить до add(a, a)! Конечно, можно преобразовать add(a1, S(a1)) следующим образом:

let v1 = a1, v2 = S(a1) in add(v1, v2)

При этом, получается, что add(a1, S(a1)) - это частный случай add(v1, v2). Но беда в том, что add(v1, v2) не является частным случаем add(a, a) (чего нам хотелось бы добиться). Совсем наоборот! add(a, a) - это частный случай add(v1, v2), поскольку существует такая подстановка {v1:=a, v2:= a}, что

add(v1, v2){v1:=a, v2:= a} = add(a, a)

Вот так-то! Абстрактно говоря, сначала встретилась конфигурация X1, а потом - конфигурация X2. Попробовали обобщить X2 до X1, но выяснилось, что это невозможно. Единственно, чего можно добиться, так это найти такую конфигурацию Y, которая является обобщением как по отношению к X1, так и по отношению к X2. В данном случае:

add(v1, v2){v1:=a, v2:= a} = add(a, a)
add(v1, v2){v1:=a1, v2:=S(b)} = add(a1, S(b))

Как должен действовать суперкомпилятор в подобных случаях? Наверное, возможны разные варианты... Но, наверное, самое простое решение проблемы таково.

Как мы помним, граф конфигураций - это дерево плюс обратные стрелки. X2 находится в поддереве, подвешенном под X1. Пусть Y - обобщение по отношению к X1 и X2. Тогда суперкомпилятор уничтожает всё поддерево, подвешенное к X1 (в том числе - и X2), а узел X1 заменяет на узел вида

let v1 = E1,..., vk = Ek in Y

После чего суперкомпиляция продолжается. Суперкомпилятор SPSC именно так и поступает: add(a, a)!

Однако, новизна ситуации в том, что вместо поступательного построения дерева получается некоторая последовательность попыток: строим поддерево, "разочаровываемся" в нём, уничтожаем его, обобщаем конфигурацию, из которой оно выросло, строим поддерево заново и т.д. Какая-то подозрительная ситуация! А вдруг, этот процесс будет продолжаться бесконечно? Как ни странно, оказывается, если всё делать аккуратно, процесс завершается. Кто сомневается, может проштудировать обстоятельную статью Сёренсена, в которой всё что надо научно доказываются:

Sørensen, M. B. 2000. Convergence of program transformers in the metric space of trees. Sci. Comput. Program. 37, 1-3 (May. 2000), 163-205. DOI= http://dx.doi.org/10.1016/S0167-6423(99)00026-X

Итак, если мы решили, что две конфигурации X1 и X2 - "похожи", то можно либо обобщить X2 до X1, либо, на худой конец, построить конфигурацию Y, являющуюся обобщением по отношению как к X1, так и к X2. Вопрос только в том, как формализовать само понятие "похожи"? Можно было бы рассматривать некоторое симметричное отношение "похожести" для конфигураций, но нам нужно не это. Суперкомпиляция - это имитация "обычных" вычислений. Тем самым, процесс суперкомпиляции имеет некоторое направление! Поэтому, при сравнении конфигураций нужно учитывать, какая из конфигураций появилсь раньше, а какая - позже.

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

Вот, допустим, под конфигурацией X1 в дереве висит конфигурация X2. Нам нужно решить, нужно ли обобщать X2 (или даже X2 вместе с X1), или же дела идут хорошо, и можно продолжать процесс, приделывая, с помощью прогонки, к X2 новое поддерево.

Здесь возникает конфликт интересов. С одной стороны, суперкомпиляция делается для того, чтобы проанализировать поведение программы "в общем виде". Каждая конфигурация описывает некоторое множество возможных состояний вычислительного процесса. Если конфигураций в дереве конфигураций много, это означает, что суперкомпилятор разбивает множество состояний на много частей, рассматривает много частных случаев. Стало быть, анализ процесса вычислений - утончённый и глубокий. А если конфигураций мало - это означает, что суперкомпилятор работает "топорно", и ничего интересного с помощью суперкомпиляции не получается (например, на выходе суперкомпилятора просто вываливается исходная программа).

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

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

Итак, разумным представляется такой подход: сравниваем X1 и X2. Если X2 на X1 "непохожа", то не обобщаем X2 и X1. А если X2 "похожа" на X1, то надо изучить ситуацию подробнее. Если X2 - "меньше по размерам", чем X1, то разумно X2 не обобщать, поскольку количество конфигураций, которые "меньше", чем X1 - конечно, и мы можем себе позволить их все перебрать не рискуя тем, что дерево конфигураций получится бесконечным. (Разумеется, это верно, если понятие "меньше" определено надлежащим образом.) А вот если X1 и X2 похожи, и при этом X2 - "больше", чем X1, то ситуация - опасная, нужно обощать! Введем для ситуации, когда X1 и X2 "похожи", но при этом X2 - "больше", чем X1, такое обозначение:

X1 <| X2

Как определить такое отношение, разные умные люди думали. Но первыми придумали Хигман (Higman) и Крускал (Kruskal). (Кстати, именно "КрУскал", а не "КрускАль", поскольку Kruskal - не француз. Был бы француз, его фамилия писалась бы как "Crouscal".)

Хигман и Крускал догадались, что определить отношение <| можно гениально простым способом! А именно, пусть считается, что X1 <| X2, если X2 можно превратить в X1 стерев в X2 некоторые его части. Сразу убивается два зайца:

• Если X2 можно превратить в X1, кое-что стирая в X2, то кто же усомнится, что X1 и X2 - "похожи"?

• Если X2 можно превратить в X1, кое-что стирая в X2, то это и означает, что X2 - "толще" или "больше", чем X1.

Хигман применил эту идею к линейным строкам, а Крускал - обобщил для деревьев (термов, составленных из n-арных конструкторов). А отношение <| научно назвали "отношением гомеоморфного вложения", так что, X1 <| X2 читается так: "X1 гомеоморфно вложено в X2". Ну да, можно считать, что X1 полностью присутствует в X2, но в "разбавленном" виде. Например, если у нас есть 50 граммов коньяка, и мы доливаем в него 150 граммов водки, можно считать, что в получившейся смеси 50 граммов коньяка "вложены" в 200 граммов получившейся смеси. При этом, исходные 50 граммов коняка можно получить обратно, отпив из стакана 150 граммов водки.

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

Leuschel, M. 2002. Homeomorphic embedding for online termination of symbolic methods. In the Essence of Computation: Complexity, Analysis, Transformation, T. Æ. Mogensen, D. A. Schmidt, and I. H. Sudborough, Eds. Springer-Verlag New York, New York, NY, 379-403.

Рассмотрим, например add(a, b) и add(a1, S(b)). Верно ли, что

add(a, b) <| add(a1, S(b))

? Верно! Подтираем в add(a1, S(b)) конструктор S и получаем add(a1, b). А это выражение совпадает с add(a, b) с точностью до имён переменных.

Рассмотрим mult(a, b) и add(mult(a1, b), b). Верно ли, что

mult(a, b) <| add(mult(a1, b), b)

? Верно! Подтираем в add(mult(a1, b), b) вызов функции add с её вторым аргументом, и получаем mult(a1, b), что совпадает с mult(a, b) с точностью до имён переменных.

Рассмотрим add(a, a) и add(a1, S(a1)). Верно ли, что

add(a, a) <| add(a1, S(a1))

? Верно! Стираем в add(a1, S(a1)) конструктор S и получаем add(a1, a1), что совпадает с add(a, a) с точностью до имён переменных.

Можно дать и формальное определение гомеоморфного вложения с помощью индуктивного определения в виде трёх правил:

1. x <| y для любых переменных x и y.

2. X <| f(E1,...,Ek), если f - имя конструктора или функции, и для некоторого i выполнено X <| Ei.

3. f(X1,...,Xk) <| f(Y1,...,Yk), если f - имя конструктора или функции, и для всех i выполнено Xi <| Yi.

Правило 2 называется правилом "ныряния" (левое выражение "ныряет" в один из аргументов правого), а привило 3 - правилом "сочетания" (аргументы конструктора/функции с двух сторон "сочетаются браком" друг с другом).

Интересно, что отношение гомеоморфного вложения нашло первое применение не в суперкомпиляции, а в системах переписывания термов:

Dershowitz, N. and Jouannaud, J. 1990. Rewrite systems. In Handbook of theoretical Computer Science (Vol. B): Formal Models and Semantics, J. van Leeuwen, Ed. MIT Press, Cambridge, MA, 243-320.

Некоторое время спустя, Мортен Сёренсен и Роберт Глюк задумчиво сидели в DIKU (что означает Факультет Информатики Копенгагенского Университета) и ломали голову над проблемой сравнения конфигураций. И тут к ним в комнату вошёл Нил Джоунс с какой-то статьёй в руках и спросил "А не это ли вы ищете?". А в статье было описано отношение гомеоморфного вложения. Оказалось, что именно это и искали... После чего, Сёренсен и Глюк и написали вот эту статью:

M. H. Sørensen and R. Glück. An algorithm of generalization in positive super-compilation. In J. W. Lloyd, editor, Proceedings of ILPS'95, the International Logic Programming Symposium, pages 465-479, Portland, USA, December 1995. MIT Press.

Интересно, что отношение <| хорошо работает также в случаях, когда у суперкомпилятора появляется возможность выполнить какие-то вычисления над известными частями данных во время суперкомпиляции. Например, вспомним функцию addAcc, которая выполняет сложение с помощью накапливающего параметра (аккумулятора):

addAcc(Z, y) = y;
addAcc(S(x), y) = addAcc(x, S(y));

Попробуем просуперкомпилировать выражение addAcc(S(S(a)), b). Как с ним разделывается суперкомпилятор SPSC? А вот так: addAcc(S(S(a)), b). На одной из ветвей дерева получается такая последовательность конфигураций:

1. addAcc(S(S(a)), b)
2. addAcc(S(a), S(b))
3. addAcc(a, S(S(b)))
4. addAcc(a1, S(S(S(b))))

Видно, что второй аргумент всё время угрожающе раздувается. Но суперкомпилятор не пугается! Второй аргумент раздувается, но зато первый аргумент уменьшается. Поэтому конфигурация 1 не вложена в конфигурации 2, 3 и 4, а конфигурация 2 - в конфигурации 3 и 4. А вот конфигурация 3 вложена в конфигурацию 4! И при этом 4 является частным случаем 3. Поэтому, 4 обобщается до 3 и в дереве конфигураций создаётся обратная стрелка на конфигурацию 3.

Возникает такой вопрос: а не может ли получиться так, что в процессе прогонки у нас всё время будут получаться всё время разные конфигурации, которые не буду вкладываться друг в друга. Оказывается, это не так! Для любой бесконечной последовательности конфигураций X1, X2, X3,... обязательно найдутся такие i и j, что i < j и

Xi <| Xj

Соответствующую теорему доказали Хигман и Крускал. Крускал - для случая, когда выражения составлены только из конструкторов. При этом принципиальным является то, что все конструкторы принадлежат конечному множеству. Однако, в суперкомпиляторе SPSC, например, выражения могут содержать ещё и вызовы функций, и переменные. Однако, теорема всё равно применима, поскольку вызовы функций, с синтаксической точки зрения - то же, что и конструкторы (а смысл термов для гомеоморфного вложения безразличен). При этом, в конфигурациях могут появляться только те конструкторы и имена функций, которые присутствуют в исходной программе. Некоторую проблему представляют переменные, ибо переменные-то могут появляться в конфигурациях в неограниченном количестве: суперкомпилятор их генерирует по мере надобности. Как быть? Простейшее решение, свалить все переменных в одну кучу и не различать их между собой. Т.е. считать, что

x <| y

для любых переменных x и y. Вот и получается, что с точки зрения <| переменная как бы одна-единственная, и её можно воспринимать как нуль-арный конструктор.

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

Turchin, V., The Algorithm of Generalization in the Supercompiler, in: Proceedings of the IFIP TC2 Workshop on Partial Evaluation and Mixed Computation, 1988, pp. 531--549. PDF

Но об этом надо будет написать отдельно...

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

Можно посмотреть, как всё это реализовано в специализаторе суперкомпиляторе SPSC, написанном на языке Scala (который, по сути, можно рассматривать как некий синтез Standard ML и Java). Для "учебных" целей был изготовлен "облегчённый" вариант SPSC, SPSC Light, исходные тексты которого выставлены там же. SPSC Light полностью работоспособен: в нём присутствуют все "принципиально важные" элементы суперкомпилятора, но опущены некоторые неинтересные части (вроде проверки разных контекстных ограничений на входные программы).

Читать дальше...

Ранняя история суперкомпиляции

"Откуда есть пошла" суперкомпиляция? Сейчас мы уже как-то привыкли к тому, что всё новое придумывают иностранцы, что они же это новое изготавливают и продают, а мы потом всё это покупаем за нефть. Однако, в случае с суперкомпиляцией дело обстоит на так: она была изобретена в России. Ну, точнее, в СССР. Причём придумал её не программист, а физик: Валентин Фёдорович Турчин:

• http://refal.net/author.html

• Валентин Турчин: "Проплыть между Сциллой и Харибдой"

Точнее, сначала он в 1966 году придумал "метаалгоритмический язык" Рефал, предназначенный для обработки алгоритмов, записанных на каких-то языках программирования.

• Турчин В.Ф.. Метаязык для формального описания алгоритмических языков, сб. "Цифровая вычислитель­ная техника и программирование", изд-во "Советское радио", М.-Л., 1966.

• Турчин В.Ф. Метаалгоритмический язык. — Кибернетика № 4, 1968. С. 116−124. DJVU , PDF

Со второй из статей можно ознакомиться (на выбор - в формате djvu или pdf), а первую из них, я когда-то держал в руках, а где добыть сейчас - не знаю...

Через некоторое время Турчин задумался над такой мыслью: если Рефал, в принципе, годится для обработки программ на любых алгоритмических языках, то, по определению, должен быть пригоден и для обработки программ на нём же самом. (Задним числом эта мысль кажется очевидной.) :-)

Правда, "обработка" программ тоже бывает разная... Например, раскраска ключевых слов в программа - это, можно считать, тоже "обработка" программы. Турчина же заинтересовал особый вид "обработки", вытекающий из идеи "метасистемного перехода". Что понимает Турчин под "метасистемным переходом", можно прочитать в его книге:

• Турчин В.Ф. Феномен науки: Кибернетический подход к эволюции. Изд. 2-е – М.: ЭТС. — 2000. — 368 с.

Тема эта - интересная, но очень обширная, поэтому мы сейчас в неё не будем углубляться, а рассмотрим только один частный случай, относящийся к исполнению программ.

Рассмотрим некоторый алгоритмический язык.  (Заметим в скобках, что понятие "алгоритмический язык" не совсем совпадает с понятием "язык программирования". Например, язык машин Тьюринга очевидным образом является "алгоритмическим языком", но "языком программирования" его обычно не называют. :-) ) Допустим, у нас есть программа на этом языке, которую нам хочется "выполнить", применив к некоторым "исходным данным". (Впрочем, в некоторых языках, например, в лямбда-исчислении, разницы между "данными" и "программой" не существует.)

Понятно, что "выполнить" программу можно только в том случае, если есть некий субъект, который её "понимает" и умеет выполнять. Этим субъектом может быть "железным" устройством (вроде процессора компьютера), программой или человеком. Для краткости, будем называть этого субъекта "интерпретатором".

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

А теперь представим, что над основным уровнем есть ещё "метауровень", на котором находится другой субъект, который с большим интересом наблюдает за тем, что происходит в основной системе. Вот это всё и называется "метасистемой". (Правда, затрудняюсь сейчас сказать, нужно ли считать, что основная система находится внутри метасистемы, являясь её частью, или же метасистема и система разделены? Это, видимо, вопрос определения...)

Ну, а переход от ситуации, когда есть только основная система, к ситуации, когда возникает метасистема, как и следует ожидать, называется "метасистемным переходом".

Имеем ли мы дело с метасистемными переходами в программировании? Не знаю, как там насчёт теоретиков, но программисты-практики сталкиваются с ними каждый день. Ну, например, что представляет из себя процесс отладки? Отладчик исполняет программу + данные по-шагам, а над ними тяжело дышит программист, который тщетно пытается понять, что происходит. Этот программист и находится на "метауровне" и, стало быть, является "метасистемой" (или её частью). Однако же, идея "автоматизации программирования" (жалко, что про этот изящный термин ныне почти забыли), подразумевает, что было бы хорошо, если бы всех программистов можно было повыгонять и заменить из на бездушные машины и/или программы.

Т.е., в идеале, поведение одной программы должна была бы изучать другая программа, а не человек. А над этой программой, естественно, можно было бы поставить другую программу (сидящую на мета-мета-уровне), и т.д. Но, как говорится, "гладко было на бумаге, да забыли про овраге". Светлая и завлекательная мечта об "автоматизации программирования" так мечтой и осталась. Хотя, кое-что сделать всё же удалось...

Итак, Турчин задумался о том, как можно было бы построить метасистему (в виде программы), наблюдающую за Рефал-программой, обрабатывающей какие-то данные. И вскорости он обнаружил, что на метауровне имеются кое-какие возможности изучать поведение программы "в общем виде", т.е. для целых классов входных данных, а не только для какого-то конкретного набора исходных данных (как в случае отладки). Говоря по-простому, обнаружилась возможность перейти от "арифметики" а "алгебре" (в школьном понимании этого слова). Например, то, что 3*(2+1) = 3*2+3*1 - это факт из арифметики. А то, что для любых a, b, и c верно a*(b+c) = a*b+a*c - уже факт из алгебры.

Так появилась система преобразований Рефал-программ, получившая название "прогонка" (driving). Слово "прогонка" появилось из-за того, что "конкретные" данные проходят через процесс вычислений "естественным" путём, а вот в случае "обобщённых" данных, изображающих целые классы "конкретных" данных, дело обстоит хуже: их приходится пропихивать через процесс вычислений буквально пинками, для которых, кстати, в прогонке используются прямо-таки садистские названия: "сужение" и "расщепление". Сразу на ум приходит сцена в духе "Преступления и наказания": стоит на метауровне субъект с топором и то обтёсывает "обобщенные данные", то расщепляет...

Прогонка была описана Турчиным в статьях

• В.Ф.Турчин, Эквивалентные преобразования рекурсивных функций, описанных на языке РЕФАЛ. В сб.: Труды симпозиума "Теория языков и методы построения систем программирования'', Киев-Алушта: 1972. Стр. 31-42. DJVU scan , PDF scan , DJVU LaTeX , PDF LaTeX
  

• Турчин В.Ф. Эквивалентные преобразования программ на РЕФАЛе. Автоматизированная система управления строительством. Труды ЦНИПИАСС, N 6. ЦНИПИАСС. Москва, 1974. Стр. 36-68. DJVU , PDF

Главный недостаток статьи 1972 года в том, что сборник трудов симпозиума был напечатан на серой бумаге бедными серыми буквами. Поэтому, в некоторых местах текст можно прочитать только с помощью сильной лупы. Понятно, что при попытке оцифровать эту статью возникли ну очень большие трудности. Пришлось проявить смекалку и изобретательность. Результат можете оценить сами. Выглядит довольно мерзко (хотя читать уже можно без лупы). Поэтому, пришлось перенабрать статью через LaTeX. Этот вариант выглядит чистенько, но зато в нём не ощущается "аромат эпохи" и возраст текста...

В статьях 1972 и 1974 года описана система преобразований Рефал-программ (прогонка), а также её применение для решения "обратных" задач. А именно, допустим, что на Рефале описана некая функция f, которая для любого входного x выдаёт True или False (если завершается). И вот, Турчин показывает, что с помощью прогонки можно решать "обратную задачу": подбирать для f такие значения x, что f(x) = True.

С точки зрения чистой теории в этом нет ничего удивительного, поскольку известно, что область определения любой рекурсивной функции является рекурсивно-перечислимой. Интерес был в том, что прогонка позволяла искать решения не тупым полным перебором, а вполне разумным способом. Например, в статьях рассматривается вопрос о решении уравнений вида a+x=b, где a и b - натуральные числа, представленные в двоичной системе счисления, а сложение определено как сложение "в столбик" в виде функции на Рефале. И получилось, что поиск x с помощью прогонки делается не перебором, а вычитанием "в столбик". Получалось, что компьютер, получив алгоритм сложения в виде программы автоматически находил разумный алгоритм вычитания.

Должен сказать, что описанное в статьях было тогда же реализовано в виде программ на Рефале (хотя в самих статьях это и не отражено). Турчин написал реализацию прогонки на Рефале, а "хождение на машину" (как это тогда называлось) и отладку поручил (или, скажем более точно, доверил :-) ) мне. К слову, программы тогда набивались на перфокартах , а "машиной" была могучая БЭСМ-6 (которая, правда, несколько уступала американской CDC-6600 ).

И, действительно, всё работало по теории: обратные задачи решались... А решения печатались на широченных лентах бумаги.

Однако же, если внимательно вчитаться в статью 1972 года, то у тех, кто знаком с Прологом, наверняка возникнет ощущение чего-то знакомого... Ну да, "обобщённое отождествление" - это "унификация". Стало быть, Турчин ничего нового не придумал: просто взял Пролог, перекрасил и выдал за своё. :-) Но это не совсем так. Или, точнее, совсем не так. Ведь, как утверждают сведущие люди:

Язык Пролог был изобретен французским математиком-программистом Колмэрауе в 1972 году как язык логического программирования для проведения экспериментов в области “искусственного интеллекта” на ЭВМ.

Т.е. в 1972 году Колмэрауе сидел и придумывал Пролог как раз в то самое время, когда Турчин придумывал прогонку. И, естественно, друг о друге они нечего не знали.

Также есть и различия на содержательном уровне:

• Пролог основан на "унификации", а унификация симметрична по отношению к своим двум аргументам. А прогонка основана на "обобщённом алгоритме отождествления", который асимметричен, и представляет собой сопоставление выражения, содержащего переменные с образцом. При этом "сужения" (подстановки) над образцом не выполняются, а переменные из образца "принимают значения".

• Турчин следовал своей методологии "метасистемного перехода". Сначала - основной уровень (т.е. Рефал и обычные вычисления), затем - метауровень (на котором наблюдается и изучается поведение основной системы). Поэтому, прогонка - это надстройка над "обыкновенным" функциональным языком программирования (Рефалом). Программист может сначала написать и отладить программу на традиционном языке и традиционными методами. А после этого - засунуть эту программу в прогонку.

• Колмэрауе пошёл другим путём. Он объявил, что нужно отказаться от традиционных (неправильных?) языков и методов программирования, и заменить их на новый (правильный?) язык Пролог. Наверное, он при этом надеялся, что программистское сообщество удастся уговорить свернуть с неправильной кривой дорожке на правильную. И многих уговорить удалось! Но не всех... И для этих "не всех" подход Турчина, наверное, выглядит не таким экстремистским, как у Колмэрауе.

Понятно, что прогонка - это только первый шаг на пути построения интересной метасистемы. И Турчин активно занялся дальнейшим продвижением на пути к суперкомпиляции. Но вскоре возникли небольшие затруднения, связанные не с самой научной работой, а, скажем так, с "объемлющей метасистемой" (в виде тогдашних начальников СССР). В результате, Турчина сначала выгнали с работы, а потом и вовсе предложили выбирать: либо поехать далеко-далеко на Восток, либо поехать далеко-далеко на Запад. Вот так Турчин и превратился из советского/российского учёного в американского...

Но не будем отвлекаться от темы, т.е. суперкомпиляции.

 

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

Нет работы - нет зарплаты. А если рассматривать научный аспект, то нет работы - нет возможности что-то опубликовать, поскольку опубликовать научную статью можно было только проделав некоторые обязательные действия по месту работы!

Поэтому, между 1974 и 1979 годами - публикаций нет. Точнее, в 1977 году Турчину удалось-таки (с помощью маленькой военной хитрости) опубликовать аж 4 (!) страницы, посвящённых суперкомпиляции. Вот они, эти страницы, однако:

• Базисный Рефал и его реализация на вычислительных машинах. М.: ЦНИПИАСС, 1977. - 258 с. Стр. 92-95 DJVU , PDF

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

• Подтверждение авторства С.А.Романенко... DJVU PDF

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

Что касается 4-х страниц, вставленных потихоньку в книгу в процессе её "редакторской правки", так они - просто шедевр научной прозы. В эти 4 страницы Турчину удалось втиснуть:

• Объяснение сущности суперкомпиляции.

• Объяснение того, что сейчас известно как "три проекции Футамуры".
  

"Проекции Футамуры" - вопрос тонкий и имеющий свою интересную историю. Его нужно рассматривать отдельно. Поэтому я изложу его сейчас чисто формально и мимоходом, не рассчитывая, что моё описание будет кому-нибудь понятно (кроме тех, кто уже заранее знает, о чём речь).

Допустим, что у нас есть программа f, исходные данные для которой разбиты на две части: "статическую" часть x и "динамическую" часть y. Обозначим через f(x,y) результат применения программы f к исходным данным (x,y). Тогда "специализатором" называется такая программа s, что

• s(p,x)(y) = p(x,y)

Допустим, что p - программа, результатом применения которой к исходным данным d является p(d). Тогда  "интерпретатором" называется такая программа i, что

• i(p,d) = p(d)

Теперь, используя свойства s и i, мы можем построить такую цепочку равенств:

• p(d) = i(p,d) = s(i,p)(d) = s(s,i)(p)(d) = s(s,s)(i)(p)(d)

из которой легко(!) видно, что

• s(i,p) - скомпилированная программа.

• s(s,i) - скомпилированный компилятор для языка, который интерпретирует i.

• s(s,s) - скомпилированный компилятор компиляторов (преобразующий интерпретаторы в компиляторы).

Впрочем, как потом выяснилось,  Ёсихико Футамура додумался до s(i,p) и s(s,i) ещё в 1971 году:

Yoshihiko Futamura: Partial Evaluation of Computation Process --- An approach to a Compiler-Compiler, Higher-Order and Symbolic Computation, Volume 12, December 1999, pp381-391. (Reproduction of the 1971 paper). PDF

Про s(s,s) он в этой статье не было ничего сказано, и это выглядело загадочно: первые 2 шага сделал - а почему не сделал третий? Не догадался? Но потом обнаружился некий отчёт, в котором s(s,s) было выписано. Так что, загадка только усугубилась. Если знал и понимал, почему не упомянул в статье про s(s,s)?

В общем, как бы то ни было, Футамура действительно самым первым додумался и до s(i,p), и до s(s,i), и до s(s,s). Поэтому, в соответствии с научными традициями и принципами справедливости, эти штуки и называются "проекциями Футамуры".

Однако же, когда Футамура опубликовал свою статью в 1971, на неё никто не обратил внимания. И только когда другие "дозрели" и начали додумываться до того же самого, эта статья была замечена и оценена.

Можно ли считать, что Футамура изобрёл и суперкомпиляцию? Вопрос тонкий. Для практической реализации проекций Футамуры полноценная суперкомпиляция не нужна: вполне достаточно "частичных вычислений". А с точки зрения суперкомпиляции, частичные вычисления - это некоторый экстремальный, вырожденный случай суперкомпиляции. Ну, а для особого, частного случая, можно использовать и особые методы, специально "заточенные" под этот общий случай. Вот и получается, что по решаемой задаче, частичные вычисления это частный случай суперкомпиляции, а по применяемым методам - различаются. Впрочем, это - отдельная интересная тема... А мы вернёмся к суперкомпиляции.

К сожалению, с 1979 года приходится читать уже на английском языке...

Оказавшись в Нью-Йоркском Городском университете, Турчин, первым делом, занялся публикацией того, что ему не удалось втиснуть в 4 страницы, пока он находился в СССР:

• Turchin, V. F. 1979. A supercompiler system based on the language REFAL. SIGPLAN Not. 14, 2 (Feb. 1979), 46-54. DOI= http://doi.acm.org/10.1145/954063.954069

• Turchin, V.F. The Language REFAL, the Theory of Compilation, and Metasystem Analysis. Courant Institute Report #20, New York, 1980. DJVU , PDF

• Turchin, V. F. 1980. The Use of Metasystem Transition in Theorem Proving and Program Optimization. In Proceedings of the 7th Colloquium on Automata, Languages and Programming (July 14 - 18, 1980). J. W. Bakker and J. v. Leeuwen, Eds. Lecture Notes In Computer Science, vol. 85. Springer-Verlag, London, 645-657.

• Turchin, V. F., Nirenberg, R. M., and Turchin, D. V. 1982. Experiments with a supercompiler. In Proceedings of the 1982 ACM Symposium on LISP and Functional Programming (Pittsburgh, Pennsylvania, United States, August 15 - 18, 1982). LFP '82. ACM, New York, NY, 47-55. DOI= http://doi.acm.org/10.1145/800068.802134

Все публикации существуют в оцифрованном виде. К сожалению, по правилам игры, установленным правообладателями, кое-что не находится в открытом доступе. Впрочем, некоторые проницательные люди утверждают, что запустив eMule/aMule из сделав поиск по ключевым словам "Turchin" и "supercompilation", кое-что можно найти...)

Ну вот, можно считать, что мы подошли к концу ранней истории суперкомпиляции. Хороший обзор этого периода можно найти у Сёренсена:

• Morten Heine Sørensen. Turchin's Supercompiler Revisited. Master's thesis, Department of Computer Science, University of Copenhagen, 1994. DIKU-rapport 94/17. PDF

Сёренсена заинтересовал следующий вопрос. У Турчина суперкомпиляция всегда рассматривалась применительно к языку Рефал. Верно ли, что суперкомпиляция применима только к Рефалу. Как и следовало ожидать, оказалось, что можно и без Рефала. Можно и объяснить без Рефала. Что Сёренсен и сделал. Так сказать, реализовал лозунг: "Без царя - а правительство рабочее!"

Читать дальше...

Обобщение конфигураций при суперкомпиляции

В заметке "Что такое суперкомпиляция?" разбирался пример, в котором всё получалось хорошо и гладко. Как легко догадаться, это свидетельствует вовсе не о том, что суперкомпиляция способна колоть как орехи любые проблемы, а о том, что пример был тщательно выбран.

Поэтому, чтобы компенсировать допущенную "нечестность" и "необъективность", давайте разберём пример, в котором суперкомпиляция сталкивается с некоторыми проблемами. Некоторые из этих проблем решаются с помощью "обобщения" конфигураций. Но "обобщение" тут же создаёт новые проблемы: когда его делать, а когда не делать. И какие конфигурации следует обобщать до каких?

Итак, рассмотрим такую забавную функцию:

addAcc(0, n) = n;
addAcc(m+1, n) = addAcc(m, n+1);

Эта функция выдаёт результат сложения двух её аргументов. Но, в отличие от функции add, рассмотренной в "Что такое суперкомпиляция?", она долго трудится, ничего не выдавая наружу: перекладывает единички из первого аргумента во второй, а потом сразу выдаёт готовый результат. А функция add выдавала результат своей работы частями.

Если перейти к представлению натуральных чисел конструкторы Z и S, определение функции addAcc принимает вид:

addAcc(Z, y) = y;
addAcc(S(x), y) = addAcc(x, S(y));

Теперь попробуем просуперкомпилировать addAcc(a, b). Получается такое дерево процесса:

Видно, что это дерево - бесконечно, поскольку всё время получаются конфигурации, не совпадающие с предыдущими:

addAcc(a, b)
addAcc(a1, S(b))
addAcc(a2, S(S(b)))
addAcc(a3, S(S(S(b))))
...

Если и дальше продолжать в таком же духе, то процесс построения дерева никогда не закончится!

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

Сейчас постараемся разобраться более точно, что именно означают слова "частный случай".

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

Можно считать, что каждое рабочее выражение изображает некоторое "конкретное" состояние вычислительного процесса. А каждая конфигурация, может рассматриваться как изображение некоторого множества рабочих выражений, или, другими словами, возможных состояний вычислительного процесса. А именно, берём конфигурацию, подставляем вместо её переменных всевозможные рабочие выражения, и получаем разные рабочие выражения из множества, изображаемого конфигурацией.

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

Можно подойти к делу и с другого конца. Допустим, у нас есть некая конфигурация X и некое рабочее выражение A. Можно ли проверить, принадлежит ли A к множеству, изображаемому X? Или, другими словами, можно ли переменные в X заменить на такие рабочие выражения, что X после этого совпадёт с A? Поиск таких значений переменных часто называют "сопоставлением A с образцом X".

Найти подходящие значения переменных (если таковые существуют) можно наложив A и X друг на друга. Например: сопоставим addAcc(S(Z) , S(Z)) с addAcc(a1, S(b)). Удалим те части двух выражений, которые попарно совпадают, и сразу становится видно, что S(Z) накладывается на a1, а Z на b. Или, выражаясь более формально,

A = X {a1:=S(Z), b := Z}

где X {a1:=S(Z), b := Z} - это результат применения к X подстановки {a1:=S(Z), b := Z}. Впрочем, для подстановок часто применяют и другие обозначения, например, такое: [S(Z)/a1, Z/b]. Как говорится, "на вкус и цвет товарищей нет"...

Теперь рассмотрим две конфигурации X1 и X2. Предположим, что конфигурацию X1 можно превратить в конфигурацию X2, заменив переменные, входящие в X1, на некоторые выражения (которые могут содержать переменные). Или, говоря формально,

X1 S = X2

где S - некоторая подстановка. В этом случае будем говорить, что X2 является "частным случаем" X1, и будем записывать это как X1 <= X2. Знак <= (меньше или равно) здесь используется из-за того, что X1 не может быть "толще", чем X2. Ведь переменные в X1 заменяются либо на переменные, либо на что-то более "массивное". Например,

addAcc(a1, S(b)) <= addAcc(a2, S(S(b)))

поскольку

addAcc(a1, S(b)) {a1 := a2, b := S(b)} <= addAcc(a2, S(S(b)))

Можно доказать такую теорему: если X1 <= X2, то множество рабочих выражений, изображаемых X2, полностью покрывается множеством рабочих выражений, изображаемых X1. В этом смысле, X2 и является "частным случаем" X1: X1 "накрывает" X2.

А теперь мы можем вернуться к графу конфигураций, который рассматривали в начале. Теперь мы видим, что при построении дерева у нас получилась последовательность конфигураций

addAcc(a, b) <= addAcc(a1, S(b)) <= addAcc(a2, S(S(b))) <= ...

в которой каждая последующая является частным случаем предыдущей.

Поэтому, возникает такая идея: если в процессе суперкомпиляции нам сначала попадается конфигурация X1, а затем - конфигурация X2, которая является частным случаем X1, то зачем изучать дальнейшее течение вычислительного процесса для X2? Всё, что включено в X2, входит и в X1, а все пути вычислений, выходящие из X1 мы и так изучим. Поэтому, не лучше ли как-то привести X2 к такому виду, чтобы она совпала с X1 (c точностью до имён переменных) и провести в графе "обратную" стрелку от X2 к X1?

Сведение X2 к "более общей" конфигурации X1 в процессе суперкомпиляции и называется "обобщением X2 до X1". А именно, заменяем X2 на конструкцию

let v1 = E1, ... , vk = Ek in E0

где E0 {v1 = E1, ... , vk = Ek} = X2, а E0 совпадает с X1 с точностью до переименования переменых. При этом, в качестве v1, ... , vk выбираются такие переменные, которые нигде больше не используются в дереве процесса (чтобы случайно не возникло путаницы с другими переменными).

Выглядит всё это устрашающе, но суть дела проста. Поскольку X1 <= X2, то просто накладываем X1 на X2 и смотрим, какие куски из X2 наложатся на переменные из X1. Если X1 содержит k переменных, то эти переменные наложатся на какие-то подвыражения E1, ..., Ek из X2. Придумаем для них свежие уникльные имена v1, ..., vk. После этого, извлекаем E1, ..., Ek из X2 и заменяем их на v1, ..., vk соответственно. Результат всех этих действий изображаем в виде let-выражения

let v1 = E1, ... , vk = Ek in E0

Например, сопоставляем addAcc(a, b) и addAcc(a1, S(b)) и видим, что

addAcc(a, b) { a := a1, b := S(b)} = addAcc(a1, S(b))

Отлично! Значит - E1 и E2 - это a1 и S(b). Придумываем для них имена v1 и v2. После чего переписываем addAcc(a1, S(b)) в виде

let v1 = a1, v2 = S(b) in addAcc(v1, v2)

теперь мы видим, что addAcc(v1, v2) совпадает с add(a, b) с точностью до переименования переменных. Но, чтобы можно было добавить к графу конфигураций обратную стрелку, нужно совершить ещё одно действие: развалить let-узел на части, чтобы выражение addAcc(v1, v2) оказалось в отдельном узле, который мы и соединим с узлом, в котором находится addAcc(a, b).

Растаскивание let-узла на части мы будет изображать следующим образом:

Это очень похоже на растаскивание на части узла, содержащего конструктор на верхнем уровне. И, как и в том случае, порядок, в котором расположены стрелки, существен.

Теперь мы можем, в качестве результата суперкомпиляции addAcc(a, b), построить следующий конечный граф конфигураций:

Можно посмотреть, как справляется с этим примером суперкомпилятор spsc: addAcc(a, b) и addAcc(a, Z).

Если из этого графа построить остаточную программу, то оказывается, что она совпадает с исходной программой. Таков, прямо скажем, жалкий результат всех наших всех наших мучений и титанических усилий... :-)

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

Читать дальше...

Что такое суперкомпиляция?

Под "суперкомпиляцией" обычно понимают метод анализа и преобразования программ, основанный на следующих действиях:

• Делается попытка "выполнить" программу не для конкретных входных данных, а, "символически" в "общем" виде. Т.е. для произвольных входных данных. Ну, или, для всех входных данных, удовлетворяющих каким-то ограничениям. Для этого строится "дерево конфигураций" (= "дерево процесса"). В узлах дерева находятся "конфигурации", которые описывают множества состояний вычислительного процесса. Понятно, что эти множества должны быть описаны на каком-то языке, и могут быть не вполне точными ("прихватывать" что-то лишнее). А стрелки, связывающие узлы дерева, соответствуют каким-то действиям и проверкам, происходящим при исполнении программы.
• Если исходная программа содержит циклы и/или рекурсию, то дерево конфигураций получается, вообще говоря, бесконечное. Это нехорошо. Что дальше делать с бесконечным деревом? Поэтому, в процессе суперкомпиляции, делается попытка свернуть бесконечное дерево в конечный "граф конфигураций". Для этого конфигурации сравниваются между собой. Если появляются две похожие конфигурации, делается попытка "свести" ту конфигурацию, что находится в дереве ниже, к той, что появилась выше. В результате, в дереве появляется "обратная" стрелка, и дерево превращается в граф с циклами.
• Построенный конечный граф конфигураций превращается в "остаточную" программу. Название "остаточная" связано с тем, что не все части исходной программы "выпадают в осадок". Некоторые из них могут просто исчезать в результате суперкомпиляции (например, если они недостижимы при заданных ограничениях на входные данные).

Под "суперкомпилятором" обычно понимают некую систему анализа и преобразования программ, основанную на суперкомпиляции. Другими словами, не бывает "суперкомпиляторов", не использующих суперкомпиляцию. :-) Но авторы суперкомпиляторов имеют полное право использовать в своих сооружениях не только суперкомпиляцию как таковую, но и любые дополнительные методы анализа, преобразования и оптимизации программ. (И обычно так и поступают.)

Сам термин "суперкомпиляция", может быть, и не очень хорош в силу своей двусмысленности. "Супер" может означать "крутой и могучий" ("супермен" = "сверхчеловек"), а может означать "тот, кто находится сверху и присматривает" ("супервизор" = "надсмотрщик"). Когда придумывался термин "суперкомпилятор" имелась в виду не "могучесть", а "присмотр"...

А теперь постараемся спуститься с сияющих абстрактных вершин к чему-то более конкретному и попытаемся разобраться, как работает суперкомпиляция, на конкретных примерах.

Допустим, что программы, с которыми мы будем иметь дело, написаны на простом функциональном языке (что это за язык, будет понятно из примеров, но, при желании, описание языка можно посмотреть здесь .)

Как известно, если в нашем распоряжении есть ноль и есть операция прибавления единицы, функцию сложения целых неотрицательных чисел можно определить следующим образом:

add(0, y) = y;

add(x+1, y) = add(x, y) + 1;

Будем считать, что неотрицательные целые числа представлены следующим образом. Ноль - как Z (где Z - это конструктор без аргументов), а число, следующее за числом n - как S(n) (где S - это унарный конструктор). Т.е. числа

0, 1, 2, 3,...

будут представлены как

Z, S(Z), S(S(Z)), S(S(S(Z)))...

Теперь программа сложения приобретает вид:

add(Z, y) = y;

add(S(x), y) = S(add(x, y));

В таком виде, программа уже ничего не знает о свойствах чисел: она просто механически перетасовывает S и Z.

Попробуем вычислить, например, 1+2. С точки зрения нашей программы, это означает, что нужно преобразовывать выражение

add(S(Z), S(S(Z)))

до тех пор, пока из него не исчезнут все вызовы функций. А сами преобразования должны выполняться путём применения двух правил, из которых состоит определение функции add. Такие преобразования часто называют "редукцией", а сами правила - "правилами редукции". В данном случае получаем такую последовательность преобразований:

add(S(Z), S(S(Z))) ----> S(add(Z, S(S(Z)))) ----> S(S(S(Z)))

При этом, какое правило когда применять, на каждом шаге определяется однозначно.

То, что было до сих пор - это "обычное" исполнение программы. А теперь мы переходим к "метавычислениям" (= "символическим вычислениям", "прогонке").

А что будет, если мы попробуем отследить вычисления "в общем виде"? Например, попытавшись "вычислить" add(S(S(Z)), b), где b - это некая переменная, значение которой неизвестно? А почему бы и нет? Получается:

add(S(S(Z)), b) ----> S(add(S(Z), b)) ----> S(S(add(Z, b))) ----> S(S(b))

Выяснилось, что для любого b, результатом вычисления add(S(S(Z)), b) является b к которому прибавлено 2. Блестящий результат! (И какой неожиданный. :-) )

Теперь наберёмся нахальства и попробуем вычислить "в общем виде" что-нибудь более интересное. Например, (a+b)+c. Или, в терминах нашего языка, изучим процесс вычисления выражения add(add(a, b), c).

Здесь мы впервые сталкиваемся c вложенными вызовами функций, и возникает вопрос: в каком порядке вычислять вызовы функций? Ответ зависит от того, с каким языком мы имеем дело: "строгим" или "ленивым". В "строгом языке", разрешается раскрывать вызов функции только если все её аргументы полностью вычислены. А в "ленивом" языке, можно раскрывать вызов функции, как только в аргументах появляется достаточно информации, чтобы стало ясно, какое из правил применимо (не дожидаясь, пока все аргументы полностью вычислятся). Это объяснение весьма приблизительно, но пока что нам хватит и такого.

Итак, будем считать, что язык, с которым мы имеем дело, - "ленивый". И рассмотрим, как будет вычисляться ((1+0)+0)

add(add(S(Z), Z)) ----> add(S(add(Z, Z)), Z) ----> S(add(add(Z, Z), Z)) ----> S(add(Z, Z)) ----> S(Z)

Как и следовало ожидать, в результате получилось 1. Но в самом процессе вычислений есть что-то не вполне удовлетворительное. А именно, при вычислении выражения вида add(add(a, b), c) получается так, что a обрабатывается 2 раза. Каждый раз, когда внутренний вызов add видит конструктор S, он снимает его с a и выталкивает наружу. Наружный add сразу же замечает это, и проталкивает S дальше, на верхний уровень. Получается, что каждый S обрабатывается два раза. А почему бы его не выталкивать на верхний уровень сразу?

Теперь попробуем "вычислить" выражение add(add(a, b), c) (содержащее переменные!).

Пытаемся раскрыть наружный add - не получается, поскольку мешает внутренний add. Делать нечего, нужно "подпихнуть" внутренний add, чтобы он выдал наружу какую-то информацию. Пробуем раскрыть внутренний add. Но и это не можем сделать, поскольку его первый аргумент - переменная a (значение которой нам неизвестно). Ну что же, тогда применим ломовой приём, отлично известный ещё из школьного курса математики: рассуждение методом "разбора случаев". Рассмотрим 3 взаимоисключающих случая:

• a имеет вид Z
• a имеет вид S(a1), где a1 - это переменная, изображающая нечто, о чём мы пока ничего не знаем.
• a - это не Z, и не может быть представлено в виде S( нечто ).

Третий случай нам не интересен, поскольку в программе для него не предусмотрено никакого правила. И попытка раскрыть вызов add с таким аргументом приводит к аварийному завершению программы.

Если a имеет вид Z, то add(add(a, b), c) превращается в add(add(Z, b), c), и мы можем раскрыть внутренний вызов add, получив add(b, c). Более кратко это можно записать так:

add(add(a, b), c) --{a=Z}--> add(add(Z, b), c) ----> add(b, c)

Если a имеет вид S(a1), мы тоже можем раскрыть внутренний вызов add:

add(add(a, b), c) --{a=S(a1)}--> add(add(S(a1), b), c) ----> add(S(add(a1, b)), c)

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

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

add(add(a, b), c) --{a=Z}--> add(b, c)

add(add(a, b), c) --{a=S(a1)}--> add(S(add(a1, b)), c)

Ещё более наглядно это можно изобразить в виде графа:

Теперь мы видим, что раскрытие внутреннего вызова add привело к тому, что вверх "всплыла" некоторая полезная информация в виде конструктора S. И теперь имеется достаточно информации, чтобы можно было выполнить раскрытие наружного вызова add. При этом, применимо только одно правило, т.е. разбор случаев не требуется.

add(S(add(a1, b)), c) ----> S(add(add(a1, b), c))

В виде графа это выглядит так:

Теперь мы видим, что конструктор S "всплыл" на самый верх, и ничего интересного с ним происходить уже не будет. А нам следует сосредоточиться на анализе его аргумента add(add(a1, b), c). Т.е. мы можем извлечь аргумент из конструктора, и работать дальше только с ним. Будем записывать это так:

S(add(add(a1, b), c)) ====> add(add(a1, b), c)

Или, в общем случае, если некий конструктор C имеет k аргументов, как

C(E1, E2, ..., Ek) ====> E1, E2, ..., Ek

А при изображении в виде графа будем поступать так: под узлом, содержащим C(E1, E2, ..., Ek) будем подвешивать узлы E1, E2, ..., Ek:

Здесь, наглядности, вместо обычных, мы используем широкие стрелки. (Хотя можно было бы использовать и обычные стрелки, поскольку смысл стрелок всегда однозначно определяется типом узла, из которого они исходят.)

Теперь граф конфигураций (= дерево процесса) принимает вид:

И тут возникает интересная ситуация! Присмотревшись к выражению add(add(a1, b), c) мы видим, что оно совпадает (с точностью до переименования переменных) с исходным выражением add(add(a, b), c) ! Это означает, что продолжать анализировать add(add(a1, b), c) просто глупо, поскольку ничего нового и интересного мы не получим. Всё, что можно было узнать, мы уже узнали при анализе выражения add(add(a, b), c). Поэтому, мы добавляем к графу "обратную" пунктирную стрелку от add(add(a1, b), c) к add(add(a, b), c) и оставляем add(add(a1, b), c) в покое.

Теперь нужно заняться выражением add(b, c). Здесь требуется разобрать два случая:

add(b, c) --{b=Z}--> c

add(b, c) --{b=S(b1)}--> S(add(b1, c))

Извлекаем add(b1, c) из S(add(b1, c))

S(add(b1, c)) ====> add(b1, c)

После чего видим, что add(b1, c) совпадает, с точностью до переименования переменных, с add(b, c). Получается граф

Этот граф изображает все возможные пути вычисления выражения add(add(a, b), c) для любых a, b и c.

Интересно, что случаи аварийного завершения вычисления тоже отражены в графе, хотя и неявно. Просто, если в аргументе вызова функции появляется некий конструктор, для которого в графе нет стрелки, считается, что вычисление завершается аварийно.

Ну, а если граф содержит полную информацию о возможных путях вычисления, это означает, что эту информацию можно превратить в программу. Эта программа и будет окончательным результатом работы суперкомпилятора!

Способ генерации программы из графа конфигураций (дерева процесса) довольно прямолинеен.

Каждый узел в графе можно превратить в функцию. Для этого, пометим каждый узел в графе неким идентификатором, который будет служить именем функции. Посмотрим, какие переменные появляются в конфигурации. Эти переменные и будут аргументами функции. Например, если для узла придумано имя g1 и в узле написано add(add(a, b), c), то этому узлу будет соответствовать функция g1(a, b, c).

Теперь надо посмотреть, какие стрелки выходят из узла. Допустим, выходят стрелки, соответствующие проверкам. Например:

add(add(a, b), c) --{a=Z}--> add(b, c)

add(add(a, b), c) --{a=S(a1)}--> add(S(add(a1, b)), c)

Тогда для каждой из стрелок генерируется правило, выполняющее проверку

g1(Z, b, c) = ...

g1(S(a1), b, c) = ...

Теперь нужно сгенерировать правые части правил. Для этого надо посмотреть, что находится в тех узлах, на которые направлены стрелки. В случае правила с левой частью g1(S(a1), b, c) стрелка идёт в узел, в котором находится выражение add(S(add(a1, b)), c). Допустим, этому узлу присвоено имя f1. Тогда ему соответствует функция f1(a1, b, c). Ну, так эту функцию и нужно вызвать в правой части правила:

g1(S(a1), b, c) = f1(a1, b, c)

Теперь займёмся узлом f1. Из него выходит только одна стрелка:

add(S(add(a1, b)), c) ----> S(add(add(a1, b), c))

и на этой стрелке нет проверки условий. Отлично! Значит, нужно просто вызвать функцию, соответствующую узлу S(add(add(a1, b), c)). Допустим, ему присвоено имя f2. Стало быть, ему соответствует функция f2(a1, b, c). Получается правило:

f1(a1, b, c) = f2(a1, b, c)

Понятно, что, на самом деле, функция f1 - лишняя, поскольку из g1 можно было бы вызвать f2 напрямую, минуя f1. Но это уже - оптимизация. А нам сейчас важно разобраться, с генерацией программы из графа, так сказать, на идейном уровне.

Теперь надо рассмотреть узел, в котором написано S(add(add(a1, b), c)). Ему, как упоминалось выше, соответствует функция f2(a1, b, c). А стрелка, выходящая из этого узла идёт в узел, в котором находится add(add(a1, b), c), и означает, что нужно вычислить add(add(a1, b), c), а на то, что получится, надеть конструктор S. Пусть узлу add(add(a1, b), c) присвоено имя f3 и соответствует функция f3(a1, b, c). Тогда всему вышесказанному соответствует правило:

f2(a1, b, c) = S(f3(a1, b, c))

И теперь мы можем, наконец, рассмотреть узел add(add(a1, b), c), которому, как сказано выше, соответствует функция f3(a1, b, c). Из этого узла идёт обратная стрелка в узел add(add(a, b), c), соответствующий функции g1(a, b, c). Очень хорошо! Это можно изобразить в виде правила:

f3(a1, b, c) = g1(a1, b, c)

Как узнать, каким способом следует сформировать аргументы в вызове функции g1? Очень просто! Нужно просто наложить друг на друга два выражения

add(add(a, b), c)

add(add(a1, b), c)

и убрать совпадающие части. Вот и получатся два списка переменных:

a, b, c

a1, b, c

из которого и видно, какие переменные каким соответствуют.

Продолжая в том же духе (и удаляя лишние промежуточные функции), получаем остаточную программу:

start(a, b, c) = g1(a, b, c);

g1(Z, a, b) = g2(a, b);

g1(S(a), b, c) = S(g1(a, b, c));

g2(S(a), b) = S(g2(a, b));

g2(Z, a) = a;

Ну, а теперь можно посмотреть, что делает с рассмотренной программой реальный суперкомпилятор spsc: spsc: AddAdd

Если у вас есть аккаунт в Гугле, можете сделать Sign In и тогда появляется возможность заводить свои собственные задания для spsc через веб-интерфейс.

Читать дальше...