Equivalence Relations in Soufflé
Patrick Nappa has implemented a fast & low overhead method of representing equivalence relations in Soufflé. An Honours thesis has been submitted, available here, where corresponding slides can be found here.
The improved version is currently undergoing maintenance pending inclusion into the main branch of Soufflé, however an older (albeit slightly slower) implementation currently exists in Soufflé. The following demo demonstrates the special relation
eqrel_fast which is equivalent to the
eqrel_slow relation, yet the former carries an upper bounded quadratic speedup & memory improvement over the latter.
.decl eqrel_fast(x : number, y : number) eqrel eqrel_fast(a,b) :- rel1(a), rel2(b). .decl eqrel_slow(x : number, y : number) eqrel_slow(a,b) :- rel1(a), rel2(b). eqrel_slow(a,a) :- rel1(a). // reflexivity eqrel_slow(b,a) :- eqrel_slow(a,b). // symmetry eqrel_slow(a,c) :- eqrel_slow(a,b), eqrel_slow(b, c). // transitivity