Re: Language is not markup and markup is not language.

[Paul Prescod <paul@xxxxxxxxxxx>]

Guy_Murphy@xxxxxxxxxx wrote:
> 
> Half of it went straight over my head, but I have a hunch that your post
> here is pithy, precise, and hits the nail on the head. Just to be sure,
> have you a reference to "Turing-complete[ness]" I can have a gander at <g>?
> My background is informal, so I'm unfamiliar with the reference.

http://plato.stanford.edu/entries/turing-machine/
http://www.geometry.net/turing.html

A Turing machine is an extremely simple computational device. You can
think of it as a physical machine or as a programming language. It is so
simple that you could probably implement a Turing machine emulator in a
few hundred lines of Python code (I've never tried it so I'm just guessing
here). The interesting thing about Turing machines is that they can
compute anything any other programming language can do. In other words,
this simple "programming language" is as powerful as C++ or Prolog. Put
yet another way: all programming languages have the same computational
power -- they only differ in their I/O capabilities and their user
interfaces. We say that they are all "Turing complete." You can emulate a
Turing machine in them and you can emulate any of them in a Turing
machine.

The problem is that there are many interesting analyses of computer
programs that are probably not possible. If you make a language that is
Turing complete then there are certain optimizations and checks that you
know that you will NEVER be able to do.

For instance imagine you are serving documents through a script to publish
them to the Web. Wouldn't it be nice to be able to check if the documents
and the script are "compatible" before you put them on your website? A
"compatible" document would be one that wouldn't cause the script to go
into an infinite loop or crash. Well with a scripting language the only
way to check is to run the script. If it seems to go into an infinite loop
then you could wait for half an hour and say: "well, I guess it is in an
infinite loop"-- but unless you know the details of the code you are just
guessing. You don't know for sure.

Turing proved that it is impossible to make a program that checks
compatibility of other programs and documents. The best you can do is "try
it and see." According to my interpretation, that's why software
development is so hard and software is often so buggy -- we can't check
the code with code.
Even when we have AI, they will only be able to use heuristics as we do.

"Declarative formats, such as context-free grammars, are formally
tractable, allowing reliable document interchange and maintenance."

 - http://www7.scu.edu.au/programme/fullpapers/1920/com1920.htm

Turing completeness is like winning the lottery: you get awesome freedom
but you lose some freedom also. This is why I fought against hacks like
xsl:script.

On the other hand, there are many other computational categories leading
up to Turing completeness and each of them has a similar cost/benefit
proposition. The more powerful the language, the more constrained the
optimization and static analysis techniques that implementors have
available. I don't think anybody really knows what we have lost as XSL has
become more and more advanced between the first draft and the most recent. 

Maybe there was a point at which it was feasible to prove that schemas and
documents were compatible and maybe we crossed it somewhere so that we are
left to use heuristics even though XSL is not fully Turing complete. 

It isn't as big a deal as if XML itself were Turing complete. If anyone
ever tries to sell you on a Turing complete language for storing your
primary data in, run far away! I will refer you again to this URL for
information on why that is the wrong way to go:

http://www7.scu.edu.au/programme/fullpapers/1920/com1920.htm

-- 
 Paul Prescod  - ISOGEN Consulting Engineer speaking for only himself
 http://itrc.uwaterloo.ca/~papresco

And so, in one of history's little ironies, the global triumph of bad
software in the age of the PC was reversed by a surprising combination
of forces: the social transformation initiated by the network, a
long-discarded European theory of political economy, and a small band
of programmers throughout the world mobilized by a single simple idea. 
 - http://old.law.columbia.edu/my_pubs/anarchism.html


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list