Powered by AppSignal & Oban Pro

Loge: translations

notebooks/translations.livemd

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.