Jour: Vendredi
Date: 01/10/04
Heure: 10h30
Salle: Salle de conférences du bâtiment 7
Projet: cristal
Orateur: Haruo Hosoya
Institution(optionnel): University of Tokyo
Titre: Parametric Polymorphism for XML
Titre-long(optionnel):
Message(optionnel): 
Resume:

Although several type systems have been investigated for XML, parametric
polymorphism is rarely treated.  This well-established typing discipline
can also be useful in XML processing in particular for programs involving
``parametric schemas,'' i.e., schemas parameterized over other schemas
(e.g., SOAP).  The difficulty in treating polymorphism for XML lies in how
to extend the ``semantic'' approach used in the mainstream (monomorphic)
XML type systems.  A naive extension would be ``semantic'' quantification
over all substitutions for type variables.  However, this approach reduces
to an NEXPTIME-complete problem for which no practical algorithm is known,
and, moreover, the type system obtained in this way is characterized by a
hardly useful expressiveness.  In this paper, we propose a lighter-weight
way of extending the semantic approach, where we interpret type variables
as {\em markings\/} in data values for indicating the parameterized
subparts.  As a result, we can construct a sensible polymorphic type
system both with a semantic flavor and a set of practical algorithms
needed for typechecking.  Most of these algorithms can be obtained by
local modifications to existing ones for a monomorphic system.