pub struct Sequent { /* private fields */ }Expand description
A sequent of linear logic: its formulas, kept one-sided and in negation normal form, over an arena of shared subterms.
Read a sequent from text with parse (feature parse) or from JSON
(feature serialize). Display writes it one-sided: A |- A prints
as ⊢ ~A, A.
§Text syntax
A sequent is written formulas ⊢ formulas, or with |- for ⊢.
Each side is a list of formulas separated by commas, and may be
empty. Whitespace may stand between any two tokens. Text that is no
sequent gives Error::Parse, whose ParseError says where it went
wrong.
The connectives, from the loosest to the tightest:
| connective | ASCII | Unicode | groups |
|---|---|---|---|
| linear implication | -o | ⊸ | to the right |
| plus | + | ⊕ | to the left |
| with | & | & | to the left |
| par | | or par | ⅋ | to the left |
| tensor | * | ⊗ | to the left |
| negation, of course, why not | ~A, !A, ?A | prefix | |
| negation | A^ | postfix |
The constants are 0, 1, bot (⊥) and top (⊤). Parentheses
group.
An atom is named by a Unicode identifier: _ or a character of
XID_Start, then characters of XID_Continue.
- A name is read in NFC, so one name is one atom however its accents are encoded.
bot,topandparare keywords: as whole identifiers they are that constant or connective.forallandexistsare the quantifiers’ keywords. No keyword names an atom.- Every atom name of a sequent is such an identifier, however the sequent was read, so a sequent written as text reads back as itself.
parse_ordered also reads the two divisions of
the Lambek calculus, A \ B (groups to the right) and B / A
(groups to the left). They bind as loosely as -o. Mixed, a division
takes everything to its right: A \ B / C is A \ (B / C), and
A / B \ C is A / (B \ C).
§First-order syntax
forall x. A(∀x. A) andexists x. A(∃x. A) bind loosest. Their scope runs right as far as it can: to a), a,, the turnstile or the end.forall x y. Abinds both variables.- An atom may be a predicate applied to terms:
p(x, f(a)). In a term, an identifier that an enclosing quantifier binds is that variable. Any other identifier is a constant, or a function symbol when a(follows it. - A symbol has one arity in the whole sequent. A name is a predicate or a function symbol, never both. No keyword names a symbol or a variable.
- Every formula is closed: each variable is bound by a quantifier.
How the sequent stores them:
- A quantifier’s variable is bound by index in the arena
(
Term::Forall); its name is kept for printing (binder_name). Two quantifiers that differ only in their variable’s name are one term. - An atom with arguments is named by its text,
p(f(a), b). An atom under a quantifier is named by its text with the bound variables as indices,p(#0)(atom_name). - The symbols and the terms are the sequent’s tables
(
symbols,fo_terms,atom_predicate). A propositional sequent has them empty.
§The one-sided form
- The formulas left of the turnstile are negated.
A ⊸ Bis~A ⅋ B.- Negations are pushed down to the atoms.
So A |- A is ⊢ ~A, A, which is what Display writes.
The formulas keep the order they were written in. The sequent also
remembers how many stood left of the turnstile
(antecedents). From that,
Reading reads an intuitionistic sequent
back two-sided. Display leaves the sides out, so its text reads back
as ⊢ Γ. The reading’s text and the JSON keep the sides.
§JSON
With the feature serialize, a sequent is the object
{"version": 1, "terms": […], "roots": […], "atoms": […], "antecedents": k}.
The version stands only at the top of a document
(wire). The command’s seq json writes this form.
| key | holds |
|---|---|
terms | the arena, each term naming only terms before it |
roots | the root formulas, as indices into terms, in the order written |
atoms | the atom names |
antecedents | how many of the roots, the first ones, stand left of ⊢; absent when the sides are not known |
cuts | the cut formulas (cuts), only when there are some |
symbols, fo, binders | the first-order tables, only for a first-order sequent |
antecedents is written whenever the sides are known, 0 included.
A term of terms is one of these, k and l indices into terms
and a an index into atoms:
| term | JSON |
|---|---|
| a unit | its symbol: "1", "⊥", "⊤" or "0" |
| an atom, its dual | {"V": a}, {"D": a} |
| a binary connective | {"⊗": [k, l]}, and ⅋, &, ⊕ alike |
!A, ?A | {"!": k}, {"?": k} |
∀x. A, ∃x. A | {"∀": k}, {"∃": k}, k the body |
Reading checks that:
- every term names only terms before it;
antecedentsis at most the number of roots;- every atom name is an identifier of the text syntax
(
Error::AtomNameotherwise).
A name that the table repeats is one atom. Reading counts the occurrences against the limits before anything unfolds.
cuts holds the term of each cut formula A; the reader builds its
dual. A document that holds a cut formula is at wire level 6.
A first-order sequent is at wire level 7 and writes:
"symbols": [["p", 1], …], each symbol’s name and arity;"fo": […], its terms, each before the terms that name it:{"B": n}is a bound variable,{"F": [symbol, [terms]]}an application;- every atom as
{"P": [symbol, [terms]]}; "binders": ["x", …], the quantifiers’ variable names in the order of their terms.
A propositional sequent writes none of these keys.
§Examples
use deduxit::linear::Sequent;
let sequent: Sequent = "A, A -o B |- B".parse()?;
assert_eq!(sequent.to_string(), "⊢ ~A, A ⊗ ~B, B");
assert_eq!(sequent.antecedents(), Some(2));
let sequent: Sequent = "A |- A".parse()?;
assert_eq!(
serde_json::to_string(&sequent)?,
r#"{"version":1,"terms":[{"D":0},{"V":0}],"roots":[0,1],"atoms":["A"],"antecedents":1}"#
);Implementations§
Source§impl Sequent
impl Sequent
Sourcepub fn fragment(&self) -> Fragment
pub fn fragment(&self) -> Fragment
Returns the smallest fragment the sequent lives in: the connective classes of the terms that its root and cut formulas reach.
§Examples
use deduxit::linear::{Fragment, Sequent};
let mll: Sequent = "A, A -o B |- B".parse()?;
assert_eq!(mll.fragment(), Fragment::MLL);
assert_eq!(mll.fragment().to_string(), "MLL");
let ll: Sequent = "|- (A & B) * !C".parse()?;
assert!(ll.fragment().has_additives());
assert!(Fragment::LL.contains(ll.fragment()));
assert!(!Fragment::MALL.contains(ll.fragment()));
assert_eq!(ll.fragment().to_string(), "LL");Source§impl Sequent
impl Sequent
Sourcepub fn parse_within(text: &str, limits: &Limits) -> Result<Self, Error>
pub fn parse_within(text: &str, limits: &Limits) -> Result<Self, Error>
Parses a sequent such as A, B |- A * B into its one-sided form,
within limits.
The text is refused at the first term past limits.occurrences,
before anything of that size is built. Formulas may nest to any
depth.
Needs the cargo feature parse (on by default).
§Errors
Error::Parsefor text that is no sequent;Refusal::Occurrencespastlimits.occurrences;Refusal::Indexfor more terms than a forest can index, whatever the bound;Refusal::Termswhen the atoms’ arguments unfold to more thanlimits.termsterms.
§Examples
use deduxit::{Limits, linear::Sequent};
let sequent = Sequent::parse_within("A, A -o B |- B", &Limits::default())?;
assert_eq!(sequent.to_string(), "⊢ ~A, A ⊗ ~B, B");
// The text has five terms, more than this bound allows.
let small = Limits::default().with_occurrences(Some(3));
assert!(Sequent::parse_within("A, A -o B |- B", &small).is_err());Sourcepub fn parse_ordered(
text: &str,
order: Order,
limits: &Limits,
) -> Result<Self, Error>
pub fn parse_ordered( text: &str, order: Order, limits: &Limits, ) -> Result<Self, Error>
Parses a sequent as parse_within does, for
a calculus that keeps the order order.
In Order::Cyclic:
- the dual of a product reverses it:
~(A * B)reads as~B par ~A; - the formulas left of the turnstile come in reverse order, each
negated:
A, B |- Cis|- ~B, ~A, C, the cyclic sequent with the same proofs as the two-sided one; - the two divisions of the Lambek calculus are read:
A \ BasA -o B(associating to the right) andB / AasB par ~A(to the left), both binding as loosely as-o.
The formulas then stand in the order the cyclic calculus reads,
which is the occurrence forest’s. In Order::Commutative this is
parse_within.
Needs the cargo feature parse (on by default).
§Errors
Those of parse_within.
§Examples
use deduxit::{Limits, linear::{Order, Sequent}};
let cyclic = Sequent::parse_ordered("a * b |- a * b", Order::Cyclic, &Limits::default())?;
assert_eq!(cyclic.to_string(), "⊢ ~b ⅋ ~a, a ⊗ b");
let commutative: Sequent = "a * b |- a * b".parse()?;
assert_eq!(commutative.to_string(), "⊢ ~a ⅋ ~b, a ⊗ b");Source§impl Sequent
impl Sequent
Sourcepub fn walk(&self, id: TermId) -> Walk<'_, TermId> ⓘ
pub fn walk(&self, id: TermId) -> Walk<'_, TermId> ⓘ
Returns the walk over the formula rooted at id, which must belong
to this sequent: the stops a printer of the formula in another
syntax follows. Each stop names a term that Sequent::term
returns.
§Examples
use deduxit::linear::sequents::Visit;
use deduxit::linear::{Sequent, Term};
let sequent: Sequent = "⊢ a ⊗ !b".parse().unwrap();
let mut out = String::new();
for visit in sequent.walk(sequent.roots()[0]) {
match visit {
Visit::Enter(id) => match sequent.term(id) {
Term::Atom(a) => out += sequent.atom_name(a),
Term::Tensor(..) => out += "(",
Term::Bang(_) => out += "!",
_ => unreachable!(),
},
Visit::Between(..) => out += " * ",
Visit::Exit(id) if sequent.term(id).kind().arity() == 2 => out += ")",
Visit::Exit(_) => {}
}
}
assert_eq!(out, "(a * !b)");§Panics
The walk panics if id is past the end of the arena, as an id of
another sequent can be.
Source§impl Sequent
impl Sequent
Sourcepub fn terms(&self) -> &[Term]
pub fn terms(&self) -> &[Term]
Returns the arena: every subformula, each referring only to terms at lower indices.
Sourcepub fn term(&self, id: TermId) -> Term
pub fn term(&self, id: TermId) -> Term
Returns the term at id, which must belong to this sequent.
§Panics
If id is past the end of the arena, as an id of another sequent
can be.
Sourcepub fn antecedents(&self) -> Option<u32>
pub fn antecedents(&self) -> Option<u32>
Returns how many root formulas were written left of ⊢.
They are the first ones of roots; the rest stood
right of ⊢. The result is None when the sides are not known: a
JSON sequent without them, or the sum of two sequents
(add). Text always gives them, Some(0) for ⊢ Γ.
Only the intuitionistic reading uses them, to find the goal
(Reading).
Sourcepub fn cuts(&self) -> &[[TermId; 2]]
pub fn cuts(&self) -> &[[TermId; 2]]
Returns the cut formulas, in the order they were added: for each
cut, the term of the formula A and the term of its dual A⊥.
Cut formulas are not part of the conclusion (the
roots). A proof with cuts
(Node::Cut) proves a sequent that
holds its cut formulas, and that sequent’s
Forest numbers each pair after the roots.
A sequent read from text holds none, and Display writes only the
conclusion.
Sourcepub fn add_cut(&mut self, formula: Self) -> Result<(), Error>
pub fn add_cut(&mut self, formula: Self) -> Result<(), Error>
Adds a cut formula A, given as formula, a sequent of one root
formula.
An atom of formula is this sequent’s atom of the same name. A
and its dual A⊥ join the arena, and the pair is numbered after
the roots and the earlier cut formulas. The roots and their sides
do not change.
§Errors
Error::CutFormula when formula
has more or fewer than one root formula, or cut formulas of its
own.
Sourcepub fn atom_names(&self) -> &[String]
pub fn atom_names(&self) -> &[String]
Returns the atom names, in the order Atom indexes them.
Sourcepub fn atom_name(&self, atom: Atom) -> &str
pub fn atom_name(&self, atom: Atom) -> &str
Returns the name of atom, which must belong to this sequent.
§Panics
If atom is past the end of the atom table, as an atom of another
sequent can be.
Sourcepub fn atom(&self, name: &str) -> Option<Atom>
pub fn atom(&self, name: &str) -> Option<Atom>
Returns the atom called name, if the sequent has one.
Sourcepub fn is_first_order(&self) -> bool
pub fn is_first_order(&self) -> bool
Returns whether the sequent is first-order: an atom has arguments or a formula has a quantifier. A propositional sequent has empty first-order tables, and its JSON holds none of their keys.
Sourcepub fn fo_size(&self) -> u64
pub fn fo_size(&self) -> u64
Returns how many first-order terms the atoms’ arguments unfold to
when written out as trees, saturating at u64::MAX.
A term that several atoms or terms share counts once for each
place. This is what Limits::terms bounds.
A propositional sequent gives 0.
Sourcepub fn atom_is_open(&self, atom: Atom) -> bool
pub fn atom_is_open(&self, atom: Atom) -> bool
Returns whether an argument of atom holds a bound variable, which
only an atom under a quantifier can.
A ground atom pairs with its dual as a propositional atom does. An open one is instantiated through the quantifiers above it.
§Panics
If atom is past the end of the table, as an atom of another
sequent can be.
Sourcepub fn symbols(&self) -> &[(String, u32)]
pub fn symbols(&self) -> &[(String, u32)]
Returns the symbols, each a name with its arity, in the order
Symbol indexes them. Empty in a propositional sequent.
Sourcepub fn fo_terms(&self) -> &[FoTerm]
pub fn fo_terms(&self) -> &[FoTerm]
Returns the first-order terms, in the order FoTermId indexes
them, each referring only to terms before it.
Sourcepub fn arguments(&self, args: Args) -> &[FoTermId]
pub fn arguments(&self, args: Args) -> &[FoTermId]
Returns the terms of the argument list args, which must belong
to this sequent.
§Panics
If args is past the end of the table, as a list of another
sequent can be.
Sourcepub fn binder_name(&self, term: TermId) -> Option<&str>
pub fn binder_name(&self, term: TermId) -> Option<&str>
Returns the name of the variable that the quantifier term binds,
for printing, or None where term is no quantifier.
Sourcepub fn occurrences(&self) -> u64
pub fn occurrences(&self) -> u64
Returns the number of subformula occurrences of the sequent: the nodes of its formulas, cut formulas included, written out as trees.
A term that several terms or formulas share counts once for each
place. This is how many occurrences a
Forest of the sequent has. It can be
exponentially more than the arena has terms, and saturates at
u64::MAX. It takes one pass over the arena.
Sourcepub fn optimize(&mut self)
pub fn optimize(&mut self)
Merges atoms of the same name and equal terms, and drops the terms that no root or cut formula reaches.
The root formulas keep the order they were written in. The parser
optimizes what it reads; after add, this merges the
terms the two sequents share.
Sourcepub fn add(&mut self, s: Self)
pub fn add(&mut self, s: Self)
Appends the sequent s to this one: its root formulas after this
one’s, its cut formulas after this one’s, its arena after this one’s.
An atom of s becomes this sequent’s atom of the same name, if
there is one. The sides of the sum are not known, so
antecedents becomes None.
Trait Implementations§
Source§impl<'a> Deserialize<'a> for Sequent
impl<'a> Deserialize<'a> for Sequent
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 sequent within the default limits, as
wire::upgrade does.
impl Eq for Sequent
Source§impl From<Sequent> for CutFormula
impl From<Sequent> for CutFormula
Source§impl Readable for Sequent
impl Readable for Sequent
impl StructuralPartialEq for Sequent
Auto Trait Implementations§
impl Forget for Sequent
impl Freeze for Sequent
impl Move for Sequent
impl RefUnwindSafe for Sequent
impl Send for Sequent
impl Sync for Sequent
impl Unpin for Sequent
impl UnsafeUnpin for Sequent
impl UnwindSafe for Sequent
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>,
Source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
Source§impl<Q, K> Equivalent<K> for Q
impl<Q, K> Equivalent<K> for Q
Source§fn equivalent(&self, key: &K) -> bool
fn equivalent(&self, key: &K) -> bool
key and return true if they are equal.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.