Type-based specialization of xml transformations

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é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
• 2: Richard Bird, Introduction to Functional Programming, Pearson Education, 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: Claus Brabrand , Anders Møller , Michael I. Schwartzbach, Dual syntax for XML languages, Information Systems, v.33 n.4-5, p.385-406, June, 2008 [doi>10.1016/j.is.2008.01.006]
• 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: 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
• 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: Robert Glück , Masahiko Kawabe, Revisiting an automatic program inverter for Lisp, ACM SIGPLAN Notices, v.40 n.5, p.8-17, May 2005 [doi>10.1145/1071221.1071222]
• 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: 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]
• 17: Kazuhiro Inaba , Haruo Hosoya , Sebastian Maneth, Multi-Return Macro Tree Transducers, Proceedings of the 13th international conference on Implementation and Applications of Automata, July 21-24, 2008, San Franciscon, CA, USA [doi>10.1007/978-3-540-70844-5_11]
• 18: Michael Y. Levin , Benjamin C. Pierce, Run, xtatic, run: efficient implementation of an object-oriented language with regular pattern matching, University of Pennsylvania, Philadelphia, PA, 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 , 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 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: Kazutaka Matsuda , Zhenjiang Hu , Keisuke Nakano , Makoto Hamana , Masato Takeichi, Bidirectionalization transformation based on automatic derivation of view complement functions, Proceedings of the 12th ACM SIGPLAN international conference on Functional programming, October 01-03, 2007, Freiburg, Germany
• 25: 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]
• 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: Makoto Murata , Dongwon Lee , Murali Mani , Kohsuke Kawaguchi, Taxonomy of XML schema languages using formal language theory, ACM Transactions on Internet Technology (TOIT), v.5 n.4, p.660-704, November 2005 [doi>10.1145/1111627.1111631]
• 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: Thomas Perst , Helmut Seidl, Macro forest transducers, Information Processing Letters, v.89 n.3, p.141-149, 14 February 2004 [doi>10.1016/j.ipl.2003.05.001]
• 31: E. L. Post. A variant of a recursively unsolvable problem. Bulletin of the American Mathematical Society, 52(4):264--268, 1946.
• 32: Philip Wadler, Deforestation: transforming programs to eliminate trees, Theoretical Computer Science, v.73 n.2, p.231-248, June 22, 1990

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.1 Applicative (Functional) Programming

General Terms:
Languages

Keywords:
program specialization, tree automata, types, xml