On Fri, May 7, 2010 at 10:55 AM, C. M. Sperberg-McQueen
<cmsmcq(_at_)blackmesatech(_dot_)com> wrote:
On 6 May 2010, at 19:49 , Dimitre Novatchev wrote:
4. Favor recursive functions over xsl:for-each. (True or False)
No, Always choose iterative processing over recursion, if this is
possible. You may gain significant efficiency this way.
True.
But if we are going to allow efficiency of execution to play a role
in our choice (it's not always wrong to do so, I guess!), then in
the context of XSLT it's important to note that the choice between
for-each and apply-templates with a mode (along the lines suggested
by David Carlisle) is not a choice between iterative processing and
recursion: both constructs are iterative in XSLT.
This is just a clarification that I used the word "recursion", not
"apply-templates".
And using <xsl:apply-templates> is not automatically synonymous to recursion.
Only when we have <xsl:apply-templates> evaluated *within* a template
(that itself was instantiated explicitly or implicitly by an
<xsl:apply-templates> or <xsl:call-template>) this *may* lead to
recursion if this causes directly or indirectly the same template to
be evaluated further down the call graph.
As for the rest of the text of . M. Sperberg-McQueen's message, there
is probably nothing more to argue about -- these are wellknown facts.
Also it is a fact that not all XSLT implementations recognize/optimize
tail-recursion, so if we are writing a portable XSLT application and
want it to be efficient when processing more or less large XML
documents, we have to resort either to DVC-style recursion or to try
to avoid recursion, if possible.
--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
In imperative languages, it's different. If you iterate over the
integers from 1 to 1000000 using a tail-recursive function of the
form
(defun f (i)
... body ...
(f (+1 i)))
or
declare function f ( $i : xs:int) as xs:int {
... body ...
if ... then
return $result
else
return f($i + 1)
}
then the stack will grow as the recursion proceeeds, and in the
absence of tail-recursion optimization you are going to end up
trying to push a million stack frames onto the execution stack,
which means you are likely to run out of stack space. And in
the imperative languages I know, those are your two choices:
iterative constructs or iteration by means of tail-recursive
functions.
It's possible to write a similar style of (tail-) recursive
template in XSLT, of course. (I'm not telling D.N. anything
he doesn't know, of course.)
As far as I can tell the main reason (maybe the only reason?) to do
it is to pass some value along in a parameter that serves as a kind
of accumulator, and finally, when the recursion ends, to pass back
the accumulated value, so that the pattern I have in mind is
something like this:
<xsl:apply-templates select="first-node-of-nodeset-foo"
mode="s.w.a.b."/>
<xsl:template match="*" mode="s.w.a.b.">
<xsl:param name="accumulator" select="0"/>
... body ...
<xsl:choose>
<xsl:when test="... termination condition ... ">
<xsl:value-of select="$new-accum"/>
</xsl:when>
<xsl:otherwise>
<xsl:apply-templates
select="next-node-of-nodeset-foo"
mode="s.w.a.b.">
<xsl:with-param
name="accumulator" select="$new-accum"/>
</xsl:apply-templates>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
(The mode name 's.w.a.b.' stands for 'Scheme with angle brackets'
and is intended to amuse those readers who may find it amusing. The
rest of you can stop groaning now, please. Thank you.)
For this, you really do need tail-recursion optimization or a lot of
stack space, at least in principle. (In practice, when I have
needed this pattern it has run without any trouble at all, perhaps
because my input documents were not large. The common view seems to
be that this will always fail on anything but artificially small
examples; in reality, it has always worked for me.)
Two observations arise here:
(1) I don't know how to get the effect of the accumulator with
xsl:for-each. (But just wait for XSLT 2.1 and the xsl:iterate
instruction!)
Is it possible to do accumulator-passing in for-each?
(2) As David Carlisle has pointed out, if you take a for-each
construct of the form
<xsl:for-each select="foo">
... body ...
</xsl:for-each>
the equivalent apply-templates construction does not resemble the
s.w.a.b. example above, but instead has
<xsl:apply-templates select="foo" mode="unique-mode-id"/>
and elsewhere
<xsl:template match="*" mode="unique-mode-id">
<!--* or match="@*|/|node()" if you like, but let's
* assume we are matching only elements
*-->
... body ...
</xsl:template>
This iterates over the elements which match the select pattern, and
the resulting stack usage will be that
a) A node-set stack frame F1 goes on the stack.
b) A node N is selected from the node set (this is done for
each node in F1 in turn); a template T is found for the node N.
If the node set has no nodes, or none that have yet been
selected, then we go to step f).
c) A template frame F2 is added to the stack for the evaluation
of template T with context node N,
d) Template T is evaluated with context node N. Here, the
stack may grow owing to instructions in T, just as it may grow
in the for-each case owing to the instructions in the body of
the for-each. After all, they contain the same body. Any
stack growth caused by constructs in the body will be the same
for for-each and for apply-templates, so that's a wash. At the
end of the evaluation, template frame F2 will once again be at
the top of the stack.
e) The template frame F2 is popped from the stack, so the
node-set frame F1 will be at the top of the stack again. Go to
step b).
f) The node set frame F1 is popped from the stack.
If the node set we are concerned with has K members, then the loop
from b) to e) will be run once for each node in the node set
selected, but even without tail-recursion optimization, the stack
will grow by 1 item, not by K items. Contrast the s.w.a.b. example,
in which you do get an increase in stack depth of K frames (or in a
really naive implementation K*2, since each recursion will push both
a singleton node-set and a template frame onto the stack).
I'm assuming a fairly naive pattern of stack usage here; it's
possible to improve it in various ways. But an implementation
would have to go a long way out of its way to make a single call
to apply-templates, with a select expression matching K nodes,
increase stack depth by K instead of by 1.
There may be good reasons to use for-each. It may for example be
better optimized than an apply-templates with a mode (but if the
mode has only a single template, which matches everything, just how
slow can the processor make the search for the appropriate
template?). Some people may for example find for-each clearer
(although in my experience some programmers who find for-each
clearer are not comfortable in XSLT in the first place).
But difference in stack usage is NOT a reason to choose for-each
over apply-templates.
--
****************************************************************
* C. M. Sperberg-McQueen, Black Mesa Technologies LLC
* http://www.blackmesatech.com
* http://cmsmcq.com/mib
* http://balisage.net
****************************************************************
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail:
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--
--~------------------------------------------------------------------
XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--