Implement simplify() algorithm

[cthoyt]

The simplify algorithm takes a graph, a probabilistic expression, and a topological sort order and produces a simplified probabilistic expression

Originally published with https://github.com/cran/causaleffect

class Simplifier:
    """A data structure to support application of the simplify algorithm.
    The simplify function is implemented inside a class since there is shared state between recursive calls
    and this makes it much easier to reference rather than making the simplify function itself have many
    arguments
    """

    #: The constant topological ordering
    ordering: Sequence[Variable]

    def __init__(
        self,
        graph:NxMixedGraph,
        ordering: Optional[Sequence[Union[str, Variable]]] = None,
    ) -> None:
        """Instantiate the simplifier.
        :param graph: A graph
        :param ordering: An optional topological ordering. If not provided, one will be generated from the graph.
        """
        self.graph = graph

        if ordering is None:
            self.ordering = [Variable(name) for name in self.graph.topological_sort()]
        else:
            self.ordering = _upgrade_ordering(ordering)

    def simplify(self, expression: Expression) -> Expression:
        """Simplify the expression given the internal topological ordering.
        :param expression: The expression to simplify
        :returns: The simplified expression
        """
        raise NotImplementedError

[djinnome]

• [ ] simplify Simplification of an atomic expression $A=<T,S>$ given graph G and topological ordering $\pi$
• [ ] join: Construction of the joint distribution of the set $J$ and a variable $V$ given their conditional sets $D$ and $C$ using d-separation criteria in $G$. $S$ is the current summation variable, $M$ is the set of variables not contained in the expression and $\pi$ is a topological ordering.
• [ ] insert: Insertion of variable $M'$ into the joint term $P(J |D)$ using d-separation criteria in $G$ . $S$ is the current summation variable and $\pi$ is a topological ordering.
• [ ] deconstruct Recursive wrapper for the simplification of an expression $B=< B , A , S >$ given graph $G$ and topological ordering $\pi$ .
• [ ] extract Extraction of terms independent of the summation indices from a expression B = 〈B , A, S 〉 given graph G and topological ordering π .
• [ ] q-simplify Simplification of a quotient $P_{B_1}/P_{B_2}$ given by the values of two expressions $B_1 = 〈 B_1 , A_1 , S_1 〉$ and $B_2 = 〈 \mathbf{B}_2 , \mathbf{A}_2 , \mathbf{S}_2 〉 given graph G and topological ordering π .

[cthoyt]

It would be really great to have a y0 DSL to causaleffect converter, then we could create objects to pass directly to the causaleffect simplify implementation as an oracle for the tests