deduxit 0.3.0

Logic suites, linear logic first: decides, checks, proves step by step and exports sequents of classical and intuitionistic linear logic, and ordinary propositional logic through its embeddings.
Documentation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
// deduxit © Fabian Lukas Grubmüller 2026
// Licensed under the EUPL

//! What a check reports: the derived sequents of a failing node, the
//! fault, or the refusal that ended it without a verdict.

use crate::errors::describe::{Budget, Limit, Names, cut, occurrence};
use crate::errors::{Described, Owner, Subject};
use crate::limits::Refusal;
use crate::linear::occurrences::{Member, ShapeError, Side};
use crate::linear::proofs::{Node, NodeId};
use crate::linear::sequents::Eigen;
use std::fmt::{Display, Formatter, Result as FmtResult};

/// A dyadic sequent as the checker derived it, by members: the
/// unrestricted zone `Θ`, the linear zone `Γ` with repeats, and whether a
/// `⊤` above absorbs any further linear context.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Dyadic {
    /// The unrestricted zone, ascending.
    pub theta: Vec<Member>,
    /// The linear zone, ascending, with repeats.
    pub gamma: Vec<Member>,
    /// Whether the linear zone may hold anything more.
    pub any: bool,
}

impl Display for Dyadic {
    /// Writes `⊢ Θ ; Γ` with the zones as ids, omitting `Θ ;` when it is
    /// empty, and `…` after `Γ` when anything more is allowed.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        self.write(f, None, None)
    }
}

impl Dyadic {
    /// Writes the sequent as [`Display`] does, with formulas instead of ids
    /// when a forest is given.
    fn write(&self, f: &mut Formatter<'_>, names: Option<Names<'_>>, limit: Limit) -> FmtResult {
        let list = |f: &mut Formatter<'_>, ids: &mut dyn Iterator<Item = &Member>, len: usize| {
            let mut budget = Budget::new(f, limit);
            for (i, &o) in ids.enumerate() {
                let written =
                    std::fmt::Write::write_str(&mut budget, if i == 0 { " " } else { ", " })
                        .and_then(|()| occurrence(&mut budget, names, o));
                if written.is_err() && budget.cut {
                    return write!(budget.f, "… ({len} formulas)");
                }
                written?;
            }
            Ok(())
        };
        let any =
            |f: &mut Formatter<'_>, empty: bool| f.write_str(if empty { " …" } else { ", …" });
        // Two-sided under a reading: `Θ ; Γ ⊢ C`, the unrestricted zone
        // being hypotheses under a `!`.
        if let Some(Names {
            reading: Some(reading),
            framing,
            ..
        }) = names
        {
            let occ = move |m: Member| framing.map_or(m.occ(), |f| f.occurrence(m));
            let side = |side: Side| move |o: &&Member| reading.position(occ(**o)) == side;
            let inputs = self.gamma.iter().filter(side(Side::Input)).count();
            if !self.theta.is_empty() {
                list(f, &mut self.theta.iter(), self.theta.len())?;
                f.write_str(" ;")?;
            }
            list(f, &mut self.gamma.iter().filter(side(Side::Input)), inputs)?;
            if self.any {
                any(f, inputs == 0)?;
            }
            f.write_str(if self.theta.is_empty() && inputs == 0 && !self.any {
                "⊢"
            } else {
                " ⊢"
            })?;
            let outputs = self.gamma.len() - inputs;
            return list(
                f,
                &mut self.gamma.iter().filter(side(Side::Output)),
                outputs,
            );
        }
        f.write_str("⊢")?;
        if !self.theta.is_empty() {
            list(f, &mut self.theta.iter(), self.theta.len())?;
            f.write_str(" ;")?;
        }
        list(f, &mut self.gamma.iter(), self.gamma.len())?;
        if self.any {
            any(f, self.gamma.is_empty())?;
        }
        Ok(())
    }
}

/// Why a check of a proof ended without accepting it: the term is not a
/// proof of its conclusion, a verdict, or the check was given up without
/// one. A caller must never report a refusal as an invalid proof, which
/// the two variants keep apart.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum CheckError {
    /// The term is not a proof of its conclusion in the mode.
    Invalid(Box<Invalid>),
    /// The check was given up without a verdict on the term: a bound or the
    /// caller's stop.
    Refused(Refused),
}

/// What makes a term no proof: the node at fault, what the checker had
/// derived for its premises, and what the rule required.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Invalid {
    /// The node at fault; the root when the proof concludes the wrong
    /// sequent or the sequent has no intuitionistic reading.
    pub node: NodeId,
    /// The node's rule instance.
    pub rule: Node,
    /// The sequents derived for the node's premises, in the node's order.
    pub premises: Vec<Dyadic>,
    /// What the rule required and did not get.
    pub fault: Fault,
}

/// Where a check was given up, and why.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Refused {
    /// The node the check had come to.
    pub node: NodeId,
    /// The bound that refused it, or the stop.
    pub refusal: Refusal,
}

/// What a rule required and did not get.
#[non_exhaustive]
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Fault {
    /// The mode forbids the rule: weakening of a formula that is not a `?`
    /// outside affine mode, Mix without Mix or in intuitionistic mode, and
    /// in an ordered mode every rule but the axiom, `⊗` and `⅋`.
    Forbidden,
    /// The mode is intuitionistic and the sequent has no intuitionistic
    /// reading, so no proof of it is checked.
    Shape(ShapeError),
    /// The mode is intuitionistic and a sequent of the rule has this many
    /// formulas on the right of `⊢` instead of one: the premise's linear
    /// zone after the rule, or the context a `⊤` would absorb, or a
    /// weakening of the goal.
    #[non_exhaustive]
    Succedents {
        /// How many formulas stand right of `⊢`.
        count: usize,
    },
    /// The member is not of the kind the rule acts on.
    #[non_exhaustive]
    Kind {
        /// The member the rule names.
        member: Member,
    },
    /// The two literals of an axiom are not an atom and its negation.
    NotDual,
    /// A premise, by its index in the node, lacks the member the rule
    /// consumes from it.
    #[non_exhaustive]
    Missing {
        /// Which premise.
        premise: usize,
        /// What it lacks.
        member: Member,
    },
    /// The premise of a promotion has a linear zone besides the promoted
    /// subformula.
    NotEmpty,
    /// The premises of `&` do not share their linear zone.
    Differ,
    /// In an ordered mode, the contexts of a `⊗`'s premises are not the
    /// two arcs of its conclusion's cyclic order on either side of the
    /// `⊗`: going round from it, the right premise's context must come
    /// first and the left one's after it, and joining them otherwise
    /// needs an exchange.
    Order,
    /// In the Lambek calculus without empty antecedents, a sequent of the
    /// rule has no formula left of `⊢`: every sequent of a proof keeps a
    /// hypothesis.
    EmptyAntecedent,
    /// A copy of a member that is not the subformula of a `?`.
    #[non_exhaustive]
    NotUnderQuest {
        /// The member copied.
        member: Member,
    },
    /// A cut names a member that is no occurrence of a cut formula `A`
    /// of the sequent: one of the conclusion, or of a cut formula's dual.
    #[non_exhaustive]
    NotACut {
        /// The member the cut names.
        member: Member,
    },
    /// The node's linear zone holds more formulas than the rest of the
    /// proof can consume: every later rule takes two at most, and the root
    /// concludes the sequent. Only a term no engine builds gets here, and
    /// over unbounded counts it would fail at the root instead.
    Surplus,
    /// The member is an occurrence under binders named without an
    /// instance: a term for each binder above it, which only a member of
    /// the proof's instance table has.
    #[non_exhaustive]
    Instance {
        /// The member the node names.
        member: Member,
    },
    /// The eigenvariable occurs outside the `∀` step that introduces it:
    /// a witness or a cut's frame below that step, or beside it, names it.
    /// Found at the root, where it remains. (An eigenvariable no `∀` step
    /// introduces is a constant outside the signature, a witness like any
    /// other.)
    #[non_exhaustive]
    Eigenvariable {
        /// The eigenvariable.
        eigen: Eigen,
    },
    /// A second `∀` step introduces the eigenvariable: every one has its
    /// own.
    #[non_exhaustive]
    Reintroduced {
        /// The eigenvariable.
        eigen: Eigen,
    },
    /// The root derives this sequent, which is not the proof's conclusion:
    /// its linear zone differs from the conclusion's formulas, or its
    /// unrestricted zone holds a copied member that no `?` rule below
    /// moved there.
    #[non_exhaustive]
    Conclusion {
        /// What the root derives.
        derived: Dyadic,
    },
}

impl Invalid {
    /// Returns the fault at `node`, with the premises derived for it.
    pub(crate) fn new(node: NodeId, rule: Node, premises: Vec<Dyadic>, fault: Fault) -> Self {
        Self {
            node,
            rule,
            premises,
            fault,
        }
    }
}

impl CheckError {
    /// Returns the node at fault, or the node the check had come to when
    /// it was refused: the first one where it never began.
    pub fn node(&self) -> NodeId {
        match self {
            Self::Invalid(invalid) => invalid.node,
            Self::Refused(refused) => refused.node,
        }
    }

    /// Returns the fault, or `None` for a refusal.
    pub fn fault(&self) -> Option<&Fault> {
        match self {
            Self::Invalid(invalid) => Some(&invalid.fault),
            Self::Refused(_) => None,
        }
    }

    /// Returns the error of a fault at `node`.
    pub(crate) fn invalid(node: NodeId, rule: Node, premises: Vec<Dyadic>, fault: Fault) -> Self {
        Self::Invalid(Box::new(Invalid::new(node, rule, premises, fault)))
    }
}

impl Display for CheckError {
    /// Writes the node, its premises and the problem, as in `node 2 (⊗ on 1
    /// from 0, 1) with premises ⊢ 0, 3 and ⊢ 3, 4: premise 0 lacks
    /// occurrence 2`.
    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
        self.write(f, None, None)
    }
}

impl CheckError {
    /// Returns the error for display with formulas instead of occurrence
    /// ids, read from `owner`, the proof that failed or its forest; the
    /// nodes keep their ids. For instance `node 2 (⊗ on A ⊗ ~B from 0, 1)
    /// with premises ⊢ ~A, ~B and ⊢ ~B, B: premise 0 lacks A`.
    pub fn describe<'a>(&'a self, owner: &'a impl Owner) -> Described<'a> {
        Described::new(Subject::Check(self), owner)
    }

    /// Writes the error as [`Display`] does, with formulas instead of ids
    /// when a forest is given.
    pub(crate) fn write(
        &self,
        f: &mut Formatter<'_>,
        names: Option<Names<'_>>,
        limit: Limit,
    ) -> FmtResult {
        let invalid = match self {
            Self::Invalid(invalid) => invalid,
            Self::Refused(refused) => {
                return write!(
                    f,
                    "the check was given up at node {}, without a verdict on the proof: {}",
                    refused.node.get(),
                    refused.refusal
                );
            }
        };
        invalid.write(f, names, limit)
    }
}

impl Invalid {
    /// Writes the fault as [`CheckError`]'s `Display` does, with formulas
    /// instead of ids when a forest is given.
    fn write(&self, f: &mut Formatter<'_>, names: Option<Names<'_>>, limit: Limit) -> FmtResult {
        let reading = names.and_then(|n| n.reading);
        let occ = |m: Member| {
            names
                .and_then(|n| n.framing)
                .map_or(m.occ(), |framing| framing.occurrence(m))
        };
        write!(
            f,
            "node {} ({}",
            self.node.get(),
            name(self.rule, reading, occ)
        )?;
        for (i, o) in self.rule.members().enumerate() {
            f.write_str(if i == 0 { " on " } else { ", " })?;
            cut(f, names, o, limit)?;
        }
        for (i, p) in self.rule.premises().enumerate() {
            write!(f, "{}{}", if i == 0 { " from " } else { ", " }, p.get())?;
        }
        f.write_str(")")?;
        for (i, p) in self.premises.iter().enumerate() {
            f.write_str(if i == 0 { " with premises " } else { " and " })?;
            p.write(f, names, limit)?;
        }
        f.write_str(": ")?;
        use Fault::*;
        match &self.fault {
            Forbidden => f.write_str("the mode forbids the rule"),
            Shape(e) => {
                f.write_str("not an intuitionistic sequent: ")?;
                e.write(f, names, limit)
            }
            Succedents { count } => write!(
                f,
                "a sequent of the rule has {count} formulas on the right of ⊢ instead of one"
            ),
            Kind { member: o } => {
                if names.is_none() {
                    f.write_str("occurrence ")?;
                }
                cut(f, names, *o, limit)?;
                f.write_str(" is not what the rule acts on")
            }
            NotDual => f.write_str(if reading.is_some() {
                "the axiom's formulas are not one atom on either side of ⊢"
            } else {
                "the literals are not an atom and its negation"
            }),
            Missing { premise, member: o } => {
                write!(f, "premise {premise} lacks ")?;
                if names.is_none() {
                    f.write_str("occurrence ")?;
                }
                cut(f, names, *o, limit)
            }
            NotEmpty => f.write_str("the linear zone is not empty"),
            Differ => f.write_str("the premises differ"),
            Order => f.write_str("the premises' contexts are not the arcs on either side of the ⊗"),
            EmptyAntecedent => f.write_str(
                "the sequent has no formula left of ⊢, which the Lambek calculus without empty antecedents forbids",
            ),
            NotACut { member: o } => {
                if names.is_none() {
                    f.write_str("occurrence ")?;
                }
                cut(f, names, *o, limit)?;
                f.write_str(" is not in a cut formula")
            }
            NotUnderQuest { member: o } => {
                if names.is_none() {
                    f.write_str("occurrence ")?;
                }
                cut(f, names, *o, limit)?;
                // An input `?` is a hypothesis under a `!`.
                f.write_str(if reading.is_some() {
                    " is not under a hypothesis's !"
                } else {
                    " is not under a ?"
                })
            }
            Surplus => f.write_str(
                "the linear zone holds more formulas than the rest of the proof can consume",
            ),
            Instance { member: o } => {
                if names.is_none() {
                    f.write_str("occurrence ")?;
                }
                cut(f, names, *o, limit)?;
                f.write_str(" stands under a binder and is named without its instance")
            }
            Eigenvariable { eigen } => {
                f.write_str("eigenvariable ")?;
                eigenvariable(f, names, *eigen)?;
                f.write_str(" occurs outside the ∀ step that introduces it")
            }
            Reintroduced { eigen } => {
                f.write_str("eigenvariable ")?;
                eigenvariable(f, names, *eigen)?;
                f.write_str(" is introduced by a second ∀ step")
            }
            Conclusion { derived: d } => {
                f.write_str("the proof concludes ")?;
                d.write(f, names, limit)?;
                f.write_str(", not the sequent")
            }
        }
    }
}

impl std::error::Error for CheckError {}

/// Returns the name of a node's rule: its tag, or under a reading the
/// two-sided name of the rule on its principal formula (`⊸L` for a `⊗` on
/// a hypothesis).
fn name(
    node: Node,
    reading: Option<&crate::linear::Reading<'_>>,
    occ: impl Fn(Member) -> crate::linear::OccId,
) -> &'static str {
    use crate::linear::proofs::{Branch, Named, Rule};
    let (Some(reading), Some(o)) = (reading, node.principal()) else {
        return node.name();
    };
    let rule = match node {
        Node::Tensor(..) => Rule::Tensor,
        Node::Par(..) => Rule::Par,
        Node::One(_) => Rule::One,
        Node::Bot(..) => Rule::Bot,
        Node::With(..) => Rule::With,
        Node::Plus(_, Branch::Left, _) => Rule::PlusLeft,
        Node::Plus(_, Branch::Right, _) => Rule::PlusRight,
        Node::Top(_) => Rule::Top,
        Node::Bang(..) => Rule::Promotion,
        Node::Quest(..) => Rule::Dereliction,
        Node::Forall(..) => Rule::Forall,
        Node::Exists(..) => Rule::Exists,
        // Their tags name no connective.
        Node::Ax(..) | Node::Copy(..) | Node::Weaken(..) | Node::Mix(..) | Node::Cut(..) => {
            return node.name();
        }
    };
    Named::applied(rule, Some(reading), occ(o)).name()
}

/// Writes an eigenvariable by the name its proof's derivation writes it
/// with where the names are given, else by its number.
fn eigenvariable(f: &mut Formatter<'_>, names: Option<Names<'_>>, eigen: Eigen) -> FmtResult {
    match names.and_then(|n| n.framing) {
        Some(framing) => f.write_str(framing.name(eigen)),
        None => write!(f, "{}", eigen.get()),
    }
}