-
Notifications
You must be signed in to change notification settings - Fork 248
Description
It would help to explain not just what the various field of a
Substitutionare (which can usually be adequately captured by inline doxygen comments), but to give some insight/intuition into why the particular design was chosen (see thevisitableREADME for an example)
As an example, the beginning of the README could be replaced with
A _substitution_ takes a PCG as input and rewrites a subgraph of the given PCG in a way that maintains the correctness of the PCG.
Equivalently, we can view a substitution as taking a subgraph of a PCG and replacing it with a different graph.
We refer to the subgraph that is replaced as the _input graph_, and the graph that replaces input graph we refer to as the _output graph_.
This intuitively defines what a substitution is, but does not tell us how to represent a substitution within FlexFlow.
If we naively represent a substitution with a pair of graphs, we run into a few problems:
1. What happens to the edges between nodes in the input graph and nodes in the rest of the PCG? Since every edge in a graph ends in a node, the output graph would be completely isolated from the rest of the PCG.
2. If we represent each input and output graph concretely, we may end up with an enormous or even potentially infinite number of substitutions. To provide some intuition, consider a substitution that takes a node with integer value `a` and a node with integer value `b` and returns a node with integer value `c = a + b`. To represent this substitution for all input graphs would require enumerating every possible value of `a` and `b`, which is essentially infinite.
To solve (1) we instead represent both the input and output graphs as _open graphs_ (see [graph](lib/utils/include/graph/README.md) for more details).
To solve (2) we replace the input open graph with a _graph pattern_ which is similar to a regular expression in that it is capable of matching a potentially infinite number of input graphs, and we replace the output graph with a _graph expression_, which is essentially a function from the nodes matched by the input graph pattern to the resulting output graph.In addition, it would help to introduce a basic example (does not have to have any connection to actual operators--will probably be clearest with fake operators named like A, B, etc. just to avoid any details of dealing with and explaining real operators. This example could then be used throughout the README to provide concrete values for each of the fields discussed, which would make the document much more approachable.