Укрощение строптивого кода: "Taming Code Explosion in Supercompilation"

В последние два-три года суперкомпиляция набирает обороты. Отрадно, что статья шведов Питера Джонсона и Йохана Нордландера,  посвященная суперкомпиляции, принята на PEPM 2011. Саму статью можно взять отсюда.

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

1. Масштабируемость -  в идеале суперкомпилятор должен выполнять работу за прогнозируемое время - практически любой нетривиальный суперкомпилятор рискует "зависнуть" (очень долго преобразовывать) какую-нибудь программу.
2. Риск взрывоопасного роста кода (code explosion) - некоторые хитрые программы могут в результате суперкомпиляции разбухать.
3. Как показала практика, суперкомпилированные программы с трудом поддаются другим оптимизациям. Например, отсуперкомпилированную программу с трудом пережевывает компилятор GHC.

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

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

Например, выражение

case (case f x of {[] → []; x:xs → xs;}) of {[] → []; y:ys → [];}

"выворачивается наизнанку" и представляется так (в стековом виде):

[f x, 
case __ of {[] → []; x : xs → xs;},
case __ of {[] → []; y : ys → [];}]

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

Тестирование на вложение можно ускорить, если в каждом выражении хранить его размер - ведь вложиться может только меньшее в большее - можно избежать лишних переборов.

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

before - это некоторая часть нижней конфигурации, after - верхней. Вот, собственно, и вся эвристика.

Какие практические результаты? Есть известный бенчмарк nofib, состоящей из трех частей - мнимой (imaginary), спектральной (spectral) и реальной (real). Шведский суперкомпилятор преобразует большие части мнимой и спектральной части за разумное время - меньше трех секунд и увеличение объемы кода не превышает 5%.