peteg's blog - hacking - 2007 11 27 XSLT Turing Complete

XSLT is Turing Complete. So What?

/hacking | Link

There are several proofs of this fact, such as this one from 2006. So, why would IBM's DeveloperWorks publish an an article that apparently says otherwise [*]?

Finally, XSLT is the familiar technique that, in a sense, best matches the structure of XML. Perhaps reflecting this match, XSL documents are themselves XML document instances. XSLT is a special-purpose functional programming language that allows you to specify transformations of XML documents into other things (especially, but not only, into other XML documents). Aside from the somewhat annoying verboseness of XSLT, it is limited in its expressiveness — the things you can say are expressed rather clearly (and functionally, not procedurally), but you quickly bump up against all the things that you simply cannot say in XSLT.

OK, so there is an appeal to a Turing tarpit argument, but how about that last phrase, the worrying ... all the things that you simply cannot say in XSLT? Let's keep reading:

The problem comes as soon as you want to filter or compute something for the output — something that is not included in the few comparisons available to XSLT. For example, maybe you want (in a numerological spirit) to display only the even-numbered hexagrams, or only the prime ones. With XSLT, you are out of luck for something this simple.

So, what we have here is something like control completeness — it has enough in the way of control flow constructs — but data-incompleteness — you can't munge your data in all the ways you'd like to. This has always bothered me: how do you prove that you have provided enough operations for your datatype? I'm sure there are people studying algebraic data types and algebraic specification who have some answers for that.

[*] As this article should make clear, the claim of Turing Completeness is weaker and slipperier than most people seem to think.