A framework for the checking and refactoring of crosscutting concepts

Abstract

Programmers employ crosscutting concepts, such as design patterns and other programming idioms, when their design ideas cannot be efficiently or effectively modularized in the underlying programming language. As a result, implementations of these crosscutting concepts can be hard to change even when the code is well structured.

In this article, we describe Arcum, a system that supports the modular maintenance of crosscutting concepts. Arcum can be used to both check essential constraints of crosscutting concepts and to substitute crosscutting concept implementations with alternative implementations. Arcum is complementary to existing refactoring systems that focus on meaning-preserving program transformations at the programming-language-semantics level, because Arcum focuses on transformations at the conceptual level.

We present the underpinnings of the Arcum approach and show how Arcum can be used to address several classical software engineering problems.

References

1. Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison-Wesley, Boston, MA.
2. Aiken, A. and Fähndrich, M. 1997. Program analysis using mixed term and set constraints. In Proceedings of the 4th International Symposium on Static Analysis (SAS).
3. Alt, M. and Martin, F. 1995. Generation of efficient interprocedural analyzers with PAG. In Proceedings of the 2nd International Static Analysis Symposium. Lecture Notes in Computer Science, vol. 983, Springer-Verlag, Berlin. 33--50.
4. Babich, W. and Jazayeri, M. 1978a. The method of attributes for data flow analysis, part I: Exhaustive analysis. Acta Informatica 10, 3, 245--264.
5. Babich, W. and Jazayeri, M. 1978b. The method of attributes for data flow analysis, part II: Demand analysis. Acta Informatica 10, 3, 265--272.
6. Balaban, I., Tip, F., and Fuhrer, R. 2005. Refactoring support for class library migration. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). ACM Press, New York, NY, 265--279.
7. Ball, T., Majumdar, R., Millstein, T., and Rajamani, S. K. 2001. Automatic predicate abstraction of C programs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.
8. Bancilhon, F. and Spyratos, N. 1981. Update semantics of relational views. ACM Trans. Database Syst. 6, 4, 557--575.
9. Barbosa, D. M. J., Cretin, J., Foster, N., Greenberg, M., and Pierce, B. C. 2010. Matching lenses: Alignment and view update. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP).
10. Baxter, I. D., Pidgeon, C., and Mehlich, M. 2004. Dms: Program transformations for practical scalable software evolution. In Proceedings of the 26th International Conference on Software Engineering (ICSE'04). IEEE Computer Society, Los Alamitos, CA, 625--634.
11. Berndl, M., Lhoták, O., Qian, F., Hendren, L., and Umanee, N. 2003. Points-to analysis using BDDs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'03). ACM Press, New York, NY, 103--114.
12. Bohannon, A., Foster, J. N., Pierce, B. C., Pilkiewicz, A., and Schmitt, A. 2008. Boomerang: Resourceful lenses for string data. In Proceedings of the ACM SIGPLAN--SIGACT Symposium on Principles of Programming Languages (POPL).
13. Boshernitsan, M. 2006. Program manipulation via interactive transformations. Ph.D. dissertation, University of California at Berkeley, Berkeley, CA.
14. Boshernitsan, M. and Graham, S. L. 2004. ixj: interactive source-to-source transformations for java. In Companion to the 19th Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications (OOPSLA'04). ACM, New York, NY, 212--213.
15. Bravenboer, M., Kalleberg, K. T., Vermaas, R., and Visser, E. 2008. Stratego/xt 0.17. a language and toolset for program transformation. Sci. Comput. Program. 72, 1--2, 52--70.
16. Bryant, A., Catton, A., Volder, K. D., and Murphy, G. C. 2002. Explicit programming. In Proceedings of the 1st International Conference on Aspect-Oriented Software Development (AOSD'02). 10--18.
17. Bryant, R. E. 1992. Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Comput. Surv. 24, 3, 293--318.
18. Budinsky, F., Brodsky, S. A., and Merks, E. 2003. Eclipse Modeling Framework. Pearson Education, Upper Saddle River, NJ.
19. Burch, J., Clarke, E., McMillan, K., Dill, D., and Hwang, L. 1992. Symbolic model checking: 10²⁰ states and beyond. Inform. Comput. 98, 2, 142--170.
20. Carroll, M. D. and Ryder, B. G. 1988. Incremental data flow analysis via dominator and attribute updates. In Proceedings of the 15th SIGPLAN-SIGACT Symposium on Principles of Programming Languages.
21. Clements, P. and Northrop, L. 2001. Software Product Lines: Practices and Patterns. Addison-Wesley, Boston, MA.
22. Clifton, C., Leavens, G. T., Chambers, C., and Millstein, T. 2000. Multijava: Modular open classes and symmetric multiple dispatch for java. In Proceedings of the 15th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'00). ACM, New York, NY, 130--145.
23. Colyer, A. and Clement, A. 2004. Large-scale aosd for middleware. In Proceedings of the 3rd International Conference on Aspect-Oriented Software Development (AOSD'04). ACM, New York, NY, 56--65.
24. Cousot, P. and Cousot, R. 1977. Abstract interpretation: A unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM Symposium on Principles of Programming Languages. 238--252.
25. Cousot, P. and Cousot, R. 1979. Systematic design of program analysis frameworks. In Proceedings of the 6th ACM Symposium on Principles of Programming Languages. 269--282.
26. Das, M., Lerner, S., and Seigle, M. 2002. Esp: Path-sensitive program verification in polynomial time. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation.
27. Demers, A., Reps, T., and Teitelbaum, T. 1981. Incremental evaluation for attribute grammars with application to syntax-directed editors. In Proceedings of the 8th SIGPLAN-SIGACT Symposium on Principles of Programming Languages.
28. Dennett, D. C. 1992. Consciousness Explained. Back Bay Books, New York, NY.
29. Dwyer, M. B. and Clarke, L. A. 1998. A flexible architecture for building data flow analyzers. In Proceedings of the 18th International Conference on Software Engineering. 554--564.
30. Fähndrich, M., Foster, J. S., Su, Z., and Aiken, A. 1998. Partial online cycle elimination in inclusion constraint graphs. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'98). 85--96.
31. Foster, J. N., Greenwald, M. B., Moore, J. T., Pierce, B. C., and Schmitt, A. 2007. Combinators for bidirectional tree transformations: A linguistic approach to the view-update problem. ACM Trans. on Program. Lang. Syst. 29, 3, 17.
32. Foster, J. N., Pilkiewicz, A., and Pierce, B. C. 2008. Quotient lenses. In Proceedings of the ACM SIGPLAN International Conference on Functional Programming (ICFP).
33. Gafter, N. 2006. Super type tokens. http://gafter.blogspot.com/2006/12/super-type-tokens.html.
34. Gamma, E., Helm, R., Johnson, R., and Vlissides, J. 1995. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley, Boston, MA.
35. Google. 2007. Google collections library 0.5 (alpha). http://code.google.com/p/google-collections/.
36. Gosling, J., Joy, B., Steele, G., and Bracha, G. 2005. The Java Language Specification, 3rd ed. Addison-Wesley, Boston, MA.
37. Griswold, W. G. 2001. Coping with crosscutting software changes using information transparency. In Proceedings of the 3rd International Conference on Metalevel Architectures and Separation of Crosscutting Concerns. 250--265.
38. Griswold, W. G., Sullivan, K., Song, Y., Shonle, M., Tewari, N., Cai, Y., and Rajan, H. 2006. Modular software design with crosscutting interfaces. IEEE Softw. 23, 1, 51--60.
39. Hannemann, J. and Kiczales, G. 2002. Design pattern implementation in java and aspectj. In Proceedings of the 17th ACM SIGPLAN Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA'02). 161--173.
40. Hannemann, J., Murphy, G. C., and Kiczales, G. 2005. Role-based refactoring of crosscutting concerns. In Proceedings of the International Conference on Aspect Oriented Software Development (AOSD). 135--146.
41. Hu, Z., Mu, S.-C., and Takeichi, M. 2004. A programmable editor for developing structured documents based on bidirectional transformations. In Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'04). ACM, New York, NY, 178--189.
42. Kawanaka, S. and Hosoya, H. 2006. biXid: A bidirectional transformation language for XML. In Proceedings of the 11th ACM SIGPLAN International Conference on Functional Programming (ICFP'06). 201--214.
43. Kennedy, A. J. 2004. Functional pearl pickler combinators. J. Funct. Program. 14, 6, 727--739.
44. Kiczales, G., Hilsdale, E., Hugunin, J., Kersten, M., Palm, J., and Griswold, W. 2001a. Getting started with aspectj. Commun. ACM 44, 10, 59--65.
45. Kiczales, G., Hilsdale, E., Hugunin, J., Kersten, M., Palm, J., and Griswold, W. G. 2001b. An overview of AspectJ. In Proceedings of the European Conference on Object-Oriented Programming. 327--353.
46. Kiczales, G., Lamping, J., Mendhekar, A., Maeda, C., Lopes, C., Loingtier, J., and Irwin, J. 1997. Aspect-oriented programming. In Proceedings of the European Conference on Object-Oriented Programming. 220--242.
47. Kotik, G. and Markosian, L. 1989. Automating software analysis and testing using a program transformation system. In Proceedings of the ACM SIGSOFT 3rd Symposium on Software Testing, Analysis, and Verification. ACM Press, New York, NY, 75--84.
48. Kozaczynski, W., Ning, J., and Engberts, A. 1992. Program concept recognition and transformation. IEEE Trans. Softw. Eng. 18, 12, 1065--1075.
49. Lacey, D., Jones, N. D., Wyk, E. V., and Frederiksen, C. C. 2002. Proving correctness of compiler optimizations by temporal logic. In Proceedings of the 29th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages.
50. Lerner, S., Millstein, T., Rice, E., and Chambers, C. 2005. Automated soundness proofs for dataflow analyses and transformations via local rules. In Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'05). ACM Press, New York, NY, 364--377.
51. Lieberherr, K. J. 1996. Adaptive Object-Oriented Software: The Demeter Method with Propagation Patterns. PWS Publishing Company, Boston, MA.
52. Lieberherr, K. J. and Orleans, D. 1997. Preventive program maintenance in Demeter/Java (research demonstration). In Proceedings of the International Conference on Software Engineering. 604--605.
53. Liu, J., Batory, D., and Lengauer, C. 2006. Feature oriented refactoring of legacy applications. In Proceedings of the 28th International Conference on Software Engineering (ICSE'06). 112--121.
54. Marin, M., Moonen, L., and van Deursen, A. 2005. An approach to aspect refactoring based on crosscutting concern types. In Proceedings of the Workshop on Modeling and Analysis of Concerns in Software (MACS'05). ACM Press, New York, NY, 1--5.
55. Martin, M., Livshits, B., and Lam, M. S. 2005. Finding application errors and security flaws using pql: A program query language. SIGPLAN Not. 40, 10, 365--383.
56. Masticola, S. P., Marlowe, T. J., and Ryder, B. G. 1995. Lattice frameworks for multisource and bidirectional data flow problems. ACM Trans. Program. Lang. Syst. 17, 5, 777--803.
57. Metsker, S. and Wake, W. C. 2006. Design Patterns in Java. Addison-Wesley, Boston, MA.
58. Moor, O. d., Verbaere, M., Hajiyev, E., Avgustinov, P., Ekman, T., Ongkingco, N., Sereni, D., and Tibble, J. 2007. Keynote address: .ql for source code analysis. In Proceedings of the 7th IEEE International Working Conference on Source Code Analysis and Manipulation (SCAM'07). 3--16.
59. Morgan, C., Volder, K. D., and Wohlstadter, E. 2007. A static aspect language for checking design rules. In Proceedings of the International Conterence on Aspect Oriented Software Development (AOSD). 63--72.
60. Nita, M. and Notkin, D. 2010. Using twinning to adapt programs to alternative apis. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering (ICSE'10). 205--214.
61. Nystrom, N., Clarkson, M., and Myers, A. 2003. Polyglot: An extensible compiler framework for java. In Proceedings of the 12th International Confernce on Compiler Construction.
62. Orleans, D. and Lieberherr, K. J. 2001. Dj: Dynamic adaptive programming in java. In Proceedings of the 3rd International Conference on Metalevel Architectures and Separation of Crosscutting Concerns. 73--80.
63. Parnas, D. L. 1972. On the criteria to be used in decomposing systems into modules. Commun. ACM 15, 12, 1053--1058.
64. Parnas, D. L. 2001. Software Fundamentals: Collected Papers by David L. Parnas. Addison-Wesley, Boston, MA. 193--213.
65. Reichenbach, C., Coughlin, D., and Diwan, A. 2009. Program metamorphosis. In Proceedings of the 23rd European Conference on Object-Oriented Programming. 394--418.
66. Reps, T. W. 1994. Demand interprocedural program analysis using logic databases. In Applications of Logic Databases, R. Ramakrishnan, Ed. Kluwer Academic Publishers, Boston, MA, 163--196.
67. Roberts, D. B. 1999. Practical analysis for refactoring. Ph.D. dissertation, University of Illinois at Urbana-Champaign, Champaign, IL.
68. Shankar, A. and Bodík, R. 2007. Ditto: automatic incrementalization of data structure invariant checks (in java). In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07). 310--319.
69. Shonle, M. 2007. Modular-like transformations and style checking for crosscutting programming concepts. In Companion to the Proceedings of the 29th International Conference on Software Engineering. IEEE Computer Society, Los Alamitos, CA, 95--96.
70. Shonle, M., Griswold, W. G., and Lerner, S. 2007. Beyond refactoring: A framework for modular maintenance of crosscutting design idioms. In Proceedings of the the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on the Foundations of Software Engineering. ACM, New York, NY, 175--184.
71. Shonle, M., Griswold, W. G., and Lerner, S. 2008a. Addressing common crosscutting problems with arcum. In Proceedings of the 8th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering.
72. Shonle, M., Griswold, W. G., and Lerner, S. 2008b. When refactoring acts like modularity: Keeping options open with persistent condition checking. In Proceedings of the Second Workshop on Refactoring Tools.
73. Simonyi, C. 1995. The death of computer languages, the birth of intentional programming. Tech. rep. MSR-TR-95-52, Microsoft Research.
74. Sittampalam, G., de Moor, O., and Larsen, K. F. 2004. Incremental execution of transformation specifications. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL'04). ACM, New York, NY, 26--38.
75. Steffen, B. 1991. Data flow analysis as model checking. In Theoretical Aspects of Computer Science, T. Ito and A. Meyer, Eds. Lecture Notes in Computer Science, vol. 526. Springer-Verlag, Berlin, 346--364.
76. Steffen, J. 1985. Interactive examination of a c program with cscope. In Proceedings of the Winter USENIX Conference.
77. Sullivan, K., Griswold, W. G., Song, Y., Cai, Y., Shonle, M., Tewari, N., and Rajan, H. 2005. Information hiding interfaces for aspect-oriented design. In Proceedings of the 10th European Software Engineering Conference held jointly with the 13th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York, NY, 166--175.
78. Tarr, P., Ossher, H., and Sutton, Jr., S. M. 2002. Hyper/j: Multi-dimensional separation of concerns for java. In Proceedings of the International Conference on Software Engineering (ICSE'02). 689--690.
79. Tilevich, E. and Back, G. 2008. “Program, enhance thyself!” -- demand-driven pattern-oriented program enhancement. In Proceedings of the International Conference on Aspect Oriented Software Development (AOSD).
80. Tip, F., Kiezun, A., and Bäumer, D. 2003. Refactoring for generalization using type constraints. In Proceedings of the Conference on Object Oriented Programming, Systems, Languages, and Applications. 13--26.
81. Tjiang, S. W. K. and Hennessy, J. L. 1992. Sharlit -- A tool for building optimizers. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 82--93.
82. Venkatesh, G. A. and Fischer, C. N. 1992. SPARE: A development environment for program analysis algorithms. IEEE Trans. Softw. Eng. 18, 4, 304--318.
83. Verbaere, M., Ettinger, R., and de Moor, O. 2006. Jungl: A scripting language for refactoring. In Proceedings of the International Conference on Software Engineering. 172--181.
84. von Dincklage, D. 2003. Making patterns explicit with metaprogramming. In Proceedings of the 2nd International Conference on Generative Programming and Component Engineering. 287--306.
85. Whaley, J., Avots, D., Carbin, M., and Lam, M. S. 2005. Using Datalog and binary decision diagrams for program analysis. In Proceedings of the 3rd Asian Symposium on Programming Languages and Systems, K. Yi, Ed. Lecture Notes in Computer Science, vol. 3780. Springer-Verlag, Berlin.
86. Whaley, J. and Lam, M. S. 2004. Cloning-based context-sensitive pointer alias analysis using binary decision diagrams. In Proceedings of the Conference on Programming Language Design and Implementation.
87. Whitfield, D. L. and Soffa, M. L. 1997. An approach for exploring code improving transformations. ACM Trans. Program. Lang. Syst. 19, 6, 1053--1084.
88. Xiong, Y., Liu, D., Hu, Z., Zhao, H., Takeichi, M., and Mei, H. 2007. Towards automatic model synchronization from model transformations. In Proceedings of the 22nd IEEE/ACM International Conference on Automated Software Engineering (ASE'07). ACM, New York, NY, 164--173.
89. Yi, K. and Harrison III, W. L. 1993. Automatic generation and management of interprocedural program analyses. In Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 246--259.

Index Terms

• Software and its engineering

  • Software notations and tools

    • Context specific languages

      • Domain specific languages

    • General programming languages

      • Language features

        • Patterns

    • System description languages

  • Software organization and properties

    • Software system structures

      • Distributed systems organizing principles

        • Client-server architectures

      • Software architectures