RE: [xml-dev] Your XML document is a programming language

["Costello, Roger L." <costello@mitre.org>]

Michael Kay wrote:

> you can certainly design a programming language 
> in which your <Book>..</Book> sample is a program. 
> It only becomes an interesting programming language 
> if it is suitable for writing a sufficiently general class of 
> programs, and that's something you have yet to 
> demonstrate.

Thanks Michael. Very nicely put.

Please permit me to explore this a bit further. I am convinced that it is useful to view XML vocabularies as programming languages and XML instances as programs. 

Although it is very simple, with my Book programming language I can create an infinite number of programs. In my first message I showed one program. Here is another

<Book>
    <Title>XSLT 2.0 and XPath 2.0</Title>
    <Author>Michael Kay</Author>
</Book>

When I execute that program my interpreter outputs

    XSLT 2.0 and XPath 2.0
    Michael Kay

I will grant you that my Book programming language is not a very exciting one and it limited. Nonetheless, it is a programming language -- there are constructs (markup) with specific semantics, there are variable parts (data), and the program instructs the computer what to do.

You may have noticed that in the Book programming language the programs had no input. The programs were standalone.

In the next programming language the programs take an input. This is a program

<Item name="Date">
    <Action>Remove</Action>
</Item>

and it has the following meaning

	Remove from the input the element 
	with the name, Date.

Here is sample input

<Email>
    <To>Roger Costello</To>
    <From>John Doe</From>
    <Date>September 9, 2013</Date>
</Email>

My interpreter, when given the program and input will output this

<Email>
    <To>Roger Costello</To>
    <From>John Doe</From>
</Email>

I think that you will agree that this programming language is simple yet surprisingly powerful.

Okay, what is the benefit of viewing XML vocabularies as programming languages and XML instances as programs? Answer: we can apply formal language theory to XML. We can ask questions such as

	Will all programs (XML instances) halt on 
	their inputs?

or

	Are all the programs decidable?
	(that is, stop and return yes or no)

This article [1] is fantastic and discusses the idea of applying formal language theory to inputs. The inputs are treated as programs that act upon a passive computer/silicon.

RECAP

In this message I have attempted to persuade you that

a. An XML vocabulary is a programming language (where the semantics of the markup is defined).

b. XML instances are programs.

c. A program is executed by an interpreter (an application) which outputs the result of running the program.

d. A program may have inputs.

e. Formal language theory can be applied programs.

f. By applying formal language theory to these programs we gain valuable insights regarding the complexity them.

Thoughts?

/Roger

[1] http://www.cs.dartmouth.edu/~sergey/langsec/papers/Sassaman.pdf