Reverse-Engineering Reusable Language Modules from Legacy Domain-Specific Languages

Reverse-Engineering Reusable Language Modules from Legacy Domain-Specific Languages David M´endez-Acu˜na, Jose´A. Galindo, Benoit Combemale, Arnaud Blouin, Benoit Baudry, and Gurvan Le Guernic Abstract. The use of domain-specific languages (DSLs) has become a successful technique in the development of complex systems. Nevertheless, the construction of this type of languages is time-consuming and requires highly-specialized knowledge and skills. An emerging practice to facilitate this task is to enable reuse through the definition of lan-guage modules which can be later put together to build up new DSLs. Still, the identification and definition of language modules are complex and errorprone activities, thus hindering the reuse exploitation when developing DSLs. In this paper, we propose a computer-aided approach to (i) identify potential reuse in a set of legacy DSLs; and (ii) capitalize such potential reuse by extracting a set of reusable language modules with well defined interfaces that facilitate their assembly. We validate our approach by using realistic DSLs coming out from industrial case studies and obtained from public GitHub repositories. 1 Introduction A domain-specific language (DSL) is a software language whose expressiveness is limited to a well-defined domain. A DSL offers the abstractions (a.k.a., language constructs) needed to describe an aspect of a system under construction. For example, we find DSLs to build graphical user interfaces [22] and to specify security policies [15]. The use of DSLs has become a successful technique to achieve separation of concerns in the development of complex systems [7]. Naturally, the adoption of such a language-oriented vision relies on the availability of the DSLs necessary to describe all the aspects of the system [3]. This implies the development of many DSLs, which is a challenging task due the specialized knowledge it demands. The ultimate value of DSLs has been severely limited by the cost of the associated tooling (i.e., editors, parsers, etc.) [13]. To improve cost-benefit when using DSLs, the research community in software languages engineering has proposed mechanisms to increase reuse during the language development process. The idea is to leverage previous engineering efforts and minimize implementation from scratch. In particular, there are approaches that take ideas from Component-Based Software Engineering [4]in the construction of DSLs (e.g., [17,24]). Language constructs are grouped into interdependent language modules that can be later integrated as part of the specification of future DSLs. Current approaches for the modular development of DSLs are focused on providing foundations and tooling that allow language designers to specify dependencies among language modules as well as to provide the composition operators needed during the subsequent assembly process. In practice, however, reuse not necessarily achieved through monolithic processes where language designers define language modules while trying to predict that they will be useful in future DSLs. Contrariwise, the exploitation of reuse is often an iterative process where reuse opportunities are discovered in the form of replicated functionalities during the construction of individual DSLs. Those functionalities can be extracted in reusable language modules. For example, many DSLs offer expression languages with simple imperative instructions, variables management, and mathematical operators. Xbase [1] is a successful experiment that shows that, using compatible tooling, such replicated functionality can be encapsulated and (re)used in different DSLs. A major complexity of this reuse process is that both, the identification of replicated functionalities and the extraction of the corresponding language modules are manually-performed activities. Language designers must compare DSL specifications to identify replicated language constructs, and then, to perform a refactoring process to extract those replications in language modules. Due the large number of language constructs defined within a DSL, and the dependencies among them, this process is tedious and error-prone [9]. As a result, modularization approaches are often discarded, and non-systematic reuse practices such as simple copy&paste are still quite popular in DSLs development processes. This type of solutions produce many code clones within DSLs’ specifications thus replicating bugs and increasing maintenance costs [26]. In this paper, we propose the use of reverse-engineering techniques to automatically extract reusable language modules from a given set of legacy DSLs. To this end, we define some comparison operators that allow the identification of replicated language constructs. These operators take into account not only the names of the constructs but also the inter-constructs relationships and the semantics. Then, we extract replicated constructs as interdependent language modules whose dependencies are expressed through well-defined interfaces. Those language modules can be later assembled among them to build up new DSLs. The approach presented in this paper is implemented in a language workbench on top of the Eclipse Modeling Framework. The validation of our approach is twofold. Firstly, we apply the reverseengineering strategy to a case study, deeply explained by Crane et al. [8], and composed of a set of DSLs for finite state machines. Secondly, we explore public GitHub repositories in search of insights that indicate how common is the phenomenon of specification clones in DSLs development process. The reminder of this paper is organized as follows: Sect. 2introduces a set of preliminary definitions/assumptions that we use all along the paper. Section 3 presents a motivation to the problem by introducing a concrete development scenario. Section 4describes the proposed approach. Section 5presents the validation. Section 6discusses the related work. Section 7concludes the paper. 2 Background: Domain-Specific Languages in a Nutshell We use this section to introduce some basic definitions intended to establish a unified vocabulary that facilitates the comprehension of the ideas presented in the rest of the paper. DSLs Specification. Like general purpose languages, domain specific languages are defined regarding three implementation concerns: abstract syntax, concrete syntax, and semantics [11]. The abstract syntax refers to the structure of the DSL expressed as the set of concepts that are relevant to the domain and the relationships among them. The concrete syntax relates language concepts to a set of symbols that facilitate the usage of the DSL. These representations are usually supported by editors acting as the user interface of the DSL. Finally, the semantics of a DSL assigns a precise meaning to each of its language constructs. More precisely, static semantics constrains the sets of valid programs while dynamic semantics specifies how they are evaluated. Technological Space. There are diverse technological spaces available for the implementation of the aforementioned concerns [18]. The abstract syntax can be specified using context-free grammars or metamodels. The concrete syntax can be either textual or graphical. The static semantics can be expressed through diverse constraint languages. Finally, the dynamic semantics can be defined operationally, denotationally, or axiomatically [20]. In this paper, we are interested in executable domain-specific modeling languages (xDSMLs) where the abstract syntax is specified by means of metamodels, and dynamic semantics is specified operationally as a set of domain-specific actions [5]. Domain-specific actions are weaved on the metaclasses of a metamodel [12]. The concrete syntax and static semantics are out of the scope of this paper. Example: A DSL for Finite State Machines. Figure 1shows a DSL for finite states machines. In that case, the metamodel that implements the abstract syntax contains three metaclasses: StateMachine,State,andTransition. There are some references among those metaclasses representing the relationships existing among the corresponding language constructs. The domain-specific actions at the right of the Fig. 1introduce the operational semantics to the DSL. In this example, there is one domain-specific action for each metaclass. In executable metamodeling, the interactions among domainspecific actions can be internally specified in their implementation by means of the interpreter pattern, or externalized in a model of computation [5]. Fig. 1. A simple DSL for finite state machines 3 Motivating Scenario Suppose a team of language designers working on the construction of the DSL for finite state machines presented in Sect. 2. During that process, language designers implement the constructs typically required for expressing finite state machines: states, transitions, events, and so on. Besides, a constraint language that allows final users to express guards on the transitions should be provided, as well as an expression language for the specification of actions in the states. After language designers release the DSL for state machines, they are required to build another DSL. The new DSL is intended to manipulate the traditional Logo turtle, which is often used in elementary schools for teaching the first foundations of programming [21]. Instead of states and transitions, Logo offers some primitives (such as Forward,Backward,Left,andRight) to move a character (i.e., the turtle) within a bounded canvas. Still, Logo also requires an expression language to specify complex movements. For example, final users may write instructions such as: forward (x + 2). At this point, language designers face the problem of reusing the expression language they already defined for the state machine DSL. Because this expression language was not implemented separately from the DSL for state machines, the typical approach is to copy&paste its corresponding specification segment in the second DSL. In doing so, language designers introduce specification clones all along the project. This practice is repeated in the construction of each new DSL where some reuse is needed. For example, if our language designers team is required to build a third DSL such as a flowchart language that uses not only expressions but also constraints, they will (again) copy&paste the corresponding specification segments. After some iterations, we obtain a set of DSLs with many specification clones, which is quite expensive to maintain. Fig. 2. Approach overview 4 Proposed Approach We propose the use of reverse-engineering techniques to deal with the problem illustrated above. Our proposal, summarized in Fig. 2, starts from a classical language development process where a team of language designers develops a set DSLs (a.k.a., the DSLs portfolio) introducing specification clones by copy&paste repeated constructs. This portfolio is the input of a reverse-engineering strategy to extract a set of reusable language modules. Those modules are useful for two purposes. First, they can be assembled to build a new version of the portfolio that does not contain specification clones, thus reducing maintenance costs. Second, they can be used in the construction of future DSLs. In that case, language designers might have to build new language modules. 4.1 Principles of Reverse-Engineering for Language Reuse Our reverse-engineering strategy is based on five principles that will be introduced in this section. Then, we explain how we use those principles to extract a catalog of reusable language modules. Principle 1: DSL specifications are comparable. Hence, specification clones can be automatically detected. Two DSL specifications can be compared each other. This comparison can be either coarse-grained indicating if the two specifications are equal regarding both syntax and semantics, or fine-grained detecting segments of the specifications that match. The latter approach permits to identify specification clones between two DSLs and supposes the comparison of each specification element. In the case of the technological space discussed in this paper, specification elements for the abstract syntax are metaclasses whereas specification elements for the semantics are domain-specific actions. For the case of comparison of metaclasses, we need to take into account that a metaclass is specified by a name, a set of attributes, and a set of references to other metaclasses. Two metaclasses are considered as equal (and so, they are clones) if all those elements match. Formally, comparison of metaclasses can be specified by the operator . :MC ×MC →bool (1) MCAMCB=true =⇒ MCA.name =MCB.name ∧ ∀a1∈MCA.attr |(∃a2∈MCB.attr |a1=a2)∧ ∀r1∈MCA.refs |(∃r2∈MCB.refs |r1=r2)∧ |MCA.attr|=|MCB.attr|∧|MCA.refs|=|MCB.refs| (2) In turn, for the case of comparison for domain-specific actions we need to take into account that –like methods in Java– domain-specific actions have a signature that specifies its contract (i.e., return type, visibility, parameters, name, and so on), and a body where the behavior is implemented. Two domainspecific actions are equal if they have the same signature and body. Whereas comparison of signatures can be performed by syntactic comparison of the signature elements, comparison of bodies can be arbitrary difficult. If we try to compare the behavior of the domain-specific actions, then we will have to address the semantic equivalence problem, which is known to be undecidable [16]. To address this issue, we conceive bodies comparison in terms of its abstract syntax tree as proposed by Biegel et al. [2]. In other words, to compare two bodies, we first parse them to extract their abstract syntax tree, and then we compare those trees. Note that this decision makes sense because we are detecting specification clones more than equivalent behavior. Formally, comparison of domain-specific actions (DSAs) is specified by the operator . :DSA ×DSA →bool (3) DSAADSAB=true =⇒ DSAA.name =DSAB.name ∧ DSAA.returnType =DSAB.returnType ∧ DSAA.visibility =DSAB.visibility ∧ ∀p1∈DSAA.params |(∃p2∈DSAB.params |p1=p2)∧ |DSAA.params|=|DSAB.params|∧ DSAA.AST =DSAB.AST (4) Principle 2: Specification clones are viewed as overlapping. If a DSL specification is viewed as sets of metaclasses and domain-specific actions, then specification clones can be viewed as intersections (a.k.a., overlapping) of those sets. Figure 3illustrates this observation for the case of the motivation scenario introduced in Sect. 3. We use two Venn diagrams to represent both syntax and semantic overlapping. In that case, the fact that the expression language is used in all the DSLs is represented by the intersection in the center of the diagram where the three sets overlap the metaclass Expression (and its domain-specific actions). In turn, the intersection between the state machines DSL and Logo shows that they overlap the metaclass Constraint that belongs to the constraint language. Note that the identification of such overlapping is only possible when there are comparison operators (principle 1) that formalize the notion of equality. Fig. 3. Syntactic and semantic overlapping in a set of DSLs Principle 3: Breaking down overlapping produces reusable language modules. According to principle 2, overlapping between two DSLs implies the existence of repeated metaclasses/domain-specific actions (i.e., specification clones). Those repeated elements can be specified once and reused in the two DSLs [25, pp. 60–61]. Hence, reusable language modules can be obtained by breakingdown the overlapping existing among DSL specifications as illustrated in Fig. 4; each different intersection is encapsulated in a different language module. Fig. 4. Breaking down overlapping for obtaining reusable language modules Principle 4: Abstract syntax first, semantics afterwards. As aforementioned, the abstract syntax of a DSL specifies its structure in terms of metaclasses and relationships among them. Then, the domain-specific actions add executability to the metaclasses. Hence, the abstract syntax is the backbone of the DSL specification, and so, the process of breaking down overlapping should be performed for the abstract syntax first. Afterwards, we can do the proper for the semantics. In doing so, we need to take into consideration the phenomenon of semantic variability. That is, two cloned metaclasses might have different domain-specific actions. That occurs when two DSLs share some syntax specification but differ in their semantics. Principle 5: Metamodels are directed graphs. Hence, breaking down a metamodel is a graph partitioning problem. The metamodel that specifies the abstract syntax of a DSL can be viewed as a directed graph G. G=<V,A> where: –V: is the set of vertices each of which represents a metaclass. –A: is the set of arcs each of which represents a relationships between two meta-classes (i.e., references, containments, and inheritances). This observation is quite useful at the moment of breaking down a metamodel to satisfy the principle 4. Breaking down a metamodel can be viewed as a graph partitioning problem where the result is a finite set of subgraphs. Each subgraph represents the metamodel of a reusable language module. 4.2 Reverse-Engineering Process: The 5 Principles in Action The reverse-engineering strategy to produce a catalog of reusable modules is illustrated in Fig. 5. It is composed of two steps: identifying overlapping and breaking down. Fig. 5. Breaking down the input set by cutting overlapping Identifying Overlapping: match and merge.To identify syntactic overlapping in a given set of DSLs, we start by producing a graph for each DSL according to the principle 5. Then, we identify specification clones (the matching phase) using the comparison operators defined in principle 1. After that, we have a set of graphs (one for each DSL) and a set of matching relationships among some of the vertex. At that point we can proceed to create the overlapping defined in principle 2. To this end, we merge the matched vertex as illustrated in the second square of Fig. 5. This merging permits to remove cloned metaclasses. To identify semantic overlapping, we check whether the domain-specific actions of the matched metaclasses are equal as well. If so, they can be considered as clones in the semantic specification, so there is semantic overlapping. In that case, these domain-specific actions are merged. If not all the domain-specific actions associated to the matched metaclasses are the same, different clusters of domain-specific actions are created, thus establishing semantic variation points. Breaking Down: cut and encapsulate.Once overlapping among the DSLs of the portfolio has been identified, we extract a set of reusable language modules. This process corresponds to break-down the graph produced in the last phase using a graph partitioning algorithm. The algorithm receives the graph(s) obtained from the merging process and returns a set of vertex clusters: one cluster for each intersection of the Venn diagram. Arcs defined between vertices in different clusters can be considered as cross-cutting dependencies between clusters. Then, we encapsulate each vertex cluster in the form of language modules. Each module contains a metamodel, a set of domain-specific actions, and a set of dependencies towards other language modules. Dependencies between language modules can be viewed through the classical required and provided roles in components-based software development illustrated in Fig. 6. There is a requiring module that uses some constructs provided by a providing module. The requiring module has a dependency relationship towards the providing one. To avoid direct references between modules, we introduce the notion of interfaces for dealing with modules’ dependencies. The requiring language has a required interface whereas the providing one has the provided interface. A required interface contains the set of constructs required by the requiring module that are supposed to be replaced by actual construct provided by another module(s). Fig. 6. Interfaces for language modules We use model types [23] to express both required and provided interfaces. A module can have some references to the constructs declared in its required 12. J´ez´equel, J.-M., Combemale, B., Barais, O., Monperrus, M., Fouquet, F.: Mashup of metalanguages and its implementation in the kermeta language workbench. Softw. Syst. Mod. 14(2), 905–920 (2015) 13. J´ez´equel, J.-M., M´endez-Acu˜na, D., Degueule, T., Combemale, B., Barais, O.: When systems engineering meets software language engineering. In: Boulanger, F., Krob, D., Morel, G., Roussel, J.-C. (eds.) CSD&M 2014, pp. 1–13. Springer International Publishing, Heidelberg (2015) 14. de Lara, J., Guerra, E.: Domain-specific textual meta-modelling languages for model driven engineering. In: Vallecillo, A., Tolvanen, J.-P., Kindler, E., St¨orrle, H., Kolovos, D. (eds.) ECMFA 2012. LNCS, vol. 7349, pp. 259–274. Springer, Heidelberg (2012) 15. Lodderstedt, T., Basin, D., Doser, J.: SecureUML: a UML-based modeling language for model-driven security. In: J´ez´equel, J.-M., Hussmann, H., Cook, S. (eds.) UML 2002. LNCS, vol. 2460, pp. 426–441. Springer, Heidelberg (2002) 16. Lucanu, D., Rusu, V.: Program equivalence by circular reasoning. In: Johnsen, E.B., Petre, L. (eds.) IFM 2013. LNCS, vol. 7940, pp. 362–377. Springer, Heidelberg (2013) 17. Mernik, M.: An object-oriented approach to language compositions for software language engineering. J. Syst. Softw. 86(9), 2451–2464 (2013) 18. Mernik, M., Heering, J., Sloane, A.M.: When and how to develop domain-specific languages. ACM Comput. Surv. 37(4), 316–344 (2005) 19. Mishra, S., Kushwaha, D., Misra, A.: Creating reusable software component from object-oriented legacy system through reverse engineering. J. Object Technol. 8(5), 133–152 (2009) 20. Mosses, P.D.: The varieties of programming language semantics. In: Bjørner, D., Broy, M., Zamulin, A.V. (eds.) PSI 2001. LNCS, vol. 2244, pp. 165–190. Springer, Heidelberg (2001) 21. Olson, A., Kieren, T., Ludwig, S.: Linking logo, levels and language in mathematics. Educ. Stud. Math. 18(4), 359–370 (1987) 22. Oney, S., Myers, B., Brandt, J.: Constraintjs: programming interactive behaviors for the web by integrating constraints and states. In: Proceedings of the Annual Symposium on User Interface Software and Technology, UIST 2012, pp. 229–238, Cambridge, Massachusetts, USA. ACM (2012) 23. Steel, J., J´ez´equel, J.-M.: On model typing. Softw. Syst. Mod. 6(4), 401–414 (2007) 24. Voelter, M.: Language and IDE modularization and composition with MPS. In: L¨ammel, R., Saraiva, J., Visser, J. (eds.) GTTSE 2011. LNCS, vol. 7680, pp. 383– 430. Springer, Heidelberg (2013) 25. V¨olter, M., Benz, S., Dietrich, C., Engelmann, B., Helander, M., Kats, L.C.L., Visser, E., Wachsmuth, G.: DSL Engineering - Designing, Implementing and Using Domain-Specific Languages. CreateSpace Independent Publishing Platform, Hamburg (2013). dslbook.org 26. Zschaler, S., Kolovos, D.S., Drivalos, N., Paige, R.F., Rashid, A.: Domain-specific metamodelling languages for software language engineering. In: van den Brand, M., Gaˇsevi´c, D., Gray, J. (eds.) SLE 2009. LNCS, vol. 5969, pp. 334–353. Springer, Heidelberg (2010)