Article

XML goes native: run-time representations for XTATIC

Authors:

Vladimir Gapeyev,

Michael Y. Levin,

Benjamin C. Pierce,

Alan SchmittAuthors Info & Claims

CC'05: Proceedings of the 14th international conference on Compiler Construction

Pages 43 - 58

https://doi.org/10.1007/978-3-540-31985-6_4

Published: 04 April 2005 Publication History

Abstract

Xtatic is a lightweight extension of C^# offering native support for statically typed XML processing. XML trees are built-in values in Xtatic, and static analysis of the trees manipulated by programs is part of the ordinary job of the typechecker. “Tree grep” pattern matching is used to investigate and transform XML trees. Xtatic's surface syntax and type system are tightly integrated with those of C^#. Beneath the hood, however, an implementation of Xtatic must address a number of issues common to any language supporting a declarative style of XML processing (e.g., XQuery, XSLT, XDuce, CDuce, Xact, Xen, etc.). In particular, it must provide representations for XML tags, trees, and textual data that use memory efficiently, support efficient pattern matching, allow maximal sharing of common substructures, and permit separate compilation. We analyze these representation choices in detail and describe the solutions used by the Xtatic compiler.

References

[1]

Hosoya, H., Pierce, B.C.: XDuce: A statically typed XML processing language. ACM Transactions on Internet Technology 3 (2003) 117-148

Digital Library

[2]

Hosoya, H., Vouillon, J., Pierce, B.C.: Regular expression types for XML. In: Proceedings of the International Conference on Functional Programming (ICFP). (2000)

Digital Library

[3]

Gapeyev, V., Pierce, B.C.: Regular object types. In: European Conference on Object-Oriented Programming (ECOOP), Darmstadt, Germany. (2003) A preliminary version was presented at FOOL '03.

[4]

Hosoya, H., Pierce, B.C.: Regular expression pattern matching. In: ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), London, England. (2001) Full version in Journal of Functional Programming, 13(6), Nov. 2003, pp. 961-1004.

Digital Library

[5]

W3C: XSL Transformations (XSLT) (1999) http://www.w3.org/TR/xslt.

[6]

XQuery 1.0: An XML Query Language, W3C Working Draft (2004) http://www.w3.org/TR/xquery/.

[7]

Benzaken, V., Castagna, G., Frisch, A.: CDuce: An XML-centric general-purpose language. In: ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden. (2003) 51-63

Digital Library

[8]

Christensen, A.S., Kirkegaard, C., Møller, A.: A runtime system for XML transformations in Java. In Bellahsène, Z., Milo, T., Michael Rys, e.a., eds.: Database and XML Technologies: International XML Database Symposium (XSym). Volume 3186 of Lecture Notes in Computer Science., Springer (2004) 143-157

[9]

Levin, M.Y.: Compiling regular patterns. In: ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden. (2003)

Digital Library

[10]

Gapeyev, V., Levin, M.Y., Pierce, B.C., Schmitt, A.: XML goes native: Runtime representations for Xtatic. Technical Report MS-CIS-04-23, University of Pennsylvania (2004)

[11]

Gapeyev, V., Levin, M.Y., Pierce, B.C., Schmitt, A.: The Xtatic experience. Technical Report MS-CIS-04-24, University of Pennsylvania (2004)

[12]

Tabuchi, N., Sumii, E., Yonezawa, A.: Regular expression types for strings in a text processing language. In den Bussche, J.V., Vianu, V., eds.: Proceedings of Workshop on Types in Programming (TIP). (2002) 1-18

[13]

Kaplan, H., Okasaki, C., Tarjan, R.E.: Simple confluently persistent catenable lists. SIAM Journal on Computing 30 (2000) 965-977

Digital Library

[14]

Franc, X.: Qizx. http://www.xfra.net/qizxopen (2003)

[15]

Schmidt, A.R., Waas, F., Kersten, M.L., Carey, M.J., Manolescu, I., Busse, R.: XMark: A benchmark for XML data management. In: Proceedings of the International Conference on Very Large Data Bases (VLDB), Hong Kong, China (2002) 974-985 See also http://www.xml-benchmark.org/.

Digital Library

[16]

DataPower Technology, Inc.: XSLTMark. http://www.datapower.com/xml community/xsltmark.html (2001)

[17]

Kirkegaard, C., Møller, A., Schwartzbach, M.I.: Static analysis of XML transformations in Java. IEEE Transactions on Software Engineering 30 (2004) 181-192

Digital Library

[18]

Meijer, E., Schulte, W., Bierman, G.: Programming with circles, triangles and rectangles. In: XML Conference and Exposition. (2003)

[19]

Harren, M., Raghavachari, B.M., Shmueli, O., Burke, M., Sarkar, V., Bordawekar, R.: XJ: Integration of XML processing into Java. Technical Report rc23007, IBM Research (2003)

[20]

Kempa, M., Linnemann, V.: On XML objects. In: Workshop on Programming Language Technologies for XML (PLAN-X). (2003)

[21]

Emir, B.: Extending pattern matching with regular tree expressions for XML processing in Scala. Diploma thesis, EPFL, Lausanne; http://lamp.epfl.ch/ ~buraq (2003)

[22]

Kay, M.H.: Saxon: Anatomy of an xslt processor (2001) http://www-106.ibm.com/developerworks/library/x-xslt2/.

[23]

Morris, J.H., Schmidt, E., Wadler, P.: Experience with an applicative string processing language. In: ACM Symposium on Principles of Programming Languages (POPL), Las Vegas, Nevada. (1980) 32-46

Digital Library

[24]

Sleep, M.R., Holmström, S.: A short note concerning lazy reduction rules for append. Software Practice and Experience 12 (1982) 1082-4

[25]

Keller, R.M.: Divide and CONCer: Data structuring in applicative multiprocessing systems. In: Proceedings of the 1980 ACM conference on LISP and functional programming. (1980) 196-202

Digital Library

[26]

Hughes, J.: A novel representation of lists and its application to the function "reverse". Information Processing Letters 22 (1986) 141-144

Digital Library

[27]

Wadler, P.: The concatenate vanishes. Note, University of Glasgow (1987) (revised 1989).

[28]

Voigtländer, J.: Concatenate, reverse and map vanish for free. In: ACM SIGPLAN International Conference on Functional Programming (ICFP), Pittsburgh, Pennsylvania. (2002) 14-25

Digital Library

[29]

Sterling, L., Shapiro, E.: The Art of Prolog. MIT Press (1986)

[30]

Marriott, K., Søndergaard, H.: Difference-list transformation for prolog. New Generation Computing 11 (1993) 125-157

Cited By

Busatto GLohrey MManeth S(2008)Efficient memory representation of XML document treesInformation Systems10.1016/j.is.2008.01.00433:4-5(456-474)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.is.2008.01.004
Coupey PFouqueré CLoddo J(2007)Tree components programmingProceedings of the 4th international conference on Theoretical aspects of computing10.5555/1777259.1777269(139-153)Online publication date: 26-Sep-2007
https://dl.acm.org/doi/10.5555/1777259.1777269
Hirzel MGrimm R(2007)JeannieACM SIGPLAN Notices10.1145/1297105.129703042:10(19-38)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297105.1297030
Show More Cited By

Recommendations

XML: Visual QuickStart Guide
Definitive XML Schema
Native XML support in DB2 universal database
VLDB '05: Proceedings of the 31st international conference on Very large data bases

The major relational database systems have been providing XML support for several years, predominantly by mapping XML to existing concepts such as LOBs or (object-)relational tables. The limitations of these approaches are well known in research and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

CC'05: Proceedings of the 14th international conference on Compiler Construction

April 2005

304 pages

ISBN:3540254110

Editor:
Rastislav Bodik
Computer Science Division, University of California, #1776, Berkeley, CA

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 04 April 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Busatto GLohrey MManeth S(2008)Efficient memory representation of XML document treesInformation Systems10.1016/j.is.2008.01.00433:4-5(456-474)Online publication date: 1-Jun-2008
https://dl.acm.org/doi/10.1016/j.is.2008.01.004
Coupey PFouqueré CLoddo J(2007)Tree components programmingProceedings of the 4th international conference on Theoretical aspects of computing10.5555/1777259.1777269(139-153)Online publication date: 26-Sep-2007
https://dl.acm.org/doi/10.5555/1777259.1777269
Hirzel MGrimm R(2007)JeannieACM SIGPLAN Notices10.1145/1297105.129703042:10(19-38)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297105.1297030
Hirzel MGrimm RGabriel RBacon DLopes CSteele G(2007)JeannieProceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems, languages and applications10.1145/1297027.1297030(19-38)Online publication date: 21-Oct-2007
https://dl.acm.org/doi/10.1145/1297027.1297030
Lämmel RMeijer E(2006)Revealing the X/O impedance mismatchProceedings of the 2006 international conference on Datatype-generic programming10.5555/1782894.1782900(285-367)Online publication date: 24-Apr-2006
https://dl.acm.org/doi/10.5555/1782894.1782900
Sulzmann MLu K(2006)A Type-Safe Embedding of XDuce into MLElectronic Notes in Theoretical Computer Science (ENTCS)10.1016/j.entcs.2005.11.047148:2(239-264)Online publication date: 1-Mar-2006
https://dl.acm.org/doi/10.1016/j.entcs.2005.11.047
Møller ASchwartzbach M(2005)The design space of type checkers for XML transformation languagesProceedings of the 10th international conference on Database Theory10.1007/978-3-540-30570-5_2(17-36)Online publication date: 5-Jan-2005
https://dl.acm.org/doi/10.1007/978-3-540-30570-5_2

View Options

View options

Media

Figures

Other

Tables

View Table of Contents