Source transformation, analysis and generation in TXL

ABSTRACT

The TXL transformation framework has been widely used in practical source transformation tasks in industry and academia for many years. At the core of the framework is the TXL language, a functional programming language specifically designed for expressing source transformation tasks. TXL programs are self-contained, specifying and implementing all aspects of parsing, pattern matching, transformation rules, application strategies and unparsing in a single uniform notation with no dependence on other tools or technologies. Programs are directly interpreted by the TXL processor without any compile or build step, making it particularly well suited to rapid turnaround, test-driven development. In this paper we provide a practical introduction to using TXL in rapidly developing source transformations from concrete examples, and review experience in applying TXL to a number of practical large scale applications in source code analysis, renovation and migration.

REFERENCES

• 1: Paul Anderson , Mark Zarins, The CodeSurfer Software Understanding Platform, Proceedings of the 13th International Workshop on Program Comprehension, p.147-148, May 15-16, 2005 [doi>10.1109/WPC.2005.37]
• 2: Ira D. Baxter, Design maintenance systems, Communications of the ACM, v.35 n.4, p.73-89, April 1992 [doi>10.1145/129852.129859]
• 3: Kent Beck , Cynthia Andres, Extreme Programming Explained: Embrace Change (2nd Edition), Addison-Wesley Professional, 2004
• 4: J. A. Bergstra , Jan Heering , Paul Klint, Algebraic specification, ACM Press, New York, NY, 1989
• 5: Mark G. J. van den Brand , Arie van Deursen , Jan Heering , H. A. de Jong , Merijn de Jonge , Tobias Kuipers , Paul Klint , Leon Moonen , Pieter A. Olivier , Jeroen Scheerder , Jurgen J. Vinju , Eelco Visser , Joost Visser, The ASF+SDF Meta-environment: A Component-Based Language Development Environment, Proceedings of the 10th International Conference on Compiler Construction, p.365-370, April 02-06, 2001
• 6: T. Cassidy, J. R. Cordy, T. Dean and J. Dingel, "Source Transformation for Concurrency Analysis", Proc. LDTA 2005, ACM 5th International Workshop on Language Descriptions, Tools and Applications, 26--43 (2005).
• 7: J. R. Cordy, "TXL - A Language for Programming Language Tools and Applications", Proc. LDTA 2004, ACM 4th International Workshop on Language Descriptions, Tools and Applications, Electronic Notes in Theoretical Computer Science110, 3--31 (2004).
• 8: J. R. Cordy, I. H. Carmichael and R. Halliday, The TXL Programming Language, Queen's University at Kingston (1988, rev. 2005).
• 9: J. R. Cordy and E. M. Promislow, "Specification and Automatic Prototype Implementation of Polymorphic Objects in Turing Using the TXL Dialect Processor", Proc. 1990 IEEE International Conference on Computer Languages, 145--154 (1990).
• 10: James R. Cordy , Charles D. Halpern-Hamu , Eric Promislow, TXL: a rapid prototyping system for programming language dialects, Computer Languages, v.16 n.1, p.97-107, 1991 [doi>10.1016/0096-0551(91)90019-6]
• 11: James R. Cordy , Medha Shukla, Practical metaprogramming, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
• 12: J. R. Cordy, T. R. Dean, A. J. Malton and K. A. Schneider, "Source Transformation in Software Engineering using the TXL Transformation System", Journal of Information and Software Technology44(13), 827--837 (2002).
• 13: HSML: Design Directed Source Code Hot Spots, Proceedings of the 9th International Workshop on Program Comprehension, p.145, May 12-13, 2001
• 14: Using Design Recovery Techniques to Transform Legacy Systems, Proceedings of the IEEE International Conference on Software Maintenance (ICSM'01), p.622, November 07-09, 2001
• 15: Thomas R. Dean , James R. Cordy , Andrew J. Malton , Kevin A. Schneider, Agile Parsing in TXL, Automated Software Engineering, v.10 n.4, p.311-336, October 2003 [doi>10.1023/A:1025801405075]
• 16: David Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.1, p.80-112, Jan. 1985 [doi>10.1145/2363.2433]
• 17: Patrice Godefroid, On the costs and benefits of using partial-order methods for the verification of concurrent systems (invited paper), Proceedings of the DIMACS workshop on Partial order methods in verification, p.289-303, February 1997, Princeton, New Jersey, United States
• 18: X. Guo, J. R. Cordy and T. R. Dean, "Unique Renaming of Java Using Source Transformation", Proc. SCAM 2003, IEEE 3rd International Workshop on Source Code Analysis and Manipulation, 151--160 (2003).
• 19: C. Halpern, "TXL: A Rapid Prototyping Tool for Programming Language Design", M.Sc. thesis, Department of Computer Science, University of Toronto (1986).
• 20: Richard C. Holt , James R. Cordy, The Turing programming language, Communications of the ACM, v.31 n.12, p.1410-1423, Dec. 1988 [doi>10.1145/53580.53581]
• 21: N. Kiyavitskaya, N. Zeni, J. R. Cordy, L. Mich and J. Mylopoulos, "Applying Software Analysis Technology to Lightweight Semantic Markup of Document Text", Proc. ICAPR 2005, 3rd International Conference on Advances in Pattern Recognition, Lecture Notes in Computter Science3686, 590--600 (2005).
• 22: David Alex Lamb , Kevin A. Schneider, Formalization of information hiding design methods, Proceedings of the 1992 conference of the Centre for Advanced Studies on Collaborative research, November 09-12, 1992, Toronto, Ontario, Canada
• 23: A. J. Malton, "The Denotational Semantics of a Functional Tree Manipulation Language", Computer Languages19(3), 157--168 (1993).
• 24: T. J. Parr , R. W. Quong, ANTLR: a predicated-LL(k) parser generator, Software—Practice & Experience, v.25 n.7, p.789-810, July 1995 [doi>10.1002/spe.4380250705]
• 25: Robert Paige, Viewing A Program Transformation System At Work, Proceedings of the 6th International Symposium on Programming Language Implementation and Logic Programming, p.5-24, September 14-16, 1994
• 26: R. Paige, "APTS External Specification Manual", Unpublished manuscript, available at http://www.cs.nyu.edu/jessie (1993).
• 27: R. Ramesh , I. V. Ramakrishnan, Nonlinear pattern matching in trees, Journal of the ACM (JACM), v.39 n.2, p.295-316, April 1992 [doi>10.1145/128749.128752]
• 28: O. Tal, S. Knight, and T. Dean, "Syntax-based Vulnerability Testing of Frame-based Network Protocols", Proc. 2nd Annual Conference on Privacy, Security and Trust (2004).
• 29: Masaru Tomita, An efficient augmented-context-free parsing algorithm, Computational Linguistics, v.13 n.1-2, p.31-46, January-June 1987
• 30: Eelco Visser, Stratego: A Language for Program Transformation Based on Rewriting Strategies, Proceedings of the 12th International Conference on Rewriting Techniques and Applications, p.357-362, May 22-24, 2001
• 31: E. Visser, "Program Transformation in Stratego/XT: Rules, Strategies, Tools and Systems in Stratego XT/0.9", Proc. Domain Specific Program Generation 2003, Lecture Notes in Computer Science3016, 216--238 (2004).
• 32: Richard Zanibbi , Dorothea Blostein , James R. Cordy, Recognizing Mathematical Expressions Using Tree Transformation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.11, p.1455-1467, November 2002 [doi>10.1109/TPAMI.2002.1046157 ]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.2 Automatic Programming
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Patterns
      D.3.4 Processors

General Terms:
Algorithms, Design, Languages

Keywords:
TXL, migration, rapid prototyping, re-engineering, rule-based programming, software analysis, source transformation, term rewriting, test-driven development, translators