Re: [xsl] stack usage in for-each and apply-templates (was Re: [xsl] Is xsl:for-each "syntactic sugar"?)

[Dimitre Novatchev <dnovatchev@xxxxxxxxx>]

On Fri, May 7, 2010 at 10:55 AM, C. M. Sperberg-McQueen
<cmsmcq@xxxxxxxxxxxxxxxxx> 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. B If you iterate over the
> integers from 1 to 1000000 using a tail-recursive function of the
> form
>
> B (defun f (i)
> B  B  B  B ... body ...
> B  B  B  B (f (+1 i)))
>
> or
>
> B declare function f ( $i : xs:int) as xs:int {
> B  B ... body ...
> B  B if ... then
> B  B  B return $result
> B  B else
> B  B  B return f($i + 1)
> B }
>
> 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. B 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. B (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?) B 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:
>
> B <xsl:apply-templates select="first-node-of-nodeset-foo"
> B  B mode="s.w.a.b."/>
>
> B <xsl:template match="*" mode="s.w.a.b.">
> B  B <xsl:param name="accumulator" select="0"/>
>
> B  B ... body ...
>
> B  B <xsl:choose>
> B  B  B <xsl:when test="... termination condition ... ">
> B  B  B  B <xsl:value-of select="$new-accum"/>
> B  B  B </xsl:when>
> B  B  B <xsl:otherwise>
> B  B  B  B <xsl:apply-templates
> B  B  B  B  B select="next-node-of-nodeset-foo"
> B  B  B  B  B mode="s.w.a.b.">
> B  B  B  B  B  B <xsl:with-param
> B  B  B  B  B  B  B name="accumulator" select="$new-accum"/>
> B  B  B  B </xsl:apply-templates>
> B  B  B </xsl:otherwise>
> B  B </xsl:choose>
> B </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. B 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. B (In practice, when I have
> needed this pattern it has run without any trouble at all, perhaps
> because my input documents were not large. B 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. B (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
>
> B <xsl:for-each select="foo">
> B  B ... body ...
> B </xsl:for-each>
>
> the equivalent apply-templates construction does not resemble the
> s.w.a.b. example above, but instead has
>
> B <xsl:apply-templates select="foo" mode="unique-mode-id"/>
>
> and elsewhere
>
> B <xsl:template match="*" mode="unique-mode-id">
> B  B <!--* or match="@*|/|node()" if you like, but let's
> B  B  B  B * assume we are matching only elements
> B  B  B  B *-->
> B  B ... body ...
> B </xsl:template>
>
> This iterates over the elements which match the select pattern, and
> the resulting stack usage will be that
>
> B a) A node-set stack frame F1 goes on the stack.
>
> B b) A node N is selected from the node set (this is done for
> B  B  each node in F1 in turn); a template T is found for the node N.
> B  B  If the node set has no nodes, or none that have yet been
> B  B  selected, then we go to step f).
>
> B c) A template frame F2 is added to the stack for the evaluation
> B  B  of template T with context node N,
>
> B d) Template T is evaluated with context node N. B Here, the
> B  B  stack may grow owing to instructions in T, just as it may grow
> B  B  in the for-each case owing to the instructions in the body of
> B  B  the for-each. B After all, they contain the same body. B Any
> B  B  stack growth caused by constructs in the body will be the same
> B  B  for for-each and for apply-templates, so that's a wash. B At the
> B  B  end of the evaluation, template frame F2 will once again be at
> B  B  the top of the stack.
>
> B e) The template frame F2 is popped from the stack, so the
> B  B  node-set frame F1 will be at the top of the stack again. B Go to
> B  B  step b).
>
> 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. B 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. B 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. B 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?). B 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
> ****************************************************************