#![cfg_attr(feature = "parse", doc = "```")]
#![cfg_attr(not(feature = "parse"), doc = "```ignore")]
use super::{Formulas, Logic, Node, NodeId, Outcome, Sequent, Verdict, decide_within};
use crate::Error;
use crate::limits::{Limits, Progress};
use crate::linear::search;
use std::fmt::{Display, Formatter, Result as FmtResult};
#[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 = "kebab-case"))]
pub enum Translation {
#[default]
Kolmogorov,
GodelGentzen,
Kuroda,
Glivenko,
}
impl Translation {
pub const ALL: &'static [Self] = &[
Self::Kolmogorov,
Self::GodelGentzen,
Self::Kuroda,
Self::Glivenko,
];
pub const NAMES: &'static [&'static str] =
&["kolmogorov", "godel-gentzen", "kuroda", "glivenko"];
pub const fn name(self) -> &'static str {
match self {
Self::Kolmogorov => "kolmogorov",
Self::GodelGentzen => "godel-gentzen",
Self::Kuroda => "kuroda",
Self::Glivenko => "glivenko",
}
}
pub const fn title(self) -> &'static str {
match self {
Self::Kolmogorov => "Kolmogorov's translation",
Self::GodelGentzen => "Gödel and Gentzen's translation",
Self::Kuroda => "Kuroda's translation",
Self::Glivenko => "Glivenko's translation",
}
}
pub const fn target(self) -> Logic {
match self {
Self::Kolmogorov | Self::GodelGentzen => Logic::Minimal,
Self::Kuroda | Self::Glivenko => Logic::Intuitionistic,
}
}
pub const fn reaches(self, logic: Logic) -> bool {
match logic {
Logic::Classical => false,
Logic::Intuitionistic => true,
Logic::Minimal => matches!(self.target(), Logic::Minimal),
}
}
}
impl Display for Translation {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
f.write_str(self.name())
}
}
impl std::str::FromStr for Translation {
type Err = Error;
fn from_str(name: &str) -> Result<Self, Error> {
Self::ALL
.iter()
.copied()
.find(|t| t.name() == name)
.ok_or_else(|| Error::UnknownName {
what: "negative translation",
name: name.into(),
known: Self::NAMES,
})
}
}
#[non_exhaustive]
#[derive(Clone, Copy, Debug, Default, 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 translation: Translation,
pub target: Option<Logic>,
}
impl Options {
#[must_use]
pub const fn with_translation(self, translation: Translation) -> Self {
Self {
translation,
..self
}
}
#[must_use]
pub const fn with_target(self, target: Option<Logic>) -> Self {
Self { target, ..self }
}
pub const fn target(&self) -> Logic {
match self.target {
Some(logic) => logic,
None => self.translation.target(),
}
}
}
#[derive(Clone, Copy)]
struct Row {
shape: Shape,
negations: u8,
}
#[derive(Clone, Copy)]
enum Shape {
Same,
DeMorgan,
}
const fn row(translation: Translation, node: Node) -> Row {
const KEEP: Row = Row {
shape: Shape::Same,
negations: 0,
};
const DOUBLE: Row = Row {
shape: Shape::Same,
negations: 2,
};
match (translation, node) {
(Translation::Kolmogorov, _) => DOUBLE,
(Translation::GodelGentzen, Node::Atom(_)) => DOUBLE,
(Translation::GodelGentzen, Node::Or(..)) => Row {
shape: Shape::DeMorgan,
negations: 0,
},
(
Translation::GodelGentzen,
Node::True
| Node::False
| Node::Not(_)
| Node::And(..)
| Node::Implies(..)
| Node::Iff(..),
)
| (Translation::Kuroda | Translation::Glivenko, _) => KEEP,
}
}
const fn sides(translation: Translation) -> (u8, u8) {
match translation {
Translation::Kolmogorov | Translation::GodelGentzen => (0, 0),
Translation::Kuroda => (2, 2),
Translation::Glivenko => (0, 2),
}
}
pub fn translate(sequent: &Sequent, options: &Options, limits: &Limits) -> Result<Sequent, Error> {
let translation = options.translation;
let target = options.target();
if !translation.reaches(target) {
return Err(Error::NegativeTarget {
translation,
logic: target,
});
}
let mut source = sequent.formulas().clone();
let mut goal = None;
for &d in sequent.right() {
goal = Some(match goal {
None => d,
Some(g) => source.add(Node::Or(g, d))?,
});
}
let mut reached = vec![false; source.len()];
for &root in sequent.left().iter().chain(&goal) {
reached[root.index()] = true;
}
for k in (0..source.len()).rev() {
if reached[k] {
let (a, b) = source.nodes[k].operands();
for id in [a, b].into_iter().flatten() {
reached[id.index()] = true;
}
}
}
let mut out = Formulas::default();
let mut image: Vec<NodeId> = vec![NodeId(0); source.len()];
for (k, &node) in source.nodes.iter().enumerate() {
if !reached[k] {
continue;
}
let of = |id: NodeId| image[id.index()];
let Row { shape, negations } = row(translation, node);
let mut id = match (shape, node) {
(Shape::DeMorgan, Node::Or(a, b)) => {
let na = out.add(Node::Not(of(a)))?;
let nb = out.add(Node::Not(of(b)))?;
let both = out.add(Node::And(na, nb))?;
out.add(Node::Not(both))?
}
(_, Node::Atom(a)) => out.atom(source.atom_name(a))?,
(_, Node::True) => out.add(Node::True)?,
(_, Node::False) => out.add(Node::False)?,
(_, Node::Not(a)) => out.add(Node::Not(of(a)))?,
(_, Node::And(a, b)) => out.add(Node::And(of(a), of(b)))?,
(_, Node::Or(a, b)) => out.add(Node::Or(of(a), of(b)))?,
(_, Node::Implies(a, b)) => out.add(Node::Implies(of(a), of(b)))?,
(_, Node::Iff(a, b)) => out.add(Node::Iff(of(a), of(b)))?,
};
id = negated(&mut out, id, negations)?;
image[k] = id;
}
let (hypotheses, goals) = sides(translation);
let mut left = Vec::with_capacity(sequent.left().len());
for &h in sequent.left() {
let id = image[h.index()];
left.push(negated(&mut out, id, hypotheses)?);
}
let right = match goal {
Some(g) => {
let id = image[g.index()];
vec![negated(&mut out, id, goals)?]
}
None => Vec::new(),
};
super::bound(&out, &left, &right, limits)?;
Sequent::new(out, left, right)
}
fn negated(out: &mut Formulas, mut id: NodeId, count: u8) -> Result<NodeId, Error> {
for _ in 0..count {
id = out.add(Node::Not(id))?;
}
Ok(id)
}
#[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 Agreement {
Valid,
NotValid,
Unknown,
}
#[non_exhaustive]
#[derive(Clone, Debug)]
pub struct Comparison {
pub translation: Translation,
pub sequent: Sequent,
pub translated: Sequent,
pub classical: Outcome,
pub decided: Outcome,
pub agreement: Agreement,
}
pub fn compare(
sequent: &Sequent,
options: &Options,
search: &search::Options,
limits: &Limits,
mut stop: impl FnMut(Progress) -> bool,
) -> Result<Comparison, Error> {
let translated = translate(sequent, options, limits)?;
let classical = decide_within(
sequent,
&super::Options::default().with_logic(Logic::Classical),
search,
limits,
&mut stop,
)?;
let target = options.target();
let decided = decide_within(
&translated,
&super::Options::default().with_logic(target),
search,
limits,
&mut stop,
)?;
let fails = |was: &str, is: &str| Error::ClaimFails {
claim: options.translation.title().to_owned(),
reason: format!(
"the sequent is {was} in classical logic and its translation {is} in {target} logic"
),
};
let agreement = match (&classical.verdict, &decided.verdict) {
(Verdict::Valid(_), Verdict::Valid(_)) => Agreement::Valid,
(Verdict::NotValid, Verdict::NotValid) => Agreement::NotValid,
(Verdict::Unknown(_), _) | (_, Verdict::Unknown(_)) => Agreement::Unknown,
(Verdict::Valid(_), Verdict::NotValid) => return Err(fails("valid", "not valid")),
(Verdict::NotValid, Verdict::Valid(_)) => return Err(fails("not valid", "valid")),
};
Ok(Comparison {
translation: options.translation,
sequent: sequent.clone(),
translated,
classical,
decided,
agreement,
})
}
pub fn compare_default(sequent: &Sequent, options: &Options) -> Result<Comparison, Error> {
compare(
sequent,
options,
&search::Options::default(),
&Limits::default(),
|_| false,
)
}
#[cfg(all(test, feature = "parse"))]
mod tests {
use super::*;
#[test]
fn each_table_writes_its_formulas() {
let sequent: Sequent = "a, a -> b |- b \\/ c".parse().unwrap();
let limits = Limits::default();
let written: Vec<String> = Translation::ALL
.iter()
.map(|&t| {
let options = Options::default().with_translation(t);
translate(&sequent, &options, &limits).unwrap().to_string()
})
.collect();
assert_eq!(
written,
[
"¬¬a, ¬¬(¬¬a → ¬¬b) ⊢ ¬¬(¬¬b ∨ ¬¬c)",
"¬¬a, ¬¬a → ¬¬b ⊢ ¬(¬¬¬b ∧ ¬¬¬c)",
"¬¬a, ¬¬(a → b) ⊢ ¬¬(b ∨ c)",
"a, a → b ⊢ ¬¬(b ∨ c)",
]
);
}
#[test]
fn every_translation_keeps_the_verdict() {
let cases = [
("a \\/ ~a", true),
("~~a -> a", true),
("((a -> b) -> a) -> a", true),
("false -> a", true),
("a -> b |- ~a \\/ b", true),
("~(a /\\ b) |- ~a \\/ ~b", true),
("a <-> b, b |- a", true),
("a |- b, a", true),
("a \\/ b |- a", false),
("a -> b", false),
("~a, b |-", false),
("true |- a <-> ~a", false),
];
for (text, valid) in cases {
let sequent: Sequent = text.parse().unwrap();
for &t in Translation::ALL {
let options = Options::default().with_translation(t);
let comparison = compare_default(&sequent, &options)
.unwrap_or_else(|e| panic!("{text} by {t}: {e}"));
let expected = if valid {
Agreement::Valid
} else {
Agreement::NotValid
};
assert_eq!(comparison.agreement, expected, "{text} by {t}");
assert_eq!(comparison.decided.logic, t.target());
}
}
}
#[test]
fn generated_sequents_keep_their_verdicts() {
use crate::linear::search::generate::Rng;
let mut rng = Rng::new(63);
for _ in 0..200 {
let sequent = super::super::tests::generated_sequent(&mut rng);
for &t in Translation::ALL {
let options = Options::default().with_translation(t);
if let Err(error) = compare_default(&sequent, &options) {
panic!("{sequent} by {t}: {error}");
}
}
}
}
#[test]
fn targets_and_bounds_are_kept() {
let sequent: Sequent = "a -> a".parse().unwrap();
let limits = Limits::default();
for (t, logic, ok) in [
(Translation::Kuroda, Logic::Minimal, false),
(Translation::Glivenko, Logic::Minimal, false),
(Translation::Kolmogorov, Logic::Classical, false),
(Translation::Kolmogorov, Logic::Intuitionistic, true),
] {
let options = Options::default()
.with_translation(t)
.with_target(Some(logic));
assert_eq!(
translate(&sequent, &options, &limits).is_ok(),
ok,
"{t} into {logic}"
);
}
let small = Limits::default().with_occurrences(Some(5));
assert!(matches!(
translate(&sequent, &Options::default(), &small),
Err(Error::Refused(crate::Refusal::Occurrences { .. }))
));
}
}