RE: [xsl] Re: lookup-table thoughts (was Re: matching multiple times, outputting once?

[Tom Myers <tommy@xxxxxxxxxxxxxx>]

At 02:27 PM 11/8/2001 +0000, Michael Kay wrote:
>The reason the tail-recursive version is taking longer is that each time
>round the loop, it makes a copy of the complete tree built so far. It's
>therefore not surprising that it has O(n^n) performance (not at all the same
>thing as increasing exponentially, by the way!). The non-tail-recursive
>solution creates a single temporary tree, adding nodes to it at each level
>of recursion, and never copying the tree until its final iteration.
>
>As for the divide-and-conquer algorithm, it looks interesting and performs
>well, but as it produces completely different output from the other two, I
>can't quite see the relevance.

I assume that "O(n^n)" above is a typo for "O(n^2)" = "O(n*n)", right?
Quadratic. Let me just check that I understand this from Saxon's point of
view...I'm trying to come up with a simple moral to the tale, something 
like "recursion inside constructors should not usually be made into tail 
recursions, but other recursions should be", to go along with "accumulations
of associative functions can usually be made into divide-and-conquer
templates" and other such rules that I often find helpful. Simplifying Jeni's 
templates slightly, I do a constructor recursion like so:

  consRec(N) =  [],                      if N=0
                cons("X", consRec(N-1))  otherwise

<xsl:template name="consRec">
   <xsl:param name="N" select="100"/>
   <xsl:if test="$N">
      <X>
        <xsl:call-template name="consRec">
          <xsl:with-param name="N" select="$N - 1"/>
        </xsl:call-template>
      </X>
   </xsl:if>
</xsl:template>

and if called by <xsl:call-template name="consRec"/> it will generate 100
nested X-tags, the innermost being empty, and Saxon will do this in O(n)
time, O(n) stack space, and O(n) heap space -- whereas a lazy implementation
would still need O(n) time and O(n) heap space but O(1) stack space, since
it would return the top of the tree without waiting for the bottom. This is
not, however, an argument for a lazy evaluator, since actual tree-depth
is rarely a limiting factor in recursion. Anyway, to do this tail-recursively 
we do need an accumulator:

   tailRec(N,A) = A, if N=0
                  = tailRec(N-1,cons("X",A)) otherwise

<xsl:template name="tailRec">
   <xsl:param name="N" select="100"/>
   <xsl:param name="A" select="/.."/>
   <xsl:choose>
     <xsl:when test="not($N)"><xsl:copy-of select="$A"/></xsl:when>
     <xsl:otherwise>
       <xsl:call-template name="tailRec">
          <xsl:with-param name="N" select="$N - 1"/>
          <xsl:with-param name="A">
           <X><xsl:copy-of select="$A"/></X>
          </xsl:with-param>
       </xsl:call-template>
    </xsl:otherwise>
   </xsl:choose>
</xsl:template>

And Saxon will do this in O(n^2) time, O(1) stack space, and O(n) max
heap requirement but O(n^2) total heap allocation, whereas if you 
could somehow replace "copy-of" with "reference-to", using the fact
that the accumulator $A is only used once on any computation path,
then you'd have O(n) time, O(1) stack, O(n) max heap.

My main question is "hey, is this right for Saxon?" but I'd like to
know also -- is such a replacement of "copy-of" with something like
"reference-to" possible in principle, or does it violate some XSLT
principle of which trees go where, or...?

As a distinctly stranger thought, to which you will probably not feel
like responding but Dimitre might:

You note that Jeni's divconq version doesn't generate the same output.
A divide-and-conquer equivalent is possible in languages with higher-order
functions; if we think of consX(a) = cons("X",a) as a function, then
tailRec(N) = divConq(N) = consX(consX(consX(... ([]) ...))) and we get
   divConq(N) = dC(N)([])
where
     dC(0)(a) = a 
     dC(1)(a) = consX(a) =  cons("X",a)  and so on,
in other words
     dC(0) = IdentityFunction
     dC(2*N) = compose(dC(N),dC(N))
     dC(2*N + 1) = compose(dC(N),compose(dC(N),consX));
and divConq works just like foldL and foldR (because function composition
is associative). I admit I'm thinking back to Backus' FP systems, wherein
function composition was one of the primitives (but application was not.)
I think that some of the massively-parallel proposals for implementations
of FP (or FFP) might in fact construct the N-deep tree in logarithmic time,
using linearly many processors, just about as readily as they'd construct
an N-long list the same way. But I'm not sure, not sure at all.

Tom Myers


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list