Port
The input metamodel is shown on Figure 1. The TruthTable class is as the root of the model, and contains a collection of Ports and Rows. Ports come in two types: InputPorts and OutputPorts. Rows contain sequences of Cells, which assign values to the InputPorts and OutputPorts of the table.
Automated EMF opposite references are used liberally in the metamodel to simplify the specification of the transformation. owner is used to access the container from several child objects (e.g. the TruthTable of a Row), and it is possible to see which cells referenced a specific Port.
A sample model is shown on Table 1. The truth table has four InputPorts named A to D, and one OutputPort named S. The first Row contains only 3 Cells, specifying that if A and B are 0, then S should be 0. 2.2
The original output metamodel from the ATL Zoo version is shown on Figure 2. The BDD class is the root of the model, and contains the root of the Tree and a collection of Ports. Similarly to the Truth Tables metamodel, there are InputPorts and OutputPorts.
Figure 3 shows the changes introduced into a revised version of the original metamodel, which allow the BDD to be a rooted acyclic graph and not just a tree. This would allow the BDD to reuse common subtrees, which would produce more compact circuits in some situations. The case provides both versions as separate metamodels: solution implementers were free to choose either version.
Tree is the common superclass for any node in the tree. Inner nodes check the value of an InputPort: if it is a false value, evaluation will proceed through the treeForZero Tree; otherwise, evaluation will go through [1..1] treeForOne
[1..1] treeForZero
BDD the treeForOne Tree. Leaf nodes are Leaf objects, which provide an Assignment of a boolean value to each of the available OutputPorts.
The equivalent BDD for the truth table on Table 1 is shown on Figure 4. Subtrees are represented by the circle referencing an InputPort and their subtrees for when the port takes a 0 or 1 value. Assignments are represented by the highlighted nodes that provide values to the OutputPorts. 2.3
The transformation essentially needs to construct a (preferably minimal) binary decision diagram that produces the same values for the output ports, given the same values in the input ports. Given the high interest about this problem in circuit design, many algorithms have been proposed in the literature.
Solution authors are welcome to implement a more optimal algorithm in their transformation tool. This section will only outline a simple approach that can be readily implemented without too much complication.
There are some basic mappings which are immediately obvious:
Each TruthTable object should correspond to a BDD object, with the same name and equivalent Ports. Each InputPort and OutputPort should be mapped to an object of the BDD type with the same name.
Each Row should become a Leaf node: the Cells for the OutputPorts will become Assignments.
The complexity is in deriving the inner nodes: the Subtree objects. One simple approach is to find a TT InputPort which is (ideally) defined in all the Rows, and turn it into an inner node (a Subtree) which points to the equivalent BDD InputPort and has two Trees:
The zero subtree, produced from the Row(s) where the port was 0. This will be a Subtree if there are at least two rows in that situation: the transformation should proceed recursively in this case with those rows, excluding the input ports that have already been considered. If there is only one such row, this would simply point to the Leaf created above.
The one subtree, produced in a parallel way to the zero subtree. D 1
C 0 B
1 S = 0 0 S = 0
This simple approach does not necessarily ensure a minimal subtree, as in some points there may be multiple ports to choose from. It may require improvements for cases where there are no input ports which are defined in all available rows. 3
The main task was implementing the transformation, ensuring that the BDDs were equivalent to the original truth table. To simplify the work involved, the case included an Eclipse Modelling Framework implementation, and a set of sample XMI input models conforming to the metamodels.
The models folder includes two additional tools:
A generator that produced truth tables of an arbitrary number of input and output ports, given a seed. A validator that checked if a BDD model was equivalent to a source truth table model, by evaluating all possible input combinations through the BDD and comparing the values of the OutputPorts.
Solutions could focus on any specific quality attribute of the transformation beyond optimality and performance. For instance, it may be useful to be able to prove that the transformation does indeed produce a BDD which is equivalent to the TT (even if suboptimal). One of the solutions did focus on verifiability. 4
If focusing on performance, the solution authors had to integrate their solution with the provided benchmark
framework. It is based on that of the TTC 2017 Smart Grid case [
The benchmark consisted of three phases: Initialisation (setting up the basic infrastructure), Load (for loading the models), and Run (for executing the transformation and saving the results).
Solutions had to be forks of the main Github project2, for their later integration into the main Github repository. The solutions could be implemented in any language: they only had to print to the standard output lines in a specific format, mentioning the memory usage and wall clock time spent in transforming each model.
The solutions had to include a solution.ini file with instructions on how to automatically build, test, and run them. Solutions were run multiple times, as indicated in the main configuration of the benchmark. To ensure reproducibility, the solutions were integrated into a Docker image, which is automatically built by Docker Hub on each push3. 5
Given the call for a broader set of research interests in this transformation, the evaluation operated on two dimensions: 2https://github.com/TransformationToolContest/ttc2019-tt2bdd 3https://hub.docker.com/r/bluezio/ttc2019-tt2bdd-git
Was it a high-quality model transformation? The transformation should be complete, correct, easy to understand, efficient, and produce optimal results.
The validator was used to check the produced BDDs against the source truth tables, and the authors had to provide a convincing argument about the correctness of the solution.
The understandability of the solution was evaluated through an audience survey, and the Docker image was used by the contest organizers to provide independent measurements of memory and time usage in identical conditions. Particularly, Google Cloud Compute c2-standard-4 images were used.
Tree sizes for the BDDs were considered for the optimality of the transformations: the smaller, the better. Did it highlight a promising research direction? Although the transformation may not be entirely complete or may be harder to understand, it may serve as an example of an active research area within model transformations that the community may wish to showcase.
This may include aspects such as incrementality, bidirectionality, traceability, verifiability, or the ability to visualize interactively the transformation, among other areas of interest in the field.
As mentioned before, there was one solution which focused on the verifiability of the solution. This solution received an award for the promising results towards integrating verifiability in a model transformation language.