introduction.htm

Суперкомпиляция двойной интерпретации

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

Александр Корлюков, Андрей Немытых

      Введение

      В статье идет речь о преобразованиях программ с целью получения более эффективных программ. В качестве преобразователя используется суперкомпилятор 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    !      >          

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