Subject: SCP's
From: Alexandr Korlyukov (korlyukov@grsu.grodno.by)
Date: Thu Mar 09 2000 - 10:01:45 MSK
Что может и чего не может суперкомпилятор
Суперкомпилятор есть !
Отметим сразу, что та часть данного текста, где речь идет о том, "что может суперкомпилятор", относится к суперкомпилятору SCP4, а та часть, где речь идет о том, "чего не может суперкомпилятор", касается всех суперкомпиляторов. Здесь собрано в одно место сказанное разными людьми в разных местах и в разное время.
При оценке способностей суперкомпилятора не уместны ни оптимистическая, ни пессимистическая позиции. Суперкомпилятор многое умеет - об этом можно посмотреть в "Пособии по суперкомпиляции", но при этом он многое и не может. Ничего удивительного в этом нет.
Имеет смысл воспринимать суперкомпилятор как новый инструмент, которым можно пользоваться. Инструмент, аналогичный любому разделу математики.
К примеру, понятием производной очень часто пользуются. Очень хорошо, что любую функцию можно продифференцировать. Но попробуйте найти с помощью производной минимум какой-либо произвольной функции не из задачника по математическому анализу!
Или попробуйте решить случайное тригонометрическое уравнение, опять же не из задачника.
Никого не удивляет подобное положение дел. Любой раздел математики хорош в одних случаях и никуда не годится в совершенно аналогичных случаях.
Суперкомпилятор умеет оптимизировать программы, Это утверждение и верно и неверно. Он умеет оптимизировать некоторые программы. Программу, которая уже написана оптимально, невозможно оптимизировать. Наверное, уже один раз обработанная суперкомпилятором программа не будет далее оптимизироваться. Наконец, наличие алгоритмически неразрешимых проблем накладывает свои ограничения на пределы оптимизации. Например, никакой суперкомпилятор не сможет любую программу-константу упростить до одного предложения. При этом всегда найдутся программы-константы, которые сокращаются до одного предложения.
Верно утверждение, что любую программу, которую суперкомпилятор хорошо обрабатывает, можно изменить так, что суперкомпилятор не сможет ее оптимизировать.
Перейдем к неформальным рекомендациям по использованию и применению суперкомпилятора. Здесь мы находимся в затруднительном положении ввиду вышеотмеченной аналогии с другими разделами математики. Ну о каких рекомендациях по решению логарифмических уравнений можно говорить, к примеру. Ситуации усугубляется еще и тем, что мы имеем дело с новым объектом, объектом не до конца исследованным, не все свойства которого известны. Думается, что многие сюрпризы еще впереди, и никакие рекомендации не будут полными и окончательными.
Отметим сразу, что наличие суперкомпилятора изменяет стиль программирования. Не будем обсуждать, в какую сторону меняется стиль, в лучшую или худшую. Что такое хорошо и что такое плохо при программировании под суперкомпилятор.
Пользуясь суперкомпилятором можно смело вводить такие функции, без которых очевидно можно обойтись. Например, функцию из одного предложения с левой частью e.1.Такая функция исчезнет из результирующей программы, в результате чего будет экономиться шаг рефал-машины при исполнении.
Можно не раздумывая пользоваться интерпретирующими функциями. Например, если в программе часто приходится вычислять арифметические выражения, то писать и читать
<Ar (e.1 '+' e.2) '*' (e.3 '+' e.4) >
гораздо удобнее, чем
<MUL (<ADD (e.1) e.2>) <ADD (e.3) e.4> >
Интерпретирующая функция Ar исчезнет из результирующей программы.
Замечено, что в следующих трех ситуациях суперкомпилятор проявляет себя достаточно эффективно.
Первый случай относится к функциям нескольких аргументов, часть из которых фиксирована до начала исполнения программы, например,
<F (e.Const) (e.Var)>
Сюда относятся интерпретаторы языков. В этом случае с переменной e.Const можно делать почти все, что угодно, добиваясь наглядности. Можно писать (s.1) (s.2) (s.3), можно размножать переменные. Конкретные примеры можно посмотреть в "Пособии по суперкомпиляции" в разделах "Машина Тьюринга", "Поиск подпоследовательности" и других. С переменной e.Var лучше не делать никаких преобразований, а только описывать левыми частями предложений ее структуру.
Второй случай относится к композиции функций
<F <G e.1>>
Например, функция G - перевод с русского языка на английский, функция F - перевод с английского на немецкий. В результате композиции получаем функцию перевода с русского языка на немецкий. При этом полезно иметь в виду, что промежуточная терминология (английские слова) не будет присутствовать в результирующей программе после суперкомпиляции.
Третий случай касается использования фильтров. Рассмотрим пример дифференцирования произвольной функции <Diff e.1>. Пусть мы хотим теперь получить функцию дифференцирования многочленов. Для этого можно ввести функцию <P e.1> , аргументом которой является произвольная функция, а значением - либо сама функция, если она многочлен, либо "отождествление невозможно" в противном случае. Тогда в результате суперкомпиляции композиции <Diff <P e.1>> мы получим более простую программу дифференцирования многочленов.
Отдельно выделяется случай, когда множество аргументов функции по каким-либо причинам оказывается конечным. Тогда после суперкомпиляции получится функция с постоянными левыми частями предложений. Это хорошо, когда имеется несколько случаев, и плохо, когда случаев несколько миллионов.
Суперкомпилятор позволяет строить из уже имеющихся функций новые функции, при этом часто оказывается, что не всегда будет иметься в наличии программа-оригинал, с которой можно было бы производить сравнение эффективности выполнения и тому подобное.
Отметим возможность чисто формально превращать интерпретатор в компилятор. При этом речь идет не просто о превращении, а о полезном превращении. Имеются примеры построения обратной функции исходя из алгоритма прямой функции.
Часто эффект применения суперкомпилятора проявляется именно там, где как-то можно представить результат оптимизации, хотя и не всегда. Пример неудачного применения суперкомпиляции - сложение в римской системе счисления. Там с самого начала было неизвестно, что же мы надеемся получить в качестве правил сложения в римской системе счисления. Использование Валидатора в качестве фильтра является примером удачного применения суперкомпилятора, хотя для выяснения этого понадобились эксперименты.
Для любого объема знаний находятся как простые задачи, так и сложные. Есть задачи из школьного учебника, а есть задачи олимпиадного характера любой степени сложности. Для решения и тех, и других достаточно школьных знаний.
Что-то похожее наблюдается и с использованием суперкомпилятора. Есть примеры и рекомендации полезного его использования. Есть примеры, когда не имеет смысла применять суперкомпиляцию. Появляются новые примеры, демонстрирующие эффект преобразования программ. Будут появляться примеры неочевидного применения суперкомпилятора. Так всегда происходит в каждой новой области знания.
Напрашивается аналогия с нестандартным анализом. Нестандартный анализ не позволяет доказывать ничего другого, что нельзя было бы доказать обычными методами. Это новая техника, новый аппарат, с помощью которого можно открывать новые факты (как чертежи в геометрии).
Все что может сделать суперкомпилятор, можно сделать и без него, например, вручную Раньше вручную писали программы в машинных кодах и многое другое.
This archive was generated by hypermail 2b25 : Mon Oct 25 2004 - 21:24:58 MSD