Skip to content

Instantly share code, notes, and snippets.

@kmicinski
Created September 2, 2020 02:15
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kmicinski/b6931fafe4f3b4d814984a8bf82e4ef9 to your computer and use it in GitHub Desktop.
Save kmicinski/b6931fafe4f3b4d814984a8bf82e4ef9 to your computer and use it in GitHub Desktop.
.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