6. Вперед, к рефалу-5 !

После всего проделанного в предыдущих параграфах возникает вопрос, а нельзя ли все это получить проще ?

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

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

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

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

В этом параграфе мы рассмотрим один из возможных способов реализации идеи и сравним результаты с предыдущими результатами.

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

Search_ {
((State) s.q)
((Symbol) s.symbol)
((Progr)((Instruction) ((CurrentState) s.q)
                       ((CurrentSymbol) s.symbol)
                       ((NextSymbol) s.c)
                       ((NextState) s.r)
                       ((Move) s.s)) e.instr) =
       ((NextSymbol) s.c)
       ((NextState) s.r)
       ((Move ) s.s)  ;

((State) s.q)
((Symbol) s.symbol)
((Progr)((Instruction) e.1) e.instr) =
		<Search_ 
		((State) s.q)
		((Symbol) s.symbol)
		((Progr) e.instr) > ;
 }

Суперкомпилируем этот интерпретатор и получаем результирующую программу. Здесь мы переходим к представлению ленты в виде последовательности символов на одном уровне скобочной структуры.

$ENTRY Go {
 ((Go) ((TapeLeft) e.103)
       ((Symbol) s.108)
       ((TapeRight) e.109))  = <F7 (e.103) s.108 e.109 > ;
}

F30 {
 (e.103 ((Square) s.135)) (e.109 ) '2'
  = <F30 (e.103 ) (((Square) '2') e.109) s.135 > ;

 (e.103 ) (((Square) s.142) e.109 ) 'b'
  = <F7 (e.103 ((Square) '2')
               ((Square) '2')) s.142 e.109 > ;
}

F7 {
 (e.103 ) 'b' ((Square) s.114) e.109
  = ((TapeLeft) e.103 ((Square) '.'))
    ((Symbol) s.114)
    ((TapeRight) e.109) ;

 (e.103 ) '2' ((Square) s.121) e.109
  = <F7 (e.103 ((Square) '2')) s.121 e.109 > ;

 (e.103 ((Square) s.131)) '1' e.109
  = <F30 (e.103 ) (e.109 ) s.131 > ;
}

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

Опять произведем пуски программ для последовательности из 256 единиц..

Исходный интерпретатор до суперкомпиляции делает 656 906 шагов и тратит на это 44.050 секунды. Результирующая после суперкомпиляции программа делает 131 078 шагов за 2.140 секунды.

Итак, в этой работе мы трижды получали суперкомпиляцией программу удвоения количества единиц на ленте.

На примере из 256 единиц

первая программа из первого параграфа тратила около одной секунды,

вторая программа из предыдущего параграфа тратила около четырех секунд,

третья программа из этого параграфа тратил около двух секунд.