{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:27Z","timestamp":1750307547129,"version":"3.41.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,10,1]],"date-time":"2009-10-01T00:00:00Z","timestamp":1254355200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["IST-2001-32617"],"award-info":[{"award-number":["IST-2001-32617"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2009,10]]},"abstract":"<jats:p>Despite the extensiveness of recent investigations on static typing for XML, parametric polymorphism has rarely been treated. This well-established typing discipline can also be useful in XML processing in particular for programs involving \u201cparametric schemas,\u201d that is, schemas parameterized over other schemas (e.g., SOAP). The difficulty in treating polymorphism for XML lies in how to extend the \u201csemantic\u201d approach used in the mainstream (monomorphic) XML type systems. A naive extension would be \u201csemantic\u201d quantification over all substitutions for type variables. However, this approach reduces to an NEXPTIME-complete problem for which no practical algorithm is known and induces a subtyping relation that may not always match the programmer's intuition. In this article, we propose a different method that smoothly extends the semantic approach yet is algorithmically easier. The key idea here is to devise a novel and simple<jats:italic>marking<\/jats:italic>technique, where we interpret a polymorphic type as a set of values with annotations of which subparts are parameterized. We exploit this interpretation in every ingredient of our polymorphic type system such as subtyping, inference of type arguments, etc. As a result, we achieve a sensible system that directly represents a usual expected behavior of polymorphic type systems\u2014\u201cvalues of abstract types are never reconstructed\u201d\u2014in a reminiscence of Reynold's parametricity theory. Also, we obtain a set of practical algorithms for typechecking by local modifications to existing ones for a monomorphic system.<\/jats:p>","DOI":"10.1145\/1596527.1596529","type":"journal-article","created":{"date-parts":[[2009,11,4]],"date-time":"2009-11-04T18:28:31Z","timestamp":1257359311000},"page":"1-56","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Parametric polymorphism for XML"],"prefix":"10.1145","volume":"32","author":[{"given":"Haruo","family":"Hosoya","sequence":"first","affiliation":[{"name":"The University of Tokyo, Tokyo, Japan"}]},{"given":"Alain","family":"Frisch","sequence":"additional","affiliation":[{"name":"LexiFi - France"}]},{"given":"Giuseppe","family":"Castagna","sequence":"additional","affiliation":[{"name":"PPS (CNRS) - Universit\u00e9 Denis Diderot, Paris, France"}]}],"member":"320","published-online":{"date-parts":[[2009,11,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1139"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375570"},{"key":"e_1_2_1_3_1","unstructured":"Altheim M. and McCarron S. 2001. XHTML 1.1 \u2014 Module-based XHTML. http:\/\/www.w3.org\/TR\/2001\/REC-xhtml11-20010531\/. Altheim M. and McCarron S. 2001. XHTML 1.1 \u2014 Module-based XHTML. http:\/\/www.w3.org\/TR\/2001\/REC-xhtml11-20010531\/."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54444-5_83"},{"key":"e_1_2_1_5_1","unstructured":"Ausbrooks R. Buswell S. Dalmas S. Devitt S. Diaz A. Hunter R. Smith B. Soiffer N. Sutor R. and Watt S. 2003. Mathematical Markup Language (MathML) Version 2.0 (Second Edition). http:\/\/www.w3.org\/Math\/. Ausbrooks R. Buswell S. Dalmas S. Devitt S. Diaz A. Hunter R. Smith B. Soiffer N. Sutor R. and Watt S. 2003. Mathematical Markup Language (MathML) Version 2.0 (Second Edition). http:\/\/www.w3.org\/Math\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/944705.944711"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/286936.286957"},{"key":"e_1_2_1_8_1","unstructured":"Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2000. Extensible markup language (XML#8482;). http:\/\/www.w3.org\/XML\/. Bray T. Paoli J. Sperberg-McQueen C. M. and Maler E. 2000. Extensible markup language (XML#8482;). http:\/\/www.w3.org\/XML\/."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99392"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1013"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411204.1411210"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199539"},{"key":"e_1_2_1_13_1","unstructured":"Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1999. Tree automata techniques and applications. Draft book; available electronically on http:\/\/www.grappa.univ-lille3.fr\/tata. Comon H. Dauchet M. Gilleron R. Jacquemard F. Lugiez D. Tison S. and Tommasi M. 1999. Tree automata techniques and applications. Draft book; available electronically on http:\/\/www.grappa.univ-lille3.fr\/tata."},{"key":"e_1_2_1_14_1","unstructured":"Fallside D. and Lafon Y. 2004. XML protocol working group. http:\/\/www.w3.org\/2000\/xp\/Group\/. Fallside D. and Lafon Y. 2004. XML protocol working group. http:\/\/www.w3.org\/2000\/xp\/Group\/."},{"key":"e_1_2_1_15_1","unstructured":"Fankhauser P. Fern\u00e1ndez M. Malhotra A. Rys M. Sim\u00e9on J. and Wadler P. 2001. XQuery 1.0 Formal Semantics. http:\/\/www.w3.org\/TR\/query-semantics\/. Fankhauser P. Fern\u00e1ndez M. Malhotra A. Rys M. Sim\u00e9on J. and Wadler P. 2001. XQuery 1.0 Formal Semantics. http:\/\/www.w3.org\/TR\/query-semantics\/."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1160074.1159829"},{"volume-title":"Proceedings of the 17th Annual IEEE Symposium on Logic Computer Science. IEEE Computer Society Press","author":"Frisch A.","key":"e_1_2_1_18_1","unstructured":"Frisch , A. , Castagna , G. , and Benzaken , V . 2002. Semantic subtyping . In Proceedings of the 17th Annual IEEE Symposium on Logic Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 137--146. Frisch, A., Castagna, G., and Benzaken, V. 2002. Semantic subtyping. In Proceedings of the 17th Annual IEEE Symposium on Logic Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 137--146."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391293"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2747"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060788"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796806005909"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1040305.1040310"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 8th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science","volume":"2759","author":"Hosoya H.","unstructured":"Hosoya , H. and Murata , M . 2003. Boolean operations and inclusion test for attribute-element constraints . In Proceedings of the 8th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science , vol. 2759 . Springer-Verlag, Berlin, Germany, 201--212. Hosoya, H. and Murata, M. 2003. Boolean operations and inclusion test for attribute-element constraints. In Proceedings of the 8th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science, vol. 2759. Springer-Verlag, Berlin, Germany, 201--212."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360209"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/767193.767195"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1053468.1053470"},{"key":"e_1_2_1_29_1","unstructured":"Ishikawa M. 2002. An XHTML + MathML + SVG Profile. http:\/\/www.w3.org\/TR\/XHTMLplusMathMLplusSVG\/xhtml-math-svg.html. Ishikawa M. 2002. An XHTML + MathML + SVG Profile. http:\/\/www.w3.org\/TR\/XHTMLplusMathMLplusSVG\/xhtml-math-svg.html."},{"key":"e_1_2_1_30_1","unstructured":"Jackson D. Ferraiolo J. and Fujisawa J. 2002. Scalable Vector Graphics (SVG) 1.1 Specification. http:\/\/www.w3.org\/TR\/2002\/CR-SVG11-20020430\/. Jackson D. Ferraiolo J. and Fujisawa J. 2002. Scalable Vector Graphics (SVG) 1.1 Specification. http:\/\/www.w3.org\/TR\/2002\/CR-SVG11-20020430\/."},{"volume-title":"Proceedings of the Programming Language Technologies for XML (PLAN-X). 87","author":"Kirkegaard C.","key":"e_1_2_1_31_1","unstructured":"Kirkegaard , C. and M\u00f8ller , A . 2006. XACT - XML transformations in Java . In Proceedings of the Programming Language Technologies for XML (PLAN-X). 87 . Kirkegaard, C. and M\u00f8ller, A. 2006. XACT - XML transformations in Java. In Proceedings of the Programming Language Technologies for XML (PLAN-X). 87."},{"key":"e_1_2_1_32_1","unstructured":"Leroy X. Doligez D. Garrigue J. Vouillon J. and R\u00e9my D. 1996. The Objective Caml system. Software and documentation available on the Web http:\/\/pauillac.inria.fr\/ocaml\/. Leroy X. Doligez D. Garrigue J. Vouillon J. and R\u00e9my D. 1996. The Objective Caml system. Software and documentation available on the Web http:\/\/pauillac.inria.fr\/ocaml\/."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065203"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_18"},{"key":"e_1_2_1_35_1","unstructured":"Meijer E. and Shields M. 1999. XM\u03bb: A functional programming language for constructing and manipulating XML documents. Manuscript. Meijer E. and Shields M. 1999. XM\u03bb: A functional programming language for constructing and manipulating XML documents. Manuscript."},{"key":"e_1_2_1_36_1","unstructured":"Milner R. Tofte M. and Harper R. 1990. The Definition of Standard ML. The MIT Press Cambridge MA. Milner R. Tofte M. and Harper R. 1990. The Definition of Standard ML. The MIT Press Cambridge MA."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335171"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375569"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Nottingham M. and Sayre R. 2005. The Atom Syndication Format (RFC 4287). ftp:\/\/ftp.rfc-editor.org\/in-notes\/rfc4287.txt. Nottingham M. and Sayre R. 2005. The Atom Syndication Format (RFC 4287). ftp:\/\/ftp.rfc-editor.org\/in-notes\/rfc4287.txt.","DOI":"10.17487\/rfc4287"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"OASIS. 2002. DocBook. http:\/\/www.docbook.org. OASIS. 2002. DocBook. http:\/\/www.docbook.org.","DOI":"10.1145\/504689.504690"},{"key":"e_1_2_1_41_1","unstructured":"OAS1S. 2007. Open Document Format for Office Applications (OpenDocument). http:\/\/www.oasis-open.org\/committees\/office\/. OAS1S. 2007. Open Document Format for Office Applications (OpenDocument). http:\/\/www.oasis-open.org\/committees\/office\/."},{"volume-title":"Proceedings of the UK Joint Framework for Information Technology (JFIT) Technical Conference.","author":"Peyton Jones S. L.","key":"e_1_2_1_42_1","unstructured":"Peyton Jones , S. L. , Hall , C. V. , Hammond , K. , Partain , W. , and Wadler , P . 1993. The Glasgow Haskell compiler: a technical overview . In Proceedings of the UK Joint Framework for Information Technology (JFIT) Technical Conference. Peyton Jones, S. L., Hall, C. V., Hammond, K., Partain, W., and Wadler, P. 1993. The Glasgow Haskell compiler: a technical overview. In Proceedings of the UK Joint Framework for Information Technology (JFIT) Technical Conference."},{"key":"e_1_2_1_43_1","unstructured":"Python XML Special Interest Group. 1998. The XML bookmark exchange language. http:\/\/pyxml.sourceforge.net\/topics\/xbel\/. Python XML Special Interest Group. 1998. The XML bookmark exchange language. http:\/\/pyxml.sourceforge.net\/topics\/xbel\/."},{"key":"e_1_2_1_44_1","first-page":"513","article-title":"Types, abstraction, and parametric polymorphism","volume":"83","author":"Reynolds J. C.","year":"1983","unstructured":"Reynolds , J. C. 1983 . Types, abstraction, and parametric polymorphism . Inf. Proc. 83 , 513 -- 523 . Reynolds, J. C. 1983. Types, abstraction, and parametric polymorphism. Inf. Proc. 83, 513--523.","journal-title":"Inf. Proc."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/360204.360230"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1994.316077"},{"volume-title":"The C++ Programming Language","author":"Stroustrup B.","key":"e_1_2_1_47_1","unstructured":"Stroustrup , B. 2000. The C++ Programming Language . Addison-Wesley , Reading, MA . Stroustrup, B. 2000. The C++ Programming Language. Addison-Wesley, Reading, MA."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/11605157_25"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.11.047"},{"volume-title":"XHaskell. In Proceedings of the Programming Language Technologies for XML (PLAN-X). 92","author":"Sulzmann M.","key":"e_1_2_1_50_1","unstructured":"Sulzmann , M. and Lu , K. Z. M. 2006b . XHaskell. In Proceedings of the Programming Language Technologies for XML (PLAN-X). 92 . Demonstration. Sulzmann, M. and Lu, K. Z. M. 2006b. XHaskell. In Proceedings of the Programming Language Technologies for XML (PLAN-X). 92. Demonstration."},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 8th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science","volume":"2759","author":"Tozawa A.","unstructured":"Tozawa , A. and Hagiya , M . 2003. XML schema containment checking based on semi-implicit techniques . In Proceedings of the 8th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science , vol. 2759 . Springer-Verlag, Berlin, Germany, 213--225. Tozawa, A. and Hagiya, M. 2003. XML schema containment checking based on semi-implicit techniques. In Proceedings of the 8th International Conference on Implementation and Application of Automata. Lecture Notes in Computer Science, vol. 2759. Springer-Verlag, Berlin, Germany, 213--225."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133651.1133652"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111037.1111047"},{"key":"e_1_2_1_54_1","volume-title":"PLAN-X '06, Proceedings of the 4th Workshop on Programming Language Technologies for XML. 49--60","author":"Vouillon J.","year":"2006","unstructured":"Vouillon , J. 2006 b. Polymorphism and XDuce-style patterns . In PLAN-X '06, Proceedings of the 4th Workshop on Programming Language Technologies for XML. 49--60 . Vouillon, J. 2006b. Polymorphism and XDuce-style patterns. In PLAN-X '06, Proceedings of the 4th Workshop on Programming Language Technologies for XML. 49--60."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/317636.317794"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1596527.1596529","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1596527.1596529","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:32Z","timestamp":1750249412000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1596527.1596529"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,10]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,10]]}},"alternative-id":["10.1145\/1596527.1596529"],"URL":"https:\/\/doi.org\/10.1145\/1596527.1596529","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2009,10]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-11-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}