Введение

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

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

Целью работы суперкомпилятора является анализ некоторой программы на предмет возможной ее оптимизации. В полном объеме такую задачу решить невозможно по принципиальной причине - такая задача относится к числу алгоритмически неразрешимых задач.

Что умеет делать суперкомпилятор - об этом и пойдет речь в настоящем пособии.

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

Предполагается, что читатель данного пособия знаком с языком программирования рефал. Все примеры приводятся для версии рефал-5 .

В настоящий момент есть ограничения: запрещены открытые переменные и повторные переменные выражения. Некоторые примеры предполагают от читателя знакомство с высшей математикой в объеме первого курса ВУЗа.

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

Для удобства пользования пособием в начале каждого параграфа организован набор ссылок:

- в первой строке - index, предыдущий параграф, последующий параграф,

- во второй строке - ссылки на тексты исходных рефал-программ,

- в третьей строке - ссылки на MST-схемы примеров,

- в четвертой строке - ссылки на тексты результирующих рефал-программ.

В конце параграфа повторяется первая строка ссылок.

Упражнения содержат возможные модификации приведенных примеров. Как правило, количество упражнений в каждом параграфе можно намного увеличивать.

В правилах пользования суперкомпилятором помещена общая информация для всех параграфов.