Суперкомпиляция

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

Например, пусть исходный алгоритм — вычисление квадрата числа: square(x) => x * x. Для x = 0 можно получить более короткий и более быстрый вариант алгоритма, который просто возвращает ноль: square(0) => 0.

Равенство аргумента функции константе — только частный и самый простой вариант данных для суперкомпиляции. Другими примерами могут служить чётность/нечётность числа, конкретные или чётные/нечётные размеры массива, знания о порядке элементов массива или коллекции.

Например, для случая сортировки массива целых чисел можно получить несколько алгоритмов для размеров массива в 0, 1, 2, 3 и т. д. элементов, — результирующие алгоритмы будут работать без циклов, сводиться к нескольким сравнениям и выполняться максимально эффективно.

Процедура суперкомпиляции заключается в следующих шагах:

1. исполнение исходного алгоритма над интересующими данными на некоторой метамашине с запоминанием всех произведенных вычислений;
2. свёртка полученного списка вычислений таким образом, чтобы интересующие показатели алгоритма улучшились, а результат вычисления остался верным;
3. обратное преобразование списка вычислений в код нового алгоритма.

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

В отличие от классических методов оптимизации, суперкомпиляция может во много раз улучшить показатели работы даже простых алгоритмов. Например, для программы консольной игры в крестики-нолики суперкомпилятор может упразднить все массивы и циклы в предположении, что используется игровое поле 3×3, а также все написанные классы и подпрограммы или функции, в результате чего получится одна монолитная функция.

В 1970-е годы Валентин Турчин, Андрей Климов и их коллеги в Институте прикладной математики разработали суперкомпилятор для языка РЕФАЛ[2]. С 1998 года они работают над тем, чтобы использовать эти приёмы для языка Java[3][4][5].

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

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

• Смешанные вычисления — те же задачи и решение Андрея Петровича Ершова.
• Частичные вычисления — современный технически близкий подход

• Luba Parmyonova, Суперкомпиляция, TWiki Refaldevel, botik.ru, 2005, по материалам
  • https://web.archive.org/web/20130314234502/http://www.refal.org/doc/turchin/dag/dag.html#CONTENTS
  • Valentin F. Turchin. The Algorithm of Generalization in the Supercompiler. Partial Evaluation and Mixed Computation, IFIP 1988
• http://ndmitchell.com/downloads/paper-a_supercompiler_for_core_haskell-01_may_2008.pdf