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

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

Во всех примерах количество непустых клеток на ленте машины Тьюринга равно 8.

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

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

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

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

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

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

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

Для замены 8 единиц на 8 двоек потребовалось 24 шага без обработки краев ленты и 34 шага в случае обработки краев (здесь количество шагов больше ожидаемых восьми из-за запятых в остаточной программе и из-за представления последовательности символов в виде дерева). Для удвоения 8 единиц потребовалось 135 шагов без обработки краев ленты и 230 шагов в случае обработки краев (количество операций порядка 2*n^2), но в режиме интерпретации - 671 шаг, что тоже понятно, ведь приходится искать каждый раз подходящую инструкцию для машины Тьюринга. Эти цифры понятны и объяснимы, они демонстрируют идеальность суперкомпиляции.

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

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

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

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

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

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

Возьмем третью строку TMmul2, где коэффициент по шагам равен 4181. Нас интересует коэффициент 4181 - будет ли он такой же для времени.

Будем изменять количество единиц на ленте, а именно, сначала 2 единицы, затем 4 и так далее, каждый раз удваивая их количество (в первом столбце указываем это количество). Получаем

.

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

Далее будем производить пуски программы только после суперкомпиляции, пока не получим разумное время -

Для вычисленией, возьмем время до суперкомпиляции для 8 единиц - 13.620 секунды, и время после суперкомпиляции для 128 единиц - 1.100 секунды.

128 разделить на 8 будет 16.

16 в квадрате - получается 256.

Время 13.620 надо умножить на 256 получается 3 486.720 секунд (или 58 минут, или около одного часа).

Теперь делим 3 486.720 секунд на 1.100 секунды - получаем коэффициент 3170.

Немного меньше, чем первоначальный коэффициент 4188 по шагам ( но не в 10 или в 100 раз меньше, что, в принципе, могло быть).

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

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

Go {
 ((Instruction e.103 ) e.101 )
 ((State ) e.105 )
 ((TapeLeft ) e.107 )
 ((Symbol ) e.113 )
 ((TapeRight ) e.111 ) e.1  = <F18 (e.107 ) (e.111 ) e.113 > ;
}

F63 {
 (((Nod) ((Square) '2') ((Nod) e.175) e.167) e.107)
                        ((Nod) e.169) e.111
  = <F63 (((Nod) e.175)) ((Nod) ((Square) '2')
                         ((Nod) e.169 )) >;

 (((Nod) ((Square)'b') ((Nod) e.181) e.167) e.107)
                       ((Nod ) ((Square) e.185)) e.111
  = <F18 (((Nod) ((Square) '2') ((Nod) ((Square) '2')
                                ((Nod) e.181 )))) ( ) e.185 >;

 (((Nod) ((Square) 'b') ((Nod) e.181) e.167) e.107)
                        ((Nod) ((Square) e.185)
                        ((Nod) e.188) e.169) e.111
  = <F18 (((Nod) ((Square) '2') ((Nod) ((Square) '2')
                                ((Nod) e.181))))
         (((Nod) e.188)) e.185 >;
}

F18 {
 (((Nod) e.115) e.107)
 (((Nod) ((Square) e.121))) 'b'
  = ((TapeLeft) ((Nod) ((Square) '.')
                ((Nod) e.115)))
    ((Symbol) e.121)
    ((TapeRight)) ;

 (((Nod) e.115) e.107)
 (((Nod) ((Square) e.121) ((Nod) e.130) e.117) e.111) 'b'
  = ((TapeLeft) ((Nod) ((Square) '.') ((Nod) e.115 )))
    ((Symbol) e.121)
    ((TapeRight) ((Nod) e.130)) ;

 (((Nod) e.137) e.107)
 (((Nod) ((Square) e.143)))) '2'
  = <F18 (((Nod) ((Square) '2')) ((Nod) e.137))) ( ) e.143 >;

 (((Nod) e.137) e.107)
 (((Nod) ((Square) e.143) ((Nod) e.153) e.139) e.111) '2'
  = <F18 (((Nod) ((Square) '2') ((Nod) e.137)))
         (((Nod) e.153)) e.143 >;

 (e.107) (e.111) '1'  = <F63 (e.107) e.111 >;
}

Поясним, что конструкция языка XSLT

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

в поле зрения языка рефал записываем в виде

((tag . . . ) . . . )

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

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