Generation of visitor components that implement program transformations

ABSTRACT

The visitor pattern is appealing to developers of program-analysis tools because it separates the design of the data structures that represent a program from the design of software that traverses these structures. Unfortunately, the visitor pattern is difficult to apply when the analysis involves transformation logic that involves multiple program fragments simultaneously. We encountered this problem in our work on the {\proj} project and discovered a novel way to use multiple cooperating visitor objects to systematically implement such functions when they are specified via a set of transformation rules. This paper introduces our {\em curried-visitor framework} and illustrates how we applied it to implement a key component in the {\proj} framework. We are working on a code generator that will automatically synthesize curried-visitor frameworks from a description of a program's abstract syntax and a set of pattern-matching transformation rules.

REFERENCES

• 1: D. Batory. Refinements and separation of concerns. In Proc. of the Second Workshop on Multi-dimensional Separation of Concerns, 2000. Co-located with ICSE'2000.
• 2: Don Batory , Sean O'Malley, The design and implementation of hierarchical software systems with reusable components, ACM Transactions on Software Engineering and Methodology (TOSEM), v.1 n.4, p.355-398, Oct. 1992 [doi>10.1145/136586.136587]
• 3: Tommaso Bolognesi , Ed Brinksma, Introduction to the ISO specification language LOTOS, Computer Networks and ISDN Systems, v.14 n.1, p.25-59, March, 1987 [doi>10.1016/0169-7552(87)90085-7]
• 4: J.R. Burch, E.M. Clarke, K.L. McMillan, D.L. Dill, and L.J. Hwang. Symbolic model checking: 10-20 states and beyond. In Proc. of the 5 th International Symposium on Logic in Computer Science, June 1990.
• 5: E. M. Clarke , E. A. Emerson , A. P. Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.2, p.244-263, April 1986 [doi>10.1145/5397.5399]
• 6: 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]
• 7: Premkumar T. Devanbu, GENOA: a customizable language- and front-end independent code analyzer, Proceedings of the 14th international conference on Software engineering, p.307-317, May 11-15, 1992, Melbourne, Australia [doi>10.1145/143062.143148]
• 8: Laura K. Dillon , R. E. Kurt Stirewalt, Lightweight analysis of operational specifications using inference graphs, Proceedings of the 23rd International Conference on Software Engineering, p.57-67, May 12-19, 2001, Toronto, Ontario, Canada
• 9: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 10: R. E. Johnson and B. Foote. Designing reusable classes. Journal of Object-Oriented Programming, pages 22-35, June/July 1988.
• 11: G. Kiczales et al. Aspect oriented programming. In European Conference on Object-Oriented Programming (ECOOP'97), 1997.
• 12: K. J. Lieberherr , C. Xiao, Object-Oriented Software Evolution, IEEE Transactions on Software Engineering, v.19 n.4, p.313-343, April 1993 [doi>10.1109/32.223802]
• 13: R. Milner, Communication and concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 14: Gail C. Murphy , David Notkin, Lightweight source model extraction, Proceedings of the 3rd ACM SIGSOFT symposium on Foundations of software engineering, p.116-127, October 12-15, 1995, Washington, D.C., United States
• 15: D. Parnas. Designing software for ease of extension and contraction. IEEE Trans. Softw. Eng., 5(2), 1979.
• 16: G. D. Plotkin. A structural approach to operational semantics. Technical Report DAIMI FN-19, Computer Science Department, Aarhus University, 1981.
• 17: James J. Purtilo , John R. Callahan, Parse tree annotations, Communications of the ACM, v.32 n.12, p.1467-1477, Dec. 1989 [doi>10.1145/76380.76387]
• 18: Reasoning Systems Incorporated, Palo Alto, CA. Refine User's Guide.
• 19: Linda M. Seiter , Jens Palsberg , Karl J. Lieberherr, Evolution of Object Behavior Using Context Relations, IEEE Transactions on Software Engineering, v.24 n.1, p.79-92, January 1998 [doi>10.1109/32.663999]
• 20: R. E. Kurt Stirewalt , Laura K. Dillon, A component-based approach to building formal analysis tools, Proceedings of the 23rd International Conference on Software Engineering, p.167-176, May 12-19, 2001, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  D. Software

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.2 SOFTWARE ENGINEERING

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program transformation; Program synthesis

General Terms:
Design, Languages, Performance, Theory

Keywords:
amalia, curried visitor framework, lightweight analysis components, program transformations, visitor pattern