The goal of the talk was to show that XSLT is Turing-complete by coding μ-recursive functions in XSLT. Fine, interesting. Let's see, in brief explanation of XSLT Stephan writes:
Templates may have a name. If a template has a name, it can be called by another template via this name:As Norm Walsh pointed out, that's wrong. XSLT 2.0 (at least the latest Last Call Working Draft) doesn't allow dynamic template calls. Name of a template to call must be known at compile time. That was XSLT 1.0 behaviour and looks like XSLT 2.0 won't break it. Saxon XSLT processor for years has an extension for allowing that, but that's just an extension and after all Saxon has lots of weird extensions, up to assignable variables. The fact is that XSLT 1.0 and latest XSLT 2.0 Last Call Working Draft doesn't support that.
<xsl:call-template name="f">
…
</xsl:call-template>
Instead of an identifier (Qname in XSLT terminology) like f there may be an expression that can be evaluated to an identifier, so that the template to be called may be determined at run-time. This is one of the features newly introduced in XSLT version 2.0 that we will make use of to simplify the exposition.
Well, that means Stephan's proof is based on a proprietary XSLT extension (or even a bug). But that doesn't mean the proof of Turing-Completeness of XSLT failed. There is pure XSLT way to call templates by name dynamically. It's a method of "template references", apparently invented by Corey Haines and developed by Dimitre Novatchev (in fact the whole "FXSL -- the Functional Programming Library for XSLT" is based on that method).
Then Stephan proposes to build a stack in XSLT using a string:
XPath provides stings as data types and string functions which allow one to emulate stacks by strings. One needs a symbol separating objects on the stack. In our case it will be the slash (/). To push an element on the stack, we use the function concat to concatenate strings. It takes two or more arguments and returns their concatenation. To get the top element of the stack, we use the function substring-before which takes two strings as arguments and returns the substring of the first string before the first occurrence of the second string. When using the stack as the first and the separating symbol `/' as the second argument, the top of the stack is returned. In other words, the leftmost element of the string is the top of the stack. To get the rest of the stack, we use substing-after.Interesting approach, but do we really need stack in XSLT for anything more practical than academic paper?
And the last problem Stephan struggles with is returning a value from a template. Well, academics love to solve problems, even when there are no problems:
Thus the key problem of computing with templates is the (assumed) lack of the ability to return a value from a subcomputation. How can one pass on the result of a subcomputation? We propose to recode the control flow for templates and to pass on results of prior computations by means of stacks.The "(assumed)" word was inserted recently into the paper, it was more categorical assertion when I read it first some time ago ;) Of course it's easy to return a value from a template using result-tree fragments (XSLT 1.0) or temporary trees (XSLT 2.0):
<xsl:variable name="result"> <xsl:call-template name="foo"/> </xsl:variable>
Anyway, quite interesting paper...