Program Transformation with Scoped Dynamic Rewrite Rules

• Autorzy: Bravenboer M. , Dam A. van , Olmos K. , Visser E.
• Języki publikacji: EN

Abstrakty

EN

The applicability of term rewriting to program transformation is limited by the lack of control over rule application and by the context-free nature of rewrite rules. The first problem is addressed by languages supporting user-definable rewriting strategies. The second problem is addressed by the extension of rewriting strategies with scoped dynamic rewrite rules. Dynamic rules are defined at run-time and can access variables available from their definition context. Rules defined within a rule scope are automatically retracted at the end of that scope. In this paper, we explore the design space of dynamic rules, and their application to transformation problems. The technique is formally defined by extending the operational semantics underlying the program transformation language Stratego, and illustrated by means of several program transformations in Stratego, including constant propagation, bound variable renaming, dead code elimination, function inlining, and function specialization.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 69, nr 1,2
• Strony: 123--178
• Opis fizyczny: bibliogr. 47 poz.

Twórcy

autor

Bravenboer M.

autor

Dam A. van

autor

Olmos K.

autor

Visser E.

• Department of Information and Computing Sciences, Utrecht University P.O. Box 80089, 3508 TB Utrecht, The Netherlands,

Bibliografia

• [1] A. Aho, R. Sethi, and J. Ullman. Compilers: Principles, techniques, and tools. Addison Wesley, Reading, Massachusetts, 1986.
• [2] A. W. Appel. Modern Compiler Implementation in ML. Cambridge University Press, 1998.
• [3] A. W. Appel and T. Jim. Shrinking lambda expressions in linear time. Journal of Functional Programming, 7(5):515-540, September 1997.
• [4] P. Borovansky, C. Kirchner, and H. Kirchner. Controlling rewriting by rewriting. In J. Meseguer, editor, Proceedings of the First International Workshop on Rewriting Logic and its Applications, volume 4 of Electronic Notes in Theoretical Computer Science, Asilomar, Pacific Grove, CA, September 1996. Elsevier Science Publishers.
• [5] J. M. Boyle, T. J. Harmer, and V. L. Winter. The TAMPR program transforming system: Simplifying the development of numerical software. In E. Arge, A. M. Bruaset, and H. P. Langtangen, editors, Modern Software Tools in Scientific Computing, pages 353-372. Birkhuser, 1997.
• [6] M. G. J. van den Brand, H. de Jong, P. Klint, and P. Olivier. Efficient annotated terms. Software, Practice & Experience, 30(3):259-291, 2000.
• [7] M. G. J. van den Brand, P. Klint, and J. J. Vinju. Term rewriting with traversal functions. ACM Transactions on Software Engineering and Methodology, 12(2):152-190, 2003.
• [8] M. Bravenboer, A. van Dam, K. Olmos, and E. Visser. Program transformation with scoped dynamic rewrite rules. Technical Report UU-CS-2005-005, Department of Information and Computing Sciences, Utrecht University, 2005. Extended version of this article with appendices on implementation and performance.
• [9] M. Bravenboer and E. Visser. Rewriting strategies for instruction selection. In S. Tison, editor, Rewriting Techniques and Applications (RTA'02), volume 2378 of Lecture Notes in Computer Science, pages 237-251, Copenhagen, Denmark, July 2002. Springer-Verlag.
• [10] J. Cocke and J. T. Schwartz. Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University, April 1970.
• [11] P. Cousot and R. Cousot. Systematic design of programtransformation frameworks by abstract interpretation. In ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'02), pages 178-190, Portland, Oregon, USA, January 2002. ACM Press.
• [12] E. Dolstra and E. Visser. Building interpreters with rewriting strategies. In M. G. J. van den Brand and R. Lmmel, editors, Workshop on Language Descriptions, Tools and Applications (LDTA'02), volume 65/3 of Electronic Notes in Theoretical Computer Science, Grenoble, France, April 2002. Elsevier Science Publishers.
• [13] J. Eaton. Octave, http://www.octave.org
• [14] M. Fowler. Refactoring: Improving the Design of Existing Programs. Addison-Wesley, 1999.
• [15] C. Hanson. MIT/GNU Scheme reference. http://www.gnu.org/software//mit-scheme/documentation/scheme.html , 2003.
• [16] D. R. Hanson and T. A. Proebsting. Dynamic variables. In Programming Language Design and Implementation (PLDI'01), Snowbird, UT, USA, June 2001. ACM.
• [17] N. Jones, C. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993.
• [18] M. Kay. XSL Transformations (XSLT) Version 2.0,W3C Working Draft 12 November 2003. WorldWideWeb Consortium, November 2003. http://www.w3.org/TR/xslt20/
• [19] S. Lerner, D. Grove, and C. Chambers. Combining dataflow analyses and transformations. In SIGPLAN Symposium on Principles of Programming Languages (POPL 2002), pages 270-282, Portland, Oregon, January 2002.
• [20] J. Lewis. The hugs 98 user's guide: Implicit parameters. http://www.cvs.haskell.org/Hugs/pages/users/_guide/implicit-parameters.htlm, 2003.
• [21] J. R. Lewis, J. Launchbury, E. Meijer, and M. Shields. Implicit parameters: Dynamic scoping with static types. In Symposium on Principles of Programming Languages (POPL'00), pages 108-118. ACM, January 2000.
• [22] B. Luttik and E. Visser. Specification of rewriting strategies. In M. P. A. Sellink, editor, 2nd International Workshop on the Theory and Practice of Algebraic Specifications (ASF+SDF'97), Electronic Workshops in Computing, Berlin, November 1997. Springer-Verlag.
• [23] J. McCarthy. History of LISP. In R. L. Wexelblat, editor, History of Programming Languages: Proceedings of the ACM SIGPLAN Conference, pages 173-197. Academic Press, June 1-3 1978.
• [24] S. S. Muchnick. Advanced Compiler Design and Implementation. Morgan Kaufmann Publishers, 1997.
• [25] K. Olmos and R. Vermaas. The Stratego Octave Compiler. http://www.octave-compiler.org, 2003- 2005.
• [26] K. Olmos and E. Visser. Strategies for source-to-source constant propagation. In B. Gramlich and S. Lucas, editors,Workshop on Reduction Strategies (WRS'02), volume 70 of Electronic Notes in Theoretical Computer Science, page 20, Copenhagen, Denmark, July 2002. Elsevier Science Publishers.
• [27] K. Olmos and E. Visser. Composing source-to-source data-flow transformations with rewriting strategies and dependent dynamic rewrite rules. In R. Bodik, editor, 14th International Conference on Compiler Construction (CC'05), volume 3443 of Lecture Notes in Computer Science, pages 204-220. Springer-Verlag, April 2005.
• [28] W. F. Opdyke. Refactoring Object-Oriented Frameworks. PhD thesis, University of Illinois, Urbana-Champaign, IL, USA, 1992.
• [29] R. Paige. Future directions in program transformations. Computing Surveys, 28A(4), December 1996.
• [30] A. Pettorossi and M. Proietti. Future directions in program transformation. ACM Computing Surveys, 28(4es):171-es, December 1996. Position Statement at the Workshop on Strategic Directions in Computing Research. MIT, Cambridge,MA, USA, June 14-15, 1996.
• [31] S. Peyton Jones and S. Marlow. Secrets of the Glasgow Haskell Compiler inliner. Journal of Functional Programming, 12(4):393-434, July 2002.
• [32] A. M. Pitts and M. J. Gabbay. A metalanguage for programming with bound names modulo renaming. In R. Backhouse and J. N. Oliveira, editors, Mathematics of Program Construction. 5th International Conference, MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings, volume 1837 of Lecture Notes in Computer Science, pages 230-255. Springer-Verlag, 2000.
• [33] G. Schadow. Request for dynamically scoped variables in XSLT. http://www.lists.w3.org/Archives/Public/xsl-editors/2002JanMar/0002.html, 2002.
• [34] M. R. Shinwell, A. M. Pitts, and M. J. Gabbay. FreshML: Programming with binders made simple. In Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, pages 263-274. ACM Press, Aug. 2003.
• [35] Terese. Term Rewriting Systems, volume 55 of Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 2003.
• [36] E. Visser. Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam, September 1997.
• [37] E. Visser. Strategic pattern matching. In P. Narendran and M. Rusinowitch, editors, Rewriting Techniques and Applications (RTA'99), volume 1631 of Lecture Notes in Computer Science, pages 30-44, Trento, Italy, July 1999. Springer-Verlag.
• [38] E. Visser. Language independent traversals for program transformation. In J. Jeuring, editor, Workshop on Generic Programming (WGP'00), Ponte de Lima, Portugal, July 2000. Technical Report UU-CS-2000-19, Department of Information and Computing Sciences, Universiteit Utrecht.
• [39] E. Visser. Scoped dynamic rewrite rules. In M. van den Brand and R. Verma, editors, Rule Based Programming (RULE'01), volume 59/4 of Electronic Notes in Theoretical Computer Science. Elsevier Science Publishers, September 2001.
• [40] E. Visser. Meta-programming with concrete object syntax. In D. Batory, C. Consel, and W. Taha, editors, Generative Programming and Component Engineering (GPCE'02), volume 2487 of Lecture Notes in Computer Science, pages 299-315, Pittsburgh, PA, USA, October 2002. Springer-Verlag.
• [41] E. Visser. Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9. In C. Lengauer et al., editors, Domain-Specific Program Generation, volume 3016 of Lecture Notes in Computer Science, pages 216-238. Spinger-Verlag, June 2004.
• [42] E. Visser. A survey of strategies in rule-based program transformation systems. Journal of Symbolic Computation, 40(1):831-873, 2005. Reduction Strategies in Rewriting and Programming special issue.
• [43] E. Visser and Z.-e.-A. Benaissa. A core language for rewriting. In C. Kirchner and H. Kirchner, editors, Second International Workshop on Rewriting Logic and its Applications (WRLA'98), volume 15 of Electronic Notes in Theoretical Computer Science, Pont-`a-Mousson, France, September 1998. Elsevier Science Publishers.
• [44] E. Visser, Z.-e.-A. Benaissa, and A. Tolmach. Building program optimizers with rewriting strategies. In Proceedings of the third ACM SIGPLAN International Conference on Functional Programming (ICFP'98), pages 13-26. ACM Press, September 1998.
• [45] E. Visser, M. Bravenboer, and K. Olmos. Implementation of partial evaluation in Stratego/XT. Presentation at Functional Refactoring Workshop in Canterbury, Kent, UK, February 9 2004. http://www.cs.uu.nl/wiki/Visser/ResearchTalks
• [46] E. Visser et al. Stratego/XT http://www.stratego-language.org, 1999-2005.
• [47] M. Wegman and F. Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13:181-210, April 1991.