Skip to main content

ProofStructure

Struct ProofStructure 

Source
pub struct ProofStructure { /* private fields */ }
Expand description

A proof structure of unit-free MLL: the formula trees of a sequent plus axiom links between dual literals, checked under a Criterion.

The formula trees are the sequent’s occurrence forest, and vertex i is occurrence i of it (vertex, occurrence). An axiom link joins two literals a and ~a of one atom. A switching keeps one of the two premise edges of every ⅋ vertex and drops the other. The structure is a proof net when every literal is linked and the switchings pass the criterion, which is_correct decides.

Over a sequent with cut formulas, a structure may have cut links (with_cuts). A cut link joins an occurrence of a cut formula’s tree to its dual; it is the cut rule of a proof. The vertices are then the conclusions’ trees and the trees above the cut links’ ends: the ends and their subformulas. The occurrences of the cut formulas’ trees above no cut link’s end are no vertices. For the criterion a cut link is an edge every switching keeps. cut eliminates the cut links.

link adds a link and refuses what is not one. unlink takes back the last link made. So a search can try linkings by backtracking. The structure keeps its ⅋-free skeleton (the premise edges of ⊗ vertices, the cut links and the axiom links) as a union-find. So same_component answers in logarithmic time whether a candidate link would close a cycle that no switching breaks.

§Examples

use deduxit::linear::{Criterion, Forest, ProofStructure, Sequent, VertexId};

// ⊢ ~A, A ⊗ ~B, B, with the vertices 0: ~A, 1: A ⊗ ~B, 2: A,
// 3: ~B, 4: B.
let sequent: Sequent = "A, A -o B |- B".parse()?;
let v = VertexId::new;
let links = [(v(0), v(2)), (v(3), v(4))];
let net = ProofStructure::from_links(Forest::new(&sequent)?, Criterion::MLL, &links)?;
assert!(net.is_complete());
assert_eq!(net.partner(v(2)), Some(v(0)));
assert_eq!(net.is_correct(|_| false), Ok(()));

§JSON

With the feature serialize a structure is {"version": 1, "sequent": …, "mix": …, "links": [[x, y], …]} (wire). sequent is in Sequent’s form. The criterion’s fields follow: whether Mix is allowed, and "order": "cyclic" at level 2 for the cyclic order. The cut links are "cuts": [[x, y], …], at level 6, where the structure has some. links holds the axiom links as pairs of vertex ids, in the order they were made.

Reading validates the cut links and links as with_cuts does. It takes a partial or incorrect structure, since whether it is a net is is_correct’s question.

Implementations§

Source§

impl ProofStructure

Source

pub fn reading(&self) -> Result<Reading<'_>, ShapeError>

Returns the intuitionistic reading of the structure’s sequent: the side of ⊢ every vertex stands on, which orients its essential net.

Under a criterion of the cyclic order it is the ordered reading of the Lambek calculus (Reading::of_mode), with empty antecedents allowed. It is recomputed on each call, in time linear in the forest.

§Errors

The ShapeError of a sequent with no intuitionistic reading.

Source

pub fn is_essential( &self, stop: impl FnMut(Progress) -> bool, ) -> Result<(), NetError>

Decides whether the structure is an essential net of its sequent’s intuitionistic reading, independently of any search and of the proof checker.

An essential net has every literal linked, and its directed graph has no cycle. Every implication in output position (on the goal’s side of ⊢ in the reading) but the goal dominates its antecedent: every path from the antecedent to the goal passes through it. For a structure of an intuitionistic sequent the verdict is that of is_correct without Mix, whatever the structure’s criterion. A structure with cut links has no essential net here: its verdict is that of is_correct without Mix.

The call holds working memory linear in the structure. It takes time linear in it for the cycle and for each implication. It asks stop once after the search for a cycle and once per implication.

§Errors

NetError::Empty, NetError::Unlinked, NetError::NotIntuitionistic for a sequent without a reading, NetError::DirectedCycle or NetError::NoDominator with a witness; NetError::Refused when stop ended it.

§Examples
use deduxit::linear::{Criterion, Forest, ProofStructure, Sequent, VertexId};

// a ⊸ b, a ⊢ b is ⊢ a ⊗ ~b, ~a, b, with the vertices 0: a ⊗ ~b,
// 1: a, 2: ~b, 3: ~a, 4: b.
let sequent: Sequent = "a -o b, a |- b".parse()?;
let v = VertexId::new;
let links = [(v(1), v(3)), (v(2), v(4))];
let net = ProofStructure::from_links(Forest::new(&sequent)?, Criterion::MLL, &links)?;
assert_eq!(net.is_essential(|_| false), Ok(()));
Source§

impl ProofStructure

Source

pub fn sequentialize( &self, limits: &Limits, stop: impl FnMut(Progress) -> bool, ) -> Result<Proof, Error>

Turns a proof net into a proof term of its sequent, which the proof checker accepts.

The proof has ⅋, ⊗ and axiom nodes, a cut for each cut link, and Mix nodes where the structure falls apart. It records the mode it is meant for: classical, with Mix where the criterion allows it, or the cyclic mode under a criterion of the cyclic order.

The call takes time quadratic in the structure at most. It holds within limits.memory_bytes, which it compares with an estimate before it makes anything. It asks stop as is_correct does, and once per stage, each stage a search of the sub-net left.

§Errors

The criterion’s NetError if the structure is not a proof net; NetError::Refused when the bound or the stop ended it.

§Examples
use deduxit::Limits;
use deduxit::linear::{Criterion, Forest, Mode, ProofStructure, Sequent, VertexId};

// ⊢ ~A, A ⊗ ~B, B, with the vertices 0: ~A, 1: A ⊗ ~B, 2: A,
// 3: ~B, 4: B.
let sequent: Sequent = "A, A -o B |- B".parse()?;
let v = VertexId::new;
let links = [(v(0), v(2)), (v(3), v(4))];
let net = ProofStructure::from_links(Forest::new(&sequent)?, Criterion::MLL, &links)?;

// Two axioms and the ⊗.
let limits = Limits::default();
let proof = net.sequentialize(&limits, |_| false)?;
assert_eq!(proof.nodes().len(), 3);
assert_eq!(proof.check(Mode::CLASSICAL), Ok(()));

// The proof's net is the net it came from.
let back = ProofStructure::from_proof(&proof, Criterion::MLL, &limits, |_| false)?;
assert_eq!(back.links(), net.links());
Source§

impl ProofStructure

Source

pub fn new(forest: Forest, criterion: Criterion) -> Result<Self, Error>

Returns the structure over the forest, with no link yet.

Over a forest with cut formulas the structure has no cut link, so the cut formulas’ trees hold none of its vertices. with_cuts makes one with cut links.

§Errors

NetError::Fragment for a sequent outside unit-free MLL, which has no proof nets; NetError::Mode for a criterion of the cyclic order with Mix, which no calculus has; Refusal::Index for a forest of more than 1 431 655 764 occurrences, more vertices than a structure holds.

Returns the structure with the given axiom links, made in the order given.

§Errors

As new does, and the NetError of link for a pair that is no link: a vertex outside the structure, two literals that are not dual, or a literal linked twice.

Source

pub fn with_cuts( forest: Forest, criterion: Criterion, cuts: &[(VertexId, VertexId)], links: &[(VertexId, VertexId)], ) -> Result<Self, Error>

Returns the structure with the given cut links and axiom links.

A cut link joins an occurrence of a cut formula’s tree to its dual (Forest::dual), given in either order. The vertices of the structure are then the conclusions’ trees and the trees above the ends of every cut link. No cut link may lie in the tree above another.

§Errors

As from_links does; NetError::Placement with Placement::Cut for a cut link that does not join an occurrence of a cut formula’s tree to its dual or that lies in the tree above another, with Placement::Uncut for a link to a vertex of a cut formula above no cut link; NetError::Mode for cut links under a criterion of the cyclic order, whose calculus has no cut.

Source

pub fn from_proof( proof: &Proof, criterion: Criterion, limits: &Limits, stop: impl FnMut(Progress) -> bool, ) -> Result<Self, Error>

Returns the proof net of a proof of MLL, the net’s axiom links read off the proof’s Ax nodes and its cut links off its Cut nodes. This is desequentialization, the converse of sequentialize.

The structure is built over a copy of the proof’s forest. Every proof the checker accepts gives a proof net, and two proofs that differ only in the order of their rules give the same one. The checker is not run: the net of a proof the checker would reject can still be a proof net, and is returned as one.

The call holds within limits.memory_bytes: it estimates the structure and the criterion’s working memory before it makes anything. It asks stop once per node and once per round of the criterion, and gives up when stop returns true.

§Errors
  • Error::GoalProof for a proof of a goal other than the sequent.
  • NetError::Rule for a node a net has no place for: any but ax, ⊗, ⅋, Mix and the cut.
  • The errors of from_links, and the criterion’s error if the links are not a proof net. That happens only for a proof the checker rejects, or one that uses Mix where the criterion forbids it.
  • NetError::Placement with Placement::Cut for a proof that cuts one occurrence in two branches, or an occurrence in one branch and a subformula of it in another. Its net needs two vertices of one occurrence. The checker accepts such a proof, and MellStructure::from_proof makes its net.
  • NetError::Refused when the bound or the stop ended the call.
§Examples
use deduxit::Limits;
use deduxit::linear::{Criterion, Mode, Options, ProofStructure, Sequent, prove};

let sequent: Sequent = "A, A -o B |- B".parse()?;
let outcome = prove(&sequent, Mode::CLASSICAL, &Options::default())?;
let proof = outcome.verdict.proof().expect("provable");
let net = ProofStructure::from_proof(proof, Criterion::MLL, &Limits::default(), |_| false)?;
assert!(net.is_complete());
assert_eq!(net.links().len(), 2);
Source

pub fn forest(&self) -> &Forest

Returns the forest of the sequent.

Source

pub fn sequent(&self) -> &Sequent

Returns the sequent.

Source

pub fn criterion(&self) -> Criterion

Returns the rules the structure is checked under.

Source

pub fn vertex(&self, o: OccId) -> Option<VertexId>

Returns the vertex of an occurrence of the forest. None for an id outside it, and for an occurrence of a cut formula’s tree above no cut link’s end.

Source

pub fn occurrence(&self, v: VertexId) -> Option<OccId>

Returns the occurrence a vertex stands for, None for a vertex outside the structure.

Source

pub fn vertices(&self) -> impl Iterator<Item = VertexId> + '_

Returns the vertices, in order: every occurrence of the forest but those of cut formulas’ trees above no cut link’s end.

Source

pub fn cuts(&self) -> &[(VertexId, VertexId)]

Returns the cut links, each from its end in a cut formula’s tree to its dual end, in the order they were given.

Source

pub fn cut_partner(&self, v: VertexId) -> Option<VertexId>

Returns the other end of the cut link at a vertex, None for a vertex at no cut link.

Source

pub fn is_cut_free(&self) -> bool

Returns whether the structure has no cut link.

Source

pub fn partner(&self, v: VertexId) -> Option<VertexId>

Returns the literal a vertex is linked to, or None for an unlinked literal, a connective or a vertex outside the structure.

Returns the links in the order they were made.

Source

pub fn is_complete(&self) -> bool

Returns whether every literal is linked.

Source

pub fn unlinked(&self) -> impl Iterator<Item = VertexId>

Returns the literals without a link, grouped by atom and sign as Forest::all_literals lists them.

Links two unlinked dual literals, in time logarithmic in the structure.

§Errors

Fails, and leaves the structure as it is, if one of the two is no vertex of the structure (NetError::NoVertex), no literal (NetError::NotLiteral) or a literal of a cut formula’s tree above no cut link’s end (NetError::Placement with Placement::Uncut), if they are not dual (NetError::NotDual), or if one has a link already (NetError::LinkedTwice).

Takes back the last link made, in constant time, and returns it. None if there is no link.

Links are undone in the reverse order of their making, as a backtracking search undoes them.

Source

pub fn same_component(&self, x: VertexId, y: VertexId) -> bool

Returns whether two vertices are joined by a path that uses no premise edge of a ⅋: only ⊗ premise edges, cut links and axiom links.

Linking two such literals closes a cycle that every switching keeps. A vertex outside the structure is joined to nothing. It takes time logarithmic in the structure.

Source

pub fn scratch(&self) -> Scratch

Returns working memory for the tests of the criterion, sized for this structure. One serves any number of calls.

Source

pub fn is_acyclic(&self, scratch: &mut Scratch) -> bool

Returns whether no cycle survives any switching.

The answer means the same on a partial structure, since an unlinked literal lies on no cycle. With a scratch from scratch the call allocates nothing. A scratch sized for another structure is replaced by one for this one.

It runs the deletion procedure of Yeo’s theorem on the graph whose edges are the premise edges, the cut links and the axiom links. The two premise edges of a ⅋ share a colour, and every other edge has a colour of its own. A vertex that every part of the graph without it meets in edges of one colour only lies on no switching cycle, and is deleted. When no vertex is left to delete, either nothing remains or what remains carries a switching cycle.

Source

pub fn is_correct( &self, stop: impl FnMut(Progress) -> bool, ) -> Result<(), NetError>

Decides whether the structure is a proof net by the Danos–Regnier criterion, independently of any search and of the proof checker.

A proof net has every literal linked, and no cycle survives any switching. Unless the criterion allows Mix, every switching is also connected. Once no switching has a cycle, connectedness is a count: the edges a switching keeps are one fewer than the vertices. A cut link is an edge every switching keeps, as a ⊗ without a conclusion would be (Girard, Linear logic, 1987). Under a criterion of the cyclic order the links must also be planar (is_planar).

The call holds working memory linear in the structure. It asks stop once per round of the deletion procedure (is_acyclic). The witness of a cycle runs that procedure once per edge.

§Errors

NetError::Empty, NetError::Unlinked, NetError::SwitchingCycle or NetError::Disconnected with a witness; NetError::Crossing under a criterion of the cyclic order; NetError::Refused when stop ended it.

§Examples
use deduxit::linear::{Criterion, Forest, NetError, ProofStructure, Sequent, VertexId};

// ⊢ A ⅋ B, ~A, ~B, with the vertices 0: A ⅋ B, 1: A, 2: B, 3: ~A,
// 4: ~B.
let sequent: Sequent = "|- A par B, ~A, ~B".parse()?;
let forest = Forest::new(&sequent)?;
let v = VertexId::new;
let links = [(v(1), v(3)), (v(2), v(4))];

// Every switching falls into two parts: the one that keeps A
// leaves B and ~B apart.
let net = ProofStructure::from_links(forest.clone(), Criterion::MLL, &links)?;
assert!(matches!(
    net.is_correct(|_| false),
    Err(NetError::Disconnected { .. })
));

// With Mix a proof net need not be connected.
let mix = Criterion::MLL.with_mix();
let net = ProofStructure::from_links(forest, mix, &links)?;
assert_eq!(net.is_correct(|_| false), Ok(()));
Source

pub fn is_planar(&self) -> Result<(), NetError>

Decides whether the links are planar: no two of them cross in the cyclic order of the literals. The answer is independent of any search and of the criterion’s other conditions.

The cyclic order is the order of the occurrence ids: the order the formulas are written in, a formula’s left operand before its right one. Two links cross when their four literals alternate between them going round. That is the same in the cyclic order as in the linear one, whatever the rotation. A partial structure is planar when the links it has are. The test is one pass over the vertices, with a stack of the links whose first literal has been passed and whose second has not. In a planar structure the second literal reached always closes the link on top.

A structure of unit-free MLL is a proof net of cyclic MLL exactly when it is a proof net and planar. Every derivation of the cyclic calculus joins its premises’ planar nets side by side at a ⊗. And every sequentialization of a planar net splits each ⊗ into the two arcs on either side of it, since the parts that removing it leaves are connected and drawn without crossing.

§Errors

NetError::Crossing with two links that cross.

Source§

impl ProofStructure

Source

pub fn written_in(&self, mode: Mode) -> impl Display + '_

Returns the structure for display as mode reads it.

That is what Display writes, except in an intuitionistic mode where the sequent has a reading. There the sequent is two-sided, and every formula is written as the reading writes it (A ⊸ B, A ⊢ B, A[0] — A[2]).

Trait Implementations§

Source§

impl Clone for ProofStructure

Source§

fn clone(&self) -> Self

Returns a duplicate of the value. Read more
1.0.0 (const: unstable) · Source§

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source. Read more
Source§

impl Debug for ProofStructure

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter. Read more
Source§

impl<'a> Deserialize<'a> for ProofStructure

Source§

fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error>

Deserializes a structure within the default limits, as wire::upgrade does.

Source§

impl Display for ProofStructure

Source§

fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult

Writes the sequent, then one line per cut link, in their order, as cut A ⊗ B[5] — ~A ⅋ ~B[8]. Then one line per axiom link as ~A[0] — A[2], each literal with its vertex id, the smaller id first and the links ordered by it. Last comes the verdict of the criterion: proof net (the correctness criterion holds), the same with Mix, a planar proof net in the cyclic order, or not a proof net: and the reason with formulas. No trailing newline.

Source§

impl Net for ProofStructure

Source§

impl Owner for ProofStructure

Source§

fn forest(&self) -> &Forest

The structure’s forest.

Source§

impl Readable for ProofStructure

Source§

fn read<'de, D: Deserializer<'de>>( deserializer: D, limits: &Limits, ) -> Result<Self, D::Error>

Reads a structure. Builds the forest of its sequent within the limits, and validates the cut links and links as ProofStructure::with_cuts does. Whether it is a proof net is for ProofStructure::is_correct to say.

Source§

const FORM: &'static str = "proof structure"

The form’s name, as an error names it: sequent, proof, …
Source§

impl Serialize for ProofStructure

Source§

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serializes the structure as a document: its level, sequent, criterion, cut links and links.

Auto Trait Implementations§

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> CloneToUninit for T
where T: Clone,

Source§

unsafe fn clone_to_uninit(&self, dest: *mut u8)

🔬This is a nightly-only experimental API. (clone_to_uninit)
Performs copy-assignment from self to dest. Read more
Source§

impl<T> DeserializeOwned for T
where T: for<'de> Deserialize<'de>,

Source§

impl<T> ErasedDestructor for T
where T: 'static,

Source§

impl<T> Finish for T

Source§

fn finish(self)

Does nothing but move self, equivalent to drop.
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T> IntoEither for T

Source§

fn into_either(self, into_left: bool) -> Either<Self, Self> ⓘ

Converts self into a Left variant of Either<Self, Self> if into_left is true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

fn into_either_with<F>(self, into_left: F) -> Either<Self, Self> ⓘ
where F: FnOnce(&Self) -> bool,

Converts self into a Left variant of Either<Self, Self> if into_left(&self) returns true. Converts self into a Right variant of Either<Self, Self> otherwise. Read more
Source§

impl<T> Pointable for T

Source§

const ALIGN: usize

The alignment of pointer.
Source§

type Init = T

The type for initializers.
Source§

unsafe fn init(init: <T as Pointable>::Init) -> usize

Initializes a with the given initializer. Read more
Source§

unsafe fn deref<'a>(ptr: usize) -> &'a T

Dereferences the given pointer. Read more
Source§

unsafe fn deref_mut<'a>(ptr: usize) -> &'a mut T

Mutably dereferences the given pointer. Read more
Source§

unsafe fn drop(ptr: usize)

Drops the object pointed to by the given pointer. Read more
Source§

impl<T> ToOwned for T
where T: Clone,

Source§

type Owned = T

The resulting type after obtaining ownership.
Source§

fn to_owned(&self) -> T

Creates owned data from borrowed data, usually by cloning. Read more
Source§

fn clone_into(&self, target: &mut T)

Uses borrowed data to replace owned data, usually by cloning. Read more
Source§

impl<U, T> ToOwnedObj<U> for T
where U: FromObjRef<T>,

Source§

fn to_owned_obj(&self, data: FontData<'_>) -> U

Convert this type into T, using the provided data to resolve any offsets.
Source§

impl<U, T> ToOwnedTable<U> for T
where U: FromTableRef<T>,

Source§

fn to_owned_table(&self) -> U

Source§

impl<T> ToString for T
where T: Display + ?Sized,

Source§

fn to_string(&self) -> String

Converts the given value to a String. Read more
Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = !

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, !>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.