datalog-dafsa

Language Reference

This is the complete reference for the rule language. Every example is a real construct that the parser and compiler accept (several are drawn directly from the passing test suite). Rules are passed to the engine as source text via dl_load_rules, the CLI query / qmagic commands, or a .dl file.

Comments

Line comments start with # and run to the end of the line.

# this is a comment
tc(X, Y) :- edge(X, Y).        # transitive closure base case
tc(X, Y) :- edge(X, Z), tc(Z, Y).

Facts

A fact is a ground predicate with constants only — a predicate followed by a parenthesised argument list, terminated by a full stop. There is no :-. 

edge(1, 2).
edge(2, 3).
person("alice").

Rules

A rule is head :- body1, body2, ..., bodyN. The body atoms are conjoined with commas; the head is a single atom. Rules may reference existing relations (arity must match) or declare a new derived relation. 

path(X, Y) :- edge(X, Y).
tc(X, Y) :- edge(X, Y).
tc(X, Y) :- edge(X, Z), tc(Z, Y).

Multiple rules with the same head predicate form a union: the engine materialises each rule and unions the results, deduplicating. There is no ; disjunction operator — same-head rules are the way to express a disjunction. 

p(X) :- edge(X, Y).
p(Y) :- edge(X, Y).   # p = union of the two rules' results, deduplicated

Variables, constants, integers and strings

q("alice").          # double-quoted string constant
q(foo).              # bare lowercase symbol constant
q(42).               # integer literal (raw u32)

Note the asymmetry: "foo" (double quotes) is a string constant; '...' (single quotes) is a regex pattern and is only valid after ~ (see Regex). A bare lowercase identifier is itself a symbol constant.

Recursion

Recursive rules are evaluated with a semi-naive fixpoint. A predicate is recursive if it appears in its own body, directly or through a cycle. 

tc(X, Y) :- edge(X, Y).
tc(X, Y) :- edge(X, Z), tc(Z, Y).     # recursive: tc in its own body

Aggregates are not allowed in recursive rules (a compile error).

Negation

A negated body atom is prefixed with !. Negation is stratified: a variable in a negated atom must be bound by a positive body atom first, and negation through recursion is rejected at compile time. 

path(X, Y) :- edge(X, Y), !blocked(X, Y).
reachable(X) :- edge(X, Y), !blocked(X).

Un-stratifiable programs (a strict dependency cycle through negation) are a loud compile error.

Equality

Body equality is written X = Y (both sides variables). It acts as a filter when both sides are bound, and binds an unbound variable from its bound counterpart otherwise. 

q(X, Y) :- edge(X, Y), X = Y.        # keep rows where X == Y
q(Y)    :- edge(X, Y), X = Y.        # bind Y from an already-bound X

Comparisons

Ordering comparisons < <= > >= accept a variable or an integer constant on either side. Inequality != additionally accepts a symbol constant on the right (it interns the symbol and compares symbol ids). A symbol constant is not allowed in an ordering comparison. 

lt(X, Y) :- pair(X, Y), X < Y.
le(X, Y) :- pair(X, Y), X <= Y.
gt(X, Y) :- pair(X, Y), X > Y.
ge(X, Y) :- pair(X, Y), X >= Y.
ne(X, Y) :- pair(X, Y), X != Y.
r(X)     :- val(X), X != foo.        # != accepts a symbol-constant RHS

An ungrounded comparison operand (a variable not bound by any positive body atom) is a loud compile error.

Arithmetic

Arithmetic is written X = <expr> in the body, producing the value X. Operators are + - * / %; * / % bind tighter than + -, all left-associative, with parentheses allowed. Operands are variables and integer constants (a symbol constant is rejected — symbols have no numeric value). Arithmetic wraps at u32 (0 - 1 == 0xFFFFFFFF), and division/modulo by a literal 0 is a compile error (a variable divisor of 0 simply yields no tuple). 

r1(X) :- pair(A, B, C), X = A + B * C.      # precedence: A + (B*C)
r2(X) :- pair(A, B, C), X = (A + B) * C.    # parentheses
add(X, Y, S) :- pair(X, Y), S = X + Y.
inc(X)       :- pair(A, B, C), X = A + 1.   # integer constant operand

Arithmetic in a recursive rule works (bounded by the fixpoint), and the result variable must not be bound before the arithmetic is evaluated.

Aggregates

Aggregates appear in the body, binding a result variable: N = count(), S = sum(Y), M = min(Y), M = max(Y). The result variable is referenced in the head, and every other head variable is the implicit group-by key. 

# group by X: number of outgoing edges per node
cnt(X, N) :- edge(X, Y), N = count().

# group by X: total of Y per X
total(X, S) :- edge(X, Y), S = sum(Y).

# min / max of Y per X
minv(X, M) :- edge(X, Y), M = min(Y).
maxv(X, M) :- edge(X, Y), M = max(Y).

# no group-by vars -> a single global count
cnt(N) :- edge(X, Y), N = count().

Constraints on aggregates:

String builtins

String values are interned symbols. Two kinds of builtin exist: 

cat(A, B, C) :- pair(A, B), C = concat(A, B).
lens(A, N)   :- str(A),    N = length(A).       # byte length
lc(X)        :- s(Y),      X = lower(Y).        # ASCII case folding
uc(X)        :- s(Y),      X = upper(Y).
pref(X)      :- str(X),    prefix(X, "he").
suf(X)       :- str(X),    suffix(X, "o").
cont(X)      :- str(X),    contains(X, "ll").

lower and upper are implemented (ASCII A–Z folding). length is the byte length (UTF-8 bytes, not codepoints), and it also accepts a constant list literal (list length). String operands must be variables or double-quoted string constants — a raw integer operand is rejected. A producer result longer than 4096 bytes backtracks (no tuple).

Lists

Lists are first-class values, interned in a term store (equal lists share one handle). List literals are written [e1, e2, ...]; [] is the empty list. 

r(X, H, T, A) :- p(X), L = cons(X, [7, 8]), H = car(L),
                 T = cdr(L), A = append(L, [9]).
q(H, T)       :- p([H | T]).                 # pattern in a relational arg
r(X)          :- p([7, X]).                  # constant element + var
r(X)          :- p(L), member(X, L).         # generator
s(X)          :- num(X), p(L), member(X, L). # filter
empty_tail(A, B) :- [A, B] = [1, 2].         # assignment form, empty tail
tail_pat(H, T)   :- [H | T] = [1, 2, 3].     # assignment form, tail
from_var(H, T)   :- p(L), [H | T] = L.       # assignment from a var

A list pattern is not allowed in a rule head or fact (use cons to build), or in a negated atom (patterns cannot bind variables under negation). The tail after | must be a variable.

Range

range(X, Rel, Lo, Hi) is a reserved builtin that scans the distinct leading-column values of the relation Rel in the half-open interval [Lo, Hi):

When X is unbound, range acts as a generator yielding each distinct col0 value of Rel in [Lo, Hi), in lex order. When X is bound it acts as a filter. The range is over the leading column only. 

q(X) :- range(X, r, 10, 20).          # X in {col0 of r in [10, 20)}
p(X) :- r(X), range(X, r, 10, 20).    # filter form
q(X, Lo, Hi) :- bounds(Lo, Hi), range(X, r, Lo, Hi).   # var bounds

Rel must be a known, non-variadic relation of arity ≥ 1. Range over a recursive relation, an unknown relation, a negated range, or an ungrounded bound variable is a loud compile error.

Regex patterns

A body atom may carry a regex pattern written as a single-quoted string after a tilde: pred(...) ~ 'pattern' or, to target a specific column, pred(...) ~ k 'pattern' where k is a 0-based integer column index (default 0 = leading column). The pattern is compiled to a DFA and matched against the string content of that column's value (via the symbols table), not the raw binary key — so ~ 'a.*' means "column's text starts with a". An integer (non-string) column matches nothing. In the CLI, use pattern <rel> [<col>] '<pattern>' for standalone regex queries. 

q(X, Y) :- edge(X, Y) ~ 1 '(a|b).*'.   # filter on column 1's text

A negated pattern atom is not supported (compile error). A column index out of range for the atom is also a compile error. In rules, patterns are compiled at load time; a bad regex is a loud error.

Variadic relations

A relation may be declared variadic, accepting facts of any arity 1–8. Storage is per-arity fixed-width; rule atoms resolve to the variant matching their syntactic argument count. A variadic head must be declared before dl_load_rules. Aggregates over a variadic relation, recursive variadic heads, and magic/top-down queries over programs containing variadics are rejected at compile time (they always evaluate via the full fixpoint). 

/* C API: */
dl_declare_relation_variadic(db, "v");

Reserved names

The builtin names are reserved — a rule head cannot use them (rejected with a clear diagnostic): member, car, cons, cdr, append, concat, length, lower, upper, prefix, suffix, contains, range.

Compile-error semantics

The engine never silently mis-evaluates. Unsupported or malformed programs are rejected with a diagnostic at compile time and dl_load_rules / dl_compile return -1. Rejected cases include: