Сообщений 0    Оценка 555        Оценить  
Система Orphus

Функциональный подход к обработке XML на языке Haskell

Автор: Константин Владимиров
Источник: RSDN Magazine #1-2010
Опубликовано: 21.08.2010
Исправлено: 10.12.2016
Версия текста: 1.1
Концепции
Фильтры
Комбинаторы
Простой пример
Свойства фильтров и комбинаторов
Обработка и генерация сложных документов
Заключение
Список использованных источников

Концепции

Функциональный стиль обработки XML позволяет строить очень лаконичные и изящные программы. Одновременно с этим существует проблема недостатка материалов на русском языке по работе с XML на языке Haskell. Эта статья является попыткой обобщить опыт автора по работе с библиотекой HaXML [1, 2] и, не занимаясь переводом документации, дать читателю первоначальную базу и направление для дальнейших исследований.

Статья требует от читателя знакомства с языком Haskell, способности установить соответствующие библиотеки и настроить компилятор.

Библиотека HaXML является не единственным способом обработки XML на языке Haskell. Кроме неё на сегодняшний день существуют несколько библиотек, из которых наиболее популярны две:

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

Между XML и функциональным программированием есть некоторая связь. Прародителем HTML, а стало быть и XML был язык SGML. Язык DSSSL служивший языком описания стилей и преобразования данных в SGML-документах базировался на подмножестве функционального языка Scheme (одного из диалектов Lisp). Сейчас для обработки XML-данных принято использовать отдельный язык XSLT. Многие идеи XSLT позаимствованы из DSSSL. Точно так же и работа с древовидными структурами вполне естественна именно для функциональных языков, а любой XML- документ является древовидной структурой по определению.

Далее будут рассмотрены основные идиомы HaXML, которые на практике используются для обработки XML-документов. Важнейшими понятиями, которые совершенно нетипичны для императивного подхода (демонстрируемого, например, MSXML, libxml и прочими) являются фильтры и комбинаторы.

Фильтры

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

Тип CFilter определяется как:

      type CFilter i = Content i -> [Content i]

Здесь Content – это сложный алгебраический тип, внутренняя реализация которого имеет тенденцию меняться от версии к версии, но под которым понимается "что угодно, что может встретиться в XML", включая строки, ссылки, элементы XML и так далее.

Примерами простых для понимания и часто встречающихся в практических задачах фильтров являются:

elm – проверяет, является ли вход произвольным XML-элементом, при удаче возвращает вход.

txt – проверяет, является ли вход чистым текстом, при удаче возвращает вход.

children – проверяет, есть ли у XML-элемента потомки, при удаче – возвращает потомков.

Конструкторы фильтров имеют тип, сводимый к (a -> CFilter b), и позволяют строить фильтры для использования в программе. Например, конструктор tag, имеющий тип

tag :: String -> CFilter i

позволяет, путём частичного применения, строить фильтры вида (tag "имя_тега"), которые проверяют, является ли входной элемент XML-тегом с данным именем. Аналогично фильтр, построенный конструктором (attr "имя_атрибута") проверяет, содержится ли данный атрибут в данном теге.

Важным примером конструктора является также (?) (showAttr, содержимое атрибута). Будучи применён к имени атрибута, он возвращает из входной выборки выборку значений этого атрибута. Этот конструктор фильтров конструирует, таким образом, совершенно особый вид фильтра – модификатор или конструирующий фильтр. Он не просто возвращает часть входной выборки, а, обрабатывая вход, даёт принципиально новый результат.

Но сами по себе фильтры являются всего лишь базовыми строительными блоками, которые не слишком полезны без комбинаторов.

Комбинаторы

Ключевой концепцией в HaXML является активное использование комбинаторов. Комбинатор – это функция высшего порядка, берущая на вход другие функции, что позволяет строить даже очень сложные алгоритмы обработки из простых составных частей. В работе [3] они остроумно сравниваются с "unix pipes" – действительно есть много общего в использовании комбинаторов HaXML с привычным комбинированием команд Unix shell.

Прямо сейчас имеет смысл рассмотреть несколько важных комбинаторов с примерами.

Комбинатор `o` (Irish composition, последовательное соединение)

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

Типизация:

o :: CFilter i -> CFilter i -> Content i -> [Content i]

Пример:

attr "x" `o` attr "y"

Такой фильтр проверит наличие во входных данных обоих атрибутов "x" и "y"

Комбинатор `/>` (Slash, содержимое)

На вход последующему даёт теги, являющиеся содержимым тегов выборки предыдущего.

Типизация:

o :: CFilter i -> CFilter i -> Content i -> [Content i]

Пример:

tag "parent" /> tag "child"

Такой фильтр вернёт из входных данных данные с тегом "child", содержащиеся внутри данных с тегом "parent".

Обратите внимание на разную связность комбинаторов. Irish composition связывается слева направо, в то время как slash – справа налево.

Существует также множество других комбинаторов, общий список которых в последней версии библиотеки всегда доступен в [2]. Кроме того, каждый комбинатор является обычной функцией, определённой и определяемой в языке Haskell, а значит, заметив в своей ежедневной работе с XML некоторый паттерн, вы также можете определить свой комбинатор, расширив библиотеку.

Важная идиома составления фильтров с помощью комбинаторов может быть выражена псевдокодом:

Составной_Фильтр = Фильтр Комбинатор Фильтр Комбинатор ... Комбинатор Фильтр

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

Простой пример

На этом этапе можно рассмотреть простой пример использования базовых предикатов с комбинаторами в HaXML.

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

<letter name="A">
  <point x="0.50" y="0.10"/>
  <point x="0.45" y="0.20"/>
  <point x="0.55" y="0.20"/>
  <point y="0.8"/>
  <point x="0.40" y="0.35"/>
  <point x="0.60" y="0.35"/>
  <point x="0.30" y="0.55"/>
  <point x="0.40" y="0.55"/>
  <point x="0.50" y="0.55"/>
  <point x="0.60" y="0.55"/>
  <point x="0.70" y="0.55"/>
  <point x="0.25" y="0.70"/>
  <point x="0.75" y="0.70"/>
  <point x="0.20" y="0.80"/>
  <point x="0.80" y="0.80"/>
</letter>

Содержательная часть программы, переводящей этот файл в список элементов (x, y) на Haskell представлена ниже.

      import Text.XML.HaXml 
import Text.XML.HaXml.Posn (noPos)

contentAs :: (Read t) => (Content i) -> t
contentAs cont = read str
        where (CString _ str _) = cont
              
getList :: String -> [(Float, Float)]              
getList cont = zip xpoints ypoints
        where
          (Document _ _ root _) = xmlParse "error.log" cont
          pointFilter = attr "x" `o` attr "y" `o` (tag "letter" /> tag "point")
          rootElem = CElem root noPos
          xpoints = map (contentAs) (("x" ?) `o` pointFilter $ rootElem)
          ypoints = map (contentAs) (("y" ?) `o` pointFilter $ rootElem)

По итогам отработки getList битая точка будет проигнорирована. Если убрать проверку наличия атрибутов (attr "x" `o` attr "y"), то она будет сигнализирована исключением.

*** Exception: missing attribute:

которое достаточно информативно.

Функция contentAs является полезной абстракцией, позволяющей управлять типом, к которому приводится строчное значение атрибута через типизацию функции, из которой её вызывают (в данном случае – getList), благодаря механизму вывода типов.

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

getList :: String -> [(String, [(Float, Float)])]

чтобы она возвращала список всех букв такой конфигурации и всех их точек.

Свойства фильтров и комбинаторов

Поскольку Haskell это не только практический, но и академически-чистый язык, библиотека HaXML имеет серьёзную теоретико-алгебраическую проработку.

Два важных комбинатора, объявленных в HaXML и не упомянутых здесь ранее, поскольку имеют в основном теоретическое значение, это комбинаторы keep и none, соответствующие "комбинаторной единице" и "комбинаторному нулю", причём для любого t, keep t = [t], none t = [].

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

Для комбинаторов могут быть установлены и, вследствие функциональной чистоты, доказаны алгебраические свойства. Так например комбинатор композиции при любых селекторах f, g и h, удовлетворяет условиям:

f `o` (g `o` h) = (f `o` g) `o` h
none `o` f = f `o` none = none
keep `o` f = f `o` keep = f

Второе и третье сохраняются также для модификатора f.

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

(f `o` g) c = [c'' | c' <- g c, c'' <- f c']

Или определение в point-free стиле:

f `o` g = concat . map f . g

И далее провести доказательство по списочной индукции. Полная алгебраическая спецификация для комбинаторов HaXML приведена в [4].

Обработка и генерация сложных документов

Модифицирующие комбинаторы, хотя и представляют слабые гарантии, позволяют осуществлять эффективную обработку сложных документов. Следующий пример проиллюстрирует использование HaXML для генерации HTML кода по XML схеме. Пусть дан список гексаграмм И-Цзин в XML.

<IChing>
    <title>Some Hexagrams from the I Ching</title>
    <hexagram>
        <number>1</number>
        <name>Ch'ien / The Creative</name>
        <judgement>
            The Creative works sublime success,
            Furthering through perseverance.
        </judgement>
    </hexagram>
    <hexagram>
        <number>2</number>
        <name>K'un / The Receptive</name>
        <judgement>
            The Receptive brings about sublime success,
            Furthering through the perseverance of a mare.
        </judgement>
    </hexagram>
    <hexagram>
        <number>3</number>
        <name>Chun / Difficulty at the Beginning</name>
        <judgement>
            Difficulty at the Beginning works supreme success,
            Furthering through perseverance.
        </judgement>
    </hexagram>
</IChing>

Содержательная часть программы, которая превращает его в корректный HTML, пользуется контейнерами html, hhead, hbody и прочими. Контейнер (на примере html) это очень простая концепция с типизацией вида:

html :: [CFilter i] -> CFilter i

Список значений на входе контейнера помещается в тег, как правило, легко семантически выводимый из имени контейнера.

Конструирующий фильтр mkElemAttr и его более простая разновидность mkElem являются обобщением идеи контейнера. Они строят элемент с заданным именем и содержимым, а в случае mkElemAttr – ещё и с заданными атрибутами. Типизация говорит сама за себя:

mkElemAttr :: String -> [(String, CFilter i)] -> [CFilter i] -> CFilter i

Поскольку большая часть примитивов библиотеки HaXML не создает экземпляр класса типов Show, в модуле Text.XML.HaXml.Pretty предусмотрены функции для облегчения выдачи на экран, которые переводят их в формат Pretty-Print. В частности, ниже будет использована функция content, в документации перечислены и иные.

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

      import Text.XML.HaXml 
import Text.XML.HaXml.Posn (noPos)
import Text.XML.HaXml.Pretty (content)

getHexagrams :: String -> String
getHexagrams cont = render $ content htmline
        where
          (Document _ _ root _) = xmlParse "error.log" cont
          rootElem = CElem root noPos
          (htmline:_) = filter $ rootElem
          filter = (hexagrams `o` tag "IChing")
          hexagrams =
              html [
                hhead [htitle [keep /> tag "title" /> txt] ],
                hbody [htableBorder [rows `o` children `with` tag "hexagram"] ]
              ]
          htableBorder = mkElemAttr "TABLE" [("BORDER",("1"!))]
          rows f =
            let
              num = keep /> tag "number" /> txt
              nam = keep /> tag "name" /> txt
              jdg = keep /> tag "judgement" /> txt
            in
              hrow [hcol [num], hcol [nam], hcol [jdg]] f

Пример взят из [5] и несколько переработан, в частности для упрощения иллюстрации pretty-printing и для исключения зависимости от стандартных потоков ввода-вывода. Также очень интересный пример нетривиальной обработки документа рассмотрен в [6], он рекомендуется читателю для самостоятельного рассмотрения.

Заключение

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

Список использованных источников

  1. HaXML library page, http://www.haskell.org/HaXml/
  2. Hackage haddock-generated documentation, http://hackage.haskell.org/package/HaXml
  3. Bijan Parsia, "Functional Programming and XML", http://www.xml.com/lpt/a/2001/02/14/functional.html
  4. Malcolm Wallace, Colin Runciman, "Haskell and XML: Generic Combinators or Type-Based Translation?", http://www.haskell.org/HaXml/icfp99.html
  5. David Mertz, "XML Matters: Transcending the limits of DOM, SAX, and XSLT", http://www.ibm.com/developerworks/xml/library/x-matters14.html
  6. Koen Roelandt, "Using HaXml to clean legacy HTML pages", http://www.krowland.net/tutorials/haxml_tutorial.html


Эта статья опубликована в журнале RSDN Magazine #1-2010. Информацию о журнале можно найти здесь
    Сообщений 0    Оценка 555        Оценить