Bx Examples Repository
Title: ExpressionTreesAndDAGs
Version: 0.1
Type:
Sketch.
Overview
This example is taken from compiler construction: Given an abstract syntax tree of an expression, a directed acyclic graph (dag) is to be constructed, which contains common subexpressions only once.
Given such a the dag created by this folding transformation, the original tree may be reconstructed by unfolding the dag.
The figure below (taken from [1]) depicts a concrete example for the expression (a/10 + (b-10))*(a/10 + (b-10)).
Models
In the diagram below (taken from [1]), simple class diagrams are used to show one possible representation of this scenario.
Consistency
A pair of a tree and a DAG is consistent, if traversing both the tree and the DAG in the same order (e.g., inorder) results in the same sequentialisation (the expression represented by the tree/DAG).
Consistency Restoration
Properties [optional section]
Variants [optional section]
Discussion
This is a particularly nasty example for TGGs and highlights a current limitation.
The problem is that the tree is best constructed top-down by unfolding the DAG, while the DAG is best constructed bottom-up by folding the tree.
As a TGG, however, describes the simultaneous construction of both structures, it is difficult (currently this seems actually impossible) to describe and unify these conflicting traversal strategies in a single (triple graph) grammar.
This might be a starting point to formally characterising the class of consistency relations that can be described with TGGs: perhaps the order of "information" in both structures must be the same or similar…
There are, however, some interesting advanced language features that exist for graph transformations and that might be integrated into TGGs and used to solve this problem in the future: (i) amalgamation, which could be used to achieve some form of unfolding/folding, and some form of path expressions to extract information far away in the tree/DAG.
References [optional section]
This example is taken from the following paper:
[1] Westfechtel, Bernhard. "Case-based exploration of bidirectional transformations in QVT Relations." Software & Systems Modeling (2016): 1-41.
Author(s)
Bernhard Westfechtel, Anthony Anjorin
Reviewer(s)
Comments
Artefacts [optional section]
An implementation with QVT-R can be taken from: Westfechtel, Bernhard. "Case-based exploration of bidirectional transformations in QVT Relations." Software & Systems Modeling (2016): 1-41.