Content area
XSLT is a standard rule-based programming language for expressing transformations of XML data. The language is currently in transition from version 1.0 to 2.0. In order to understand the computational consequences of this transition, we restrict XSLT to its pure tree-transformation capabilities. Under this focus, we observe that XSLT 1.0 was not yet a computationally complete tree-transformation language: every 1.0 program can be implemented in exponential time, using a DAG representation of trees. A crucial new feature of version 2.0, however, which allows node sets over temporary trees, yields completeness. We provide a formal operational semantics for XSLT programs, and establish confluence for this semantics. [PUBLICATION ABSTRACT]
Acta Informatica (2007) 43:371393 DOI 10.1007/s00236-006-0026-8
ORIGINAL ARTICLE
On the tree-transformation power of XSLT
Wim Janssen Alexandr Korlyukov Jan Van den Bussche
Received: 10 November 2005 / Revised: 10 August 2006 / Published online: 26 October 2006 Springer-Verlag 2006
Abstract XSLT is a standard rule-based programming language for expressing transformations of XML data. The language is currently in transition from version1.0 to 2.0. In order to understand the computational consequences of this transition, we restrict XSLT to its pure tree-transformation capabilities. Under this focus, we observe that XSLT 1.0 was not yet a computationally complete tree-transformation language: every 1.0 program can be implemented in exponential time, using a DAG representation of trees. A crucial new feature of version 2.0, however, which allows node sets over temporary trees, yields completeness. We provide a formal operational semantics for XSLT programs, and establish conuence for this semantics.
1 Introduction
XSLT is a powerful rule-based programming language, relatively widely used, for expressing transformations of XML data, and is developed by the W3C (World Wide Web Consortium) [2,8,18]. An XSLT program is run on an XML document as input, and produces another XML document as output. (XSLT programs are actually called stylesheets, as one of their main uses is to produce stylised renderings of the input data, but we will continue to call them programs here.)
The language is actually in a transition period: the current standard, version 1.0, is being replaced by version 2.0. It is important to understand what the new features of
Wim Janssen is a research assistant of the Fund for Scientic Research, Flanders. Alexandr Korlyukov sadly passed away shortly after we agreed to write a joint paper.
W. Janssen J. Van den Bussche (B)
Hasselt University & transnational University of Limburg, 3590 Diepenbeek, Belgium e-mail: [email protected]
A. Korlyukov Grodno State University, Grodno, Belarus
372 W. Janssen et al.
2.0 really add. In the present paper, we focus on the tree-transformation capabilities of XSLT. Indeed, XML documents are essentially ordered, node-labeled trees.
From the perspective of tree-transformation capabilities, the most important new feature is that of node sets over temporary trees. We will show that this feature turns XSLT into a computationally complete tree-transformation language. Indeed, as we will also show, XSLT 1.0 was not yet complete in this sense. Specically, any1.0 program can be implemented within exponential time in the worst case. Some programs actually express PSPACE-complete problems, because we will show that any linear-space turing machine can be simulated by an XSLT 1.0 program.
To put our results in context, we note that the designers of XSLT will most probably regard the incompleteness of their language as a feature, rather than a defect. Indeed, in the requirements document for 2.0, turning XSLT into a generalpurpose programming language is explicitly stated as a non-goal [3]. In that respect, our result on the completeness of 2.0 exposes (albeit in a narrow sense) a failure to meet the requirements!
At this point we should be a little clearer on what we mean by focusing on the tree-transformation capabilities of XSLT. As already mentioned, XML documents are essentially trees where the nodes are labeled by arbitrary strings. We make abstraction of this string content by regarding the node labels as coming from some nite alphabet. Accordingly, we strip XSLT of its string-manipulation functions, and restrict its arithmetic to arbitrary polynomial-time functions on counters, i.e., integers in the range {1, 2, ... , n} with n the number of nodes in the input tree.
We will provide a formal operational semantics for the substantial fragment of XSLT discussed in this paper. A formal semantics has not been available, although the W3C specications represent a ne effort in dening it informally. Of course we have tried to make our formalisation faithful to those specications. Our semantics does not impose an order on operations when there is no need to, and as a result the resulting transition relation is non-deterministic. We establish, however, a conuence property, so that any two terminating runs on the same input yield the same nal result. Conuence was not yet proven rigorously for XSLT, and can help in providing a formal justication for alternative processing strategies that XSLT implementations may follow for the sake of optimisation.
In closing, we remark that it is easy to see that XSLT 1.0 without restrictions on string functions or arithmetic can express all computable functions on strings (or integers). Indeed, rules in XSLT can be called recursively, and arbitrary recursion or iteration over the strings or the integers is well-known to yield computational completeness [15]. In this vein, many turing machine simulations, or simulations of computable functions on natural numbers, using XSLT with string functions (or keys) or with arithmetic, have been provided by XSLT practitioners and researchers (e.g., [19,22,26]). The proof we will give of the computational completeness of XSLT 2.0 for tree transformations also has a turing machine simulation as an ingredient, but that simulation is quite different in that it makes no use of strings or unrestricted arithmetic.1
1 The simulation was rst announced in the year 2001, on Internet forums and the Web (http://www. refal.net/~korlukov/tm/).
On the tree-transformation power of XSLT 373
Fig. 1 Adatatree
2 Data model
2.1 Data trees
Let be a nite alphabet, including the special label doc.Bya data tree we simply mean a nite ordered tree, in which the nodes are labeled by elements of .Upto isomorphism, we can describe a data tree t byastring string(t) over the alphabet extended with the two symbols { and }: if the root of t is labeled a and its sequence of top-level subtrees is t1, ... , tk,then
string(t) = a{string(t1)... string(tk)}
Thus, for the data tree shown in Fig. 1, the string representation equals
a{b{}c{a{}b{}}c{}}.
A data forest is a nite sequence of data trees. Forests arise naturally in XSLT, and for uniformity reasons we need to be able to present them as data trees. This can easily be done as follows:
Denition 1 (maketree) Let F be a data forest. Then maketree(F) is the data tree obtained by afxing a root node on top of F, and labeling this root node with doc.2
2.2 Stores and values
Let T be a supply of tree variables, including the special tree variable Input. We dene: Denition 2 A store is a nite set S of pairs of the form (x, t),where x T and t is adatatree, such that (1) Input occurs in S; (2) no tree variable occurs twice in S;and(3) all data trees occurring in S have disjoint sets of nodes.
The tree assigned to Input is called the input tree; the other trees are called the temporary trees.
Denition 3 A value over S is a nite sequence consisting of nodes from trees in S,and counters over S.Here, a counter over S is an integer in the range {1, 2, ... , n},where n is the total number of nodes in S.
Values as dened above formalise the kind of values that can be returned by XPath expressions. XPath [1,5] is a language that is used as a sublanguage in XSLT for the
2 The root node added by maketree models what is called the document root in the XPath data model [6], although we do not model it entirely faithfully, as we do not formally distinguish document nodes from element nodes. This is only for simplicity; it is no problem to incorporate this distinction in our formalism, and our technical results do not depend on our simplication.
374 W. Janssen et al.
purpose of selecting nodes from trees. But XPath expressions can also return numbers, which is useful as an aid in making node selections (e.g., the i-th child of a node, or the i-th node of the tree in preorder). We limit these numbers to counters, in order to concentrate on pure tree transformations.
3 XPath abstraction
Since the language XPath is already well understood [7,13,14,34], and its study in itself is not our focus, we will work with an abstraction of XPath, which we denote by
X . For our purposes it will sufce to divide the X -expressions in only two different types, which we denote by nodes and mixed. A value is of type nodes if it consists exclusively of nodes; otherwise it is of type mixed.
In order to dene the semantics of X , we need some denitions, which reect those from the XPath specication. Let V be a supply of value variables, disjoint from T . Denition 4 An environment over S is a nite set E of pairs of the form (x, v),where x V and v is a value over S, such that no value variable occurs twice in E. Denition 5 A context focus over S is a triple (z, i, k) where z is a node from S or a counter over S, and i and k are counters over S such that i [lessorequalslant] k. We call z the context item,ithe context position, and k the context size.
Denition 6 A context is a triple (S, E, c) where S is a store, E is an environment over S, and c is a context focus over S.
If we denote the universe of all possible contexts by Contexts, the semantics of X is now given by a partial function eval on X Contexts, such that whenever dened, eval(e, C) is a value over Cs store, in the sense of Denition 3. Moreover, this value has the same type as e.
Remark 3.1 A static type system, based on XML Schema [4,31], can be put on contexts to ensure denedness of expressions [7], but we omit that as safety is not the focus of the present paper.
In general we do not assume much from X , except for the availability of the following basic expressions, also present in real XPath:
An expression / , such that eval(/ , C) equals the root node of the input tree in Cs store.
An expression child:: , such that eval(child:: , C) is dened whenever Cs context item is a node n, and then equals the list of children of n.
Our later proofs of the computational completeness of XSLT 2.0, and computational incompleteness of 1.0, will need some additional assumptions, but again these will be mild and readily satised by real XPath.
4Syntax
In this section, we dene the syntax of a sizeable fragment of XSLT 2.0. The reader familiar with XSLT will notice that we have simplied and cleaned up the language
On the tree-transformation power of XSLT 375
Fig. 2 The surface syntax we use for XSLT. The terminal symbol expr stands for an X -expression; label stands for an element of our alphabet ; value_variable and tree_variable stand for elements of V and T , respectively; and name is self-explanatory. As usual we use * to denote repetition, ? to denote optionality, and use (and) for lexical grouping
in a few places. These modications are only for the sake of simplicity of exposition, and our technical results do not depend on them. We discuss our deviations from the real language further in Sect. 5.5.
Also, the concrete syntax of real XSLT is XML-based and rather unwieldy. For the sake of presentation, we therefore give a syntax of our own, which is non-XML, but otherwise follows the same lines as the real syntax. The grammar is shown in Fig. 2. The only typing condition we need is that in an apply-statement or in a vcopy-statement, expr must be of type nodes. Also, no two different rules can have the same name,andthe name in a call-statement must be the name of some rule. The following table shows the correspondence between our keywords and those of real XSLT.
Our syntax Real XSLTtemplate templatecons elementapply apply-templatescall call-templateforeach for-eachval variable, parameter (for XPath values)tree variable, parameter (for temporary trees, aka result-tree fragments) vcopy copy-of (for value variables) tcopy copy-of (for tree variables)if else if, choose otherwise
We will often identify a template M with its syntax tree. This tree consists of all occurrences of statements in M and represents how they follow each other and how they are nested in each other; we omit the formal denition. Observe that only cons-, foreach-, tree-, and if-statements can have children. Note also that, since a template is a sequence of statements, the syntax tree is actually a forest, i.e., a sequence of trees, but we will still call it a tree.
Variable denitions happen through val- and tree-statements. We will need the notion of a statement being in the scope of some variable denition; this is dened in the standard way as follows.
376 W. Janssen et al.
Fig. 3 Depiction of a syntax tree. The nodes in the scope of the black node are those that are striped
Denition 7 Let M be a template, and let S1 and S2 be two statements occurring in M. We say that S2 is in the scope of S1 if S2 is a right sibling of S1 in the syntax tree of M, or a descendant of such a right sibling. An illustration is in Fig. 3.
One nal denition:
Denition 8 Template M is called a subtemplate of template M if M consists of a sequence of consecutive sibling statements occurring in M.
5 Operational semantics
Fix a program P and a data tree t. We will describe the semantics of P on input t as a rewrite relation among congurations.Denition 9 A conguration consists of a template M together with a partial function that assigns a context to some of the statements of M (more precisely, the nodes of its syntax tree). The statements that have a context are called active; we require that the descendants of an inactive node are inactive too. Cons-statements are never active.
We use the following notation concerning congurations:
S denotes that S is a statement occurring in the template of conguration . If S ,then (S) = C denotes that S is active in , having context C. If M is a subtemplate of a conguration , then M itself can be taken as a conguration by inheriting all the context assignments done by . We call such a conguration a subconguration.
If M is a subconguration of ,and is another conguration, then (M ) denotes the conguration obtained from by replacing M by .
The initial conguration is dened as follows.
Denition 10 1. The initial context equals
[parenleftbig]{(Input, t)},
, (r,1,1)[parenrightbig]
where r is the root of t.2. The initial template equals the single statement apply / .3. The initial conguration consists of the initial template, whose single statement is assigned the initial context.
The goal will be to rewrite the initial conguration into a terminal template;this is a conguration consisting exclusively of cons-statements. Observe that terminal templates can be viewed as data forests; indeed, simply by removing the conss from a terminal template, we obtain the string representation of a data forest.
On the tree-transformation power of XSLT 377
Fig. 4 Semantics of if-statements; denotes the empty sequence. If under the current context C,the test expression e yields a nonempty result, the statement is replaced by its then-branch; otherwise it is replaced by its else-branch
For the rewrite relation we are going to dene, terminal congurations will be normal forms, i.e., cannot be rewritten further. If, for two congurations 0 and 1, we have 0 1 and 1 is a normal form, we denote that by 0 ! 1.The relation will be dened in such a way that if 0 is the initial conguration and 0 ! 1,then 1 will be terminal. Moreover, we will prove in Theorem 1 that each conguration 0 has at most one such normal form 1. We thus dene:
Denition 11 Given P and t,let 0 be the initial conguration and let 0 ! 1.Then the nal result tree of applying P to t is dened to be maketree(1).
In the above denition, we can indeed apply maketree, dened on data forests (Denition 1), to 1,since 1 is terminal and we just observed that terminal templates describe forests. Since terminal templates describe only the structure of a forest and not the actual identities of the nodes of the forest, the nal result tree is only determined up to isomorphism.
5.1 If-statements
If-statements are the only ones that generate control ow, so we treat them by a
separate rewrite relation if, dened by the semantic rules shown in Fig. 4.
It is not difcult to show that if
is terminating and locally conuent, whence conuent, so that every conguration has a unique normal form w.r.t. if [32]. This normal form no longer contains any active if-statements. (Quite obviously, the most efcient way to get to this normal form is to work out the if-statements top-down.) We write
if ! to denote that is the normal form of w.r.t.
Remark 5.1 Our main rewrite relation is not terminating in general. The reason why we treat if-statements separately is to avoid nonsensical rewritings such as where we execute a non-terminating statement in the else-branch of an if-statement whose test evaluates to true.
5.2 Apply-, call-, and foreach-statements
For the semantics of apply-statements, we need the following denitions. (We deviate here from real XSLT, as will be discussed in Sect. 5.5.)
Denition 12 (ruletoapply) Let C be a context, let n be a node, and let m be a name. Then ruletoapply(C, n) (respectively, ruletoapply(C, n, m)) equals the template belong-
if
.
378 W. Janssen et al.
Fig. 5 Semantics of apply-, call-, and foreach-statements. In an apply-statement, rst the expression e is evaluated under the current context, yielding a list of nodes. For each node, the rst rule that applies to it is determined, and its template is initialised so that the node in question becomes the context item. The apply-statement is then replaced by the list of initialized templates, and if-statements are worked out. The reading of the rules for call- and foreach-statements is similar
ing to the rst rule in P (respectively, with mode name equal to m) whose expr satises n eval(expr, C).
If no such rule exists, both ruletoapply(C, n) and ruletoapply(C, n, m) default to the single-statement template apply child::.Denition 13 (init) Let M be a template, and let C be a context. Then init(M, C) equals the conguration obtained from M by assigning context C to every statement in M, except for all statements in the scope of any variable denition, and all statements that are below a foreach-statement; all those statements remain inactive.
We are now ready for the semantic rule for apply-statements, shown in Fig. 5. We omit the rule for an apply-statement with a mode m: the only difference with the rule shown is that we use ruletoapply(C, ni, m).
The semantic rule for foreach-statements is very similar to that for apply-statements, and is also shown in Fig. 5.
For call-statements, we need the following denition.
Denition 14 (rulewithname) For any name, let rulewithname(name) denote the template of the rule in P with that name.
The semantic rule for a call-statement is then again shown in Fig. 5.
On the tree-transformation power of XSLT 379
5.3 Variable denitions
For a context C = (S, E, c), a value variable x, a value v, a tree variable y,and adata tree t, we denote by
C(x: v) the context obtained from C by updating E with the pair (x, v); and by C(y: t) the context obtained from C by updating S with the pair (y, t). We also dene:
Denition 15 (updateset) Let be a conguration and let S . Let M be the template underlying .Let S1, ... , Sk be the right siblings of S in M, in that order. Let j be the smallest index for which Sj is active in ; if all the Si are inactive, put j = k + 1.Then thetemplateS1 ... Sj1 is denoted by updateset( , S).Ifj = 1 then this is the empty template.
To give an example of updateset, consider the following program fragment:
template mytempl match (//) {val myvar 1 call anothertempl}
Consider further the following conguration , where every node is active:
call mytemplval anothervar 2
We have ,where equals the following: val myvar 1call anothertemplval anothervar 2
Here, the rst and third line are active nodes. So, the updateset of the rst line contains the second line, but not the third line.
We are now ready for the semantic rules for variable denitions, shown in Fig. 6.
5.4 Copy-statements
The following denitions are illustrated in Fig. 7.
Denition 16 (forest) Let S be a store, and let (n1, ... , nk) be a sequence of nodes from S.For i = 1, ... , k, let ti be the data subtree rooted at ni. Then forest((n1, ... , nk), S) equals the data forest (t1, ... , tk).
Denition 17 (ttemp) Let F be a data forest. Then ttemp(F) equals the terminal template describing F.
We also need:
Denition 18 (choproot) Let t be a data tree with top-level subtrees t1, ... , tk,inthat order. Then choproot(t) equals the data forest (t1, ... , tk).
The semantic rules for copy-statements are now shown in Fig. 8.
380 W. Janssen et al.
5.5 Discussion
The nal result of applying P to t (Denition 11) may be undened for two very different reasons. The rst, fundamental, reason is that the rewriting may be nonterminating. The second reason is that the rewriting may abort because the evaluation of an X -expression is undened, or the tree variable in a tcopy-statement is not dened
Fig. 6 Semantics of variable denitions. In a val-statement, the dening expression is evaluated under the current context, which is then updated to reect this new value for the variable being dened. The portion of the current conguration in the scope of the variable denition is determinedval-statement and if-statementsout. Thea tree-statement
Fig. 7 Illustration of Denitions 16 and 17. The store S is shown on top
Fig. 8 Semantics of copy-statements. In a vcopy-statement, the expression is evaluated in the current context, and the forest corresponding to the result is inserted in the current conguration. A tcopy-statement is similar, but now the tree to be inserted is retrieved by looking up the tree variable in the store
On the tree-transformation power of XSLT 381
in the store. This second reason can easily be avoided by a type system on X , as already mentioned in Remark 3.1, together with scoping rules to keep track of which variables are visible in the XSLT program and which variables are used in the X -expressions. Such scoping rules are entirely standard, and indeed are implemented in the XSLT processor SAXON [17].
In the same vein, we have simplied the parameter passing mechanism of XSLT, by using all variables as parameters. We allow updates of variables, whereas in real XSLT this is easily simulated using parameter passing. We have also omitted global variables. Otherwise, our formalisation covers all programming constructs of the real programming language XSLT 2.0. In fact, our mechanism for choosing the rule to apply (Denition 12) is more powerful than the one provided by XSLT, as ours is context-dependent. It is actually easier to dene that way. As already mentioned at the beginning of Sect. 4, none of our technical results depend on the modications we have made.
Finally, we note that the XSLT processor SAXON evaluates variable denitions lazily, whereas we simply evaluate them eagerly. Again, lazy evaluation could have been easily incorporated in our formalism. Some programs may terminate on some inputs lazily, while they do not terminate eagerly, but for programs that use all the variables they dene there is no difference.
5.6 Conuence
Recall that we call a rewrite relation conuent if, whenever we can rewrite a conguration 1 to 2 as well as to 3, then there exists 4 such that we can further rewrite both 2 and 3 into 4. Conuence guarantees that all terminating runs from a common conguration also end in a common conguration [32]. Since, for our rewrite relation , either all runs on some input are nonterminating, or none is, the following theorem implies that the same nal result of a program P on an input t, if dened at all, will be obtained regardless of the order in which we process active statements.
Theorem 1 Our rewrite relation is conuent.
Proof The proof is a very easy application of a basic theorem of Rosen about subtree replacement systems [30]. A subtree replacement system R is a (typically innite) set of pairs of the form ,where and are descriptions up to isomorphism of ordered, node-labeled trees, where the node labels come from some (again typically innite) set V. Let us refer to such trees as V-trees. Such a system R naturally induces a rewrite system R on V-trees: we have t R t if there exists a node n of t and apair in R such that the subtree t/n is isomorphic to ,and t is isomorphic to t(n ). Here, we use the notation t/n for the subtree of t rooted at n,and the notation t(n ) for the tree obtained from t by replacing t/n by a fresh copy of . Rosens theorem states that if R is unequivocal and closed, then R is conuent.
Unequivocal means that for each there is at most one such that is in R. The denition of R being closed is a bit more complicated. To state it, we need the notion of a residue map from to . This is a mapping r from the nonroot nodes of to sets of nonroot nodes of , such that for m r(n) the subtrees /n and /m are isomorphic. Moreover, if n1 and n2 are independent (no descendants of each other), then all nodes in r(n1) must also be independent of all nodes in r(n2).
Now R being closed means that we can assign a residue map r[, ] to every in R in such a way that for any 0 0 in R, and any node n of 0, if there exists a
382 W. Janssen et al.
pair 0/n in R, then the pair 0(n ) 0(r[0, 0](n) ) is also in R. (Here we simultaneously replace all subtrees rooted at nodes in the set r[0, 0](n) by .) Denoting the latter pair by 1 1, we must moreover have for each node p of 0 that is independent of n,that r[1, 1](p) = r[0, 0](p).
To apply Rosens theorem, we view congurations (Denition 9) as V-trees, where V = Statements (Statements Contexts).Here, Statements is the set of all possible syntactic forms of statements. So, given a conguration, we take the syntax tree of the underlying template, and label every inactive node by its corresponding statement, and every active node by its corresponding statement and its context in the congu-ration. (Since templates are sequences, we actually get V-forests rather than V-trees, but that is a minor fuss.)
Now consider the subtree replacement system R consisting of all pairs for which as dened by our semantics, where consists of a single statement S0, and the active statement being processed to get is a direct child of S0. Since our semantics always substitutes siblings for siblings, it is clear that R then coincides with our rewrite relation . Since the processing of every individual statement is always deterministic (up to isomorphism of trees), R as just dened is clearly unequivocal.
We want to show that R is closed. Thereto, we dene residue maps r[ , ] as follows.
Thecasewhere is the processing of an apply- or call-statement, is depicted in Fig. 9 (top). The node being processed is shown in black. The subtemplates to the left and right are left untouched. Referring to the notation used in Fig. 5, the newly
substituted subtemplate new is such that 1 ...k
(for call). Indeed, since we apply if
! at the end of every processing step, itself does not contain any active if-statements. We dene r = r[ , ] as follows:
For nodes n in left or right, we put r(n) := {n },where n is the corresponding node in .
For the black node b, we put r(b) :=
.
To see that the main condition for closedness is satised, we consider the various possibilities for the node n mentioned in the condition.
If n is b, we observe that b has no children, let alone active children. Consequently, by denition of R, there is no 1 1 in R with 1 = /b and thus we can put r(b) =
If n is in left,then 1 is the result of applying /n at n in (and 1 is the result of applying /n at n in ). We must show that 1 1 is in R. Thereto, it sufces to observe that 1 1 is of the form
where
left is the result of processing the statement at node n in left.Thisisindeed in R, as it again corresponds to the processing of an apply or call statement. If n is in right, we can make the same reasoning.
if
! new (for apply) or 1
if
! new
.
On the tree-transformation power of XSLT 383
Fig. 9 Illustration to the proof of Theorem 1
The closedness condition on ps is also satised, because both r[0, 0] and r[1, 1] will set r(p) to {p }.
Thecasewhere is the processing of a foreach-statement is depicted in Fig. 9 (middle). This case is analogous to the previous one. The only difference is that the black node now has descendants (M in the gure). However, because the init function (Denition 13) always leaves descendants of a foreach node inactive, the nodes in M are inactive at this time, and we can put r(n) :=
for all of them.
Thecasewhere is the processing of a val-statement is depicted in Fig. 9 (bottom). Since all nodes in the update set are inactive by denition (Denition 15), we can again put r(n) :=
for all nodes in the update set. The case of a tree-statement is similar; now the black node again has descendants, but again these are all inactive (they are all cons-statements). The case where is the processing of a copy-statement, nally, is again analogous.
6 Computational power of XSLT 2.0
As dened in Denition 11, an XSLT program P expresses a partial function from data trees to data forests, where the output forest is represented by a tree by afxing a root node labeled doc on top (Denition 1). The output is dened up to isomorphism only, and P does not distinguish between isomorphic inputs. This leads us to the following denition:
Denition 19 A tree transformation is a partial function from data trees to data trees with root labeled doc, mapping isomorphic trees to isomorphic trees.
Using the string representation of data trees dened in Sect. 2.1, we further dene:
384 W. Janssen et al.
Denition 20 A tree transformation f is called computable if the string function
f : string(t) string(f (t)) is computable in the classical sense.
Up to now, we have assumed from our XPath abstraction X only the availability of the expressions / and child:: . For our proof of the following theorem, we need to assume the availability of a few more very simple expressions, also present in real XPath:
y/, for any tree variable y, evaluates to the root of the tree assigned to y. // evaluates to the sequence of all nodes in the store (it does not matter in which order).
child:: [1] evaluates to the rst child of the context item (which should be a node). following-sibling:: [1] evaluates to the immediate right sibling of the context node, or the empty sequence if the context node has no right siblings.
the constant expression 1, and the expressions x + 1, x 1, and x = 1 for any value variable x, which should consist of a single counter. If x has the maximal counter value, then x + 1 need not be dened, and if x has value 1, then x 1 need not be dened. The test x = 1 yields any nonempty sequence for true and the empty sequence for false.
name() = a, for any a , returning any nonempty sequence if the label of the context node is a, and the empty sequence otherwise.
() evaluates to the empty sequence.
We establish:
Theorem 2 Every computable tree transformation f can be realised by a program.
Proof We can naturally represent any string s over some nite alphabet as a at data tree over the same alphabet. We denote this at tree by attree(s). Its root is labeled doc, and has k children, where k is the length of s, such that the labels of the children spell out the string s. There are no other nodes.
The proof now consists of three parts:
1. Program the transformation t attree(string(t)).2. Show that every turing machine (working on strings) can be simulated by some program working on the attree representation of strings.
3. Program the transformation attree(string(t)) t.
The theorem then follows by composing these three steps, where we simulate a turing machine for f in step 2. Note that the composition of three programs can be written as a single program, using a temporary tree to pass the intermediate results, and using modes to keep the rules from the different programs separate.
The programs for steps 1 and 3 are shown in Figs. 10 and 11. Figure. 10 is given for an alphabet consisting of two letters a and b, and Fig. 11 is given for an alphabet consisting of a single letter a (since that case already holds all the difculties). It is obvious how to generalise the programs to larger alphabets. The real XSLT versions are given in the Appendix. We point out that these programs are actually 1.0 programs, so it is only for step 2 of the proof that we need XSLT 2.0.
A real XSLT implementation of step 2 is provided on the Web [21]; here we describe the main ideas. We can represent a conguration of a turing machine A by two temporary trees left and right. At each step, variable right holds (as a at
On the tree-transformation power of XSLT 385
Fig. 10 From t to attree(string(t))
tree) the content of the tape starting at the head position and ending in the last tape cell; variable left holds the reverse of the tape portion left of the head position. To keep track of the current state of the machine, we use value variables q for each state q of A, such that at each step precisely one of these is nonempty. (This is why we need the X -expression ().) Changing the symbol under the head to an a amounts to assigning a new content to right by putting in cons a{}, followed by copies of the nodes in the current content of right, where we skip the rst one. Moving the head a cell to the right amounts to assigning a new content to left by putting in a node labeled with the current symbol, followed by copies of the nodes in the current content of left. We also assign a new content to right in the now obvious way; if we were at the end of the tape we add a new node labeled blank. Moving the head a cell to the left is simulated analogously. The only X -expressions we need here are the ones we have assumed to be available.
The simulation thus consists of repeatedly calling a big if-then-else that tests for the transition to be performed, and performs that transition. We may assume A is programmed in such a way that the nal output is produced starting from a designated state. In this way we can build up the nal output string in a fresh temporary tree and pass it to step 3.
7 Computational power of XSLT 1.0
In this section we will show that every XSLT 1.0 program can be implemented in exponential time, in sharp contrast to the computational completeness result of the previous section.
A fundamental difference between XSLT 1.0 and 2.0 is that in 1.0, X -expressions are input-only, dened as follows.
Denition 21 1. Let C = (S, E, (z, i, k)) be a context. Let the input tree in S be t.Then we call C input-only if every value appearing in E is already a value over the store
{(Input, t)},andalso (z, i, k) is like that.2. By, we mean the context ({(Input, t)}, E, (z, i, k)).So, equals C where we have removed all temporary trees.
3. Now an X -expression e is called input-only if for any input-only context C for which eval(e, C) is dened, we have eval(e, C) = eval(e,), and this must be a value over Cs input tree only.
In other words, input-only expressions are oblivious to the temporary trees in the store; they only see the input tree.
We further dene:
386 W. Janssen et al.
Fig. 11 From attree(string(t)) to t
Denition 22 An input-only X -expression e is called polynomial if for each input-only context C, the computation of eval(e, C) can be done in time polynomial in the size of Cs input tree.
We now dene:
Denition 23 A program is called 1.0 if it only uses input-only, polynomial
X -expressions.
Essentially, 1.0 programs cannot do anything with temporary trees except copy them using tcopy statements. We note that real XPath 1.0 expressions are indeed
On the tree-transformation power of XSLT 387
Fig. 12 Left adatatreeand right a DAG representation of it
input-only and polynomial; actually, real XPath 1.0 is much more restricted than that, but for our purpose we do not need to assume anything more.
In order to establish an exponential upper bound on the time-complexity of 1.0 programs, we cannot use an explicit representation of the output tree. Indeed, 1.0 programs can produce result trees of size doubly exponential in the size of the input tree. For example, using subsets of input nodes, ordered lexicographically, as depth counters, we can produce a full binary tree of depth 2n from an input tree with n nodes. Obviously a doubly exponentially long output could never be computed in singly exponential time.
We therefore use a DAG representation of trees: an old and well-known trick [28] that is also used in tree transduction [23], and that has recently found new applications in XML [10]. Formally, a DAG representation is a collection G of trees, where trees in G can have special leafs which are not labeled, and from which a pointer departs to the root of another tree in G. On condition that the resulting pointer graph is acyclic, starting from a designated root tree in G we can naturally obtain a tree by unfolding along the pointers. An illustration is shown in Fig. 12.
We establish:
Theorem 3 Let P be an 1.0 program. Then the following problem is solvable in exponential, i.e., 2nO(1) time:
Input: adatatree t
Output: a DAG representation of the nal result tree of applying P to t, or a message signaling non-termination if P does not terminate on t.
Proof We will generate a DAG representation G by applying modied versions of the semantic rules from Sect. 5. We initialise G with all the subtrees of t. These trees have no pointers. Each tree that will be added to G will be a conguration, which still has to be developed further into a nal data tree with pointers, using the same modied rules. Because we will have to point to the newly added congurations later, we identify each added conguration by a pair (name, C) where name isthenameofa template rule in P and C is a context. In the description below, whenever we say that we add a conguration to G, identied by some pair (name, C), we really mean that we add it unless a conguration identied by that same pair already exists in G.
The modications are now the following.
1. When executing an apply-statement, we do not directly insert copies of the templates belonging to the rules that must be applied (the is in Fig. 5). Rather, we
388 W. Janssen et al.
add, for i = 1, ... , k, the conguration i to G,where i
! i. We identify i by the pair (namei, Ci), with namei thenameofthe rule i comes from, and Ci = (S, E, (ni, i, k)) using the notation of Fig. 5. Moreover, in place of the apply-statement we insert a sequence of k pointer nodes pointing to (name1, C1), ... , (namek, Ck), respectively.2. When executing a call-statement call name under context C, we again do not
insert 1 (compare Fig. 5), but add the conguration 1 to G,where 1
! 1,
and identify it by the pair (name, C). We then replace the statement by a pointer node pointing to that pair.3. By making template rules from the bodies of all foreach-statements in P,we may assume without loss of generality that the body of every foreach-statement is a single call-statement. A foreach-statement is then processed analogously to apply- and call-statements.
4. As we did with foreach-statements, we may assume that the body of each tree-statement is a single call-statement. When executing a tree-statement, we may assume that the call-statement has already been turned into a pointer to some pair (name0, C0). We then assign that pair directly to y in the new context C (compare Figure 6); we no longer apply maketree.
So, in the modied kind of store we use, we assign namecontext pairs, rather than fully specied temporary trees, to tree variables.
5. Correspondingly, when executing a statement tcopy y, we now directly turn it into a pointer to the pair assigned to y.
6. Finally, when executing a vcopy-statement, we do not insert the whole forest generated by (n1, ... , nk) in the conguration (compare Fig. 8), but merely insert a sequence of k pointers to the input subtrees rooted at n1, ... , nk, respectively.
We initiate the generation of G by starting with the initial conguration as always. Processing that conguration will add the rst tree to G, which serves as the root tree of the DAG representation. When all trees in G have been fully developed into data trees with pointer nodes, the algorithm terminates. In case P does not terminate on t, however, that will never happen, and we need a way to detect nontermination.
Thereto, recall that every context consists of an environment E and a context focus c on the one hand, and a store S on the other hand. Since all X -expressions used are input-only, and thus oblivious to the store-part of a context (except for the input tree, which does not change), we are in an innite loop from the moment that there is a cycle in Gs pointer graph where we ignore the store-part of the contexts.More precisely, this happens when from a pointer node in a tree identied by (name, C1) we can follow pointers and reach a pointer to a pair (name, C2) with the same name and where C1 and C2 are equal in their (E, c)-parts. As soon as we detect such a cycle, we terminate the algorithm and signal nontermination. Note that thus the algorithm always terminates. Indeed, since only input-only X -expressions are used, all contexts that appear in the computation are input-only, and there are only a nite number of possible (E, c)-parts of input-only conguration over a xed input tree.
Let us analyse the complexity of this algorithm. Since all X -expressions used are polynomial, there is a natural number K such that each value that appears in a context is at most nK long, where n equals the number of nodes in t. Each element of such a length-nK sequence is a node or a counter over t, so there are at most (2n)nK different values. There are a constant c1 number of different value variables in P,sothereareat most ((2n)nK )c1 different environments. Likewise, the number of different context foci
if
if
On the tree-transformation power of XSLT 389
is (2n)3, so, ignoring the stores, there are in total at most (2n)3 (2n)c
different contexts, for some natural number K [greaterorequalslant] K. With a constant c2 number of different template names in P, we get a maximal number of c22nK
different congurations that can be added to G before the algorithm will surely terminate.
It remains to see how long it takes to fully rewrite each of those congurations into a data tree with pointers. A conguration initially consists of at most a constant c3 number of statements. The evaluation of X -expressions, which are polynomial, takes at most c3nK time in total. Processing an apply- or a foreach-statement takes at most c3nK modications to the conguration and to G; for the other statements this takes at most c3 such operations. Each such operation, however, involves the handling of contexts, whose stores can become quite large if treated naively. Indeed, tree-statements assign a context to a tree variable, yielding a new context which may then again be assigned to a tree variable, and so on. To keep this under control, we do not copy the contexts literally, but number them consecutively in the order they are introduced in
G. A map data structure keeps track of this numbering. The stores then consist of an at most constant c4 number of assignments of pairs (name, context number) to tree variables. As there are at most 2nK different contexts, each number is at most nK bits long. Looking up whether a given context is already in G, and if so, nding its number, takes O(log 2nK ) = O(nK ) time using a suitable map data structure.
We conclude that the processing of G takes a total time of c22nK
1nK [lessorequalslant] 2nK
O(nK ) = 2nO(1), as had to be proven.
A legitimate question is whether the complexity bound given by Theorem 3 can still be improved. In this respect we can show that, even within the limits of real XSLT 1.0, any linear-space turing machine can be simulated by a 1.0 program. Note that some PSPACE-complete problems, such as QBF-SAT [27], are solvable in linear space. This shows that the time complexity upper bound of Theorem 3 cannot be improved without showing that PSPACE is properly included in EXPTIME (a famous open problem).
The simulation gets as input a at tree representing an input string, and uses the n child nodes to simulate the n tape cells. For each letter a of the tape alphabet, a value variable cella holds the nodes representing the tape cells that have an a. A value variable head holds the node representing the cell seen by the machines head. The machines state is kept by additional value variables stateq for each state q, such that stateq is nonempty iff the machine is in state q. Writing a letter in a cell, moving the head left or right, or changing state, are accomplished by easy updates on the value-variables, which can be expressed by real XPath 1.0 expressions. Choosing the right transition is done by a big if-then-else statement. Successive transitions are performed by recursively applying the simulating template rule until a halting state is reached.
Remark 7.1 A nal remark is that our results imply that XSLT 1.0 is not closed under composition. Indeed, building up a tree of doubly exponential size (as we already remarked is possible in XSLT 1.0), followed by the building up of a tree of exponential size, amounts to building up a tree of triply exponential size. If that would be possible by a single program, then a DAG representation of a triply exponentially large tree would be computable in singly exponential time. It is well known, however, that a DAG representation cannot be more than singly exponentially smaller than
390 W. Janssen et al.
the tree it represents.3 Closure under composition is another sharp contrast between XSLT 1.0 and 2.0, as the latter is indeed closed under composition as already noted in the proof of Theorem 2.
8 Conclusions
W3C recommendations such as the XSLT specications are no Holy scriptures. Theoretical scrutinising of W3C work, which is what we have done here, can help in better understanding the possibilities and limitations of various newly proposed programming languages related to the Web, eventually leading to better proposals.
A formalisation of the full XSLT 2.0 language, with all the dirty details both concerning the language itself as concerning the XPath 2.0 data model, is probably something that should be done. We believe our work gives a clear direction how this could be done.
Note also that XSLT contains a lot of redundancies. For example, foreach-statements are eliminable, as are call-statements, and the match attribute of template rules. A formalisation such as ours can provide a rigorous foundation to prove such redundancies, or to prove correct various processing strategies or optimisation techniques XSLT implementations may use.
A formal tree transformation model denoted by TL, in part inspired by XSLT, but still omitting many of its features, has already been studied by Maneth and his collaborators [9,24]. The TL model can be compiled into the earlier formalism of macro tree transducers [12,29]. It is certainly an interesting topic for further research to similarly translate our XSLT formalisation (even partially) into macro tree transducers, so that techniques already developed for these transducers can be applied. For example, under regular expression types [16] (known much earlier under the name of recognisable tree languages), exact automated typechecking is possible for compositions of macro tree transducers, using the method of inverse type inference [25]. This method has various other applications, such as deciding termination on all possible inputs [24]. Being able to apply this method to our XSLT 1.0 formalism would improve existing analysis techniques [11,33], which are not complete.
Also Kirchner et al. have proposed a formalisation of XSLT based on rewriting[20], and used it to design an XSLT interpreter in the ELAN programming language. They follow essentially the same approach as us, thus conrming the naturalness of our formalisation (which was done independently). Kirchner et al.s formalisation is restricted to XSLT 1.0, and omits important features which we do formalise, such as modes, variables, and call-statements. They also did not prove the conuence of their rewrite system.
Acknowledgment We are indebted to Frank Neven for his initial participation in this research.
n log n
3 Indeed, the size of the tree represented by a DAG of n nodes cannot be larger than nn = 2
(1) , which is singly exponential.
2nO
=
On the tree-transformation power of XSLT 391
A Real XSLT programs
A.1 Figure 10 in real XSLT
<xsl:transformxmlns:xsl="http://www.w3.org/1999/XSL/Transform"version="1.0">
<xsl:template name="tree2string" match="//*"><xsl:if test="name()=a">
<a/></xsl:if><xsl:if test="name()=b">
<b/></xsl:if><lbrace/><xsl:apply-templates select="child::*"/><rbrace/></xsl:template>
</xsl:transform>
A.2 Figure 11 in real XSLT
<xsl:transformxmlns:xsl="http://www.w3.org/1999/XSL/Transform"version="1.0">
<xsl:template match="/doc">
<xsl:apply-templates select="child::*[1]"/></xsl:template>
<xsl:template name="string2tree" match="/doc//*">
<a>
<xsl:apply-templates select="following-sibling::*[1]" mode="dochildren"/></a><xsl:call-template name="searchnextsibling">
<xsl:with-param name="counter" select="1"/></xsl:call-template></xsl:template>
<xsl:template match="//*" mode="dochildren">
<xsl:if test="name()=lbrace">
<xsl:apply-templates select="following-sibling::*[1]" mode="dochildren"/></xsl:if><xsl:if test="name()=a">
<xsl:call-template name="string2tree"/></xsl:if>
392 W. Janssen et al.
</xsl:template>
<xsl:template name="searchnextsibling" match="//*" mode="search"><xsl:param name="counter"/><xsl:if test="name()=lbrace">
<xsl:apply-templates select="following-sibling::*[1]" mode="search">
<xsl:with-param name="counter" select="$counter + 1"/></xsl:apply-templates></xsl:if><xsl:if test="name()=a">
<xsl:apply-templates select="following-sibling::*[1]" mode="search">
<xsl:with-param name="counter" select="$counter"/></xsl:apply-templates></xsl:if><xsl:if test="name()=rbrace">
<xsl:if test="$counter=2">
<xsl:apply-templates select="following-sibling::*[1]"mode="dochildren"/></xsl:if><xsl:if test="$counter>2">
<xsl:apply-templates select="following-sibling::*[1]" mode="search">
<xsl:with-param name="counter" select="$counter - 1"/></xsl:apply-templates></xsl:if></xsl:if></xsl:template>
</xsl:transform>
References
1. XML path language (XPath) version 1.0. W3C Recommendation, November (1999)2. XSL transformations (XSLT) version 1.0. W3C Recommendation, November (1999)3. XSLT requirements version 2.0. W3C Working Draft, February (2001)4. XML schema. W3C Recommendation, October (2004)5. XML path language (XPath) version 2.0. W3C Working Draft, April (2005)6. XQuery 1.0 and XPath 2.0 data model. W3C Working Draft, April (2005)7. XQuery 1.0 and XPath 2.0 formal semantics. W3C Working Draft, June (2005)8. XSL transformations (XSLT) version 2.0. W3C Working Draft, April (2005)9. Bex, G.J., Maneth, S., Neven, F.: A formal model for an expressive fragment of XSLT. Informat. Syst. 27(1), 2139 (2002)
10. Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: Freytag, J.C., Lockemann, P.C., et al. (eds.) Proceedings 29th International Conference on Very Large Data Bases, pp. 141152, Morgan Kaufmann (2003)
11. Dong, C., Bailey, J.: Static analysis of XSLT programs. In: Schewe, K.D., Williams, H.E., (eds.) Database TechnologiesProceedings ADC 2004, pp. 151160 Australian Computer Society (2004)
12. Engelfriet, J., Vogler, H.: Macro tree transducers. J. Comput. Syst. Sci. 31(1), 71146 (1985)13. Gottlob, G., Koch, C., Pichler, R.: XPath processing in a nutshell. SIGMOD Rec. 32(2), 2127 (2003)
14. Hidders, J., Paredaens, J., Vercammen, R., et al.: A light but formal introduction to XQuery. In: Bellahsne, Z., Milo, T., Rys, M., et al. (eds.) Database and XML TechnologiesProceedings XSym. Lecture Notes in Computer Science, vol. 3186, pp. 520. Springer, Berlin Heidelberg New York (2004)
On the tree-transformation power of XSLT 393
15. Hopcroft, J.E., Ullman, J.E.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA (1979)
16. Hosoya, H., Pierce, B.C.: XDuce: A statically typed XML processing language. ACM Trans. Internet Technol. 3(2), 117148 (2003)
17. Kay, M.: SAXON: The XSLT and XQuery processor. http://saxon.sourceforge.net
18. Kay, M.: XSLT 2.0 Programmers Reference. Wrox, 3rd ed (2004)19. Kepser, S.: A simple proof for the turing-completeness of XSLT and XQuery. Presented at Extreme Markup Languages 2004. http://www.mulberrytech.com/Extreme/Proceedings/
20. Kirchner, C., Qian, Z., Singh, P.K., Stuber, J.: Xemantics: a rewriting calculus-based semantics of XSLT. LORIA Technical Report A01-R-386, Laboratoire Lorrain de Recherche en Informatique et ses Applications, Nancy (2001)
21. Korlyukov, A.: Turing machine for XSLT. http://www.refal.net/korlukov/tm/index.htm22. Lyons, B.: Universal turing machines in XSLT. http://www.unidex.com/turing/utm.htm23. Maneth, S.: The complexity of compositions of deterministic tree transducers. In: Agrawal, M., Seth, A., (eds.) FST TCS 2002 Proceedings, Lecture Notes in Computer Science, vol. 2556, pp. 265276. Springer, Berlin Heidelberg New York (2002)
24. Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: Proceedings 24th ACM Symposium on Principles of Database Systems, pp. 283294. ACM Press (2005)
25. Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers. J. Comput. Syst. Sci. 66(1), 6697 (2003)
26. Novatchev, D.: FXSL: The functional programming library for XSLT. http://fxsl.sourceforge.net27. Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading, MA (1994)28. Paterson, M.S., Wegman, M.N.: Linear unication. J. Comput. Syst. Sci. 16(2), 158167 (1978)29. Perst, T., Seidl, H.: Macro forest transducers. Informat. Process. Lett. 89(3), 141149 (2004)30. Rosen, B.K.: Tree-manipulating systems and Church-Rosser theorems. J. ACM 20(1), 160187 (1973)
31. Simon, J., Wadler, P.: The essence of XML. In: Proceedings 30th ACM Symposium on Principles of Programming Languages, p. 113. ACM Press (2003)
32. Terese.: Term Rewriting Systems. Cambridge University Press, Cambridge (2003)33. Trombetta, A., Montesi, D.: Equivalences and optimizations in an expressive XSLT subset. Acta Informat. 42(6), 515539 (2006)
34. Wadler, P.: A formal semantics of patterns in XSLT and XPath. Markup Langu. Theor. Pract. 2(2), 183202 (2000)
Springer-Verlag 2007