article

The TXL source transformation language

Author:

James R. CordyAuthors Info & Claims

Science of Computer Programming, Volume 61, Issue 3

Pages 190 - 210

https://doi.org/10.1016/j.scico.2006.04.002

Published: 01 August 2006 Publication History

Abstract

TXL is a special-purpose programming language designed for creating, manipulating and rapidly prototyping language descriptions, tools and applications. TXL is designed to allow explicit programmer control over the interpretation, application, order and backtracking of both parsing and rewriting rules. Using first order functional programming at the higher level and term rewriting at the lower level, TXL provides for flexible programming of traversals, guards, scope of application and parameterized context. This flexibility has allowed TXL users to express and experiment with both new ideas in parsing, such as robust, island and agile parsing, and new paradigms in rewriting, such as XML mark-up, rewriting strategies and contextualized rules, without any change to TXL itself. This paper outlines the history, evolution and concepts of TXL with emphasis on its distinctive style and philosophy, and gives examples of its use in expressing and applying recent new paradigms in language processing.

References

[1]

{1} G. Adelson-Velskii, E. Landis, An algorithm for the organization of the information, Soviet Mathematics Dokay 3 (1962) 1259-1263.]]

[2]

{2} M. Auguston, RIGAL--A programming language for compiler writing, Lecture Notes in Computer Science 502 (1991) 529-564.]]

Digital Library

[3]

{3} D.T. Barnard, R.C. Holt, Hierarchic syntax error repair for LR grammars, International Journal of Computing and Information Sciences 11 (4) (1982) 231-258.]]

[4]

{4} D.T. Barnard, Automatic generation of syntax-repairing and paragraphing parsers, Technical Report CSRG-52, Computer Systems Research Group, University of Toronto, 1975, 132 pp.]]

[5]

{5} I.D. Baxter, Parallel support for source code analysis and modification, in: Proc. IEEE 2nd International Workshop on Source Code Analysis and Manipulation, 2002, pp. 3-15.]]

[6]

{6} J.A. Bergstra, J. Heering, P. Klint, Algebraic Specification, ACM, 1989.]]

[7]

{7} T.J. Biggerstaff, Design recovery for maintenance and reuse, IEEE Computer 22 (7) (1989) 36-49.]]

Digital Library

[8]

{8} D. Blostein, J.R. Cordy, R. Zanibbi, Applying compiler techniques to diagram recognition, in: Proc. 16th IAPR International Conference on Pattern Recognition, 3, 2002, pp. 127-130.]]

[9]

{9} P. Borovansky, C. Kirchner, H. Kirchner, P.E. Moreau, C. Ringeissen, An overview of ELAN, in: Proc. 2nd International Workshop on Rewriting Logic and its Applications, WRLA'98, Electronic Notes in Theoretical Computer Science 15 (1998) 55-70.]]

[10]

{10} M. Bravenboer, A. van Dam, K. Olmos, E. Visser, Program transformation with dynamically scoped rewrite rules, Fundamenta Informaticae 69 (1) (2005) 1-56.]]

[11]

{11} M. van den Brand, J. Heering, P. Klint, P.A. Olivier, Compiling language definitions: The ASF + SDF compiler, ACM Transactions on Programming Languages and Systems 24 (4) (2002) 334-368.]]

Digital Library

[12]

{12} M. van den Brand, P. Klint, J.J. Vinju, Term rewriting with traversal functions, ACM Transactions on Software Engineering and Methodology 12 (2) (2003) 152-190.]]

Digital Library

[13]

{13} M. van den Brand, J. Scheerder, J.J. Vinju, E. Visser, Disambiguation filters for scannerless generalized LR parsers, in: Proc. 11th International Conference on Compiler Construction, 2002, pp. 143-158.]]

[14]

{14} T. Bray, A. Paoli, C.M. Sperberg-McQueen (Eds.), Extensible Markup Language (XML) 1.0, http://www.w3.org/TR/1998/REC-xml- 19980210.pdf, 1998.]]

[15]

{15} J. Cai, R. Paige, Towards increased productivity of algorithm implementation, ACM Software Engineering Notes 18 (5) (1993) 71-78.]]

Digital Library

[16]

{16} I. Carmichael, TXL: Experiments with pattern-directed tree transformation as a programming paradigm, M.Sc. Thesis, Department of Computing and Information Science, Qujeen's University, Kingston, 1990.]]

[17]

{17} J. Clark (Ed.), XSL Transformations (XSLT) Version 1.0', W3C Recommendation http://www.w3.org/TR/1999/REC-xslt-19991116, 1999.]]

[18]

{18} J.R. Cordy, I.H. Carmichael, R. Halliday, The TXL Programming Language, Queen's University, Kingston, 1988 (rev. 2005)]]

[19]

{19} J.R. Cordy, E.M. Promislow, Specification and automatic prototype implementation of polymorphic objects in Turing using the TXL dialect processor, in: Proc. 1990 IEEE International Conference on Computer Languages, 1990, pp. 145-154.]]

[20]

{20} J.R. Cordy, C.D. Halpern, E. Promislow, TXL: A rapid prototyping system for programming language dialects, Computer Languages 16 (1) (1991) 97-107]]

Digital Library

[21]

{21} J.R. Cordy, T.R. Dean, A.J. Malton, K.A. Schneider, source transformation in software engineering using the TXL transformation system, Journal of Information and Software Technology 44 (13) (2002) 827-837.]]

[22]

{22} J.R. Cordy, K.A. Schneider, Architectural design recovery using source transformation, in: Proc. CASE'95 Workshop on Software Architecture, 1995.]]

[23]

{23} J.R. Cordy, Generalized selective XML markup of source code using agile parsing, in: Proc. IEEE 11th International Workshop on Program Comprehension, 2003, pp. 144-153.]]

[24]

{24} T.R. Dean, J.R. Cordy, K.A. Schneider, A.J. Malton, Experience using design recovery techniques to transform legacy systems, in: Proc. 2001 IEEE International Conference on Software Maintenance, 2001, pp. 622-631.]]

Digital Library

[25]

{25} T.R. Dean, J.R. Cordy, A.J. Malton, K.A. Schneider, Agile parsing in TXL, Journal of Automated Software Engineering 10 (4) (2003) 311-336.]]

[26]

{26} A. van Deursen, T. Kuipers, Building documentation generators, in: Proc. 1999 International Conference on Software Maintenance, 1999, pp. 40-49.]]

[27]

{27} G. Gelernter, Generative communication in Linda, ACM Transactions on Programming Languages and Systems 7 (1) (1985) 80-112.]]

Digital Library

[28]

{28} C. Halpern, TXL: A rapid prototyping tool for programming language design, M.Sc. Thesis, Department of Computer Science, University of Toronto, 1986.]]

[29]

{29} R.C. Holt, J.R. Cordy, The Turing programming language, Communications of the ACM 31 (12) (1988) 1410-1423.]]

Digital Library

[30]

{30} R.C. Holt, P.A. Matthews, J.A. Rosselet, J.R. Cordy, The Turing Programming Language--Design and Definition, Prentice-Hall, 1987.]]

[31]

{31} M.A. Jenkins, Q'Nial: A portable interpreter for the nested interactive array language, Nial, Software--Practice and Experience 19 (2) (1989) 111-126.]]

Digital Library

[32]

{32} E. Kohlbecker, Using MkMac, Computer Science Technical Report 157, Indiana University, 1984.]]

[33]

{33} J. Kort, R. Laemmel, Parse-tree annotations meet re-engineering concerns, in: Proc. IEEE 3rd International Workshop on Source Code Analysis and Manipulation, 2003, pp. 161-171.]]

[34]

{34} R. Laemmel, Grammar adaptation, in: Proc. International Symposium on Formal Methods Europe, FME 2001, Lecture Notes in Computer Science 2021 (2001) 550-570.]]

[35]

{35} A.J. Malton, The denotational semantics of a functional tree manipulation language, Computer Languages 19 (3) (1993) 157-168.]]

Digital Library

[36]

{36} A.J. Malton, K.A. Schneider, J.R. Cordy, T.R. Dean, D. Cousineau, J. Reynolds, Processing software source text in automated design recovery and transformation, in: Proc. IEEE 9th International Workshop on Program Comprehension, 2001, pp. 127-134.]]

[37]

{37} J. McCarthy et al., LISP 1.5 Programmer's Manual, MIT Press, 1962.]]

[38]

{38} L. Moonen, Generating robust parsers using island grammars, in: Proc. IEEE 8th Working Conference on Reverse Engineering, 2001, pp. 13-22.]]

[39]

{39} T.J. Parr, R.W. Quong, ANTLR: A predicated LL(k) parser generator, Software, Practice and Experience 25 (7) (1995) 789-810.]]

Digital Library

[40]

{40} R. Paige, Viewing a program transformation system at work, in: Proc. Joint 6th International Conference Programming Language Implementation and Logic Programming, and 4th International Conference on Algebraic and Logic Programming, Lecture Notes in Computer Science 844 (1991) 5-24.]]

[41]

{41} R. Paige, APTS External Specification Manual, Unpublished manuscript, available at, http://www.cs.nyu.edu/~jessie, 1993.]]

[42]

{42} T.J. Parr, An Overview of SORCERER: A Simple Tree-parser Generator, Technical Report, http://www.antlr.org/papers/sorcerer.ps, 1994.]]

[43]

{43} F. Pereira, D. Warren, Definite clause grammars for language analysis--A survey of the formalism and a comparison with augmented transition networks, Artificial Intelligence 13 (3) (1980) 231-278.]]

[44]

{44} E. Promislow, A run-time model for generating semantic transformations from syntactic specifications, M.Sc. Thesis, Department of Computing and Information Science, Qujeen's University, Kingston, 1990.]]

[45]

{45} J.J. Purtilo, J.R. Callahan, Parse-tree annotations, Communications of the ACM 32 (12) (1989) 1467-1477.]]

Digital Library

[46]

{46} R. Ramesh, I.V. Ramakrishnan, Nonlinear pattern matching in trees, Journal of the ACM 39 (2) (1992) 295-316.]]

Digital Library

[47]

{47} J. Sarbo, Grammar transformations for optimizing backtrack parsers, Computer Languages 20 (2) (1994) 89-100.]]

Digital Library

[48]

{48} F. Schroer, The GENTLE Compiler Construction System, Oldenbourg, 1997.]]

[49]

{49} M.P.A. Selink, C. Verhoef, Native patterns, in: Proc. IEEE 5th Working Conference on Reverse Engineering, 1998, pp. 89-103.]]

Digital Library

[50]

{50} A. Thurston, Evolving TXL, M.Sc. Thesis, School of Computing, Queen's University, Kingston, 2005.]]

[51]

{51} M. Tomita, An efficient augmented context-free parsing algorithm, Computational Linguistics 13 (1-2) (1987) 31-46.]]

Digital Library

[52]

{52} K. Vijay-Shanker, D. Weir, Polynomial time parsing of combinatory categorical grammars, in: Proc. 28th International Meeting of the Association for Computational Linguistics, 1990, pp. 1-8.]]

[53]

{53} E. Visser, Stratego: A language for program transformation based on rewriting strategies, in: Proc. Rewriting Techniques and Applications RTA'01, Lecture Notes in Computer Science 2051 (2001) 357-361.]]

[54]

{54} E. Visser, Program transformation in Stratego/XT: Rules, strategies, tools and systems in stratego XT/0.9, in: Proc. Domain Specific Program Generation 2003, Lecture Notes in Computer Science 3016 (2004) 216-238.]]

[55]

{55} E. Visser, Z. Benaissa, A. Tolmach, Building program optimzers with rewriting strategies, in: Proc. ACM 3rd SIGPLAN International Conference on Functional Programming, ICFP'98, 1998 pp. 13-26.]]

Digital Library

[56]

{56} E. Visser, Scannerless generalized-LR parsing, Technical Report P9707, in: Programming Research Group, University of Amsterdam, 1997.]]

[57]

{57} G.M. Weinberg, The Psychology of Computer Programming, Dorset House, 1971.]]

[58]

{58} R. Zanibbi, D. Blostein, J.R. Cordy, Recognizing mathematical expressions using tree transformation, IEEE Transactions on Pattern Analysis and Machine Intelligence 24 (11) (2002) 1455-1467.]]

Digital Library

Cited By

Huang ZChen JJiang JLiang YYou HLi F(2024)Mapping APIs in Dynamic-typed Programs by Leveraging Transfer LearningACM Transactions on Software Engineering and Methodology10.1145/364184833:4(1-29)Online publication date: 18-Apr-2024
https://dl.acm.org/doi/10.1145/3641848
Zhang BChen WYao PWang CTang WZhang CTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)SIRO: Empowering Version Compatibility in Intermediate Representations via Program SynthesisProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651366(882-899)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651366
Wang BLi RLi MSaxena PChandra SBlincoe KTonella P(2023)TransMap: Pinpointing Mistakes in Neural Code TranslationProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616322(999-1011)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616322
Show More Cited By

Index Terms

The TXL source transformation language
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Formal languages and automata theory
  2. Semantics and reasoning
    1. Program semantics

Recommendations

TXL - A Language for Programming Language Tools and Applications

TXL is a special-purpose programming language designed for creating, manipulating and rapidly prototyping language descriptions, tools and applications. TXL is designed to allow explicit programmer control over the interpretation, application, order and ...
Source transformation, analysis and generation in TXL
PEPM '06: Proceedings of the 2006 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

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 ...
Agile Parsing in TXL

Syntactic analysis forms a foundation of many source analysis and reverse engineering tools. However, a single standard grammar is not always appropriate for all source analysis and manipulation tasks. Small custom modifications to the grammar can make ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Science of Computer Programming

Science of Computer Programming Volume 61, Issue 3

The fourth workshop on language descriptions, tools, and applications (LDTA'04)

August 2006

76 pages

ISSN:0167-6423

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 August 2006

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

127
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Huang ZChen JJiang JLiang YYou HLi F(2024)Mapping APIs in Dynamic-typed Programs by Leveraging Transfer LearningACM Transactions on Software Engineering and Methodology10.1145/364184833:4(1-29)Online publication date: 18-Apr-2024
https://dl.acm.org/doi/10.1145/3641848
Zhang BChen WYao PWang CTang WZhang CTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)SIRO: Empowering Version Compatibility in Intermediate Representations via Program SynthesisProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651366(882-899)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651366
Wang BLi RLi MSaxena PChandra SBlincoe KTonella P(2023)TransMap: Pinpointing Mistakes in Neural Code TranslationProceedings of the 31st ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3611643.3616322(999-1011)Online publication date: 30-Nov-2023
https://dl.acm.org/doi/10.1145/3611643.3616322
Wang BKolluri ANikolić IBaluta TSaxena P(2023)User-Customizable Transpilation of Scripting LanguagesProceedings of the ACM on Programming Languages10.1145/35860347:OOPSLA1(201-229)Online publication date: 6-Apr-2023
https://dl.acm.org/doi/10.1145/3586034
Hong JRyu SGrundy JPollock LPenta M(2023)Concrat: An Automatic C-to-Rust Lock API Translator for Concurrent ProgramsProceedings of the 45th International Conference on Software Engineering10.1109/ICSE48619.2023.00069(716-728)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE48619.2023.00069
Hong JGrundy J(2023)Improving Automatic C-to-Rust Translation with Static AnalysisProceedings of the 45th International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion58688.2023.00074(273-277)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE-Companion58688.2023.00074
Voinov PRigger MSu ZScholliers CSinger J(2022)Forest: Structural Code Editing with Multiple CursorsProceedings of the 2022 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software10.1145/3563835.3567663(137-152)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3563835.3567663
Ling MYu YWu HWang YCordy JHassan ADwyer M(2022)In rust we trustProceedings of the ACM/IEEE 44th International Conference on Software Engineering: Companion Proceedings10.1145/3510454.3528640(354-355)Online publication date: 21-May-2022
https://dl.acm.org/doi/10.1145/3510454.3528640
Al-Sibahi AJensen TDimovski AWąsowski A(2021)Verification of Program Transformations with Inductive Refinement TypesACM Transactions on Software Engineering and Methodology10.1145/340980530:1(1-33)Online publication date: 20-Jan-2021
https://dl.acm.org/doi/10.1145/3409805
Babar AImam FDean TFernandez J(2020)An approach to represent and transform application-specific constraints for an intrusion detection systemProceedings of the 30th Annual International Conference on Computer Science and Software Engineering10.5555/3432601.3432609(53-62)Online publication date: 10-Nov-2020
https://dl.acm.org/doi/10.5555/3432601.3432609
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents