Re: [xml-dev] RE: Concerned about the increasing reliance on XPath

[Dimitre Novatchev <dnovatchev@gmail.com>]

Roger,

> You stated the problem perfectly:
>
>   ... analyzing/assessing programs is equivalent
>   to the halting problem
>
> That is, once XPath is introduced into an XML vocabulary then analysis/assessment becomes impossible.

I still don't know what you mean by "analysis/assessment".

If you know what exact relationships you want to express, then it
might be possible to design a restricted language.

Such a language would express only limited class of relationshops.

I strongly suspect that there will be relationships that you'd want to
express that cannot be done using this specific language only, and
thus you'll need yet another language.

So, it seems that the full power of a programming language will be
necessary in the general case.

If this isn't so, one must provide a proof (and a proof requires exact
definitions) -- do you have one?


-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.


On Mon, May 9, 2011 at 1:20 PM, Costello, Roger L. <costello@mitre.org> wrote:
> Hi Dimitre,
>
>> If you need to express *any* possible relationships
>> then most probably you need a full-fledged programming language and
>> analyzing/assessing programs is equivalent to the halting problem.
>
> You stated the problem perfectly:
>
>   ... analyzing/assessing programs is equivalent
>   to the halting problem
>
> That is, once XPath is introduced into an XML vocabulary then analysis/assessment becomes impossible.
>
> Often it is not necessary to express *any* possible relationship. For my "purchase XML vocabulary" it seems reasonable that one should be able to identify the relationships that are really needed. It is unlikely that *any* relationship is needed.
>
> By constraining the set of relationships -- using XML markup -- then the analysis/assessment problem is reduced from the halting problem (i.e., impossible) to something that is achievable.
>
> /Roger
>
> -----Original Message-----
> From: Dimitre Novatchev [mailto:dnovatchev@gmail.com]
> Sent: Monday, May 09, 2011 4:05 PM
> To: Costello, Roger L.
> Cc: xml-dev@lists.xml.org
> Subject: Re: [xml-dev] RE: Concerned about the increasing reliance on XPath
>
>> Assessing the <Item> elements is easy; they just contain decimal values. Assessing the <Total> element is probably impossible since it can contain any arbitrary XPath expression.
>>
>> That's bad.
>>
>> XPath is fine if all you want to do is "execute" the XML vocabulary. But if you want to "assess/analyze" your  XML vocabulary then XPath is not fine.
>
>
> This is true for any programming language. Why should the use of XPath
> be any different? If you need to express *any* possible relationships
> then most probably you need a full-fledged programming language and
> analyzing/assessing programs is equivalent to the halting problem.
>
>
> Please, reformulate, or otherwise this strikes the reader as another
> rediscovering the wheel.
>
> --
> Cheers,
> Dimitre Novatchev
> ---------------------------------------
> Truly great madness cannot be achieved without significant intelligence.
> ---------------------------------------
> To invent, you need a good imagination and a pile of junk
> -------------------------------------
> Never fight an inanimate object
> -------------------------------------
> You've achieved success in your field when you don't know whether what
> you're doing is work or play
> -------------------------------------
> Facts do not cease to exist because they are ignored.
> -------------------------------------
> I finally figured out the only reason to be alive is to enjoy it.
>
>
> On Mon, May 9, 2011 at 12:18 PM, Costello, Roger L. <costello@mitre.org> wrote:
>> Hi Folks,
>>
>> Suppose you create an XML vocabulary for describing purchases:
>>
>> Purchase
>>     Item: decimal
>>     Total: XPath
>>
>> The value of <Total> is any XPath expression.
>>
>> Here's a sample instance document:
>>
>> <Purchase>
>>      <Item>10.00</Item>
>>      <Item>20.00</Item>
>>      <Total>sum(../Item)</Total>
>> </Purchase>
>>
>> You input that instance document into your "purchase processor" and it outputs:
>>
>>    Your purchases:
>>        Item: $10.00
>>        Item: $20.00
>>        Total: $30.00
>>
>> The XPath expression in the <Total> element was evaluated by the "purchase processor."
>>
>> The <Total> element is powerful - the full power of XPath is available to it. To further illustrate its power, we could write an XPath expression to convert the sum of the Items to another currency:
>>
>>    <Total>sum(../Item) * 2.1034</Total>
>>
>> Or we could write an XPath expression that pulls in data from other documents to compute the total.
>>
>> Pretty powerful, aye?
>>
>> Now, write this tool: the input to the tool is a "purchase instance document", such as this:
>>
>> <Purchase>
>>      <Item>10.00</Item>
>>      <Item>20.00</Item>
>>      <Total>sum(../Item)</Total>
>> </Purchase>
>>
>> The tool assesses the instance document and outputs the results of the assessment.
>>
>> Ouch!
>>
>> Assessing the <Item> elements is easy; they just contain decimal values. Assessing the <Total> element is probably impossible since it can contain any arbitrary XPath expression.
>>
>> That's bad.
>>
>> XPath is fine if all you want to do is "execute" the XML vocabulary. But if you want to "assess/analyze" your  XML vocabulary then XPath is not fine.
>>
>> Contrast the above with this XML vocabulary:
>>
>> Purchase
>>     Item: decimal
>>     Total
>>         SumPrecedingItems
>>              Value: decimal
>>
>> Here's a sample instance document:
>>
>> <Purchase>
>>      <Item>10.00</Item>
>>      <Item>20.00</Item>
>>      <Total>
>>            <SumPrecedingItems>
>>                 <Value>30.00</Value>
>>            </SumPrecedingItems>
>>      </Total>
>> </Purchase>
>>
>> The <Total> element is much less powerful - its content is an element that has the semantics "sum all the preceding <Item> elements."
>>
>> Now, write a tool in which you give it a "purchase instance document" and it assesses the instance document.
>>
>> Easy!
>>
>> Analysis of the XML vocabulary is possible (easy, in fact).
>>
>> Summary: if an XML vocabulary permits XPath expressions then analysis of the XML vocabulary becomes exceedingly difficult (or impossible).
>>
>> Comments?
>>
>> /Roger
>>
>> _______________________________________________________________________
>>
>> XML-DEV is a publicly archived, unmoderated list hosted by OASIS
>> to support XML implementation and development. To minimize
>> spam in the archives, you must subscribe before posting.
>>
>> [Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
>> Or unsubscribe: xml-dev-unsubscribe@lists.xml.org
>> subscribe: xml-dev-subscribe@lists.xml.org
>> List archive: http://lists.xml.org/archives/xml-dev/
>> List Guidelines: http://www.oasis-open.org/maillists/guidelines.php
>>
>>
>