Dagaz: Вновь об XSLT

    Ранее я уже писал небольшую статью о программировании на XSLT, но она носила несколько синтетический, учебный характер. В самом деле, если кому-то вдруг и понадобиться найти одну из возможных расстановок «8 ферзей», для решения этой задачи найдётся с десяток других, более удобных, языков, чем XSLT. Я часто использую XSLT в работе, но эти примеры его использования какие-то скучные и не особо интересные. Совсем недавно я нашёл для этого языка более забавное применение. Именно об этом, а также о том «как я докатился до мысли такой» я и собираюсь рассказать. 

    Вот уже на протяжении некоторого, весьма продолжительного, времени, я буквально одержим идеей создания универсального «движка», предназначенного для разработки абстрактных логических игр (таких как Шашки, Шахматы или Го). Разумеется, я не оригинален. Подобные проекты существуют, но все они, на мой взгляд, имеют недостатки (помимо "фатального"). Впрочем, достоинств у этих разработок заметно больше и едва ли не главным является декларативность используемых описаний. Вот так, например, выглядит описание игры на языке GDL:

    (game Tic-Tac-Toe
       (board
          (tiling square)
          (size 3 3)
       )
       (win (in-a-row 3))
    )
    

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

    Мельница
    (define variables
       (let hash 0)
    )
    
    (define invariant
       (check (not-situation-repeated? hash 1 1))
    )
    
    (define goals
       (check-loss 
          (and (> mans-left 0)
               (>= 2 (count (check is-friend?))
          )
       )
       (check-loss
          (not-exists? try-moves)
       )
    )
    
    (define man-drop
       (check (decrement! mans-left))
       (check is-empty?)
       (drop-pieces Man)
       (set! unique mans-left)
       add-move
    )
    
    (define (man-move direction)
       (check (= 0 mans-left))
       (check (< flying-mans-count (count (check is-friend?))))
       (check is-friend?)
       (take-piece-to-head current-pieces)
       (check direction)
       (check is-empty?)
       (drop-pieces current-pieces)
       add-move
    )
    
    (define man-random
       (check (= 0 mans-left))
       (check (>= flying-mans-count (count (check is-friend?))))
       (check is-friend?)
       (take-piece-to-head current-pieces)
       (any
          (check is-empty?)
          (drop-pieces current-pieces)
          add-move
       )
    )
    
    (define (check-line direction)
       (check (exists?
                  (check is-friend?)
                  (add-to-zobrist-hash hash)
                  (check direction)
                  (check is-friend?)
                  (add-to-zobrist-hash hash)
                  (check direction)
                  (check is-friend?)
                  (add-to-zobrist-hash hash)
              )
       )
    )
    
    (define capturing
       (if (or (check-line strong-n) (check-line strong-e) (check-line strong-ne) (check-line strong-se))
           (any (check is-enemy?) capture)
       )
    )
    
    (game
       (title "Nine Men's Morris")
       (players White Black)
       (board
          (positions A1 A4 A7 B2 B4 B6 C3 C4 C5 D1 D2 D3 D5 D6 D7 E3 E4 E5 F2 F4 F6 G1 G4 G7)
          (link (name strong-n) (A1 A4) (A4 A7) (B2 B4) (B4 B6) (C3 C4) (C4 C5) (D1 D2) (D2 D3)
                                (D5 D6) (D6 D7) (E3 E4) (E4 E5) (F2 F4) (F4 F6) (G1 G4) (G4 G6)
          )
          (link (name weak-s)   (A4 A1) (A7 A4) (B4 B2) (B6 B4) (C4 C3) (C5 C4) (D2 D1) (D3 D2)
                                (D6 D5) (D7 D6) (E4 E3) (E5 E4) (F4 F2) (F6 F4) (G4 G1) (G6 G4)
          )
          (link (name strong-e) (A1 D1) (D1 G1) (B2 D2) (D2 F2) (C3 D3) (D3 E3) (A4 B4) (B4 C4)
                                (E4 F4) (F4 G4) (C5 D5) (D5 E5) (B6 D6) (D6 F6) (A7 D7) (D7 G7)
          )
          (link (name weak-w)   (D1 A1) (G1 D1) (D2 B2) (F2 D2) (D3 C3) (E3 D3) (B4 A4) (C4 B4)
                                (F4 E4) (G4 F4) (D5 C5) (E5 D5) (D6 B6) (F6 D6) (D7 A7) (G7 D7)
          )
          (link (name weak-ne)  (A1 B2) (B2 C3) (E5 F6) (F6 G7))
          (link (name weak-sw)  (B2 A1) (C3 B2) (F6 E5) (G7 F6))
          (link (name weak-se)  (A7 B6) (B6 C5) (E3 F2) (F2 G1))
          (link (name weak-nw)  (B6 A7) (C5 B6) (F2 E3) (G1 F2))
          (attribute (name mans-left) (players White Black) 9)
          (attribute (name flying-mans-count) 4)
       )
       (pieces
          (pre  variables)
          (pre  goals)
          (post invariant)
          (piece 
                (name Man)
                (attribute unique 0)
                (moves
                   (post capturing)
                   (man-drop)
                   (man-move strong-n) (man-move strong-nw)
                   (man-move strong-s) (man-move strong-se)
                   (man-move strong-w) (man-move strong-sw)
                   (man-move strong-e) (man-move strong-ne)
                   (man-move weak-n) (man-move weak-nw)
                   (man-move weak-s) (man-move weak-se)
                   (man-move weak-w) (man-move weak-sw)
                   (man-move weak-e) (man-move weak-ne)
                   (man-random)
                )
          )
       )
    )
    


    При всей своей декларативности, такому описанию требуется парсер и это именно та задача, которой я занимаюсь в настоящее время. Как и в Lisp-е, в этом языке практически полностью отсутствует какой бы то ни было «синтаксический сахар». Задача разбора исходного текста на лексемы тривиальна, но что делать дальше? Очевидно, что требуется какое-то внутреннее представление, предоставляющее удобный доступ к описаниям таких объектов, как доска и фигуры.

    Я долго думал над этим вопросом, пока не поймал себя на мысли, что собираюсь разрабатать упрощённый аналог XPath. Попытка разработки подобного «велосипеда» безусловно является «тревожным звоночком». В самом деле, если понадобилось что-то, ведущее себя как XPath, почему бы его и не использовать? Достаточно всего лишь преобразовать данные в XML, например следующим образом:

    XML-представление
    <r>
      <n>
        <a>define</a>
        <a>variables</a>
        <n>
          <a>let</a>
          <a>hash</a>
          <v>0</v>
        </n>
      </n>
      ...
    </r>
    


    Парсер, формирующий такое представление, чуть менее тривиален, чем рассмотренный ранее сканер (на самом деле ещё проще, если не рассматривать реализацию include). Его задача — сформировать поток SAX-событий, в порядке поступления на вход соответствующих лексем. После получения DOM-представления, задача навигации, по загруженному описанию, решается элементарно. Но есть одно «но»: для более удобной работы, желательно иметь XML-описание в незначительно отличающемся формате:

    Преобразованное XML-представление
    <r>
      <define>
        <variables/>
        <let>
          <hash/>
          <v>0</v>
        </let>
      </define>
      ...
    </r>
    


    Здесь, жизнь вносит свои коррективы. В приведённом мной выше исходном тексте, можно видеть такие строки как "decrement!", "is-empty?" или ">=" и это явно не те «идентификаторы», которые можно помещать в имена XML-тэгов. После некоторого размышления, я решил размещать их в атрибутах, следующим образом:

    Скорректированное XML-представление
    <r>
      <n t="define">
        <n t="variables"/>
        <n t="let">
          <n t="hash"/>
          <v>0</v>
        </n>
      </n>
      ...
    </r>
    


    Конечно, такая запись куда менее интуитивна, но ведь она не для человека предназначена! Как получить такую форму? Можно переписать парсер… Но есть способ проще! Для преобразования XML из одной формы в другую, предназначен XSLT. Его мы и используем. Можно видеть, что это очень простое преобразование (во всяком случае, изменения в исходном коде парсера выглядели бы куда менее очевидными). Загрузка же из SAX в DOM с попутно выполняемой трансформацией мало чем отличается от такой же загрузки без неё.

    Аппетит приходит во время еды. Там где есть одна трансформация можно выполнить и несколько. Достаточно просто объединить их в "конвейер". Для чего могут понадобиться дополнительные преобразования? Да для чего угодно! В ZRF, например, имеется замечательная возможность. Один файл может содержать описания сразу нескольких похожих друг на друга игр, различающихся лишь деталями. При этом имеется одно главное описание "game" и несколько наследующих его "variant":

    Вариант Мельницы
    (variant
       (title "Three Men's Morris")
       (board
          (grid (dimensions "A_C" "3_1")
                (direction (name strong-n)  0 -1)
                (direction (name weak-s)    0  1)
                (direction (name strong-e)  1  0)
                (direction (name weak-w)   -1  0)
          )
          (link (name strong-ne) (A1 B2) (B2 C3))
          (link (name weak-sw)   (B2 A1) (C3 B2))
          (link (name strong-se) (A3 B2) (B2 C1))
          (link (name weak-nw)   (B2 A3) (C1 B2))
          (attribute (name mans-left) (players White Black) 3)
       )
    )
    


    Требуется описать лишь те объекты, которые изменились. Остальное будет унаследовано от единственного в файле тэга game. Вот трансформация, реализующая эту «магию». Идея преобразования проста. Раскрывая очередной variant, мы создаём переменную, содержащую как подтэги как самого тэга variant, так и соответствующего ему тэга game (порядок следования подтэгов значения не имеет):

    <xsl:variable name="u">
      <xsl:copy-of select="n"/>
      <xsl:copy-of select="/r/n[*[position()=1 and name()='a']='game']/n"/>
    </xsl:variable>
    

    Далее просто убираем дубликаты:

    <xsl:for-each select="exsl:node-set($u)/n">
      <xsl:variable name="pos" select="position()"/>
      <xsl:if test="$pos=1 or not(*[position()=1 and name()='a'] = preceding-sibling::n/*[position()=1 and name()='a'])">
        <xsl:copy-of select="."/>
      </xsl:if>
    </xsl:for-each>
    

    Единственное, о чем здесь следует помнить, это то, что, по спецификации XSLT 1.0, «фрагмент результирующего дерева», сохраненный в переменную, нельзя использовать напрямую (кроме тривиальных случаях использования в copy-of). Необходимо использовать функцию расширения node-set, для преобразования его в набор узлов.

    Можно создать и ещё более изощренное оружие для борьбы с «копипастом». Эта трансформация посложнее. Мне удалось реализовать её правильно лишь с третьей попытки, но результат того стоил. Дело в том, что в ZRF ключевое слово define определяет, по сути, макрос, который можно встроить абсолютно в любое место описания. Иногда это бывает очень удобно и спасает от большого объема писанины. В макросах ZRF можно использовать параметры $1, $2 и т.д. Мы сделаем лучше! Наши параметры будут иметь нормальные имена:

    (macro (plus a b)
      (+ a b)
    )
    
    (plus (* 2 3) (* 5 6))
    

    После выполнения преобразования macro.xsl, в исходном коде получим следующее:

    (+ (* 2 3) (* 5 6))
    

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

    XSLT может быть применено и для более сложных преобразований исходного кода. Трансформации, преобразующая описание игры на языке GDL или ZRF в исходный код Dagaz должны получиться сложными, но в них нет ничего фантастического. При желании, можно реализовать даже макросы PREZRF (впрочем, думаю, что это уже лишнее). Таким образом, XSLT обеспечит обратную совместимость, без необходимости непосредственной обработки устаревших (с точки зрения Dagaz) форматов. Не удастся обеспечить лишь поддержку формата описаний Axiom, но лишь по той причине, что это потребовало бы реализации в XSLT-преобразовании полноценной Forth-машины.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 3

      +1
      Не сочтите за критику, но можно вопрос: А xlst преобразования в данном случае реально вам необходимы для задачи или просто для тренировки навыков и демонстрации xlst в статье? Просто я не заметил критичной причины, почему нельзя в данной задаче было сразу написать парсер в нужный формат xml, раз вы все равно уже парсер писали (и по сложности написания парсеры не сильно бы на мой взгляд отличались, но возможно я просто не увидел чего-то что нельзя сделать/или сложно сделать только с помощью парсера...). Но если вас интересовала именно тренировка работы с xlst, тогда вопрос снимается.
        +1
        Да нет, вопрос на самом деле хороший. В идеале хочется видеть преобразование из ZRF и GDL. Это трудозатратно, но если возложить эту задачу на Java-код изменениями в парсере дело не ограничится (там логика сильно отличается и её трогать не хочется). Те преобразования которые уже есть, реализовать в парсере в общем то просто, но это без нужды усложнило бы его логику. Вообще мне нужен был XPath, а XSLT я рассматриваю как бонус, позволяющий решать задачи метапрограммирования. Не очень удобный, но «бесплатный». Проблема может возникнуть на мобильных платформах, поскольку Xalan весит не так уж мало. Там придется делать упрощенное внутреннее представление вместо DOM и отказаться от любых преобразований (в том числе от совместимости с ZRF и GDL). Это, в любом случае, задача не близкая.
        0
        Хочется верить, что XSLT станет несколько популярнее с появлением специального вычислительного облака под него. Там была бы поддержана лишь одна СУБД хранящая все данные в массиве xml-файлов, ну и язык поддерживался бы только один — XSLT. Язык хорош тем, что прост при всей мощности в реализации бизнес-логики, но его хочется обрамить более комфортной СУБД, ну и облачным удобством, что бы было как в Heroku или в нашем dokkur.com.
        Стараюсь реализовать это в рамках проекта «формуляр» (https://github.com/m8data/formulyar).

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое