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

DOIhttps://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.


Last updated on 2025-17-10 at 10:06