Re: [xsl] The output of evaluating an XSLT transform is the same regardless of the order in which output elements are evaluated. Right?

["C. M. Sperberg-McQueen" <cmsmcq@xxxxxxxxxxxxxxxxx>]

On 12 Apr 2010, at 11:37 , Costello, Roger L. wrote:


> Is this statement true or false:

>  XSLT elements that produce output can be evaluated in any order.

Within some limits (some of which I'll try to identify below) and
modulo the fact that your terminology is kind of informal, the answer
is "yes, that's true."  The order of things in the result does not
depend on the temporal order in which one could see expressions being
evaluated by the XSLT processor if one could see into the processor:
the processor is free to evaluate things in any possible order.

Some of the limitations have already been mentioned in this thread.
If the value of some expression E depends on the value of some other
expression F (often but not always a sub-expression), then the nature
of that dependency is that the evaluation of E cannot finish before
the evaluation of F.


> Example: This XSLT produces two outputs:

>   <xsl:text>Hello</xsl:text>
>   <xsl:text>World</xsl:text>

> Is this statement true or false:

>   The output will always be "HelloWorld" regardless of which
>   <xsl:text> element is evaluated first.

For concreteness, I'm going to assume a context like the one suggested
by Syd Bauman for this:

 <xsl:variable name="hw">
   <xsl:text>Hello</xsl:text>
   <xsl:text>World</xsl:text>
 </xsl:variable>

There's no guarantee that the value of the variable will form part of
the output of the stylesheet, so any formulation that starts "the
output will always be ..." feels awkward: there won't always *be*
"output" in that sense.  But the string value of the variable $hw will
certainly always be "HelloWorld" regardless of whether the processor
evaluates the two xsl:text elements elder first, younger first, or in
parallel.

One limitation needs to be mentioned, because it will be making some
readers nervous along about here (if not long since): the semantics of
XSLT expressions do not allow completely arbitrary reordering of
evaluation events, and it is not always the case that for any two
constructs A and B in an XSLT stylesheet, it's possible to evaluate
them in either order, or in parallel.  The difference between XSLT
(and declarative languages generally) is that in XSLT the only
constraints are those imposed by the logical dependencies which
connect expressions.  In conventional imperative languages, it is not
unusual for the spec to prescribe an order for the evaluation of
expressions.  (The short-cut logical operators of C and other
languages are an example: their prescribed meaning involves a temporal
sequence for evaluating the subexpressions.)

But for the concrete example in question your statement is right: the
variable $hw has as its value a sequence of two text nodes: the first
has the string value "Hello" and the second the string value "World",
and this will always be the case.  And the reason it will always be
the case is that the XSLT rule for evaluating sequence constructors is
to evaluate the elements of the sequence constructor and to
concatenate the resulting sequences of items.  It is easy enough for a
processor to represent a sequence constructor as a queue, and evaluate
its elements one by one from start to end, but it's also easy to
represent the constructor as a stack and evaluate the items end to
start.  Both give the required result, both are legal.

> Is this explanation correct:

> Explanation: the outputs produced by each XSLT element is placed in
> an in-memory "result tree."

That's a well known implementation strategy (used, for example, by the
Gnome libxslt library), and can be a useful mental model of what
happens.

If you leave off the "in-memory", and take "output" loosely to mean "a
value visible in the output" (which is what I assume you do mean),
then I think this is a fairly good way to think about the simple basic
case of stylesheet processing: you're producing an output tree, and
the values obtained by evaluating XSLT constructs are placed in that
output tree, and at a suitable moment that result tree is written out.

But (a) nothing in the XSLT 1.0 or 2.0 specs requires that the final
result tree be buffered in memory, and (b) unless you take "tree" to
have a rather broad meaning, not all XSLT constructs produce trees.
(Is a sequence of integers a result tree?)  And (c) XSLT is carefully
designed so that it's easy even for simple implementations to emit the
final result tree in a streaming fashion without buffering it in
memory; it is only implementations with very strong KISS principles
(like libxslt) that materialize the final result tree in memory before
serializing it.


> Their position in the result tree depends on the sequential order of
> the outputs in the XSLT document.

True in many cases, including the $hw example above, though I would
rephrase it without the "output": The relative position of values in
the output depends -- often, but exception coming soon -- on the
relative position of the corresponding expressions in the stylesheet.

But this is not always true: if two expressions are in different
templates, and each contributes one value to a result tree, the
relative position of the values in the result tree is determined by
declarative rules (i.e. not by the temporal order of evaluation), but
not by the textual position of the two templates.

Turn it around and restrict it to siblings, and I believe it's always
true: if two sibling nodes in a stylesheet contribute one value each
to a result tree, then the order of the two values in the result tree
is the same as the order of the two expressions in the stylesheet.

You may make a lot of XSLT experts less nervous if you talk more about
expressions and values and less about outputs, perhaps.


> Thus, this XSLT element:

>   <xsl:text>World</xsl:text>

> occurs later in the XSLT document and so therefore it is placed
> later in the result tree.

Make that more concrete and say that

  The element <xsl:text>World</xsl:text> occurs later in the sequence
  constructor than the element <xsl:text>Hello</text>, and therefore
  its string value appears later in the result tree than the string
  value of its older sibling.

and it's true, I think.

Some contributors to the thread have suggested that one shouldn't
think about things like order of execution. (I don't think anyone
actually said out loud "you'll go blind if you do that", but I did get
the impression that that was in the back of their minds).  My
experience is the contrary: learning to work with declarative systems
I found it helpful to imagine as many different orders of execution as
I could, not because I was interested in trying to predict the order
in which a particular implementation would perform tasks, but
precisely because I wanted to be clear in my mind about what
properties of the sequence of events were fixed (by the language spec,
or by the logical dependencies of contructs in the code) and what
properties were not fixed.  In particular, it can be very difficult
for some programmers to break themselves of the habit of thinking of
execution order as fixed.  It's an important property of XSLT
that the sequence constructor

   <xsl:text>Hello</xsl:text>
   <xsl:text>World</xsl:text>

can be evaluated in document order -- it makes it much easier to write
a simple (naive?) processor -- but it's an equally important property
that it need not be evaluated in that order.  You are right to try to
get your head around that fact: don't let the warnings you have
received in this thread deter you from that work.  (I think some
respondents thought you were trying to do something really clever
with side effects, and were trying to warn you off.)

I hope this helps.


--
****************************************************************
* C. M. Sperberg-McQueen, Black Mesa Technologies LLC
* http://www.blackmesatech.com
* http://cmsmcq.com/mib
* http://balisage.net
****************************************************************