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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hosoya, H., Pierce, B.C.: XDuce: A statically typed XML processing language. ACM Transactions on Internet Technology 3, 117–148 (2003)
Hosoya, H., Vouillon, J., Pierce, B.C.: Regular expression types for XML. In: Proceedings of the International Conference on Functional Programming, ICFP (2000)
Gapeyev, V., Pierce, B.C.: Regular object types. In: Cardelli, L. (ed.) ECOOP 2003. LNCS, vol. 2743, Springer, Heidelberg (2003); A preliminary version was presented at FOOL 2003
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), 961–1004 (2003)
W3C: XSL Transformations, XSLT (1999), http://www.w3.org/TR/xslt
XQuery 1.0: An XML Query Language, W3C Working Draft (2004), http://www.w3.org/TR/xquery/
Benzaken, V., Castagna, G., Frisch, A.: CDuce: An XML-centric general-purpose language. In: ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden, pp. 51–63 (2003)
Christensen, A.S., Kirkegaard, C., Møller, A.: A runtime system for XML transformations in java. In: Bellahsène, Z., Milo, T., Rys, M., Suciu, D., Unland, R. (eds.) XSym 2004. LNCS, vol. 3186, pp. 143–157. Springer, Heidelberg (2004)
Levin, M.Y.: Compiling regular patterns. In: ACM SIGPLAN International Conference on Functional Programming (ICFP), Uppsala, Sweden (2003)
Gapeyev, V., Levin, M.Y., Pierce, B.C., Schmitt, A.: XML goes native: Run-time representations for Xtatic. Technical Report MS-CIS-04-23, University of Pennsylvania (2004)
Gapeyev, V., Levin, M.Y., Pierce, B.C., Schmitt, A.: The Xtatic experience. Technical Report MS-CIS-04-24, University of Pennsylvania (2004)
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), pp. 1–18 (2002)
Kaplan, H., Okasaki, C., Tarjan, R.E.: Simple confluently persistent catenable lists. SIAM Journal on Computing 30, 965–977 (2000)
Franc, X.: Qizx (2003), http://www.xfra.net/qizxopen
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, pp. 974–985 (2002), see also http://www.xml-benchmark.org/
DataPower Technology, Inc.: XSLTMark (2001), http://www.datapower.com/xml_community/xsltmark.html
Kirkegaard, C., Møller, A., Schwartzbach, M.I.: Static analysis of XML transformations in Java. IEEE Transactions on Software Engineering 30, 181–192 (2004)
Meijer, E., Schulte, W., Bierman, G.: Programming with circles, triangles and rectangles. In: XML Conference and Exposition (2003)
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)
Kempa, M., Linnemann, V.: On XML objects. In: Workshop on Programming Language Technologies for XML, PLAN-X (2003)
Emir, B.: Extending pattern matching with regular tree expressions for XML processing in Scala. In: Diploma thesis, EPFL, Lausanne (2003), http://lamp.epfl.ch/~buraq
Kay, M.H.: Saxon: Anatomy of an xslt processor (2001), http://www-106.ibm.com/developerworks/library/x-xslt2/
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, pp. 32–46 (1980)
Sleep, M.R., Holmström, S.: A short note concerning lazy reduction rules for append. Software Practice and Experience 12, 1082–1084 (1982)
Keller, R.M.: Divide and CONCer: Data structuring in applicative multiprocessing systems. In: Proceedings of the 1980 ACM conference on LISP and functional programming, pp. 196–202 (1980)
Hughes, J.: A novel representation of lists and its application to the function ”reverse”. Information Processing Letters 22, 141–144 (1986)
Wadler, P.: The concatenate vanishes. Note, University of Glasgow (1987) (revised 1989)
Voigtländer, J.: Concatenate, reverse and map vanish for free. In: ACM SIGPLAN International Conference on Functional Programming (ICFP), Pittsburgh, Pennsylvania, pp. 14–25 (2002)
Sterling, L., Shapiro, E.: The Art of Prolog. MIT Press, Cambridge (1986)
Marriott, K., Søndergaard, H.: Difference-list transformation for prolog. New Generation Computing 11, 125–157 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gapeyev, V., Levin, M.Y., Pierce, B.C., Schmitt, A. (2005). XML Goes Native: Run-Time Representations for Xtatic . In: Bodik, R. (eds) Compiler Construction. CC 2005. Lecture Notes in Computer Science, vol 3443. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31985-6_4
Download citation
DOI: https://doi.org/10.1007/978-3-540-31985-6_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25411-9
Online ISBN: 978-3-540-31985-6
eBook Packages: Computer ScienceComputer Science (R0)