Re: Implementing recursion (Was Re: Char node-type)

In message <200011240919.JAA29457@xxxxxxxxxxxxxxxxxxx>, David Carlisle
<davidc@xxxxxxxxx> writes
>
>> Will it not be simpler just to use SAXON -- it recognises tail
>> recursion and implements it using iteration -- therefore no stack
>> overflow will occur.
>
>But a good question is the algorithm in question tail recursive?
>If it's doing a binary cut and processing each branch with two recursive
>calls then, it isn't...

The original algorithm was, I think.  Here is the relevant named
template, and the text() template which calls it:

<!--process-string: works its way along the string s one character at a
time,
        checking to see if it is in the list of 'normal' characters and
processing
        it if it is not:
-->
<xsl:template name="process-string">
  <xsl:param name="s" select="."/>
  <xsl:variable name="rest" select="substring($s, 2)"/>
  <xsl:variable name="ch" select="substring($s, 1, 1)"/>
  <xsl:variable name="next-text" select="following-sibling::text()[1]"/>
  <xsl:choose>
    <!-- this test doesn't work, at least for the MS XSL processor,
because the
        combining character (always an entity reference) isn't part of
the same
        text() string as the character it modifies: -->
    <xsl:when test="($output-encoding='HTML') and (string-
length($rest)&gt;0) and
                                (contains($ASCII-chars-as-string, $ch))
and
                                (contains($combining-chars-as-string,
substring($rest, 1, 1)))">
      <xsl:value-of select="'combining char found'"/>
      <xsl:call-template name="process-combining-char">
        <xsl:with-param name="ch" select="$ch"/>
        <xsl:with-param name="combining-ch" select="substring($rest, 1,
1)"/>
      </xsl:call-template>
    </xsl:when>
    <!-- this variation deals with the MS problem outlined above:
    -->
    <xsl:when test="($output-encoding='HTML') and (string-length($s)=1)
and
                                (contains($ASCII-chars-as-string, $ch))
and
                                (string-length($next-text)&gt;0) and
                                (contains($combining-chars-as-string,
substring($next-text, 1, 1)))">
      <xsl:call-template name="process-combining-char">
        <xsl:with-param name="ch" select="$ch"/>
        <xsl:with-param name="combining-ch" select="substring($next-
text, 1, 1)"/>
      </xsl:call-template>
    </xsl:when>
    <xsl:when test="contains($normal-chars, $ch)"><xsl:value-of
select="$ch"/></xsl:when>
    <xsl:otherwise>
      <xsl:call-template name="process-char">
        <xsl:with-param name="ch" select="$ch"/>
      </xsl:call-template>
    </xsl:otherwise>
  </xsl:choose>
  <xsl:if test="string-length($rest) &gt; 0">
    <xsl:call-template name="process-string">
     <xsl:with-param name="s" select="$rest"/>
    </xsl:call-template>
  </xsl:if>
</xsl:template>

<xsl:template match="text()">
 <xsl:call-template name="process-string"/>
</xsl:template>

Richard.

Richard Light
SGML/XML and Museum Information Consultancy
richard@xxxxxxxxxxxxxxxxx


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