Суперкомпиляция двойной интерпретации
(как один час машинного времени можно превратить в одну секунду)
В статье идет речь о преобразованиях программ с целью получения более эффективных программ. В качестве преобразователя используется суперкомпилятор SCP4 [1]. Суперкомпиляции происходит достаточно успешно при обработке интерпретирующих алгоритмов.
Представляет интерес вопрос о самоприменимости любых преобразователей программ. Здесь делается шаг к решению этой задачи - рассматриваем пример суперкомпиляции двойной интерпретации. Наблюдаемое здесь ускорение выполнения вынесено в название статьи.
Перейдем к постановке задачи. Мы имеем здесь дело с рядом объектов, взаимосвязанных между собой.
(1). Машина Тьюринга TM получает в качестве аргумента ленту Tape, запишем это так
<TM e.tape>
(2). Интерпретатор машины Тьюринга, написанный на XSLT [2] , он получает в качестве аргументов XML и DTD , запишем это так
<IntTM (e.DTD) (e.XML)>
или, подробнее,
<IntTM (e.DTD) e.tape >
<TM ! >
Мы перенесли обращение к конкретной машине Тьюринга на строчку ниже, чтобы подчеркнуть, что объектом преобразований итерпретатора является имеено сам этот вызов, а не его значение.
(3). Интерпретатор языка XSLT, написанный на рефале [3], который получает произвольные XSLT, XML, DTD, запишем это так
<IntXSLT (e.XSLT) (e.DTD) (e.XML)
или подробнее
<IntXSLT e.DTD e.tape >
<IntTM ( ! ) ! >
<TM ! >
(4). Ко всему этому применяется суперкомпилятор SCP4, запишем это так
<SCP4 >
<IntXSLT e.tape >
<IntTM <DTD ! > >
<TM ! >
Описание документа DTD у нас используется в качестве фильтра (рекурсивная динамическая типизация средствами языка рефал) входных XML-документов.
Итак, суперкомпилятор имеет в этом примере дело с пятью объектами, перечисленных выше. Часть из них можно специализировать, Тогда, если записать и поставить перед суперкопилятором задачу
( 1 )
<IntXSLT e.TM e.tape >
<IntTM <DTD ! ! > >
< ! ! >
|
то получится интерпретатор машины Тьюринга, написанный на рефале. Содержательный интерес представляет вопрос насколько полученная программа-интерпретатор будет эффективной. Небезинтересено также исследовать структуру полученной программы.
Если же использовать конструкцию
( 2 )
<IntXSLT e.tape >
<IntTM <DTD ! > >
<TM ! >
|
то получится конкретная программа на рефале, например, программа удвоения количества единиц mul2 или программа F12 замен 1 на 2.
План работы.
1. Машина Тьюринга.
2. Регулярные выражения и конечные автоматы, их интерпретация и суперкомпиляция.
3. Интерпретатор XSLT на рефале и суперкомпиляция его.
4. Интерпретатор машины Тьюринга на языке XSLT.