link. There is also a lter(lambda) operation that applies the passed lambda function to all rows and keeps only the rows where the lambda function computes true. Finally, there is an addColumn(colName,lambda) operation that runs the passed lambda function on each row and adds the result to the row. This may e.g. be used to create new neighbor objects or do some other model transformation.
Altogether, Fulib tables allow to build complex model queries and model transformations. These Fulib model transformations are still missing some common features provided by modern model transformation languages, but to our surprise, this small interface already su ces for most of the example cases that we have studied. Actually, for the Truth Table to Binary Decision Diagram case, we had to add some more features which is discussed below. 3
First, I decided not to load the ttmodel les as EMF object models but to read the data directly into a Fulib table. Thus, I just read the ttmodel le line by line and use a regular expression to match lines starting with "<ports" and to retrieve the contained port name. Then I extended the Fulib table class with an addColumn(colName) operation that I use to add a column for each retrieved port (no rows yet).
Internally, a Fulib Table consists of an ArrayList<ArrayList<Object>> and an additional LinkedHashMap<String,Integer> used to translate column names into ArrayList index values. Thus, while reading the ttmodel le line by line, for each "<rows" line, I create a new ArrayList and for each "<cells" line I add either 0 or 1 to this ArrayList. On a "</rows" line, I add the ArrayList to the current Fulib table. Yes, this very much relies of a very regular structure of the ttmodel les, but it works great for the generated example models.
Next, I programmed a splitTable(tt,colName) model transformation, cf. Listing 2. Basically, splitTable derives a falseTable and a trueTable from a given table truthTable. The new tables get all columns from the old table, without the varName column, cf. Lines 4 to 9. Then, we iterate through all rows of the input table (Line 11), clone it (Line 12), and remove the value that corresponds to the current varName (Line 13). The resulting reduced row is then added either to the falseTable or to the trueTable depending on the row value corresponding to the current varName (Lines 14 to 20).
Listing 3 shows my overall Truth Table to Binary Decision Diagram transformation doOneBDDLevel. In Line 17 doOneBDDLevel just chooses an (the rst) input port and then splits the current table at this port (name) (Line 18). Lines 19 to 21 create the corresponding SubTree node. Then, Line 22 and 23 call doOneBDDLevel for 1 private A r r a y L i s t <F u l i b T a b l e > s p l i t T a b l e ( F u l i b T a b l e t r u t h T a b l e , S t r i n g varName ) f 2 F u l i b T a b l e f a l s e T a b l e = new F u l i b T a b l e ( ) ; 3 F u l i b T a b l e t r u e T a b l e = new F u l i b T a b l e ( ) ; 4 f o r ( S t r i n g key : t r u t h T a b l e . getColumnMap ( ) . k e y S e t ( ) ) f 5 i f ( ! key . e q u a l s ( varName ) ) f 6 f a l s e T a b l e . addColumn ( key ) ; 7 t r u e T a b l e . addColumn ( key ) ; 8 g 9 g 10 i n t v a r I n d e x = t r u t h T a b l e . getColumnMap ( ) . g e t ( varName ) ; 11 f o r ( A r r a y L i s t row : t r u t h T a b l e . g e t T a b l e ( ) ) f 12 A r r a y L i s t <I n t e g e r > c l o n e = ( A r r a y L i s t <I n t e g e r >) row . c l o n e ( ) ; 13 c l o n e . remove ( v a r I n d e x ) ; 14 i n t v a l u e = ( I n t e g e r ) row . g e t ( v a r I n d e x ) ; 15 i f ( v a l u e == 1 ) f 16 t r u e T a b l e . addRow ( c l o n e ) ; 17 g 18 e l s e f 19 f a l s e T a b l e . addRow ( c l o n e ) ; 20 g 21 g 22 A r r a y L i s t <F u l i b T a b l e > r e s u l t = new A r r a y L i s t < >(); 23 r e s u l t . add ( f a l s e T a b l e ) ; 24 r e s u l t . add ( t r u e T a b l e ) ; 25 return r e s u l t ; 26 g
the sub tables falseTable and trueTable recursively. Lines 24 and 25 add the resulting sub trees to the current sub tree. If the current truthTable has only a single row left (cf. Line 2), I generate a Leaf node with appropriate Assignment s (Lines 3 to 14).
Generally, the size of the generated BDD tree may be reduced by combining leaf nodes with similar output. Thus, we might improve our tree generation by checking whether all rows of a given table have the same output values. With a Fulib table, we may drop all input columns. The dropColumns operation would result in a table with only the output columns remaining and it would automatically eliminate all row duplicates. Thus we might then check for a single row or single vector of output values. However, such a dropColumns operation uses runtime that is linear to the number of rows and we are not sure that it pays o . Similarly, the size of the BDD tree may depend on the order of the input ports that you use for splitting. After all, within the benchmark the input examples are generated using random output values. Thus, there is little hope that a smart ordering of variables achieves an early pruning of the BDD tree. Thus, I did not investigate in a smart port selection algorithm but I just split the tables on the rst column.
The reader may argue, that my splitTable operation is just plain Java and thus no real model transformation. On the other hand, our input is a Truth Table and thus I argue that a (Fulib) table is indeed an appropriate model for our input. Similarly, operations like expandLink, addColumn, and addRow are appropriate model transformations for a table model and these are the operations splitTable relies on. 4
Figure 1 shows some runtime results for the Fulib solution in comparison with the default EMFSolutionATL. Figure 1 shows just the time used for the actual transformation in seconds. For 4 input ports and 2 output ports EMFSolutionATL needs about 0,45 seconds on my computer. For 8 input ports and 2 output ports EMFSolutionATL needed about 40 seconds on the same test. I have omitted this and larger measurements as you would no longer see the Fulib results. Fulib solves the case with 15 inputs and 5 outputs within 0.18 seconds.
I have validated the results of the Fulib solution using the validator provided with the case study. It passes all tests.
I am not sure, how the di erence in runtime may be explained. First of all, an ArrayList<ArrayList<Object>> is a pretty compact and fast model. If we count each ArrayList as one object, the case with 15 + 5 ports has 215 i.e. about 32 000 rows. Within the original EMF Truth Table Model, there are extra objects for each cell. These are additional 20 cell objects per row resulting in 640 000 cell objects. Thus, this may account for some factor of 20 in memory and accordingly in runtime usage. Still, it seems that the EMFSolutionATL is not in the same runtime complexity class as the Fulib solution. Maybe EMFSolutionATL does some more optimization or it does some more searching through the entire table during query matching. To be honest, the current Fulib solution works only for regular input (no don't cares, always the same order of cells). While I claim that this could be xed within a runtime overhead of less than a factor of 2, this may also explain some of the di erences.
Github: https://github.com/azuendorf/FulibSolutionTTC2019
Docker: zuendorf/fulib-solution-ttc2019
[NNZ00] Ulrich Nickel, Jorg Niere, and Albert Zundorf. 2000. The FUJABA environment. In Proceedings of the 22nd international conference on Software engineering (ICSE '00). ACM, New York, NY, USA, 742-745. DOI=http://dx.doi.org/10.1145/337180.337620 [SDMLib] SDMLib - Story Driven Modeling Library www.sdmlib.org May, 2017. [ZGR17] Zundorf A., Gebauer D., Reichmann C. (2017) Table Graphs. In: de Lara J., Plump D. (eds) Graph Transformation. ICGT 2017. Lecture Notes in Computer Science, vol 10373. Springer, Cham