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 specification of state elimination more declarative and faster than the reference implementation in JFLAP for smaller models.
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
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 ModelRepository () ; 2 var transitionGraph = repository . Resolve ( path ). RootElements [0] as TransitionGraph ;
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 = transitionGraph . 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 transitionGraph . Transitions . Add ( new Transition 12 { 13 Source = s ,
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.
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 );
3
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. # Elements
3NMF 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.
Model leader3_2 leader3_3 leader3_4 leader3_5 leader3_6 leader3_8 leader4_2 leader4_3 leader4_4 leader4_5 leader4_6 leader5_2 leader5_3 leader5_4 leader5_5 leader6_2 leader6_3 leader6_4 leader6_5 leader6_6 leader6_8
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
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.