Тезисы докладов

Программирование

В.Ф.Турчин предложил ряд идей по автоматическому преобразованию программ, которые назвал суперкомпиляций. Он поставил задачу создать инструменты для наблюдения за операционной семантикой программы, когда фиксирована функция F, вычисляемая этой программой. Результатом таких наблюдений должно быть построение нового алгоритмического определения некоторого расширения функции F. Новый алгоритм строится с целью более быстрого вычисления F на конкретных аргументах.

Позже, рядом авторов эти идеи В.Ф.Турчина изучались и в той или иной мере доводились до алгоритмов.

Нам удалось построить суперкомпилятор предметной областью которого является функциональный язык программирования Рефал-5. Демонстрация суперкомпилятора доступна на Web-странице в режиме on-line.

Первым шагом суперкомпилятор транслирует программу в язык Рефал-графов. Язык Рефал-графов ориентирован на адекватное описание временной эффективности и является выходным языком основной стадии преобразований.

Ключевые инструменты преобразований:

• Прогонка - расширение одношагового интерпретатора языка Рефал-графов Int. Int: Prog x States -> States , где Prog - множество программ, States - множество конкретных состояний памяти абстрактной машины. Прогонка определена на Prog x P_States, где P_States множество параметрических описаний подмножеств множества States в некотором фиксированном языке Param. States есть подножество множества P_States. Инструмент строит некоторое дерево возможных вычислений Int на заданном подмножестве множества States. Ветвления в дереве определяются синтаксисом и операционной семантикой преобразуемой программы, узлы дерева содержат параметризованные описания стека функций в данной точке. Возможны два режима работы алгоритма, соответсвующих ленивой и аппликативной семантикам интерпретации.
• Структурная индукция порождает потенциально бесконечное дерево таких вычислений посредством прогонки и факторизует его в конечный граф, порождая индукционные гипотезы в языке Param; пытается их доказать и, если не удается, строит более слабые гипотезы и ( или ) разбивает задачу на несколько подзадач.

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

  Приведём простой пример демострирующий оба этих иструмента:

  
         $ENTRY Go { e.input = ; }
         Sum {
          (e.x) () = e.x;
          (e.x) ('1' e.y) = '1' ;
         }
         

  Четыре последовательных применения нашего преобразователя к этой программе ( и результатам преобразований при последующих итерациях) приводят к такой одношаговой программе:

  
         $ENTRY Go { e.input = '111' e.input; }
         

  Профакторизованная компонента является кандидатом на оформление в виде функции в конечной программе-результате.

• В заключительной стадии программа чистится от лишних переменных, вызовов функций и транслируется из языка Рефал-графов в Рефал-5.

Литература.

• А.В.Корлюков. Несколько примеров преобразований суперкомпилятором Scp4. http://www.refal.net/~korlukov/pearls/ , 2001.
• А.В.Корлюков. Пособие по суперкомпилятору Scp4. http://www.refal.net/supercom.htm , 1999.
• A.P.Nemytykh. Supercompiler Scp4: Use of Quasi-Distributive Laws in Program Transformation , In: Proceedings of International Software Engineering Symposium, Wuhan University Journal of Natural Sciences, Vol. 6, No. 1-2, pp:375-382, March 2001, Wuhan, China.
• A.P.Nemytykh, V.F.Turchin. A Supercompiler Scp4: sources, on-line demonstration. http://www.botik.ru/pub/local/scp/refal5/ , 1999.
• A.P.Nemytykh, V.A.Pinchuk and V.F.Turchin. A Self-Applicable Supercompiler, in O. Danvy, R. Glueck, P. Thiemann (Eds.), Partial Evaluation, International Seminar, LNCS, vol.1110, pp. 322-337, Springer, 1996. Accessible via ftp://ftp.botik.ru/pub/local/APP/self-appl.ps.gz
• S.A. Romanenko. Arity Raiser and Its Use in Program Specialization. In: Proceedings of the ESOP'90, LNCS, vol. 432 Springer-Verlag, 1990, pp. 341-360.
• V.F.Turchin. The concept of a supercompiler, ACM Transactions on Programming Languages and Systems, 8, pp.292-325, 1986.
• V.F.Turchin. Refal-5, Programming Guide and Reference Manual, New England Publishing Co., 1989. Accessible via http://www.botik.ru/pub/local/scp/refal5/

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии

[Головная страница] [Конференции] [СО РАН]

© 2001, Сибирское отделение Российской академии наук, Новосибирск
© 2001, Объединенный институт информатики СО РАН, Новосибирск
© 2001, Институт вычислительных технологий СО РАН, Новосибирск
© 2001, Институт систем информатики СО РАН, Новосибирск
© 2001, Институт математики СО РАН, Новосибирск
© 2001, Институт цитологии и генетики СО РАН, Новосибирск
© 2001, Институт вычислительной математики и математической геофизики СО РАН, Новосибирск
© 2001, Новосибирский государственный университет
Дата последней модификации 06-Jul-2012 (11:45:21)