use oxilean_kernel::{BinderInfo, Declaration, Environment, Expr, Level, Name};
use super::types::{
BiFormula, BoundedLinearLogic, CoherenceSpace, DialecticaTransform, GeometryOfInteraction,
Heap, LinFormula, LinSequent, LinearFormula, LinearSequent, LinearTypeSystem, Link, LlFormula,
LlGame, LlRule, PhaseSpace, ProofStructure, SepLogicTriple,
};
pub fn app(f: Expr, a: Expr) -> Expr {
Expr::App(Box::new(f), Box::new(a))
}
pub fn app2(f: Expr, a: Expr, b: Expr) -> Expr {
app(app(f, a), b)
}
pub fn app3(f: Expr, a: Expr, b: Expr, c: Expr) -> Expr {
app(app2(f, a, b), c)
}
pub fn cst(s: &str) -> Expr {
Expr::Const(Name::str(s), vec![])
}
pub fn prop() -> Expr {
Expr::Sort(Level::zero())
}
pub fn type0() -> Expr {
Expr::Sort(Level::succ(Level::zero()))
}
pub fn pi(bi: BinderInfo, name: &str, dom: Expr, body: Expr) -> Expr {
Expr::Pi(bi, Name::str(name), Box::new(dom), Box::new(body))
}
pub fn arrow(a: Expr, b: Expr) -> Expr {
pi(BinderInfo::Default, "_", a, b)
}
pub fn impl_pi(name: &str, dom: Expr, body: Expr) -> Expr {
pi(BinderInfo::Implicit, name, dom, body)
}
pub fn bvar(n: u32) -> Expr {
Expr::BVar(n)
}
pub fn nat_ty() -> Expr {
cst("Nat")
}
pub fn bool_ty() -> Expr {
cst("Bool")
}
pub fn list_ty(elem: Expr) -> Expr {
app(cst("List"), elem)
}
pub fn linear_formula_ty() -> Expr {
type0()
}
pub fn tensor_ty() -> Expr {
arrow(
cst("LinearFormula"),
arrow(cst("LinearFormula"), cst("LinearFormula")),
)
}
pub fn par_ty() -> Expr {
arrow(
cst("LinearFormula"),
arrow(cst("LinearFormula"), cst("LinearFormula")),
)
}
pub fn with_ty() -> Expr {
arrow(
cst("LinearFormula"),
arrow(cst("LinearFormula"), cst("LinearFormula")),
)
}
pub fn plus_ty() -> Expr {
arrow(
cst("LinearFormula"),
arrow(cst("LinearFormula"), cst("LinearFormula")),
)
}
pub fn bang_ty() -> Expr {
arrow(cst("LinearFormula"), cst("LinearFormula"))
}
pub fn why_not_ty() -> Expr {
arrow(cst("LinearFormula"), cst("LinearFormula"))
}
pub fn linear_neg_ty() -> Expr {
arrow(cst("LinearFormula"), cst("LinearFormula"))
}
pub fn lollipop_ty() -> Expr {
arrow(
cst("LinearFormula"),
arrow(cst("LinearFormula"), cst("LinearFormula")),
)
}
pub fn mult_unit_ty() -> Expr {
cst("LinearFormula")
}
pub fn add_top_ty() -> Expr {
cst("LinearFormula")
}
pub fn mult_bot_ty() -> Expr {
cst("LinearFormula")
}
pub fn add_zero_ty() -> Expr {
cst("LinearFormula")
}
pub fn linear_context_ty() -> Expr {
type0()
}
pub fn linear_sequent_ty() -> Expr {
arrow(cst("LinearContext"), prop())
}
pub fn provable_ll_ty() -> Expr {
arrow(cst("LinearContext"), prop())
}
pub fn provable_mll_ty() -> Expr {
arrow(cst("LinearContext"), prop())
}
pub fn provable_mall_ty() -> Expr {
arrow(cst("LinearContext"), prop())
}
pub fn cut_elim_ll_ty() -> Expr {
impl_pi(
"gamma",
cst("LinearContext"),
arrow(
app(cst("ProvableLL"), bvar(0)),
app(cst("ProvableLL"), bvar(1)),
),
)
}
pub fn exchange_rule_ty() -> Expr {
impl_pi(
"gamma",
cst("LinearContext"),
impl_pi(
"delta",
cst("LinearContext"),
arrow(
app2(cst("Permutation"), bvar(1), bvar(0)),
arrow(
app(cst("ProvableLL"), bvar(2)),
app(cst("ProvableLL"), bvar(2)),
),
),
),
)
}
pub fn tensor_intro_ty() -> Expr {
arrow(
cst("LinearContext"),
arrow(
cst("LinearContext"),
arrow(
cst("LinearFormula"),
arrow(
cst("LinearFormula"),
arrow(
app(cst("ProvableLL"), bvar(3)),
arrow(
app(cst("ProvableLL"), bvar(3)),
app(cst("ProvableLL"), bvar(4)),
),
),
),
),
),
)
}
pub fn bang_intro_ty() -> Expr {
arrow(
cst("LinearContext"),
arrow(
cst("LinearFormula"),
arrow(
app(cst("ProvableLL"), bvar(1)),
app(cst("ProvableLL"), bvar(2)),
),
),
)
}
pub fn dereliction_ty() -> Expr {
arrow(
cst("LinearFormula"),
arrow(
app(cst("ProvableLL"), cst("LinearContext")),
app(cst("ProvableLL"), cst("LinearContext")),
),
)
}
pub fn proof_structure_ty() -> Expr {
type0()
}
pub fn is_correct_proof_net_ty() -> Expr {
arrow(cst("ProofStructure"), prop())
}
pub fn proof_net_to_sequent_ty() -> Expr {
impl_pi(
"ps",
cst("ProofStructure"),
arrow(
app(cst("IsCorrectProofNet"), bvar(0)),
app(cst("ProvableMLL"), app(cst("ConclusionOf"), bvar(1))),
),
)
}
pub fn sequent_to_proof_net_ty() -> Expr {
impl_pi(
"gamma",
cst("LinearContext"),
arrow(
app(cst("ProvableMLL"), bvar(0)),
app2(
cst("Exists"),
cst("ProofStructure"),
cst("IsCorrectProofNet"),
),
),
)
}
pub fn phase_space_ty() -> Expr {
type0()
}
pub fn fact_ty() -> Expr {
arrow(
cst("PhaseSpace"),
arrow(app(cst("Set"), cst("PhaseSpace")), prop()),
)
}
pub fn phase_semantics_valid_ty() -> Expr {
arrow(cst("LinearFormula"), prop())
}
pub fn phase_completeness_ty() -> Expr {
impl_pi(
"a",
cst("LinearFormula"),
arrow(
app(cst("PhaseSemanticsValid"), bvar(0)),
app(cst("ProvableLL"), app(cst("SingletonCtx"), bvar(1))),
),
)
}
pub fn coherence_space_ty() -> Expr {
type0()
}
pub fn web_of_ty() -> Expr {
arrow(cst("CoherenceSpace"), type0())
}
pub fn clique_ty() -> Expr {
arrow(cst("CoherenceSpace"), arrow(type0(), prop()))
}
pub fn coherence_tensor_ty() -> Expr {
arrow(
cst("CoherenceSpace"),
arrow(cst("CoherenceSpace"), cst("CoherenceSpace")),
)
}
pub fn coherence_linear_map_ty() -> Expr {
arrow(cst("CoherenceSpace"), arrow(cst("CoherenceSpace"), type0()))
}
pub fn arena_ty() -> Expr {
type0()
}
pub fn position_ty() -> Expr {
arrow(cst("Arena"), type0())
}
pub fn strategy_ty() -> Expr {
arrow(cst("Arena"), type0())
}
pub fn innocent_strategy_ty() -> Expr {
arrow(cst("Strategy"), prop())
}
pub fn winning_strategy_ty() -> Expr {
arrow(cst("Strategy"), prop())
}
pub fn game_compose_ty() -> Expr {
arrow(cst("Strategy"), arrow(cst("Strategy"), cst("Strategy")))
}
pub fn game_semantics_soundness_ty() -> Expr {
impl_pi(
"gamma",
cst("LinearContext"),
arrow(
app(cst("ProvableLL"), bvar(0)),
app2(
cst("Exists"),
cst("Strategy"),
app2(cst("And"), cst("InnocentStrategy"), cst("WinningStrategy")),
),
),
)
}
pub fn relevant_formula_ty() -> Expr {
type0()
}
pub fn provable_r_ty() -> Expr {
arrow(cst("RelevantFormula"), prop())
}
pub fn contraction_rule_ty() -> Expr {
impl_pi(
"a",
cst("RelevantFormula"),
impl_pi(
"b",
cst("RelevantFormula"),
arrow(
app2(
cst("ProvableR"),
app2(cst("Arr"), bvar(1), app2(cst("Arr"), bvar(2), bvar(1))),
bvar(0),
),
app2(
cst("ProvableR"),
app2(cst("Arr"), bvar(2), bvar(1)),
bvar(1),
),
),
),
)
}
pub fn affine_formula_ty() -> Expr {
type0()
}
pub fn provable_aff_ty() -> Expr {
arrow(cst("AffineFormula"), prop())
}
pub fn weakening_rule_ty() -> Expr {
impl_pi(
"gamma",
cst("LinearContext"),
impl_pi(
"a",
cst("LinearFormula"),
arrow(
app(cst("ProvableLL"), bvar(1)),
app(cst("ProvableLL"), bvar(2)),
),
),
)
}
pub fn bi_formula_ty() -> Expr {
type0()
}
pub fn sep_conj_ty() -> Expr {
arrow(cst("BIFormula"), arrow(cst("BIFormula"), cst("BIFormula")))
}
pub fn sep_impl_ty() -> Expr {
arrow(cst("BIFormula"), arrow(cst("BIFormula"), cst("BIFormula")))
}
pub fn heap_ty() -> Expr {
type0()
}
pub fn disjoint_heaps_ty() -> Expr {
arrow(cst("Heap"), arrow(cst("Heap"), prop()))
}
pub fn sep_conj_semantics_ty() -> Expr {
impl_pi(
"h",
cst("Heap"),
impl_pi(
"p",
cst("BIFormula"),
impl_pi(
"q",
cst("BIFormula"),
app2(
cst("Iff"),
app2(
cst("Satisfies"),
bvar(2),
app2(cst("SepConj"), bvar(1), bvar(0)),
),
app2(cst("Exists"), cst("Heap"), cst("DisjointHeaps")),
),
),
),
)
}
pub fn frame_rule_ty() -> Expr {
arrow(
cst("BIFormula"),
arrow(
cst("BIFormula"),
arrow(
cst("BIFormula"),
arrow(
app3(cst("Hoare"), bvar(2), cst("Command"), bvar(1)),
app3(
cst("Hoare"),
app2(cst("SepConj"), bvar(3), bvar(0)),
cst("Command"),
app2(cst("SepConj"), bvar(2), bvar(1)),
),
),
),
),
)
}
pub fn build_linear_logic_env(env: &mut Environment) {
let axioms: &[(&str, Expr)] = &[
("LinearFormula", linear_formula_ty()),
("Tensor", tensor_ty()),
("Par", par_ty()),
("With", with_ty()),
("Plus", plus_ty()),
("Bang", bang_ty()),
("WhyNot", why_not_ty()),
("LinearNeg", linear_neg_ty()),
("Lollipop", lollipop_ty()),
("MultUnit", mult_unit_ty()),
("AddTop", add_top_ty()),
("MultBot", mult_bot_ty()),
("AddZero", add_zero_ty()),
("LinearContext", linear_context_ty()),
("LinearSequent", linear_sequent_ty()),
("ProvableLL", provable_ll_ty()),
("ProvableMLL", provable_mll_ty()),
("ProvableMALL", provable_mall_ty()),
("CutElimLL", cut_elim_ll_ty()),
("ExchangeRule", exchange_rule_ty()),
("TensorIntro", tensor_intro_ty()),
("BangIntro", bang_intro_ty()),
("Dereliction", dereliction_ty()),
(
"Permutation",
arrow(cst("LinearContext"), arrow(cst("LinearContext"), prop())),
),
(
"SingletonCtx",
arrow(cst("LinearFormula"), cst("LinearContext")),
),
(
"ConclusionOf",
arrow(cst("ProofStructure"), cst("LinearContext")),
),
("ProofStructure", proof_structure_ty()),
("IsCorrectProofNet", is_correct_proof_net_ty()),
("ProofNetToSequent", proof_net_to_sequent_ty()),
("SequentToProofNet", sequent_to_proof_net_ty()),
("PhaseSpace", phase_space_ty()),
("Fact", fact_ty()),
("PhaseSemanticsValid", phase_semantics_valid_ty()),
("PhaseCompleteness", phase_completeness_ty()),
("CoherenceSpace", coherence_space_ty()),
("WebOf", web_of_ty()),
("Clique", clique_ty()),
("CoherenceTensor", coherence_tensor_ty()),
("CoherenceLinearMap", coherence_linear_map_ty()),
("Arena", arena_ty()),
("Position", position_ty()),
("Strategy", strategy_ty()),
("InnocentStrategy", innocent_strategy_ty()),
("WinningStrategy", winning_strategy_ty()),
("GameCompose", game_compose_ty()),
("GameSemanticsSoundness", game_semantics_soundness_ty()),
("RelevantFormula", relevant_formula_ty()),
("ProvableR", provable_r_ty()),
("ContractionRule", contraction_rule_ty()),
("AffineFormula", affine_formula_ty()),
("ProvableAff", provable_aff_ty()),
("WeakeningRule", weakening_rule_ty()),
(
"Arr",
arrow(
cst("RelevantFormula"),
arrow(cst("RelevantFormula"), cst("RelevantFormula")),
),
),
("BIFormula", bi_formula_ty()),
("SepConj", sep_conj_ty()),
("SepImpl", sep_impl_ty()),
("Heap", heap_ty()),
("DisjointHeaps", disjoint_heaps_ty()),
(
"Satisfies",
arrow(cst("Heap"), arrow(cst("BIFormula"), prop())),
),
(
"Hoare",
arrow(
cst("BIFormula"),
arrow(cst("Command"), arrow(cst("BIFormula"), prop())),
),
),
("Command", type0()),
("SepConjSemantics", sep_conj_semantics_ty()),
("FrameRule", frame_rule_ty()),
];
for (name, ty) in axioms {
env.add(Declaration::Axiom {
name: Name::str(*name),
univ_params: vec![],
ty: ty.clone(),
})
.ok();
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_linear_formula_dual_involutive() {
let a = LinFormula::Atom("A".to_string());
let b = LinFormula::Tensor(
Box::new(LinFormula::Atom("A".to_string())),
Box::new(LinFormula::Atom("B".to_string())),
);
assert_eq!(a.dual().dual(), a);
assert!(matches!(b.dual(), LinFormula::Par(_, _)));
assert_eq!(b.dual().dual(), b);
}
#[test]
fn test_linear_formula_lollipop() {
let a = LinFormula::Atom("A".to_string());
let b = LinFormula::Atom("B".to_string());
let lol = LinFormula::lollipop(a, b);
assert!(matches!(lol, LinFormula::Par(_, _)));
}
#[test]
fn test_linear_formula_complexity() {
let a = LinFormula::Atom("A".to_string());
let b = LinFormula::Atom("B".to_string());
let t = LinFormula::Tensor(Box::new(a), Box::new(b));
assert_eq!(t.complexity(), 1);
let bang_t = LinFormula::Bang(Box::new(t.clone()));
assert_eq!(bang_t.complexity(), 2);
}
#[test]
fn test_sequent_is_axiom() {
let a = LinFormula::Atom("A".to_string());
let seq = LinSequent::new(vec![a.clone(), a.dual()]);
assert!(seq.is_axiom());
let b = LinFormula::Atom("B".to_string());
let seq2 = LinSequent::new(vec![a, b]);
assert!(!seq2.is_axiom());
}
#[test]
fn test_proof_structure_correct() {
let mut ps = ProofStructure::new(2);
ps.add_link(Link::axiom(0, 1));
assert!(ps.is_correct());
}
#[test]
fn test_proof_structure_incorrect_cycle() {
let mut ps = ProofStructure::new(4);
ps.add_link(Link::axiom(0, 1));
assert!(!ps.is_correct());
}
#[test]
fn test_coherence_space_clique() {
let cs = CoherenceSpace::complete(3);
assert!(cs.is_clique(&[0, 1, 2]));
let cs_flat = CoherenceSpace::flat(3);
assert!(cs_flat.is_clique(&[0]));
assert!(!cs_flat.is_clique(&[0, 1]));
}
#[test]
fn test_phase_space_trivial() {
let ps = PhaseSpace::trivial();
let all = vec![true];
assert!(ps.is_fact(&all));
}
#[test]
fn test_heap_sep_split() {
let h = Heap::singleton(1, 10)
.union(&Heap::singleton(2, 20))
.expect("union should succeed");
let result = h.sep_split(|h1| h1.read(1) == Some(10), |h2| h2.read(2) == Some(20));
assert!(result.is_some());
}
#[test]
fn test_build_linear_logic_env() {
let mut env = Environment::new();
build_linear_logic_env(&mut env);
assert!(env.get(&Name::str("LinearFormula")).is_some());
assert!(env.get(&Name::str("Tensor")).is_some());
assert!(env.get(&Name::str("Bang")).is_some());
assert!(env.get(&Name::str("SepConj")).is_some());
assert!(env.get(&Name::str("CoherenceSpace")).is_some());
}
}
pub fn build_env(env: &mut oxilean_kernel::Environment) {
build_linear_logic_env(env);
}
#[cfg(test)]
mod ll_ext_tests {
use super::*;
#[test]
fn test_ll_formula_negation() {
let a = LlFormula::atom("A");
let neg_a = a.linear_negation();
assert!(matches!(neg_a, LlFormula::Neg(_)));
let one = LlFormula::One;
assert_eq!(one.linear_negation(), LlFormula::Bottom);
}
#[test]
fn test_ll_formula_types() {
let a = LlFormula::tensor(LlFormula::atom("A"), LlFormula::atom("B"));
assert!(a.is_multiplicative());
let b = LlFormula::with_op(LlFormula::atom("A"), LlFormula::atom("B"));
assert!(b.is_additive());
let c = LlFormula::of_course(LlFormula::atom("A"));
assert!(c.is_exponential());
}
#[test]
fn test_ll_rules() {
let rules = [
LlRule::Ax,
LlRule::Cut,
LlRule::TensorR,
LlRule::ParR,
LlRule::Contraction,
LlRule::Weakening,
];
for r in &rules {
assert!(!r.name().is_empty());
}
assert!(LlRule::Contraction.is_structural());
assert!(!LlRule::TensorR.is_structural());
}
#[test]
fn test_linear_type_system() {
let rust = LinearTypeSystem::rust_ownership();
assert!(rust.prevents_use_after_free());
assert!(rust.affine_types);
}
#[test]
fn test_phase_semantics() {
let ps = PhaseSpace::new("(M, *)");
assert!(!ps.completeness_description().is_empty());
}
}
#[cfg(test)]
mod ll_game_tests {
use super::*;
#[test]
fn test_ll_game() {
let g = LlGame::new("A tensor B");
assert!(!g.abramsky_jagadeesan_description().is_empty());
}
#[test]
fn test_goi() {
let goi = GeometryOfInteraction::girard_goi();
assert!(!goi.dynamic_description().is_empty());
}
}
#[cfg(test)]
mod sep_logic_tests {
use super::*;
#[test]
fn test_bi_formula() {
let emp = BiFormula::Emp;
assert!(emp.is_separation_connective());
let sc = BiFormula::sep_conj(BiFormula::atom("P"), BiFormula::atom("Q"));
assert!(sc.is_separation_connective());
}
#[test]
fn test_separation_logic() {
let triple = SepLogicTriple::new("x -> 3", "*x := 5", "x -> 5");
let framed = triple.frame_rule("y -> 7");
assert!(framed.precondition.contains("y -> 7"));
assert!(!triple.display().is_empty());
}
}
#[cfg(test)]
mod dialectica_tests {
use super::*;
#[test]
fn test_dialectica() {
let dt = DialecticaTransform::new("A -> B", "A_d -> B_d");
assert!(!dt.de_paiva_description().is_empty());
}
#[test]
fn test_bll() {
let bll = BoundedLinearLogic::new("n^2");
assert!(bll.captures_ptime());
assert!(!bll.description().is_empty());
}
}