Skip to main content

Sequent

Struct Sequent 

Source
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:

connectiveASCIIUnicodegroups
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, ?Aprefix
negationA^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, top and par are keywords: as whole identifiers they are that constant or connective. forall and exists are 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) and exists 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. A binds 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 ⊸ B is ~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.

keyholds
termsthe arena, each term naming only terms before it
rootsthe root formulas, as indices into terms, in the order written
atomsthe atom names
antecedentshow many of the roots, the first ones, stand left of ⊢; absent when the sides are not known
cutsthe cut formulas (cuts), only when there are some
symbols, fo, bindersthe 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:

termJSON
a unitits 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;
  • antecedents is at most the number of roots;
  • every atom name is an identifier of the text syntax (Error::AtomName otherwise).

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

Source

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

Source

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
§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());
Source

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 |- C is |- ~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 \ B as A -o B (associating to the right) and B / A as B 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

Source

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

pub fn formula(&self, id: TermId) -> Formula<'_>

Returns the formula rooted at id, which must belong to this sequent, as a value that prints it.

§Panics

Printing it panics if id is past the end of the arena, as an id of another sequent can be.

Source§

impl Sequent

Source

pub const fn new() -> Self

Returns the empty sequent.

Source

pub fn terms(&self) -> &[Term]

Returns the arena: every subformula, each referring only to terms at lower indices.

Source

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.

Source

pub fn roots(&self) -> &[TermId]

Returns the root formulas, in the order they were written.

Source

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).

Source

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.

Source

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.

Source

pub fn atom_names(&self) -> &[String]

Returns the atom names, in the order Atom indexes them.

Source

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.

Source

pub fn atom(&self, name: &str) -> Option<Atom>

Returns the atom called name, if the sequent has one.

Source

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.

Source

pub fn atom_predicate(&self, atom: Atom) -> Option<(Symbol, Args)>

Returns the predicate symbol of atom and its argument list.

Returns None in a propositional sequent, which has no symbol table: there an atom is just its name (atom_name).

§Panics

If atom is past the end of the table, as an atom of another sequent can be.

Source

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.

Source

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.

Source

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.

Source

pub fn fo_terms(&self) -> &[FoTerm]

Returns the first-order terms, in the order FoTermId indexes them, each referring only to terms before it.

Source

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.

Source

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.

Source

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.

Source

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.

Source

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 Clone for Sequent

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 Sequent

Source§

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

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

impl Default for Sequent

Source§

fn default() -> Self

Returns the empty sequent.

Source§

impl<'a> Deserialize<'a> for Sequent

Source§

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

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

Source§

impl Display for Sequent

Source§

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

Writes the sequent one-sided: ⊢ followed by its formulas, separated by commas.

Source§

impl Eq for Sequent

Source§

impl From<Sequent> for CutFormula

Source§

fn from(formula: Sequent) -> Self

Returns the cut formula of a one-sided sequent ⊢ C, written one-sided.

Source§

impl FromStr for Sequent

Source§

fn from_str(s: &str) -> Result<Self, Self::Err>

Parses a sequent as Sequent::parse_within does, within the default Limits.

Source§

type Err = Error

The associated error which can be returned from parsing.
Source§

impl PartialEq for Sequent

Source§

fn eq(&self, other: &Self) -> bool

Equality operator ==. Read more
1.0.0 (const: unstable) · Source§

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=. Read more
Source§

impl Readable for Sequent

Source§

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

Reads a sequent and checks that its arena keeps the invariants. It must unfold to no more occurrences, and its atoms to no more terms, than the limits allow.

Source§

const FORM: &'static str = "sequent"

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

impl Serialize for Sequent

Source§

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

Serializes the sequent as a document: its level, arena, roots and atoms, and where it has them, its first-order tables, binders’ names, sides and cut formulas.

Source§

impl StructuralPartialEq for Sequent

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<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

Source§

fn equivalent(&self, key: &K) -> bool

Checks if this value is equivalent to the given key. Read more
Source§

impl<Q, K> Equivalent<K> for Q
where Q: Eq + ?Sized, K: Borrow<Q> + ?Sized,

Source§

fn equivalent(&self, key: &K) -> bool

Compare self to key and return true if they are equal.
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.