Lambda the Ultimate

inactiveTopic XQuery 1.0 and XPath 2.0 Formal Semantics
started 8/28/2003; 8:54:29 AM - last post 8/31/2003; 10:36:12 AM
Ehud Lamm - XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/28/2003; 8:54:29 AM (reads: 8735, responses: 9)
XQuery 1.0 and XPath 2.0 Formal Semantics
Working draft, dated 22 August 2003.

Two important design aspects of [XPath/XQuery] are that it is functional and that it is typed. These two aspects play an important role in the [XPath/XQuery] Formal Semantics.

Ever wanted to see the typing rules for XQuery in all their gory details? This document is for you (yes Wadler is on the editorial team). FLWR experessions and the rest are all there.

And if, on the other hand, the mere mention of formal semantics makes faint, don't worry: the document provides a very gentle introduction.


Posted to xml by Ehud Lamm on 8/28/03; 8:59:04 AM

Andris Birkmanis - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/28/2003; 10:37:16 AM (reads: 658, responses: 2)
I wish OCL were defined with a comparable rigor... As a side-note, it's so interesting Ehud posted this adjacent to my humble OCL post - I always thought OCL was a simplified XQuery :-) Always since I understood that operating on general graphs is in fact simpler than on trees - you don't care about axes other than child (and derivatives), as you just don't have access to them. From the other side, all my uses of UML Static Structure Diagrams (class diagrams I used to call them) end up having a skeletal tree of aggregations enhanced by a web of mostly one-way associations... Probably just my personal style, what is your mileage? Ah, and to define mutually-recursive types - just Generalization trick (as in Composite Pattern). Lately I play with an idea to (mentally) unify UML and its schemes (not capitalized) with algebraic types. Every time I think I almost grokked it, I find something new about algebraic types ;-( This time it was Generic Haskell, I am in process of creating my pet Generic UML ;-)

What is your experience - do you think of UML in terms of algebras (and when defining operations, probably coalgebras?)? Or do you ignore it? It's really interesting cognitive problem for me, as I came from the opposite direction, thinking of categories in terms of UML classes :-)

Frank Atanassow - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/29/2003; 6:56:51 AM (reads: 603, responses: 1)
Always since I understood that operating on general graphs is in fact simpler than on trees - you don't care about axes other than child (and derivatives), as you just don't have access to them.

It cannot be the case that processing graphs is easier than processing trees since every tree is a graph but not vice versa, so there are more possibilities to cover.

do you think of UML in terms of algebras (and when defining operations, probably coalgebras?)?

I try not to think of UML.

It's really interesting cognitive problem for me

Uh oh... :)

Ehud Lamm - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/29/2003; 7:07:12 AM (reads: 628, responses: 0)
do you think of UML in terms of algebras (and when defining operations, probably coalgebras?)?

I try not to think of UML.

Moi aussi.

Andris Birkmanis - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/29/2003; 9:25:58 AM (reads: 574, responses: 1)
It cannot be the case that processing graphs is easier than processing trees since every tree is a graph but not vice versa, so there are more possibilities to cover.

If you define the same goals, then true.
But the very fact that you have a more specific structure 
with more invariants opens new possibilities for processing,
so not covering them will be a shame...
And covering them requires additional effort - that was my point.

For example, if XPath pretended you cannot universally access a parent (ancestor, siblings, following etc.), it would be much simpler.

I try not to think of UML.

Moi aussi.

Excuse moi :-)
I hope it was not tabu to mention it...

Is UML hopelessly worthless? Is it going the wrong way? Or is it being pushed/dragged the wrong way?

IMHO, it's not UML as notation that is evil (I use class diagrams frequently), but over-estimating "silver-bulletness" of monstrous shemes. I'm affraid it takes some efforts for people with imperative background to dispel MDA PR of uber methodology - I witness people falling prey to that daily...

"More methodology will save us, we just need to be more UML-compliant, and use design patterns everywhere" :-)
Then again, maybe OMG just lack people like Wadler? ;-)

Ehud Lamm - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/29/2003; 2:02:14 PM (reads: 550, responses: 0)
Then again, maybe OMG just lack people like Wadler?

Do you think this is a coincidence?

(And no, UML is not taboo. My personal likes and dislikes are just that: personal).

Frank Atanassow - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/31/2003; 7:46:38 AM (reads: 474, responses: 0)
Is UML hopelessly worthless?

The UML spec is huge now, and I have no idea what most of it contains, and so I cannot comment on it. But I can comment on the original idea for UML, which was to standardize an informal notation for inheritance diagrams.

Do I think that inheritance diagrams are worthless? No. Do I think that standardizing an informal notation is pointless? Yes. Do I think there are more useful ways of describing an OO system than with inheritance diagrams, use-case diagrams, interaction diagrams and whatnot? Yes.

I might as well add that I am largely opposed to standardization anyway. I support standardization of some ubiquitous low-level concepts (TCP/IP, floating point operations and Unicode are examples) but not high-level concepts unless they can be effectively formalized, as is the case with programming languages.

One reason for this is that I think the point of a standard is to fix arbitrary choices, and not to limit the design space. There are orders of magnitude more design choices with high-level concepts than with low-level ones, and consequently far fewer (and often zero) people who are qualified and knowledgeable enough to distinguish between design choices that merely fix some arbitrary representational issue, and design choices that really fix some aspect of the specification.

In cases where there is really not enough knowledge available to make that sort of distinction, I favor encoding a solution as a program (or white-box library) in some standardized (portable) programming language.

For example, I think things like CSS are lame: we just don't know enough about 2D drawing to characterize it effectively, so there are lots of limitations to CSS which you don't realize are there until you're halfway through a project. (For example, the order of displayed elements must match the order in the input document, and there is no fine control over relationships between font sizes, indentation and so on.) It's better, then, to encode CSS as a library in some portable language, since there you at least have an escape hatch if you need to overcome some limitation.

This is the reason I favor standardizing programming languages: they provide a provably complete solution to the problem they claim to solve, namely how to do computation. The same cannot be said for most high-level standards.

Dominic Fox - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/31/2003; 8:38:36 AM (reads: 468, responses: 0)
For example, the order of displayed elements must match the order in the input document...
div.firstpara {
   position: absolute;
   top: 0px;
   left: 0px;
}

div.secondpara { position: absolute; top: 300px; left: 0px; }

[...]

<div class="secondpara">This is the first paragraph in the document</div> <div class="firstpara">This is the second paragraph in the document</div>

Not that the above particularly detracts from the lameness of CSS. I don't know that XSL-FO is much better.

Hmmm, I wonder what a decent little declarative language for describing formatting, layout and presentation might look like...

Manuel Simoni - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/31/2003; 9:17:27 AM (reads: 450, responses: 0)
Hmmm, I wonder what a decent little declarative language for describing formatting, layout and presentation might look like...

I think a good idea is to use a constraint solver, like CSVG does.

there is no fine control over relationships between font sizes,

Maybe you like Constraint CSS.

Andris Birkmanis - Re: XQuery 1.0 and XPath 2.0 Formal Semantics  blueArrow
8/31/2003; 10:36:12 AM (reads: 453, responses: 0)
Bravo, Frank, I really enjoyed your post. CSS is one of the monsters who torture me daily :-( I agree whole-heartedly that there are things that should not be standardized, and so pompously at that. Somebody mentioned premature standardization not so long ago... IMHO, the main problem is not even the fact somebody tries to unify some field of human activity, which is not ripe for that (or is not fit at all). The problem as I see it is this somebody is usually big (and rich) enough to push it. To push it into existence, then to businesses, then businesses start demanding that from their suppliers, universities start teaching it, it spreads like a virus. Is it western corporate culture that helps this phenomenon? Is it western culture in general? Is it (current) human culture?

Oops, I shouldn't have gone so far over-generalizing, is it a UML habit :-)