×

A survey of strategies in rule-based program transformation systems. (English) Zbl 1129.68043

Summary: Program transformation is the mechanical manipulation of a program in order to improve it relative to some cost function and is understood broadly as the domain of computation where programs are the data. The natural basic building blocks of the domain of program transformation are transformation rules expressing a ‘one-step’ transformation on a fragment of a program. The ultimate perspective of research in this area is a high-level, language parametric, rule-based program transformation system, which supports a wide range of transformations, admitting efficient implementations that scale to large programs. This situation has not yet been reached, as trade-offs between different goals need to be made. This survey gives an overview of issues in rule-based program transformation systems, focusing on the expressivity of rule-based program transformation systems and in particular on transformation strategies available in various approaches. The survey covers term rewriting, extensions of basic term rewriting, tree parsing strategies, systems with programmable strategies, traversal strategies, and context-sensitive rules.

MSC:

68Q55 Semantics in the theory of computing
68Q42 Grammars and rewriting systems
68Q60 Specification and verification (program logics, model checking, etc.)
68N30 Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.)
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aho, A.; Sethi, R.; Ullman, J., Compilers: Principles, Techniques, and Tools (1986), Addison Wesley: Addison Wesley Reading, MA
[2] Appel, A. W., Modern Compiler Implementation in ML (1998), Cambridge University Press · Zbl 0888.68035
[3] Appel, A. W.; Jim, T., Shrinking lambda expressions in linear time, Journal of Functional Programming, 7, 5, 515-540 (1997) · Zbl 0893.68021
[4] Augusteijn, A., 1993. Functional Programming, Program Transformations and Compiler Construction. Ph.D. Thesis, Department of Computing Science, Eindhoven University of Technology, The Netherlands; Augusteijn, A., 1993. Functional Programming, Program Transformations and Compiler Construction. Ph.D. Thesis, Department of Computing Science, Eindhoven University of Technology, The Netherlands · Zbl 0828.68046
[5] Baader, F.; Nipkow, T., Term Rewriting and All That (1998), Cambridge University Press
[6] Baeten, J.; Bergstra, J.; Klop, J.; Weijland, W., Term-rewriting systems with rule priorities, Theoretical Computer Science, 67, 2-3, 283-301 (1989) · Zbl 0686.68018
[7] Benzaken, V., Castagna, G., Frisch, A., 2003. CDuce: An XML-centric general-purpose language. In: Proceedings of the ACM International Conference on Functional Programming, pp. 51-64; Benzaken, V., Castagna, G., Frisch, A., 2003. CDuce: An XML-centric general-purpose language. In: Proceedings of the ACM International Conference on Functional Programming, pp. 51-64 · Zbl 1315.68046
[8] Bird, R. S.; Meertens, L., Two exercises found in a book on algorithmics, (Meertens, L., Program Specification and Transformation (1987), North-Holland), 451-458
[9] Borovanský, P.; Cirstea, H.; Dubois, H.; Kirchner, C.; Kirchner, H.; Moreau, P.-E.; Ringeissen, C.; Vittek, M., ELAN V 3.4 User Manual (2000), LORIA: LORIA Nancy, France
[10] Borovanský, P.; Kirchner, C.; Kirchner, H., Controlling rewriting by rewriting, (Meseguer, J., Proceedings of the First International Workshop on Rewriting Logic and its Applications. Proceedings of the First International Workshop on Rewriting Logic and its Applications, WRLA’96. Proceedings of the First International Workshop on Rewriting Logic and its Applications. Proceedings of the First International Workshop on Rewriting Logic and its Applications, WRLA’96, Electronic Notes in Theoretical Computer Science, vol. 4 (1996), Elsevier Science Publishers) · Zbl 0912.68088
[11] Borovansky, P.; Kirchner, C.; Kirchner, H.; Moreau, P.-E., ELAN from a rewriting logic point of view, Theoretical Computer Science, 285, 155-185 (2002) · Zbl 1001.68057
[12] Borovanský, P.; Kirchner, C.; Kirchner, H.; Moreau, P.-E.; Ringeissen, C., An overview of ELAN, (Kirchner, C.; Kirchner, H., Proceedings of the second International Workshop on Rewriting Logic and Applications. Proceedings of the second International Workshop on Rewriting Logic and Applications, WRLA’98. Proceedings of the second International Workshop on Rewriting Logic and Applications. Proceedings of the second International Workshop on Rewriting Logic and Applications, WRLA’98, Electronic Notes in Theoretical Computer Science, vol. 15 (1998), Elsevier Science Publishers) · Zbl 0917.68022
[13] Borovanský, P.; Kirchner, C.; Kirchner, H.; Moreau, P.-E.; Vittek, M., ELAN: a logical framework based on computational systems, (Meseguer, J., Proceedings of the First Workshop on Rewriting Logic and Applications 1996. Proceedings of the First Workshop on Rewriting Logic and Applications 1996, WRLA’96. Proceedings of the First Workshop on Rewriting Logic and Applications 1996. Proceedings of the First Workshop on Rewriting Logic and Applications 1996, WRLA’96, Electronic Notes in Theoretical Computer Science, vol. 4 (1996), Elsevier Science Publishers) · Zbl 0912.68091
[14] Boyle, J. M., Abstract programming and program transformation—An approach to reusing programs, (Biggerstaff, T. J.; Perlis, A. J., Software Reusability, vol. 1 (1989)), 361-413
[15] Boyle, J. M.; Harmer, T. J.; Winter, V. L., The TAMPR program transformation system: Simplifying the development of numerical software, (Arge, E.; Bruaset, A. M.; Langtangen, H. P., Modern Software Tools for Scientific Computing (1997), Birkhäuser), 353-372 · Zbl 1114.68375
[16] Bravenboer, M.; Visser, E., Rewriting strategies for instruction selection, (Tison, S., Rewriting Techniques and Applications. Rewriting Techniques and Applications, RTA’02. Rewriting Techniques and Applications. Rewriting Techniques and Applications, RTA’02, Lecture Notes in Computer Science, vol. 2378 (2002), Springer-Verlag), 237-251 · Zbl 1045.68578
[17] Bravenboer, M., Visser, E., 2004. Concrete syntax for objects. Domain-specific language embedding and assimilation without restrictions. In: Schmidt, D.C. (Ed.), Proceedings of the 19th ACM SIGPLAN conference on Object-Oriented Programing, Systems, Languages, and Applications. OOPSLA’04; Bravenboer, M., Visser, E., 2004. Concrete syntax for objects. Domain-specific language embedding and assimilation without restrictions. In: Schmidt, D.C. (Ed.), Proceedings of the 19th ACM SIGPLAN conference on Object-Oriented Programing, Systems, Languages, and Applications. OOPSLA’04
[18] de Bruijn, N., A survey of the project AUTOMATH, (To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalisms (1980), Academic Press), 579-606
[19] de Moor, O.; Sittampalam, G., Higher-order matching for program transformation, Theoretical Computer Science, 269, 1-2, 135-162 (2001) · Zbl 0983.68020
[20] de Moor, O., Backhouse, K., Swierstra, S.D., 2000. First class attribute grammars. In: Attribute Grammars and Their Applications. Informatica: An International Journal of Computing and Informatics 24 (2), 329-341; de Moor, O., Backhouse, K., Swierstra, S.D., 2000. First class attribute grammars. In: Attribute Grammars and Their Applications. Informatica: An International Journal of Computing and Informatics 24 (2), 329-341 · Zbl 0968.68076
[21] Burstall, R. M.; Darlington, J., A transformational system for developing recursive programs, Journal of the ACM, 24, 1, 44-67 (1977) · Zbl 0343.68014
[22] Chikofski, E.; Cross, J., Reverse engineering and design recovery: A taxonomy, IEEE Software, 7, 1, 13-17 (1990)
[23] Clavel, M.; Durán, F.; Eker, S.; Lincoln, P.; Martí-Oliet, N.; Meseguer, J.; Quesada, J. F., Maude: specification and programming in rewriting logic, Theoretical Computer Science, 285, 2, 187-243 (2002) · Zbl 1001.68059
[24] Collberg, C., Thomborson, C., Low, D., 1998. Manufacturing cheap, resilient and stealthy opaque constructs. In: Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’98. pp. 184-196; Collberg, C., Thomborson, C., Low, D., 1998. Manufacturing cheap, resilient and stealthy opaque constructs. In: Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’98. pp. 184-196
[25] Cordy, J.R., Carmichael, I.H., Halliday, R., 1995. The TXL Programming Language, Version 8; Cordy, J.R., Carmichael, I.H., Halliday, R., 1995. The TXL Programming Language, Version 8
[26] Cousot, P., Cousot, R., 2002. Systematic design of program transformation frameworks by abstract interpretation. In: Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’02. pp. 178-190; Cousot, P., Cousot, R., 2002. Systematic design of program transformation frameworks by abstract interpretation. In: Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’02. pp. 178-190 · Zbl 1323.68356
[27] Czarnecki, K.; Eisenecker, U. W., Intentional programming, (Generative Programming. Methods, Tools, and Applications (2000), Addison-Wesley), (Chapter 11)
[28] Dershowitz, N.; Jouannaud, J.-P., Rewrite systems, (van Leeuwen, J., Handbook of Theoretical Computer Science, vol. B (1990), Elsevier Science Publishers), 243-320, (Chapter 6) · Zbl 0900.68283
[29] Dijkstra, E. W., A constructive approach to the problem of program correctness, BIT, 8, 3, 174-186 (1968) · Zbl 0167.46002
[30] Dolstra, E.; Visser, E., Building interpreters with rewriting strategies, (van den Brand, M. G.J.; Lämmel, R., Workshop on Language Descriptions, Tools and Applications. Workshop on Language Descriptions, Tools and Applications, LDTA’02. Workshop on Language Descriptions, Tools and Applications. Workshop on Language Descriptions, Tools and Applications, LDTA’02, Electronic Notes in Theoretical Computer Science, vol. 65/3 (2002), Elsevier Science Publishers)
[31] Elliott, C.; Finne, S.; de Moor, O., Compiling Embedded Languages (2000), Springer-Verlag · Zbl 1044.68545
[32] Feather, M. S., A system for assisting program transformation, ACM Transactions on Programming Languages and Systems, 4, 1, 1-20 (1982) · Zbl 0479.68014
[33] Feather, M. S., A survey and classification of some program transformation approaches and techniques, (Meertens, L. G.L. T., Program Specification and Transformation. Program Specification and Transformation, IFIP (1987), Elsevier Science Publishers), 165-195
[34] Felty, A., A logic programming approach to implementing higher-order term rewriting, (Eriksson, L.-H.; Hallnäs, L.; Schroeder-Heister, P., Extensions of Logic Programming. ELP’91. Extensions of Logic Programming. ELP’91, Lecture Notes in Artificial Intelligence, vol. 596 (1992), Springer-Verlag), 135-158
[35] Field, J.; Heering, J.; Dinesh, T. B., Equations as a uniform framework for partial evaluation and abstract interpretation, ACM Computing Surveys, 30, 3es, 2 (1998)
[36] Fischer, B.; Visser, E., Retrofitting the AutoBayes program synthesis system with concrete object syntax, (Lengauer, C.; etal., Domain-Specific Program Generation. Domain-Specific Program Generation, Lecture Notes in Computer Science, vol. 3016 (2004), Spinger-Verlag), 239-253
[37] Fitzpatrick, S., Stewart, A., Clint, M., Boyle, J.M., 1995. An algebra for deriving efficient implementations for an array processor parallel computer from functional specifications. Technical Report 1995/Jun-SF.AS.MC.JMB, Department of Computer Science, The Queen’s University of Belfast, Northern Ireland; Fitzpatrick, S., Stewart, A., Clint, M., Boyle, J.M., 1995. An algebra for deriving efficient implementations for an array processor parallel computer from functional specifications. Technical Report 1995/Jun-SF.AS.MC.JMB, Department of Computer Science, The Queen’s University of Belfast, Northern Ireland
[38] Fokkink, W. J.; Kamperman, J. F.T.; Walters, H. R., Lazy rewriting on eager machinery, ACM Transactions on Programming Languages and Systems, 22, 1, 45-86 (2000)
[39] Fowler, M., Refactoring: Improving the Design of Existing Programs (1999), Addison-Wesley
[40] Fraser, C. W.; Hanson, D. R.; Proebsting, T. A., Engineering a simple, efficient code-generator generator, ACM Letters on Programming Languages and Systems, 1, 3, 213-226 (1992)
[41] Fraser, C. W.; Henry, R. R.; Proebsting, T. A., BURG—fast optimal instruction selection and tree parsing, ACM SIGPLAN Notices, 27, 4, 68-76 (1992)
[42] Futatsugi, K., Goguen, J., Jouannaud, J.-P., Meseguer, J., 1985. Principles of OBJ2. In: Reid, B. (Ed), Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’85. pp. 52-66; Futatsugi, K., Goguen, J., Jouannaud, J.-P., Meseguer, J., 1985. Principles of OBJ2. In: Reid, B. (Ed), Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’85. pp. 52-66
[43] Goguen, J. A.; Thatcher, J. W.; Wagner, E. G.; Wright, J. B., Initial algebra semantics and continuous algebras, Journal of the ACM, 24, 1, 68-95 (1977) · Zbl 0359.68018
[44] Goguen, J. A.; Winkler, T.; Meseguer, J.; Futatsugi, K.; Jouannaud, J.-P., Introducing OBJ, (Goguen, J. A.; Malcolm, G., Software Engineering with OBJ: Algebraic Specification in Action. Software Engineering with OBJ: Algebraic Specification in Action, Advances in Formal Methods (2000), Kluwer Academic Publishers), 3-167, (Chapter 1)
[45] Guttmann, W.; Partsch, H.; Schulte, W.; Vullinghs, T., Tool Support for the Interactive Derivation of Formally Correct Functional Programs, Journal of Universal Computer Science, 9, 2, 173-188 (2003)
[46] Hatcher, W. S.; Rus, T., Context-free algebras, Journal of Cybernetics, 6, 65-76 (1976) · Zbl 0362.68107
[47] Heering, J., Implementing higher-order algebraic specifications, (Miller, D., Proceedings of the Workshop on the \(\lambda\) Prolog Programming Language (1992), University of Pennsylvania: University of Pennsylvania Philadelphia), 141-157, Also published as Technical Report MS-CIS-92-86
[48] Heering, J.; Hendriks, P. R.H.; Klint, P.; Rekers, J., The syntax definition formalism SDF-reference manual, ACM SIGPLAN Notices, 24, 11, 43-75 (1989)
[49] Heering, J., Klint, P., 2003. Rewriting-based Languages and Systems, chapter 15, pp. 776-789. vol. 55 of Terese (2003); Heering, J., Klint, P., 2003. Rewriting-based Languages and Systems, chapter 15, pp. 776-789. vol. 55 of Terese (2003)
[50] Huet, G., Functional pearl: the zipper, Journal of Functional Programming, 7, 5, 549-554 (1997) · Zbl 0893.68014
[51] Huet, G.; Lang, B., Proving and applying program transformations expressed with second-order patterns, Acta Informatica, 11, 31-55 (1978) · Zbl 0389.68008
[52] Johann, P.; Visser, E., Fusing logic and control with local transformations: An example optimization, (Gramlich, B.; Lucas, S., Workshop on Reduction Strategies in Rewriting and Programming. Workshop on Reduction Strategies in Rewriting and Programming, WRS’01. Workshop on Reduction Strategies in Rewriting and Programming. Workshop on Reduction Strategies in Rewriting and Programming, WRS’01, Electronic Notes in Theoretical Computer Science, vol. 57 (2001), Elsevier Science Publishers) · Zbl 1268.68098
[53] Johnsson, T., Attribute grammars as a functional programming paradigm, (Kahn, G., Functional Programming Languages and Computer Architecture. Functional Programming Languages and Computer Architecture, Lecture Notes in Computer Science, vol. 274 (1987), Springer-Verlag), 154-173 · Zbl 0633.68072
[54] Jones, N.; Gomard, C.; Sestoft, P., Partial Evaluation and Automatic Program Generation (1993), Prentice Hall · Zbl 0875.68290
[55] Klop, J. W., Term rewriting systems, (Abramsky, S.; Gabbay, D.; Maibaum, T., Handbook of Logic in Computer Science, vol. 2 (1992), Oxford University Press: Oxford University Press Oxford, England), 1-116
[56] Knuth, D. E., Semantics of context-free languages, Mathematical Systems Theory. (Mathematical Systems Theory, vol. 5(1) (1971), Springer-Verlag), 2, 2, 95-96 (1968), Correction in: · Zbl 0219.68035
[57] Kort, J.; Lämmel, R., Parse-tree annotations meet re-engineering concerns, (Third IEEE International Workshop on Source Code Analysis and Manipulation. Third IEEE International Workshop on Source Code Analysis and Manipulation, SCAM’03 (2003), IEEE Computer Society Press.), 161-172
[58] Lacey, D.; deMoor, O., Imperative program transformation by rewriting, (Compiler Construction. Compiler Construction, CC’01. Compiler Construction. Compiler Construction, CC’01, Lecture Notes in Computer Science, vol. 2027 (2001), Springer-Verlag), 52-68 · Zbl 0977.68675
[59] Lämmel, R., Typed generic traversal with term rewriting strategies, Journal of Logic and Algebraic Programming, 54, 1-64 (2003) · Zbl 1026.68076
[60] Lämmel, R., Peyton Jones, S.L., 2003. Scrap your boilerplate: a practical design pattern for generic programming. In: Proceedings of the ACM SIGPLAN Workshop on Types in Language Design and Implementation. TLDI’03. ACM SIGPLAN Notices 38 (3), 26-37; Lämmel, R., Peyton Jones, S.L., 2003. Scrap your boilerplate: a practical design pattern for generic programming. In: Proceedings of the ACM SIGPLAN Workshop on Types in Language Design and Implementation. TLDI’03. ACM SIGPLAN Notices 38 (3), 26-37
[61] Lämmel, R.; Riedewald, G., Prological language processing, (van den Brand, M.; Parigot, D., Proceedings of the First Workshop on Language Descriptions, Tools and Applications. Proceedings of the First Workshop on Language Descriptions, Tools and Applications, LDTA’01. Proceedings of the First Workshop on Language Descriptions, Tools and Applications. Proceedings of the First Workshop on Language Descriptions, Tools and Applications, LDTA’01, Electronic Notes in Theoretical Computer Science, vol. 44 (2001), Elsevier Science Publishers)
[62] Lämmel, R.; Visser, J., Typed combinators for generic traversal, (Proceedings Practical Aspects of Declarative Programming PADL 2002. Proceedings Practical Aspects of Declarative Programming PADL 2002, Lecture Notes in Computer Science, vol. 2257 (2002), Springer-Verlag), 137-154
[63] Lämmel, R., Visser, J., Kort, J., 2000. Dealing with large bananas. In: Jeuring, J. (Ed.), Proceedings of the Workshop on Generic Programming. WGP’00. Technical Report UU-CS-2000-19, Department of Information and Computing Sciences, Utrecht University, pp. 46-59.; Lämmel, R., Visser, J., Kort, J., 2000. Dealing with large bananas. In: Jeuring, J. (Ed.), Proceedings of the Workshop on Generic Programming. WGP’00. Technical Report UU-CS-2000-19, Department of Information and Computing Sciences, Utrecht University, pp. 46-59.
[64] Lämmel, R., Visser, E., Visser, J., 2002. The essence of strategic programming, October 2002 (Draft); Lämmel, R., Visser, E., Visser, J., 2002. The essence of strategic programming, October 2002 (Draft) · Zbl 1028.68921
[65] Lämmel, R.; Visser, E.; Visser, J., Strategic programming meets adaptive programming, (Proceedings of Aspect-Oriented Software Development. Proceedings of Aspect-Oriented Software Development, AOSD’03 (2003), ACM Press: ACM Press Boston, USA, March 2003), 168-177
[66] Luttik, B.; Visser, E., Specification of rewriting strategies, (Sellink, M. P.A., 2nd International Workshop on the Theory and Practice of Algebraic Specifications. 2nd International Workshop on the Theory and Practice of Algebraic Specifications, ASF+SDF’97 (1997), Springer-Verlag: Springer-Verlag Electronic Workshops in Computing)
[67] Muchnick, S. S., Advanced Compiler Design and Implementation (1997), Morgan Kaufmann Publishers
[68] Nadathur, G.; Miller, D., An overview of \(\lambda\) Prolog, (Kowalski, R. A., Logic Programming. Proceedings of the Fifth International Conference and Symposium, vol. 1 (1988), MIT Press: MIT Press USA), 810-827, 1988
[69] Neighbors, J. M., The Draco approach to constructing software from reusable components, IEEE Transactions on Software Engineering, SE-10, 5, 564-573 (1984)
[70] Ogata, K.; Futatsugi, K., Implementation of term rewritings with the evaluation strategy, (Proceedings 9th Symposium on Programming Languages: Implementations, Logics, and Programs. Proceedings 9th Symposium on Programming Languages: Implementations, Logics, and Programs, PLILP’97. Proceedings 9th Symposium on Programming Languages: Implementations, Logics, and Programs. Proceedings 9th Symposium on Programming Languages: Implementations, Logics, and Programs, PLILP’97, Lecture Notes in Computer Science, vol. 1292 (1997), Springer-Verlag), 225-239
[71] Olmos, K.; Visser, E., Strategies for source-to-source constant propagation, (Gramlich, B.; Lucas, S., Workshop on Reduction Strategies. Workshop on Reduction Strategies, WRS’02. Workshop on Reduction Strategies. Workshop on Reduction Strategies, WRS’02, Electronic Notes in Theoretical Computer Science, vol. 70/6 (2002), Elsevier Science Publishers) · Zbl 1270.68138
[72] Olmos, K.; Visser, E., Turning dynamic typing into static typing by program specialization, (Binkley, D.; Tonella, P., Third IEEE International Workshop on Source Code Analysis and Manipulation. Third IEEE International Workshop on Source Code Analysis and Manipulation, SCAM’03 (2003), IEEE Computer Society Press), 141-150
[73] Paige, R., Viewing a program transformation system at work, (Hermenegildo, M.; Penjam, J., Proceedings of the Sixth International Symposium on Programming Language Implementation and Logic Programming. Proceedings of the Sixth International Symposium on Programming Language Implementation and Logic Programming, Lecture Notes in Computer Science, vol. 844 (1994), Springer-Verlag), 5-24 · Zbl 0988.68760
[74] Paige, R., Future directions in program transformations, Computing Surveys, 28A, 4 (1996)
[75] Parr, T.J. et al., 2003. ANTLR reference manual. http://www.antlr.org; Parr, T.J. et al., 2003. ANTLR reference manual. http://www.antlr.org
[76] Partsch, H., Transformational program development in a particular problem domain, Science of Computer Programming, 7, 2, 99-241 (1986) · Zbl 0601.68015
[77] Partsch, H., Specification and Transformation of Programs. A Formal Approach to Software Development (1990), Springer-Verlag · Zbl 0751.68036
[78] Partsch, H., Schulte, W., Vullinghs, T., 1999. System support for the interactive transformation of functional programs. In: Proceedings of the 21st International Conference on Software engineering (Sant’Anna et al., 1999http://www.dur.ac.uk/CSM/STS/; Partsch, H., Schulte, W., Vullinghs, T., 1999. System support for the interactive transformation of functional programs. In: Proceedings of the 21st International Conference on Software engineering (Sant’Anna et al., 1999http://www.dur.ac.uk/CSM/STS/
[79] Partsch, H.; Steinbrüggen, R., Program transformation systems, ACM Computing Surveys, 15, 3, 199-236 (1983)
[80] Pettorossi, A.; Proietti, M., Future directions in program transformation, ACM Computing Surveys, 28, 4es, 171-es (1996), December 1996. Position Statement at the Workshop on Strategic Directions in Computing Research. MIT, Cambridge, MA, USA, June 14-15
[81] Pettorossi, A.; Proietti, M., Rules and strategies for transforming functional and logic programs, ACM Computing Surveys, 28, 2, 360-414 (1996)
[82] Peyton Jones, S. L.; Marlow, S., Secrets of the Glasgow Haskell Compiler inliner, Journal of Functional Programming, 12, 4, 393-434 (2002) · Zbl 1037.68042
[83] Peyton Jones, S. L.; Santos, A. L.M., A transformation-based optimiser for Haskell, Science of Computer Programming, 32, 1-3, 3-47 (1998) · Zbl 0942.68030
[84] Peyton Jones, S. L.; Tolmach, A.; Hoare, T., Playing by the rules: rewriting as a practical optimisation technique in GHC, (Hinze, R., 2001 Haskell Workshop (2001), ACM SIGPLAN)
[85] Pfenning, F.; Elliot, C., Higher-order abstract syntax, (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI’88 (1988), ACM), 199-208
[86] Pitts, A. M.; Gabbay, M. J., A metalanguage for programming with bound names modulo renaming, (Backhouse, R.; Oliveira, J. N., Proceedings of the 5th International Conference on Mathematics of Programme Construction. Proceedings of the 5th International Conference on Mathematics of Programme Construction, MPC2000. Proceedings of the 5th International Conference on Mathematics of Programme Construction. Proceedings of the 5th International Conference on Mathematics of Programme Construction, MPC2000, Lecture Notes in Computer Science, vol. 1837 (2000), Springer-Verlag), 230-255 · Zbl 0963.68502
[87] Proebsting, T. A., BURS automata generation, ACM Transactions on Programming Languages and Systems, 17, 3, 461-486 (1995)
[88] Reps, T.; Teitelbaum, T., The Synthesizer Generator: A System for Constructing Language-Based Editors (1988), Springer-Verlag · Zbl 0711.68028
[89] Rich, C.; Waters, R. C., The Programmer’s Apprentice, Frontier Series (1990), ACM Press
[90] Roberts, D.; Brant, J.; Johnson, R. E., A refactoring tool for Smalltalk, Theory and Practice of Object Systems, 3, 4, 253-263 (1997)
[91] Sant’Anna, M.; Leite, J.; Baxter, I.; Wile, D.; Biggerstaff, T.; Batory, D.; Devanbu, P.; Burd, L., International workshop on software transformation systems (STS’99), (Proceedings of the 21st International Conference on Software Engineering (1999), IEEE Computer Society Press), 701-702, The actual proceedings are available at
[92] Saraiva, J.; Kuiper, M., LRC—A generator for incremental language-oriented tools, (Koskimies, K., 7th International Conference on Compiler Construction. 7th International Conference on Compiler Construction, CC’98. 7th International Conference on Compiler Construction. 7th International Conference on Compiler Construction, CC’98, Lecture Notes in Computer Science, vol. 1383 (1998), Springer-Verlag)
[93] Saraiva, J.; Swierstra, S. D., Data structure free compilation, (8th International Conference on Compiler Construction. 8th International Conference on Compiler Construction, CC’99. 8th International Conference on Compiler Construction. 8th International Conference on Compiler Construction, CC’99, Lecture Notes in Computer Science, vol. 1575 (1999), Springer-Verlag), 1-16
[94] Sheard, T.; Peyton Jones, S. L., Template metaprogramming for Haskell, (Chakravarty, M. M.T., ACM SIGPLAN Haskell Workshop 02 (2002)), 1-16
[95] Sittampalam, G., de Moor, O., Larsen, K.F., 2004. Incremental execution of transformation specifications. In: Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’04, pp. 26-38; Sittampalam, G., de Moor, O., Larsen, K.F., 2004. Incremental execution of transformation specifications. In: Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. POPL’04, pp. 26-38 · Zbl 1325.68044
[96] Smaragdakis, Y.; Batory, D., Application generators, (Webster, J., Encyclopedia of Electrical and Electronics Engineering (2000), John Wiley and Sons)
[97] Smith, D. R., KIDS: A semiautomatic program development system, IEEE Transactions on Software Engineering, 16, 9, 1024-1043 (1990)
[98] Taha, W.; Sheard, T., MetaML and multi-stage programming with explicit annotations, Theoretical Computer Science, 248, 1-2, 211-242 (2000) · Zbl 0949.68047
[99] Terese, Term Rewriting Systems, Cambridge Tracts in Theoretical Computer Science, vol. 55 (2003), Cambridge University Press
[100] van den Brand, M. G.J.; Visser, E., Generation of formatters for context-free languages, ACM Transactions on Software Engineering and Methodology, 5, 1, 1-41 (1996)
[101] van den Brand, M. G.J.; Klint, P.; Verhoef, C., Reverse engineering and system renovation: an annotated bibliography, ACM Software Engineering Notes, 22, 1, 42-57 (1997)
[102] van den Brand, M. G.J.; Klint, P.; Vinju, J. J., Term rewriting with traversal functions, ACM Transactions on Software Engineering and Methodology, 12, 2, 152-190 (2003) · Zbl 1270.68143
[103] van den Brand, M. G.J.; Sellink, M. P.A.; Verhoef, C., Generation of components for software renovation factories from context-free grammars, Science of Computer Programming, 36, 209-266 (2000)
[104] van den Brand, M. G.J.; de Jong, H.; Klint, P.; Olivier, P., Efficient annotated terms, Software, Practice & Experience, 30, 3, 259-291 (2000)
[105] van Deursen, A.; Visser, E., The reengineering Wiki, (Proceedings 6th European Conference on Software Maintenance and Reengineering. Proceedings 6th European Conference on Software Maintenance and Reengineering, CSMR’02 (2002), IEEE Computer Society), 217-220
[106] van Deursen, A.; Klint, P.; Tip, F., Origin tracking, Journal of Symbolic Computation, 15, 5-6, 523-546 (1993) · Zbl 0804.68088
[107] Language Prototyping. An Algebraic Specification Approach, (van Deursen, A.; Heering, J.; Klint, P., AMAST Series in Computing, vol. 5 (1996), World Scientific: World Scientific Singapore) · Zbl 0962.68114
[108] van de Pol, J., Just-in-time: On strategy annotations, (International Workshop on Reduction Strategies in Rewriting and Programming. International Workshop on Reduction Strategies in Rewriting and Programming, WRS’01. International Workshop on Reduction Strategies in Rewriting and Programming. International Workshop on Reduction Strategies in Rewriting and Programming, WRS’01, Electronic Notes in Theoretical Computer Science, vol. 57 (2001)) · Zbl 1268.68104
[109] Visser, E., Strategic pattern matching, (Narendran, P.; Rusinowitch, M., Rewriting Techniques and Applications. Rewriting Techniques and Applications, RTA’99. Rewriting Techniques and Applications. Rewriting Techniques and Applications, RTA’99, Lecture Notes in Computer Science, vol. 1631 (1999), Springer-Verlag), 30-44
[110] Visser, E., 2000. Language independent traversals for program transformation. In: Jeuring, J. (Ed.), Workshop on Generic Programming. WGP’00. Technical Report UU-CS-2000-19, Department of Information and Computing Sciences, Utrecht University; Visser, E., 2000. Language independent traversals for program transformation. In: Jeuring, J. (Ed.), Workshop on Generic Programming. WGP’00. Technical Report UU-CS-2000-19, Department of Information and Computing Sciences, Utrecht University
[111] Visser, E., Scoped dynamic rewrite rules, (van den Brand, M.; Verma, R., Rule Based Programming. Rule Based Programming, RULE’01. Rule Based Programming. Rule Based Programming, RULE’01, Electronic Notes in Theoretical Computer Science, vol. 59/4 (2001), Elsevier Science Publishers) · Zbl 1268.68106
[112] Visser, E., A survey of rewriting strategies in program transformation systems, (Gramlich, B.; Lucas, S., Workshop on Reduction Strategies in Rewriting and Programming. Workshop on Reduction Strategies in Rewriting and Programming, WRS’01. Workshop on Reduction Strategies in Rewriting and Programming. Workshop on Reduction Strategies in Rewriting and Programming, WRS’01, Electronic Notes in Theoretical Computer Science, vol. 57 (2001), Elsevier Science Publishers) · Zbl 1268.68105
[113] Visser, E., Meta-programming with concrete object syntax, (Batory, D.; Consel, C.; Taha, W., Generative Programming and Component Engineering. Generative Programming and Component Engineering, GPCE’02. Generative Programming and Component Engineering. Generative Programming and Component Engineering, GPCE’02, Lecture Notes in Computer Science, vol. 2487 (2002), Springer-Verlag), 299-315 · Zbl 1028.68921
[114] Visser, E., Program transformation with Stratego/XT: Rules, strategies, tools, and systems in StrategoXT-0.9, (Lengauer, C.; etal., Domain-Specific Program Generation. Domain-Specific Program Generation, Lecture Notes in Computer Science, vol. 3016 (2004), Spinger-Verlag)
[115] Visser, J., 2001. Visitor combination and traversal control. In: Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications. OOPSLA’01. pp. 270-282; Visser, J., 2001. Visitor combination and traversal control. In: Proceedings of the 16th ACM SIGPLAN Conference on Object-Oriented Programing, Systems, Languages, and Applications. OOPSLA’01. pp. 270-282
[116] Visser, E., Benaissa, Z.-e.-A., Tolmach, A., 1998 Building program optimizers with rewriting strategies. In: Proceedings of the third ACM SIGPLAN International Conference on Functional Programming. ICFP’98. pp. 13-26; Visser, E., Benaissa, Z.-e.-A., Tolmach, A., 1998 Building program optimizers with rewriting strategies. In: Proceedings of the third ACM SIGPLAN International Conference on Functional Programming. ICFP’98. pp. 13-26 · Zbl 1369.68084
[117] Visser, E. et al., 2004. The Program Transformation Wiki. http://www.program-transformation.org; Visser, E. et al., 2004. The Program Transformation Wiki. http://www.program-transformation.org
[118] Vogt, H., 1989. Higher-order attribute grammars. Ph.D. Thesis, Department of Computer Science, Utrecht University; Vogt, H., 1989. Higher-order attribute grammars. Ph.D. Thesis, Department of Computer Science, Utrecht University
[119] Wadler, P., Views: A way for pattern matching to cohabit with data abstraction, (Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Proceedings of the ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL’87 (1987), ACM), 307-313
[120] Waters, R. C., The programmer’s apprentice: Knowledge based program editing, IEEE Transactions on Software Engineering, 8, 1, 1-12 (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.