Typed iterators for XML

ABSTRACT

XML transformations are very sensitive to types: XML types describe the tags and attributes of XML elements as well as the number, kind, and order of their sub-elements. Therefore, operations, even simple ones, that modify these features may affect the types of documents. Operations on XML documents are performed by iterators that, to be useful, need to be typed by a kind of polymorphism that goes beyond what currently exists. For this reason these iterators are not programmed but, rather, hard-coded in the languages. However, this approach soon reaches its limits, as the hard-coded iterators cannot cover fairly standard usage scenarios.

As a solution to this problem we propose a generic language to define iterators for XML data. This language can either be used as a compilation target (e.g., for XPATH) or it can be grafted on any statically typed host programming language (as long as this has product types) to endow it with XML processing capabilities. We show that our language mostly offers the required degree of polymorphism, study its formal properties, and show its expressiveness and practical impact by providing several usage examples and encodings.

REFERENCES

• 1: Roberto M. Amadio , Luca Cardelli, Subtyping recursive types, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.575-631, Sept. 1993 [doi>10.1145/155183.155231]
• 2: Véronique Benzaken , Giuseppe Castagna , Dario Colazzo , Kim Nguyên, Type-based XML projection, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Véronique Benzaken , Giuseppe Castagna , Alain Frisch, CDuce: an XML-centric general-purpose language, Proceedings of the eighth ACM SIGPLAN international conference on Functional programming, p.51-63, August 25-29, 2003, Uppsala, Sweden
• 4: V. Benzaken, G. Castagna, and C. Miachon. A full pattern-based paradigm for XML query processing. In PADL 05, number 3350 in LNCS, pages 235--252, 2005.
• 5: B. Courcelle. Fundamental properties of infinite trees. Theoretical Computer Science, 25:95--169, 1983.
• 6: W3C: DTD specifications. http://www.w3.org/TR/REC-xml.
• 7: A. Frisch. Regular tree language recognition with static information. In Proc. IFIP Conf. on Theor. Comput. Sci. (TCS). Kleuwer, 2004.
• 8: Alain Frisch, OCaml + XDuce, ACM SIGPLAN Notices, v.41 n.9, September 2006
• 9: Alain Frisch , Giuseppe Castagna , Véronique Benzaken, Semantic Subtyping, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.137-146, July 22-25, 2002
• 10: Alain Frisch , Giuseppe Castagna , Véronique Benzaken, Semantic subtyping: Dealing set-theoretically with function, union, intersection, and negation types, Journal of the ACM (JACM), v.55 n.4, p.1-64, September 2008 [doi>10.1145/1391289.1391293]
• 11: Alain Frisch and Haruo Hosoya. Towards practial typechecking for macro tree transducers. In DBPL, 2007.
• 12: Vladimir Gapeyev , Michael Y. Levin , Benjamin C. Pierce, Recursive subtyping revealed, Journal of Functional Programming, v.12 n.6, p.511-548, November 2002 [doi>10.1017/S0956796802004318]
• 13: V. Gapeyev, M. Y. Levin, B. C. Pierce, and A. Schmitt. The Xtatic experience. In PLAN-X, 2005.
• 14: H. Hosoya. Regular expression filters for XML. In Programming Languages Technologies for XML (PLAN-X), pages 13--27, 2004.
• 15: Haruo Hosoya , Alain Frisch , Giuseppe Castagna, Parametric polymorphism for XML, Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.50-62, January 12-14, 2005, Long Beach, California, USA
• 16: Haruo Hosoya , Benjamin Pierce, Regular expression pattern matching for XML, Proceedings of the 28th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-80, January 2001, London, United Kingdom
• 17: Haruo Hosoya , Benjamin C. Pierce, XDuce: A statically typed XML processing language, ACM Transactions on Internet Technology (TOIT), v.3 n.2, p.117-148, May 2003 [doi>10.1145/767193.767195]
• 18: Haruo Hosoya , Jérôme Vouillon , Benjamin C. Pierce, Regular expression types for XML, ACM SIGPLAN Notices, v.35 n.9, p.11-22, Sept. 2000
• 19: Ralf Lämmel, Scrap your boilerplate with XPath-like combinators, Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 17-19, 2007, Nice, France
• 20: M.Y. Levin and B.C. Pierce. Type-based optimization for regular patterns. In DBPL '05, August 2005.
• 21: S. Maneth , A. Berlea , T. Perst , H. Seidl, XML type checking with macro tree transducers, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065203]
• 22: S. Maneth, T. Perst, and H. Seidl. Exact XML type checking in polynomial time. In ICDT, pages 254--268, 2007.
• 23: Tova Milo , Dan Suciu , Victor Vianu, Typechecking for XML transformers, Journal of Computer and System Sciences, v.66 n.1, p.66-97, 01 February 2003 [doi>10.1016/S0022-0000(02)00030-2]
• 24: Mark-Jan Nederhof, Practical experiments with regular approximation of context-free languages, Computational Linguistics, v.26 n.1, p.17-44, March 2000 [doi>10.1162/089120100561610]
• 25: Kim Nguyen. Combinator language for XML: design, typing, and implementation. PhD thesis, Université Paris-Sud 11, 2008.
• 26: OASIS Committee Specification: Relax-NG. http://relaxng.org/
• 27: M. Sulzmann and K. Zhuo Ming Lu. A type-safe embedding of XDuce into ML. El. Notes Theor. Comp. Sci., 148(2):239--264, 2006.
• 28: M. Sulzmann and K. Zhuo Ming Lu. XHaskell. In PLAN-X, 2006.
• 29: Jérôme Vouillon, Polymorphic regular tree types and patterns, Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.103-114, January 11-13, 2006, Charleston, South Carolina, USA
• 30: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990
• 31: W3C: XML Schema. http://www.w3.org/XML/Schema.
• 32: W3C: XML Path Language Ver. 1.0. http://www.w3.org/TR/xpath.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Polymorphism

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs
          Subjects: Type structure

General Terms:
Design, Languages, Theory

Keywords:
XML, iterators, polymorphism, subtyping