skip to main content
10.1145/1480945.1480955acmconferencesArticle/Chapter ViewAbstractPublication PagespepmConference Proceedingsconference-collections
research-article

Type-based specialization of xml transformations

Published: 19 January 2009 Publication History

Abstract

It is often convenient to write a function and apply it to a specific input. However, a program developed in this way may be inefficient to evaluate and difficult to analyze due to its generality. In this paper, we propose a technique of new specialization for a class of XML transformations, in which no output of a function can be decomposed or traversed. Our specialization is type-based in the sense that it uses the structures of input types; types are described by regular hedge grammars and subtyping is defined set-theoretically. The specialization always terminates, resulting in a program where every function is fully specialized and only accepts its rigid input. We present several interesting applications of our new specialization, especially for injectivity analysis.

References

[1]
V. Benzaken, G. Castagna, and A. Frisch. CDuce: an XML-centric generalpurpose language. In ICFP '03: Proceedings of the 2003 ACM SIGPLAN international conference on Functional programming, pages 51--63, 2003.
[2]
R. S. Bird. Introduction to Functional Programming Using Haskell. Prentice Hall, 1998.
[3]
C. Brabrand, R. Giegerich, and A. Moller. Analyzing ambiguity of contextfree grammars. In Proceedings of 12th International Conference on Implementation and Application of Automata, CIAA '07, volume 4783 of LNCS. Springer-Verlag, July 2007.
[4]
C. Brabrand, A. Moller, and M. I. Schwartzbach. Dual syntax for XML languages. Information Systems, 33(4), June 2008. Earlier version in Proc. 10th International Workshop on Database Programming Languages, DBPL '05, Springer-Verlag LNCS vol. 3774.
[5]
P. Bunneman and B. C. Pierce. Union types for seminstrcutred data. Technical Report MS-CIS-99-09, University of Pennsylvania Department of Computer and Information Science, 1999.
[6]
H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http://www.grappa.univ-lille3.fr/tata, 1997. release October, 1st 2002.
[7]
J. Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory, 10:289--303, 1977.
[8]
J. Engelfriet and S. Maneth. A comparison of pebble tree transducers with macro tree transducers. Acta Informatica, 39(9):613.698, 2003.
[9]
D. Eppstein. A heuristic approach to program inversion. In International Joint Conference on Artificial Intelligence (IJCAI-85), pages 219--221, 1985.
[10]
A. Frisch. Regular tree language recognition with static information. In Exploring New Frontiers of Theoretical Informatics, IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004), pages 661--674, 2004.
[11]
A. Frisch, G. Castagna, and V. Benzaken. Semantic subtyping. In LICS '02: Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, pages 137--146, Washington, DC, USA, 2002. IEEE Computer Society.
[12]
R. Gluck and M. Kawabe. Derivation of deterministic inverse programs based on LR parsing. In FLOPS '04: The Seventh International Symposium on Functional and Logic Programming, pages 291--306, 2004.
[13]
R. Gluck and M. Kawabe. Revisiting an automatic program inverter for lisp. SIGPLAN Notices, 40(5):8.17, 2005.
[14]
D. Gries. The Science of Programming, chapter 21 Inverting Programs. Springer, 1981.
[15]
H. Hosoya. Regular expression pattern matching. a simpler design. Technical Report 1397, RIMS, Kyoto University, 2003.
[16]
H. Hosoya and B. C. Pierce. XDuce: A statically typed XML processing language. ACM Trans. Internet Technol., 3(2):117--148, 2003.
[17]
K. Inaba, H. Hosoya, and S. Maneth. Multi-return macro tree transducers. In Proceedings of 13th International Conference on Implementation and Application of Automata, CIAA '08, pages 102--111, 2008.
[18]
M. Y. Levin. Run, Xtatic, Run: Efficient Implementation of an Object-Oriented Language with Regular Pattern Matching. PhD thesis, University of Pennsylvania, 2005.
[19]
M. Y. Levin and B. C. Pierce. Type-based optimization for regular patterns. In DBPL '05: Proceedings of 10th International Symposium on Database Programming Languages, pages 184--198, 2005.
[20]
S. Maneth. The macro tree transducer hierarchy collapses for functions of linear size increase. In FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, pages 326--337, 2003.
[21]
S. Maneth, A. Berlea, T. Perst, and H. Seidl. XML type checking with macro tree transducers. In PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 283--294, 2005.
[22]
S. Maneth and K. Nakano. XML type checking for macro tree transducers with holes. In PLAN-X '08: Programming Languages Technologies for XML, 2008.
[23]
S. Maneth, T. Perst, and H. Seidl. Exact XML type checking in polynomial time. In ICDT '07: Proceedings of the 11th International Conference of Database Theory, volume 4353 of LNCS, pages 254--268, 2007.
[24]
K. Matsuda, Z. Hu, K. Nakano, M. Hamana, and M. Takeichi. Bidirectionalization transformation based on automatic derivation of view complement functions. In ICFP '07: Proceedings of the 2007 ACM SIGPLAN international conference on Functional programming, pages 47--58, New York, NY, USA, 2007. ACM.
[25]
T. Milo, D. Suciu, and V. Vianu. Typechecking for XML transformers. Journal of Computer and System Sciences, 66(1):66--97, 2003.
[26]
M. Mohri and M.-J. Nederhof. Regular approximation of context-free grammars through transformation. In J.-C. Junqua and G. van Noord, editors, Robusteness in Language and Speech Technology. Kluwer Academic Publishers, The Netherlands, 2001.
[27]
Murata. Hedge automata: a formal model for XML schemata, 1999. Available on: http://www.xml.gr.jp/relax/hedge_nice.html.
[28]
M. Murata, D. Lee, M. Mani, and K. Kawaguchi. Taxonomy of XML schema languages using formal language theory. ACM Trans. Internet Technol., 5(4):660--704, 2005.
[29]
N. Nishida, M. Sakai, and T. Sakabe. Generation of inverse term rewriting systems for pure treeless functions. In Y. Toyama, editor, Proceedings of the International Workshop on Rewriting in Proof and Computation (RPC'01), pages 188--198, 10 2001.
[30]
T. Perst and H. Seidl. Macro forest transducers. Information Processsing Letters, 89(3):141--149, 2004.
[31]
E. L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264--268, 1946.
[32]
P. Wadler. Deforestation: Transforming programs to eliminate trees. Theoretical Computer Science, 73(2):231--248, 1990.

Cited By

View all
  • (2013)Polynomial-time inverse computation for accumulative functions with multiple data traversalsHigher-Order and Symbolic Computation10.1007/s10990-013-9097-825:1(3-38)Online publication date: 25-Sep-2013
  • (2012)Polynomial-time inverse computation for accumulative functions with multiple data traversalsProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103752(5-14)Online publication date: 23-Jan-2012
  • (2012)Typing model transformations using tractsProceedings of the 5th international conference on Theory and Practice of Model Transformations10.1007/978-3-642-30476-7_4(56-71)Online publication date: 28-May-2012
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation
January 2009
208 pages
ISBN:9781605583273
DOI:10.1145/1480945
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 January 2009

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. program specialization
  2. tree automata
  3. types
  4. xml

Qualifiers

  • Research-article

Conference

PEPM '09
Sponsor:
PEPM '09: Partial Evaluation and Program Manipulation
January 19 - 20, 2009
GA, Savannah, USA

Acceptance Rates

Overall Acceptance Rate 66 of 120 submissions, 55%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)1
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2013)Polynomial-time inverse computation for accumulative functions with multiple data traversalsHigher-Order and Symbolic Computation10.1007/s10990-013-9097-825:1(3-38)Online publication date: 25-Sep-2013
  • (2012)Polynomial-time inverse computation for accumulative functions with multiple data traversalsProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103752(5-14)Online publication date: 23-Jan-2012
  • (2012)Typing model transformations using tractsProceedings of the 5th international conference on Theory and Practice of Model Transformations10.1007/978-3-642-30476-7_4(56-71)Online publication date: 28-May-2012
  • (2010)The view update problem for XMLProceedings of the 2010 EDBT/ICDT Workshops10.1145/1754239.1754262(1-9)Online publication date: 22-Mar-2010
  • (2010)Three complementary approaches to bidirectional programmingProceedings of the 2010 international spring school conference on Generic and Indexed Programming10.1007/978-3-642-32202-0_1(1-46)Online publication date: 22-Mar-2010

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media