A4 Refereed article in a conference publication
Expressing multi-way data-flow constraint systems as a commutative monoid makes many of their properties obvious
Authors: Järvi, Jaakko; Haveraaen, Magne; Freeman, John; Marcus, Mat
Publication year: 2012
Book title : Proceedings of the 8th ACM SIGPLAN Workshop on Generic Programming
DOI: https://doi.org/https://doi.org/10.1145/2364394.2364399
Web address : 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.
Downloadable publication This is an electronic reprint of the original article. |