use super::{
DEDUXIT_FIRST_ORDER_PRELUDE, DEDUXIT_FIRST_ORDER_REFUTATION_PRELUDE,
DEDUXIT_FIRST_ORDER_TWO_SIDED_PRELUDE, DEDUXIT_PRELUDE, DEDUXIT_REFUTATION_PRELUDE,
DEDUXIT_TWO_SIDED_PRELUDE, Options, Unsupported,
};
use crate::Error;
use crate::export::Form;
use crate::export::notation::{Step, flush, walk};
use crate::linear::occurrences::instances::Framing;
use crate::linear::occurrences::{Forest, FrameId, Member, OccId, Reading, Side, Sign};
use crate::linear::proofs::{Derivation, InfId, Rule};
use crate::linear::search::{Classical, Disproof, OneSidedSymbol, Refutation, UnbalancedSymbol};
use crate::linear::sequents::{Args, Atom, FoTerm, FoTermId, Stop, Stops, Symbol, Term};
use std::fmt::Write;
#[derive(Clone, Copy, Debug)]
pub(super) struct Calculus {
pub(super) mix: bool,
pub(super) weakening: bool,
pub(super) cut: bool,
}
fn literal(mix: bool, weakening: bool, cut: bool) -> String {
format!("{{| mix := {mix}; weakening := {weakening}; cut := {cut} |}}")
}
fn qualified(mix: bool, weakening: bool, cut: bool) -> String {
format!(
"{{| Calculus.mix := {mix}; Calculus.weakening := {weakening}; Calculus.cut := {cut} |}}"
)
}
pub(super) fn write(
derivation: &Derivation,
options: &Options,
calculus: Calculus,
out: &mut impl Write,
mut stop: impl FnMut() -> bool,
) -> Result<(), Error> {
for inference in derivation.inferences() {
if inference.times > 1 {
return Err(Unsupported::Compact.into());
}
if inference.rule.rule == Rule::Open {
return Err(Unsupported::Open.into());
}
}
let mut term = Writer::new(derivation);
let reading = derivation.reading();
let first_order = term.fo.is_some();
let (atom, ill_module) = if first_order {
("symbol", "Intuitionistic.")
} else {
("atom", "")
};
if options.form == Form::Standalone {
let own = match (reading, first_order) {
(Some(_), false) => DEDUXIT_TWO_SIDED_PRELUDE,
(None, false) => DEDUXIT_PRELUDE,
(Some(_), true) => DEDUXIT_FIRST_ORDER_TWO_SIDED_PRELUDE,
(None, true) => DEDUXIT_FIRST_ORDER_PRELUDE,
};
let prelude = options.prelude.as_deref().unwrap_or(own);
write!(out, "{}\n\n", prelude.trim_end())?;
}
let root = derivation.inference(derivation.root());
write!(term.out, "Lemma {} : ", options.lemma)?;
let theorem = if let Some(reading) = reading {
let rules = match (calculus.weakening, calculus.cut) {
(true, false) => format!("{ill_module}affine"),
(false, false) => format!("{ill_module}intuitionistic"),
(weakening, true) => {
format!("{{| {ill_module}iweakening := {weakening}; {ill_module}icut := true |}}")
}
};
write!(term.out, "ill ({atom} := string) {rules} [")?;
let hypotheses = root
.sequent
.iter()
.map(|m| m.occ())
.filter(|&o| reading.position(o) == Side::Input);
for (i, o) in hypotheses.enumerate() {
if i > 0 {
term.out.push_str("; ");
}
term.iformula((o, None), 0, false);
}
term.out.push_str("] ");
let goal = goal(derivation, reading, &root.sequent);
term.iformula(term.parts(goal), 0, true);
format!("soundness_ill String.eqb String.eqb_spec {rules}")
} else {
let Calculus {
mix,
weakening,
cut,
} = calculus;
let record = if first_order { qualified } else { literal };
let (rules, theorem) = match (mix, weakening, cut) {
(false, false, false) if first_order => {
("Calculus.classical".to_owned(), "soundness_classical")
}
(false, false, false) => ("classical".to_owned(), "soundness_classical"),
(true, false, false) => (record(mix, weakening, cut), "soundness_mix"),
(false, true, false) => (record(mix, weakening, cut), "soundness_affine"),
_ => (record(mix, weakening, cut), "soundness"),
};
write!(term.out, "ll ({atom} := string) {rules} [")?;
for (i, m) in root.sequent.iter().enumerate() {
if i > 0 {
term.out.push_str("; ");
}
term.formula((m.occ(), None), 0, false);
}
term.out.push(']');
if theorem == "soundness" {
format!("{theorem} String.eqb String.eqb_spec {rules}")
} else {
format!("{theorem} String.eqb String.eqb_spec")
}
};
write!(term.out, ".\nProof.\n apply ({theorem}\n ")?;
walk(derivation, |step| {
match step {
Step::Enter(id, _) => term.enter(id),
Step::Exit(id, _) => {
for _ in 0..term.closes[id.index()] {
term.out.push(')');
}
}
}
flush(out, &mut term.out, &mut stop)
})?;
out.write_str(").\n vm_compute. reflexivity.\nQed.")?;
Ok(())
}
fn goal(derivation: &Derivation, reading: &Reading, sequent: &[Member]) -> Member {
*sequent
.iter()
.find(|&&m| reading.position(derivation.occurrence(m)) == Side::Output)
.expect("a two-sided sequent has its goal")
}
type Instance = (OccId, Option<FrameId>);
#[derive(Clone, Copy)]
struct Fo<'a> {
forest: &'a Forest,
framing: Option<&'a Framing<'a>>,
}
impl Fo<'_> {
fn parts(self, m: Member) -> Instance {
match self.framing {
Some(framing) if m.index() >= self.forest.len() => {
let (o, frame) = framing
.table
.instance(m)
.expect("a member of the proof's table");
(o, Some(frame))
}
_ => (m.occ(), None),
}
}
fn frame(self, frame: Option<FrameId>) -> Vec<FoTermId> {
match (frame, self.framing) {
(Some(frame), Some(framing)) => framing.table.frame_terms(frame),
_ => Vec::new(),
}
}
fn term(self, id: FoTermId) -> FoTerm {
match self.framing {
Some(framing) => framing.terms().term(id),
None => self.forest.sequent().fo.terms[id.index()],
}
}
fn list(&self, args: Args) -> &[FoTermId] {
match self.framing {
Some(framing) => framing.list(args),
None => self.forest.sequent().fo.list(args),
}
}
fn opened_with(self, body: Instance) -> FoTermId {
let framing = self.framing.expect("a quantifier step has instances");
let frame = body.1.expect("a body's instance has a frame");
framing.table.frame_parts(frame).1
}
fn write_term(
self,
out: &mut String,
id: FoTermId,
depth: u32,
frame: &[FoTermId],
argument: bool,
) {
enum Item {
Term(FoTermId, bool),
Text(&'static str),
}
let mut stack = vec![Item::Term(id, argument)];
while let Some(item) = stack.pop() {
let (t, argument) = match item {
Item::Text(text) => {
out.push_str(text);
continue;
}
Item::Term(t, argument) => (t, argument),
};
let (open, close) = if argument { ("(", ")") } else { ("", "") };
match self.term(t) {
FoTerm::Bound(i) if i < depth => {
write!(out, "{open}bound {i}{close}").expect("a string takes the text");
}
FoTerm::Bound(i) => stack.push(Item::Term(frame[(i - depth) as usize], argument)),
FoTerm::Eigen(a) => {
write!(out, "{open}eigen {}{close}", a.get()).expect("a string takes the text");
}
FoTerm::App(f, args) => {
let name = &self.forest.sequent().fo.symbols[f.index()].0;
write!(out, "{open}tapp {} [", string(name)).expect("a string takes the text");
stack.push(Item::Text(if argument { "])" } else { "]" }));
let list = self.list(args);
for (k, &u) in list.iter().enumerate().rev() {
stack.push(Item::Term(u, false));
if k > 0 {
stack.push(Item::Text("; "));
}
}
}
FoTerm::Meta(_) => unreachable!("a proof's table holds no metavariable"),
}
}
}
fn write_formula(
self,
out: &mut String,
reading: Option<&Reading>,
instance: Instance,
depth: u32,
argument: bool,
) {
let forest = self.forest;
let frame = self.frame(instance.1);
let mut depth = depth;
for visit in Stops::new(instance.0, argument, |k| (forest.left(k), forest.right(k))) {
match visit {
Stop::Enter(k, argument) => {
let t = forest.sequent().term(forest.term(k));
let nullary = matches!(t, Term::One | Term::Bot | Term::Top | Term::Zero);
if argument && !nullary {
out.push('(');
}
let name = match reading {
None => one_sided(t),
Some(reading) => two_sided(t, reading.position(k) == Side::Output),
};
out.push_str(name);
match t {
Term::Atom(a) | Term::DualAtom(a) => {
let (symbol, args) = forest.sequent().fo.atoms[a.index()];
let name = &forest.sequent().fo.symbols[symbol.index()].0;
write!(out, "{} [", string(name)).expect("a string takes the text");
for (i, &t) in self.list(args).iter().enumerate() {
if i > 0 {
out.push_str("; ");
}
self.write_term(out, t, depth, &frame, false);
}
out.push(']');
if argument {
out.push(')');
}
}
Term::Forall(_) | Term::Exists(_) => depth += 1,
Term::One
| Term::Bot
| Term::Top
| Term::Zero
| Term::Tensor(..)
| Term::Par(..)
| Term::With(..)
| Term::Plus(..)
| Term::Bang(_)
| Term::Quest(_) => {}
}
}
Stop::Between(_) => out.push(' '),
Stop::Exit(k, argument) => {
let t = forest.sequent().term(forest.term(k));
if matches!(t, Term::Forall(_) | Term::Exists(_)) {
depth -= 1;
}
if argument {
out.push(')');
}
}
}
}
}
}
const fn one_sided(t: Term) -> &'static str {
match t {
Term::Atom(_) => "var ",
Term::DualAtom(_) => "covar ",
Term::One => "one",
Term::Bot => "bot",
Term::Top => "top",
Term::Zero => "zero",
Term::Tensor(..) => "tens ",
Term::Par(..) => "parr ",
Term::With(..) => "awith ",
Term::Plus(..) => "aplus ",
Term::Bang(_) => "oc ",
Term::Quest(_) => "wn ",
Term::Forall(_) => "fall ",
Term::Exists(_) => "fex ",
}
}
const fn two_sided(t: Term, output: bool) -> &'static str {
match (t, output) {
(Term::Atom(_) | Term::DualAtom(_), _) => "ivar ",
(Term::One | Term::Bot, _) => "ione",
(Term::Top, true) | (Term::Zero, false) => "itop",
(Term::Zero, true) | (Term::Top, false) => "izero",
(Term::Tensor(..), true) | (Term::Par(..), false) => "itens ",
(Term::Par(..), true) | (Term::Tensor(..), false) => "ilmap ",
(Term::With(..), true) | (Term::Plus(..), false) => "iwith ",
(Term::Plus(..), true) | (Term::With(..), false) => "iplus ",
(Term::Bang(_) | Term::Quest(_), _) => "ioc ",
(Term::Forall(_), true) | (Term::Exists(_), false) => "iall ",
(Term::Exists(_), true) | (Term::Forall(_), false) => "iex ",
}
}
struct Writer<'a> {
derivation: &'a Derivation<'a>,
forest: &'a Forest,
fo: Option<Fo<'a>>,
out: String,
quests: Vec<Vec<Instance>>,
closes: Vec<u32>,
spaced: bool,
}
impl<'a> Writer<'a> {
fn new(derivation: &'a Derivation<'a>) -> Self {
let forest = derivation.forest();
let fo = forest.has_binders().then(|| Fo {
forest,
framing: derivation.framing(),
});
let parts = |m: Member| fo.map_or((m.occ(), None), |fo| fo.parts(m));
let count = derivation.inferences().len();
let mut quests = vec![Vec::new(); count];
if derivation.reading().is_none() {
let is_quest =
|o: OccId| matches!(forest.sequent().term(forest.term(o)), Term::Quest(_));
let root = derivation.root();
quests[root.index()] = derivation
.inference(root)
.sequent
.iter()
.map(|&m| parts(m))
.filter(|&(o, _)| is_quest(o))
.collect();
for (i, inference) in derivation.inferences().iter().enumerate() {
if let Some(a) = inference.cut {
let (a, frame) = parts(a);
let dual = forest.dual(a).expect("a cut formula has its dual");
for (&premise, o) in inference.premises.iter().zip([a, dual]) {
let sequent = &derivation.inference(premise).sequent;
if is_quest(o) && sequent.iter().any(|&m| parts(m) == (o, frame)) {
quests[premise.index()].push((o, frame));
}
}
}
let Some(principal) = inference.principal else {
continue;
};
let (o, frame) = parts(inference.sequent[principal]);
let children: Vec<Instance> =
if matches!(inference.rule.rule, Rule::Forall | Rule::Exists) {
vec![parts(body(derivation, InfId::new(i as u32)))]
} else {
[forest.left(o), forest.right(o)]
.into_iter()
.flatten()
.map(|child| (child, frame))
.collect()
};
for &premise in &inference.premises {
let sequent = &derivation.inference(premise).sequent;
for &child in &children {
if is_quest(child.0) && sequent.iter().any(|&m| parts(m) == child) {
quests[premise.index()].push(child);
}
}
}
}
}
Self {
derivation,
forest,
fo,
out: String::new(),
quests,
closes: vec![0; count],
spaced: false,
}
}
fn parts(&self, m: Member) -> Instance {
self.fo.map_or((m.occ(), None), |fo| fo.parts(m))
}
fn separate(&mut self) {
if self.spaced {
self.out.push(' ');
self.spaced = false;
}
}
fn formula(&mut self, instance: Instance, depth: u32, argument: bool) {
match self.fo {
Some(fo) => fo.write_formula(&mut self.out, None, instance, depth, argument),
None => formula(self.forest, &mut self.out, instance.0, argument),
}
}
fn iformula(&mut self, instance: Instance, depth: u32, argument: bool) {
let reading = self.derivation.reading().expect("a two-sided derivation");
match self.fo {
Some(fo) => fo.write_formula(&mut self.out, Some(reading), instance, depth, argument),
None => iformula(self.forest, reading, &mut self.out, instance.0, argument),
}
}
fn literal(&mut self, m: Member) {
let instance = self.parts(m);
match self.fo {
None => atom(self.forest, &mut self.out, instance.0),
Some(fo) => {
let mut text = String::new();
fo.write_formula(&mut text, None, instance, 0, false);
let args = text
.strip_prefix("var ")
.or_else(|| text.strip_prefix("covar "))
.expect("a literal");
self.out.push_str(args);
}
}
}
fn node(&mut self, id: InfId, constructor: &str, formulas: &[Instance], two_sided: bool) {
self.separate();
let leaf = self.derivation.inference(id).premises.is_empty();
if !leaf || !formulas.is_empty() {
self.out.push('(');
}
self.out.push_str(constructor);
for &f in formulas {
self.out.push(' ');
if two_sided {
self.iformula(f, 0, true);
} else {
self.formula(f, 0, true);
}
}
if leaf {
if !formulas.is_empty() {
self.out.push(')');
}
} else {
self.closes[id.index()] += 1;
}
self.spaced = true;
}
fn quantifier(&mut self, id: InfId, constructor: &str, principal: Instance, two_sided: bool) {
let fo = self.fo.expect("a quantifier step is first-order");
let opened = fo.parts(body(self.derivation, id));
let term = fo.opened_with(opened);
self.separate();
self.out.push('(');
self.out.push_str(constructor);
self.out.push(' ');
let body = (
self.forest.left(principal.0).expect("a binder's body"),
principal.1,
);
if two_sided {
self.iformula(body, 1, true);
} else {
self.formula(body, 1, true);
}
self.out.push(' ');
if constructor_introduces(constructor) {
let FoTerm::Eigen(a) = fo.term(term) else {
unreachable!("a ∀ step's body is opened with its eigenvariable")
};
write!(self.out, "{}", a.get()).expect("a string takes the text");
} else {
fo.write_term(&mut self.out, term, 0, &[], true);
}
self.closes[id.index()] += 1;
self.spaced = true;
}
fn enter(&mut self, id: InfId) {
let derivation = self.derivation;
let forest = self.forest;
let inference = derivation.inference(id);
for i in 0..self.quests[id.index()].len() {
let (q, frame) = self.quests[id.index()][i];
self.separate();
self.out.push_str("(Quest ");
self.formula((forest.left(q).expect("a ? formula"), frame), 0, true);
self.closes[id.index()] += 1;
self.spaced = true;
}
let principal = inference
.principal
.map(|p| self.parts(inference.sequent[p]));
let children: Vec<Instance> = principal
.into_iter()
.flat_map(|(o, frame)| {
[forest.left(o), forest.right(o)]
.into_iter()
.flatten()
.map(move |child| (child, frame))
})
.collect();
if let Some(reading) = derivation.reading() {
self.two_sided(id, reading, principal, &children);
return;
}
let is_quest = |o: OccId| matches!(forest.sequent().term(forest.term(o)), Term::Quest(_));
match inference.rule.rule {
Rule::Forall => {
let principal = principal.expect("a principal formula");
self.quantifier(id, "Forall", principal, false);
}
Rule::Exists => {
let principal = principal.expect("a principal formula");
self.quantifier(id, "Exists", principal, false);
}
Rule::Ax => {
let literal = inference.sequent[0];
self.separate();
self.out.push_str("(Ax ");
self.literal(literal);
self.out.push(')');
self.spaced = true;
}
Rule::Tensor => self.node(id, "Tensor", &children, false),
Rule::Par => self.node(id, "Par", &children, false),
Rule::One => self.node(id, "One", &[], false),
Rule::Bot => self.node(id, "Bot", &[], false),
Rule::With => self.node(id, "With", &children, false),
Rule::PlusLeft | Rule::PlusRight => {
let side = if inference.rule.rule == Rule::PlusLeft {
"Left"
} else {
"Right"
};
self.separate();
self.out.push_str("(Plus");
for &f in &children {
self.out.push(' ');
self.formula(f, 0, true);
}
self.out.push(' ');
self.out.push_str(side);
self.closes[id.index()] += 1;
self.spaced = true;
}
Rule::Top => self.node(id, "Top", &[], false),
Rule::Promotion => self.node(id, "Bang", &children, false),
Rule::Dereliction => self.node(id, "Copy", &children, false),
Rule::Mix => self.node(id, "Mix", &[], false),
Rule::AffineWeakening => {
let principal = principal.expect("a principal formula");
if !is_quest(principal.0) {
self.node(id, "Weaken", &[principal], false);
}
}
Rule::Contraction | Rule::Weakening => {}
Rule::Cut => {
let a = self.parts(inference.cut.expect("a cut names its formula"));
self.node(id, "Cut", &[a], false);
}
Rule::Open => unreachable!("refused before anything is written"),
}
}
fn two_sided(
&mut self,
id: InfId,
reading: &Reading,
principal: Option<Instance>,
children: &[Instance],
) {
let derivation = self.derivation;
let inference = derivation.inference(id);
let side = inference.rule.side;
let constructor = match (inference.rule.rule, side) {
(Rule::Forall, Some(Side::Output)) => {
self.quantifier(id, "IAllR", principal.expect("a principal formula"), true);
return;
}
(Rule::Forall, _) => {
self.quantifier(id, "IExL", principal.expect("a principal formula"), true);
return;
}
(Rule::Exists, Some(Side::Output)) => {
self.quantifier(id, "IExR", principal.expect("a principal formula"), true);
return;
}
(Rule::Exists, _) => {
self.quantifier(id, "IAllL", principal.expect("a principal formula"), true);
return;
}
(Rule::Ax, _) => {
let literal = inference.sequent[0];
self.separate();
self.out.push_str("(IAx ");
self.literal(literal);
self.out.push(')');
self.spaced = true;
return;
}
(Rule::Top, _) => {
let at = inference.principal.expect("a principal formula");
let others: Vec<Member> = inference
.sequent
.iter()
.copied()
.filter(|&m| m != inference.sequent[at])
.collect();
let right = side == Some(Side::Output);
let goal = goal(derivation, reading, &inference.sequent);
let (constructor, context): (_, Vec<Member>) = if right {
("(ITopR [", others)
} else {
(
"(IZeroL [",
others.into_iter().filter(|&m| m != goal).collect(),
)
};
self.separate();
self.out.push_str(constructor);
for (i, &m) in context.iter().enumerate() {
if i > 0 {
self.out.push_str("; ");
}
self.iformula(self.parts(m), 0, false);
}
self.out.push(']');
if !right {
self.out.push(' ');
self.iformula(self.parts(goal), 0, true);
}
self.out.push(')');
self.spaced = true;
return;
}
(Rule::One, _) => "IOneR",
(Rule::Bot, _) => "IOneL",
(Rule::Tensor, Some(Side::Output)) => "ITensR",
(Rule::Tensor, _) => "ILmapL",
(Rule::Par, Some(Side::Output)) => "ILmapR",
(Rule::Par, _) => "ITensL",
(Rule::With, Some(Side::Output)) => "IWithR",
(Rule::With, _) => "IPlusL",
(Rule::PlusLeft, Some(Side::Output)) => "IPlusR1",
(Rule::PlusLeft, _) => "IWithL1",
(Rule::PlusRight, Some(Side::Output)) => "IPlusR2",
(Rule::PlusRight, _) => "IWithL2",
(Rule::Promotion, _) => "IOcR",
(Rule::Dereliction, _) => "IDe",
(Rule::Contraction, _) => "ICo",
(Rule::Weakening, _) => "IWk",
(Rule::AffineWeakening, _) => {
let principal = principal.expect("a principal formula");
self.node(id, "IWeaken", &[principal], true);
return;
}
(Rule::Cut, _) => {
let (a, frame) = self.parts(inference.cut.expect("a cut names its formula"));
let dual = self.forest.dual(a).expect("a cut formula has its dual");
let proved = if reading.position(a) == Side::Output {
a
} else {
dual
};
self.node(id, "ICut", &[(proved, frame)], true);
return;
}
(Rule::Mix | Rule::Open, _) => {
unreachable!("no two-sided rule, or refused before anything is written")
}
};
self.node(id, constructor, children, true);
}
}
fn constructor_introduces(constructor: &str) -> bool {
matches!(constructor, "Forall" | "IAllR" | "IExL")
}
fn body(derivation: &Derivation, id: InfId) -> Member {
let inference = derivation.inference(id);
let premise = &derivation.inference(inference.premises[0]).sequent;
let conclusion = &inference.sequent;
let mut j = 0;
for &m in premise {
while j < conclusion.len() && conclusion[j] < m {
j += 1;
}
if conclusion.get(j) == Some(&m) {
j += 1;
} else {
return m;
}
}
unreachable!("a quantifier step's premise holds its body")
}
fn atom(forest: &Forest, out: &mut String, o: OccId) {
let sequent = forest.sequent();
let (Term::Atom(a) | Term::DualAtom(a)) = sequent.term(forest.term(o)) else {
unreachable!("a literal")
};
out.push_str(&string(&sequent.atom_names()[a.index()]));
}
fn formula(forest: &Forest, out: &mut String, o: OccId, argument: bool) {
for visit in Stops::new(o, argument, |k| (forest.left(k), forest.right(k))) {
match visit {
Stop::Enter(k, argument) => {
let t = forest.sequent().term(forest.term(k));
let nullary = matches!(t, Term::One | Term::Bot | Term::Top | Term::Zero);
if argument && !nullary {
out.push('(');
}
let name = match t {
Term::Atom(_) => "var ",
Term::DualAtom(_) => "covar ",
Term::One => "one",
Term::Bot => "bot",
Term::Top => "top",
Term::Zero => "zero",
Term::Tensor(..) => "tens ",
Term::Par(..) => "parr ",
Term::With(..) => "awith ",
Term::Plus(..) => "aplus ",
Term::Bang(_) => "oc ",
Term::Quest(_) => "wn ",
Term::Forall(_) | Term::Exists(_) => {
unreachable!("a sequent with a binder is written by `Fo`")
}
};
out.push_str(name);
if matches!(t, Term::Atom(_) | Term::DualAtom(_)) {
atom(forest, out, k);
if argument {
out.push(')');
}
}
}
Stop::Between(_) => out.push(' '),
Stop::Exit(_, argument) => {
if argument {
out.push(')');
}
}
}
}
}
fn iformula(forest: &Forest, reading: &Reading, out: &mut String, o: OccId, argument: bool) {
for visit in Stops::new(o, argument, |k| (forest.left(k), forest.right(k))) {
match visit {
Stop::Enter(k, argument) => {
let t = forest.sequent().term(forest.term(k));
let output = reading.position(k) == Side::Output;
let nullary = matches!(t, Term::One | Term::Bot | Term::Top | Term::Zero);
if argument && !nullary {
out.push('(');
}
let name = match (t, output) {
(Term::Atom(_) | Term::DualAtom(_), _) => "ivar ",
(Term::One | Term::Bot, _) => "ione",
(Term::Top, true) | (Term::Zero, false) => "itop",
(Term::Zero, true) | (Term::Top, false) => "izero",
(Term::Tensor(..), true) | (Term::Par(..), false) => "itens ",
(Term::Par(..), true) | (Term::Tensor(..), false) => "ilmap ",
(Term::With(..), true) | (Term::Plus(..), false) => "iwith ",
(Term::Plus(..), true) | (Term::With(..), false) => "iplus ",
(Term::Bang(_) | Term::Quest(_), _) => "ioc ",
(Term::Forall(_) | Term::Exists(_), _) => {
unreachable!("a sequent with a binder is written by `Fo`")
}
};
out.push_str(name);
if matches!(t, Term::Atom(_) | Term::DualAtom(_)) {
atom(forest, out, k);
if argument {
out.push(')');
}
}
}
Stop::Between(_) => out.push(' '),
Stop::Exit(_, argument) => {
if argument {
out.push(')');
}
}
}
}
}
pub(super) fn disproof(
disproof: &Disproof,
options: &Options,
out: &mut impl Write,
) -> Result<(), Error> {
disproof.check()?;
let forest = Forest::new(disproof.sequent())?;
let first_order = forest.has_binders();
if first_order && matches!(disproof.refutation(), Refutation::Equation(_)) {
return Err(super::Unsupported::Quantifiers.into());
}
let goal: Vec<OccId> = match disproof.goal() {
None => forest.roots().to_vec(),
Some(members) => members
.iter()
.filter_map(|m| m.occurrence(&forest))
.collect(),
};
let mode = disproof.mode();
let reading = if mode.is_intuitionistic() {
Some(Reading::new(&forest).map_err(Error::NotIntuitionistic)?)
} else {
None
};
if let Some(reading) = &reading {
let count = goal
.iter()
.filter(|&&o| reading.position(o) == Side::Output)
.count();
if count != 1 {
return Err(Error::GoalOutputs { count });
}
}
if options.form == Form::Standalone {
let own = if first_order {
DEDUXIT_FIRST_ORDER_REFUTATION_PRELUDE
} else {
DEDUXIT_REFUTATION_PRELUDE
};
let prelude = options.prelude.as_deref().unwrap_or(own);
write!(out, "{}\n\n", prelude.trim_end())?;
}
let fo = Fo {
forest: &forest,
framing: None,
};
let formula = |text: &mut String, o: OccId, argument: bool| match (&reading, first_order) {
(_, true) => fo.write_formula(text, reading.as_ref(), (o, None), 0, argument),
(Some(reading), false) => iformula(&forest, reading, text, o, argument),
(None, false) => self::formula(&forest, text, o, argument),
};
let (atom, module) = if first_order {
("symbol", "Intuitionistic.")
} else {
("atom", "")
};
let mut text = format!("Lemma {} : ~ ", options.lemma);
let side = if let Some(reading) = &reading {
let rules = if mode.is_affine() {
"affine"
} else {
"intuitionistic"
};
write!(text, "ill ({atom} := string) {module}{rules} [").expect("a string takes the text");
let hypotheses = goal
.iter()
.copied()
.filter(|&o| reading.position(o) == Side::Input);
for (i, o) in hypotheses.enumerate() {
if i > 0 {
text.push_str("; ");
}
formula(&mut text, o, false);
}
text.push_str("] ");
let conclusion = goal
.iter()
.copied()
.find(|&o| reading.position(o) == Side::Output)
.expect("the goal has one conclusion");
formula(&mut text, conclusion, true);
"i"
} else {
let rules = match (mode.has_mix(), mode.is_affine(), first_order) {
(false, false, false) => "classical".to_owned(),
(false, false, true) => "Calculus.classical".to_owned(),
(mix, weakening, false) => literal(mix, weakening, false),
(mix, weakening, true) => qualified(mix, weakening, false),
};
write!(text, "ll ({atom} := string) {rules} [").expect("a string takes the text");
for (i, &o) in goal.iter().enumerate() {
if i > 0 {
text.push_str("; ");
}
formula(&mut text, o, false);
}
text.push(']');
""
};
let sequent = forest.sequent();
let names = sequent.atom_names();
let unit = |positive: bool| if positive { "1%Z" } else { "(-1)%Z" };
let theorem = match disproof.refutation() {
Refutation::Classical(Classical { assignment }) => {
let truths: Vec<String> = (0..names.len())
.filter(|&a| assignment[a])
.map(|a| string(&names[a]))
.collect();
format!(
"{side}classical_refutation _ (fun a => existsb (String.eqb a) [{}])",
truths.join("; ")
)
}
Refutation::Unbalanced(unbalanced) if first_order => {
fo.weighted_atom(side, unbalanced.atom, unit(unbalanced.least > 0))
}
Refutation::Unbalanced(unbalanced) => format!(
"{side}unbalanced_refutation String.eqb {} _",
string(&names[unbalanced.atom.index()])
),
Refutation::OneSided(one_sided) if first_order => {
fo.weighted_atom(side, one_sided.atom, unit(one_sided.copied == Sign::Atom))
}
Refutation::OneSided(one_sided) => weighted(
side,
&[(
&names[one_sided.atom.index()],
unit(one_sided.copied == Sign::Atom),
)],
),
Refutation::UnbalancedSymbol(UnbalancedSymbol { symbol, least, .. })
| Refutation::OneSidedSymbol(OneSidedSymbol { symbol, least, .. }) => {
let positive = if let Refutation::OneSidedSymbol(one_sided) = disproof.refutation() {
one_sided.copied == Sign::Atom
} else {
*least > 0
};
if first_order {
fo.weighted_symbol(side, *symbol, unit(positive))
} else {
let atoms: Vec<(&str, &str)> = (0..names.len())
.filter(|&a| {
sequent
.atom_predicate(Atom::new(a as u32))
.is_some_and(|(s, _)| s == *symbol)
})
.map(|a| (names[a].as_str(), unit(positive)))
.collect();
weighted(side, &atoms)
}
}
Refutation::Equation(_) => format!("{side}equation_refutation _"),
Refutation::StateEquation(equation) => {
let deaths =
crate::linear::search::weighted::state_equation(&forest, &goal, mode, equation)
.expect("the check accepted the weights");
let negated = deaths.body == Sign::Dual;
let weights: Vec<String> = equation
.atoms
.iter()
.map(|&(a, w)| {
let w = if negated {
-i128::from(w)
} else {
i128::from(w)
};
format!("({}, {})", string(&names[a.index()]), integer(w))
})
.collect();
let dead: Vec<String> = (0..names.len())
.filter(|&a| deaths.dead[a])
.map(|a| string(&names[a]))
.collect();
let theorem = if mode.is_affine() {
"affine_refutation"
} else {
"weighted_refutation"
};
format!(
"{side}{theorem} (weight_of String.eqb [{}])\n (fun a => existsb (String.eqb a) [{}]) {} _",
weights.join("; "),
dead.join("; "),
!negated
)
}
Refutation::Exhausted => unreachable!("the check certifies no exhausted search"),
Refutation::Saturated(_) => unreachable!("the writer refuses a saturated set first"),
};
write!(
text,
".\nProof.\n apply ({theorem}).\n vm_compute. reflexivity.\nQed."
)
.expect("a string takes the text");
out.write_str(&text)?;
Ok(())
}
fn weighted(side: &str, atoms: &[(&str, &str)]) -> String {
let table: Vec<String> = atoms
.iter()
.map(|&(name, w)| format!("({}, {w})", string(name)))
.collect();
format!(
"{side}weighted_refutation (weight_of String.eqb [{}])\n (fun a => existsb (String.eqb a) []) true _",
table.join("; ")
)
}
fn integer(z: i128) -> String {
if z < 0 {
format!("({z})%Z")
} else {
format!("{z}%Z")
}
}
impl Fo<'_> {
fn fixed(self) -> String {
let sequent = self.forest.sequent();
let atoms = sequent.atom_names().len();
let mut open = vec![false; sequent.symbols().len()];
let mut predicate = vec![false; sequent.symbols().len()];
for a in (0..atoms).map(|a| Atom::new(a as u32)) {
if let Some((symbol, _)) = sequent.atom_predicate(a) {
predicate[symbol.index()] = true;
open[symbol.index()] |= sequent.atom_is_open(a);
}
}
let fixed: Vec<String> = (0..open.len())
.filter(|&s| predicate[s] && !open[s])
.map(|s| string(&sequent.symbols()[s].0))
.collect();
format!("(fun p => existsb (String.eqb p) [{}])", fixed.join("; "))
}
fn weighted_atom(self, side: &str, atom: Atom, w: &str) -> String {
let sequent = self.forest.sequent();
let (symbol, args) = sequent
.atom_predicate(atom)
.expect("an atom of a predicate");
let mut terms = String::new();
for (i, &t) in self.list(args).iter().enumerate() {
if i > 0 {
terms.push_str("; ");
}
self.write_term(&mut terms, t, 0, &[], false);
}
format!(
"FirstOrderWeights.{side}weighted_refutation {}\n (fun p ts => if String.eqb p {} && TermsCheck.terms_eqb String.eqb ts [{terms}] then {w} else 0%Z)\n (fun _ => 0%Z) _",
self.fixed(),
string(&sequent.symbols()[symbol.index()].0),
)
}
fn weighted_symbol(self, side: &str, symbol: Symbol, w: &str) -> String {
let name = string(&self.forest.sequent().symbols()[symbol.index()].0);
format!(
"FirstOrderWeights.{side}weighted_refutation {}\n (fun p _ => if String.eqb p {name} then {w} else 0%Z)\n (fun p => if String.eqb p {name} then {w} else 0%Z) _",
self.fixed(),
)
}
}
fn string(name: &str) -> String {
format!("\"{}\"", name.replace('"', "\"\""))
}