Разные мысли о метавычислениях, суперкомпиляции, специализации программ. И об их применениях. Желающие приглашаются в соавторы блога.

суббота, 6 июня 2009 г.

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

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

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

4 комментария:

  1. Замечательное объяснение о том, что для самоприменимости специализатор должен быть не слишком глуп, но и не шибко умен. Но, все-таки, самоприменимость - достаточно высокая и, пока-что, достаточно "научная" задача.

    Интересно, а есть ли более идейно простая задача-пример специализации конкретной программы, где частичный вычислитель оказывается на высоте, а суперкомпилятор - тот же самый SPSC или HOSC дает плохой результат?

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

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

    ОтветитьУдалить
  2. Может ли частичный вычислитель "обойти" суперкомпилятор по грубине преобразования программы (а не по "потребительским" качествам, вроде скорости работы и предсказуемости результатов)?

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

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

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

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

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

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

    Опять же, сравнивать надо не на "конкретной" программе, а на каких-то классах задач. Дело в том, что под конкретную программу всегда можно "подхакать" и частичный вычислитель, и суперкомпилятор, чтобы "получилось хорошо".

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

    Также следует учитывать, что частичные вычислители обычно работают не совсем автоматически: в исходную программу можно (или требуется?) вставлять аннотации, с помощью которых указывается, какие методы нужно "раскрывать" (подставлять in-line), где нужно "обобщать" аргументы (от S до D), и т.п. Поэтому и возникает вопрос, что мы собираемся "сравнивать" применительно к "конкретной программе"? С одной стороны - искусство человека по расставлению аннотаций в программе, а с другой - полностью автоматические методы?

    ОтветитьУдалить
  3. Кстати, я недавно собрался с силами, создал в Google Code проект, и выставил в нём частичный вычислитель Unmix (в том виде, в котором он был в 1993 году).

    Когда мне удалось его первый раз самоприменить и вычислить Unmix(Unmix, Unmix), у меня в компьютере было 640 Kb, а сейчас - 4 Gb. Неудивительно, что с тех пор мозги у меня несколько атрофировались.

    Вот когда у компьютера мозги были совсем куриные, иногда приходилось думать и самому... :-)

    ОтветитьУдалить
  4. А ссылку-то на проект вставить забыл:

    http://code.google.com/p/unmix/

    ОтветитьУдалить

Постоянные читатели