Stephan Kepser (University of Tubingen) has presented a talk called "A Simple Proof for the Turing-Completeness of XSLT and XQuery" on recent Extreme Markup Languages 2004 conference. You can find the paper at the link above and report by Elliotte Rusty Harold here. Here are my comments on that paper.
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...
Corey,
I am so glad to read your blog with full recollection of the happy old times. Thank you for preserving pointers to those threads -- I tried too, but didn't succeed as xsl-talk now has many thousands of messages.
I have always admired your modesty and this case is no exception. While you're saying that we discovered the "template reference" together, I think it is obvious from the thread that the discoverer was you alone.
I am proud that I know you, mate. Hope that we could work together again.
Cheers,
Dimitre.
Yeah. I never realized that I was even a "Corey Haines." HAHA!
I was kind of surprised when I saw my name (actually through a roundabout google search), as I've been subscribed to you for quite a while, and this was one entry that I had to put off reading for a while I was catching up on my blogs after being away for a while. I wish that I had read this earlier, for sure.
Hmm, really small world. Being subscribed to you blog I never had any idea you are that Corey Haines! :)
Wow! Small world, indeed. It is funny how a small conversation with Dimitre a few years ago has influenced such cool stuff. I remember reading his article of FXSL, which was awesome and got me inspired to really investigate declarative, functional languages.
It's good to see you around still, Dimitre, seems like I keep running into you. When I'm teaching people XSLT, I still use the problem that we were discussing when we came up with the idea for "template references."
I never thought it was anything worthy of being called "invented," although I do remember how big it seemed when we discovered it and started seeing the implications. Personally, I always called them "callbacks." :)
Dimitre, drop me a line on my blog. Where's yours?
Completely agree with your comment.
Just a note that this specific problem has a very simple and compact XSLT 1.0 solution (just 5 lines of code):
<xsl:template name="maxSubtreeDepth">
<xsl:variable name="vLeaves" select="$prootNode//node()[not(node())]"/>
<xsl:for-each select="$vLeaves">
<xsl:sort select="count(ancestor::node())" data-type="number" order="descending"/>
<xsl:if test="position() = 1">
<xsl:value-of select="count(ancestor::node())"/>
<xsl:if>
<xsl:for-each>
<xsl:template>
This is just another example the poor quality of the peer review process for most XML academic articles. Back when I was doing research on XML optimizations, I found that with a couple of exceptions (notably papers by Victor Vianu and Dan Suciu), most XML research papers contained numerous, obvious errors.
As just one example, one paper complained that MSXML doesn't seem to optimize a[count(b) > 1] into a[b]. (Which is a good thing, since they're not the same query - the latter tests count(b) > 0.)
Result tree fragments (RTFs) do have limitations that impact theoretical work in XSLT 1.0. They're sort of nodes but not really, and they're definitely not atomic values. For academic purposes, you really can't "return" a non-RTF value from a template.
For practical applications, almost every implementation provides a nodeset() extension to XSLT 1.0 that can be used to overcome the limitations of RTFs (making them ordinary nodes) and then you can "return" any desired value from a template. [However, constructing an XML tree and then converting its string value to number is an expensive way to get a number.]
If you want a fun challenge that's impacted by this limitation of RTFs, write an XSLT - without using extensions - that given a node in an XML tree, computes the unique maximum (or minimum) depth among the subtrees rooted at that node.
<xsl:template name="max-depth">
<xsl:param name="root"/>
...
</xsl:template>
1. By "the (assumed) lack of the ability to return a value from a subcomputation" he means that in XSLT 1.0 one must use the exslt:node-set() ext. fn. in order to convert an RTF to a node-set.
If one needs only "pure XSLT 1.0" without using exslt:node-set(), then the only possible way is not to return a computed node-set, but to pass it down by calling the continuation of the computation.
2. Corey Haines is the person, who showed the template reference technique to me. Michael Kay claims (see the xsl-list archives) that he knew about this technique long ago.
Therefore, it is not clear who exactly "invented" the technique (my modesty prevents me from pointing out that I was the first to use the term "template reference" :o) ). What is really important is that this idea has been explored in a useful way and with FXSL we have functional programming in XSLT -- something that is not offered by either XSLT 1.0 or XSLT 2.0.
Now we see another important use of the idea of template references -- in a formal proof of the Turing-completeness of XSLT. Wonderful !
Cheers,
Dimitre.