art21.htm

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

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

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

2.1. Языки XML, DTD, XSLT.

      XML - язык описания документов [2], XSLT - язык описания преобразований этих документов [2]. Пара (XSLT, XML) представляет собой некоторый язык программирования. Этот язык требует типизации данных - область определения конкретной программы описывается на языке DTD [2].

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

      Заметим, что то же верно и для технологии преобразований называемой специализацией [9??на Джонса]. Принятое разделение данных на статические и динамические ( известные и неизвестные в момент преобразований ) [ссылка] , с точки зрения простоты процесса преобразований, было бы правильно уточнить: на статические , динамические-однопроходные, динамические-двупроходные и т.д. Интересные преобразования алгоритма "по существу" могут быть получены лишь инструментами анализа и преобразований многопроходности. Суперкомпилятор SCP4 имеет несколько таких простых инструментов.

      Рассматриваемый ниже интерпретатор машины Тьюринга, конечно, имеет многопроходную ленту. Входным и выходным языком суперкомпилятора SСP4 является Рефал-5, поэтому программы на XSLT преобразуются косвенно - через интерпретатор XSLT, написанный на Рефале-5. И , следовательно, на выходе мы получаем также программу на Рефале-5.

      Осталось отметить, что инструменты анализа многопроходности позволяют динамически типизировать данные в момент суперкомпиляции. Эта информация может привести к дополнительным преобразованиям. Требование описания области определения XSLT-программы средствами DTD делает такую типизацию естественной.

      Язык DTD представляет собой расширенный вариант языка регулярных выражений [4].