[xquery-talk] XQuery static typing algorithms?

[Per Bothner]

Thanks to both Jens Teubner and Bas de Bakker for your suggestions!

Jens Teubner wrote:
> My personal impression is that, if you want to be standards-compliant, the
> best way to start is to literally implement all the judgments in the W3C
> Formal Semantics.

In general that is good advice, but when it comes to subtyping, then
the Formal Semantics doesn't provide judgements that are implementable,
as far as I can tell:

8.3.2 Subtyping (<:)

...

Note

The above definition, although complete and precise, does not give a 
simple means to compute subtyping. Notably the definition above refers 
to values, which are not available at static type checking time.

The structural component of the [XPath/XQuery] type system can be 
modeled by regular expressions. Regular expressions can be implemented 
by means of finite state automata. Computing subtyping between two types 
can then be done by computing if inclusion holds between their 
corresponding finite state automata.

Finite state automata and how to compute operations on those automata, 
such as inclusion, emptiness or intersection, have been extensively 
studied and documented in the literature. The interested reader can 
consult the relevant literature on tree grammars, for instance 
[Languages], or [TATA].
-- 
	--Per Bothner
per at bothner.com   http://per.bothner.com/