Skip to content

Instantly share code, notes, and snippets.

@philzook58
Last active March 4, 2022 20:17
Show Gist options
  • Save philzook58/b3e8f8ad5d465b384da8474eea841e34 to your computer and use it in GitHub Desktop.
Save philzook58/b3e8f8ad5d465b384da8474eea841e34 to your computer and use it in GitHub Desktop.
souffle findNode functor

Building a findNode user defined functor in souffle:

First build souffle with the addition below in src/include/souffle/datastrucutre/EquivalenceRelation.h

     /*
     * Returns unionfind parent of Node
     * @param x
     */
    value_type findNode(value_type x) const {
        return sds.findNode(x);
    }

souffle test.dl -g out.cpp

Edit out.cpp. Grep for myeq to find the rel_*_myeq relation name. Replace

extern "C" {
souffle::RamSigned eqfind(souffle::RamSigned);
}

with

#include "helper.h"

and replace the name in helper.h accordingly

souffle-compile out.cpp ./out

Result:

philip@philip-desktop:~/Documents/prolog/soffule/userdef/eqrel$ ./out 
---------------
parents
===============
1
5
7
===============

This is hopefully useful for not inserting obviously bad enodes into the database, reducing pressue on subsumption. Also maybe subsumpition can be written for an add enode for example

add(x,y,z) <= add(@eqfind(x),@eqfind(y),@eqfind(z)) :- add(x,y,z).

Which may be more efficient

yada yada ayda
/**
* Returns unionfind parent of Node
* @param x
*/
value_type findNode(value_type x) const {
return sds.findNode(x);
}
yadyadayaydayada
#define eqfind(x) rel_1_myeq->ind.findNode(x)
.functor eqfind(number):number
.decl myeq(x : number, y : number) eqrel
myeq(1,2).
myeq(2,3).
myeq(2,4).
myeq(5,8).
myeq(7,7).
.decl parents(x : number)
parents(@eqfind(x)) :- myeq(x,_).
.output parents(IO=stdout)
@remysucre
Copy link

One typo: datastrucutre -> datastructure

For subsumption to work, findNode(x) needs to return x if the equivalence relation does not contain x yet:

    /**
     * Returns unionfind parent of Node
     * @param x
     */
    value_type findNode(value_type x) const {
        if (!sds.nodeExists(x)) return x;
        return sds.findNode(x);
    }

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment