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

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

25.02.2001, "Компьютерра" №25 от 02 июля 2001 года

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

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

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

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

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

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

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

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

В первые годы после появления Рефала он был единственным языком, сочетавшим эти две черты. В 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 = <Palindrome e.x>;

s.1 = True;

= True;

e.x = False; }

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

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

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

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

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

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

XML-терм вида:

<tag property-list> content </tag>

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

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

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

property-name = “property-value”,

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

property-name (property-value).
В 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.

(обратно к тексту)
Listing 1. XML-документ. После рефализации получаем R-выражения (Listing 2).

<Name>Lime Jello Marshmallow Cottage Cheese Surprise</Name>

My grandma's favorite (may she rest in peace).

</Description>

<Item>lime gelatin</Item>

</Ingredient>

<Item>multicolored tiny marshmallows</Item>

</Ingredient>

<Item>Cottage cheese</Item>

</Ingredient>

<Item optional="1">Tabasco sauce</Item>

</Ingredient>

</Ingredients>

</Recipe>

(обратно к тексту)
Listing 2. Документ (Listing 1), форматированный как R-выражения. Обратное отображение R-выражений в XML так же просто и эффективно.

((Recipe)

((Name) 'Lime Jello Marshmallow Cottage Cheese Surprise')

((Description) 'My grandma\'s favorite (may she rest in peace).')

((Ingredients)

((Ingredient)

((Qty Unit('box')) 1)

((Item) 'lime gelatin')

)

((Ingredient)

((Qty Unit('g')) 500)

((Item) 'multicolored tiny marshmallows')

)

((Ingredient)

((Qty Unit('ml')) 500)

((Item) 'Cottage cheese')

)

((Ingredient)

((Qty Unit('dash'))

((Item Optional('1')) 'Tabasco sauce')

)

(обратно к тексту)
Listing 3. HTML-файл, полученный преобразованием программы из Listing 2.

<HTML>

<HEAD>

<TITLE>Lime Jello Marshmallow Cottage Cheese Surprise</TITLE>

</HEAD>

<BODY>

<H3>Lime Jello Marshmallow Cottage Cheese Surprise</H3>

My grandma’s favorite (may she rest in peace).

<H4>Ingredients</H4>

<TR BGCOLOR=”#308030"><TH>Qty</TH><TH>Units</TH><TH>Item</TH></TR>

<TR><TD>1</TD><TD>box</TD><TD>lime gelatin</TD></TR>

<TR><TD>500 </TD><TD>g</TD><TD>multicolored tiny marshmallows</TD></TR>

<TR><TD>500 </TD><TD>ml</TD><TD>Cottage cheese</TD></TR>

<TR><TD></TD><TD>dash</TD><TD>Tabasco sauce(optional)</TD></TR>

</TABLE>

</BODY>

</HTML>

(обратно к тексту)
Listing 4. Программа преобразования программы из Listing 2 (XML) в Listing 3 (HTML), написанная на Рефале.

* Convert Xml file to Html file

Xh {

((Recipe) e.on) = '<HTML>'<Xh e.on> '</HTML>';

((Name) e.name) ((Description) e.descr) e.on =

'<HEAD>'

'<TITLE>'e.name '</TITLE>'

'</HEAD>'

'<BODY>'

'<H3>'e.name'</H3>'

e.descr

'</BODY>';

((Ingredients)e.on) =

'<H4>'Ingredients'<H4>'

'<TABLE>' BORDER="1">'

'<TR BGCOLOR="#308030">'

'<TH>Qty</TH> <TH>Units</TH> <TH>Item</TH> </<TR>'

'</TABLE>';

((Ingredient) ((Qty Unit(e.unit)) e.qty)

((Item e.option) e.item) ) e.on =

'<TR><TD>'e.qty'</TD>'

'<TD>'e.unit'</TD>'

'<TD>'e.item<Option e.option>'</TD>'

'</TR>'

<Xh e.on>;

= ; }

Option {

Optional('1') = '(optional)';

= ; }