Abstract
We present a type system for a substantial fragment of the Web query language Xcerpt. It is a descriptive type system: the typing of a program is an approximation of its semantics. This paper augments the previous work on typing single Xcerpt rules, by a type inference method for possibly recursive Xcerpt programs (consisting of many rules). The method may be seen as abstract interpretation. We provide a way to make fixed point computations finite, and to estimate in advance the number of iterations needed to obtain a fixed point. The latter is necessary, as a test for a fixed point is too expensive. We also show how the obtained type information can be used for discovering dependencies between rules. We expect that besides typical usage of a type system, such as discovering type errors, the presented methods can be used for improving efficiency of program evaluation.

URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-TR-2007-08

BibTeX:

@techreport{REWERSE-TR-2007-08,
	author = {W\lodzimierz Drabent and Artur Wilk},
	title = {Type Inference and Rule Dependencies in Xcerpt},
	institution = {Institute for Informatics, University of Munich},
	year = {2007},
	type = {{research report, REWERSE-TR-2007-08}},
	number = {REWERSE-TR-2007-08},
	url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-TR-2007-08}
}