scp2int

(как один час машинного времени можно превратить в одну секунду)

2. Язык преобразования документов XSLT: эксперименты с суперкомпилятором Scp4.

2.5. Эксперименты по суперкомпиляции двойной интерпретации.

program.zip - все программы, упомянутые в тексте статьи

В статье идет речь о преобразованиях программ с целью получения более эффективных программ. В качестве преобразователя используется суперкомпилятор SCP4 [1]. Суперкомпиляции происходит достаточно успешно при обработке интерпретирующих алгоритмов.

Представляет интерес вопрос о самоприменимости любых преобразователей программ. Здесь делается шаг к решению этой задачи - рассматривается пример суперкомпиляции двойной интерпретации. Наблюдаемое здесь ускорение выполнения вынесено в название статьи.

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

(1). Машина Тьюринга TM получает в качестве аргумента ленту Tape, запишем это так

(2). Интерпретатор машины Тьюринга, написанный на XSLT [2] , он получает в качестве аргументов XML и DTD , запишем это так

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

(3). Интерпретатор языка XSLT, написанный на рефале [3], который получает произвольные XSLT, XML, DTD, запишем это так

(4). Ко всему этому применяется суперкомпилятор SCP4, запишем это так

Описание документа DTD у нас используется в качестве фильтра (рекурсивная динамическая типизация средствами языка рефал) входных XML-документов.

Итак, суперкомпилятор имеет в этом примере дело с пятью объектами, перечисленных выше. Часть из них можно специализировать, Тогда, если записать и поставить перед суперкопилятором задачу

то получится интерпретатор машины Тьюринга, написанный на рефале. Содержательный интерес представляет вопрос насколько полученная программа-интерпретатор будет эффективной. Небезинтересено также исследовать структуру полученной программы.

то получится конкретная программа на рефале, например, программа TMDoublePQ удвоения количества символов P с заменой их на символы Q или программа TMPQ замен P на Q.

В теоpии алгоpитмов в качестве точного математического эквивалента для общего интуитивного пpедставления об алгоpитме используется понятие машины Тьюpинга .

Пpогpамма для машины Тьюpинга состоит из последовательности инстpукций. Каждая инстpукция имеет вид

Пpедполагается, что в обе стоpоны от введенной последовательности символов находится бесконечное количество символов пpобел (пробел будем обозначать символом B).

Hачальное внутpеннее состояние - 'start', конечное внутреннее состояние - 'stop'.

Рассмотрим пример программы для машины Тьюринга, который будет многократно использоваться в дальнейшем - пример DoublePQ удвоения количества символов P на ленте с заменой их на символы Q. Если, к примеру, на ленте в начале работы находится 10 (подряд написанных) букв P, и головка указывает на первую из них, то в конце будут находиться 20 букв Q.

                                                       ( 3 )
  CurrentState CurrentSymbol NextSymbol NextState   Movement    
    start            B           B       stop        right     
    start            Q           Q       start       right     
    start            P           Q       moveleft    left     
    moveleft         Q           Q       moveleft    left     
    moveleft         B           Q       start       right

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

*$MST_FROM_ENTRY;                                         ( 4 )

* Call for a concrete Turing machine ( the program ).
$ENTRY Go {
 (e.TapeLeft) (s.CurrentSymbol) (e.TapeRight) =
   <Turing (
       (start     'BB'  stop      right)
       (start     'QQ'  start     right)
       (start     'PQ'  moveleft  left )
       (moveleft  'QQ'  moveleft  left )
       (moveleft  'BQ'  start     right) )
   (start)  (e.TapeLeft) (s.CurrentSymbol) (e.TapeRight) >;
 }

* The interpretator itself. <Turing (e.Program)
*                                   (s.CurrentState)
*                                   (e.LeftPartOfTape)
*                                   (s.CurrentSymbol)
*                                   (e.RightPartOfTape)>
Turing  {
  (e.instr) (stop) (e.left) (s.symbol) (e.right) =
                    (e.left) (s.symbol) (e.right) ;

  (e.instr) (s.q) (e.left) (s.symbol) (e.right)  =
           <Turing (e.instr) <Turing1 
                             <Search (s.q s.symbol) (e.instr)> 
                             (e.left) (s.symbol) (e.right)>  >;
 }

Turing1   {
 (s.c s.r left) ( ) (s.symbol) (e.right) = 
                         (s.r) ( ) ('B') (s.c e.right) ;
 (s.c s.r left) (e.left s.a) (s.symbol) (e.right) =
                         (s.r) (e.left) (s.a) (s.c e.right) ;
 (s.c s.r right) (e.left) (s.symbol) ( ) =
                         (s.r) (e.left s.c) ('B') ( ) ;
 (s.c s.r right) (e.left) (s.symbol) (s.a e.right) =
                         (s.r) (e.left s.c) (s.a) (e.right) ;
 }

Search   {
  (s.q s.b) ((s.q s.b s.NextSymbol s.NextState s.Movement) e.instr) =
                     (s.NextSymbol s.NextState s.Movement);
  (s.q s.b) ((e.1) e.2) = <Search (s.q s.b) (e.2)>;
 }

Входная точка Go зафиксировала специализацию интерпретатора по конкретной машине Тьюринга. После суперкомпиляции получаем программу

                                                         ( 5 )

* InputFormat: <Go (e.TapeLeft)(s.CurrentSymbol) (e.TapeRight)>
$ENTRY Go {
 (e.101 ) (s.103 ) (e.104 )  = <F6 (e.101 ) s.103 e.104 > ;
}

F59 {
 () () 'Q'  = ('QQQB' ) ('B' ) () ;
 () (s.119 e.104 ) 'Q'  = <F6 ('QQQ' ) s.119 e.104 > ;
 (e.101 s.118 ) (e.104 ) 'Q'  = <F59 (e.101 ) ('Q' e.104 ) s.118 > ;
 (e.101 ) () 'B'  = (e.101 'QQB' ) ('B' ) () ;
 (e.101 ) (s.123 e.104 ) 'B'  = <F6 (e.101 'QQ' ) s.123 e.104 > ;
}

F6 {
 (e.101 ) 'B'  = (e.101 'B' ) ('B' ) () ;
 (e.101 ) 'B' s.105 e.104  = (e.101 'B' ) (s.105 ) (e.104 ) ;
 (e.101 ) 'Q'  = (e.101 'QB' ) ('B' ) () ;
 (e.101 ) 'Q' s.109 e.104  = <F6 (e.101 'Q' ) s.109 e.104 > ;
 () 'P'  = ('QQB' ) ('B' ) () ;
 () 'P' s.117 e.104  = <F6 ('QQ' ) s.117 e.104 > ;
 (e.101 s.116 ) 'P' e.104  = <F59 (e.101 ) (e.104 ) s.116 > ;
}

Для получения коэффициентов ускорения выполнения мы подготовили пример из 512 единиц.

Суперкомпилятор SCP4 преобразует программы на диалекте Рефал-5 [3]. Выполнение рефал-программы состоит из последовательности элементарных действий, называемых шагами [3]. Время исполнения шага Рефал-машины, вообще говоря, не является равномерно-ограниченным по данным. Конкретное проявление этой неограниченности зависит от реализации Рефала. Кроме того, в статье используется только подмножество Рефала-5 ( strict Рефал ), в котором: в образцах не допускаются открытые e-переменные и повторные t- и е-переменные [3]; левая часть предложения состоит из одного образца. Везде далее мы будем иметь ввиду это подмножество Рефала и конкретную релизацию Рефала-5 [7]. В данных условиях, время исполнения шага машины , соответствующего некоторому Рефал-предложению, равномерно ограничено тогда, когда в этом предложении нет повторных t- и е-переменных в правой части. Обратное неверно. Время исполнения каждого шага программы (4) равномерно ограничено по данным, если же входной точкой объявить Turing, то шаги соответствующие второму предложению этой функции не обладают таким свойством.

До суперкомпиляции количество Рефал-шагов равняется 2 634 778, время исполнения - 15.242 секунды, после суперкомпиляции количество Рефал-шагов равняется 525 319, время - 2.053 секунды. Таким образом, мы имеем ускорение по шагам Kstep = 5.016, ускорение по времени Ktime = 7.388.

Примеры выполнялись на машине 500MHz, оперативная память 262 144K, операционная система Windows2000.

Глядя на остаточную после суперкомпиляции программу, мы видим, что многие предложения предназначаны для обработки краев ленты. Теоретически, лента предполагается бесконечной в обе стороны, практически же, она конечна, и мы можем, либо добавлять по мере надобности пустые клетки, либо предполагать, что пустых клеток всегда достаточно. Ясно, что во втором случае все программы получаются компактнее.

В дальнейшем мы будем рассматривать именно этот более простой случай, каждый раз упоминая, что же получается в общем случае.

Уберем в исходной Рефал-прогамме в функции Turing1 первое и третье предложения, тогда после суперкомпиляции получается следующая более обозримая программа :

                                                        ( 6 )

* InputFormat: <Go (e.TapeLeft)(s.CurrentSymbol) (e.TapeRight)>
$ENTRY Go {
 (e.101 ) (s.103 ) (e.104 )  = <F6 (e.101 ) s.103 e.104 > ;
}

F27 {
 (e.101 s.117 ) (e.104 ) 'Q'  = <F27 (e.101 ) ('Q' e.104 ) s.117 > ;
 (e.101 ) (s.121 e.104 ) 'B'  = <F6 (e.101 'QQ' ) s.121 e.104 > ;
}

F6 {
 (e.101 ) 'B' s.105 e.104  = (e.101 'B' ) (s.105 ) (e.104 ) ;
 (e.101 ) 'Q' s.109 e.104  = <F6 (e.101 'Q' ) s.109 e.104 > ;
 (e.101 s.116 ) 'P' e.104  = <F27 (e.101 ) (e.104 ) s.116 > ;
}

Здесь все прекрасно видно. Функция F6 соответствует внутреннему состоянию start , функция F27 соответствует внутреннему состоянию moveleft. Каждое предложение соответствует одной инструкции программы для машины Тьюринга. Количество Рефал-шагов равняется количеству шагов машины Тьюринга. В результирующей программе отсутствуют термины start, moveleft, stop.

Выходом суперкомпилятора является оптимальная программа на рефале, то есть произошла компиляция программы для машины Тьюринга (3) в рефал-программу (6). Здесь под "оптимальностью " мы имеем ввиду оптимальность в рамках описанного нами ранее алгоритма: никакого изменения алгоритма "по существу " не произошло.

2. Язык преобразования документов XSLT: эксперименты с суперкомпилятором Scp4.

XML - язык описания документов [2], XSLT - язык описания преобразований этих документов [2]. Пара (XSLT, XML) представляет собой некоторый язык программирования. Этот язык требует типизации данных - область определения конкретной программы описывается на языке DTD [2].

Данный язык интересен с точки зрения суперкомпиляции по следующим причинам. С одной стороны, это реальный язык программирования интернет-документов, который, видимо, получит широкое распространение. С другой стороны, данные-XML этого языка очень близки к данным Рефала. Наконец, язык преобразований XSLT достоточно беден по выразительным средствам и стимулирует к написанию программ однопроходных по данным ( т.е. однажды преобразованная часть данных навсегда выходит из поля зрения конкретной программы ). Последнее обстоятельство облегчает процесс суперкопиляции, позволяет получать на выходе SCP4 более эффективные по времени исполнения программы.

Заметим, что то же верно и для технологии преобразований называемой специализацией [9??на Джонса]. Принятое разделение данных на статические и динамические ( известные и неизвестные в момент преобразований ) [ссылка] , с точки зрения простоты процесса преобразований, было бы правильно уточнить: на статические , динамические-однопроходные, динамические-двупроходные и т.д. Интересные преобразования алгоритма "по существу" могут быть получены лишь инструментами анализа и преобразований многопоходности. Суперкомпилятор SCP4 имеет несколько таких простых инструментов.

Рассматриваемый ниже интерпретатор машины Тьюринга, конечно, имеет многопроходную ленту. Входным и выходным языком суперкомпилятора SСP4 является Рефал-5, поэтому программы на XSLT преобразуются косвенно - через интерепретатор XSLT, написанный на Рефале-5. И , следовательно, на выходе мы получаем также программу на Рефале-5.

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

Язык DTD представляет собой расширенный вариант языка регулярных выражений [4].

При функционировании трансформатора (программы XSLT) используется описание DTD преобразуемого документа XML.

Мы используем следующее DTD для машины Тьюринга.

<!ELEMENT Go (Instruction, State, TapeLeft, Symbol, TapeRight)>
<!ELEMENT TapeLeft  (Nod) >
<!ELEMENT TapeRight (Nod) >
<!ELEMENT Nod ((Square, Nod) | Square) >
<!ELEMENT Symbol    (#PCDATA) >
<!ELEMENT Square    (#PCDATA) >
<!ELEMENT State     (#PCDATA) >
<!ELEMENT Instruction (Instruction | EMPTY) >
<!ATTLIST Instruction
                       CurrentState  CDATA #REQUIRED
                       CurrentSymbol CDATA #REQUIRED 
                       NextSymbol    CDATA #REQUIRED
                       NextState     CDATA #REQUIRED
                       Movement      CDATA #REQUIRED >

Здесь Instruction - это набор инструкций для машины Тьюринга, State - текущее внутреннее состояние, TapeLeft - левая часть ленты до обозреваемого сивола, Symbol - обозреваемый символ, TapeRight - правая часть ленты.

Логично было бы ленту для машины Тьюринга записывать в виде последовательности символов, у нас - Square. Мы не стали выбирать такое представление по двум причинам. По идеологии машины Тьюринга все действия происходят на ленте локально около обозреваемого символа. Язык XSLT не позволяет просто переписать остаток ленты, приходится переписывать все оставшиеся символы по одному, что приводит к неэффективности.

Поэтому у нас на каждом уровне дерева записывается один символ и одна ссылка на оставшуюся часть ленты. Вторая причина состоит в том, что по смыслу интерпретации приходится постоянно сравнивать значения из различных мест. В языке XSLT инструкция <xsl:for-each . . . > переводит нас внутрь поддерева, и другие части дерева становятся или недоступны, или доступны сложным образом.

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

Как мы отмечали выше, DTD используется для контроля структуры входного документа XML. С другой стороны, знание структуры документа может помочь строить более эффективные программы. При обычном программировании (без использования суперкомпилятора) совсем не очевидно и не просто использовать знание о структуре документа для повышения эффективности исполнения алгоритма.

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

Мы используем фильтр, который является тождественной функцией на документах, соответствующих заданному DTD, и вызывающий аварийную остановку на остальных документах.

2.3. Интерпретатор XSLT на Рефале и суперкомпиляция его.

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

На языке программирования рефал-5 [3] написан интерпретатор VT.ref некоторого подмножества языка XSLT.

На примере подмножества XSLT и его интерпретатора продемонстрирована возможность (через суперкомпиляцию интерпретатора) компиляции в эффективную программму (на рефале) с очень приличным ускорением по сравнению с интерпретацией. Целью нашей работы является демонстрация способностей суперкомпилятора SCP4. [1].

Интерпретатор VT.ref принимает программы из фрагмента языка XSLT, замкнутого относительно синтаксических конструкций

Реализована интерпретация встроенной функции xt:node-set - без нее невозможно организовать рекурсию, которая необходима при интерпретации машины Тьюринга.

Невозможность описать в языке XSLT повторный проход по данным делает его великолепным практическим объектом суперкомпиляции. Именно в этом и есть гланая причина, почему всё так легко получается при специализации интерпретатора по конкретным программам, если эти программы не используют функцию xt:node-set.

Заметим, что это свойство хорошо и для специализаторов.

2.4. Интерпретатор машины Тьюринга на языке XSLT.

Интерпретатор VT.ref определяет семантику рассматриваего фрагмента языка XSLT в терминах Рефала. Второй интерпретатор, рассматриваемый в этом параграфе, является интерпретатором машины Тьюринга, и написан он на языке XSLT.

Предъявление такого интерпретатора машины Тьюринга является доказательством алгоритмической полноты данного подмножества XSLT.

Для проведения сравнительных экспериментов были подготовлены следующие документы :

TM.dtd - описание области определения программ TM.xsl , TMPQ.xsl и TMDoublePQ.xsl,

TM.xml - входные данные для программ TM.xsl , TMPQ.xsl и TMDoublePQ.xsl,

TM.xsl - интерпретатор машины Тьюринга , обработка краев ленты не предусмотрена, эксперименты производились для конкретной машины Тьюринга из примера DoublePQ,

TMPQ.xsl - вариант предыдущей программы, работающей с конкретной машиной Тьюринга - замены символов P на Q,

TMDoublePQ.xsl - вариант предыдущей программы, работающей с конкретной машиной Тьюринга - удвоение букв P с заменой их на Q.

TMN.dtd - описание области определения TMNPQ.xsl и TMNDoublePQ.xsl,

TMN.xml - входные данные для программ TMNPQ.xsl и TMNDoublePQ.xsl,

TMNPQ.xsl , TMNDoublePQ.xsl - варианты TMPQ.xsl,TMDoublePQ.xsl , в которых предусмотрена обработка краев ленты, при необходимости справа или слева добавляются пустые клетки.

2.5. Эксперименты по суперкомпиляции двойной интерпретации

2.5.1. Об адекватной выразимости результата суперкомпиляции.

Прежде чем рассматривать конкретные результаты экспериментов, необходимо сказать, что реальным внутренним языком преобразований суперкомпилятора SCP4 является не Рефал-5, а язык Рефал-графов [ссылка на китайскую статью],[ссылка на Турчина], в котором шаги Рефал-машины разбиты на более элементарные действия и отождествление происходит не с одним образцом из левой части Рефал-предложения, а , в некотором смысле, со всеми левыми частями "одновременно", то есть в языке есть средства позволяющие описать процесс отождествления в виде нетривиального дерева, причём неудача при отождествлении отбрасывает лишь на ближайшее ветвление. Ветвления в этом смысле "функциональны" то есть ведут себя как Рефал-5 функции, неудача внутри которых приводит к аварийной остановке. Можно указать здесь на грубую аналогию с блоками в Рефале-5.

Первым шагом SCP4 переводит программу в язык Рефал-графов, и лишь затем начинает преобразования. Получив ответ в этом же языке, он строит Рефал-программу: с точки зрения пользователя, как входным так и выходным языком является Рефал-5.

Программа на яыке Рефал-графов часто содержит простую синтаксическую информацию, позволяющую оптимизировать процесс интерпретации, если его вести напрямую. Рефал-5 некоторых из этих выразительных средств не содержит. Это может привести к неадекватной трансляции в него результата преобразований SCP4 [ссылка на С.Романенко]. Тем самым, с практической точки зрения, представляет интерес непосредственная интерпретация языка Рефал-графов.

Результаты вычислений пяти примеров, описанных в предыдущем параграфе, мы оформили в таблицу.

Во всех примерах количество непустых клеток на ленте машины Тьюринга равно 16. Такое маленькое число объясняется получающимся соотношением времен - часы и секунды. Иначе либо одно время очень большое, либо другое - очень маленькое.

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

В столбце steps указано количество рефал-шагов интерпретатора, в столбце seconds - время исполнения в секундах.

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

В столбце steps указано количество рефал-шагов, в столбце seconds - время исполнения в секундах.

Число SpeedupSteps - коэффициент ускорения по шагам - частное от деления первого столбца на третий.

Число SpeedupTime - коэффициент ускорения по времени - частное от деления второго столбца на четвертый. Если происходило деление на 0, то частное не указано.

Сделаем пояснения по таблице. Рассмотрим третий столбец steps.

Для замены 16 букв P на 16 букв Q потребовалось 40 шагов без обработки краев ленты и 58 шагов в случае обработки краев (здесь количество шагов больше ожидаемых 16 из-за неадекватности перевода остаточной программы из Рефал-графа в Рефал-5 ( смотри пункт 2.5.1. ) и из-за представления последовательности символов в виде дерева). Для удвоения 16 букв P потребовалось 519 шагов без обработки краев ленты и 1018 шагов в случае обработки краев (количество операций порядка 2*n^2), но в режиме интерпретации - 3195 шагов, что тоже понятно, ведь приходится искать каждый раз подходящую инструкцию для машины Тьюринга. Эти числа понятны, они демонстрируют серьёзные преобразования в процессе суперкомпиляции.

Первый столбец. Числа большие, потому что происходит интерпретация интерпретатора. Количество элементарных действий как бы возводится в квадрат.

Коэффициент SpeedupSteps очень большой из-за малости чисел после суперкомпиляции. Этого следовало ожидать на основании свойств XSLT-программ из тестируемых примеров.

Коэффициент SpeedupTime здесь ничему не соответствует. Как большие, так и малые времена вызывают недоверие.

Мы попробовали косвенно определить коэффициент ускорения по времени получаемый при суперкомпиляции двойной интерпретации.Трудность, связанных с определением этого коэффициента состоит в том, что либо не хватает памяти (свопинг) при интерпретации до суперкомпиляции, либо нулевое время после суперкомпиляции.

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

Вывод, к которому мы пришли, состоит в том, что ускорения по времени и по шагам примерно совпадают.

Возьмем третью строку TMDoublePQ, где коэффициент по шагам равен 3777. Будем изменять количество единиц на ленте, а именно, сначала 2 единицы, затем 4 и так далее, каждый раз удваивая их количество. По смыслу алгоритма, зависимость квадратичная, то есть, при удвоении количества единиц время и шаги должны учетверяться. Примерно это мы и наблюдали, пока не дошли до свопинга. Далее производились пуски программы только после суперкомпиляции, пока не получили время порядка секунд. Элементарные арифметические действия показывают, что числа SpeedupSteps и SpeedupTime отличаются незначительно.

Наглядно, ускорение по времени SpeedupTime таково - один час превращается в одну секунду.

Приведем в качестве примера результирующую после суперкомпиляции программу TMDoublePQ.

Go {
 ((Instruction e.102) e.101)
 ((State ) e.104)
 ((TapeLeft) e.106) ((Symbol) s.112)
 ((TapeRight) e.110) e.1  = <F16 (e.106) (e.110) s.112> ;
 }

F69 {
 (((Nod) ((Square) Q ) ((Nod) e.171) e.166) e.106)
                       ((Nod) e.164) e.110
  = <F69 (((Nod) e.171)) ((Nod) ((Square) Q )
                         ((Nod) e.164))>;
                           
 (((Nod) ((Square) B ) ((Nod) e.176) e.166) e.106)
                       ((Nod) ((Square) s.180)) e.110
  = <F16 (((Nod) ((Square) Q ) ((Nod) ((Square) Q ) 
                               ((Nod) e.176)))) ( ) s.180>;
                                 
 (((Nod) ((Square) B ) ((Nod) e.176) e.166) e.106)
                       ((Nod) ((Square) s.180)
                       ((Nod) e.184) e.164) e.110
  = <F16 (((Nod) ((Square) Q ) ((Nod) ((Square) Q )
                               ((Nod) e.176 ))))
         (((Nod) e.184)) s.180>;
 }

F16 {
 (((Nod) e.115) e.106) (((Nod) ((Square) s.119))) B
   = ((tm) ((TapeLeft) ((Nod) ((Square) B )
                       ((Nod) e.115)))
           ((Symbol) s.119)
           ((TapeRight)));
             
 (((Nod) e.115) e.106) (((Nod) ((Square) s.119)
                        ((Nod) e.129) e.113) e.110) B
   = ((tm) ((TapeLeft) ((Nod) 
           ((Square) B ) ((Nod) e.115)))
           ((Symbol) s.119)
           ((TapeRight) ((Nod) e.129)));
            
 (((Nod) e.137) e.106) (((Nod) ((Square) s.141))) Q
   = <F16 (((Nod) ((Square) Q ) ((Nod) e.137))) ( ) s.141>;
   
 (((Nod) e.137) e.106) (((Nod) ((Square) s.141)
                        ((Nod) e.151) e.135) e.110) Q
   = <F16 (((Nod) ((Square) Q ) ((Nod) e.137)))
          (((Nod) e.151)) s.141>;
          
 (e.106) (e.110) P = <F69 (e.106) e.110>;
 }

при парсировании в данные Рефала кодируется в виде

Остаточная после суперкомпиляции программа идеальна в том смысле, что в ней не осталось ничего лишнего. Две функции соответствуют двум внутренним состояниям заданной программы для машины Тьюринга. Количество шагов результирующей программы равно количеству шагов исходной машины Тьюринга. Вся терминология интерпретатора XSLT исчезла, так же как исчезла и терминология интерпретатора машины Тьюринга.

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

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

Несколько больший объем программы, по сравнению с аналогичной программой из первого параграфа, связан с использованием длинных имен в задании ленты для машины Тьюринга.

4. Саломаа A. Жемчужины теории формальных языков, // М: Мир, 1986. - 159 с.

6. V.F. Turchin. "Refal-5, Programming Guide & Reference Manual.", New England Publishing Co., 1989 ( electronic version: http://www.botik.ru/pub/local/scp/refal5/ ,2000. )

9. Bjorner D., Ershov A.P., Jones N.D. eds. Partial Evaluation and Mixed Computation,
Proceedings of the IFIP TC2 Workshop, pp. 531-549, North-Holland Publishing Co., 1988.

	steps	seconds	steps	seconds	SpeedupSteps	SpeedupTime
TM	1960210	14.741	3195	0.070	613	210
TMPQ	48789	0.350	40	0.000	1219
TMDoublePQ	1960475	14.761	519	0.000	3777
TMNPQ	49512	0.300	58	0.000	853
TMNDoublePQ	1988750	13.830	1018	0.020	1953	691