use std::fmt::{Display, Formatter, Result as FmtResult};
#[derive(Clone, Debug)]
pub(crate) struct Rng(u64);
impl Rng {
pub(crate) fn new(seed: u64) -> Self {
Self(seed)
}
pub(crate) fn next(&mut self) -> u64 {
self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
let mut z = self.0;
z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
z ^ (z >> 31)
}
pub(crate) fn below(&mut self, n: usize) -> usize {
(self.next() % n as u64) as usize
}
pub(crate) fn one_in(&mut self, n: usize) -> bool {
self.below(n) == 0
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Rules {
pub(crate) units: bool,
pub(crate) additives: bool,
pub(crate) mix: bool,
pub(crate) exponentials: bool,
}
impl Rules {
pub(crate) const ALL: [Rules; 16] = {
let mut all = [Rules {
units: false,
additives: false,
mix: false,
exponentials: false,
}; 16];
let mut i = 0;
while i < 16 {
all[i] = Rules {
units: i & 1 != 0,
additives: i & 2 != 0,
mix: i & 4 != 0,
exponentials: i & 8 != 0,
};
i += 1;
}
all
};
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Provable {
pub(crate) formulas: Vec<Tree>,
pub(crate) copies: u32,
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) enum Tree {
Atom(u8),
Dual(u8),
One,
Bot,
Top,
Zero,
Tensor(Box<Tree>, Box<Tree>),
Par(Box<Tree>, Box<Tree>),
With(Box<Tree>, Box<Tree>),
Plus(Box<Tree>, Box<Tree>),
Bang(Box<Tree>),
Quest(Box<Tree>),
Lolli(Box<Tree>, Box<Tree>),
}
impl Tree {
fn literals(&mut self, positive: bool) -> Vec<(&mut u8, bool)> {
use Tree::*;
match self {
Atom(a) => vec![(a, positive)],
Dual(a) => vec![(a, !positive)],
One | Bot | Top | Zero => vec![],
Tensor(l, r) | Par(l, r) | With(l, r) | Plus(l, r) => {
let mut all = l.literals(positive);
all.extend(r.literals(positive));
all
}
Lolli(l, r) => {
let mut all = l.literals(!positive);
all.extend(r.literals(positive));
all
}
Bang(a) | Quest(a) => a.literals(positive),
}
}
fn bangs(&self) -> u32 {
use Tree::*;
match self {
Atom(_) | Dual(_) | One | Bot | Top | Zero => 0,
Tensor(l, r) | Par(l, r) | With(l, r) | Plus(l, r) | Lolli(l, r) => {
l.bangs() + r.bangs()
}
Bang(a) => 1 + a.bangs(),
Quest(a) => a.bangs(),
}
}
fn is_bang(&self) -> bool {
matches!(self, Tree::Bang(_))
}
fn is_quest(&self) -> bool {
matches!(self, Tree::Quest(_))
}
}
impl Display for Tree {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
use Tree::*;
let binary =
|f: &mut Formatter<'_>, l: &Tree, op: &str, r: &Tree| write!(f, "({l} {op} {r})");
match self {
Atom(a) => write!(f, "{}", (b'a' + a) as char),
Dual(a) => write!(f, "~{}", (b'a' + a) as char),
One => f.write_str("1"),
Bot => f.write_str("bot"),
Top => f.write_str("top"),
Zero => f.write_str("0"),
Tensor(l, r) => binary(f, l, "*", r),
Par(l, r) => binary(f, l, "par", r),
With(l, r) => binary(f, l, "&", r),
Plus(l, r) => binary(f, l, "+", r),
Bang(a) => write!(f, "!{a}"),
Quest(a) => write!(f, "?{a}"),
Lolli(l, r) => binary(f, l, "-o", r),
}
}
}
pub(crate) fn two_sided(hypotheses: &[Tree], goal: &Tree) -> String {
let mut text = String::new();
for (i, formula) in hypotheses.iter().enumerate() {
if i > 0 {
text.push_str(", ");
}
text.push_str(&formula.to_string());
}
if !hypotheses.is_empty() {
text.push(' ');
}
text.push_str("|- ");
text.push_str(&goal.to_string());
text
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct IllRules {
pub(crate) units: bool,
pub(crate) additives: bool,
pub(crate) zero: bool,
pub(crate) exponentials: bool,
}
impl IllRules {
pub(crate) const ALL: [IllRules; 12] = {
let mut all = [IllRules {
units: false,
additives: false,
zero: false,
exponentials: false,
}; 12];
let (mut i, mut n) = (0, 0);
while i < 16 {
let zero = i & 4 != 0;
let additives = i & 2 != 0;
if !zero || additives {
all[n] = IllRules {
units: i & 1 != 0,
additives,
zero,
exponentials: i & 8 != 0,
};
n += 1;
}
i += 1;
}
all
};
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub(crate) struct Ill {
pub(crate) hypotheses: Vec<Tree>,
pub(crate) goal: Tree,
pub(crate) copies: u32,
pub(crate) contractions: u32,
}
pub(crate) fn ill(rng: &mut Rng, rules: IllRules, atoms: u8, budget: usize) -> Ill {
let mut generator = IllGenerator {
rng,
rules,
atoms,
contractions: 0,
};
let (hypotheses, goal, copies) = generator.proof(budget);
Ill {
hypotheses,
goal,
copies,
contractions: generator.contractions,
}
}
struct IllGenerator<'a> {
rng: &'a mut Rng,
rules: IllRules,
atoms: u8,
contractions: u32,
}
impl IllGenerator<'_> {
fn proof(&mut self, budget: usize) -> (Vec<Tree>, Tree, u32) {
use Tree::*;
if budget <= 1 {
return self.leaf();
}
let (mut hypotheses, mut goal, mut copies) = self.proof(budget - 1);
let mut choices: Vec<u8> = vec![b'a', b't', b't'];
if !hypotheses.is_empty() {
choices.extend(*b"llLL");
if self.rules.additives {
choices.extend(*b"wo");
}
if self.rules.exponentials {
choices.extend(*b"dc");
}
}
if hypotheses.len() >= 2 {
choices.push(b'T');
}
if self.rules.units {
choices.push(b'1');
}
if self.rules.additives {
choices.extend(*b"&+");
}
if self.rules.exponentials {
choices.extend(*b"!W");
}
let boxed = |t: Tree| Box::new(t);
match choices[self.rng.below(choices.len())] {
b'a' => return self.leaf(),
b't' => {
let other = 1 + self.rng.below(budget - 1);
let (delta, b, c) = self.proof(other);
hypotheses.extend(delta);
goal = Tensor(boxed(goal), boxed(b));
copies += c;
}
b'l' => {
let a = self.take_hypothesis(&mut hypotheses);
goal = Lolli(boxed(a), boxed(goal));
}
b'L' => {
let other = 1 + self.rng.below(budget - 1);
let (gamma, a, c) = self.proof(other);
let b = self.take_hypothesis(&mut hypotheses);
hypotheses.extend(gamma);
hypotheses.push(Lolli(boxed(a), boxed(b)));
copies += c;
}
b'T' => {
let a = self.take_hypothesis(&mut hypotheses);
let b = self.take_hypothesis(&mut hypotheses);
hypotheses.push(Tensor(boxed(a), boxed(b)));
}
b'1' => hypotheses.push(One),
b'&' => {
let twin = self.twin(&goal);
goal = if self.rng.one_in(2) {
With(boxed(goal), boxed(twin))
} else {
With(boxed(twin), boxed(goal))
};
}
b'+' => {
let junk = self.junk(2);
goal = if self.rng.one_in(2) {
Plus(boxed(goal), boxed(junk))
} else {
Plus(boxed(junk), boxed(goal))
};
}
b'w' => {
let a = self.take_hypothesis(&mut hypotheses);
let junk = self.junk(2);
hypotheses.push(if self.rng.one_in(2) {
With(boxed(a), boxed(junk))
} else {
With(boxed(junk), boxed(a))
});
}
b'o' => {
let a = self.take_hypothesis(&mut hypotheses);
let twin = match self.rng.below(3) {
0 if self.rules.zero => Zero,
1 => With(boxed(a.clone()), boxed(self.junk(2))),
_ => a.clone(),
};
hypotheses.push(if self.rng.one_in(2) {
Plus(boxed(a), boxed(twin))
} else {
Plus(boxed(twin), boxed(a))
});
}
b'd' => {
let a = self.take_hypothesis(&mut hypotheses);
hypotheses.push(Bang(boxed(a)));
copies += 1;
}
b'!' => {
for h in &mut hypotheses {
if !h.is_bang() {
*h = Bang(boxed(std::mem::replace(h, One)));
copies += 1;
}
}
goal = Bang(boxed(goal));
}
b'c' => {
let i = self.rng.below(hypotheses.len());
if !hypotheses[i].is_bang() {
hypotheses[i] = Bang(boxed(std::mem::replace(&mut hypotheses[i], One)));
copies += 1;
}
let Bang(b) = &hypotheses[i] else {
unreachable!()
};
let b = (**b).clone();
copies += 1 + b.bangs();
self.contractions += 1;
goal = if self.rng.one_in(2) {
Tensor(boxed(goal), boxed(b))
} else {
Tensor(boxed(b), boxed(goal))
};
}
b'W' => {
let junk = self.junk(2);
hypotheses.push(Bang(boxed(junk)));
}
_ => unreachable!(),
}
(hypotheses, goal, copies)
}
fn leaf(&mut self) -> (Vec<Tree>, Tree, u32) {
let mut choices: Vec<u8> = vec![b'a', b'a'];
if self.rules.units {
choices.push(b'1');
}
if self.rules.additives {
choices.push(b'T');
}
if self.rules.zero {
choices.push(b'0');
}
let junk_context = |this: &mut Self| -> Vec<Tree> {
(0..this.rng.below(3)).map(|_| this.junk(2)).collect()
};
match choices[self.rng.below(choices.len())] {
b'a' => {
let a = self.rng.below(self.atoms as usize) as u8;
(vec![Tree::Atom(a)], Tree::Atom(a), 0)
}
b'1' => (vec![], Tree::One, 0),
b'T' => (junk_context(self), Tree::Top, 0),
b'0' => {
let mut context = junk_context(self);
context.push(Tree::Zero);
let goal = self.junk(2);
(context, goal, 0)
}
_ => unreachable!(),
}
}
fn take_hypothesis(&mut self, hypotheses: &mut Vec<Tree>) -> Tree {
hypotheses.remove(self.rng.below(hypotheses.len()))
}
fn twin(&mut self, a: &Tree) -> Tree {
match self.rng.below(3) {
0 => Tree::Top,
1 => {
let junk = self.junk(2);
if self.rng.one_in(2) {
Tree::Plus(Box::new(a.clone()), Box::new(junk))
} else {
Tree::Plus(Box::new(junk), Box::new(a.clone()))
}
}
_ => a.clone(),
}
}
fn junk(&mut self, size: usize) -> Tree {
let mut choices: Vec<u8> = vec![b'v', b'v'];
if self.rules.units {
choices.push(b'1');
}
if self.rules.additives {
choices.push(b'T');
}
if self.rules.zero {
choices.push(b'0');
}
if size > 0 {
choices.extend(*b"tl");
if self.rules.additives {
choices.extend(*b"&+");
}
if self.rules.exponentials {
choices.push(b'!');
}
}
let boxed = |t: Tree| Box::new(t);
match choices[self.rng.below(choices.len())] {
b'v' => Tree::Atom(self.rng.below(self.atoms as usize) as u8),
b'1' => Tree::One,
b'T' => Tree::Top,
b'0' => Tree::Zero,
b't' => Tree::Tensor(boxed(self.junk(size - 1)), boxed(self.junk(size - 1))),
b'l' => Tree::Lolli(boxed(self.junk(size - 1)), boxed(self.junk(size - 1))),
b'&' => Tree::With(boxed(self.junk(size - 1)), boxed(self.junk(size - 1))),
b'+' => Tree::Plus(boxed(self.junk(size - 1)), boxed(self.junk(size - 1))),
b'!' => Tree::Bang(boxed(self.junk(size - 1))),
_ => unreachable!(),
}
}
}
pub(crate) fn sequent(formulas: &[Tree]) -> String {
let mut text = String::from("|-");
for (i, formula) in formulas.iter().enumerate() {
text.push_str(if i == 0 { " " } else { ", " });
text.push_str(&formula.to_string());
}
text
}
pub(crate) fn provable(rng: &mut Rng, rules: Rules, atoms: u8, budget: usize) -> Provable {
let mut generator = Generator { rng, rules, atoms };
let (formulas, copies) = generator.proof(budget);
Provable { formulas, copies }
}
pub(crate) fn mutate(rng: &mut Rng, formulas: &mut [Tree], atoms: u8) -> bool {
if rng.one_in(2)
&& transpose(
rng,
formulas.iter_mut().flat_map(|f| f.literals(true)).collect(),
)
{
return true;
}
let literals = formulas.iter_mut().flat_map(|f| f.literals(true));
shift(rng, literals.map(|(atom, _)| atom).collect(), atoms)
}
pub(crate) fn mutate_two_sided(
rng: &mut Rng,
hypotheses: &mut [Tree],
goal: &mut Tree,
atoms: u8,
) -> bool {
let mut literals: Vec<(&mut u8, bool)> = hypotheses
.iter_mut()
.flat_map(|h| h.literals(false))
.collect();
literals.extend(goal.literals(true));
if rng.one_in(2) && transpose(rng, literals) {
return true;
}
let literals = hypotheses
.iter_mut()
.flat_map(|h| h.literals(false))
.chain(goal.literals(true))
.map(|(atom, _)| atom)
.collect();
shift(rng, literals, atoms)
}
fn shift(rng: &mut Rng, mut literals: Vec<&mut u8>, atoms: u8) -> bool {
if literals.is_empty() || atoms < 2 {
return false;
}
let pick = rng.below(literals.len());
let shift = 1 + rng.below(atoms as usize - 1) as u8;
let atom = &mut *literals[pick];
*atom = (*atom + shift) % atoms;
true
}
fn transpose(rng: &mut Rng, mut literals: Vec<(&mut u8, bool)>) -> bool {
let pairs: Vec<(usize, usize)> = (0..literals.len())
.flat_map(|j| (0..j).map(move |i| (i, j)))
.filter(|&(i, j)| literals[i].1 == literals[j].1 && *literals[i].0 != *literals[j].0)
.collect();
if pairs.is_empty() {
return false;
}
let (i, j) = pairs[rng.below(pairs.len())];
let (left, right) = literals.split_at_mut(j);
std::mem::swap(left[i].0, right[0].0);
true
}
struct Generator<'a> {
rng: &'a mut Rng,
rules: Rules,
atoms: u8,
}
impl Generator<'_> {
fn proof(&mut self, budget: usize) -> (Vec<Tree>, u32) {
if budget <= 1 {
return (self.leaf(), 0);
}
let mut choices: Vec<u8> = vec![b'a', b'a', b't', b't', b'p', b'p'];
if self.rules.units {
choices.extend(*b"1b");
}
if self.rules.additives {
choices.extend(*b"&++T");
}
if self.rules.mix {
choices.push(b'm');
}
if self.rules.exponentials {
choices.extend(*b"dwc!");
}
match choices[self.rng.below(choices.len())] {
b'a' => (self.leaf(), 0),
b't' => {
let left_budget = 1 + self.rng.below(budget - 1);
let (mut left, lc) = self.proof(left_budget);
let (mut right, rc) = self.proof(budget - left_budget);
let a = left.swap_remove(self.rng.below(left.len()));
let b = right.swap_remove(self.rng.below(right.len()));
left.append(&mut right);
left.push(Tree::Tensor(Box::new(a), Box::new(b)));
(left, lc + rc)
}
b'p' => {
let (mut premise, copies) = self.proof(budget - 1);
if premise.len() < 2 {
if !self.rules.units {
return (premise, copies);
}
premise.push(Tree::Bot);
}
let a = premise.swap_remove(self.rng.below(premise.len()));
let b = premise.swap_remove(self.rng.below(premise.len()));
premise.push(Tree::Par(Box::new(a), Box::new(b)));
(premise, copies)
}
b'1' => (vec![Tree::One], 0),
b'b' => {
let (mut premise, copies) = self.proof(budget - 1);
premise.push(Tree::Bot);
(premise, copies)
}
b'&' => {
let (mut premise, copies) = self.proof(budget - 1);
let a = premise.swap_remove(self.rng.below(premise.len()));
let b = self.twin(&a, 2);
premise.push(Tree::With(Box::new(a), Box::new(b)));
(premise, 2 * copies)
}
b'+' => {
let (mut premise, copies) = self.proof(budget - 1);
let a = premise.swap_remove(self.rng.below(premise.len()));
let junk = self.junk(3);
premise.push(if self.rng.one_in(2) {
Tree::Plus(Box::new(a), Box::new(junk))
} else {
Tree::Plus(Box::new(junk), Box::new(a))
});
(premise, copies)
}
b'T' => {
let mut sequent = vec![Tree::Top];
for _ in 0..self.rng.below(3) {
sequent.push(self.junk(3));
}
(sequent, 0)
}
b'm' => {
let left_budget = 1 + self.rng.below(budget - 1);
let (mut left, lc) = self.proof(left_budget);
let (mut right, rc) = self.proof(budget - left_budget);
left.append(&mut right);
(left, lc + rc)
}
b'd' => {
let (mut premise, copies) = self.proof(budget - 1);
let a = premise.swap_remove(self.rng.below(premise.len()));
premise.push(Tree::Quest(Box::new(a)));
(premise, copies + 1)
}
b'w' => {
let (mut premise, copies) = self.proof(budget - 1);
let junk = self.junk(3);
premise.push(Tree::Quest(Box::new(junk)));
(premise, copies)
}
b'c' => {
let (mut premise, copies) = self.proof(budget - 1);
if !premise.iter().any(Tree::is_quest) {
let i = self.rng.below(premise.len());
let b = premise.swap_remove(i);
premise.push(Tree::Quest(Box::new(b)));
return (premise, copies + 1);
}
let a = premise.swap_remove(self.rng.below(premise.len()));
let (quests, rest): (Vec<Tree>, Vec<Tree>) =
premise.into_iter().partition(Tree::is_quest);
let mut sequent = rest.clone();
sequent.extend(rest);
sequent.extend(quests);
sequent.push(Tree::Tensor(Box::new(a.clone()), Box::new(a)));
(sequent, 2 * copies)
}
b'!' => {
let (mut premise, copies) = self.proof(budget - 1);
let a = premise.swap_remove(self.rng.below(premise.len()));
let mut derelicted = 0;
for f in premise.iter_mut() {
if !f.is_quest() {
let inner = std::mem::replace(f, Tree::One);
*f = Tree::Quest(Box::new(inner));
derelicted += 1;
}
}
premise.push(Tree::Bang(Box::new(a)));
(premise, copies + derelicted)
}
_ => unreachable!(),
}
}
fn leaf(&mut self) -> Vec<Tree> {
if self.rules.units && self.rng.one_in(4) {
return vec![Tree::One];
}
let a = self.rng.below(self.atoms as usize) as u8;
vec![Tree::Atom(a), Tree::Dual(a)]
}
fn twin(&mut self, a: &Tree, depth: usize) -> Tree {
let mut choices: Vec<u8> = vec![b'a', b'T', b'+', b'+'];
if self.rules.units {
choices.extend(*b"pt");
}
if depth > 0 {
choices.push(b'&');
}
let inner = |this: &mut Self| {
if depth > 0 {
this.twin(a, depth - 1)
} else {
a.clone()
}
};
match choices[self.rng.below(choices.len())] {
b'a' => a.clone(),
b'T' => Tree::Top,
b'+' => {
let (x, junk) = (inner(self), self.junk(2));
if self.rng.one_in(2) {
Tree::Plus(Box::new(x), Box::new(junk))
} else {
Tree::Plus(Box::new(junk), Box::new(x))
}
}
b'p' => Tree::Par(Box::new(inner(self)), Box::new(Tree::Bot)),
b't' => Tree::Tensor(Box::new(Tree::One), Box::new(inner(self))),
b'&' => {
let (x, y) = (inner(self), inner(self));
Tree::With(Box::new(x), Box::new(y))
}
_ => unreachable!(),
}
}
fn junk(&mut self, size: usize) -> Tree {
let mut choices: Vec<u8> = vec![b'v', b'd'];
if self.rules.units {
choices.extend(*b"1b");
}
if self.rules.additives {
choices.extend(*b"T0");
}
if size > 0 {
choices.extend(*b"tp");
if self.rules.additives {
choices.extend(*b"&+");
}
if self.rules.exponentials {
choices.extend(*b"!?");
}
}
let a = self.rng.below(self.atoms as usize) as u8;
let sub = |this: &mut Self| Box::new(this.junk(size - 1));
match choices[self.rng.below(choices.len())] {
b'v' => Tree::Atom(a),
b'd' => Tree::Dual(a),
b'1' => Tree::One,
b'b' => Tree::Bot,
b'T' => Tree::Top,
b'0' => Tree::Zero,
b't' => Tree::Tensor(sub(self), sub(self)),
b'p' => Tree::Par(sub(self), sub(self)),
b'&' => Tree::With(sub(self), sub(self)),
b'+' => Tree::Plus(sub(self), sub(self)),
b'!' => Tree::Bang(sub(self)),
b'?' => Tree::Quest(sub(self)),
_ => unreachable!(),
}
}
}
pub(crate) fn balanced(rng: &mut Rng, atoms: u8, pairs: usize, mix: bool) -> Vec<Tree> {
let mut formulas: Vec<Tree> = Vec::with_capacity(2 * pairs);
for _ in 0..pairs {
let a = rng.below(atoms as usize) as u8;
formulas.push(Tree::Atom(a));
formulas.push(Tree::Dual(a));
}
let tensors = if mix { rng.below(pairs) } else { pairs - 1 };
let pars = rng.below(2 * pairs - tensors);
let mut joins: Vec<bool> = vec![true; tensors];
joins.extend(vec![false; pars]);
for k in (1..joins.len()).rev() {
joins.swap(k, rng.below(k + 1));
}
for tensor in joins {
let a = formulas.swap_remove(rng.below(formulas.len()));
let b = formulas.swap_remove(rng.below(formulas.len()));
formulas.push(if tensor {
Tree::Tensor(Box::new(a), Box::new(b))
} else {
Tree::Par(Box::new(a), Box::new(b))
});
}
formulas
}
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
pub(crate) enum Lambek {
Atom(u8),
Tensor(Box<Self>, Box<Self>),
Under(Box<Self>, Box<Self>),
Over(Box<Self>, Box<Self>),
}
impl Display for Lambek {
fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
match self {
Self::Atom(a) => write!(f, "{}", char::from(b'a' + a)),
Self::Tensor(a, b) => write!(f, "({a} * {b})"),
Self::Under(a, b) => write!(f, "({a} \\ {b})"),
Self::Over(b, a) => write!(f, "({b} / {a})"),
}
}
}
pub(crate) fn lambek_text(hypotheses: &[Lambek], goal: &Lambek) -> String {
let hypotheses: Vec<String> = hypotheses.iter().map(ToString::to_string).collect();
format!("{} |- {goal}", hypotheses.join(", "))
}
pub(crate) fn lambek(rng: &mut Rng, atoms: u8, budget: usize, star: bool) -> (Vec<Lambek>, Lambek) {
use Lambek::*;
let b = Box::new;
if budget <= 1 || rng.below(5) == 0 {
let a = Atom(rng.below(usize::from(atoms)) as u8);
return (vec![a.clone()], a);
}
let least = if star { 1 } else { 2 };
match rng.below(5) {
0 => {
let (mut g, a) = lambek(rng, atoms, budget / 2, star);
let (d, c) = lambek(rng, atoms, budget - budget / 2, star);
g.extend(d);
(g, Tensor(b(a), b(c)))
}
1 => {
let (mut g, c) = lambek(rng, atoms, budget - 1, star);
if g.len() >= 2 {
let i = rng.below(g.len() - 1);
let (x, y) = (g.remove(i), g.remove(i));
g.insert(i, Tensor(b(x), b(y)));
}
(g, c)
}
2 => {
let (mut g, c) = lambek(rng, atoms, budget - 1, star);
if g.len() < least {
return (g, c);
}
if rng.below(2) == 0 {
let a = g.remove(0);
(g, Under(b(a), b(c)))
} else {
let a = g.pop().unwrap();
(g, Over(b(c), b(a)))
}
}
_ => {
let (g, a) = lambek(rng, atoms, budget / 2, star);
let (mut d, c) = lambek(rng, atoms, budget - budget / 2, star);
let k = rng.below(d.len().max(1));
if d.is_empty() || (g.is_empty() && !star) {
return (d, c);
}
let consequent = d.remove(k);
let mut middle = g;
if rng.below(2) == 0 {
middle.push(Under(b(a), b(consequent)));
} else {
middle.insert(0, Over(b(consequent), b(a)));
}
let rest = d.split_off(k);
d.extend(middle);
d.extend(rest);
(d, c)
}
}
}
pub(crate) fn written(
rng: &mut Rng,
formulas: &[Tree],
) -> (String, Vec<crate::linear::occurrences::Written>) {
use crate::linear::occurrences::Side;
let left = rng.below(formulas.len() + 1);
let mut text = String::new();
let mut record = Vec::new();
for (i, formula) in formulas.iter().enumerate() {
if i == left {
text.push_str(if i == 0 { "|- " } else { " |- " });
} else if i > 0 {
text.push_str(", ");
}
let context = if i < left { Side::Input } else { Side::Output };
write_at(rng, formula, context, &mut text, &mut record);
}
if left == formulas.len() {
text.push_str(" |-");
}
(text, record)
}
fn write_at(
rng: &mut Rng,
formula: &Tree,
context: crate::linear::occurrences::Side,
text: &mut String,
record: &mut Vec<crate::linear::occurrences::Written>,
) {
use crate::linear::occurrences::{Side, Written};
use Tree::*;
let negated = match formula {
Atom(_) => context == Side::Input,
Dual(_) => context == Side::Output,
_ => rng.one_in(4),
};
let double = !negated && rng.one_in(8);
let side = if negated { !context } else { context };
let output = side == Side::Output;
text.push_str(match (negated, double) {
(true, _) => "~(",
(false, true) => "~~(",
(false, false) => "",
});
let binary = |rng: &mut Rng,
text: &mut String,
record: &mut Vec<Written>,
(l, op, r): (&Tree, &str, &Tree),
implication: bool| {
record.push(Written::new(side, implication));
text.push('(');
write_at(rng, l, if implication { !side } else { side }, text, record);
text.push_str(op);
write_at(rng, r, side, text, record);
text.push(')');
};
match formula {
Atom(a) | Dual(a) => {
record.push(Written::new(side, false));
text.push((b'a' + a) as char);
}
One | Bot | Top | Zero => {
record.push(Written::new(side, false));
let (out, input) = match formula {
One => ("1", "bot"),
Bot => ("bot", "1"),
Top => ("top", "0"),
_ => ("0", "top"),
};
text.push_str(if output { out } else { input });
}
Tensor(l, r) if !output && rng.one_in(2) => binary(rng, text, record, (l, " -o ", r), true),
Par(l, r) if output && rng.one_in(2) => binary(rng, text, record, (l, " -o ", r), true),
Tensor(l, r) | Par(l, r) | With(l, r) | Plus(l, r) => {
let op = match (formula, output) {
(Tensor(..), true) | (Par(..), false) => " * ",
(Par(..), true) | (Tensor(..), false) => " par ",
(With(..), true) | (Plus(..), false) => " & ",
_ => " + ",
};
binary(rng, text, record, (l, op, r), false);
}
Bang(a) | Quest(a) => {
record.push(Written::new(side, false));
let bang = matches!(formula, Bang(_)) == output;
text.push(if bang { '!' } else { '?' });
write_at(rng, a, side, text, record);
}
Lolli(..) => unreachable!("a classical sequent is generated one-sided"),
}
if negated || double {
text.push(')');
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn intuitionistic_proofs_contract() {
for (n, rules) in IllRules::ALL.into_iter().enumerate() {
if !rules.exponentials {
continue;
}
let mut rng = Rng::new(100 + n as u64);
let contracted = (0..40)
.filter(|_| {
let budget = 2 + rng.below(9);
ill(&mut rng, rules, 3, budget).contractions > 0
})
.count();
assert!(contracted >= 8, "{rules:?}: {contracted} of 40 contract");
}
}
#[test]
fn some_mutants_reach_a_search() {
use crate::linear::search::{Options, Refutation, Verdict, prove};
use crate::linear::{Mode, Sequent};
let searched = |text: &str, mode: Mode| {
let sequent: Sequent = text.parse().unwrap();
match prove(&sequent, mode, &Options::default()).unwrap().verdict {
Verdict::Unprovable(disproof) => {
matches!(disproof.refutation(), Refutation::Exhausted)
}
_ => true,
}
};
for (i, rules) in Rules::ALL.into_iter().enumerate() {
if rules.additives || rules.exponentials {
continue;
}
let mode = Mode::CLASSICAL;
let mode = if rules.mix { mode.with_mix() } else { mode };
let mut rng = Rng::new(i as u64);
let (mut mutants, mut reached) = (0, 0);
for _ in 0..100 {
let budget = 2 + rng.below(9);
let mut formulas = provable(&mut rng, rules, 3, budget).formulas;
if mutate(&mut rng, &mut formulas, 3) {
mutants += 1;
reached += u32::from(searched(&sequent(&formulas), mode));
}
}
assert!(reached * 12 >= mutants, "{rules:?}: {reached} of {mutants}");
}
for (n, rules) in IllRules::ALL.into_iter().enumerate() {
if rules.additives || rules.exponentials {
continue;
}
let mut rng = Rng::new(100 + n as u64);
let (mut mutants, mut reached) = (0, 0);
for _ in 0..100 {
let budget = 2 + rng.below(9);
let Ill {
mut hypotheses,
mut goal,
..
} = ill(&mut rng, rules, 3, budget);
if mutate_two_sided(&mut rng, &mut hypotheses, &mut goal, 3) {
mutants += 1;
let text = two_sided(&hypotheses, &goal);
reached += u32::from(searched(&text, Mode::INTUITIONISTIC));
}
}
assert!(reached * 12 >= mutants, "{rules:?}: {reached} of {mutants}");
}
}
}