Created
September 2, 2020 02:15
-
-
Save kmicinski/b6931fafe4f3b4d814984a8bf82e4ef9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
.decl R(x:number,y:number) | |
.decl H(x:number) | |
.decl G(x:number) | |
.decl P(x:number,y:number) | |
.output R | |
R(x,y) :- H(x), G(y), P(x,y). | |
H(1). | |
H(2). | |
G(2). | |
G(3). | |
P(1,4). | |
P(2,3). | |
// How could I compile this rule...? | |
// R(x,y) :- H(x), G(y), P(x,y). | |
// - Iterate over P | |
// | |
// One way... (slow): | |
// - For every pair (x,y) in P | |
// - For every x0 in H | |
// - For every y0 in G | |
// - If x0 = x and y0 = y, but (x,y) in P | |
// | |
// Another way... (fast): | |
// - For every pair (x,y) in P | |
// - Select x from H | |
// - Select y from G | |
// - If selections exist, put (x,y) in R | |
// Souffle compiles a Datalog program into a graph of SCCs (strongly | |
// connected components) | |
.decl Input(x:number). | |
.decl Input1(x:number,y:number). | |
.decl P1(x:number,y:number). | |
Input(2). | |
Input(3). | |
Input1(2,3). | |
Input1(3,4). | |
// P1 gets populated with (3,2) | |
P1(x,y) :- Input(x), Input1(y,x). | |
// Interpreting this ^^ rule... One way: | |
// - Iterate over x in Input | |
// - Iterate over y (first column) in Input1 | |
// - For each x0 (second column) in Input1 | |
// - If x0 = x, put (x,y) in P1 | |
// | |
// - Iterate over x in Input | |
// - Select x (second column) from Input1 | |
// - For every y in that selection, put (x,y) in P1 | |
.decl P2(x:number, y:number) | |
P2(x,y) :- P1(y,x). | |
// I can fully run P1 before I run P2 | |
// Compile to c++ via... | |
// souffle -g semi-naive.dl -o out.cpp | |
// clang++ -std=c++17 out.cpp -o out | |
// Then run out (or inspect out.cpp) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment