An NMF solution to the State Elimination case at the TTC 2017 Georg Hinkel FZI Research Center of Information Technologies Haid-und-Neu-Straße 10-14, 76131 Karlsruhe, Germany hinkel@fzi.de Abstract This paper presents a solution to the State Elimination case at the Transformation Tool Contest (TTC) 2017 using the .NET Modeling Framework (NMF). The goal of this case was to investigate, to which degree model transformation technology may help to make the specifi- cation of state elimination more declarative and faster than the refer- ence implementation in JFLAP for smaller models. 1 Introduction State elimination is a well known technique in theoretical computer science to extract the regular expression represented by a given state machine: The regular expression represented by a state machine is extracted by eliminating states and simultaneously constructing regular expressions for the remaining states. This state elimination is repeated until only one initial and an end state is left and the regular expression can be obtained from the edge between these states. In the scope of the Transformation Tool Contest 2017, this problem has been reified as a model transformation problem[GVPK17] in order to reason on the understandability, but also on the scalability of modern model transformation systems. In this paper, we present a solution for the state elimination case using the .NET Modeling Framework (NMF, [Hin16]). However, the state elimination case does not fit either of the model transformation languages NTL [Hin13] or NMF Synchronizations [Hin15, HB17]. Both of these languages share the common assumption that it is a characterizing element of a model transformation that there is correspondence between elements of the source model and elements of some target model. Based on this simple assumption, NTL offers unidirectional, imperative model transformations meanwhile NMF Synchronizations is more declarative and supports also bidirectional and incremental transformations on top of NTL. As both of these languages do not fit, we still have NMF Expressions1 , the incrementalization system used in NMF. This incrementalization system supports the incremental execution of arbitrary analyses, but rests on the assumption that the analysis is side-effect free. Therefore, we present a solution using standard C# based on the model API generated for the given Ecore model using NMF. However, we tried to demonstrate the usage of declarative C#-parts that also reach a good degree of declarativeness. Our solution is publicly available online2 but not on SHARE because the used version of NMF requires at least Windows Vista which is not available in SHARE. Copyright c by the paper’s authors. Copying permitted for private and academic purposes. In: A. Garcia-Dominguez, F. Krikava and G. Hinkel (eds.): Proceedings of the 10th Transformation Tool Contest, Marburg, Germany, 21-07-2017, published at http://ceur-ws.org 1 There is no dedicated publication yet, but usage examples can be found in [HH15]. 2 https://github.com/georghinkel/state-elimination-mt The remainder of this paper is structured as follows: Section 2 presents our solution. Section 3 evaluates our solution with regard to performance and conciseness. Section 4 concludes the paper. 2 Solution Our proposed solution is completely standard general-purpose code. However, the language features of C# make this code already very concise such that we believe there is no further language necessary to further reduce the size of the code. As the very first step, the solution has to load the input model. For this, we need to transform the Ecore metamodel to the NMeta format used within NMF and generate code for it. Both steps can be done together using the tool Ecore2Code that ships with the NMF Nuget Package NMF-Basics. The code generator is aware of multiplicities, containments and opposite references and generates the code appropriately. However, we manually refined the generated NMeta metamodel to set lower bounds of the involved attributes to 1. As a reason, NMF generates nullable types for attributes with lower bound 0 and they are much more cumbersome to use. The actual deserialization of the input model is as straight forward as shown in Listing 1. We need to create a new repository and load the model into that repository. 1 var repository = new Mo de l Re po s it o ry () ; 2 var transiti on G ra p h = repository . Resolve ( path ) . RootElements [0] as T ra ns i ti o nG ra p h ; Listing 1: Loading the input model Our solution only solves the main task and extension task 1, due to time constraints. In the solution, we first select the initial state and create a new one, if the selected initial state has incoming edges. The implementation is depicted in Listing 2. 1 var initial = tr a ns it i on Gr a ph . States . Fir stOrDe fault ( s = > s . IsInitial ) ; 2 if ( initial . Incoming . Count > 0) 3 { 4 var newInitial = new State { IsInitial = true }; 5 transitionG ra p h . Transitions . Add ( new Transition 6 { 7 Source = newInitial , 8 Target = initial 9 }) ; 10 initial = newInitial ; 11 } Listing 2: Creating a new initial state, if the initial state has an incoming state The solution makes intensive use of the ability of C# to initialize objects inline. This syntax feature is also supported by NMF, at least for single-valued features. We also make use of the fact that NMF respects bidirectional references. Therefore, the assignments in Lines 7 and 8 of Listing 2 do not only set the Source and Target property of the newly created transition object, they also implicitly add the new transition to the Incoming and Outgoing collection for the respective states. For this to work, NMF generates special collection implementations for these two collections. This simplifies the manually written code. Next, we select a final state. Because the logic for this is slightly more complex, we extracted it into a method whose implementation is depicted in Listing 3. At first, we obtain a list of all states that are currently set as final states. If this list only contains a single element, there is no need to change anything and we simply select the state as the new final state. If there are multiple states, we create a new final state and add transitions from the existing final states to that new state. Adding those transitions is done exactly in the same way as in Listing 2. 1 var finalStates = tr a ns it i on Gr a ph . States . Where ( s = > s . IsFinal ) . ToList () ; 2 if ( finalStates . Count == 1 && finalStates [0]. Outgoing . Count == 0) 3 { 4 return finalStates [0]; 5 } 6 else 7 { 8 var newFinal = new State () ; 9 foreach ( var s in finalStates ) 10 { 11 transiti on G ra p h . Transitions . Add ( new Transition 12 { 13 Source = s , 14 Target = newFinal 15 }) ; 16 } 17 transitionG ra p h . States . Add ( newFinal ) ; 18 return newFinal ; 19 } Listing 3: Creating a new final state, if multiple final states exist The next part of the solution is the removal of states. Before we describe the implementation of this step, we take a step back to review the algorithmics of the state elimination. Roughly, removing a state implies to update i · o transitions where i is the number of incoming and o is the number of outgoing transitions. If we converted the automaton to a simple automaton as suggested in the case description, this implies i = n and o = n where n is the number of states (which decreases as states are eliminated). This immediately yields an effort of Ω(n3 ). For very large numbers of n, this is highly problematic. Therefore, we create transitions lazily to reduce the complexity. The example state machines are rather sparse, meaning that the average in and out degree of the states is low in comparison with the number of states. Still, we have to create or update i · o transitions whenever we delete a state. If we create a transition, this raises the product i · o for later removed states. Therefore, it is reasonable to delete those states with a low product i · o first as we assume that they have the least effect on eliminating other states. The implementation of this step is depicted in Listing 4. In the first line of this listing, we sort the states by the product i · o before starting to remove states. Sorting the collection can be done highly declarative in C# using the OrderBy query operator. Because .NET disallows modifications of a collection while it is iterated, we copy the ordered version into an array. Eliminating a state, we first check whether there are any self-transitions for the state to be removed and join them. To make this joining more readable, we picked the C# query syntax to select the labels of all self-edges. If there is a self-edge with a non-empty label, we directly star it for the regular expression. 1 foreach ( var s in tr an s it i on Gr a ph . States . OrderBy ( s = > s . Incoming . Count * s . Outgoing . Count ) . ToArray () ) 2 { 3 if ( s == initial || s == final ) continue ; 4 5 var selfEdge = string . Join ( " + " , from edge in s . Outgoing 6 where edge . Target == s 7 select edge . Label ) ; 8 9 if (! string . IsNullOrEmpty ( selfEdge ) ) selfEdge = string . Concat ( " ( " , selfEdge , " ) * " ) ; 10 11 foreach ( var incoming in s . Incoming . Where ( t = > t . Source != s ) ) 12 { 13 if ( incoming . Source == null ) continue ; 14 foreach ( var outgoing in s . Outgoing . Where ( t = > t . Target != s ) ) 15 { 16 if ( outgoing . Target == null ) continue ; 17 var transition = incoming . Source . Outgoing . F irstOr Defaul t ( t = > t . Target == outgoing . Target ) ; 18 if ( transition == null ) 19 { 20 trans i ti on G ra p h . Transitions . Add ( new Transition 21 { 22 Source = incoming . Source , 23 Target = outgoing . Target , 24 Label = incoming . Label + selfEdge + outgoing . Label 25 }) ; 26 } 27 else 28 { 29 transition . Label = string . Concat ( " ( " , transition . Label , " + " , incoming . Label , 30 selfEdge , outgoing . Label , " ) " ) ; 31 } 32 } 33 } 34 35 s . Delete () ; 36 } Listing 4: Removing states Before we actually remove the state, we iterate through all of its incoming and outgoing transitions. For each pair of incoming and outgoing transition, we create a new transition that avoids the state to be deleted. The label of that new transition is the same as following the incoming edge to the state marked for deletion, then making cycles in that state (only in case there actually are cycles) and then following the outgoing edge to the target state. This iteration through every pairs of incoming and outgoing transitions can be regarded as imperative code, but still has many declarative elements. For example, we do not need to specify how the collections are iterated or filtered and neither do we specify how a matching shortcut transition is found. Though these elements only provide a very thin abstraction layer, we think that they make the code quite understandable. Finally, we delete the state that we previously picked from the list of all states. Through the generated code of NMF, this operation boils down to a simple call to a Delete method. It will remove the state from the collection it is contained in, i.e. the collection of states in the transition graph. Further, it resets all references to that state3 . Because transitions are independent of states in the metamodel with respect to the containment hierarchy, the incoming and outgoing transitions will still exist after the state has been deleted. However, after the deletion operation, they are no longer connected to the deleted state, but the Source and Target reference are simply empty, i.e. point to null. We could go on and delete those transitions as they are no longer valid. However, in our experiments, we came to the conclusion that it is better to leave these transitions in there because the effort to delete them (removing an element from an ordered collection is an O(n)-operation!) is larger than the additional overhead they imply for the traversing incoming or outgoing transitions of other states. Finally, we return the possible paths from the initial state to the target state. This can be done similarly as above. The implementation, this time as a one-liner, is depicted in Listing 5. 1 return string . Join ( " + " , from edge in initial . Outgoing where edge . Target == final select edge . Label ) ; Listing 5: Calculating the overall regular expression 3 Evaluation Our solution is very concise. Besides generated code for the metamodel and one line of metamodel registration, the entire solution consists of 102 lines, of which 31 lines are either blank or only contain braces. Model # Elements Regex size Time to transform (ms) Correct JFLAP (ms) leader3_2 61 33 192 X 90 leader3_3 166 95 193 X 490 leader3_4 359 210 206 X 4,370 leader3_5 672 398 207 X 58,600 leader3_6 1,135 675 218 X 461,640 leader3_8 2,631 1,571 298 X – leader4_2 139 76 227 X 140 leader4_3 630 354 219 X 57,780 leader4_4 1,881 1,067 253 X 4,786,580 leader4_5 4,492 2,558 395 X – leader4_6 9,221 5,262 831 X – leader5_2 315 172 197 X 3,460 leader5_3 2,344 1292 286 X – leader5_4 9,513 5,267 890 X – leader5_5 28,544 15,833 5,277 X – leader6_2 735 398 207 X 143,120 leader6_3 8,248 4,487 739 X – leader6_4 45,865 24,979 17,210 X – leader6_5 173,194 94,408 395,616 X – leader6_6 515,077 280,865 4,356,603 X – leader6_8 2,886,813 – – – – Table 1: Execution times for the example input models 3 NMF can also raise an event to notify clients that an element was removed from the containment hierarchy but this event is not raised in this case as no clients are subscribed to it. The execution times for the test models are depicted in Table 1. The execution times have been recorded on an Intel i7-4710MQ clocked at 2.50Ghz on a system with 16GB RAM. For the largest model leader6_8, the solution ran out of memory. The recorded times include the initialization of NMF, initializing metamodels, loading model instances and computing the regular expression. It does not include serializing the generated regular expression to a file or testing the expression for the example inputs. The times show a very good performance and scalability. For most of the models, the regular expression can be computed in less than a second. In particular, for the example model leader4_4, the largest that the reference solution in JFLAP is able to process, our solution is faster than JFLAP by more than three orders of magnitude. Only for the largest models, the transformation takes a lot of time. 4 Conclusion In this paper, we discussed how the .NET Modeling Framework can be used to solve state elimination reified as model transformation task. Because there is no correspondence between source and target model required, the transformation languages in NMF are not well suited for this problem. Hence, our solution is essentially using general-purpose code, although the implementation of bidirectional references and automatically resetting references for deleted model elements makes the implementation more concise. The performance results for the smaller models are very good. In particular, the solution is able to process all except for the very largest models. References [GVPK17] Sinem Getir, Duc Anh Vu, Francois Peverali, and Timo Kehrer. State Elimination as Model Transfor- mation Problem. In Antonio Garcia-Dominguez, Georg Hinkel, and Filip Krikava, editors, Proceedings of the 10th Transformation Tool Contest, a part of the Software Technologies: Applications and Foun- dations (STAF 2017) federation of conferences, CEUR Workshop Proceedings. CEUR-WS.org, July 2017. [HB17] Georg Hinkel and Erik Burger. Change Propagation and Bidirectionality in Internal Transformation DSLs. Software & Systems Modeling, 2017. [HH15] Georg Hinkel and Lucia Happe. An NMF Solution to the TTC Train Benchmark Case. In Louis Rose, Tassilo Horn, and Filip Krikava, editors, Proceedings of the 8th Transformation Tool Contest, a part of the Software Technologies: Applications and Foundations (STAF 2015) federation of conferences, volume 1524 of CEUR Workshop Proceedings, pages 142–146. CEUR-WS.org, July 2015. [Hin13] Georg Hinkel. An approach to maintainable model transformations using an internal DSL. Master’s thesis, Karlsruhe Institute of Technology, October 2013. [Hin15] Georg Hinkel. Change Propagation in an Internal Model Transformation Language. In Dimitris Kolovos and Manuel Wimmer, editors, Theory and Practice of Model Transformations: 8th Inter- national Conference, ICMT 2015, Held as Part of STAF 2015, L’Aquila, Italy, July 20-21, 2015. Proceedings, pages 3–17, Cham, 2015. Springer International Publishing. [Hin16] Georg Hinkel. NMF: A Modeling Framework for the .NET Platform. Technical report, Karlsruhe Institute of Technology, Karlsruhe, 2016.