2024/07/23 Leonard Ritter, Duangle GbR
A relational event graph is described with unpredicated rules relating events, connecting a product of n sources and m conditions to a single sink (also called the goal). The format is as follows:
Y :- X[1], X[2], ..., X[n], c[1], c[2], ..., c[m].
means "when all events X[1]..X[n] have happened, and all conditions c[1]..c[m] have been met, then the goal Y will happen". Because the right hand side is a product, the arguments are commutative and associative, so that the rule makes no demands as to in what order the sources are called, or the conditions are evaluated.
The resulting graph is a directed hypergraph of the B-graph class, with each rule constituting a B-arc.
The task is now to manifest the relational event graph as a callgraph (as precursor of a control flow graph) that satisfies all rules.
We recognize the callgraph as a transitive reduction of the hypergraph, which means all source edges of a rule are reducible to one (and only one) edge that connects to a callgraph path through all sources of the rule.
Because the callgraph is initially incomplete, we must start from trivially reducible rules with single sources. This adds more edges to the callgraph, which allows us to reduce more complex rules, until a fixpoint is reached because no more rules can be reduced. See this example (conditions omitted for clarity):
(1) A.
(2) B :- A.
(3) B :- A, B, C.
(4) C :- A, B.
(5) D :- A, B, C.
// iteration 1: trivially reducible rules
(1) A.
(2) B :- A.
// iteration 2
(4) C :- B. // :- A
// iteration 3
(3) B :- C. // :- B :- A
(5) D :- C. // :- B :- A
If a rule reduction leads to more than one possible callgraph edge, there exists an ambiguity in the program that the user must resolve by adding more edges.
If one or more rules remain undecidable after the fixpoint, the user should be warned as the rules would never be applied.
Because sources are not required to dominate the reduced rules, we can not guarantee at compile time that all source events of a rule will always have happened; we can only verify that a goal is connected to all sources. An additional transformation of the callgraph is required, in which non-dominating sources are serialized to optional arguments on the dominant path, and then tested and dispatched where the rule conditions are checked. This mechanism saves the user from having to implement sum type encodings to circumvent dominance issues.