art22.htm

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

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

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

2.2. Регулярные выражения

      При функционировании трансформатора (программы 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, и вызывающий аварийную остановку на остальных документах.