Dagaz: About XSLT Again

    Earlier, I wrote a short article on XSLT programming , but it was somewhat synthetic, educational in nature. In fact, if someone suddenly needs to find one of the possible arrangements of “8 Queens”, there are a dozen other, more convenient, languages ​​than XSLT to solve this problem. I often use XSLT in my work, but these examples of its use are kind of boring and not very interesting. More recently, I found a more fun use for this language. It’s about this, as well as about “how I got to such a thought” that I’m going to tell. 

    For some very long time now, I have been literally obsessed with the idea of ​​creating a universal “engine” designed to develop abstract logic games (such as Checkers , Chess or Go ). Of course, I'm not original. Similar projects exist , but all of them, in my opinion, have drawbacks (besides the " fatal " one). However, the advantages of these developments are noticeably greater and almost the main thing is the declarative nature of the descriptions used. Here, for example, looks like a description of the game in GDL :

    (game Tic-Tac-Toe
       (board
          (tiling square)
          (size33)
       )
       (win (in-a-row3))
    )
    

    Such a record is compact and self-sufficient. It can be used as a “raw material” for the operation of genetic algorithms that develop new types of logic games. Unlike the Ludi project , I do not set myself such a goal, but the compactness of the description will not be superfluous for me either. So, today, the description of one of the famous games in my repository looks like :

    Mill
    (define variables
       (let hash 0)
    )
    (define invariant
       (check (not-situation-repeated? hash 11))
    )
    (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)
                )
          )
       )
    )
    


    For all its declarativeness, such a description requires a parser and this is exactly the task that I am currently working on. As in Lisp , there is almost no syntactic sugar in this language. The task of parsing the source text into tokens is trivial , but what to do next? Obviously, some kind of internal representation is required, providing convenient access to descriptions of objects such as a board and figures.

    I thought about this question for a long time, until I realized that I was going to develop a simplified XPath analogue.. An attempt to develop such a "bicycle" is certainly a "wake-up call". In fact, if you needed something that behaves like XPath, why not use it? All you need is to convert the data to XML , for example as follows:

    XML representation
    <r><n><a>define</a><a>variables</a><n><a>let</a><a>hash</a><v>0</v></n></n>
      ...
    </r>


    The parser that forms this representation is slightly less trivial than the scanner considered earlier (in fact, it’s even simpler if you do not consider the include implementation ). Its task is to form a stream of SAX events, in the order of receipt of the corresponding tokens at the input. After receiving the DOM representation, the navigation task, according to the loaded description, is solved elementarily . But there is one “but”: for more convenient work, it is desirable to have an XML description in a slightly different format:

    Converted XML View
    <r><define><variables/><let><hash/><v>0</v></let></define>
      ...
    </r>


    Here, life makes its own adjustments. In the above source code, you can see lines like “ decrement! ”, “ Is-empty? ” Or “ > = ” and these are clearly not the “identifiers” that can be placed in the names of XML tags. After some thought, I decided to place them in the attributes, as follows:

    Adjusted XML View
    <r><nt="define"><nt="variables"/><nt="let"><nt="hash"/><v>0</v></n></n>
      ...
    </r>


    Of course, such a record is much less intuitive, but it is not intended for humans! How to get this form? You can rewrite the parser ... But there is a simpler way! XSLT is designed to convert XML from one form to another . We use it . You can see that this is a very simple conversion (in any case, changes in the source code of the parser would look much less obvious). Downloading from SAX to the DOM along with the transformation being performed does not differ much from the same loading without it.

    Appetite comes with eating. Where there is one transformation, you can perform several. Simply combine them into a " conveyor ". Why might additional conversions be needed? Yes for anything! In ZRF, for exampleThere is a wonderful opportunity. One file can contain descriptions of several similar games at once, differing only in details. There is one main description of " game " and several " variant " inheriting it :

    Mill Option
    (variant
       (title"Three Men's Morris")
       (board
          (grid (dimensions"A_C""3_1")
                (direction (name strong-n)  0-1)
                (direction (name weak-s)    01)
                (direction (name strong-e)  10)
                (direction (name weak-w)   -10)
          )
          (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)
       )
    )
    


    It is required to describe only those objects that have changed. The rest will be inherited from the only game tag in the file . Here is the transformation that realizes this “magic”. The idea of ​​conversion is simple. Opening the next variant , we create a variable containing both subtags of both the variant tag itself and the corresponding game tag (the sequence of subtags does not matter):

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

    Next, just remove the duplicates:

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

    The only thing to keep in mind here is that, according to the XSLT 1.0 specification, a “fragment of the resulting tree” stored in a variable cannot be used directly (except for trivial use cases in copy-of ). You must use the node-set extension function to convert it to a set of nodes.

    You can create even more sophisticated weapons to combat copy-paste. This transformation is more complicated. I managed to implement it correctly only on the third attempt, but the result was worth it. The fact is that in ZRF the define keyworddefines, in fact, a macro that can be embedded absolutely anywhere in the description. Sometimes it is very convenient and saves from a lot of writing. In ZRF macros, you can use the parameters $ 1 , $ 2 , etc. We will do better! Our parameters will have normal names:

    (macro (plus a b)
      (+ a b)
    )
    (plus (*23) (*56))
    

    After the macro.xsl conversion is completed , in the source code we get the following:

    (+ (*23) (*56))
    

    Of course, the macro itself and its arguments can be much more complex. In the body of a macro, nested macros can be called. It is not yet possible to implement a recursive macro call, but only because of the lack of a recursion stop mechanism. So far I have not found a single practical example of the use of recursive macros and embedding the ability to perform arithmetic calculations in a transformation will only complicate it, without the need.

    XSLT can also be used for more complex source code transformations. The transformations that transform the description of the game in GDL or ZRF into the Dagaz source code should be complicated, but there is nothing fantastic about them. If desired, even PREZRF macros can be implemented .(however, I think that this is already superfluous). Thus, XSLT will provide backward compatibility, without the need for direct processing of legacy (from the point of view of Dagaz ) formats. It will not be possible to provide only support for the Axiom description format , but only for the reason that this would require the full Forth machine to be implemented in the XSLT transformation .

    Also popular now: