Datalog in a box
Which boxes run downstream of this one? Which two write the same property? A Field document is a graph, and questions like these often need to follow its connections more than once.
Datalog gives you a way to ask them. State some facts, write rules that derive more facts, and the engine follows those rules until it has the answers. Facts can come from Datalog text, Kotlin collections, or the document you have open. For finding values by pattern inside an object, see Querying Object Graphs.
Facts, rules, and a question
A fact is a row. A rule reads head :- body, which you can say out loud as head if body.
Capitalised names are variables; lowercase names are constants, so imports(app, ui) and
imports("app", "ui") are the same fact.
:::static
val d = Datalog()
d.add(
"""
#datalog
% which module pulls in which
imports(app, ui). imports(app, store).
imports(ui, util). imports(store, util). imports(util, log).
needs(A, B) :- imports(A, B).
needs(A, C) :- needs(A, B), imports(B, C).
""",
)
println("app needs " + d.query("needs(app, X)").column("X").joinToString(", "))
println("does app need log? " + d.ask("needs(app, log)"))
println("modules that need log: " + d.query("needs(A, log)").size)
Answers land beside the line that asked: edit a rule, run, read. Two rules for needs, read as
alternatives: app needs whatever it imports, and it needs whatever that needs. Nothing says how
far to follow the chain, and nothing has to.
The #datalog on the first line is a marker the editor looks for; the parser ignores it. Leave it
out and the program still runs. Put it in and the region lights up, which the last section covers.
The answer is a fixpoint
query runs one goal. solve hands back the whole model: every relation, with every fact the
rules can derive.
:::static
val d = Datalog()
d.add(
"""
#datalog
edge(a, b). edge(b, c). edge(c, d). edge(d, b).
path(X, Y) :- edge(X, Y).
path(X, Z) :- path(X, Y), edge(Y, Z).
""",
)
display("main", d.solve())
Four stated edges produce twelve paths. The cycle b → c → d → b makes those three nodes mutually
reachable, including each from itself. The rules still stop: they can only combine values that are
already there, so after a few rounds there is nothing new to add.
Why a fact is there
why shows how a fact was derived: which rules fired, and which stated facts they started from.
:::static
val d = Datalog()
d.add(
"""
#datalog
edge(a, b). edge(b, c). edge(c, d). edge(d, b).
path(X, Y) :- edge(X, Y).
path(X, Z) :- path(X, Y), edge(Y, Z).
""",
)
display("main", d.why("path(a, d)"))![a derivation tree headed 'why path(a, d)', indented by arrow glyphs: path(a, d) from the recursive clause, then path(a, c) from the same clause, then path(a, b) from the base clause, and at the leaves edge(a, b), edge(b, c) and edge(c, d), each tagged [fact]. Every interior node carries the rule that fired it in brackets](../assets/datalog/why.png)
Each line names the rule that produced it, and the leaves are facts you stated. Cycles are fine:
path(a, a) in the graph above gets a finite proof too.
A proof runs through an aggregate as well. A fact derived through count or sum lists the rows
that contributed to it and the arithmetic that combined them:
payroll(sales, 300) [payroll(D, S) :- dept(D), S = sum P : { emp(_1, D, P) }]
dept(sales) [fact]
S = sum P : { emp(_1, sales, P) } [aggregate: sum over 2 tuples = 300]
emp(ada, sales, 100) [fact; contributes P = 100]
emp(bob, sales, 200) [fact; contributes P = 200]min and max label the tuple that was the extreme, and keep the rest of the group in the proof
too, because "nothing bigger exists" is half of what the answer means. A group is capped at 24 lines
of display; the value is always computed over the whole of it. A negated body literal appears as its
own step, since "no such fact" is often the reason a rule fired.
Why one is not
An empty result gives no reason, so whyNot runs the query one goal at a time and names the goal
where the answers ran out.
whynot cell(C, V), V > 5, colour(C, red) no answers
1 cell(C, V) 3 answers
2 V > 5 1 answer
3 colour(C, red) 0 answers <- nothing survives here
a binding that got this far: C = a3, V = 10Ask about a single derived fact and it does the same walk once per rule that could have produced it, with the head's constants filled in, and puts the attempt that got furthest first:
whynot path(a, e) not in the model; 2 rule(s) could have produced it
via path(X, Z) :- path(X, Y), edge(Y, Z)
1 path(a, Y) 3 answers
2 edge(Y, e) 0 answers <- nothing survives here
a binding that got this far: Y = b
via path(X, Y) :- edge(X, Y)
1 edge(a, e) 0 answers <- nothing survives herewhyNot tells apart three causes that look the same in an empty result: a goal with no matching
rows, a predicate nothing defines, and a test written before the goal that binds its variable. The
last is reported as "not evaluable this early", because the fix is to reorder the rule rather than
to look for missing data.
Facts from Kotlin objects
facts takes Kotlin objects and a projection, so the rules can run over whatever you already have
in the box. Negation and aggregation are both available, with the usual condition: they need the
relations they read to be finished first, so a rule may not negate or aggregate over something that
depends on itself. The engine checks and says so by name if you try.
:::static
data class Take(val clip: String, val shot: String, val seconds: Int, val rating: Int)
val takes = [
Take("a017", "wide", 42, 5),
Take("a018", "wide", 38, 2),
Take("a021", "close", 19, 4),
Take("a022", "close", 22, 3),
Take("a030", "insert", 8, 2),
Take("a031", "insert", 11, 1),
]
val d = Datalog()
d.facts("take", takes) { [it.clip, it.shot, it.seconds, it.rating] }
d.facts("shot", [["wide"], ["close"], ["insert"]])
d.add(
"""
#datalog
covered(S) :- take(_, S, _, R), R >= 4.
reshoot(S) :- shot(S), !covered(S).
footage(S, Total, Best) :- shot(S),
Total = sum Sec : { take(_, S, Sec, _) },
Best = max R : { take(_, S, _, R) }.
""",
)
display("main", d.query("footage(S, Total, Best)"))
display("reshoot", d.query("reshoot(S)"))
An aggregate groups by whichever of its variables the enclosing rule has already bound. shot(S)
binds S before the aggregate runs, so sum Sec : { take(_, S, Sec, _) } totals one shot at a
time. Take shot(S) out and you get one number for the whole table.
_ is a hole, and each one is separate: take(_, S, Sec, _) means some take of this shot, not a
take whose clip and rating are equal. Under ! a hole is existential, so !covered(S) and
!child(_, X) both mean "no row matches".
The document is a database
Box.datalog(...) loads the graph you are looking at. Boxes, names, edges, nesting, frames and
scalar properties all arrive as relations:
:::static
display("main", dlBoxRelationTable())
Which makes the recursive questions about a document short. Here the graph is built in the box so
the answer is reproducible, but thisBox.datalog(program) runs the identical rules against the
document you have open:
:::static
fun boxNamed(id: String, name: String, parent: Box?): Box {
val b = Box(id)
b.name = name
if (parent != null) {
parent.children.add(b)
b.parents.add(parent)
}
return b
}
val root = boxNamed("root", "document", null)
val loader = boxNamed("loader", "loader", root)
val mesh = boxNamed("mesh", "mesh", loader)
val shader = boxNamed("shader", "shader", loader)
val draw = boxNamed("draw", "draw", mesh)
val notes = boxNamed("notes", "notes", root)
val d = Datalog()
d.addBoxGraph(root)
d.add(
"""
#datalog
downstream(A, B) :- child(A, B).
downstream(A, C) :- downstream(A, B), child(B, C).
leaf(X) :- box(X), !child(X, _).
""",
)
display("main", d.query("downstream(loader, X), name(X, N)"))
display("leaves", d.query("leaf(X), name(X, N)"))
The graph is read once, as a snapshot, so an answer describes the document as it was when you
asked. Build a new Datalog to refresh it.
Any object graph
addBoxGraph knows about boxes. For any other Kotlin object, addObjectGraph walks it the way
graphPaths does and turns every slot it visits into facts. A graphPaths
pattern can address slots but cannot follow an edge repeatedly, or notice that two paths lead to
the same object; Datalog supplies both.
addObjectGraph gives slot, link, segment, depth, at, value, type and writable;
dlObjectGraphRules adds alias, reaches, unreached and leaf on top. In at(Path, ObjectId)
every non-scalar value gets a number by identity, so two paths that reach the same object share a
number, and alias is at joined with itself:
:::static
class Osc(var freq: Float, var gain: Float, val label: String)
class Rig(val carrier: Osc, val modulator: Osc, val spare: Osc, var title: String)
// carrier and spare are one oscillator under two names. Nothing in the type says so.
val shared = Osc(220f, 0.8f, "shared")
val rig = Rig(shared, Osc(440f, 0.2f, "mod"), shared, "rig")
val d = Datalog()
d.addObjectGraph(rig)
d.add(dlObjectGraphRules)
display("main", d.query("alias(A, B)"))
display("settable", d.query("reaches(\"carrier\", P), writable(P)"))
alias finds the two names for one oscillator. It compares identity, not equality, so two separate
oscillators with the same settings would not match.
The second answer lists every settable slot anywhere below carrier, which takes the recursive
step a graphPaths pattern cannot express.
Narrow the walk with a graphPaths pattern: addObjectGraph(rig, "carrier/*") loads one level,
and a literal prefix is much cheaper than **, which walks everything.
For a document, use addBoxGraph anyway: its child, nested, frame and prop relations are
what you want to ask about, where a walk of a Box object turns up every internal field it has.
Drawing what it derived
Query results are rows of values you can use elsewhere in Field. Here the rules separate stated edges from the ones that follow, and the drawing gives each set a different weight:
:::static
val links = [0 to 1, 1 to 2, 2 to 3, 3 to 4, 4 to 0, 1 to 5, 5 to 6, 6 to 2]
val d = Datalog()
d.facts("edge", links.map { [it.first, it.second] })
d.add(
"""
#datalog
path(X, Y) :- edge(X, Y).
path(X, Z) :- path(X, Y), edge(Y, Z).
implied(X, Y) :- path(X, Y), !edge(X, Y), X != Y.
""",
)
val n = 7
fun at(i: Int): Vec2 {
val a = i * 2.0 * PI / n - PI / 2
return vec(340.0 + 300.0 * cos(a), 170.0 + 135.0 * sin(a))
}
fun link(a: Int, b: Int, c: Vec4, t: Double) = fline {
val p = at(a)
val q = at(b)
moveTo(p.x, p.y)
lineTo(q.x, q.y)
color = c
thickness = t
}
fun dot(i: Int) = fline {
val p = at(i)
val r = 5.0
moveTo(p.x - r, p.y)
lineTo(p.x, p.y - r)
lineTo(p.x + r, p.y)
lineTo(p.x, p.y + r)
close()
filled = true
color = vec(0.98, 0.86, 0.30, 1.0)
}
// Node numbers, set just outside the ring so an edge never runs through one. Glyphs move with
// FLine.transform, which carries the cubic handles; nudging a node's point alone smears the letter.
fun label(i: Int): List<FLine> {
val a = i * 2.0 * PI / n - PI / 2
val p = at(i)
val layout = layoutText("$i", typeface("Monospaced", 22.0))
val dx = p.x + 26.0 * cos(a) - layout.advanceWidth / 2.0
val dy = p.y + 26.0 * sin(a) + 8.0
return layout.toFLines(color = vec(0.72, 0.78, 0.86, 1.0), thickness = 0.0, filled = true, stroked = false).map {
line ->
line.transform { q -> vec(q.x + dx, q.y + dy, q.z) }
}
}
val implied = d.query("implied(X, Y)").rows.map {
link((it[0] as Long).toInt(), (it[1] as Long).toInt(), vec(0.45, 0.70, 0.98, 0.20), 1.0)
}
val direct = links.map { link(it.first, it.second, vec(0.98, 0.86, 0.30, 1.0), 2.0) }
println("${links.size} stated edges, ${implied.size} implied by them")
val labels = (0 until n).flatMap { label(it) }
lines(implied + direct + (0 until n).map { dot(it) } + labels, w = 700.0, h = 350.0, fitToSize = true)
Eight edges, thirty-four consequences. The faint lines are what implied derived, and the rule
that made them is the third line of the program. Its X != Y drops self-reachability, which the
cycle 0 → 1 → 2 → 3 → 4 → 0 would otherwise contribute for every node on it.
A box that is Datalog
Set a box's main language to Datalog (Set Main Language: Datalog in the command palette) and its
children hold programs instead of Kotlin. A Datalog box accumulates: running a fragment merges it
into that box's program and prints what the fragment asked for, so you can write a rule, run it,
write a query underneath, and run just that line. Re-running the whole box is safe, because
identical rules are merged rather than appended.
A bare non-ground atom on its own is read as a question, so over(C). asks rather than failing as
a fact with a variable in it. Lines beginning with # are session commands.
No Kotlin at all in one of these. The box below is a Datalog box, and this is its whole contents:
:::static
% a spreadsheet's worth of cells, and one rule about them
cell(a1, 3). cell(a2, 4). cell(a3, 10).
over(C) :- cell(C, V), V > 5.
?- over(C).
Run a #why next to it and the box answers with the derivation rather than the row:
:::static
cell(a1, 3). cell(a3, 10).
over(C) :- cell(C, V), V > 5.
#why over(a3)
The session commands are #help, #boxes (load the live document into the base relations),
#relations, #facts <relation>, #program, #why <goal>, #whynot <goal> and #reset. A #why
about a fact that is not there points you at #whynot, which is where you wanted to be.
The editor knows the language
A Kotlin string whose first line is #datalog is an embedded region, in the same way #stacksl
and #petri regions work (Language Extensions). Rule heads are coloured
differently from the same predicate used in a body, variables differently from constants, and
hovering a predicate reports its arity and how many clauses define it. Completion offers the
program's own predicates first, then the builtins and the box-graph relations.
Diagnostics inside a region are lexical only: unbalanced brackets, an unterminated string, a clause
with no .. The rules in "What it refuses" below are checked when the program runs.
Rest the cursor on a statement and the note beside it answers from the box's model: a rule says how many facts its body derives there and draws them as a table, a query shows its answers, and a fact says whether it is in the model and which rules read its relation. A rule edited since it last ran is reported as not in the model, and no directive is ever run for a note — see Line notes.
Reference
Syntax. % and // start a line comment, /* */ a block. A clause ends with .. A variable
starts with a capital letter or _; everything else lowercase is a constant string. Numbers,
"strings", true, false and null are literals. !goal or not goal negates. ?- goal.
records a query.
Arithmetic. + - * /, mod, div, and comparisons = != < <= > >=. X = expr binds X
when nothing has bound it yet and compares when something has. + concatenates if either side is a
string. Every integral number is stored as a Long, including a computed 4.0 / 2.0, so
arithmetic results join with stated facts.
Functions. abs sign sqrt floor ceil round pow exp log sin cos tan atan2 hypot min max len
upper lower trim cat substr indexOf contains startsWith endsWith split num str int not. A call to
one of these on its own is a test, so contains(N, "shader") filters.
Aggregates. count sum min max mean collect, written X = op Expr : { body } (count takes
no expression). min, max and mean of an empty group have no value, so the rule does not fire
for that group; count and sum give 0. The target has to be a variable nothing has bound yet, so
"the maximum, and who earned it" is two rules rather than one.
Explaining. why(goal) returns a derivation tree, through aggregates and negation as well as
rules, or null when the fact is not in the model. whyNot(goal) returns the narrowing walk instead.
Both implement ToHTML, so display(…) of either from a Kotlin box draws an indented table; the
#why and #whynot directives inside a Datalog box print render()'s plain text instead.
What it refuses. A rule whose head has a variable the body never binds. A negated goal whose variables are bound nowhere else. A predicate used at two different arities. Negation or aggregation inside a recursive cycle, which it reports with the cycle named rather than picking an evaluation order.