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
impl ProofStructure
Sourcepub fn reading(&self) -> Result<Reading<'_>, ShapeError>
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.
Sourcepub fn is_essential(
&self,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), NetError>
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
impl ProofStructure
Sourcepub fn sequentialize(
&self,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Proof, Error>
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
impl ProofStructure
Sourcepub fn new(forest: Forest, criterion: Criterion) -> Result<Self, Error>
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.
Sourcepub fn from_links(
forest: Forest,
criterion: Criterion,
links: &[(VertexId, VertexId)],
) -> Result<Self, Error>
pub fn from_links( forest: Forest, criterion: Criterion, links: &[(VertexId, VertexId)], ) -> Result<Self, Error>
Sourcepub fn with_cuts(
forest: Forest,
criterion: Criterion,
cuts: &[(VertexId, VertexId)],
links: &[(VertexId, VertexId)],
) -> Result<Self, Error>
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.
Sourcepub fn from_proof(
proof: &Proof,
criterion: Criterion,
limits: &Limits,
stop: impl FnMut(Progress) -> bool,
) -> Result<Self, Error>
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::GoalProoffor a proof of a goal other than the sequent.NetError::Rulefor a node a net has no place for: any butax,⊗,⅋, 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::PlacementwithPlacement::Cutfor 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, andMellStructure::from_proofmakes its net.NetError::Refusedwhen 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);Sourcepub fn vertex(&self, o: OccId) -> Option<VertexId>
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.
Sourcepub fn occurrence(&self, v: VertexId) -> Option<OccId>
pub fn occurrence(&self, v: VertexId) -> Option<OccId>
Returns the occurrence a vertex stands for, None for a vertex
outside the structure.
Sourcepub fn vertices(&self) -> impl Iterator<Item = VertexId> + '_
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.
Sourcepub fn cuts(&self) -> &[(VertexId, VertexId)]
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.
Sourcepub fn cut_partner(&self, v: VertexId) -> Option<VertexId>
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.
Sourcepub fn is_cut_free(&self) -> bool
pub fn is_cut_free(&self) -> bool
Returns whether the structure has no cut link.
Sourcepub fn partner(&self, v: VertexId) -> Option<VertexId>
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.
Sourcepub fn is_complete(&self) -> bool
pub fn is_complete(&self) -> bool
Returns whether every literal is linked.
Sourcepub fn unlinked(&self) -> impl Iterator<Item = VertexId>
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.
Sourcepub fn link(&mut self, x: VertexId, y: VertexId) -> Result<(), NetError>
pub fn link(&mut self, x: VertexId, y: VertexId) -> Result<(), NetError>
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).
Sourcepub fn unlink(&mut self) -> Option<(VertexId, VertexId)>
pub fn unlink(&mut self) -> Option<(VertexId, VertexId)>
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.
Sourcepub fn same_component(&self, x: VertexId, y: VertexId) -> bool
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.
Sourcepub fn scratch(&self) -> Scratch
pub fn scratch(&self) -> Scratch
Returns working memory for the tests of the criterion, sized for this structure. One serves any number of calls.
Sourcepub fn is_acyclic(&self, scratch: &mut Scratch) -> bool
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.
Sourcepub fn is_correct(
&self,
stop: impl FnMut(Progress) -> bool,
) -> Result<(), NetError>
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(()));Sourcepub fn is_planar(&self) -> Result<(), NetError>
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
impl ProofStructure
Sourcepub fn written_in(&self, mode: Mode) -> impl Display + '_
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
impl Clone for ProofStructure
Source§impl Debug for ProofStructure
impl Debug for ProofStructure
Source§impl<'a> Deserialize<'a> for ProofStructure
impl<'a> Deserialize<'a> for ProofStructure
Source§fn deserialize<D: Deserializer<'a>>(deserializer: D) -> Result<Self, D::Error>
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
impl Display for ProofStructure
Source§fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult
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.
impl Net for ProofStructure
Source§impl Readable for ProofStructure
impl Readable for ProofStructure
Source§fn read<'de, D: Deserializer<'de>>(
deserializer: D,
limits: &Limits,
) -> Result<Self, D::Error>
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.
Auto Trait Implementations§
impl Forget for ProofStructure
impl Freeze for ProofStructure
impl Move for ProofStructure
impl RefUnwindSafe for ProofStructure
impl Send for ProofStructure
impl Sync for ProofStructure
impl Unpin for ProofStructure
impl UnsafeUnpin for ProofStructure
impl UnwindSafe for ProofStructure
Blanket Implementations§
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> DeserializeOwned for Twhere
T: for<'de> Deserialize<'de>,
impl<T> ErasedDestructor for Twhere
T: 'static,
Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self> ⓘ
fn into_either(self, into_left: bool) -> Either<Self, Self> ⓘ
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 moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self> ⓘ
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self> ⓘ
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 moreSource§impl<T> Pointable for T
impl<T> Pointable for T
Source§impl<U, T> ToOwnedObj<U> for Twhere
U: FromObjRef<T>,
impl<U, T> ToOwnedObj<U> for Twhere
U: FromObjRef<T>,
Source§fn to_owned_obj(&self, data: FontData<'_>) -> U
fn to_owned_obj(&self, data: FontData<'_>) -> U
T, using the provided data to resolve any offsets.