#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
#![deny(clippy::wildcard_enum_match_arm)]
pub(crate) mod linear;
pub(crate) mod print;
pub(crate) mod simple;
#[cfg(all(test, feature = "parse"))]
mod tests;
use crate::hash::HashMap;
use crate::limits::Refusal;
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize), serde(transparent))]
pub struct TermId(u32);
impl TermId {
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize), serde(transparent))]
pub struct VarId(u32);
impl VarId {
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize), serde(transparent))]
pub struct TypeId(u32);
impl TypeId {
pub const fn index(self) -> usize {
self.0 as usize
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "lowercase"))]
pub enum Calculus {
Linear,
Affine,
Simple,
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
#[cfg_attr(feature = "serialize", serde(tag = "kind", rename_all = "snake_case"))]
pub enum Type {
Atom {
atom: u32,
},
One,
Top,
Zero,
Tensor {
left: TypeId,
right: TypeId,
},
With {
left: TypeId,
right: TypeId,
},
Plus {
left: TypeId,
right: TypeId,
},
Lollipop {
from: TypeId,
to: TypeId,
},
Bang {
of: TypeId,
},
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
pub struct Variable {
#[cfg_attr(feature = "serialize", serde(rename = "type"))]
ty: TypeId,
letter: char,
index: u32,
}
impl Variable {
pub const fn ty(&self) -> TypeId {
self.ty
}
pub const fn letter(&self) -> char {
self.letter
}
pub const fn index(&self) -> u32 {
self.index
}
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
#[cfg_attr(feature = "serialize", serde(tag = "kind", rename_all = "snake_case"))]
pub enum Node {
Var {
variable: VarId,
},
Lambda {
variable: VarId,
body: TermId,
},
Apply {
function: TermId,
argument: TermId,
},
Tensor {
left: TermId,
right: TermId,
},
LetTensor {
term: TermId,
left: VarId,
right: VarId,
body: TermId,
},
Unit,
LetUnit {
term: TermId,
body: TermId,
},
Pair {
left: TermId,
right: TermId,
},
First {
term: TermId,
},
Second {
term: TermId,
},
Left {
term: TermId,
sum: TypeId,
},
Right {
term: TermId,
sum: TypeId,
},
Case {
term: TermId,
left: VarId,
left_body: TermId,
right: VarId,
right_body: TermId,
},
True {
context: Box<[TermId]>,
},
False {
context: Box<[TermId]>,
term: TermId,
goal: TypeId,
},
Promote {
terms: Box<[TermId]>,
variables: Box<[VarId]>,
body: TermId,
},
Derelict {
term: TermId,
},
Discard {
term: TermId,
body: TermId,
},
Copy {
term: TermId,
left: VarId,
right: VarId,
body: TermId,
},
}
#[derive(Clone, Debug, PartialEq, Eq)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
pub struct Term {
calculus: Calculus,
atoms: Vec<Box<str>>,
types: Vec<Type>,
variables: Vec<Variable>,
context: Vec<VarId>,
goal: TypeId,
nodes: Vec<Node>,
root: TermId,
}
impl Term {
pub const fn calculus(&self) -> Calculus {
self.calculus
}
pub fn atoms(&self) -> &[Box<str>] {
&self.atoms
}
pub fn types(&self) -> &[Type] {
&self.types
}
pub fn variables(&self) -> &[Variable] {
&self.variables
}
pub fn context(&self) -> &[VarId] {
&self.context
}
pub const fn goal(&self) -> TypeId {
self.goal
}
pub fn nodes(&self) -> &[Node] {
&self.nodes
}
pub fn node(&self, id: TermId) -> &Node {
&self.nodes[id.index()]
}
pub const fn root(&self) -> TermId {
self.root
}
}
#[cfg_attr(feature = "parse", doc = "```")]
#[cfg_attr(not(feature = "parse"), doc = "```ignore")]
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(default, deny_unknown_fields))]
pub struct Options {
pub notation: Notation,
pub types: bool,
}
impl Options {
pub const DEFAULT_NOTATION: Notation = Notation::Unicode;
pub const DEFAULT_TYPES: bool = false;
#[must_use]
pub const fn with_notation(self, notation: Notation) -> Self {
Self { notation, ..self }
}
#[must_use]
pub const fn with_types(self, types: bool) -> Self {
Self { types, ..self }
}
}
impl Default for Options {
fn default() -> Self {
Self {
notation: Self::DEFAULT_NOTATION,
types: Self::DEFAULT_TYPES,
}
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize, serde::Deserialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "lowercase"))]
pub enum Notation {
#[default]
Unicode,
Ascii,
}
impl Notation {
pub const ALL: &'static [Self] = &[Self::Unicode, Self::Ascii];
pub const NAMES: &'static [&'static str] = &["unicode", "ascii"];
pub const fn name(self) -> &'static str {
match self {
Self::Unicode => "unicode",
Self::Ascii => "ascii",
}
}
}
impl std::str::FromStr for Notation {
type Err = crate::Error;
fn from_str(s: &str) -> Result<Self, Self::Err> {
Self::ALL
.iter()
.copied()
.find(|n| n.name() == s)
.ok_or_else(|| crate::Error::UnknownName {
what: "term notation",
name: s.into(),
known: Self::NAMES,
})
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
#[cfg_attr(feature = "serialize", derive(serde::Serialize))]
#[cfg_attr(feature = "serialize", serde(rename_all = "snake_case"))]
pub enum NoTerm {
Classical,
Mix,
Ordered,
Quantified,
Open,
Calculus,
}
impl std::fmt::Display for NoTerm {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
f.write_str(match self {
Self::Classical => {
"a proof of classical logic may have several conclusions, which no lambda-term types; a term needs an intuitionistic proof"
}
Self::Mix => "Mix has no lambda-term",
Self::Ordered => {
"the cyclic and the Lambek calculus have the terms of an ordered calculus, not these"
}
Self::Quantified => {
"quantifiers over first-order terms are not quantifiers over types"
}
Self::Open => "the proof has open goals",
Self::Calculus => "the rules of a calculus given as data have no lambda-terms",
})
}
}
#[derive(Debug)]
struct Builder {
atoms: Vec<Box<str>>,
atom_ids: HashMap<Box<str>, u32>,
types: Vec<Type>,
type_ids: HashMap<Type, TypeId>,
variables: Vec<Variable>,
named: [u32; 2],
nodes: Vec<Node>,
}
const LETTERS: [&[char]; 2] = [&['f', 'g', 'h'], &['x', 'y', 'z', 'u', 'v', 'w']];
impl Builder {
fn new() -> Self {
Self {
atoms: Vec::new(),
atom_ids: HashMap::default(),
types: Vec::new(),
type_ids: HashMap::default(),
variables: Vec::new(),
named: [0; 2],
nodes: Vec::new(),
}
}
fn atom(&mut self, name: &str) -> u32 {
if let Some(&id) = self.atom_ids.get(name) {
return id;
}
let id = self.atoms.len() as u32;
self.atoms.push(name.into());
self.atom_ids.insert(name.into(), id);
id
}
fn ty(&mut self, ty: Type) -> TypeId {
if let Some(&id) = self.type_ids.get(&ty) {
return id;
}
let id = TypeId(self.types.len() as u32);
self.types.push(ty);
self.type_ids.insert(ty, id);
id
}
fn variable(&mut self, ty: TypeId) -> (VarId, TermId) {
let class = usize::from(!matches!(self.types[ty.index()], Type::Lollipop { .. }));
let letters = LETTERS[class];
let n = self.named[class];
self.named[class] = n.saturating_add(1);
let letters_len = letters.len() as u32;
let id = VarId(self.variables.len() as u32);
self.variables.push(Variable {
ty,
letter: letters[(n % letters_len) as usize],
index: n / letters_len,
});
(id, self.node(Node::Var { variable: id }))
}
fn node(&mut self, node: Node) -> TermId {
let id = TermId(self.nodes.len() as u32);
self.nodes.push(node);
id
}
fn finish(self, calculus: Calculus, context: Vec<VarId>, goal: TypeId, root: TermId) -> Term {
let mut reached = vec![false; self.nodes.len()];
reached[root.index()] = true;
for i in (0..self.nodes.len()).rev() {
if reached[i] {
operands(&self.nodes[i], |t| reached[t.index()] = true);
}
}
let mut renumbered = vec![TermId(0); self.nodes.len()];
let mut nodes = Vec::with_capacity(reached.iter().filter(|&&r| r).count());
for (i, mut node) in self.nodes.into_iter().enumerate() {
if reached[i] {
renumber(&mut node, |t| renumbered[t.index()]);
renumbered[i] = TermId(nodes.len() as u32);
nodes.push(node);
}
}
Term {
calculus,
atoms: self.atoms,
types: self.types,
variables: self.variables,
context,
goal,
root: renumbered[root.index()],
nodes,
}
}
}
pub(crate) fn operands(node: &Node, mut f: impl FnMut(TermId)) {
match node {
Node::Var { .. } | Node::Unit => {}
Node::Lambda { body, .. } => f(*body),
Node::Apply { function, argument } => {
f(*function);
f(*argument);
}
Node::Tensor { left, right } | Node::Pair { left, right } => {
f(*left);
f(*right);
}
Node::LetTensor { term, body, .. }
| Node::LetUnit { term, body }
| Node::Discard { term, body }
| Node::Copy { term, body, .. } => {
f(*term);
f(*body);
}
Node::First { term }
| Node::Second { term }
| Node::Left { term, .. }
| Node::Right { term, .. }
| Node::Derelict { term } => f(*term),
Node::Case {
term,
left_body,
right_body,
..
} => {
f(*term);
f(*left_body);
f(*right_body);
}
Node::True { context } => context.iter().copied().for_each(f),
Node::False { context, term, .. } => {
context.iter().copied().for_each(&mut f);
f(*term);
}
Node::Promote { terms, body, .. } => {
terms.iter().copied().for_each(&mut f);
f(*body);
}
}
}
fn renumber(node: &mut Node, f: impl Fn(TermId) -> TermId) {
match node {
Node::Var { .. } | Node::Unit => {}
Node::Lambda { body, .. } => *body = f(*body),
Node::Apply { function, argument } => {
*function = f(*function);
*argument = f(*argument);
}
Node::Tensor { left, right } | Node::Pair { left, right } => {
*left = f(*left);
*right = f(*right);
}
Node::LetTensor { term, body, .. }
| Node::LetUnit { term, body }
| Node::Discard { term, body }
| Node::Copy { term, body, .. } => {
*term = f(*term);
*body = f(*body);
}
Node::First { term }
| Node::Second { term }
| Node::Left { term, .. }
| Node::Right { term, .. }
| Node::Derelict { term } => *term = f(*term),
Node::Case {
term,
left_body,
right_body,
..
} => {
*term = f(*term);
*left_body = f(*left_body);
*right_body = f(*right_body);
}
Node::True { context } => context.iter_mut().for_each(|t| *t = f(*t)),
Node::False { context, term, .. } => {
context.iter_mut().for_each(|t| *t = f(*t));
*term = f(*term);
}
Node::Promote { terms, body, .. } => {
terms.iter_mut().for_each(|t| *t = f(*t));
*body = f(*body);
}
}
}
const fn stopped() -> crate::Error {
crate::Error::Refused(Refusal::Stopped {
phase: crate::limits::Phase::ReadBack,
})
}