A4 Refereed article in a conference publication

Expressing multi-way data-flow constraint systems as a commutative monoid makes many of their properties obvious




AuthorsJärvi, Jaakko; Haveraaen, Magne; Freeman, John; Marcus, Mat

Publication year2012

Book title Proceedings of the 8th ACM SIGPLAN Workshop on Generic Programming

DOIhttps://doi.org/https://doi.org/10.1145/2364394.2364399

Web address https://dl.acm.org/doi/10.1145/2364394.2364399


Abstract

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





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