1 LocatedElement ::= <Location:String>; 2 TruthTable : LocatedElement ::= <Name:String> Port:Port* Row:Row* ; // The start symbol of this grammar 3 4 abstract Port : LocatedElement ::= <Name:String>; 5 InputPort : Port; 6 OutputPort : Port; 7 Row : LocatedElement ::= Cell:Cell*; 8 Cell : LocatedElement ::= <Value:Boolean>; 9 10 rel Port.Cell* <-> Cell.Port; Many conceptual models can be described by relational RAGs. This is possible, because many model specification languages, e.g., Ecore, require models to have a containment hierarchy, and thus a spanning tree. Listing 1 shows the grammar of the truth table that corresponds to the provided model. Since the grammar specification rules of JastAdd use concepts like inheritance and abstract types, all given Ecore models can easily be transformed into relational RAGs. The resulting BDT and BDD grammars are shown in Listings 2 and 3. While some concepts like Port potentially could be reused between the models, we refrained from doing so, because those concepts do not have exactly the same definition in all models. 2
Important aspects when dealing with several trees at the same time defined by relational RAGs are the modularity of their specification and the reachability between those trees. RAGs as specified by JastAdd are inherently modular: Both grammar and attributes can be split into aspect files. Therefore, both truth table, decision tree and -diagram models are described by one relational grammar, but specified in different modules. Since the truth table grammar shown in Listing 1 has no relations to the other models, it can be used independently. On the other hand, the diagram models have a relation to the truth table, as shown in Listing 2. Note that this is not required, but a design decision, since those relations enable traceability between the models.
2For example, a Port within a truth table is a LocatedElement, while one in a BDD is not. In other cases, the types may be the same, but the relations between them are not.
BDT()
TruthTable orderedBDD() natural() heuristic()
reducedOBDD() PortOrder PortOrder BDD BDD
noncontainment relation AST of type A computed AST
nonterminal attribute
C att() AST node with attribute att()
relational nonterminal attribute
A model transformation can be seen as the computation of a target model using information of a source model. RAGs provide a mechanism for that: attributes that compute a tree of the grammar they are defined in, called higher-order or nonterminal attributes (NTAs). There are two types of NTAs, those that describe a subtree of an AST and those that describe a new tree. In both cases, non-containment relations added by relational RAGs provide the means to link these (sub-)trees to the original tree. Figure 1 shows the structure of the trees used for the case. The only given tree is the TruthTable tree, containing two subtrees of the type PortOrder shown in Listing 4, defined by NTAs from Listing 5. The results of the transformation are stored in separate trees of type BDT and BDD, computed by the relational NTAs BDT(), orderedBDD() and reducedOBDD(). Note that different NTAs may return different instances of the same type. In addition to the relations computed by NTAs, there may be other intrinsic relations, such as the relation that selects one of the two provided PortOrder s. These relations can also link nodes in computed subtrees to nodes in the originating tree. 3
In the following, we focus on one transformation into reduced ordered BDDs using the NTA reducedOBDD(). 3.3
Constructing an optimal BDD is a computationally hard, but, since there are many real world applications that use large BDDs, appropriate simplifications and efficient heuristics exist. One commonly used simplification of BDDs are ordered BDDs (OBDD), in which the order of input variables 4 in all paths is identical, allowing a layering of the graph. Given an OBDD, two simple reduction rules are applied to reduce the number of nodes; the result of such a reduction process is a reduced OBDD. In an OBDD, the minimal diagram for a given order can be computed efficiently, however, the computation of the optimal order is still NP-hard [MT12, p. 139ff.].
We follow the definition of an OBDD given in [MT12] extending the problem to several output variables as mentioned in Section 1 as follows: • An OBDD with m input and n output variables has at most 2n leaves, each with a different assignment function f : Vo ! f0; 1g with Vo as the set of output variables. • There is an order < for input variables, such that on an edge from one node referring to input variable x to a node referring to variable y it holds that x < y.
Conceptually, we split the construction of a reduced OBDD in three stages: the computation of a port order, the construction of a perfect tree, and its reduction. Listing 6 shows the synthesized attribute that performs this process. First, a BDD node is constructed and the relations to the truth table and its variables are established (lines 2–5). Then, the leaves are constructed by a helper function and added to the diagram (line 6). Afterwards, a port order is retrieved by accessing the noncontainment relation to a PortOrder pointing to one of the NTAs that computes a port order. These are defined in a separate grammar aspect shown in Listing 4. Besides the default order defined in line 2 of Listing 5, we provide a heuristic ordering defined in line 3. Since most heuristics in the literature rely on a logical formula as an input, we have chosen to use a simple metric based on the correlation of an input variable to the output vector in the given truth table. Using this port order, the tree is constructed iteratively by adding the path for each input row (Listing 6, lines 9–13). Finally, the reduction is performed in line 14. The employed algorithm and its properties can be studied in [MT12, p. 96ff.]. For a given truth table, there is exactly one minimal OBDD, computed by the algorithm in O(d log d) for d decision nodes.
Besides computing and reducing an OBDD, we have also implemented other approaches as shown in Section 5. How to apply those approaches to the given case will be described in the next section.
3These relations must not be bidirectional, since the direction from the source model to the computed NTA model would violate the rule that attribute computations may not alter the tree — other than adding the result of the computation.
4In literature such as [MT12, RK08], ports are called variables. To perform the transformation, we follow the process outlined in Figure 2. We will show, how our approach supports variability that enables reuse and the combination of different transformation approaches and how relational RAGs support traceability between models and help in analysing these models.
As JastAdd is not based on Ecore, the meta model of EMF [SBMP08], we can not directly use the given input models. Instead, we translated the given metamodel into the grammar shown in Listing 1 and built a hand-written XMI parser constructing an AST according to this grammar. However, relational RAGs provide some mechanisms to reduce the implementation overhead and simplify this process.
While parsing an XMI file is rather straightforward, the resolution of the XMI references is not. In attribute grammars, name analysis is well-supported and a frequently used application. Relational RAGs provide an additional method to defer the name resolution after the parsing while still allowing the result of the attributecomputed name resolution to be stored as a non-containment relation. Once the truth table is parsed, the transformation is performed. The first step is to create an additional subtree with a PortOrder, which can later be used to create ordered BDTs and BDDs. This is also the first configurable step of the process, since the algorithm for the computation of the PortOrder can be switched. Afterwards, BDTs or BDTs are created by different attributes. In the case of the OBDD, the reduction can be seen as an additional step of the computation. Since all variants are independent trees, it is possible to create several variants at the same time. Each created variant contains trace links into the truth table model that are created during construction (cf. Listing 2, lines 15 to 18). Then, the results are validated and different metrics described in Section 5 are computed. One example for a metric is the number of decision nodes in Listing 7. Finally, the resulting BDT or BDD is serialized to XMI. Again, this step requires attributes to compute the references within the file, i.e., XMI path expressions. This whole process is embedded into the provided benchmarking framework 5 and evaluated in the next section. 5The implementation can be found at https://git-st.inf.tu-dresden.de/ttc/bdd Ecore TT
RAG TT
TruthTable parse compute PortOrder
RAG TT TruthTable natural()
BDT() orderedBDT() orderedBDD()
BDT
reducedOBDD()
rOBDD
YAMTL The evaluation consists of two parts. 40F:t2irst,80t:t2he tr80a:t4nsfor01m:t2ation21 :t2and 41it:t4s pro51p:t5erties are discussed with a focus on conciseness, modularity, and reuse, thI:tunpetuupOn itsI:tunpptuupOerforI:tnupmtuupOMaondeclienI:tnupstatuupOanncde tI:tunphtuupOe quaI:tnupltuupOity oI:tnupf tuupOthe target models are described. Using relational RAGs, the presented models can be specified concisely. As shown in Listings 1 to 4, the grammars for truth table, BDT and BDD comprise few lines of code. The specification of the transformation using the attributes of JastAdd proves to be a good combination of imperative code (which is beneficial for such complex transformation algorithms as, e.g., for the OBDD reduction) and efficient attribute-supported tree navigation. Additionally, attributes can help by checking both the correctness and different metrics of the obtained model.
An important aspect of the presented solution is modularity and the opportunities for reuse that stem from it. Even though, technically, all models are combined in one large grammar, this grammar can be used in independent modules consisting of grammar fragments and accompanying attributes. The example of the PortOrder extension shows how additional analysis modules can simply be added to the grammar. Using relations, entire new models can be integrated and used by existing models. On the attribute level, the definition of attributes in aspects also helps to combine and reuse separate parts of the transformation system. Furthermore, relational RAGs allow traceability. Relations between models can be established that, e.g., show which rows have taken part in the creation of a Leaf in a BDD. 5.2
To evaluate the runtime performance, the measurements of the TTC organizers were considered. All measurements were performed on a Google Cloud Compute Engine c1-standard-4 machine with 16GiB of RAM and an 30GB SSD, using a Docker image.6 Each configuration was run ten times. In addition to time measurements, we added a number of result quality metrics computed by attributes, namely the number of nodes of the two different types and the minimum, maximum, and average path length.
Figure 3 shows our evaluation results for the seven provided input models depicting total runtime and the number of decision nodes, i.e., instances of type Subtree, normalized to the greatest number among all variants. 7 For the measurement, we included the following variants of our approach: An ordered BDT variant generating the tree iteratively (ordered BDT ), an ordered BDD generated iteratively (ordered BDD ) and a reduced variant of the latter, using the algorithm described in Section 3.3 (reduced OBDD ). For the last variant, we used the order determined by the heuristic. These solutions are compared to the other contributions to the TTC that integrate into the benchmark infrastructure. As shown in Figure 3a, all variants display a good performance compared to the other solutions; the only solution that is considerably faster for larger problems is Fulib, which benefits from being a pure Java solution optimized for the input data of the benchmark. However, relational RAGs do not require any initialization other than loading the required Java classes, resulting in only a small overhead compared to Fulib that we assume is due to the larger memory footprint of JastAdd. Comparing the execution times of our approaches, the non-reduced implementations show a very similar performance, while the 6https://github.com/TransformationToolContest/ttc2019-tt2bdd/blob/master/Dockerfile 7Since a variant is included that creates a perfect tree, this number is 2m 1 where m is the number of input variables. reduced OBDD takes up more time for the largest model, due to the final reduction step.While the benchmark only measured resident memory before and after the transformation, the figures for this stayed below 1GB for all variants and scenarios and are thus lower than for all other solutions except Fulib. Looking at the number of decisions in the final result, there are three classes of approaches. All non-reduced OBDD variants generate the largest number of decision nodes, as they always produce the full tree. The algorithm used in the case description reduces the nodes in the tree by 2% to 14% compared to the full tree. When applying the reduction algorithm to an ordered BDD, 14% to 69% of the decision nodes in the full tree are removed. 6
Conclusion and Future Work We have shown how to apply Relational Reference Attribute Grammars to the problem of transforming truth tables into (ordered) binary decision diagrams. This included defining a suitable grammar for both truth tables and BDDs, parsing the given input models, computing a BDD in different ways while reusing intermediate results, and finally printing the result to the required XMI format. We used the JastAdd system to implement our solution and were able to create several configurable transformations with good performance compared to most other solutions. As the focus of this contribution was not to create new transformation algorithms, we show how the implementation of those algorithms, metrics, and tracing relations were improved by relational RAGs.
The presented approach demonstrates a manual bidirectional transformation from Ecore-based models to JastAdd ASTs and back. While the grammar as well as the parser and printer were hand-written, there is no obvious reason why this could not be automated. Having an automated transformation from Ecore meta-models to grammars and their instances to ASTs would instantly make a huge set of existing models available for efficient RAG-based analysis and is therefore an important direction of research.
This work has been funded by the German Research Foundation within the Research Training Group "Role-based Software Infrastructures for continuous-context-sensitive Systems" (GRK 1907), the research project “Rule-Based Invasive Software Composition with Strategic Port-Graph Rewriting” (RISCOS) and by the German Federal Ministry of Education and Research within the project “OpenLicht’.
Torbjörn Ekman and Görel Hedin. The JastAdd system—modular extensible compiler construction. Science of Computer Programming, 69(1):14–26, 2007.
Antonio Garcia-Dominguez and Georg Hinkel. Truth Tables to Binary Decision Diagrams. In Antonio Garcia-Dominguez, Georg Hinkel, and Filip Krikava, editors, Proceedings of the 12th Transformation Tool Contest, a part of the Software Technologies: Applications and Foundations (STAF 2019) federation of conferences, CEUR Workshop Proceedings. CEUR-WS.org, July 2019.
Görel Hedin. Reference attributed grammars. Informatica (Slovenia), 24(3), 2000.
Donald E. Knuth. Semantics of context-free languages. Mathematical systems theory, 2(2), 1968.
Christoph Meinel and Thorsten Theobald. Algorithms and Data Structures in VLSI Design: OBDDfoundations and applications. Springer Science & Business Media, 2012.
Michael Rice and Sanjay Kulhari. A survey of static variable ordering heuristics for efficient bdd/mdd construction. Technical report, 2008.
References