art252.htm

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

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

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

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

2.5.2. Тестирование: числовой янализ.

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

      Во всех примерах количество непустых клеток на ленте машины Тьюринга равно 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

<tag . . . > . . . </tag>

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

((tag . . . ) . . . )

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

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

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

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