Skip to main content

Crate deduxit

Crate deduxit 

Source
Expand description

dēdūxit [deːˈduːk.sɪt] Latin, verb: "it has derived", the perfect of dēdūcō, to lead down, derive.

A collection of logic suites: decides sequents of linear logic, and of classical, intuitionistic and minimal propositional logic. Every proof it returns has passed the crate’s checker, unless the caller turns the check off, and every Kripke countermodel its own check. A proof prints as a derivation, or exports to LaTeX, Typst, SVG, PNG, PDF or Rocq.

use deduxit::linear::{Mode, Options, Sequent, Verdict, prove};

let sequent: Sequent = "A, A -o B |- B".parse()?;
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default())?;
match &outcome.verdict {
    Verdict::Proved(proof) => println!("provable\n{}", proof.derivation()?),
    Verdict::Unprovable(disproof) => println!("unprovable: {disproof}"),
    Verdict::Unknown(reason) => println!("unknown: {reason}"),
}

{disproof} prints why the sequent is unprovable, in the words of the deduxit command; {:?} would print the whole data. The examples below also use serde_json.

This is the library of deduxit. A guide to the library and the command for AI models is served beside this documentation: its summary as llms.txt and its full reference as llms-full.txt.

§What you can do

  • Decide a sequent: linear::prove, as above. A Mode is the rules a logic allows: classical or intuitionistic, with weakening (affine) or Mix, commutative or ordered.
  • Read intuitionistic input: parse it as an IllSequent (below).
  • Bound a search’s time, memory and work: linear::prove_within with Limits and a stop (below).
  • Get the answer the command gives: Settings::stop (below).
  • Check a proof, made here or read from a file: Proof::check.
  • Print or export a derivation: Proof::derivation and the formats under export.
  • Work with proof nets: ProofStructure.
  • Prove step by step: linear::Interactive (feature interactive).
  • Decide classical, intuitionistic or minimal propositional logic, with a Kripke countermodel (kripke::Model) for what is not valid: ordinary.
  • Translate a classical sequent into intuitionistic or minimal logic, or find a Craig interpolant, each checked: ordinary::negative and ordinary::interpolant.
  • Read a proof as a lambda-term: lambda.
  • Check, build and draw a derivation in a calculus you give as a rule file, natural deduction among the built-in ones, as a tree or as a Fitch proof: rules (feature serialize).
  • List what each suite makes and does, and run it over JSON: protocol (feature protocol).
  • Keep sequents and what was made from them, with undo and redo: workspace (feature protocol).

Proofs, nets and errors name the occurrences of a sequent: an occurrence is one place of a subformula in the sequent, and the sequent’s Forest numbers them.

§A proof, its fragment and its JSON

Parse a sequent, see which fragment of linear logic it lives in, prove it, print the derivation, then write the proof as JSON, read it back and check it:

use deduxit::linear::{Fragment, Mode, Options, Sequent, Verdict, prove};

// Two-sided input becomes one-sided: ⊢ ~A, A ⊗ ~B, B.
let sequent: Sequent = "A, A -o B |- B".parse()?;
assert_eq!(sequent.fragment(), Fragment::MLL);

let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default())?;
let Verdict::Proved(proof) = &outcome.verdict else {
    panic!("the sequent is provable");
};
assert_eq!(
    proof.derivation()?.to_string(),
    "─────── ax   ─────── ax\n\
     ⊢ ~A, A      ⊢ ~B, B\n\
     ──────────────────── ⊗\n\
    \x20 ⊢ ~A, A ⊗ ~B, B"
);

let json = serde_json::to_string(&proof)?;
let back: deduxit::linear::Proof = serde_json::from_str(&json)?;
back.check(Mode::CLASSICAL)?;

§Intuitionistic input

An IllSequent reads a sequent of intuitionistic linear logic as it is written, with its hypotheses left of ⊢. Its errors are in that logic’s terms: par is refused with a hint to write A -o B. A Sequent parsed from the same text and proved in an intuitionistic mode would report a subformula instead.

use deduxit::linear::{IllSequent, Mode, Options, Verdict, prove};

let ill: IllSequent = "A -o B, B -o C |- A -o C".parse()?;
let outcome = prove(ill.sequent(), Mode::INTUITIONISTIC, &Options::default())?;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));

let Err(error) = "A par B |- B".parse::<IllSequent>() else {
    panic!("par is not intuitionistic");
};
assert!(error.to_string().contains("write ~A par B as A -o B"));

§Limits and stops

Options are a search’s settings, with their defaults. Limits are the resources a call may use. The crate reads no clock, so a long call takes a stop: a closure that the call asks from time to time and that ends the call when it returns true. The call tells it the Progress made. |_| false never stops. The limits module lists every long call with its bounds and how often it asks its stop.

Where there is no clock, as in a browser, a stop can count the work done:

use deduxit::{Limits, linear::{Fragment, Mode, Options, Verdict, prove_within}};

let mode = Mode::CLASSICAL.with_mix();
let options = Options::default().with_fragment(Some(Fragment::MALL));
let limits = Limits::default().with_memory_bytes(Some(64 << 20));
let mut budget: u64 = 10_000_000;
let sequent = "|- A par B, ~A, ~B".parse()?;
let outcome = prove_within(&sequent, mode, &options, &limits, |progress| {
    budget = budget.saturating_sub(progress.work);
    budget == 0
})?;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));
assert_eq!(outcome.fragment, Fragment::MALL);

§The command’s answers

Options::default() bounds the copies of a ? formula at three per branch, so that a call without a stop ends. The deduxit command has a clock instead. It searches without a copy bound until its time limit of two seconds, and after a tenth of a second it adds a pool of the machine’s other threads. So the two can answer differently.

Settings::default() holds the command’s settings. To decide what the command decides, search with its search options and the stop that Settings::stop makes from its clock. That stop fires at the time limit but lets the refutation after the search run, as the command does. Settings::deterministic keeps the search on one thread, as the command’s --deterministic does:

use deduxit::{Settings, linear::{Mode, Verdict, prove_within}};
use std::time::Instant;

let settings = Settings::default().deterministic();
let start = Instant::now();
let sequent = "!A |- !A * !A".parse()?;
let stop = settings.stop(|| start.elapsed());
let outcome = prove_within(&sequent, Mode::CLASSICAL, &settings.search, &settings.limits, stop)?;
assert!(matches!(outcome.verdict, Verdict::Proved(_)));

§What each suite offers, over JSON

protocol lists each suite’s kinds of values and the operations between them, and runs an operation on JSON values. Here a classical sequent is translated into intuitionistic logic, and the translation’s promise, that both are valid together or not, is checked:

use deduxit::{Settings, protocol};

let settings = Settings::default().deterministic();
let sequent = r#"{"version": 8, "formulas": [{"V": 0}, {"¬": 0}, {"∨": [0, 1]}],
    "atoms": ["a"], "left": [], "right": [2], "logic": "classical"}"#;
let glivenko = r#"{"translation": "glivenko"}"#;
let translated =
    protocol::run("ordinary.translate", &[sequent], glivenko, &settings, |_| false)?;
let text = protocol::summary("ordinary.sequent", &translated.value, &settings.limits)?;
assert_eq!(text, "⊢ ¬¬(a ∨ ¬a)");
let check = protocol::check(
    "ordinary.translate", &[sequent], glivenko, &translated.value, &settings, |_| false,
)?;
assert_eq!(check.status, protocol::Status::Held);

§Errors

Every call that can fail returns an Error, or a more specific error that converts into one without loss:

  • a CheckError when a proof fails the checker (Invalid) or its check was refused (Refused);
  • a NetError for a proof structure;
  • a ShapeError for a sequent with no intuitionistic reading;
  • a ParseError for text that is no sequent.

Error::kind says what sort of failure it is. A call that a bound or the stop ended is a refusal (ErrorKind::is_refusal, with the Refusal), never a fault of its input. Error::code is a stable name that a program can branch on.

Messages name occurrences by number. describe, given the forest or other value that the numbers belong to (an Owner), prints them as formulas (Described).

§Syntax and JSON

Sequent says how a sequent is written: the text that "…".parse::<Sequent>() reads and its Display writes, and its JSON. The JSON forms are the interchange format of the command, of front ends and of files. Those of Proof, Outcome, ProofStructure and Interactive are described on those types. ordinary::Sequent says how a sequent of ordinary logic is written.

§Features

On by default:

  • parse: the text syntaxes, the LLTP reader linear::lltp, the reader of coverability problems linear::mist, the generated linear::families and the TPTP reader ordinary::read_tptp;
  • serialize: the JSON forms, through serde;
  • interactive: Interactive, proving step by step;
  • latex, typst, svg and rocq: the exports under export;
  • sat: the SAT solver batsat, with which ordinary::sat decides classical, intuitionistic and minimal logic;
  • protocol: protocol, what each suite offers as data, run over JSON with serde_json, and workspace, values linked by its operations (it needs serialize, parse and interactive).

Off by default:

  • parallel: the search on a pool of Options::jobs threads, and a pool kept across searches, linear::search::Pool; never for WebAssembly;
  • png and pdf: the SVG drawings rendered.

An item that needs a feature says so. Every feature but parallel builds for wasm32-unknown-unknown: without parallel the crate starts no thread, it never reads a clock, and it takes its time limits as a caller’s stop. No feature is removed within a 0.y version.

§Stability

The API follows semantic versioning as Cargo reads it below 1.0: a breaking change raises the second number.

Every public enum, and every struct with public fields that may grow, is #[non_exhaustive]. The enums of the calculus are closed on purpose, so that a match over them stops compiling when the calculus grows: Term, Kind, Node, Rule, Verdict, Branch, Sign, linear::occurrences::Polarity, Side, those of ordinary’s derivations, a lambda-term’s nodes and types, and Visit, the stops of a walk.

The JSON forms are promised by their wire level (the module wire, feature serialize), not by the crate’s version. Display text, the defaults’ numbers and the engines’ counters are not promised. The repository’s changelog lists what each release changed.

Re-exports§

pub use limits::Limits;
pub use limits::Phase;
pub use limits::Progress;
pub use limits::Refusal;
pub use settings::Clock;
pub use settings::Settings;

Modules§

export
Writes sequents and proofs as LaTeX, Typst, SVG, PNG, PDF and Rocq.
kripke
Finite Kripke models, the countermodels of the suites: worlds, an order on them, and the atoms each world forces.
lambda
A proof as a program: an intuitionistic proof read back as a lambda-term.
limits
The resources a call may use, what a long call tells its stop, and why a call was refused without an answer.
linear
The linear suite: sequents of classical and intuitionistic linear logic, their fragments and modes, the occurrence forest, proofs and their checker, proof nets, and the search that decides a sequent and returns a checked proof or a refutation. The items a caller starts from are re-exported here.
ordinary
Ordinary propositional logic: classical, intuitionistic and minimal.
protocol
What each suite offers, as data: the kinds of artifacts it makes, the operations from artifacts to artifacts with their parameters, the settings each operation reads and what it promises of its output, and the functions that read, summarize, run and check them over JSON. A front end lists the operations a value takes, runs one, and shows its check beside the result, without code of its own per suite. Needs the cargo feature protocol (on by default).
rules
Calculi given as data: a rule file, a derivation whose nodes name its rules, and a checker that says whether the derivation is one of that calculus. Needs the cargo feature serialize (on by default), since a calculus enters as a document.
settings
What a front end holds: every value that configures a call, in one Settings. With the feature serialize it reads and writes JSON. Its Clock holds the time limits, which the front end applies through its stop: the library reads no clock.
wire
The wire forms: how a value crosses a process boundary, as JSON or any format serde writes, and the rule that keeps a stored document readable by later releases. Needs the cargo feature serialize (on by default).
workspace
A workspace of linked values: a sequent, its translation, the translation’s proof, a countermodel, a drawing, each a node, and how each was made from the others. Change a value upstream, and what was made from it shows as out of date until it is made again; undo and redo take whole edits back. Needs the cargo feature protocol (on by default): the kinds of values and the operations between them are the suites’ (protocol).

Structs§

Described
An error displayed with formulas in place of occurrence numbers, read from the value that owns the occurrences. describe on Error, CheckError, NetError and ShapeError returns it. Nodes and inferences keep their numbers.
ParseError
Where and why parsing failed: the place as a byte range, as a range of UTF-16 code units and as a line and a character, what was found there and what could have stood there. It owns its data, so it outlives the input.

Enums§

Error
Everything that can go wrong in a call of this crate.
ErrorKind
What sort of failure an Error is.

Traits§

Owner
A value that owns the occurrences an error names: a forest, or a value built on one. Described prints their formulas from it.