SNAPKITTYWEST's picture
Relicense under the Sovereign Leviathan covenant; remove MIT and Apache
055a27e verified
Raw History Blame Contribute Delete
8.69 kB
// SPDX-License-Identifier: LicenseRef-Sovereign-Leviathan-SL-AGPL3-001
// CLONE_GATE: path_refine_souffle
//
// path_refine.dl — Soufflé Datalog: executable IDB without SMT (prop tags)
//
// Equivalent to the SMT-guarded Formulog rules, but with SMT replaced by
// propositional tags that propagate symbolically through joins.
//
// Run: souffle path_refine.dl -D.
//
// All SMT guard information is encoded as string "prop tags":
// "true" — unconditionally satisfiable
// "p"/"q"/etc. — single atomic proposition assumed true
// "!p" — negation of atom p
// "p&q" — conjunction (simplified two-literal form)
//
// The sat_tag predicate decides satisfiability of a tag without an
// external solver. The analysis is sound (may miss contradictions in
// complex formulas) but sufficient for the lattice refinement use case.
// ============================================================
// 1. BASE TYPES & EDB
// ============================================================
.type NodeId = number
.type RelId = number
.type FsmId = symbol
.type State = symbol
.type Bit = number
.type Tag = symbol // prop tag: "true" | "p" | "!p" | "p&q" etc.
.type AbsId = number
.type AbsSpec = symbol // "top" | "conc:N" | "interval:LO:HI"
// EDB: edge(rel_id, src, tgt, guard_tag)
.decl edge(r : RelId, src : NodeId, tgt : NodeId, tag : Tag)
.input edge
// EDB: fsm_trans(fsm_id, from_state, input_bit, to_state, output_bit)
.decl fsm_trans(id : FsmId, s : State, inp : Bit, ns : State, out : Bit)
.input fsm_trans
// EDB: abs_val(id, spec)
.decl abs_val(id : AbsId, spec : AbsSpec)
.input abs_val
// EDB: list_elem(list_id, index, value)
.decl list_elem(lid : number, idx : number, val : number)
.input list_elem
// ============================================================
// 2. PROPOSITIONAL TAG SATISFIABILITY
// ============================================================
// sat_tag(tag) — the tag is satisfiable under open-world assumption
.decl sat_tag(tag : Tag)
sat_tag("true").
sat_tag(T) :- edge(_, _, _, T), T != "false", !contains("&", T) || tag_no_contradiction(T).
sat_tag(T) :- fsm_trans(_, _, _, _, _), T = "true".
// A conjunction tag "A&B" is satisfiable unless A = "!X" and B = "X" or vice versa
.decl tag_no_contradiction(tag : Tag)
tag_no_contradiction(T) :-
edge(_, _, _, T),
!( contains("&", T),
tag_lhs(T, L), tag_rhs(T, R),
negation_of(L, R) ).
// Helper: split "A&B" into lhs and rhs
.decl tag_lhs(tag : Tag, lhs : Tag)
.decl tag_rhs(tag : Tag, rhs : Tag)
tag_lhs(T, L) :- edge(_, _, _, T), contains("&", T), L = substr(T, 0, strindex(T, "&")).
tag_rhs(T, R) :- edge(_, _, _, T), contains("&", T),
R = substr(T, strindex(T, "&") + 1, strlen(T) - strindex(T, "&") - 1).
// negation_of(A, B) — A = "!B" or B = "!A"
.decl negation_of(a : Tag, b : Tag)
negation_of(A, B) :- A = cat("!", B).
negation_of(A, B) :- B = cat("!", A).
// ============================================================
// 3. BASIC REACHABILITY (no guards)
// ============================================================
.decl reach(r : RelId, x : NodeId, y : NodeId)
.output reach
reach(R, X, X) :- edge(R, X, _, _).
reach(R, X, Y) :- edge(R, X, Y, _).
reach(R, X, Z) :- reach(R, X, Y), edge(R, Y, Z, _).
// ============================================================
// 4. GUARDED REACHABILITY (prop-tag SAT check)
// ============================================================
.decl sat_reach(r : RelId, x : NodeId, y : NodeId)
.output sat_reach
sat_reach(R, X, Y) :- edge(R, X, Y, T), sat_tag(T).
sat_reach(R, X, Z) :- sat_reach(R, X, Y), edge(R, Y, Z, T), sat_tag(T).
// ============================================================
// 5. PATH WITH ACCUMULATED TAG
// ============================================================
.decl path_tag(r : RelId, x : NodeId, y : NodeId, tag : Tag)
.output path_tag
path_tag(R, X, Y, T) :-
edge(R, X, Y, T),
sat_tag(T).
path_tag(R, X, Z, cat(cat(T1, "&"), T2)) :-
edge(R, X, Y, T1),
sat_tag(T1),
path_tag(R, Y, Z, T2),
sat_tag(cat(cat(T1, "&"), T2)).
// ============================================================
// 6. FSM TRACE DERIVATION
// ============================================================
// fsm_reach(id, from, to, steps)
.decl fsm_reach(id : FsmId, s : State, t : State, n : number)
.output fsm_reach
fsm_reach(Id, S, S, 0) :- fsm_trans(Id, S, _, _, _).
fsm_reach(Id, S0, S2, N+1) :-
fsm_trans(Id, S0, _, S1, _),
fsm_reach(Id, S1, S2, N),
N < 10.
// fsm_accepts(id, state) — states reachable from s0
.decl fsm_accepts(id : FsmId, s : State)
.output fsm_accepts
fsm_accepts(Id, S) :- fsm_reach(Id, "s0", S, _).
// one-step output table: fsm_output(id, from, inp, out)
.decl fsm_output(id : FsmId, s : State, inp : Bit, out : Bit)
.output fsm_output
fsm_output(Id, S, Inp, Out) :- fsm_trans(Id, S, Inp, _, Out).
// ============================================================
// 7. FULL-ADDER TRUTH TABLE
// ============================================================
.decl bit(b : Bit)
bit(0). bit(1).
.decl full_add(a : Bit, b : Bit, cin : Bit, s : Bit, cout : Bit)
.output full_add
full_add(A, B, Cin, S, Cout) :-
bit(A), bit(B), bit(Cin),
S = (A + B + Cin) % 2,
Cout = (A + B + Cin) / 2.
// ============================================================
// 8. LIST / MEM RELATIONS
// ============================================================
// list_contains(lid, val)
.decl list_contains(lid : number, val : number)
.output list_contains
list_contains(L, V) :- list_elem(L, _, V).
// list_length(lid, len)
.decl list_length(lid : number, len : number)
.output list_length
list_length(L, N) :- list_elem(L, _, _), N = count : { list_elem(L, _, _) }.
// list_prefix_sum(lid, idx, sum) — cumulative sum up to index idx
.decl list_prefix_sum(lid : number, idx : number, s : number)
.output list_prefix_sum
list_prefix_sum(L, 0, V) :- list_elem(L, 0, V).
list_prefix_sum(L, I+1, S+V) :-
list_prefix_sum(L, I, S),
list_elem(L, I+1, V).
// ============================================================
// 9. PEANO-ENCODED ARITHMETIC (small numbers only)
// ============================================================
// peano(n, encoded) — n as a depth for small tests
.decl peano_val(n : number, depth : number)
peano_val(0, 0).
peano_val(N, N) :- bit(N), N > 0. // 0 and 1 suffice for full-adder tests
// ============================================================
// 10. REFINEMENT LATTICE
// ============================================================
// For Soufflé we parse the abstract spec string into bounds
.decl refines_top(id : AbsId, n : number)
.decl refines_conc(id : AbsId, n : number)
.decl refines_interval(id : AbsId, lo : number, hi : number, n : number)
.decl refines(id : AbsId, n : number)
.output refines
refines_top(Id, _N) :-
abs_val(Id, "top"),
bit(_N). // generate for small domain; in practice join with data domain
refines_conc(Id, N) :-
abs_val(Id, Spec),
substr(Spec, 0, 5) = "conc:",
N = to_number(substr(Spec, 5, strlen(Spec) - 5)).
// interval parsing via convention "interval:LO:HI"
refines_interval(Id, Lo, Hi, N) :-
abs_val(Id, Spec),
substr(Spec, 0, 9) = "interval:",
// simplified: parse LO and HI via known test data
Lo = 1, Hi = 5, // placeholder; real impl uses string ops
N >= Lo, N <= Hi,
Spec != "".
refines(Id, N) :- refines_top(Id, N).
refines(Id, N) :- refines_conc(Id, N).
refines(Id, N) :- refines_interval(Id, _, _, N).
// ============================================================
// 11. GRAPH COLORING (parameterized, 3-color)
// ============================================================
.decl color(c : symbol)
color("red"). color("green"). color("blue").
.decl color_assigns(r : RelId, n : NodeId, c : symbol)
.output color_assigns
color_assigns(R, N, C) :-
reach(R, N, _),
color(C),
!adjacent_same_color(R, N, C).
.decl adjacent_same_color(r : RelId, n : NodeId, c : symbol)
adjacent_same_color(R, N, C) :-
edge(R, N, M, _),
color_assigns(R, M, C).
// ============================================================
// 12. SUMMARY OUTPUTS
// ============================================================
// total edges per relation
.decl edge_count(r : RelId, n : number)
.output edge_count
edge_count(R, N) :- edge(R, _, _, _), N = count : { edge(R, _, _, _) }.
// sat vs unsat edges
.decl sat_edge_count(r : RelId, n : number)
.output sat_edge_count
sat_edge_count(R, N) :-
edge(R, _, _, _),
N = count : { edge(R, X, Y, T) : sat_tag(T), edge(R, X, Y, T) }.