=Paper=
{{Paper
|id=Vol-2550/paper4
|storemode=property
|title=Transforming Truth Tables to Binary Decision Diagrams Using Relational Reference Attribute Grammars
|pdfUrl=https://ceur-ws.org/Vol-2550/paper4.pdf
|volume=Vol-2550
|authors=Johannes Mey,René Schöne,Christopher Werner,Uwe Aßmann
|dblpUrl=https://dblp.org/rec/conf/staf/MeySWA19
}}
==Transforming Truth Tables to Binary Decision Diagrams Using Relational Reference Attribute Grammars==
https://ceur-ws.org/Vol-2550/paper4.pdf
1 LocatedElement ::= ;
2 TruthTable : LocatedElement ::= Port:Port* Row:Row* ; // The start symbol of this grammar
3
4 abstract Port : LocatedElement ::= ; // Port is an abstract node that cannot be instantiated
5 InputPort : Port; // InputPort and OutputPort are a special ports, i.e., inheriting
6 OutputPort : Port; // name and location from it
7 Row : LocatedElement ::= Cell:Cell*;
8 Cell : LocatedElement ::= ; // The cell has a intrinsic attribute, in this case
9 // the boolean value of the cell
10 rel Port.Cell* <-> Cell.Port; // A bidirectional relation stating, that a cell refers to a port
Listing 1: Grammar for a truth table in JastAdd syntax
1 BDT ::= Port:BDT_Port* Tree:BDT_Tree; 1 BDD ::= Port:BDD_Port* Tree:BDD_Tree*;
2 abstract BDT_Tree; 2 abstract BDD_Tree;
3 BDT_Leaf:BDT_Tree ::= Assignment:BDT_Assignment*; 3 BDD_Leaf:BDD_Tree ::= Assignment:BDD_Assignment*;
4 BDT_Subtree:BDT_Tree ::= TreeForZero:BDT_Tree TreeForOne:BDT_Tree; 4 BDD_Subtree:BDD_Tree;
5 5 abstract BDD_Port ::= ;
6 abstract BDT_Port ::= ; 6 BDD_InputPort : BDD_Port;
7 BDT_InputPort : BDT_Port; 7 BDD_OutputPort : BDD_Port;
8 BDT_OutputPort : BDT_Port; 8 BDD_Assignment ::= ;
9 BDT_Assignment ::= ; 9 rel BDD.Root -> BDD_Tree;
10 10 rel BDD_Subtree.TreeForZero <-> BDD_Tree.OwnerSubtreeForZero*;
11 rel BDT_InputPort.Subtree* <-> BDT_Subtree.Port; 11 rel BDD_Subtree.TreeForOne <-> BDD_Tree.OwnerSubtreeForOne*;
12 rel BDT_OutputPort.Assignment* <-> BDT_Assignment.Port; 12 rel BDD_InputPort.Subtree* <-> BDD_Subtree.Port;
13 13 rel BDD_OutputPort.Assignment* <-> BDD_Assignment.Port;
14 // relations to TruthTable model 14 // relations to TruthTable model
15 rel BDT.TruthTable -> TruthTable; 15 rel BDD.TruthTable -> TruthTable;
16 rel BDT_InputPort.TruthTableInputPort -> InputPort; 16 rel BDD_InputPort.TruthTableInputPort -> InputPort;
17 rel BDT_OutputPort.TruthTableOutputPort -> OutputPort; 17 rel BDD_OutputPort.TruthTableOutputPort -> OutputPort;
18 rel BDT_Leaf.Row* -> Row; 18 rel BDD_Leaf.Row* -> Row;
Listing 2: JastAdd grammar for Binary Decision Tree Listing 3: Grammar for a Binary Decision Diagram
1 PortOrder; 1 // TruthTable has two NTA defined:
2 rel TruthTable.PortOrder -> PortOrder ; 2 syn PortOrder TruthTable.getNaturalPortOrder() = //...
3 rel PortOrder.Port* -> InputPort; 3 syn PortOrder TruthTable.getHeuristicPortOrder() = //...
Listing 4: Grammar for PortOrder Listing 5: NTA definition for PortOrder
3 Computing a Binary Decision Diagrams with Relational RAGs
In this section, we show how truth tables, BDTs, and BDDs can be modelled using relational RAGs and, in
particular, how relations support the transformations and traceability between the models. Initially, the case
description demanded a binary decision tree (BDT) and not a binary decision diagram (BDD). Therefore, we
present different configurable algorithms to transform a truth table into either a BDT or a BDD. While the
outputs of all provided transformations are semantically equivalent for one given input, they have different
characteristics regarding both the runtime of the transformation and the properties of the resulting diagrams.
3.1 Describing Conceptual Models
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 modu-
larity 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.
2 For 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()
BDT
TruthTable orderedBDD() A B
noncontainment relation
natural() heuristic() reducedOBDD()
BDD
AST of type A computed AST nonterminal attribute
PortOrder PortOrder
BDD C att() relational
nonterminal attribute
AST node with attribute att()
Figure 1: Elements of the transformation and their relations
3.2 Computing Models
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 Computing an Ordered Binary Decision Diagram
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 → {0, 1} 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.
3 These 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.
4 In literature such as [MT12, RK08], ports are called variables.
1 syn BDD TruthTable.reducedOBDD() {
2 BDD bdd = this.asBDD(); // Construct an empty BDD with trace link to truth table
3 bdd.setName(getName()); // and copy the name from the truth table
4 for (Port port: this.getPortList()) // For each port
5 bdd.addPort(port.asBDDPort()); // the according BDD variant of the port is created and linked back
6 for (BDD_Leaf leaf: constructLeaves()) bdd.addTree(leaf); // Add leaves
7 PortOrder portOrder = getPortOrder(); // Obtain the port order by accessing a non-containment relation
8 // to the selected nonterminal attribute
9 BDD_Subtree root = new BDD_Subtree(); // Create root node, set its port to the first in the port order,
10 root.setPort(bdd.bddInputPort(portOrder.getPortList().get(0))); // add it to the BDD, and specify it as the root
11 bdd.addTree(root);
12 bdd.setRoot(root);
13 for (Row row : getRowList()) insertRow(bdd, root, row, 0); // Fill the BDD by adding all defined paths using a helper function
14 bdd.reduce(); // Perform the reduction by calling a helper function
15 return bdd;
16 }
Listing 6: Relational non-terminal attribute to create an ordered BDD
1 syn int BDT_Tree.decisionNodeCount();
2 eq BDT_Subtree.decisionNodeCount() = 1 + getTreeForZero().decisionNodeCount() + getTreeForOne().decisionNodeCount();
3 eq BDT_Leaf.decisionNodeCount() = 0;
Listing 7: Computation of the number of decision nodes in the BDT
4 A Dynamic Transformation Toolchain
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 attribute-
computed 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.
5 The implementation can be found at https://git-st.inf.tu-dresden.de/ttc/bdd
BDT()
Ecore TT RAG TT RAG TT BDT Ecore BDT
writeBDT
order
edBDT
TruthTable TruthTable ()
natural() OBDT
parse compute compute
PortOrder Metrics() Metrics
orderedBDD()
OBDD
reducedOBDD() Ecore BDD
writeBDD
rOBDD
Figure 2: Transformation process and temporary artefacts
ATL Graph Fulib NMF JastAdd ordered BDD JastAdd ordered BDT JastAdd reduced OBDD RSync BDD YAMTL
1.0
Decision nodes (normalized)
105 0.8
104
Time (ms)
0.6
103 0.4
102 0.2
105 0.0
Output: 2
Output: 2
Output: 4
Output: 2
Output: 2
Output: 4
Output: 5
Output: 2
Output: 2
Output: 4
Output: 2
Output: 2
Output: 4
Output: 5
Input: 04
Input: 08
Input: 08
Time (ms)Input: 10
Input: 12
Input: 14
Input: 15
Input: 04
Input: 08
Input: 08
Input: 10
Input: 12
Input: 14
Input: 15
104
Model instance Model instance
(a) Total time (b) Number of decision nodes (normalized)
103
Figure 3: Evaluation results
102
5 Evaluation
The evaluation consists of two parts. First, the transformation and its properties are discussed with a focus on
Output: 2
Output: 2
Output: 4
Output: 2
Output: 2
Output: 4
Output: 5
Input: 04
Input: 08
Input: 08
Input: 10
Input: 12
Input: 14
Input: 15
conciseness, modularity, and reuse, then its performance and the quality of the target models are described.
Model instance
5.1 Properties of the Transformation
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 Performance and Quality
To evaluate the runtime performance, the measurements of the TTC organizers were considered. All measure-
ments 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
6 https://github.com/TransformationToolContest/ttc2019-tt2bdd/blob/master/Dockerfile
7 Since 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.
Acknowledgements
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’.
References
[EH07] Torbjörn Ekman and Görel Hedin. The JastAdd system—modular extensible compiler construction.
Science of Computer Programming, 69(1):14–26, 2007.
[GDH19] 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) fed-
eration of conferences, CEUR Workshop Proceedings. CEUR-WS.org, July 2019.
[Hed00] Görel Hedin. Reference attributed grammars. Informatica (Slovenia), 24(3), 2000.
[Knu68] Donald E. Knuth. Semantics of context-free languages. Mathematical systems theory, 2(2), 1968.
[MSH 18] Johannes Mey, René Schöne, Görel Hedin, Emma Söderberg, Thomas Kühn, Niklas Fors, Jesper
+
Öqvist, and Uwe Aßmann. Continuous Model Validation Using Reference Attribute Grammars. In
Proceedings of the 11th ACM SIGPLAN International Conference on Software Language Engineering,
SLE 2018, pages 70–82. ACM, 2018.
[MT12] Christoph Meinel and Thorsten Theobald. Algorithms and Data Structures in VLSI Design: OBDD-
foundations and applications. Springer Science & Business Media, 2012.
[RK08] Michael Rice and Sanjay Kulhari. A survey of static variable ordering heuristics for efficient bdd/mdd
construction. Technical report, 2008.
[SBMP08] Dave Steinberg, Frank Budinsky, Ed Merks, and Marcelo Paternostro. EMF: Eclipse Modeling Frame-
work. Pearson Education, 2008.
[VSK89] H. H. Vogt, S. D. Swierstra, and M. F. Kuiper. Higher order attribute grammars. In Proceedings of
the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, PLDI
’89, pages 131–145, New York, NY, USA, 1989. ACM.