Re: XML query constructors: not well-defined

Dear Dan,

This is a response to the following message, which you posted to the XML 
Query Working Group's comments list:

http://lists.w3.org/Archives/Public/www-xml-query-comments/2001May/0009.html


The XML Query Working Group has approved the following response:

Dan Connolly wrote:
> >     You are correct that a node constructor is not function in the
> >     mathematical sense, because it has the side effect of creating a
> >     node with a unique identity.
> 
> Bummer. I really would like to have an XML data model with
> constructors that I can use in traditional math settings,
> with substitution-of-equals-for-equals and all that.

A value-based semantics would simplify the data model considerably. 
Unfortunately, we inherited baggage with XML that
includes node identity.  The crux
of the problem is that both the Infoset and XPath data models
represent the parent of a node, in addition to its children.  
So the two <a/> nodes below may be structurally equal (we
can't distinguish them by just looking at their content)
but they have distinct identities : the data model must
distinguish between the two because their parents are *not*
the same:

  <b><a/></b>
  <c><a/></c>

If we chose not to represent parent in the Query data model, then 
we could eliminate node identity and have purely functional
element constructors.  We decided that this choice was
too much of a departure from Infoset & XPath 1.0 and would
make compatibility with XPath almost impossible.  

> I ran into Michael Rys at the conference, and he started
> to explain that I could look at these operators as
> producing new monads or some such, but I don't understand
> enough background to get it. I'd appreciate pointers
> to background reading on monads or whatever.

You should ask Phil Wadler but I would start with this paper, which
is a very nice survey: 

'How to declare an imperative', Philip Wadler. ACM Computing Surveys,
29(3):240--263, September 1997. 

and then do citation hopping from there.

> [...]
> 
> > We appreciate your feedback on the XML Query specifications. Please let
> > us
> > know if this response is satisfactory. If not, please respond to this
> > message, explaining your concerns.
> 
> I'm not sure yet...
> 
> Maybe you can explain this monad stuff so that I can use
> the design as specified above in traditional math settings.

Although we might be able to define node constructors as monads,
I'm not sure we want to add that level of theoretical support
to the spec.  But if you explain what you're doing, I could
maybe help with a definition that supports your needs.

> 
> I'm going to keep an eye out for use-cases where this really
> matters. Maybe it's just a matter of taste and I'll learn
> to live with it.

It's not taste. Hopefully, the example above illustrates.
Another more practical reason is that XML in document-processing
applications makes heavy use of node identity, again, because
of dependence on parents, ancestors, and siblings.  If we just
stick with children, just like we would do in tree grammars,
then alot of problems go away.

We appreciate your feedback on the XML Query specifications. Please let
us 
know if this response is satisfactory. If not, please respond to this 
message, explaining your concerns.

Mary Fernandez
On behalf of the XML Query Working Group

> Re: XML query constructors: not well-defined
> 
> From: Dan Connolly (connolly@w3.org)
-- 
Mary Fernandez                    AT&T Labs - Research          
Principal Technical Staff Member  180 Park Ave., Bldg 103, E243 
mff@research.att.com		  Florham Park, NJ 07932-0971   
http://www.research.att.com/~mff  973-360-8679 FAX: 973-360-8187

Received on Thursday, 14 June 2001 10:10:23 UTC