Язык модификации данных формата XML функциональными методами

Д.А. Лизоркин
Труды Института системного программирования РАН

Назад Содержание Вперёд

3.3.1.2. Удаление узла

Операция удаления узла удаляет из документа обрабатываемый узел и все узлы, вложенные в него. Если рассматривать документ в виде дерева, то можно говорить о том, что в данной операции происходит удаление целого поддерева, корнем которого служит обрабатываемый узел.

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

(define delete
  (lambda (node) '()))

Необходимо отметить, что в отличие от рассмотренных в предыдущем пункте обработчиков по вставке узла, обработчик для удаления узла не требует параметризации.

Пример 2   Запрос на удаление узлов на языке модификаций, выработанном в работе [11], записывается следующим образом:

UPDATE
DELETE //blood_pressure[systolic>180]

С использованием обработчика для удаления узла, эквивалентный запрос на модификацию документов формата SXML имеет на Scheme следующий вид:

(sxml:modify
 `("//blood_pressure[systolic>180]"
   ,delete))

Заметим, что по сравнению с примером 1 в выражении языка Scheme поменялся только используемый обработчик. Благодаря гибкости предлагаемого подхода замена обработчика позволяет полностью изменить эффект производимой модификации.

3.3.1.3. Замена узла новым узлом

Операция замены узла замещает обрабатываемый узел и всё его содержимое новым узлом, который задается в качестве параметра операции. Если рассматривать документ в виде дерева, то можно говорить о том, что в данной операции происходит замещение новым поддеревом целого поддерева, корнем которого служит обрабатываемый узел.

Обработчик для замены узла новым узлом во многом напоминает рассмотренные ранее обработчики для вставки узла с тем упрощением, что теперь обрабатываемый узел node полностью игнорируется, и возвращаемым значением обработчика является новый узел new-node:

(define (replace new-node)	
  (lambda (node) new-node))

Пример 3   Запрос на замену узла новым узлом на языке модификаций, разработанном в [11], имеет следующий вид:

UPDATE
REPLACE //job[.="bit banger"]	
WITH
 <profession>Comp. Scientist</profession>

С помощью предлагаемой в данной статье идеи обработчиков эквивалентный результат достигается на Scheme так:

(sxml:modify
 `("//job[.='bit banger']"	
   ,(replace
     '(profession "Comp. Scientist"))))

3.3.1.4. Переименование узла

Операция переименования узла изменяет имя узла и оставляет неизменным его содержимое.

Операция переименования осмысленна для узлов, которые обладают именами, т.е. для элементов и атрибутов. При обработке XML-данных на языке Scheme элементы и атрибуты выражаются в виде S-выражений единообразным образом, и имя всегда является первым членом S-выражения, соответствующего данному элементу или атрибуту.

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

(define (rename new-name)
  (lambda (node)
    (if (pair? node)  ; именованный узел
        (cons new-name (cdr node))
        node)))

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

Приведенное тело обработчика может быть легко дополнено функциональностью, позволяющей для узла типа “инструкция обработки” переименовывать ее указание адреса (PI target) [19], что сделает семантику рассматриваемой операции переименования узла полностью совместимой с [11].

Пример 4   Переименование узла в терминах языка модификаций [11] записывается в виде:

UPDATE
RENAME //job[.='bit banger']	
AS "profession"

С использованием предлагаемой идеи обработчиков, эквивалентный запрос на модификацию может быть записан на Scheme так:

(sxml:modify
 `("//job[.='bit banger']"	
   ,(rename 'profession)))

Здесь 'profession имеет тип данных символ, и этот тип данных используется в SXML для представления имен элементов и атрибутов.

3.2. Возможности языка Scheme по выражению операций модификации

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

В частности, конструкторы различных типов узлов реализуются на Scheme конструкторами списков. Более того, наличие в языке Scheme выражений квази-цитирования (quasiquote) и снятия цитирования (unquote) позволяет компактным и наглядным образом комбинировать константные выражения и фрагменты вычисляемых выражений [18]. Аналогичные идеи используются в синтаксисе XSLT для комбинирования литеральных элементов результата [1] и исполняемых инструкций.

Тело обработчика может включать в себя вызовы библиотеки SXPath — реализации языка XPath на Scheme, — что позволяет приложению адресоваться к структурным частям обрабатываемого SXML-документа в соответствии со взаимоотношением этих частей с обрабатываемым узлом как контекстным узлом XPath.

Примитивы map и filter языка Scheme обеспечивают приложение при работе с узлами SXML-документа возможностями итерирования и фильтрации последовательности узлов в терминах языка запросов к XML-документам XQuery. Арифметико-логические и условные выражения языка XQuery реализуются на Scheme соответствующими стандартными функциями.

Благодаря возможности использования в теле обработчика произвольного выражения языка программирования общего назначения Scheme и интегрированности Scheme с узлами SXML-документа на уровне списковых структур данных, предложенная в данной статье идея обработчиков обеспечивает приложение выразительным и мощным механизмом для определения операций модификации.

4. Зависимая обработка нескольких узлов

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

Позиционирование операции перемещения поддерева как одной из базовых операций редактирования древовидных структур данных [13] мотивирует дальнейшее расширение предлагаемой в данной статье идеи обработчиков возможностью осуществлять перемещения поддеревьев¹. Необходимо отметить, что в работе [11] операция перемещения не обеспечивается, и вместо этого предлагается имитировать ее как независимое последовательное применения операций удаления и вставки, причем никаких средств согласованного использования этих двух операций не предоставляется.

Предлагаемый в данной статье способ представления операции модификации в виде пары значений

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

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

Для обеспечения функциональности зависимой обработки двух узлов документа введем понятие базового узла.

4.1. Базовый узел

Базовым узлом для операции модификации назовем такой узел, относительно которого вычисляется выражение_XPath данной операции модификации. Поскольку при помощи выражения XPath в операции модификации выбираются обрабатываемые узлы, можно говорить о том, что базовый узел определяет те узлы, которые выбираются, и, соответственно, обрабатываются в данной операции модификации.

Как отмечалось в разделе 1, запрос на модификацию состоит, вообще говоря, из нескольких операций модификации, которые можно считать упорядоченными между собой. Считаем, что базовым узлом для первой по порядку операции модификации в данном запросе на модификацию всегда является корневой узел обрабатываемого документа. Для последующих по порядку операций модификации корневой узел обрабатываемого документа служит базовым узлом в том и только том случае, если выражение_XPath данной операции модификации является абсолютным путем доступа (absolute location path) [12]. Если в операции модификации используется выражение_XPath другого вида, например, относительный путь доступа (relative location path), то в этом случае базовым узлом последовательно считается каждый из обрабатываемых узлов предыдущей операции модификации данного запроса на модификацию.

Сформулированное правило сопоставления базового узла с конкретной операцией модификации хорошо согласуется с семантикой вычисления путей доступа в спецификации XPath: абсолютный путь доступа вычисляется относительно корневого узла документа, а относительный путь доступа — относительно контекстного узла контекста вычисления. Использование относительного пути доступа XPath в операции модификации связывает эту операцию с предыдущей, и вычисление набора узлов, подлежащих обработке, осуществляется способом, во многом напоминающем вычисление последовательности шагов доступа в языке XPath:

• рассматривается набор обрабатываемых узлов предыдущей операции модификации;

• для каждого узла из данного набора, как для базового узла, вычисляется выражение_XPath текущей операции модификации;

• получаемые в результате вычисления выражения_XPath узлы становятся обрабатываемыми узлами в текущей операции модификации.

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

Рассмотренные в разделе 3 обработчики для наиболее употребительных операций модификации могут быть очевидным образом расширены на предмет наличия в сигнатуре обработчика нового аргумента base-node. Ввиду того, что базовый узел не влияет на результаты обработчиков для обсуждавшихся в разделе 3 наиболее употребительных операций модификации, базовый узел добавляется в эти обработчики просто в качестве фиктивного параметра.

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

Функциональность зависимой обработки двух узлов, располагающихся в разнесенных местах документа, иллюстрируется в следующем подразделе реализацией упоминавшейся ранее в данном разделе операции перемещения поддерева.

4.2. Перемещение поддерева

При наличии введенного понятия базового узла перемещение поддерева может быть реализовано совокупностью двух операций модификации. На основе рассмотренной семантики вычисления нескольких операций модификации узел – корень поддерева, подлежащего перемещению, – может выступать в роли обрабатываемого узла для первой из двух операций модификации и в роли базового узла — для второй операции. Эффект перемещения поддерева достигается тогда, когда первая операция модификации удаляет свой обрабатываемый узел из документа, а вторая операция вставляет в документ свой базовый узел (являющийся обрабатываемым узлом для предыдущей операции модификации). Поскольку обе операции являются компонентами единого запроса на модификацию, влияние этих операций на обрабатываемый документ атомарно и с точки зрения реализации осуществляется за один проход по дереву документа.

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

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

Пример 5  Предположим, что электронная версия некоторой книги состоит из элементов с именем глава (chapter), и каждая глава содержит элементы с именем параграф (para). Переместим последний параграф главы, имеющей заголовок “Введение” (“Introduction”), в следующую по порядку главу в качестве ее первого параграфа.

Запрос на желаемую модификацию реализуется следующей совокупностью из двух операций модификации, связанных друг с другом посредством базового узла:

(sxml:modify
   `("/book/chapter[title='Introduction']/
       para[last()]"
     ,(lambda (node base-node) '()))
   `("following::chapter[1]/para[1]"
     ,(lambda (node base-node)
        (list base-node node))))

Первая операция модификации выбирает параграф, подлежащий перемещению, и удаляет его по месту его исходного положения. Обрабатываемый параграф, удаленный из документа первой операцией модификации, тем не менее, является базовым узлом для второй операции модификации, поскольку во второй операции модификации в качестве выражения XPath используется относительный путь доступа. Вторая операция модификации осуществляет вставку перемещаемого параграфа – базового узла base-node – перед первым по счету параграфом главы, следующей за главой с заголовком “Введение”. Совокупный эффект обоих операций модификации рассматриваемого примера обеспечивает желаемое перемещение узла.

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

5. Сокращенный синтаксис для описания модификаций

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

Для рассмотренных выше операций вставки, удаления, переименования узла и т.п. предлагается идентифицировать каждую из этих операций своим ключевым словом, которое выражается типом данных “символ” языка Scheme. Благодаря быстроте операции сравнения в Scheme двух символов [20], при перезаписи запроса на модификацию из сокращенной формы записи в полную форму введенные ключевые слова можно быстро заменить сопоставленными им обработчиками.

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

операция_модификации_в_сокращенном_синтаксисе ::=
`( ,выражение_XPath delete ) |
`(,выражение_XPath insert-following,добавляемый_узел_на_SXML)|
`(,выражение_XPath insert-preceding,добавляемый_узел_на_SXML)|
`(,выражение_XPath insert-into     ,добавляемый_узел_на_SXML)|
`(,выражение_XPath replace          ,заменяющий_узел_на_SXML)|
`(,выражение_XPath rename                    ,новое_имя_узла)|
`(,выражение_XPath move-following 
                           ,выражение_XPath-новое_место_узла)|
`(,выражение_XPath move-preceding
                           ,выражение_XPath-новое_место_узла)|
`(,выражение_XPath move-into
                           ,выражение_XPath-новое_место_узла)

Табл. 2: Сокращенный синтаксис для наиболее употребительных операций модификации

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

По сравнению с полным синтаксисом, сокращенный синтаксис обладает тем важным преимуществом, что может быть без потерь отображен на постоянное хранилище данных типа файла или на канал передачи данных, — тогда как тип данных функция, являющийся неотъемлемой частью полного синтаксиса, может существовать только во время вычисления программы, в оперативной памяти. Данное свойство сокращенного синтаксиса может быть полезно для таких областей применения предлагаемого языка модификации как генерация скрипта редактирования (edit script) в виде запроса на модификацию при определении различий между двумя деревьями [13].

---

Назад Содержание Вперёд