Re: [xml-dev] XPath context reform?

[Joe English <jenglish@flightlab.com>]

Uche Ogbuji wrote:
>
> Do you (or anyone else) have any particular thoughts on how context might hav
> e been better implemented?  I'm very interested, because in Versa [1][2], the
>  RDF query language we've been working on, the idea of context heavily borrow
> s from that in XPath.  But most Versa folks right now have some XSLT chops, s
> o we might be thinking the XPath approach useful to follow because of the col
> oring of our experience.

The distinction between the current node/current node list
(XSLT context) and the context node/context position/context size
(XPath context) is a very subtle one that I for one had
a difficult time grasping.  For me, it helps to think in
terms of relations instead.

Each XPath axis can be thought of as a relation R \subset N \cross N
on the set N of document nodes.   For example the 'child' axis is
the relation { (p,c) | c is a child of p }; 'descendant-or-self'
is the reflexive transitive closure of 'child'; 'parent' is the converse
of 'child' { (c,p) | (p,c) \in child }, and 'self' is the identity
relation { (x,x) | x \in N }.

Then the infix '/' operator can be interpreted as relational
composition.  For example 'child::*/descendant::*' is the relation

    { (x,z) | \exists y s.t. (x,y) \in child, (y,z) \in descendant }

Node tests can also be interpreted as relations, as can
any other predicate that doesn't involve position() or last()
(including the shorthand notation 'foo[1]' which is an
abbreviation for 'child::foo[position() = 1]').  Any
predicate P is equivalent to a "coreflexive" relation
C(P) \subset id, C(P) = { (x,x) | x \in N, P(x) is true }.

Then node tests can also be explained in terms of
relational composition; for example

    descendant::olist/child::item
    	= descendant . C(name() = 'olist') . child . C(name() = 'item')

where '.' is relational composition and C(...) denotes
turning a predicate into a coreflexive relation.  The same
trick works to explain XPath predicates '[ expr ]' where 'expr'
evaluates to a boolean.  If 'expr' evaluates to a node set --
that is, if it's a path expression, and hence a relation --
it can be converted to a coreflexive relation

    { (x,x) | \exists y :  (x,y) \in expr }

or more concisely: ((expr . converse(expr)) \intersect self)

If 'expr' evaluates to a number, things get hairier to explain,
and we have to go back to context nodes and context positions again.

But as long as 'position()' and 'last()' don't appear (directly
or indirectly), any XPath expression can be interpreted as a
relation, and evaluating an XPath expression R with respect to
a node x \in N yields the node set { y : (x,y) \in R }.

If you prefer to work with node lists instead of node sets,
there's an almost identical interpretation wherein axes and
node tests are functions from nodes to node lists, and instead
of relational composition you use "list function composition":

	(f `o` g) x = [ z | y <- f x, z <- g y]

The notions of context node, context position, and context size
are only needed when you try to explain position(), last(),
and the shorthand notation foo[n] where 'n' is an integer.

So to answer the original question -- if anyone else has any
thoughts on how context might have been better implemented --
I would have left it out entirely.  For the 'foo[n]' functionality,
I'd instead define higher order functions like select-nth(expr,n),
select-first(expr), select-last(expr), or select-range(expr,n1,n2).

Of course that would never fly.  Mike Kay once observed that people
are far more willing to accept changes in semantics than they are
changes in syntax, and "foo[n]" is widely beloved by developers
even though it's a bit of a pain to formalize.


--Joe English

  jenglish@flightlab.com