Рефал как язык для обработки xml-документов

Расширенную версию статьи читайте на refal.net/english/xmlref_1.htm

Требуется: метаязык

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

Язык XSL и его расширение XSLT наиболее известен как кандидат на роль метаязыка для XML. Он декларативен. Для его использования в качестве языка программирования необходим интерпретатор. А для его квалифицированного использования надо понимать, как работает интерпретатор. И это далеко не просто.

С точки зрения автора, наилучший выбор для желаемого метаязыка - Рефал [1].

Рефал в сравнении с другими языками

Рефал - функциональный язык, основанный на распознавании по образцу. Это значит, что:

1. Любые действия в программе представляются как вычисления при вызове некоторой функции.

2. Функции определяются набором предложений (правил), где в левой части мы видим образец аргумента (то есть аргумент, определенный только частично), а в правой части - выражение, которым заменяется вызов функции на одном шаге вычислений. Представленная в таком виде программа выглядит как декларативный документ: ее намного легче читать и понимать, чем программы, представленные как набор команд, включающих переходы из одной точки программы в другую.

В первые годы после появления Рефала он был единственным языком, сочетавшим эти две черты. В 1980-х годах появилось несколько подобных языков, в частности Haskell и ML. Сравнивая их с Рефалом, мы прежде всего отмечаем, что Рефал является простейшим в этом семействе языков. Одной из целей при создании Рефала было минимизировать список основных понятий, которые пользователь языка должен был понять и запомнить. В частности, переменные в Рефале могут быть только одного из трех фундаментальных типов (см. ниже), и создать новые типы нельзя. Чтобы различать классы значений, можно использовать метки. Так, например, если переменная x принимает значения, описывающие собаку, то она всегда появляется в форме терма (Sobaka x), где Sobaka - метка класса. Такой метод не только минимизирует (в определенном смысле) число базисных понятий, но и обладает тем преимуществом, что класс переменной всегда соседствует с самой переменной. Это полезно при обработке выражений и дает возможность легко определять и переопределять классы в динамике.

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

Списки были впервые введены в языке Lisp и стали широко использоваться в теории программирования. Список - это слегка ограниченное S-выражение, а S-выражение - это бинарное дерево. Списки языка Lisp, это не совсем те списки, которые мы понимаем интуитивно. Когда мы говорим о списке из трех элементов A, B и C, мы представляем себе выражение вида A-B-C, которое можно считать слева направо или справа налево. Со списками дело обстоит иначе. Их можно читать только слева направо: A®B®C. Чтобы достать последний элемент списка, надо достать начальный элемент и пройти весь список. Такая важная структура, как цепочка (строка), по которой можно гулять в двух направлениях, не может быть представлена списками.

В Рефале мы позволяем истинную конкатенацию выражений, которая создает цепочки. Это достигается представлением данных, включающим ссылки и назад, и вперед: A«B«C. Пользователь может воображать данные в компьютере такими, как он видит их на экране или распечатке.

Кроме конкатенаций, Рефал позволяет еще заключение в скобки. Это создает древесные структуры с произвольным числом дочерних узлов. Например, (A B (C) D) можно интерпретировать как дерево, где корень имеет четыре дочерних узла A, B, (C), D; (C) имеет одного потомка С, а A, B, C, D потомков не имеют: это листья.

Синтаксис Рефала чрезвычайно прост. R-выражение определяется следующим образом:

• Символ - это элемент структуры, который не может быть разложен на части: лист древесной структуры. Примеры символов: отдельный знак ‘a’, целое число 25, символическое имя quantity.

• Терм - это или символ, или выражение в скобках.

• Выражение - это цепочка термов, возможно пустая.

Соответственно есть три типа переменных: символьная переменная, имеющая префикс s, например s.1 или s.tag; переменная терма с префиксом t, например t.x - переменное выражение; префикс e, например e.5, e.x.1.

Следует отметить, что скобки в Рефале не являются символами: это лишь специальные знаки, создающие древесную структуру. Для вызова функций используются угловые скобки. Вызов функции F с аргументом Arg записывается в виде <F Arg>.

Чтобы показать, как строятся предложения и программы, определим на Рефале функцию Palindrom как предикат, дающий ответ на вопрос, является ли данная строка палиндромом (то есть читается одинаково слева направо и справа налево):

Palindrome {

В определении четыре предложения. В первом предложении образец аргумента имеет вид s.1 e.x s.1; если словами: аргумент кончается на ту же букву, что и начинается. В этом случае предикат применяется к внутренней части строки e.x. Заметим, что образец в первом предложении не может быть выражен в языке, основанном на списках. В таком языке аргумент должен быть сперва обращен, а затем его надо сравнить с исходным аргументом. Ясно, что такой алгоритм менее эффективен, чем наш.

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

Отображение XML в R-выражения

Для выделения подструктуры язык XML использует два маркера: <tag …> в начале и </tag> в конце подструктуры. Здесь tag - цепочка литер, называемая меткой. Многоточие означает, что там может быть расположена некая дополнительная информация. Подструктуры могут конкатенировать и вкладываться.

Тот, кто программирует на Рефале, немедленно узнаёт (и приветствует!) привычную структуру R-выражения, где <tag …> играет роль левой, а </tag> - правой скобки. Чтобы обрабатывать XML-текст на Рефале, мы прежде всего конвертируем его в R-выражение. Будем называть такое преобразование рефализацией. Эта простая однопроходная процедура, по существу, является синтаксическим разбором (парсированием), ибо R-выражение уже не линейная цепочка, а дерево. Детали этого входного преобразования могут варьироваться в зависимости от предпочтений программиста. Общий принцип таков: выделяя семантически значимые подструктуры, заключаем их в скобки.

В данной работе мы использовали следующие правила преобразований (опуская детали):

1. XML-терм вида:

   <tag property-list> content </tag>

   превращается в Рефал-терм.

   ((tag[property-list])[content]),

   где квадратные скобки указывают, что их содержимое еще подлежит преобразованию. Метки, как <tag>, превращаются в R-символы, начинающиеся с заглавной буквы. Цепочки литер заключаются в кавычки.

2. Список свойств в XML - это цепочка свойств, каждое из которых имеет вид:

   property-name = “property-value”,

   где property-name - это символическое имя, а property-value - цепочка литер. В Рефале данное свойство превращается в

   property-name (property-value).

3. В XML цепочка литер входит как есть, без кавычек. В Рефал-выражениях мы заключаем их в кавычки.

В качестве примера возьмем следующий текст в XML, заимствованный из [2] с небольшим упрощением. (см. Listing 1)

Преобразование XML в HTML

Одно из главных приложений преобразования XML-документов, это преобразование XML-документа в HTML-файл для вывода на экран или на печать. В частности, язык XSL возник как средство для решения этой задачи. Мы продолжим наш пример такого преобразования (см. [2]) и покажем, как задача решается на Рефале. Первая часть дела - рефализация XML-документа - уже сделана (Listing 2). Listing 3 - желаемый результат преобразования, Listing 4 - Рефал-программа, которая его осуществляет.

Рефал-программа устроена просто. На левой стороне предложения - образцы входного XML-документа, на правой стороне - соответствующие им фрагменты создаваемого выходного HTML-документа. В начале процесса аргументом функции Xh, выполняющим преобразования, является R-терм, представляющий весь ввод. Представляя его в виде образца, мы разбиваем его на меньшие части (значения переменных образца), к которым рекурсивно применяется функция Xh. Это процесс, обратный к построению сложных образцов из простых согласно синтаксису рефализированных XML-документов.

Основной синтаксический элемент языка XML представляется R-термом вида ((A *) ?), где A - метка, * - возможный список свойств, а знак вопроса указывает, что в это место может быть встроена другая подструктура. Термы могут конкатенироваться и вкладываться.

((A *) ?) ((B *) ?)

((A *) ((B *) ?) )

Эти схемы дают представление о том, чего надо ожидать в левых частях предложения.

Рассмотрим первое предложение программы. Метка Recipe относится ко всему документу. По законам языка HTML, документ должен открываться маркером <HTML> и закрываться маркером </HTML>. Что и сделано в программе.

В левой части второго предложения мы видим не один образец терма, а два. Причина здесь в том, что значение переменной e.name используется не только в выходе от своего терма Name (мы обозначаем термы именем используемой метки, набранным курсивом), но и в выходе от следующего терма Description. Простейший способ решить эту проблему - соединить эти два терма и сразу получить значения обеих переменных e.name и e.descr.

Терм Ingredients печатает «Ingredients» и создает HTML-таблицу, начинающуюся с маркера <TABLE…>. За ним следует заголовок таблицы, затем преобразование функцией Xh всего, что осталось (он дается переменной e.on), и, наконец, закрывающий маркер </TABLE>.

К этому моменту в аргументе функции Xh осталось четыре терма Ingredient, представляющих четыре ряда таблицы. В левой части четвертого предложения отщепляется один такой терм со свободными переменными e.qty, e.unit и e.item. В правой части конструируется соответствующий ряд значений в формате таблицы HTML. Это предложение применяется рекурсивно, отщепляя терм за термом. Когда отщеплять больше нечего, работает последнее предложение, и процесс завершается. Подчеркнем, что программа работает без изменений при любом числе рядов в таблице.

Последняя деталь. От программы требуется, чтобы пользователь мог указать в XML-документе, что тот или иной Ingredient (Item) является необязательным. Это должно указываться тем, что в терме Item содержится свойство Optional=”1", то есть Optional(‘1’) после рефализации. В HTML-файле это должно проявиться приписыванием к имени Ingredient свойства ‘(optional)’.

Мы удовлетворяем это требование ввода в поле свойств терма Item в левой части переменной e.option. Эта переменная зафиксирует, есть ли там свойство или же там пусто. Теперь осталось только приписать в правой части <Option e.option> к имени e.item терма Ingredient. Функция Option решает, будет ли это ‘(optional)’, или нет.

Заключение

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

• Рефал - функциональный язык. Программа на Рефале определяет алгоритм, а выглядит как декларация отношения между элементами ввода и вывода.

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

• В отличие от других известных автору функциональных языков, Рефал базируется на R-выражениях (а не S-выражениях) для создания структур данных. Базовая структура данных языка XML является, по существу, частным случаем R-выражений. Этот выбор структур создателями XML, по-видимому, не случаен. R-выражения не только удобны, они привычны каждому, кто изучал алгебру в школе.

• Рефал имеет очень короткий список основных понятий и чрезвычайно простой синтаксис. Его легко выучить.

• Рефал универсален как язык для обработки информации. Он может использоваться как единственный язык программирования при работе с символьными данными в широком спектре проблем - от простейших подстановок до сложнейших систем искусственного интеллекта.

Литература

[1] Valentin F.Turchin, Refal5: Programming Guide & Reference Manual, New England Publishing Co., Holyoke, 1989.

[2] Mark Johnson, XML for the Absolute Beginner, www.javaworld.com/javaworld/jw-04-1999/jw-04-xml_p.html.