Lambda the Ultimate

inactiveTopic A Formal Model for an Expressive Fragment of XSLT
started 10/17/2002; 12:10:16 AM - last post 10/17/2002; 2:28:48 AM
jon fernquest - A Formal Model for an Expressive Fragment of XSLT  blueArrow
10/17/2002; 12:10:16 AM (reads: 1175, responses: 1)
A Formal Model for an Expressive Fragment of XSLT

A formal model of a subset of XSLT is analyzed with extensive examples. From a "language theoretic point of view" XSLT is shown to "correspond to tree-walking tree transducers with registers." Four XSLT language features are the key to its expressiveness:

...Modes enable XSLT to act differently upon arrival at the same element types ... Variables can be perform joins between data values. A less apparent application is to use them as a 'look-ahead'. ...we give a fragment of an XSLT program evaluating the truth value of a binary tree which represents a Boolean circuit. Essentially, the use of variables allows for a bottom-up computation. In brief, when arriving at an or-labeled node, the program returns the correct truth value based upon the truth values of the first and second subtree. Passing of data values to other template rules can be crucial for performing joins if the items to be joined do not occur at the same node. Moreover, when node IDs are present in the XML document, we can use this mechanism to place 'pebbles' on the input document which enables us to do complicated grouping operations... XPath can also select siblings and ancestors. Exactly these four features render XSLT into a quite powerful transformation language. (my emphasis)

A semantics of the sub-language is derived with rewrite relations and several properties of XSLT are proven:

XSLT0 [the sub-language], and hence XSLT, is quite expressive in the sense that it can simulate most other current XML query languages, and that it can express all join- free MSO [Monadic Second Order Logic] patterns. The latter even implies that XSLT is strictly more expressive than other XML query languages. On the negative side we obtain that deciding termination is undecidable and that XSLT0 is not closed under composition.

Personally, I find that concise mathematical descriptions accompanied by examples like this, that hone in on a language's key features, provide more insight into how a language works than verbose language specifications that are hard to grasp as a whole. [Neven's Publications, Interesting survey papers] (A Formal Model for an Expressive Fragment of XSLT, Bex, Maneth, and Neven, 2000)

Posted to xml by jon fernquest on 10/17/02; 12:35:08 AM

jon fernquest - Re: A Formal Model for an Expressive Fragment of XSLT  blueArrow
10/17/2002; 2:28:48 AM (reads: 574, responses: 0)
"Tree Automata Techniques and Applications" covers its subject comprehensively and is available for free online: