Loge: translations
root = Path.expand("..", __DIR__)
Mix.install([
{:loge, path: Path.join(root, "loge"), override: true},
{:loge_tptp, path: Path.join(root, "loge_tptp")},
{:loge_dimacs, path: Path.join(root, "loge_dimacs")},
{:loge_asp, path: Path.join(root, "loge_asp")},
{:loge_prolog, path: Path.join(root, "loge_prolog")},
{:loge_egglog, path: Path.join(root, "loge_egglog")},
{:loge_smtlib, path: Path.join(root, "loge_smtlib")},
{:loge_turtle, path: Path.join(root, "loge_turtle")},
{:kino_loge, path: Path.join(root, "kino_loge")}
])
A translation is an engine: a source in one language in, an outcome whose output is a source in another. Its status is the relation it preserves between the two:
- Equivalent: input and output have the same models.
- EquiSatisfiable: one is satisfiable exactly when the other is.
So a verdict on the output is a verdict on the input: unsatisfiable carries back under both relations, a model only under the first. An input outside the fragment a translation is defined on gives Inappropriate with the reasons and no output; nothing is translated by best effort. Bind an outcome to a name and the next cell takes it as its input.
Most translations are written in Elixir and need nothing installed. Three run a
tool: Clausify runs Vampire, SMT-LIB to DIMACS runs z3, and ASP to DIMACS
grounds with the clingo that comes with the package. Vampire and z3 are found
on PATH or set in a Logic Engine Settings cell; cells that need one say so.
Every edge
This table is read from the registry, so it lists what is installed.
label = fn id ->
case Loge.Registry.language(id) do
{:ok, language} -> language.label()
:error -> Atom.to_string(id)
end
end
Loge.Registry.translations()
|> Enum.map(fn edge ->
%{
"from" => label.(edge.from),
"to" => label.(edge.to),
"engine" => edge.engine.label(),
"preserves" => Loge.Status.name(edge.preserves),
"module" => inspect(edge.engine)
}
end)
|> Kino.DataTable.new(name: "Translations", keys: ["from", "to", "engine", "preserves", "module"])
| From | To | Engine | Fragment | Preserves | Needs |
|---|---|---|---|---|---|
| DIMACS CNF | TPTP | Loge.Dimacs.Engines.Tptp |
all | Equivalent | |
| DIMACS CNF | SMT-LIB | Loge.Dimacs.Engines.Smtlib |
all | Equivalent | |
| DIMACS CNF | ASP | Loge.Dimacs.Engines.Asp |
all | Equivalent | |
| WCNF | ASP | Loge.Dimacs.Engines.WcnfAsp |
all | Equivalent | |
| QDIMACS | SMT-LIB | Loge.Dimacs.Engines.QdimacsSmtlib |
all | Equivalent | |
| TPTP | TPTP (CNF) | Loge.Tptp.Engines.Clausify |
FOF, CNF | EquiSatisfiable | Vampire |
| TPTP | TPTP (ground CNF) | Loge.Tptp.Engines.Ground |
CNF without function symbols | EquiSatisfiable | |
| TPTP | TPTP (FOF) | Loge.Tptp.Engines.Fof |
CNF, FOF | Equivalent | |
| TPTP | TPTP (TF0) | Loge.Tptp.Engines.Tff |
FOF, CNF | Equivalent | |
| TPTP | TPTP (TH0) | Loge.Tptp.Engines.Thf |
FOF, CNF, monomorphic TF0 | Equivalent | |
| TPTP | TPTP (FOF) | Loge.Tptp.Engines.Untyped |
monomorphic TF0 without arithmetic | EquiSatisfiable | |
| TPTP | DIMACS CNF | Loge.Tptp.Engines.Dimacs |
ground CNF without equality | EquiSatisfiable | |
| TPTP | SMT-LIB | Loge.Tptp.Engines.Smtlib |
FOF, CNF, monomorphic TF0 | Equivalent | |
| TPTP | Prolog | Loge.Tptp.Engines.Prolog |
Horn CNF without equality | Equivalent | |
| SMT-LIB | TPTP (TF0) | Loge.Smtlib.Engines.Tptp |
Core with uninterpreted sorts and functions | Equivalent | |
| SMT-LIB | DIMACS CNF | Loge.Smtlib.Engines.Dimacs |
propositional and bit-vector | EquiSatisfiable | z3 |
| ASP | DIMACS CNF | Loge.Asp.Engines.Dimacs |
tight programs | EquiSatisfiable | |
| Prolog | TPTP | Loge.Prolog.Engines.Tptp |
definite clauses | Equivalent | |
| Prolog | ASP | Loge.Prolog.Engines.Asp |
Datalog | Equivalent | |
| Prolog | egglog | Loge.Prolog.Engines.Egglog |
Datalog | Equivalent | |
| Turtle | TPTP | Loge.Turtle.Engines.Tptp |
graphs in printable ASCII | EquiSatisfiable | |
| Turtle | Prolog | Loge.Turtle.Engines.Prolog |
all | EquiSatisfiable | |
| Turtle | ASP | Loge.Turtle.Engines.Asp |
all | EquiSatisfiable |
There is no edge into Turtle, SPARQL or ShEx, out of egglog or out of THF, and none for arithmetic. A pair without an engine has no row above.
DIMACS
A formula, bound to cnf: satisfiable.
cnf = Loge.source(:dimacs, "p cnf 3 3\n1 -2 0\n2 3 0\n-1 -3 0\n")
As TPTP clauses. Expected: Equivalent, three cnf statements over p1, p2, p3.
cnf_as_tptp = Loge.run!(Loge.Dimacs.Engines.Tptp, cnf, [])
And back: ground clauses are a SAT problem again. Expected: EquiSatisfiable, then Satisfiable.
cnf_again = Loge.run!(Loge.Tptp.Engines.Dimacs, cnf_as_tptp, [])
Loge.run!(Loge.Dimacs.Engines.Clasp, cnf_again, models: 1, time_limit: 10)
As an answer set program, solved by clingo. Expected: Equivalent, then Satisfiable.
cnf_as_asp = Loge.run!(Loge.Dimacs.Engines.Asp, cnf, [])
Loge.run!(Loge.Asp.Engines.Clingo, cnf_as_asp, time_limit: 10)
As an SMT-LIB script. Expected: Equivalent; z3 on it, if installed, answers Satisfiable.
cnf_as_smtlib = Loge.run!(Loge.Dimacs.Engines.Smtlib, cnf, [])
Loge.run!(Loge.Smtlib.Engines.Z3, cnf_as_smtlib, time_limit: 10)
Weighted MaxSAT as weak constraints. Expected: Equivalent, then clingo finds the optimum of cost 2.
maxsat_as_asp = Loge.run!(Loge.Dimacs.Engines.WcnfAsp, "h 1 2 0\n3 -1 0\n2 -2 0\n", [])
Loge.run!(Loge.Asp.Engines.Clingo, maxsat_as_asp, time_limit: 10)
A quantified Boolean formula, here that x and y can always be made equal, as one quantified assertion. Expected: Equivalent; z3 answers Satisfiable, the formula is true.
qbf_as_smtlib =
Loge.run!(Loge.Dimacs.Engines.QdimacsSmtlib, "p cnf 2 2\na 1 0\ne 2 0\n-1 2 0\n1 -2 0\n", [])
Loge.run!(Loge.Smtlib.Engines.Z3, qbf_as_smtlib, time_limit: 10)
TPTP: from a first-order problem to SAT
A theorem, bound to problem.
problem =
Loge.source(
:tptp,
"fof(mortals, axiom, ![X]: (human(X) => mortal(X))).\nfof(socrates, axiom, human(socrates)).\nfof(someone_dies, conjecture, ?[X]: mortal(X)).\n"
)
Clauses, by Vampire (needs vampire). Expected: EquiSatisfiable; the conjecture is negated.
clauses = Loge.run!(Loge.Tptp.Engines.Clausify, problem, time_limit: 10)
Ground instances over the constants. Expected: EquiSatisfiable.
ground = Loge.run!(Loge.Tptp.Engines.Ground, clauses, [])
Ground atoms as variables. Expected: EquiSatisfiable, the atoms in c lines.
sat = Loge.run!(Loge.Tptp.Engines.Dimacs, ground, [])
Expected: Unsatisfiable, so the conjecture follows.
Loge.run!(Loge.Dimacs.Engines.Clasp, sat, models: 1, time_limit: 10)
The clauses are Horn, so they are a Prolog program too. Expected: Equivalent, then Yes with socrates for the variable, which Vampire has renamed.
clauses_as_prolog = Loge.run!(Loge.Tptp.Engines.Prolog, clauses, [])
Loge.run!(Loge.Prolog.Engines.Swipl, clauses_as_prolog, answers: 1, time_limit: 10)
The problem as an SMT-LIB script, the conjecture negated. Expected: Equivalent; z3 answers Unsatisfiable.
problem_as_smtlib = Loge.run!(Loge.Tptp.Engines.Smtlib, problem, [])
Loge.run!(Loge.Smtlib.Engines.Z3, problem_as_smtlib, time_limit: 10)
TPTP: between the dialects
Clauses as first-order formulas. Expected: Equivalent, each clause under its quantifier.
Loge.run!(Loge.Tptp.Engines.Fof, clauses, [])
Untyped as typed first-order, and as typed higher-order with every symbol declared. Expected: Equivalent twice.
Loge.run!(Loge.Tptp.Engines.Tff, problem, [])
Loge.run!(Loge.Tptp.Engines.Thf, problem, [])
A typed problem, bound to typed.
typed =
Loge.source(
:tptp,
"tff(human_type, type, human: $tType).\ntff(socrates_type, type, socrates: human).\ntff(father_type, type, father: human > human).\ntff(mortal_type, type, mortal: human > $o).\ntff(inherited, axiom, ![X: human]: (mortal(father(X)) => mortal(X))).\ntff(first, axiom, mortal(father(socrates))).\ntff(goal, conjecture, mortal(socrates)).\n"
)
Without its types: each type a guard predicate. Expected: EquiSatisfiable.
guarded = Loge.run!(Loge.Tptp.Engines.Untyped, typed, [])
The typed problem in TH0 and as SMT-LIB with a sort per type. Expected: Equivalent twice; z3 answers Unsatisfiable.
Loge.run!(Loge.Tptp.Engines.Thf, typed, [])
typed_as_smtlib = Loge.run!(Loge.Tptp.Engines.Smtlib, typed, [])
Loge.run!(Loge.Smtlib.Engines.Z3, typed_as_smtlib, time_limit: 10)
SMT-LIB
Uninterpreted sorts and functions as TF0. Expected: Equivalent, a type per sort.
Loge.run!(
Loge.Smtlib.Engines.Tptp,
"(declare-sort S 0)\n(declare-const a S)\n(declare-fun f (S) S)\n(declare-fun p (S) Bool)\n(assert (forall ((x S)) (= (f x) x)))\n(assert (p a))\n(assert (not (p (f (f a)))))\n(check-sat)\n",
[]
)
Bit-vectors as clauses, by z3 (needs z3): is there an x with x + 1 = 0 in two bits? Expected: EquiSatisfiable, then clasp answers Satisfiable.
bits =
Loge.run!(
Loge.Smtlib.Engines.Dimacs,
"(set-logic QF_BV)\n(declare-const x (_ BitVec 2))\n(assert (= (bvadd x #b01) #b00))\n(check-sat)\n",
time_limit: 10
)
Loge.run!(Loge.Dimacs.Engines.Clasp, bits, models: 1, time_limit: 10)
ASP
A tight program, two nodes to colour, completed to SAT. Expected: EquiSatisfiable, then Satisfiable with the two colourings among the models.
colouring =
Loge.run!(
Loge.Asp.Engines.Dimacs,
"node(1..2). edge(1, 2).\n{ red(X) } :- node(X).\ngreen(X) :- node(X), not red(X).\n:- edge(X, Y), red(X), red(Y).\n:- edge(X, Y), green(X), green(Y).\n",
time_limit: 10
)
Loge.run!(Loge.Dimacs.Engines.Clasp, colouring, models: 0, time_limit: 10)
Prolog
Datalog with a left-recursive rule, bound to paths: Prolog's own search does not end on it.
paths =
Loge.source(
:prolog,
"edge(a, b). edge(b, c). edge(c, d).\npath(X, Y) :- path(X, Z), edge(Z, Y).\npath(X, Y) :- edge(X, Y).\n?- path(a, Where).\n"
)
Bottom-up in egglog. Expected: Equivalent; the run prints the three answers and is Success.
paths_as_egglog = Loge.run!(Loge.Prolog.Engines.Egglog, paths, [])
Loge.run!(Loge.Egglog.Engines.Egglog, paths_as_egglog, graph: false)
As an answer set program, the query a constraint. Expected: Equivalent, then Unsatisfiable: the query has an answer.
paths_as_asp = Loge.run!(Loge.Prolog.Engines.Asp, paths, [])
Loge.run!(Loge.Asp.Engines.Clingo, paths_as_asp, time_limit: 10)
As Horn clauses for a prover, the query the negated conjecture. Expected: Equivalent. Grounded and as SAT it is Unsatisfiable.
paths_as_tptp = Loge.run!(Loge.Prolog.Engines.Tptp, paths, [])
paths_ground = Loge.run!(Loge.Tptp.Engines.Ground, paths_as_tptp, [])
paths_sat = Loge.run!(Loge.Tptp.Engines.Dimacs, paths_ground, [])
Loge.run!(Loge.Dimacs.Engines.Clasp, paths_sat, models: 1, time_limit: 10)
Turtle
A graph, bound to graph.
graph =
Loge.source(
:turtle,
"@prefix ex: <http://example.org/> .\n\nex:alice ex:knows ex:bob ;\n ex:name \"Alice\" .\nex:bob ex:knows ex:carol .\n"
)
As facts for Prolog, bound to facts, and a program that includes them by that name. Expected: EquiSatisfiable, then Yes with Who being Bob's IRI.
facts = Loge.run!(Loge.Turtle.Engines.Prolog, graph, [])
Loge.run!(
Loge.Prolog.Engines.Swipl,
":- [facts].\n\n?- triple('http://example.org/alice', 'http://example.org/knows', Who).\n",
answers: 1,
time_limit: 10,
includes: %{"facts" => facts}
)
As facts for ASP and for a prover. Expected: EquiSatisfiable twice.
Loge.run!(Loge.Turtle.Engines.Asp, graph, [])
Loge.run!(Loge.Turtle.Engines.Tptp, graph, [])
Outside a fragment
Clauses with a function symbol have infinitely many ground instances. Expected: Inappropriate, with the statement and the reason; the outcome has no output.
not_ground =
Loge.run!(
Loge.Tptp.Engines.Ground,
"cnf(numbers, axiom, nat(zero)).\ncnf(successor, axiom, nat(s(X)) | ~ nat(X)).\n",
[]
)
A cell that takes such an outcome as its input does not run on nothing: it stops with the same reasons.
try do
Loge.run!(Loge.Tptp.Engines.Dimacs, not_ground, [])
rescue
error in ArgumentError -> Kino.Markdown.new("```\n" <> Exception.message(error) <> "\n```")
end
How the translations are checked
loge_verification runs every edge above on generated inputs and compares what a
solver says about the input with what another says about the output: clasp, clingo,
SWI-Prolog and egglog always, z3 and Vampire when installed. From that directory:
mix test, or mix test --include z3 --include vampire.