Что лучше: частичные вычисления или суперкомпиляция?

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

А ближе всего к суперкомпиляции находятся "частичные вычисления" (partial evaluation).

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

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

Пусть целые числа представлены в виде Z, S(Z), S(S(Z)), ... Рассмотрим программу

f(u) = g(u, Z);
g(Z, y) = y;
g(S(x), y) = g(x, S(y));

Функция f является "тождественной" в том смысле, что если на вход подать число u, то f (u) выдаст u.

Если подвергнуть g(u, Z) прогонке, то (на одной из ветвей дерева) получается бесконечная последовательность термов:

g(u, Z) --> g(u1, S(Z)) --> g(u2, S(S(Z))) -->

Если в суперкомпилятор вделан "свисток", основанный на гомеоморфном вложении, то суперкомпилятор замечает, что g(u, Z) гомеоморфно вложено в g(u1, S(Z)). Или, говоря по-простому, если в g(u1, S(Z)) подтереть конструктор S, то получится g(u1, Z), что (с точностью до имён переменных) совпадает с g(u, Z).

Поэтому суперкомпилятор делает обобщение и зацикливание. Можно убедиться в этом на примере суперкомпилятора SPSC: addAcc(a, Z).

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

Если частичный вычислитель - типа "offline", то он сначала размечает программу, чтобы узнать, какие подвыражения и параметры функций будут заведомо известны. Для этого символически выполняются операции над данными, а данные делятся на две категории S и D. S - известные данные, а D - неизвестные.

Основная идея "проста как лапоть":

S+S = S
S+D = D
D+S = D
D+D = D

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

В случае нашего примера есть две функции f и g. Для f возможны 2 разметки: f(S) и f(D). А для g - 4 разметки: g(S, S), g(S, D), g(D, S), g(D,D).

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

Когда процесс стабилизируется (достигается "неподвижная точка"), получается корректная разметка. D "испортили" уже всё, что смогли.

Применяем этот принцип к нашему примеру.

Для начала перепишем программу в такой форме, которая является более "естественной" с точки зрения большинства частичных вычислителей (и заодно перейдём к "нормальным" целым числам, которые для частичного вычислителя приятнее):

f(u) = g(u, z);

g(x, y) = if x == 0 then y else g(x-1, y+1);

Для примера будем считать, что нам неизвестно, что будет на входе программы. и задаём начальную разметку: f(D), g(S,S).

  D      D  S
f(u) = g(u, z);
  S  S       S           S        S    S
g(x, y) = if x == 0 then y else g(x-1, y+1);

Видно, что в одном месте g вызывается с первым параметром, имеющим пометку D. Меняем разметку параметров g с g(S,S) на g(D,S). Получается

  D      D  S
f(u) = g(u, z);
  D  S       D           S        D    S
g(x, y) = if x == 0 then y else g(x-1, y+1);

И на этом разметка стабилизируется! Везде S получается только из S. Поэтому, разметка "корректна".

Теперь надо принять решение, раскрывать ли вызовы функции g или генерировать её специализированные версии? Не раскрывать - это более осторожная тактика, применим её. Тогда частичный вычислитель действует так. У f разметка не содержит S: f(D). Поэтому, в остаточной программе генерируется только одна версия функции f. А разметка функции g содержит S: g(D,S). Это означает, что в процессе метавычислений второй аргумент g будет известен, и что для разных констант k будут сгенерированы специализированные версии g, такие, что g_k(x) = g(x, k). Принцип простой: если где-то получился вызов вида g(x,k), заменяем его на g_k(x) и генерируем определение функции g_k. При этом, с технической точки зрения, можно откладывать переименование вызовов g(x, k) в g_k(x) можно делать не сразу, а посредством отдельного прохода по программе. Т.е., просто считается, что значения S-параметров - это "часть имени функции".

А начинается процесс с генерации определения для входной функции f.

Получается так (после вычисления всех подвыражений, содержащих только S-переменные, значение которых известно):

g(u) = g(u, 0);
g(x, 0) = if x == 0 then 0 else g(x-1, 1);
g(x, 1) = if x == 0 then 1 else g(x-1, 2);
g(x, 2) = if x == 0 then 2 else g(x-1, 3);
g(x, 3) = if x == 0 then 3 else g(x-1, 4);
...

Или, после переименования функций,

g(u) = g_0(u, 0);
g_0(x) = if x == 0 then 0 else g_1(x-1);
g_1(x) = if x == 0 then 1 else g_2(x-1);
g_2(x) = if x == 0 then 2 else g_3(x-1);
g_3(x) = if x == 0 then 3 else g_4(x-1);
...

Генерируется бесконечная программа, которая для каждого k содержит определение функции вида

g_k(x) = if x == 0 then k else g_k+1(x-1);

Эта проблема характерна практически для всех частичных вычислителей (особенно - для самоприменимых). Но стоит не так остро для run-time specialization, поскольку можно не генерировать специализированные версии функций "про запас", а по мере надобности. А понадобиться могут не все варианты.

Из сказанного может сложиться ложное впечатление, что частичные вычислители, по сравнению с суперкомпиляторами, - это что-то ущербное. Зачем вообще заниматься частичными вычислениями, если суперкомпиляция "круче"? Но это - не совсем так.

Класс программ, с которыми успешно "справляются" частичные вычислители - некоторое подмножество, по сравнению с классом программ, с которыми можно делать что-то интересное с помощью суперкомпиляции.

Однако, если частичный вычислитель с какими-то программами всё же справляется, он делает это гораздо лучше, чем суперкомпилятор!

Разница здесь примерно такая же, как между лошадью и автомобилем. Если нужно ехать по шоссе, то автомобиль - быстрее лошади, и грузоподъёмность у него больше. Но если требуется проехать, например, по горной тропе...

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

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

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

Первое преимущество такого подхода очевидно: генерация остаточной программы идёт быстрее.

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

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

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

Есть и ещё одна интересная ситуация, когда проявляется преимущество (двухэтапных) частичных вычислений перед суперкомпиляцией: когда мы хотим применить специализатор программ к самому себе! Например, если у нас есть специализатор spec и интерпретатор int, то можно преобразовать интерпретатор в компилятор вычислив spec(spec,int). Это - "вторая проекция Футамуры" (которая была независимо открыта и Турчиным, хотя и немного позже).

Чем интересно выражение spec(spec,int)? Да тем, что специализатору предлагается "заглянуть в свою собственную душу" и разобраться в своём собственном поведении по отношению к самому себе. Здесь возникает некоторое противоречие: умному-то легко разобраться в душе дурака, но для дурака душа умного - потёмки. Вот и получается, что если специализатор - дурак, то самоприменять его бесполезно, поскольку сам в себе он разобраться не в состоянии. А если он слишком умён - то он всё равно не способен разобраться в себе, именно в силу своей сложности.

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

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

• С.А.Романенко. Генератор компиляторов, порожденный самоприменением специализатора, может иметь ясную и естественную структуру. - М.:ИПМ им.М.В.Келдыша АН СССР, 1987, препринт N 26. - 35 с. PDF, DJVU

• S.A.Romanenko. A Compiler Generator Produced by a Self-Applicable Specializer Can Have a Surprisingly Natural and Understandable Structure. In D.Bjorner, A.P.Ershov and N.D.Jones, editors, Partial Evaluation and Mixed Computation, pages 445-463, North-Holland, 1988. PDF, DJVU

• S. A. Romanenko. Arity Raiser and its Use in Program Specialization. In Proceedings of the Third European Symposium on Programming on ESOP '90 (Copenhagen, Denmark). N. Jones, Ed. Springer-Verlag New York, New York, NY, 341-360. PDF, DJVU

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