From: Atri Rudra (atri@cs.washington.edu)
Date: Tue Apr 13 2004 - 22:54:21 PDT
The main contribution of this paper is to give a formal model of XML,
albeit only for a subset of XML. The model allows the authors to come up
with a validation theorem which characterizes when an untyped XML document
can be validated. Though the theorem appears to be intuitive (very loosely
speaking the theorem says that an untyped value is validated as some type
if the value is of (or matches) the same type and the value corresponds to
(or erases to) the untyped value).
XML documents need to be validated to make sure that they conform to
specifications (again very loosely speaking, it is akin to compiling
code). The paper is pretty easy to follow if one has some knowledge about
functional languages (the authors being hotshots also means that in some
places the tone is very high handed). Most of the paper is building up
the model and various inference rules for various judgments (which, again
loosely speaking, are operations) and the main theorem follows easily from
applications of these inference rules.
The cool thing about the paper is the crisp model, after which the whole
things follows naturally. Restriction in XML seems similar to ranges which
are allowed in some languages and extensions are like inheritance in Java.
Interestingly, the validation theorem in addition to just being a nice
theoretical characterization can be used to speed up matching (which is a
sub-step of validation): this is vaguely similar to dynamic programming
paradigm where you use information about an already solved sub-problem and not
re-solve it again later.
This archive was generated by hypermail 2.1.6 : Tue Apr 13 2004 - 22:54:22 PDT