Pattern-based Rewriting through Abstraction

• Autorzy: Bottoni P. , Guerra E. , de Lara J.

Identyfikatory

DOI

10.3233/FI-2016-1325

• Języki publikacji: EN

Abstrakty

EN

Model-based development relies on models in different phases for different purposes, with modelling patterns being used to document and gather knowledge about good practices in specific domains, to analyse the quality of existing designs, and to guide the construction and refactoring of models. Providing a formal basis for the use of patterns would also support their integration with existing approaches to model transformation. To this end, we turn to the commonly used, in this context, machinery of graph transformations and provide an algebraic-categorical formalization of modelling patterns, which can express variability and required/forbidden application contexts. This allows the definition of transformation rules having patterns in left and right-hand sides, which can be used to express refactorings towards patterns, change the use of one pattern by a different one, or switch between pattern variants. A key element in our proposal is the use of operations to abstract models into patterns, so that they can be manipulated by pattern rules, thus leading to a rewriting mechanism for classes of graphs described by patterns and not just individual graphs. The proposal is illustrated with examples in object-oriented software design patterns and enterprise architecture patterns, but can be applied to any other domain where patterns are used for modelling.

Słowa kluczowe

EN

model-based development; modelling patterns; graphs; trees; category theory; graph transformation; refactoring; pattern variants

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 144, nr 2
• Strony: 109--160
• Opis fizyczny: Bibliogr. 51 poz., rys.

Twórcy

autor

Bottoni P.

• Computer Science Department, “Sapienza” Università di Roma, Italy

autor

Guerra E.

• Computer Science Department, Universidad Autónoma de Madrid, Spain

autor

de Lara J.

• Computer Science Department, Universidad Autónoma de Madrid, Spain

Bibliografia

• [1] Kelly S, Tolvanen JP. Domain-Specific Modeling: Enabling Full Code Generation. Wiley-IEEE CS; 2008.
• [2] OMG. MDA home page; 2009. http://www.omg.org/mda/.
• [3] Völter M, Stahl T. Model-driven software development. Wiley; 2006.
• [4] Alexander C. A Pattern Language: Towns, Buildings, Construction. Oxford University Press; 1977.
• [5] Gamma E, Helm R, Johnson R, Vlissides JM. Design Patterns. Elements of Reusable Object-Oriented Software. Addison Wesley; 1994.
• [6] Bottoni P, Guerra E, de Lara J. A language-independent and formal approach to pattern-based modeling with support for composition and analysis. Information & Software Technology. 2010;52(8):821–844. doi:10.1016/j.infsof.2010.03.005.
• [7] Bottoni P, Guerra E, de Lara J. Formal Foundation for Pattern-Based Modelling. In: Chechik M, Wirsing M, editors. FASE’09. vol. 5503 of LNCS. Springer; 2009. p. 278–293. doi:10.1007/978-3-642-00593-0 19.
• [8] Mac Lane S. Categories for the Working Mathematician. 2nd Edition. Graduate Texts in Mathematics Vol 5. Springer; 1998.
• [9] Ehrig H, Ehrig K, Prange U, Taentzer G. Fundamentals of Algebraic Graph Transformation. Springer; 2006.
• [10] Fowler M. Patterns of Enterprise Application Architecture. Addison-Wesley Professional, 1edition; 2002.
• [11] Baresi L, Heckel R, Thöne S, Varró D. Style-based modeling and refinement of service-oriented architectures. A graph transformation-based approach. Journal on Software and Systems Modeling. 2005;5(2):187–207. doi:10.1007/s10270-006-0001-4.
• [12] Bisztray D, Heckel R, Ehrig H. Verification of Architectural Refactorings: Rule Extraction and Tool Support. ECEASST. 2008;16. doi:10.1007/978-3-540-87405-8 37.
• [13] Tamzalit D, Mens T. Guiding Architectural Restructuring through Architectural Styles. In: ECBS’10; 2010. p. 69–78. doi:10.1109/ECBS.2010.15.
• [14] Mens T, Tourwé T. A Survey of Software Refactoring. IEEE Trans Software Eng. 2004, 30(2):126–139. doi:10.1109/TSE.2004.1265817.
• [15] Arendt T, Taentzer G. Integration of smells and refactorings within the Eclipse modeling framework. In: Proc. WRT’12. ACM; 2012. p. 8–15. doi:10.1145/2328876.2328878.
• [16] Courcelle B. In: The Expression of Graph Properties and Graph Transformations in Monadic Second-Order Logic. vol. 1. World Scientific; 1997. p. 313–400.
• [17] Drewes F, Hoffmann B, Plump D. Hierarchical Graph Transformation. J Comput Syst Sci. 2002, 64(2):249–283.
• [18] Bruni R, Gadducci F, Lluch-Lafuente A. An Algebra of Hierarchical Graphs. In: Proc. TGC 2010. vol. 6084 of LNCS. Springer; 2010. p. 205–221. doi:10.1007/978-3-642-15640-3 14.
• [19] Habel A, Pennemann KH. Nested Constraints and Application Conditions for High-Level Structures. In: Formal Methods in Software and Systems Modeling. vol. 3393 of LNCS. Springer; 2005. p. 293–308. doi:10.1007/978-3-540-31847-7 17.
• [20] Ehrig H, Ehrig K, Habel A, Pennemann KH. Theory of Constraints and Application Conditions: From Graphs to High-Level Structures. Fundam Inform. 2006;74(1):135–166.
• [21] Ehrig H, Ehrig K, de Lara J, Taentzer G, Varró D, Varró-Gyapay S. Termination Criteria for Model Transformation. In: FASE’05. vol. 3442 of LNCS. Springer; 2005. p. 49–63. doi:10.1007/978-3-540-31984-9 5.
• [22] Prange U, Ehrig H, Lambers L. Construction and Properties of Adhesive and Weak Adhesive High-Level Replacement Categories. Applied Categorical Structures. 2008;16(3):365–388. doi:10.1007/s10485-007-9106-3.
• [23] Warren I, Ransom J. Renaissance: A Method to Support Software System Evolution. In: COMPSAC’02. IEEE Computer Society; 2002. p. 415–420. doi:10.1109/CMPSAC.2002.1045037.
• [24] France RB, Kim DK, Ghosh S, Song E. A UML-Based Pattern Specification Technique. IEEE Trans Soft Eng. 2004;30(3):193–206. doi:10.1109/TSE.2004.1271174.
• [25] Elaasar M, Briand LC, Labiche Y. A Metamodeling Approach to Pattern Specification. In: MoDELS 2006. No. 4199 in LNCS; 2006. p. 484–498. doi:10.1007/11880240 34.
• [26] Rensink A. Canonical Graph Shapes. In: ESOP’04. vol. 2986 of LNCS. Springer; 2004. p. 401–415. doi:10.1007/978-3-540-24725-8 28.
• [27] Bauer J, Boneva I, Kurbán ME, Rensink A. A Modal-Logic Based Graph Abstraction. In: ICGT’08. vol. 5214 of LNCS. Springer; 2008. p. 321–335. doi:10.1007/978-3-540-87405-8 22.
• [28] Rensink A, Distefano D. Abstract Graph Transformation. Electr Notes Theor Comput Sci. 2006;157(1):39–59. doi:http://dx.doi.org/10.1016/j.entcs.2006.01.022.
• [29] Boneva IB, Rensink A, Kurban ME, Bauer J. Graph Abstraction and Abstract Graph Transformation. Enschede: Centre for Telematics and Information Technology University of Twente; 2007. TR-CTIT-07-50.
• [30] Rensink A, Kuperus J. Repotting the Geraniums: On Nested Graph Transformation Rules. ECEASST. 2009;18.
• [31] Rensink A, Zambon E. Pattern-Based Graph Abstraction. In: ICGT’12. vol. 7562 of LNCS. Springer; 2012. p. 66–80. doi:10.1007/978-3-642-33654-6 5.
• [32] Habel A, Pennemann KH. Correctness of high-level transformation systems relative to nested conditions. Mathematical Structures in Computer Science. 2009;19(2):245–296.
• [33] Hoffmann B. Shapely Hierarchical Graph Transformation. In: HCC’01. IEEE Computer Society; 2001. p. 30–37. doi:10.1109/HCC.2001.995230.
• [34] Drewes F, Hoffmann B, Janssens D, Minas M, Eetvelde NV. Adaptive Star Grammars. In: ICGT’06. vol. 4178 of LNCS. Springer; 2006. p. 77–91. doi:10.1007/11841883 7.
• [35] Taentzer G. Parallel and distributed graph transformation - formal description and application to communication-based systems. Berichte aus der Informatik. Shaker; 1996.
• [36] Zhu H, Bayley I. An algebra of design patterns. ACM Trans Softw Eng Methodol. 2013;22(3):23. doi:10.1145/2491509.2491517.
• [37] Angluin D. Finding Patterns Common to a Set of Strings. J Comput Syst Sci. 1980;21(1):46–62. doi:10.1016/0022-0000(80)90041-0.
• [38] Kari L, Mateescu A, Paun G, Salomaa A. Multi-Pattern Languages. Theor Comput Sci. 1995;141(1&2):253–268. doi:10.1016/0304-3975(94)00087-Y.
• [39] Paun G, Rozenberg G, Salomaa A. Pattern Grammars. Journal of Automata, Languages and Combinatorics. 1996;1(3):219–242.
• [40] Mitrana V, Paun G, Rozenberg G, Salomaa A. Pattern Systems. Theor Comput Sci. 1996;154(2):183–201. doi:10.1016/0304-3975(94)00258-4”.
• [41] Bottoni P, Labella A, Paun G. Chomsky Hierarchies of Pattern Languages. Annals of the Bucharest University. 1998;47:27–34.
• [42] Santini S. Regular languages with variables on graphs. Inf Comput. 2012;211:1–28. doi:http://dx.doi.org/10.1016/j.ic.2011.10.010.
• [43] Bottoni P, Parisi Presicce F. Patterns on Graphs. In: GRATRA 2000 Workshop. Tech. Rep. 2000-02 Fachbereich Informatik, Tech.Univ. Berlin; 2000. p. 180–188.
• [44] Taentzer G, Goedicke M, Meyer T. Dynamic Change Management by Distributed Graph Transformation: Towards Configurable Distributed Systems. In: TAGT’78. vol. 1764 of LNCS; 1998. p. 179–193. doi:10.1007/978-3-540-46464-8 13.
• [45] Parisi-Presicce F, Piersanti G. Multilevel Graph Grammars. In: WG’94. vol. 903 of Lecture Notes in Computer Science. Springer; 1995. p. 51–64. doi:10.1007/3-540-59071-4 37.
• [46] Bruni R, Gadducci F, Lluch-Lafuente A. An Algebra of Hierarchical Graphs and its Application to Structural Encoding. Sci Ann Comp Sci. 2010;20:53–96.
• [47] Goguen JA, Burstall RM. Institutions: Abstract Model Theory for Specification and Programming. J ACM. 1992;39(1):95–146. Available from: http://doi.acm.org/10.1145/147508.147524. doi:10.1145/147508.147524.
• [48] Corradini A, Gadducci F, Ribeiro L. An Institution for Graph Transformation. In: Proc. WADT 2010. vol. 7137 of LNCS. Springer; 2012. p. 160–174. doi:10.1007/978-3-642-28412-0 11.
• [49] Corradini A, Heindel T, Hermann F, König B. Sesqui-Pushout Rewriting. In: ICGT’06. vol. 4178 of LNCS. Springer; 2006. p. 30–45. doi:10.1007/11841883 4.
• [50] Orejas F, Ehrig H, Prange U. Reasoning with graph constraints. Formal Asp Comput. 2010;22(3-4):385–422. doi:10.1007/s00165-009-0116-9.
• [51] Plump D. Termination of Graph Rewriting is Undecidable. Fundam Inform. 1998;33(2):201–209. doi: 10.3233/FI-1998-33204.