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

[Greg Hunt <greg@firmansyah.com>]

Roger,
I thought that your original point was that the calculation should be
encoded as XML to make it easy to manipulate. The halting problem
arises from the complexity of the behaviour that is described, not
from its encoding.  You seem to want your hypothetical analysis to be
capable of anything (you did not seriously limit its scope in your
example), in which case ecoding the instructions as XML doesn't get
you much if anything over encoding them in some programming language
(modulo the parsing required).

Analysis becomes difficult when the behaviour that is described
becomes sufficiently complex (for suitable values of "difficult" and
"complex").  Your initial example seemed to suggest that you want to
constrain the set of behaviours that the XPath could have.    If the
same things are encoded as XPath or as some bespoke XML then the
analysis of behaviour (after parsing) has the same degree of
complexity because they are instructions for the same behaviours.
Thats just a matter of defining a subset of the full language and
enforcing that subset (I've seen examples of that).  Of course, if you
have very few behaviours that you want to support (sum for example)
then your XML element approach is easiest to implement, but as the
number grows and the complexity of the operations grows the argument
for picking up someone else's XPath implementation becomes stronger
(for example avoiding mixing data and instructions, avoiding writing
the code to implement the operations).

Greg

On Tue, May 10, 2011 at 6:20 AM, 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
>>
>>
>