RE: Complex recursion in XSLT 1.0

Thanks Michael,

so I was effectively building a stack in my first transform but it was a
stack of individual filenames as individual text parameters. Perhaps if I
build a stack as a node-set I might be able to crack this one!

I read a little on Turin completeness on Wikipedia would share the following
phrase: "Thus, a machine that can act as a universal Turing machine can, in
principle, perform any calculation that any other computer is capable of.
Note, however, that this says nothing about the effort required to write a
program for the machine."

Ain't that the truth! ;-)

Richard 

-----Original Message-----
From: Michael Kay [mailto:mike@xxxxxxxxxxxx] 
Sent: 18 February 2008 13:36
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: RE:  Complex recursion in XSLT 1.0

> Could you elucidate a little on the concept of a 'stack'. I can only 
> dream of such a thing. What mechanism would you use?
> and... does that not sound like we need to have a list of all entries 
> first - is that another infinite loop?

OK. You're processing A, and it contains

<topic ref="X"/>
<topic ref="Y"/>

then when you make the call to process X, you pass it a $stack containing
<topic ref="Y"/>.

In X you find

<topic ref="P"/>
<topic ref="Q"/>

so you make a recursive call to process P, passing it a $stack containing
the previous $stack plus <topic ref="Q"/>

When you've finished processing P, you select the last thing on the stack
(which is Q), you process that, passing a stack from which Q has been
removed. Then when you finish processing Q, you select the last thing on the
stack (which is Y) and process that, passing a stack which is now empty.
When you finish processing Y you are done.
> 
> All these Catch 22's are piling up and I'm starting to think that this 
> is fundamentally impossible in XSLT 1.0 because we are not party to 
> essential information about what went before.

It's absolutely not fundamentally impossible because XSLT is
Turing-complete. I agree it might be a bit mind-bending when you're not used
to this style of coding.

One reason I published the knight's tour stylesheet in my XSLT Programmer's
Reference was to convince people that problems like this could be solved.

Michael Kay
http://www.saxonica.com/