Вот, я писал-писал про суперкомпиляцию, и всё время её расхваливал. А теперь, для разнообразия, вдруг захотелось её поругать. А для этого нужно сравнить её с чем-то похожим, и сказать, что она хуже этого похожего.
А ближе всего к суперкомпиляции находятся "частичные вычисления" (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
