Włodzimierz Drabent, Artur Wilk:
Type Inference and Rule Dependencies in Xcerpt.

Complete Text [
.pdf, 399KB]

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.



	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 = {}