Re: Can solve the N-queens - but can't count!

["Oren Ben-Kiki" <oren@xxxxxxxxxxxxx>]

I've spent some time thinking about what would be the required changes in
XSLT to be able to solve the issues raised by the N-queens stylesheet (and
other stylesheets, of course), but keeping XSLT side effects free (that is,
without resorting to <xsl:assign>).

I came up with the following. Using them, I modified the stylesheet (see the
attachment). It is now ~20% shorter, and much cleaner. It can't be tested at
the moment, of course, but it should be more efficient.

The extensions are:

- Allow <xsl:attribute> to have an 'expr' attribute, just like <xsl:param>
and <xsl:variable>. This is just fixing an oversight in the current draft,
really; <xsl:attribute> stands as much to gain from 'expr' as these two.

- Allow applying match patterns to variables containing result tree
fragments. The current draft explicitly forbid it, for what might be very
good reasons. For example, it might be excessively difficult to implement.
Can anyone shed some light on this?

- Support general loops. This is done in the following form (which borrows
from Sather loop syntax, and of course from tail-recursion techniques in
functional languages). Here's a sample loop:

<xsl:text>Base eight digits are: </xsl:text>
<xsl:variable name="Index" expr="0">
<xsl:loop>
    <xsl:loop-while test="not($Index = 8)"/>
    <xsl:text> </xsl:text>
    <xsl:value-of select="$Index"/>
    <xsl:loop-variable name="Index" expr="$Index + 1"/>
</xsl:loop>
<xsl:text>&#xa;</xsl:text>

Which should emit:

    Base eight digits are: 0 1 2 3 4 5 6 7

The requirements for valid loops are that:

- Every occurrence of <xsl:loop-variable> refers to an existing variable.

- All occurrences of <xsl:loop-variable> are grouped at the end of the
<xsl:loop> block, similar to <xsl:attribute> occurrences being grouped at
the start of an <xsl:element> block.

- There may be any number of calls to <xsl:loop-while> anywhere in the
<xsl:loop> block, but all before the first <xsl:loop-variable>.

Note that it is easy to convert such loops to tail-recursive form: create a
loop body template, provide it with all the loop variables as parameters,
wrap its body in cascading <xsl:if>s and add a recursive call as the last
thing at the end. In fact it should be possible to write an XSLT stylesheet
to do this transformation. So unlike the SAXONS extensions, this construct
does not undermine the side effect free nature of XSL; and yet, it is
extremely general and allows for all types of loops. For example while,
do-while, and even N+1/2 loops are easily created by placing the
<xsl:loop-while> in the appropriate position.

Is it worth it? Well, some of the goals used to limit XSLT a draft or two
back longer hold. For example, XSLT is now Turing complete and therefore
creating a tool verifying that a general XSLT stylesheet converts one DTD to
another is impossible. It is still possible to do so in special cases, of
course.

On the other hand, XSLT has not gained the full benefits of abandoning these
goals. The above loop construct, for example, does not change XSLT's
computational nature in any way; it just makes it easier to write certain
types of stylesheets.

Matching on result fragments might require a change in the nature of XSLT
processor; I'd be interested to know what James Clark or Michael Kay have to
say on this. At any rate, this feature allows a whole new type of
stylesheets. For example, streaming XSLT stylesheets become much more
feasible. One can examine a part of the input tree, extract whatever is
necessary from it, and then never look at it again, using instead just the
extracted data. This isn't possible today; modes allow us to do multiple
passes on the same input tree to extract separate data from it, but it would
be very difficult for an XSLT processor to merge such passes into a single
one for streaming.

The real question is whether we'd like XSLT to be the weakest possible to do
a certain task, or the strongest possible to be easy to use and implement.
It would have helped a lot if there was a set of "representative"
transformation tasks which XSLT was required to solve.

Share & Enjoy,

    Oren Ben-Kiki

Attachment: queens_ext.xsl
Description: Binary data