Expressing multi-way data-flow constraint systems as a commutative monoid makes many of their properties obvious
: Järvi, Jaakko; Haveraaen, Magne; Freeman, John; Marcus, Mat
: 2012
: Proceedings of the 8th ACM SIGPLAN Workshop on Generic Programming
DOI: https://doi.org/https://doi.org/10.1145/2364394.2364399
: https://dl.acm.org/doi/10.1145/2364394.2364399
Here multi-way data-flow constraints systems are viewed as commutative monoids. A multi-way data-flow constraints system consists of a collection of constraints, each constraint being represented as a set of directed graphs. The monoid's binary operation between two constraints is defined as the set of (non-disjoint) graph unions between all possible pairs of graphs, choosing one graph from each constraint, such that the result of the union satisfies the conditions of a valid solution. This clearly is a commutative, associative operation, with the constraint containing the null graph as the neutral element. For a given constraint system, the carrier of the corresponding monoid is the closure of all combinations of constraints from the system. This then unifies the entire multi-way data-flow constraint system with a single constraint. This generic view is not at all a drastic departure of the established descriptions of multi-way data-flow constraint systems. Defining this generic view explicitly, however, makes several properties of and algorithms operating on constraint systems obvious. For example, a constraint system can be solved by folding the monoid's binary operator over the system's constraints. An example implementation in Haskell is described.