РОССИЙСКИЙ НАУЧНЫЙ ЭЛЕКТРОННЫЙ ЖУРНАЛ Электронные библиотеки
2003 | Том 6 | Выпуск 2

SXML: XML-документ как S-выражение

Д.А. Лизоркин, К.Ю. Лисовский

Московский Государственный Университет,
Институт Системного Программирования РАН


Эта статья является первой в серии статей, посвященных функциональным методам обработки XML-данных, которые могут использоваться для реализации основанных на XML электронных библиотек.

В статье рассматривается SXML --- реализация XML Information Set в виде вложенных списков (S-выражений) и функциональный язык программирования Схема (Scheme), который естественным образом обрабатывает S-выражения и, таким образом, SXML. Подобный подход позволяет обойти проблему несоответствия импеданса, которая возникает во многих современных XML-приложениях, и в электронных библиотеках в частности.


1.  Введение

Текстовые форматы представления слабоструктурированных данных, такие как SGML и XML, представляют текст как упорядоченную иерархическую структуру, что делает их крайне привлекательными в контексте электронных библиотек [1].

В настоящий момент "XML-революция" может считаться состоявшимся фактом, а стремительное развитие XML-технологий в течение последних лет затронуло практически все отрасли информатики. Электронные библиотеки (ЭБ) не являются здесь исключением, и XML рассматривается как одна из ключевых технологий для построения современных электронных библиотек [2].

Предлагаемые консорциумом W3C языки обработки XML-данных, такие как XPath, XSLT, XQuery и др., не являются языками программирования общего назначения и, как правило, недостаточны для реализации законченных приложений. Большинство XML-приложений реализуется при помощи традиционных языков программирования, таких как С или Java, или скрипт-языков, например Perl, JavaScript или Python.

Комбинирование двух различных по своей природе языков (например, XPath и Java) приводит к проблеме, известной как несоответствие импеданса (impedance mismatch). Данная проблема складывается из двух аспектов:

  • Различные модели данных. Например: XPath моделирует документ как дерево, в то время как большинство языков программирования общего назначения не предоставляют такого типа данных.
  • Различные вычислительные парадигмы. Так, XSLT является функциональным языком, тогда как Java объектно-ориентированным, а Perl - процедурным.

Несоответствие импеданса приводит к необходимости использовать сложные конвертеры и интерфейсы прикладного программирования (например, DOM) для комбинирования таких двух языков.

Несоответствие импеданса может быть значительно уменьшено и даже полностью устранено при использовании для задач обработки XML-данных функционального языка Схема (Scheme):

  • Вложенные списки (S-выражения) языка Схема являются естественным представлением вложенных элементов XML. Схема представляет свой код и данные в виде многоуровневых нетипизированных списков. XML-документ, являясь иерархией вложенных друг в друга XML-элементов, может быть представлен в виде подобного многоуровневого списка (который текстуально записывается при помощи так называемых S-выражений).
  • Схема является функциональным языком, как и большинство XML-языков (XSLT, XQuery). Схема обрабатывает многоуровневые списки рекурсивным способом, что может рассматриваться как обход/трансформация дерева документа.

Схема, диалект Лиспа, получила широкое признание как скрипт-язык [3]. Это один из самых лаконичных и компактных языков, применяемых на практике: описание стандарта языка Схема [4] состоит из 40 страниц. Это язык высокого уровня, пригодный для быстрого прототипирования. Программы на Схеме, как правило, в несколько раз короче эквивалентных программ на языке C.

В данной статье рассматривается SXML --- представление XML-документа в форме S-выражения. Текстовые нотации XML и SXML довольно похожи: если говорить неформально, SXML меняет открывающие/закрывающие теги XML на открывающие/закрывающие скобки. SXML, являясь S-выражением и, следовательно, базовой структурой данных языка программирования Схема, легко и естественно обрабатывается на этом языке.

Раздел 2 обсуждает родство между XML и SXML с точки зрения рекомендации XML Information Set консорциума W3C. Раздел 3 предлагает упрощенное описание SXML-спецификации. В разделе 4 рассматриваются некоторые важные свойства формата SXML.

2.  XML, XML Information Set и SXML

XML-документ [5] имеет, в сущности, древовидную структуру. Открывающий и закрывающий теги корневого элемента заключают в себе все содержимое документа, которое может содержать другие элементы и произвольные символьные данные. Текст с парными угловыми скобками является внешним представлением XML-документа. Приложениям приходится работать с его внутренним представлением: информационным пространством (XML Information Set) или его специализированными разновидностями (такими как DOM). Такое внутреннее представление позволяет приложениям находить конкретную информацию или трансформировать XML-дерево в другое дерево.

Консорциум W3C определяет Информационное пространство XML Infoset [6] как абстрактное множество данных, которое описывает информацию, содержащуюся в правильном (well-formed) XML-документе. Информационное пространство документа состоит из информационных элементов (information items), которые обозначают элементы, атрибуты, символьные данные, команды по обработке и другие компоненты документа. Каждый информационный элемент имеет набор ассоциированных с ним свойств (properties), например, имя и идентификатор пространства имен. Значения некоторых свойств, например, "дочерний элемент" и "атрибут", --- представляют собой (упорядоченный) набор других информационных элементов. Хотя Infoset определен лишь для XML, он в значительной степени применим и для других слабоструктурированных форматов данных, в частности, HTML.

Разбор XML-документа является лишь одним из возможных способов получения набора информационных элементов XML Information Set.

Необходимо отметить, что набор информационных элементов и их свойств, определенных в спецификации XML Information Set, не является ни исчерпывающим, ни минимально необходимым. Его целью является введение целостного набора определений для использования в других спецификациях стандартов платформы XML.

Абстрактная модель XML-данных, определенная в рекомендации XML Information Set, применима к любой из XML-спецификаций консорциума W3C. Так, Document Object Model [7] может рассматриваться как интерфейс прикладного программирования (API) для работы с наборами информационных элементов XML Information Set; узлы модели данных XPath [8] могут быть получены из информационных элементов XML Information Set, и так далее. Модели данных DOM и XPath являются, таким образом, двумя конкретными реализациями XML Infoset.

Рекомендация XML Information Set не содержит никаких явных требований к структурам данных или интерфейсу доступа к ним, поэтому возможны различные интерпретации абстрактной модели XML Information Set. Например, XML Information Set удобно рассматривать как древовидную структуру данных, и термины "Information Set" и "Information Item" тогда используются в значениях, близких к "дерево" и "узел" соответственно.

Другая трактовка информационного элемента --- это интерпретация его в виде контейнера, содержащего свои свойства: текстовые строки (например, имя, идентификатор пространства имен) или другие контейнеры (например, дочерние элементы для XML-элемента). Информационное пространство в этом случае представляет собой иерархию вложенных друг в друга контейнеров. Как заметил Олег Киселев [9], подобная иерархия контейнеров, состоящих из текстовых строк и других контейнеров, очень хорошо поддается описанию в виде S-выражения; поскольку последнее определяется рекурсивно как список, члены которого --- либо атомарные значения, либо снова S-выражения. S-выражения [10] легко разбираются во внутреннее представление, подходящее для организации обхода; они также имеют простую внешнюю нотацию, которая может довольно просто составляться даже вручную.

SXML является конкретной реализацей XML Infoset в форме S-выражений. Задачей информационного пространства Infoset является представление в некоторой форме всех существенных единиц данных и их абстрактного соотношения друг с другом. SXML дает множеству контейнеров конкретную реализацию в виде S-выражений, и обеспечивает средства доступа к информационным элементам и их свойствам. SXML является "родственником" XPath и DOM, модели данных которых представляют собой две других реализации XML Infoset. Формат SXML особенно удобен для решения на Схеме таких задач как конструирование XML/HTML-документов, выполнение запросов языка XPath и трансформация деревьев.

Таким образом, XML и SXML могут рассматриваться как два синтаксически различных представления XML Information Set.

3.  Спецификация SXML

SXML есть реализация XML Infoset в виде S-выражений. Дальнейшее рассмотрение SXML в данном разделе основано на спецификации SXML [9].

Упрощенная грамматика SXML в нотации EBNF представлена на рис. 1. Нетерминал <name> -- это одиночный символ языка Схема.


[1] <TOP> ::= ( *TOP* <PI>* <Element> )
[2] <Element> ::= ( <name> <attributes-list>? <child-of-element>* )
[3] <attributes-list> ::= ( @ <attribute>* )
[4] <attribute> ::= ( <name> "value"? )
[5] <child-of-element> ::= <Element> | "character data" | <PI>
[6] <PI> ::= ( *PI* pi-target "processing instruction content string" )

Рис. 1: Упрощенная грамматика SXML


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

Рис. 2 иллюстрирует XML-элемент и его SXML-представление (удовлетворяющее продукции <Element> из рис. 1).


<WEIGHT unit="pound"> <NET certified="certified">67</NET> <GROSS>95</GROSS> </WEIGHT>

(WEIGHT (@ (unit "pound")) (NET (@ (certified)) "67") (GROSS "95") )


Рис. 2: XML-элемент (слева) и его представление в SXML (справа)


Значением атрибута обычно является строка; она может опускаться (в случае HTML) для булевского атрибута, например, атрибута "certified" на рис. 2.

Коллекция атрибутов считается полноправным информационным элементом, помеченным специальным именем @ . Символ @ не может встретиться в корректном XML-имени; поэтому список атрибутов <attributes-list> не может быть перепутан со списком, отображающим элемент. XML-документ представляет атрибуты, команды по обработке и другие мета-данные отлично от разметки элемента. Напротив, SXML представляет содержимое элемента и мета-данные однородно --- как именованные списки. Язык описания схемы XML-документа RELAX NG [11] также нацелен на то, чтобы рассматривать атрибуты настолько похожим на элементы образом, насколько это возможно. Подобное однородное рассмотрение, утверждает Джеймс Кларк [12], --- это важный фактор для упрощения языка. SXML пользуется преимуществом того факта, что каждое имя языка XML является корректным идентификатором языка Схема, но не каждый идентификатор в Схеме является корректным именем в XML. Это наблюдение позволяет нам ввести служебные имена, такие как @, *PI*, *TOP*, не беспокоясь по поводу потенциального совпадения имен. Это наблюдение также хорошо определяет соотношение между XML и SXML. XML-документ, преобразованный в SXML, может быть снова реконструирован в XML-представление, эквивалентное исходному с точки зрения XML Infoset. Более того, благодаря абстрактности модели данных Infoset и возможности ее последующей конкретизации, SXML сам является примером XML Infoset.

XML Recommendation определяет, что команды по обработке (processing instructions, PI) отличаются от элементов и текстовых данных; команды по обработке должны передаваться приложению. SXML использует узлы специально выделенного типа *PI* для представления PI. Аналогичный подход используют XPath и DOM Level 2.

В качестве примера рассмотрим простой XML-документ и его SXML-версию. Обе версии приведены на рис. 3, что позволяет наглядно продемонстрировать соответствие между вложенными тегами XML и вложенными списками SXML. Отметим, что SXML-документ несколько компактнее своего XML-аналога.


<?xml version='1.0'> <di contract="728g"> <wt refnum="345"> <delivery> <date month="6" day="01" year"2001"/> <weight>783</weight> </delivery> <vehicle type="lorry" number="A567TP99"/> </wt> <wt refnum="459"> <vehicle type="car" number="25676043"/> </wt> </di>

(*TOP* (*PI* xml "version='1.0'") (di (@ (contract "728g")) (wt (@ (refnum "345")) (delivery (date (@ (month "6") (day "1") (year "2001"))) (weight "783")) (vehicle (@ (type "lorry") (number "A567TP99")))) (wt (@ (refnum "459")) (vehicle (@ (type "car") (number "25676043")))) ) )


Рис. 3: XML-документ (слева) и его представление в SXML (справа)


SXML можно рассматривать также как абстрактное дерево разбора XML-документа (abstract syntax tree). XML-документ или любая правильно сформированная (well-formed) его часть могут быть автоматически преобразованы в соответствующий SXML-вид с помощью чисто функционального, написанного на Схеме парсера SSAX [13].

Необходимо отметить, что SXML моделирует XML во всех деталях, включая комментарии, пространства имен и внешние сущности. Эти конструкции в данной статье для простоты изложения не рассматриваются, и изложены в спецификации SXML [9].

4  Свойства SXML

Данный раздел рассматривает некоторые свойства SXML [3], следующие из его грамматики и свойств S-выражений.

4.1  SXML-документ как дерево узлов

Так как SXML-документ представляет собой древовидную структуру данных, дополнительное введение понятия SXML-узла (node) для вершин этого дерева делает возможным более однородное описание SXML-документа.

SXML-узел может быть определен на основе рассмотренной выше грамматики (рис. 1) за счет добавления единственной новой продукции --- [N] на рис. 4. Альтернативно, SXML-узел можно определить через два взаимно-рекурсивных типа данных --- продукции [N1], [N2] и [N3] на рис. 4. Во втором случае Node создается присоединением имени к левому концу списка Nodelist; Nodelist, в свою очередь, является упорядоченным списком узлов (Node).


[N] <Node> ::= <Element> | <attributes-list> | <attribute> | "character data: text string" | <TOP> | <PI>
[N1] <Node> ::= ( <name1> . <Nodelist> ) | "text string"
[N2] <Nodelist> ::= ( <Node> <Node>* )
[N3] <name1> ::= <name> | @ | *TOP* | *PI*

Рис. 4: SXML-документ как дерево узлов


Такое рассмотрение SXML подчеркивает его древовидную структуру и однородное представление информационных элементов XML Infoset в виде S-выражений языка Схема.

4.2  Элементы и атрибуты в SXML

SXML использует единообразное представление для элементов, атрибутов и других узлов, что упрощает трансформацию SXML-документов и запросы к ним. В модели данных SXML атрибуты, комментарии, команды по обработке и т.д. представляются как ординарные элементы, но со специальными именами. Это делает излишней реализацию специальных функций для работы с ними, так как к ним могут применяться обычные функции со специальными именами узлов.

Особенно удобно на практике однородное представление в SXML элементов и атрибутов [14]. Различия между элементами и атрибутами в XML достаточно размыты, выбор атрибута или элемента для представления конкретной информации является часто вопросом стиля [15] и может быть пересмотрен в дальнейшем. В SXML такое изменение структуры данных выражается как добавление (или удаление) одного уровня вложенности (а именно, списка атрибутов) и требует минимальной модификации SXML-приложений. Узел атрибута отличается от элемента в SXML лишь тем, что он вложен в список атрибутов (который также является специальным XML-узлом) и не может содержать вложенных элементов.

Например, если после реструктуризации данных вес доставленного груза, который был представлен как вложенный элемент, должен быть представлен как атрибут, то его представление

(delivery ... (weight "789"))) изменится на следующее:

(delivery (@ (weight "789")) ...)

Такое представление элементов и атрибутов упрощает реструктуризацию SXML-данных и позволяет использовать для их обработки однотипные запросы.

4.3  SXML-данные как программа на Схеме

Синтаксис языков семейства Лисп, и Схемы в частности, основан на использовании S-выражений для представления как данных, так и кода программ. Это делает возможным и удобным рассмотрение программ на Схеме как слабоструктурированных данных [16] и наоборот.

Поскольку и SXML-документ, и образующие его узлы являются S-выражениями, то они могут использоваться для представления программ языка Схема. Для этого необходимо и достаточно, чтобы первым элементом каждого из списков, образующих SXML-дерево, являлась функция. При этом остальные элементы списка будут аргументами, к которым она применяется. В соответствии с грамматикой SXML, для этого с функциями должны быть связаны имена элементов и атрибутов, а также специальные имена.

Документ или узел SXML, который соответствует этим требованиям, может рассматриваться как программа на языке Схема, и такая программа может быть вычислена, например, при помощи функции eval.

Например, если определить para и bold как функции:

(define (para . x) (cons 'p x)) (define (bold . x) (cons 'b x))

то SXML-элемент

(para "plain" (bold "highlighted") "plain")

может рассматриваться как программа, а результатом ее выполнения будет SXML-элемент:

(p "plain" (b "highlighted") "plain")

Отметим, что результатом выполнения подобной программы не обязательно должен быть SXML-элемент. Так, программа может возвращать текстовое представление исходных данных в формате XML или HTML [17], или даже выполняться для достижения побочного эффекта, такого как сохранение SXML-данных в реляционной базе данных.

5.  Заключение

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

Информация, содержащаяся в правильном XML-документе, описывается спецификацией XML Information Set. XML, DOM, модель данных XPath и пр. представляют собой различные реализации XML Infoset. В данной статье рассматривался другой пример XML Infoset --- SXML --- имеющий вид S-выражения и, следовательно, легко и естественно обрабатываемый языком Схема.

Рассмотренная технология может быть использована для построения основанных на XML электронных библиотек, в особенности "легковесных" [18].

References

[1]
Ioannis Papadakis, Vasillios Chrissikopoulos. A Digital Library Framework based on XML.
http://citeseer.nj.nec.com/543571.html

[2]
Cuneiform Digital Library Initiative to Use XML Encoding for Third Millennium Texts.
http://xml.coverpages.org/ni2001-11-06-c.html

[3]
Лисовский К. Ю. Разработка XML-приложений на языке Scheme. Программирование, выпуск 28, номер 4, 2002.
http://www.maik.rssi.ru/journals/procom.htm

[4]
Revised5 Report on the Algorithmic Language Scheme. Kelsey R., Clinger W., Rees J. (Editors). Higher-Order and Symbolic Computation, Vol. 11, No. 1, September, 1998 and ACM SIGPLAN Notices, Vol. 33, No. 9, October, 1998.
http://www.schemers.org/Documents/Standards/R5RS/

[5]
Extensible Markup Language (XML) 1.0 (Second Edition). W3C Recommendation 6 October 2000.
http://www.w3.org/TR/REC-xml

[6]
XML Information Set. W3C Recommendation 24 October 2001.
http://www.w3.org/TR/xml-infoset/

[7]
Document Object Model (DOM) Level 2 Core Specification Version 1.0. W3C Recommendation, November 13, 2000.
http://www.w3.org/TR/2000/REC-DOM-Level-2-Core-20001113

[8]
XML Path Language (XPath) Version 1.0. W3C Recommendation 16 November 1999.
http://www.w3.org/TR/xpath

[9]
Oleg Kiselyov. SXML, Revision 2.5. August 9, 2002.
http://okmij.org/ftp/Scheme/SXML.html

[10]
John McCarthy. Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I. Comm. ACM, 3(4):184-195, April 1960.
http://www-formal.stanford.edu/jmc/recursive/recursive.html

[11]
James Clark, Makoto Murata, editors. RELAX NG Specification. OASIS, 2001.
http://www.oasis-open.org/committees/relax-ng/spec-20011203.html

[12]
James Clark. The Design of RELAX NG. December 6, 2001.
http://www.thaiopensource.com/relaxng/design.html

[13]
Oleg Kiselyov. Functional XML parsing framework: SAX/DOM and SXML parsers with support for XML Namespaces and validation. September 5, 2001.
http://www.okmij.org/ftp/Scheme/SSAX.scm

[14]
A Triumph of Simplicity: James Clark on Markup Languages and XML. Dr. Dobbs Journal, July, 2001.
http://www.ddj.com/articles/2001/0107/0107e/0107e.htm

[15]
St.Laurent S. XML Elements of Style. McGraw-Hill, 2000.

[16]
Lisovsky K. Scheme program source code as a semistructured data. 2nd Workshop on Scheme and Functional Programming. Florence, September 2001.
http://kaolin.unice.fr/Scheme2001/article/lisovsky.ps

[17]
Kiselyov O. XML and Scheme. Workshop on Scheme and Functional Programming 2000, Montreal, 2000.
http://www.okmij.org/ftp/Scheme/SXML-short-paper.html

[18]
Журавлева О.В., Лисовский К.Ю., Томусяк Г.С., Томусяк Э.С. Функциональные методы обработки слабоструктурированных данных и их применение для построения электронных библиотек. Сборник трудов Третьей Всероссийской конференции по электронным библиотекам. КНЦ РАН, Петрозаводск, сентябрь 2001.
http://pair.com/lisovsky/misc/biblio/index.html

Об авторах

Д.А. Лизоркин - аспирант Московского Государственного Университета. В 2002 году защитил дипломную работу, посвященную реализации языка XML Linking Language (XLink) с помощью функциональных методов.
e-mail: lizorkin@hotbox.ru

К.Ю. Лисовский - к.т.н., консультант по информационным технологиям, старший научный сотрудник Института Системного Программирования РАН. Главная область исследовательских интересов - функциональные и логические методы обработки слабоструктурированных данных. С 1999 года участвовал в ряде исследовательских и прикладных проектов, связанных с разработкой и применением методов обрабтки XML-данных с использованием языка Схема.
e-mail: lisovsky@acm.org
http://pair.com/lisovsky/

© Д.А. Лизоркин, К.Ю. Лисовский, 2003
Последнее обновление страницы было произведено: 2003-12-09

Все предложения и пожелания по содержанию и структуре портала направляйте по адресу rdlp@iis.ru