[xquery-talk] XQuery static typing algorithms?
per at bothner.com
Mon Nov 24 07:29:49 PST 2008
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 (<:)
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 at bothner.com http://per.bothner.com/
More information about the talk