1use logicaffeine_kernel::{Context, KernelError, KernelResult, Term};
13
14use crate::{DerivationTree, InferenceRule, ProofExpr, ProofTerm};
15
16struct InductionState {
25 fix_name: String,
27 ihs: Vec<(String, ProofExpr)>,
31}
32
33pub struct CertificationContext<'a> {
65 kernel_ctx: &'a Context,
66 locals: Vec<String>,
68 local_hyps: Vec<std::sync::Arc<(ProofExpr, Term)>>,
81 induction_state: Option<InductionState>,
83}
84
85impl<'a> CertificationContext<'a> {
86 pub fn new(kernel_ctx: &'a Context) -> Self {
87 Self {
88 kernel_ctx,
89 locals: Vec::new(),
90 local_hyps: Vec::new(),
91 induction_state: None,
92 }
93 }
94
95 fn with_local(&self, name: &str) -> Self {
97 let mut new_locals = self.locals.clone();
98 new_locals.push(name.to_string());
99 Self {
100 kernel_ctx: self.kernel_ctx,
101 locals: new_locals,
102 local_hyps: self.local_hyps.clone(),
103 induction_state: self.induction_state.clone(),
104 }
105 }
106
107 fn with_local_hyp(&self, prop: &ProofExpr, var: &str) -> Self {
110 self.with_local_hyp_term(prop, Term::Var(var.to_string()))
111 }
112
113 fn with_local_hyp_term(&self, prop: &ProofExpr, witness: Term) -> Self {
118 let mut new_hyps = self.local_hyps.clone();
119 new_hyps.push(std::sync::Arc::new((prop.clone(), witness)));
120 Self {
121 kernel_ctx: self.kernel_ctx,
122 locals: self.locals.clone(),
123 local_hyps: new_hyps,
124 induction_state: self.induction_state.clone(),
125 }
126 }
127
128 fn fresh_hyp_name(&self) -> String {
130 format!("_hyp{}", self.local_hyps.len())
131 }
132
133 fn get_local_hyp(&self, conclusion: &ProofExpr) -> Option<Term> {
135 self.local_hyps
136 .iter()
137 .rev()
138 .find(|h| h.0 == *conclusion)
139 .map(|h| h.1.clone())
140 }
141
142 fn with_induction(&self, fix_name: &str, step_var: &str, ih: ProofExpr) -> Self {
144 self.with_induction_multi(fix_name, vec![(step_var.to_string(), ih)])
145 }
146
147 fn with_induction_multi(&self, fix_name: &str, ihs: Vec<(String, ProofExpr)>) -> Self {
150 Self {
151 kernel_ctx: self.kernel_ctx,
152 locals: self.locals.clone(),
153 local_hyps: self.local_hyps.clone(),
154 induction_state: Some(InductionState {
155 fix_name: fix_name.to_string(),
156 ihs,
157 }),
158 }
159 }
160
161 fn is_local(&self, name: &str) -> bool {
163 self.locals.iter().any(|n| n == name)
164 }
165
166 fn get_ih_term(&self, conclusion: &ProofExpr) -> Option<Term> {
169 let state = self.induction_state.as_ref()?;
170 for (var, ih) in &state.ihs {
171 if conclusions_match(conclusion, ih) {
172 return Some(Term::App(
174 Box::new(Term::Var(state.fix_name.clone())),
175 Box::new(Term::Var(var.clone())),
176 ));
177 }
178 }
179 None
180 }
181}
182
183impl Clone for InductionState {
184 fn clone(&self) -> Self {
185 Self {
186 fix_name: self.fix_name.clone(),
187 ihs: self.ihs.clone(),
188 }
189 }
190}
191
192fn conclusions_match(a: &ProofExpr, b: &ProofExpr) -> bool {
195 a == b
196}
197
198pub fn certify(tree: &DerivationTree, ctx: &CertificationContext) -> KernelResult<Term> {
238 match &tree.rule {
239 InferenceRule::Axiom | InferenceRule::PremiseMatch => {
241 certify_hypothesis(&tree.conclusion, ctx)
242 }
243
244 InferenceRule::ModusPonens => {
247 if tree.premises.len() != 2 {
248 return Err(KernelError::CertificationError(
249 "ModusPonens requires exactly 2 premises".to_string(),
250 ));
251 }
252 let impl_term = certify(&tree.premises[0], ctx)?;
253 let arg_term = certify(&tree.premises[1], ctx)?;
254 Ok(Term::App(Box::new(impl_term), Box::new(arg_term)))
255 }
256
257 InferenceRule::ModusTollens => {
261 if tree.premises.len() != 2 {
262 return Err(KernelError::CertificationError(
263 "ModusTollens requires exactly 2 premises (implication, negated consequent)"
264 .to_string(),
265 ));
266 }
267 let p = match &tree.conclusion {
268 ProofExpr::Not(p) => p.as_ref().clone(),
269 _ => {
270 return Err(KernelError::CertificationError(
271 "ModusTollens conclusion must be a negation".to_string(),
272 ))
273 }
274 };
275 let p_type = proof_expr_to_type(&p)?;
276 let impl_proof = certify(&tree.premises[0], ctx)?;
277 let neg_q_proof = certify(&tree.premises[1], ctx)?;
278 let hp = "__mt_hp".to_string();
279 Ok(Term::Lambda {
281 param: hp.clone(),
282 param_type: Box::new(p_type),
283 body: Box::new(Term::App(
284 Box::new(neg_q_proof),
285 Box::new(Term::App(Box::new(impl_proof), Box::new(Term::Var(hp)))),
286 )),
287 })
288 }
289
290 InferenceRule::Reflexivity => {
296 let (l, r) = match &tree.conclusion {
297 ProofExpr::Identity(l, r) => (l, r),
298 _ => {
299 return Err(KernelError::CertificationError(
300 "Reflexivity conclusion must be an Identity".to_string(),
301 ))
302 }
303 };
304 let domain = Term::Global(resolved_identity_domain(l, r, ctx.kernel_ctx));
305 let term = proof_term_to_kernel_term(l)?;
306 Ok(Term::App(
307 Box::new(Term::App(
308 Box::new(Term::Global("refl".to_string())),
309 Box::new(domain),
310 )),
311 Box::new(term),
312 ))
313 }
314
315 InferenceRule::ExFalso => {
318 if tree.premises.len() != 1 {
319 return Err(KernelError::CertificationError(
320 "ExFalso requires exactly 1 premise (a proof of False)".to_string(),
321 ));
322 }
323 let false_proof = certify(&tree.premises[0], ctx)?;
324 let goal_type = proof_expr_to_type_ctx(&tree.conclusion, ctx.kernel_ctx)?;
325 Ok(Term::Match {
326 discriminant: Box::new(false_proof),
327 motive: Box::new(Term::Lambda {
328 param: "_".to_string(),
329 param_type: Box::new(Term::Global("False".to_string())),
330 body: Box::new(goal_type),
331 }),
332 cases: vec![],
333 })
334 }
335
336 InferenceRule::ConjunctionIntro => {
339 if tree.premises.len() != 2 {
340 return Err(KernelError::CertificationError(
341 "ConjunctionIntro requires exactly 2 premises".to_string(),
342 ));
343 }
344 let (p_type, q_type) = extract_and_types(&tree.conclusion)?;
345 let p_term = certify(&tree.premises[0], ctx)?;
346 let q_term = certify(&tree.premises[1], ctx)?;
347
348 let conj = Term::Global("conj".to_string());
350 let applied = Term::App(
351 Box::new(Term::App(
352 Box::new(Term::App(
353 Box::new(Term::App(Box::new(conj), Box::new(p_type))),
354 Box::new(q_type),
355 )),
356 Box::new(p_term),
357 )),
358 Box::new(q_term),
359 );
360 Ok(applied)
361 }
362
363 InferenceRule::DisjunctionIntro => {
367 if tree.premises.len() != 1 {
368 return Err(KernelError::CertificationError(
369 "DisjunctionIntro requires exactly 1 premise".to_string(),
370 ));
371 }
372 let (p, q) = match &tree.conclusion {
373 ProofExpr::Or(p, q) => (p.as_ref().clone(), q.as_ref().clone()),
374 _ => {
375 return Err(KernelError::CertificationError(
376 "DisjunctionIntro conclusion must be Or".to_string(),
377 ))
378 }
379 };
380 let proved = &tree.premises[0].conclusion;
381 let ctor = if proved == &p {
382 "left"
383 } else if proved == &q {
384 "right"
385 } else {
386 return Err(KernelError::CertificationError(
387 "DisjunctionIntro premise proves neither disjunct".to_string(),
388 ));
389 };
390 let p_type = proof_expr_to_type(&p)?;
391 let q_type = proof_expr_to_type(&q)?;
392 let proof_term = certify(&tree.premises[0], ctx)?;
393
394 let applied = Term::App(
396 Box::new(Term::App(
397 Box::new(Term::App(
398 Box::new(Term::Global(ctor.to_string())),
399 Box::new(p_type),
400 )),
401 Box::new(q_type),
402 )),
403 Box::new(proof_term),
404 );
405 Ok(applied)
406 }
407
408 InferenceRule::UniversalInst(witness) => {
411 if tree.premises.len() != 1 {
412 return Err(KernelError::CertificationError(
413 "UniversalInst requires exactly 1 premise".to_string(),
414 ));
415 }
416 let forall_proof = certify(&tree.premises[0], ctx)?;
417 let witness_term = if ctx.is_local(witness) {
419 Term::Var(witness.clone())
420 } else {
421 Term::Global(witness.clone())
422 };
423 Ok(Term::App(Box::new(forall_proof), Box::new(witness_term)))
424 }
425
426 InferenceRule::UniversalInstTerm(witness) => {
430 if tree.premises.len() != 1 {
431 return Err(KernelError::CertificationError(
432 "UniversalInstTerm requires exactly 1 premise".to_string(),
433 ));
434 }
435 let forall_proof = certify(&tree.premises[0], ctx)?;
436 let witness_term = match witness {
437 ProofTerm::Constant(name) | ProofTerm::Variable(name) if ctx.is_local(name) => {
438 Term::Var(name.clone())
439 }
440 _ => proof_term_to_kernel_term(witness)?,
441 };
442 Ok(Term::App(Box::new(forall_proof), Box::new(witness_term)))
443 }
444
445 InferenceRule::UniversalIntro { variable, var_type } => {
448 if tree.premises.len() != 1 {
449 return Err(KernelError::CertificationError(
450 "UniversalIntro requires exactly 1 premise".to_string(),
451 ));
452 }
453
454 let domain = match &tree.conclusion {
461 ProofExpr::ForAll { body, .. } => {
462 let inferred = binder_domain(variable, body, ctx.kernel_ctx);
463 if inferred == "Entity" && var_type != "Entity" {
464 var_type.clone()
465 } else {
466 inferred
467 }
468 }
469 _ => var_type.clone(),
470 };
471 let type_term = Term::Global(domain);
472
473 let extended_ctx = ctx.with_local(variable);
475 let body_term = certify(&tree.premises[0], &extended_ctx)?;
476
477 Ok(Term::Lambda {
479 param: variable.clone(),
480 param_type: Box::new(type_term),
481 body: Box::new(body_term),
482 })
483 }
484
485 InferenceRule::StructuralInduction {
488 variable: var_name,
489 ind_type,
490 step_var,
491 } => {
492 if tree.premises.len() != 2 {
493 return Err(KernelError::CertificationError(
494 "StructuralInduction requires exactly 2 premises (base, step)".to_string(),
495 ));
496 }
497
498 let motive_body = extract_motive_body(&tree.conclusion, var_name, ctx.kernel_ctx)?;
500
501 let fix_name = format!("rec_{}", var_name);
503
504 let base_term = certify(&tree.premises[0], ctx)?;
507
508 let ih_conclusion = compute_ih_conclusion(&tree.conclusion, var_name, step_var)?;
511
512 let step_ctx =
516 ctx.with_local(step_var)
517 .with_induction(&fix_name, step_var, ih_conclusion);
518
519 let step_body = certify(&tree.premises[1], &step_ctx)?;
520
521 let step_term = Term::Lambda {
523 param: step_var.clone(),
524 param_type: Box::new(Term::Global(ind_type.clone())),
525 body: Box::new(step_body),
526 };
527
528 let match_term = Term::Match {
532 discriminant: Box::new(Term::Var(var_name.clone())),
533 motive: Box::new(build_motive(ind_type, &motive_body, var_name)),
534 cases: vec![base_term, step_term],
535 };
536
537 let lambda_term = Term::Lambda {
540 param: var_name.clone(),
541 param_type: Box::new(Term::Global(ind_type.clone())),
542 body: Box::new(match_term),
543 };
544
545 Ok(Term::Fix {
548 name: fix_name,
549 body: Box::new(lambda_term),
550 })
551 }
552
553 InferenceRule::InductionScheme {
559 variable,
560 ind_type,
561 cases,
562 } => {
563 if tree.premises.len() != cases.len() {
564 return Err(KernelError::CertificationError(format!(
565 "InductionScheme requires one premise per constructor: {} cases, {} premises",
566 cases.len(),
567 tree.premises.len()
568 )));
569 }
570
571 let motive_body = extract_motive_body(&tree.conclusion, variable, ctx.kernel_ctx)?;
572 let fix_name = format!("rec_{}", variable);
573
574 let mut case_terms = Vec::with_capacity(cases.len());
575 for (case, premise) in cases.iter().zip(tree.premises.iter()) {
576 let arg_types = constructor_arg_types(ctx.kernel_ctx, &case.constructor)?;
578 if arg_types.len() != case.args.len() {
579 return Err(KernelError::CertificationError(format!(
580 "constructor {} takes {} arguments, case binds {}",
581 case.constructor,
582 arg_types.len(),
583 case.args.len()
584 )));
585 }
586
587 let mut ihs = Vec::new();
590 for arg in &case.args {
591 if arg.recursive {
592 let ih = compute_ih_conclusion(&tree.conclusion, variable, &arg.name)?;
593 ihs.push((arg.name.clone(), ih));
594 }
595 }
596
597 let mut case_ctx = ctx.with_induction_multi(&fix_name, ihs);
600 for arg in &case.args {
601 case_ctx = case_ctx.with_local(&arg.name);
602 }
603 let case_body = certify(premise, &case_ctx)?;
604
605 let mut term = case_body;
608 for (arg, ty) in case.args.iter().zip(arg_types.iter()).rev() {
609 term = Term::Lambda {
610 param: arg.name.clone(),
611 param_type: Box::new(ty.clone()),
612 body: Box::new(term),
613 };
614 }
615 case_terms.push(term);
616 }
617
618 let match_term = Term::Match {
620 discriminant: Box::new(Term::Var(variable.clone())),
621 motive: Box::new(build_motive(ind_type, &motive_body, variable)),
622 cases: case_terms,
623 };
624
625 let lambda_term = Term::Lambda {
627 param: variable.clone(),
628 param_type: Box::new(Term::Global(ind_type.clone())),
629 body: Box::new(match_term),
630 };
631
632 Ok(Term::Fix {
633 name: fix_name,
634 body: Box::new(lambda_term),
635 })
636 }
637
638 InferenceRule::ExistentialIntro {
641 witness: witness_str,
642 witness_type,
643 } => {
644 if tree.premises.len() != 1 {
645 return Err(KernelError::CertificationError(
646 "ExistentialIntro requires exactly 1 premise".to_string(),
647 ));
648 }
649
650 let (variable, body) = match &tree.conclusion {
652 ProofExpr::Exists { variable, body } => (variable.clone(), body.as_ref().clone()),
653 _ => {
654 return Err(KernelError::CertificationError(
655 "ExistentialIntro conclusion must be Exists".to_string(),
656 ))
657 }
658 };
659
660 let witness_term = if ctx.is_local(witness_str) {
662 Term::Var(witness_str.clone())
663 } else {
664 Term::Global(witness_str.clone())
665 };
666
667 let proof_term = certify(&tree.premises[0], ctx)?;
669
670 let type_a = Term::Global(witness_type.clone());
672
673 let predicate = Term::Lambda {
678 param: variable.clone(),
679 param_type: Box::new(type_a.clone()),
680 body: Box::new(proof_expr_to_type(&body)?),
681 };
682
683 let witness_ctor = Term::Global("witness".to_string());
686
687 let applied = Term::App(
688 Box::new(Term::App(
689 Box::new(Term::App(
690 Box::new(Term::App(Box::new(witness_ctor), Box::new(type_a))),
691 Box::new(predicate),
692 )),
693 Box::new(witness_term),
694 )),
695 Box::new(proof_term),
696 );
697
698 Ok(applied)
699 }
700
701 InferenceRule::ExistentialIntroTerm {
709 witness,
710 witness_type,
711 } => {
712 if tree.premises.len() != 1 {
713 return Err(KernelError::CertificationError(
714 "ExistentialIntroTerm requires exactly 1 premise".to_string(),
715 ));
716 }
717 let (variable, body) = match &tree.conclusion {
718 ProofExpr::Exists { variable, body } => (variable.clone(), body.as_ref().clone()),
719 _ => {
720 return Err(KernelError::CertificationError(
721 "ExistentialIntroTerm conclusion must be Exists".to_string(),
722 ))
723 }
724 };
725 let declared = existential_domain(&variable, &body);
726 if witness_type != &declared {
727 return Err(KernelError::CertificationError(format!(
728 "ExistentialIntroTerm declares the ∃-binder `{variable}` to be \
729 `{witness_type}`, but the body constrains it to `{declared}` — the \
730 certified term would have type `Ex {witness_type} …` where the goal is \
731 `Ex {declared} …`"
732 )));
733 }
734 let witness_term = proof_term_to_kernel_term(witness)?;
735 let proof_term = certify(&tree.premises[0], ctx)?;
736 let type_a = Term::Global(witness_type.clone());
737 let predicate = Term::Lambda {
738 param: variable.clone(),
739 param_type: Box::new(type_a.clone()),
740 body: Box::new(proof_expr_to_type(&body)?),
741 };
742 let applied = [type_a, predicate, witness_term, proof_term]
743 .into_iter()
744 .fold(Term::Global("witness".to_string()), |acc, arg| {
745 Term::App(Box::new(acc), Box::new(arg))
746 });
747 Ok(applied)
748 }
749
750 InferenceRule::ExistentialElim { witness } => {
764 if tree.premises.len() != 2 {
765 return Err(KernelError::CertificationError(
766 "ExistentialElim requires exactly 2 premises (existential, body)".to_string(),
767 ));
768 }
769 let exist_premise = &tree.premises[0];
770 let body = &tree.premises[1];
771
772 let (var, p_body) = match &exist_premise.conclusion {
773 ProofExpr::Exists { variable, body } => (variable.clone(), body.as_ref().clone()),
774 _ => {
775 return Err(KernelError::CertificationError(
776 "ExistentialElim first premise must conclude an Exists".to_string(),
777 ))
778 }
779 };
780
781 let p_c_expr = crate::unify::instantiate_expr(
783 &p_body,
784 &var,
785 &ProofTerm::Constant(witness.clone()),
786 );
787
788 let disc = certify(exist_premise, ctx)?;
790
791 let h = format!("_exh_{}", witness);
796 let h_var = Term::Var(h.clone());
797 let mut body_ctx = ctx.with_local_hyp_term(&p_c_expr, h_var.clone());
798 for (conjunct, proj) in collect_conjunct_hyps(&p_c_expr, &h_var)? {
799 body_ctx = body_ctx.with_local_hyp_term(&conjunct, proj);
800 }
801
802 let body_raw = certify(body, &body_ctx)?;
803 let c_global = Term::Global(witness.clone());
804 let c_var = Term::Var(witness.clone());
805 let body_term = substitute_term_in_kernel(&body_raw, &c_global, &c_var);
806 let p_c_type =
807 substitute_term_in_kernel(&proof_expr_to_type(&p_c_expr)?, &c_global, &c_var);
808
809 let motive = proof_expr_to_type(&tree.conclusion)?;
814
815 let case = Term::Lambda {
817 param: witness.clone(),
818 param_type: Box::new(Term::Global("Entity".to_string())),
819 body: Box::new(Term::Lambda {
820 param: h,
821 param_type: Box::new(p_c_type),
822 body: Box::new(body_term),
823 }),
824 };
825
826 Ok(Term::Match {
827 discriminant: Box::new(disc),
828 motive: Box::new(motive),
829 cases: vec![case],
830 })
831 }
832
833 InferenceRule::Rewrite { from, to } => {
837 if tree.premises.len() != 2 {
838 return Err(KernelError::CertificationError(
839 "Rewrite requires exactly 2 premises (equality, source)".to_string(),
840 ));
841 }
842
843 let eq_proof = certify(&tree.premises[0], ctx)?;
845 let source_proof = certify(&tree.premises[1], ctx)?;
846
847 let from_term = proof_term_to_kernel_term(from)?;
849 let to_term = proof_term_to_kernel_term(to)?;
850
851 let predicate = build_equality_predicate(&tree.conclusion, to, ctx.kernel_ctx)?;
854
855 let eq_rec = Term::Global("Eq_rec".to_string());
859 let domain = Term::Global(resolved_domain(from, ctx.kernel_ctx));
860
861 let applied = Term::App(
862 Box::new(Term::App(
863 Box::new(Term::App(
864 Box::new(Term::App(
865 Box::new(Term::App(
866 Box::new(Term::App(Box::new(eq_rec), Box::new(domain))),
867 Box::new(from_term),
868 )),
869 Box::new(predicate),
870 )),
871 Box::new(source_proof),
872 )),
873 Box::new(to_term),
874 )),
875 Box::new(eq_proof),
876 );
877
878 Ok(applied)
879 }
880
881 InferenceRule::RewriteAt {
887 from,
888 to,
889 occurrence,
890 } => {
891 if tree.premises.len() != 2 {
892 return Err(KernelError::CertificationError(
893 "RewriteAt requires exactly 2 premises (equality, source)".to_string(),
894 ));
895 }
896 let eq_proof = certify(&tree.premises[0], ctx)?;
897 let source_proof = certify(&tree.premises[1], ctx)?;
898 let from_term = proof_term_to_kernel_term(from)?;
899 let to_term = proof_term_to_kernel_term(to)?;
900 let predicate =
901 build_equality_predicate_at(&tree.conclusion, to, *occurrence, ctx.kernel_ctx)?;
902 let eq_rec = Term::Global("Eq_rec".to_string());
903 let domain = Term::Global(resolved_domain(from, ctx.kernel_ctx));
904 let applied = [from_term, predicate, source_proof, to_term, eq_proof]
905 .into_iter()
906 .fold(Term::App(Box::new(eq_rec), Box::new(domain)), |acc, arg| {
907 Term::App(Box::new(acc), Box::new(arg))
908 });
909 Ok(applied)
910 }
911
912 InferenceRule::EqualitySymmetry => {
915 if tree.premises.len() != 1 {
916 return Err(KernelError::CertificationError(
917 "EqualitySymmetry requires exactly 1 premise".to_string(),
918 ));
919 }
920
921 let premise_proof = certify(&tree.premises[0], ctx)?;
922
923 let (x, y, domain) = match &tree.premises[0].conclusion {
925 ProofExpr::Identity(l, r) => (
926 proof_term_to_kernel_term(l)?,
927 proof_term_to_kernel_term(r)?,
928 Term::Global(resolved_identity_domain(l, r, ctx.kernel_ctx)),
929 ),
930 _ => {
931 return Err(KernelError::CertificationError(
932 "EqualitySymmetry premise must be an Identity".to_string(),
933 ))
934 }
935 };
936
937 let eq_sym = Term::Global("Eq_sym".to_string());
941
942 Ok(Term::App(
943 Box::new(Term::App(
944 Box::new(Term::App(
945 Box::new(Term::App(Box::new(eq_sym), Box::new(domain))),
946 Box::new(x),
947 )),
948 Box::new(y),
949 )),
950 Box::new(premise_proof),
951 ))
952 }
953
954 InferenceRule::EqualityTransitivity => {
957 if tree.premises.len() != 2 {
958 return Err(KernelError::CertificationError(
959 "EqualityTransitivity requires exactly 2 premises".to_string(),
960 ));
961 }
962
963 let proof1 = certify(&tree.premises[0], ctx)?;
964 let proof2 = certify(&tree.premises[1], ctx)?;
965
966 let (x, y, domain) = match &tree.premises[0].conclusion {
968 ProofExpr::Identity(l, r) => (
969 proof_term_to_kernel_term(l)?,
970 proof_term_to_kernel_term(r)?,
971 Term::Global(resolved_identity_domain(l, r, ctx.kernel_ctx)),
972 ),
973 _ => {
974 return Err(KernelError::CertificationError(
975 "EqualityTransitivity first premise must be Identity".to_string(),
976 ))
977 }
978 };
979
980 let z = match &tree.premises[1].conclusion {
982 ProofExpr::Identity(_, r) => proof_term_to_kernel_term(r)?,
983 _ => {
984 return Err(KernelError::CertificationError(
985 "EqualityTransitivity second premise must be Identity".to_string(),
986 ))
987 }
988 };
989
990 let eq_trans = Term::Global("Eq_trans".to_string());
994
995 Ok(Term::App(
996 Box::new(Term::App(
997 Box::new(Term::App(
998 Box::new(Term::App(
999 Box::new(Term::App(
1000 Box::new(Term::App(Box::new(eq_trans), Box::new(domain))),
1001 Box::new(x),
1002 )),
1003 Box::new(y),
1004 )),
1005 Box::new(z),
1006 )),
1007 Box::new(proof1),
1008 )),
1009 Box::new(proof2),
1010 ))
1011 }
1012
1013 InferenceRule::LeTrans => {
1016 if tree.premises.len() != 2 {
1017 return Err(KernelError::CertificationError(
1018 "LeTrans requires exactly 2 premises".to_string(),
1019 ));
1020 }
1021 let (a, b) = le_terms(&tree.conclusion)?;
1022 let (_, mid) = le_terms(&tree.premises[0].conclusion)?;
1023 let p0 = certify(&tree.premises[0], ctx)?;
1024 let p1 = certify(&tree.premises[1], ctx)?;
1025 let mut t = Term::Global("le_trans".to_string());
1026 for arg in [
1027 proof_term_to_kernel_term(&a)?,
1028 proof_term_to_kernel_term(&mid)?,
1029 proof_term_to_kernel_term(&b)?,
1030 p0,
1031 p1,
1032 ] {
1033 t = Term::App(Box::new(t), Box::new(arg));
1034 }
1035 Ok(t)
1036 }
1037
1038 InferenceRule::LeRefl => {
1040 let (a, _) = le_terms(&tree.conclusion)?;
1041 Ok(Term::App(
1042 Box::new(Term::Global("le_refl".to_string())),
1043 Box::new(proof_term_to_kernel_term(&a)?),
1044 ))
1045 }
1046
1047 InferenceRule::LeAddMono => {
1049 if tree.premises.len() != 2 {
1050 return Err(KernelError::CertificationError(
1051 "LeAddMono requires exactly 2 premises".to_string(),
1052 ));
1053 }
1054 let (lhs, rhs) = le_terms(&tree.conclusion)?;
1055 let (a, c) = add_terms(&lhs)?;
1056 let (b, d) = add_terms(&rhs)?;
1057 let p0 = certify(&tree.premises[0], ctx)?;
1058 let p1 = certify(&tree.premises[1], ctx)?;
1059 let mut t = Term::Global("le_add_mono".to_string());
1060 for arg in [
1061 proof_term_to_kernel_term(&a)?,
1062 proof_term_to_kernel_term(&b)?,
1063 proof_term_to_kernel_term(&c)?,
1064 proof_term_to_kernel_term(&d)?,
1065 p0,
1066 p1,
1067 ] {
1068 t = Term::App(Box::new(t), Box::new(arg));
1069 }
1070 Ok(t)
1071 }
1072
1073 InferenceRule::LinFalse => {
1077 if tree.premises.len() != 1 {
1078 return Err(KernelError::CertificationError(
1079 "LinFalse requires exactly 1 premise".to_string(),
1080 ));
1081 }
1082 let le_proof = certify(&tree.premises[0], ctx)?;
1083 Ok(build_bool_discriminator(le_proof))
1084 }
1085
1086 InferenceRule::LeMulNonneg => {
1088 if tree.premises.len() != 2 {
1089 return Err(KernelError::CertificationError(
1090 "LeMulNonneg requires exactly 2 premises".to_string(),
1091 ));
1092 }
1093 let (lhs, rhs) = le_terms(&tree.conclusion)?;
1094 let (k, a) = binop_terms("mul", &lhs)?;
1095 let (_, b) = binop_terms("mul", &rhs)?;
1096 let p0 = certify(&tree.premises[0], ctx)?;
1097 let p1 = certify(&tree.premises[1], ctx)?;
1098 let mut t = Term::Global("le_mul_nonneg".to_string());
1099 for arg in [
1100 proof_term_to_kernel_term(&k)?,
1101 proof_term_to_kernel_term(&a)?,
1102 proof_term_to_kernel_term(&b)?,
1103 p0,
1104 p1,
1105 ] {
1106 t = Term::App(Box::new(t), Box::new(arg));
1107 }
1108 Ok(t)
1109 }
1110
1111 InferenceRule::LeSub => {
1113 if tree.premises.len() != 1 {
1114 return Err(KernelError::CertificationError(
1115 "LeSub requires exactly 1 premise".to_string(),
1116 ));
1117 }
1118 let (_zero, diff) = le_terms(&tree.conclusion)?;
1119 let (b, neg_a) = binop_terms("add", &diff)?;
1120 let (_neg_one, a) = binop_terms("mul", &neg_a)?;
1121 let p0 = certify(&tree.premises[0], ctx)?;
1122 let mut t = Term::Global("le_sub".to_string());
1123 for arg in [
1124 proof_term_to_kernel_term(&a)?,
1125 proof_term_to_kernel_term(&b)?,
1126 p0,
1127 ] {
1128 t = Term::App(Box::new(t), Box::new(arg));
1129 }
1130 Ok(t)
1131 }
1132
1133 InferenceRule::LtSuccLe => {
1138 if tree.premises.len() != 1 {
1139 return Err(KernelError::CertificationError(
1140 "LtSuccLe requires exactly 1 premise".to_string(),
1141 ));
1142 }
1143 let (succ_a, b) = le_terms(&tree.conclusion)?;
1144 let (a, _one) = binop_terms("add", &succ_a)?;
1145 let p0 = certify(&tree.premises[0], ctx)?;
1146 let mut t = Term::Global("lt_succ_le".to_string());
1147 for arg in [
1148 proof_term_to_kernel_term(&a)?,
1149 proof_term_to_kernel_term(&b)?,
1150 p0,
1151 ] {
1152 t = Term::App(Box::new(t), Box::new(arg));
1153 }
1154 Ok(t)
1155 }
1156
1157 InferenceRule::LtAdd1Le => {
1160 if tree.premises.len() != 1 {
1161 return Err(KernelError::CertificationError(
1162 "LtAdd1Le requires exactly 1 premise".to_string(),
1163 ));
1164 }
1165 let (a, b) = le_terms(&tree.conclusion)?;
1166 let p0 = certify(&tree.premises[0], ctx)?;
1167 let mut t = Term::Global("lt_add1_le".to_string());
1168 for arg in [
1169 proof_term_to_kernel_term(&a)?,
1170 proof_term_to_kernel_term(&b)?,
1171 p0,
1172 ] {
1173 t = Term::App(Box::new(t), Box::new(arg));
1174 }
1175 Ok(t)
1176 }
1177
1178 InferenceRule::LeSuccLt => {
1188 if tree.premises.len() != 1 {
1189 return Err(KernelError::CertificationError(
1190 "LeSuccLt requires exactly 1 premise (`a + 1 ≤ b`)".to_string(),
1191 ));
1192 }
1193 let (a, b) = lt_terms(&tree.conclusion)?;
1194 let premise = certify(&tree.premises[0], ctx)?;
1195 let applied = [
1196 proof_term_to_kernel_term(&a)?,
1197 proof_term_to_kernel_term(&b)?,
1198 premise,
1199 ]
1200 .into_iter()
1201 .fold(Term::Global("le_succ_lt".to_string()), |acc, arg| {
1202 Term::App(Box::new(acc), Box::new(arg))
1203 });
1204 Ok(applied)
1205 }
1206
1207 InferenceRule::LeTotal => {
1211 if !tree.premises.is_empty() {
1212 return Err(KernelError::CertificationError(
1213 "LeTotal is a leaf (no premises)".to_string(),
1214 ));
1215 }
1216 let ProofExpr::Or(left, right) = &tree.conclusion else {
1217 return Err(KernelError::CertificationError(format!(
1218 "LeTotal must conclude a disjunction of two ≤ facts, got {:?}",
1219 tree.conclusion
1220 )));
1221 };
1222 let (a, b) = le_terms(left)?;
1223 let (b2, a2) = le_terms(right)?;
1224 if a != a2 || b != b2 {
1225 return Err(KernelError::CertificationError(format!(
1226 "LeTotal must conclude `(a ≤ b) ∨ (b ≤ a)` for ONE pair; got \
1227 `({a} ≤ {b}) ∨ ({b2} ≤ {a2})`"
1228 )));
1229 }
1230 let ka = proof_term_to_kernel_term(&a)?;
1231 let kb = proof_term_to_kernel_term(&b)?;
1232 Ok(Term::App(
1233 Box::new(Term::App(
1234 Box::new(Term::Global("le_total".to_string())),
1235 Box::new(ka),
1236 )),
1237 Box::new(kb),
1238 ))
1239 }
1240
1241 InferenceRule::ArithDecision => match &tree.conclusion {
1242 ProofExpr::Identity(l, r) => {
1243 let kl = proof_term_to_kernel_term(l)?;
1244 let kr = proof_term_to_kernel_term(r)?;
1245 crate::arith::prove_int_eq(ctx.kernel_ctx, &kl, &kr).ok_or_else(|| {
1246 KernelError::CertificationError(
1247 "ArithDecision: arithmetic oracle found no proof".to_string(),
1248 )
1249 })
1250 }
1251 _ => Err(KernelError::CertificationError(
1252 "ArithDecision conclusion must be an Identity".to_string(),
1253 )),
1254 },
1255
1256 InferenceRule::NativeDecide => {
1262 if !tree.premises.is_empty() {
1263 return Err(KernelError::CertificationError(
1264 "NativeDecide is a leaf (no premises)".to_string(),
1265 ));
1266 }
1267 let prop = proof_expr_to_type_ctx(&tree.conclusion, ctx.kernel_ctx)?;
1268 let inst = decidable_instance_for(&prop, ctx.kernel_ctx).ok_or_else(|| {
1269 KernelError::CertificationError(
1270 "NativeDecide: no Decidable instance for this proposition".to_string(),
1271 )
1272 })?;
1273 logicaffeine_kernel::native_decide(ctx.kernel_ctx, &prop, &inst).ok_or_else(|| {
1274 KernelError::CertificationError(
1275 "NativeDecide: evaluation did not decide the goal true".to_string(),
1276 )
1277 })
1278 }
1279
1280 InferenceRule::GroundRefutation => {
1298 if !tree.premises.is_empty() {
1299 return Err(KernelError::CertificationError(
1300 "GroundRefutation is a leaf (no premises)".to_string(),
1301 ));
1302 }
1303 let ProofExpr::Not(inner) = &tree.conclusion else {
1304 return Err(KernelError::CertificationError(format!(
1305 "GroundRefutation must conclude a negation, got {:?}",
1306 tree.conclusion
1307 )));
1308 };
1309 let ProofExpr::Identity(l, r) = inner.as_ref() else {
1310 return Err(KernelError::CertificationError(format!(
1311 "GroundRefutation refutes a ground (dis)equality; got {:?}",
1312 inner
1313 )));
1314 };
1315 let kl = proof_term_to_kernel_term(l)?;
1316 let kr = proof_term_to_kernel_term(r)?;
1317 let domain = identity_domain(l, r);
1321 let nl = logicaffeine_kernel::normalize(ctx.kernel_ctx, &kl);
1322 let nr = logicaffeine_kernel::normalize(ctx.kernel_ctx, &kr);
1323 let hyp_name = ctx.fresh_hyp_name();
1324 let h = Term::Var(hyp_name.clone());
1325 let body = match domain {
1326 "Bool" => match (bool_of_kernel_term(&nl), bool_of_kernel_term(&nr)) {
1327 (Some(false), Some(true)) => build_bool_discriminator(h),
1328 (Some(true), Some(false)) => build_bool_discriminator(
1329 [Term::Global("Bool".to_string()), kl.clone(), kr.clone(), h]
1330 .into_iter()
1331 .fold(Term::Global("Eq_sym".to_string()), |acc, arg| {
1332 Term::App(Box::new(acc), Box::new(arg))
1333 }),
1334 ),
1335 (a, b) => {
1336 return Err(KernelError::CertificationError(format!(
1337 "GroundRefutation: `{l} = {r}` does not COMPUTE to two different \
1338 Bool literals (got {a:?} vs {b:?}), so it is not a ground \
1339 disequality — decide declines, it never guesses"
1340 )))
1341 }
1342 },
1343 "Int" => {
1344 let (Some(vl), Some(vr)) = (int_of_kernel_term(&nl), int_of_kernel_term(&nr))
1345 else {
1346 return Err(KernelError::CertificationError(format!(
1347 "GroundRefutation: `{l} = {r}` does not COMPUTE to two Int \
1348 literals, so it is not a ground disequality"
1349 )));
1350 };
1351 if vl == vr {
1352 return Err(KernelError::CertificationError(format!(
1353 "GroundRefutation: `{l} = {r}` computes to the SAME integer — the \
1354 negation is FALSE and must never be certified"
1355 )));
1356 }
1357 let le = |x: Term, y: Term| {
1360 Term::App(
1361 Box::new(Term::App(
1362 Box::new(Term::Global("le".to_string())),
1363 Box::new(x),
1364 )),
1365 Box::new(y),
1366 )
1367 };
1368 let eq_bool_true = |b: Term| {
1369 [
1370 Term::Global("Bool".to_string()),
1371 b,
1372 Term::Global("true".to_string()),
1373 ]
1374 .into_iter()
1375 .fold(Term::Global("Eq".to_string()), |acc, arg| {
1376 Term::App(Box::new(acc), Box::new(arg))
1377 })
1378 };
1379 let z = Term::Var("_ground_z".to_string());
1380 let motive_body = if vl > vr {
1381 eq_bool_true(le(kl.clone(), z))
1382 } else {
1383 eq_bool_true(le(z, kl.clone()))
1384 };
1385 let motive = Term::Lambda {
1386 param: "_ground_z".to_string(),
1387 param_type: Box::new(Term::Global("Int".to_string())),
1388 body: Box::new(motive_body),
1389 };
1390 let refl_true = [
1392 Term::Global("Bool".to_string()),
1393 Term::Global("true".to_string()),
1394 ]
1395 .into_iter()
1396 .fold(Term::Global("refl".to_string()), |acc, arg| {
1397 Term::App(Box::new(acc), Box::new(arg))
1398 });
1399 let transported = [
1400 Term::Global("Int".to_string()),
1401 kl.clone(),
1402 motive,
1403 refl_true,
1404 kr.clone(),
1405 h,
1406 ]
1407 .into_iter()
1408 .fold(Term::Global("Eq_rec".to_string()), |acc, arg| {
1409 Term::App(Box::new(acc), Box::new(arg))
1410 });
1411 build_bool_discriminator(transported)
1412 }
1413 other => {
1414 return Err(KernelError::CertificationError(format!(
1415 "GroundRefutation: no ground refutation route for an `{other}` \
1416 disequality — only `Int` (via Bool no-confusion after transport) \
1417 and `Bool` (directly) compute"
1418 )))
1419 }
1420 };
1421 Ok(Term::Lambda {
1422 param: hyp_name,
1423 param_type: Box::new(proof_expr_to_type(inner)?),
1424 body: Box::new(body),
1425 })
1426 }
1427
1428 InferenceRule::Contradiction => {
1432 if tree.premises.len() != 2 {
1433 return Err(KernelError::CertificationError(
1434 "Contradiction requires exactly 2 premises (P and ¬P)".to_string(),
1435 ));
1436 }
1437 let a = &tree.premises[0];
1438 let b = &tree.premises[1];
1439 let (pos, neg) = if is_negation_of(&b.conclusion, &a.conclusion) {
1440 (a, b)
1441 } else if is_negation_of(&a.conclusion, &b.conclusion) {
1442 (b, a)
1443 } else {
1444 return Err(KernelError::CertificationError(format!(
1445 "Contradiction premises are not a proposition and its negation: {:?} vs {:?}",
1446 a.conclusion, b.conclusion
1447 )));
1448 };
1449 let pos_term = certify(pos, ctx)?;
1450 let neg_term = certify(neg, ctx)?;
1451 Ok(Term::App(Box::new(neg_term), Box::new(pos_term)))
1453 }
1454
1455 InferenceRule::ReductioAdAbsurdum => {
1459 if tree.premises.len() != 2 {
1460 return Err(KernelError::CertificationError(
1461 "ReductioAdAbsurdum requires exactly 2 premises (assumption, ⊥-derivation)"
1462 .to_string(),
1463 ));
1464 }
1465 let assumed = &tree.premises[0].conclusion;
1466 let contradiction = &tree.premises[1];
1467 let hyp_name = ctx.fresh_hyp_name();
1468 let branch_ctx = ctx.with_local_hyp(assumed, &hyp_name);
1469 let body = certify(contradiction, &branch_ctx)?;
1470 Ok(Term::Lambda {
1471 param: hyp_name,
1472 param_type: Box::new(proof_expr_to_type(assumed)?),
1473 body: Box::new(body),
1474 })
1475 }
1476
1477 InferenceRule::CaseAnalysis { case_formula } => {
1481 if tree.premises.len() != 2 {
1482 return Err(KernelError::CertificationError(
1483 "CaseAnalysis requires exactly 2 premises (C-branch, ¬C-branch)".to_string(),
1484 ));
1485 }
1486 let c = case_formula.as_ref();
1487 let not_c = ProofExpr::Not(Box::new(c.clone()));
1488
1489 let branch_c = unwrap_case_branch(&tree.premises[0]);
1490 let branch_nc = unwrap_case_branch(&tree.premises[1]);
1491
1492 let h1 = ctx.fresh_hyp_name();
1494 let ctx_c = ctx.with_local_hyp(c, &h1);
1495 let neg_c = Term::Lambda {
1496 param: h1,
1497 param_type: Box::new(proof_expr_to_type(c)?),
1498 body: Box::new(certify(branch_c, &ctx_c)?),
1499 };
1500
1501 let h2 = ctx_c.fresh_hyp_name();
1503 let ctx_nc = ctx.with_local_hyp(¬_c, &h2);
1504 let neg_neg_c = Term::Lambda {
1505 param: h2,
1506 param_type: Box::new(proof_expr_to_type(¬_c)?),
1507 body: Box::new(certify(branch_nc, &ctx_nc)?),
1508 };
1509
1510 Ok(Term::App(Box::new(neg_neg_c), Box::new(neg_c)))
1512 }
1513
1514 InferenceRule::DisjunctionElim => {
1522 if tree.premises.len() != 2 {
1523 return Err(KernelError::CertificationError(
1524 "DisjunctionElim requires exactly 2 premises (disjunction, negation)"
1525 .to_string(),
1526 ));
1527 }
1528 let disj_premise = &tree.premises[0];
1529 let neg_premise = &tree.premises[1];
1530
1531 let (left, right) = match &disj_premise.conclusion {
1532 ProofExpr::Or(l, r) => (l.as_ref().clone(), r.as_ref().clone()),
1533 other => {
1534 return Err(KernelError::CertificationError(format!(
1535 "DisjunctionElim first premise must conclude a disjunction, got {:?}",
1536 other
1537 )))
1538 }
1539 };
1540 let refuted = match &neg_premise.conclusion {
1541 ProofExpr::Not(inner) => inner.as_ref().clone(),
1542 other => {
1543 return Err(KernelError::CertificationError(format!(
1544 "DisjunctionElim second premise must conclude a negation, got {:?}",
1545 other
1546 )))
1547 }
1548 };
1549
1550 let left_is_refuted = conclusions_match(&refuted, &left);
1551 let right_is_refuted = conclusions_match(&refuted, &right);
1552 if left_is_refuted == right_is_refuted {
1553 return Err(KernelError::CertificationError(format!(
1554 "DisjunctionElim negation {:?} matches neither (or both) disjuncts of {:?}",
1555 refuted, disj_premise.conclusion
1556 )));
1557 }
1558
1559 let goal_type = proof_expr_to_type(&tree.conclusion)?;
1560 let disc = certify(disj_premise, ctx)?;
1561 let neg_term = certify(neg_premise, ctx)?;
1562
1563 let motive = goal_type.clone();
1566
1567 let return_case = |disjunct: &ProofExpr, binder: &str| -> KernelResult<Term> {
1570 Ok(Term::Lambda {
1571 param: binder.to_string(),
1572 param_type: Box::new(proof_expr_to_type(disjunct)?),
1573 body: Box::new(Term::Var(binder.to_string())),
1574 })
1575 };
1576 let absurd_case = |disjunct: &ProofExpr, binder: &str| -> KernelResult<Term> {
1578 let falsum = Term::App(
1579 Box::new(neg_term.clone()),
1580 Box::new(Term::Var(binder.to_string())),
1581 );
1582 let ex_falso = Term::Match {
1583 discriminant: Box::new(falsum),
1584 motive: Box::new(Term::Lambda {
1585 param: "_".to_string(),
1586 param_type: Box::new(Term::Global("False".to_string())),
1587 body: Box::new(goal_type.clone()),
1588 }),
1589 cases: vec![],
1590 };
1591 Ok(Term::Lambda {
1592 param: binder.to_string(),
1593 param_type: Box::new(proof_expr_to_type(disjunct)?),
1594 body: Box::new(ex_falso),
1595 })
1596 };
1597
1598 let left_case = if left_is_refuted {
1599 absurd_case(&left, "__dl")?
1600 } else {
1601 return_case(&left, "__dl")?
1602 };
1603 let right_case = if right_is_refuted {
1604 absurd_case(&right, "__dr")?
1605 } else {
1606 return_case(&right, "__dr")?
1607 };
1608
1609 Ok(Term::Match {
1610 discriminant: Box::new(disc),
1611 motive: Box::new(motive),
1612 cases: vec![left_case, right_case],
1613 })
1614 }
1615
1616 InferenceRule::DisjunctionCases => {
1625 if tree.premises.len() != 3 {
1626 return Err(KernelError::CertificationError(
1627 "DisjunctionCases requires exactly 3 premises (disjunction, A-branch, B-branch)"
1628 .to_string(),
1629 ));
1630 }
1631 let disj_premise = &tree.premises[0];
1632 let (left, right) = match &disj_premise.conclusion {
1633 ProofExpr::Or(l, r) => (l.as_ref().clone(), r.as_ref().clone()),
1634 other => {
1635 return Err(KernelError::CertificationError(format!(
1636 "DisjunctionCases first premise must conclude a disjunction, got {:?}",
1637 other
1638 )))
1639 }
1640 };
1641 let disc = certify(disj_premise, ctx)?;
1642 let motive = proof_expr_to_type_ctx(&tree.conclusion, ctx.kernel_ctx)?;
1647
1648 let build_arm = |disjunct: &ProofExpr,
1649 branch: &DerivationTree,
1650 binder: &str|
1651 -> KernelResult<Term> {
1652 let h_var = Term::Var(binder.to_string());
1653 let mut bctx = ctx.with_local_hyp_term(disjunct, h_var.clone());
1654 for (conjunct, proj) in collect_conjunct_hyps(disjunct, &h_var)? {
1655 bctx = bctx.with_local_hyp_term(&conjunct, proj);
1656 }
1657 let body = certify(branch, &bctx)?;
1658 Ok(Term::Lambda {
1659 param: binder.to_string(),
1660 param_type: Box::new(proof_expr_to_type(disjunct)?),
1661 body: Box::new(body),
1662 })
1663 };
1664
1665 let lname = ctx.fresh_hyp_name();
1670 let rname = ctx.fresh_hyp_name();
1671 let left_case = build_arm(&left, &tree.premises[1], &lname)?;
1672 let right_case = build_arm(&right, &tree.premises[2], &rname)?;
1673
1674 Ok(Term::Match {
1675 discriminant: Box::new(disc),
1676 motive: Box::new(motive),
1677 cases: vec![left_case, right_case],
1678 })
1679 }
1680
1681 InferenceRule::BicondIntro => {
1684 if tree.premises.len() != 2 {
1685 return Err(KernelError::CertificationError(
1686 "BicondIntro requires exactly 2 premises (P→Q, Q→P)".to_string(),
1687 ));
1688 }
1689 let (p, q) = match &tree.conclusion {
1690 ProofExpr::Iff(p, q) => (p.as_ref().clone(), q.as_ref().clone()),
1691 other => {
1692 return Err(KernelError::CertificationError(format!(
1693 "BicondIntro conclusion must be a biconditional, got {:?}",
1694 other
1695 )))
1696 }
1697 };
1698 let pq_type = proof_expr_to_type(&ProofExpr::Implies(
1699 Box::new(p.clone()),
1700 Box::new(q.clone()),
1701 ))?;
1702 let qp_type = proof_expr_to_type(&ProofExpr::Implies(Box::new(q), Box::new(p)))?;
1703 let pq_proof = certify(&tree.premises[0], ctx)?;
1704 let qp_proof = certify(&tree.premises[1], ctx)?;
1705 Ok(Term::App(
1706 Box::new(Term::App(
1707 Box::new(Term::App(
1708 Box::new(Term::App(
1709 Box::new(Term::Global("conj".to_string())),
1710 Box::new(pq_type),
1711 )),
1712 Box::new(qp_type),
1713 )),
1714 Box::new(pq_proof),
1715 )),
1716 Box::new(qp_proof),
1717 ))
1718 }
1719
1720 InferenceRule::DoubleNegation => {
1723 if tree.premises.len() != 1 {
1724 return Err(KernelError::CertificationError(
1725 "DoubleNegation requires exactly 1 premise (a proof of P)".to_string(),
1726 ));
1727 }
1728 let p = match &tree.conclusion {
1729 ProofExpr::Not(inner) => match inner.as_ref() {
1730 ProofExpr::Not(core) => core.as_ref().clone(),
1731 other => {
1732 return Err(KernelError::CertificationError(format!(
1733 "DoubleNegation conclusion must be ¬¬P, got ¬{:?}",
1734 other
1735 )))
1736 }
1737 },
1738 other => {
1739 return Err(KernelError::CertificationError(format!(
1740 "DoubleNegation conclusion must be ¬¬P, got {:?}",
1741 other
1742 )))
1743 }
1744 };
1745 let p_type = proof_expr_to_type(&p)?;
1746 let p_proof = certify(&tree.premises[0], ctx)?;
1747 let not_p_type = Term::Pi {
1748 param: "_".to_string(),
1749 param_type: Box::new(p_type),
1750 body_type: Box::new(Term::Global("False".to_string())),
1751 };
1752 let hnp = "__dn_hnp".to_string();
1753 Ok(Term::Lambda {
1754 param: hnp.clone(),
1755 param_type: Box::new(not_p_type),
1756 body: Box::new(Term::App(Box::new(Term::Var(hnp)), Box::new(p_proof))),
1757 })
1758 }
1759
1760 InferenceRule::ClassicalReductio => {
1763 if tree.premises.len() != 1 {
1764 return Err(KernelError::CertificationError(
1765 "ClassicalReductio requires exactly 1 premise (a proof of False)".to_string(),
1766 ));
1767 }
1768 let g = tree.conclusion.clone();
1769 let g_type = proof_expr_to_type(&g)?;
1770 let neg_g = ProofExpr::Not(Box::new(g));
1771 let neg_g_type = proof_expr_to_type(&neg_g)?; let binder = ctx.fresh_hyp_name();
1773 let bctx = ctx.with_local_hyp_term(&neg_g, Term::Var(binder.clone()));
1774 let false_proof = certify(&tree.premises[0], &bctx)?;
1775 let nn_g = Term::Lambda {
1776 param: binder,
1777 param_type: Box::new(neg_g_type),
1778 body: Box::new(false_proof),
1779 };
1780 Ok(Term::App(
1781 Box::new(Term::App(
1782 Box::new(Term::Global("dne".to_string())),
1783 Box::new(g_type),
1784 )),
1785 Box::new(nn_g),
1786 ))
1787 }
1788
1789 InferenceRule::ImpliesIntro => {
1793 if tree.premises.len() != 1 {
1794 return Err(KernelError::CertificationError(
1795 "ImpliesIntro requires exactly 1 premise (the consequent proof)".to_string(),
1796 ));
1797 }
1798 let ant = match &tree.conclusion {
1799 ProofExpr::Implies(a, _) => a.as_ref().clone(),
1800 ProofExpr::Not(a) => a.as_ref().clone(),
1804 other => {
1805 return Err(KernelError::CertificationError(format!(
1806 "ImpliesIntro conclusion must be an implication or a negation, got {:?}",
1807 other
1808 )))
1809 }
1810 };
1811 let binder = ctx.fresh_hyp_name();
1812 let h_var = Term::Var(binder.clone());
1813 let mut bctx = ctx.with_local_hyp_term(&ant, h_var.clone());
1814 for (conjunct, proj) in collect_conjunct_hyps(&ant, &h_var)? {
1815 bctx = bctx.with_local_hyp_term(&conjunct, proj);
1816 }
1817 let body = certify(&tree.premises[0], &bctx)?;
1818 Ok(Term::Lambda {
1819 param: binder,
1820 param_type: Box::new(proof_expr_to_type(&ant)?),
1821 body: Box::new(body),
1822 })
1823 }
1824
1825 InferenceRule::ConjunctionElim => {
1828 if tree.premises.len() != 1 {
1829 return Err(KernelError::CertificationError(
1830 "ConjunctionElim requires exactly 1 premise (the conjunction)".to_string(),
1831 ));
1832 }
1833 let conj_premise = &tree.premises[0];
1834 let (a, b) = match &conj_premise.conclusion {
1835 ProofExpr::And(l, r) => (l.as_ref().clone(), r.as_ref().clone()),
1836 ProofExpr::Iff(l, r) => (
1839 ProofExpr::Implies(l.clone(), r.clone()),
1840 ProofExpr::Implies(r.clone(), l.clone()),
1841 ),
1842 other => {
1843 return Err(KernelError::CertificationError(format!(
1844 "ConjunctionElim premise must conclude a conjunction, got {:?}",
1845 other
1846 )))
1847 }
1848 };
1849 let take_left = conclusions_match(&tree.conclusion, &a);
1850 if !take_left && !conclusions_match(&tree.conclusion, &b) {
1851 return Err(KernelError::CertificationError(format!(
1852 "ConjunctionElim conclusion {:?} matches neither conjunct of {:?}",
1853 tree.conclusion, conj_premise.conclusion
1854 )));
1855 }
1856 let disc = certify(conj_premise, ctx)?;
1857 let left_type = proof_expr_to_type(&a)?;
1858 let right_type = proof_expr_to_type(&b)?;
1859 Ok(project_conjunct(&disc, &left_type, &right_type, take_left))
1860 }
1861
1862 InferenceRule::OracleVerification(detail) => Err(KernelError::CertificationError(format!(
1870 "oracle (Z3) results are not kernel-certifiable — they attest \
1871 satisfiability but produce no checkable proof term ({})",
1872 detail
1873 ))),
1874
1875 rule @ (InferenceRule::ModalAccess
1891 | InferenceRule::ModalGeneralization
1892 | InferenceRule::TemporalTransitivity
1893 | InferenceRule::TemporalInduction
1894 | InferenceRule::TemporalUnfolding
1895 | InferenceRule::EventualityProgress
1896 | InferenceRule::UntilInduction) => Err(KernelError::CertificationError(format!(
1897 "E_DEAD_INFERENCE_RULE: {:?} — {}. This derivation was never certifiable: \
1898 rebuild it from live rules, or reject the input. Do not report this as the \
1899 kernel refusing a proof.",
1900 rule,
1901 rule.uncertifiable_reason()
1902 .expect("a dead rule states why it is dead")
1903 ))),
1904 }
1905}
1906
1907fn is_negation_of(neg: &ProofExpr, pos: &ProofExpr) -> bool {
1909 matches!(neg, ProofExpr::Not(inner) if inner.as_ref() == pos)
1910}
1911
1912fn unwrap_case_branch(tree: &DerivationTree) -> &DerivationTree {
1916 if matches!(tree.rule, InferenceRule::PremiseMatch) && tree.premises.len() == 1 {
1917 &tree.premises[0]
1918 } else {
1919 tree
1920 }
1921}
1922
1923fn build_equality_predicate(
1929 goal: &ProofExpr,
1930 replace_term: &ProofTerm,
1931 kctx: &Context,
1932) -> KernelResult<Term> {
1933 if let ProofExpr::Predicate { name, args, .. } = goal {
1936 if args.len() == 1 && &args[0] == replace_term {
1937 return Ok(Term::Global(name.clone()));
1938 }
1939 }
1940
1941 let goal_type = proof_expr_to_type_ctx(goal, kctx)?;
1944 let param_name = "_eq_var".to_string();
1945 let substituted = substitute_term_in_kernel(
1946 &goal_type,
1947 &proof_term_to_kernel_term(replace_term)?,
1948 &Term::Var(param_name.clone()),
1949 );
1950
1951 Ok(Term::Lambda {
1952 param: param_name,
1953 param_type: Box::new(Term::Global(resolved_domain(replace_term, kctx))),
1957 body: Box::new(substituted),
1958 })
1959}
1960
1961fn build_equality_predicate_at(
1974 goal: &ProofExpr,
1975 replace_term: &ProofTerm,
1976 occurrence: usize,
1977 kctx: &Context,
1978) -> KernelResult<Term> {
1979 let goal_type = proof_expr_to_type_ctx(goal, kctx)?;
1980 let param_name = "_eq_var".to_string();
1981 let from = proof_term_to_kernel_term(replace_term)?;
1982 let mut seen = 0usize;
1983 let substituted = substitute_nth_in_kernel(
1984 &goal_type,
1985 &from,
1986 &Term::Var(param_name.clone()),
1987 occurrence,
1988 &mut seen,
1989 );
1990 if seen <= occurrence {
1991 return Err(KernelError::CertificationError(format!(
1992 "RewriteAt names occurrence {occurrence} of `{replace_term}`, but the goal has \
1993 only {seen}"
1994 )));
1995 }
1996 Ok(Term::Lambda {
1997 param: param_name,
1998 param_type: Box::new(Term::Global(resolved_domain(replace_term, kctx))),
1999 body: Box::new(substituted),
2000 })
2001}
2002
2003fn substitute_nth_in_kernel(
2007 term: &Term,
2008 from: &Term,
2009 to: &Term,
2010 target: usize,
2011 seen: &mut usize,
2012) -> Term {
2013 if term == from {
2014 let here = *seen;
2015 *seen += 1;
2016 return if here == target {
2017 to.clone()
2018 } else {
2019 term.clone()
2020 };
2021 }
2022 let mut go = |t: &Term, seen: &mut usize| substitute_nth_in_kernel(t, from, to, target, seen);
2023 match term {
2024 Term::App(f, a) => {
2025 let f2 = go(f, seen);
2026 let a2 = go(a, seen);
2027 Term::App(Box::new(f2), Box::new(a2))
2028 }
2029 Term::Pi {
2030 param,
2031 param_type,
2032 body_type,
2033 } => {
2034 let p2 = go(param_type, seen);
2035 let b2 = go(body_type, seen);
2036 Term::Pi {
2037 param: param.clone(),
2038 param_type: Box::new(p2),
2039 body_type: Box::new(b2),
2040 }
2041 }
2042 Term::Lambda {
2043 param,
2044 param_type,
2045 body,
2046 } => {
2047 let p2 = go(param_type, seen);
2048 let b2 = go(body, seen);
2049 Term::Lambda {
2050 param: param.clone(),
2051 param_type: Box::new(p2),
2052 body: Box::new(b2),
2053 }
2054 }
2055 Term::Match {
2056 discriminant,
2057 motive,
2058 cases,
2059 } => {
2060 let d2 = go(discriminant, seen);
2061 let m2 = go(motive, seen);
2062 let mut cs = Vec::with_capacity(cases.len());
2063 for c in cases {
2064 cs.push(go(c, seen));
2065 }
2066 Term::Match {
2067 discriminant: Box::new(d2),
2068 motive: Box::new(m2),
2069 cases: cs,
2070 }
2071 }
2072 other => other.clone(),
2073 }
2074}
2075
2076fn bool_of_kernel_term(t: &Term) -> Option<bool> {
2078 match t {
2079 Term::Global(g) if g == "true" => Some(true),
2080 Term::Global(g) if g == "false" => Some(false),
2081 _ => None,
2082 }
2083}
2084
2085fn int_of_kernel_term(t: &Term) -> Option<logicaffeine_base::BigInt> {
2088 match t {
2089 Term::Lit(lit) => logicaffeine_kernel::lit_bigint(lit),
2090 _ => None,
2091 }
2092}
2093
2094pub(crate) fn existential_domain(variable: &str, body: &ProofExpr) -> String {
2108 let mut found: Option<String> = None;
2109 binder_sort_from_expr(variable, body, &mut found);
2110 found.unwrap_or_else(|| "Entity".to_string())
2111}
2112
2113fn is_named_var(t: &ProofTerm, name: &str) -> bool {
2114 matches!(t, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == name)
2115}
2116
2117fn binder_sort_from_expr(variable: &str, e: &ProofExpr, found: &mut Option<String>) {
2120 fn note(d: &str, found: &mut Option<String>) {
2121 if d != "Entity" && (found.is_none() || d == "Bool") {
2122 *found = Some(d.to_string());
2123 }
2124 }
2125 match e {
2126 ProofExpr::TypedVar { name, typename } if name == variable => {
2130 *found = Some(typename.clone());
2131 }
2132 ProofExpr::Identity(l, r) => {
2135 if is_named_var(l, variable) || is_named_var(r, variable) {
2136 note(identity_domain(l, r), found);
2137 }
2138 binder_sort_from_term(variable, l, found);
2139 binder_sort_from_term(variable, r, found);
2140 }
2141 ProofExpr::Predicate { args, .. } => {
2142 for a in args {
2143 binder_sort_from_term(variable, a, found);
2144 }
2145 }
2146 ProofExpr::And(l, r)
2147 | ProofExpr::Or(l, r)
2148 | ProofExpr::Implies(l, r)
2149 | ProofExpr::Iff(l, r) => {
2150 binder_sort_from_expr(variable, l, found);
2151 binder_sort_from_expr(variable, r, found);
2152 }
2153 ProofExpr::Not(p) | ProofExpr::Temporal { body: p, .. } => {
2154 binder_sort_from_expr(variable, p, found)
2155 }
2156 ProofExpr::ForAll { variable: v, body } | ProofExpr::Exists { variable: v, body } => {
2159 if v != variable {
2160 binder_sort_from_expr(variable, body, found);
2161 }
2162 }
2163 _ => {}
2164 }
2165}
2166
2167fn binder_sort_from_term(variable: &str, t: &ProofTerm, found: &mut Option<String>) {
2169 if let ProofTerm::Function(name, args) = t {
2170 let arith = is_arith_builtin(name);
2171 for a in args {
2172 if arith && is_named_var(a, variable) && found.is_none() {
2173 *found = Some("Int".to_string());
2174 }
2175 binder_sort_from_term(variable, a, found);
2176 }
2177 }
2178}
2179
2180fn substitute_term_in_kernel(term: &Term, from: &Term, to: &Term) -> Term {
2182 if term == from {
2183 return to.clone();
2184 }
2185 match term {
2186 Term::App(f, a) => Term::App(
2187 Box::new(substitute_term_in_kernel(f, from, to)),
2188 Box::new(substitute_term_in_kernel(a, from, to)),
2189 ),
2190 Term::Pi {
2191 param,
2192 param_type,
2193 body_type,
2194 } => Term::Pi {
2195 param: param.clone(),
2196 param_type: Box::new(substitute_term_in_kernel(param_type, from, to)),
2197 body_type: Box::new(substitute_term_in_kernel(body_type, from, to)),
2198 },
2199 Term::Lambda {
2200 param,
2201 param_type,
2202 body,
2203 } => Term::Lambda {
2204 param: param.clone(),
2205 param_type: Box::new(substitute_term_in_kernel(param_type, from, to)),
2206 body: Box::new(substitute_term_in_kernel(body, from, to)),
2207 },
2208 Term::Match {
2209 discriminant,
2210 motive,
2211 cases,
2212 } => Term::Match {
2213 discriminant: Box::new(substitute_term_in_kernel(discriminant, from, to)),
2214 motive: Box::new(substitute_term_in_kernel(motive, from, to)),
2215 cases: cases
2216 .iter()
2217 .map(|c| substitute_term_in_kernel(c, from, to))
2218 .collect(),
2219 },
2220 Term::Fix { name, body } => Term::Fix {
2221 name: name.clone(),
2222 body: Box::new(substitute_term_in_kernel(body, from, to)),
2223 },
2224 other => other.clone(),
2225 }
2226}
2227
2228fn project_conjunct(disc: &Term, left_type: &Term, right_type: &Term, take_left: bool) -> Term {
2237 let chosen = if take_left { left_type } else { right_type };
2238 let result = if take_left { "__l" } else { "__r" };
2239 let case = Term::Lambda {
2240 param: "__l".to_string(),
2241 param_type: Box::new(left_type.clone()),
2242 body: Box::new(Term::Lambda {
2243 param: "__r".to_string(),
2244 param_type: Box::new(right_type.clone()),
2245 body: Box::new(Term::Var(result.to_string())),
2246 }),
2247 };
2248 Term::Match {
2249 discriminant: Box::new(disc.clone()),
2250 motive: Box::new(chosen.clone()),
2255 cases: vec![case],
2256 }
2257}
2258
2259fn collect_conjunct_hyps(expr: &ProofExpr, witness: &Term) -> KernelResult<Vec<(ProofExpr, Term)>> {
2268 match expr {
2269 ProofExpr::And(l, r) => {
2270 let left_type = proof_expr_to_type(l)?;
2271 let right_type = proof_expr_to_type(r)?;
2272
2273 let left_proj = project_conjunct(witness, &left_type, &right_type, true);
2274 let right_proj = project_conjunct(witness, &left_type, &right_type, false);
2275
2276 let mut hyps = collect_conjunct_hyps(l, &left_proj)?;
2277 hyps.extend(collect_conjunct_hyps(r, &right_proj)?);
2278 Ok(hyps)
2279 }
2280 _ => Ok(vec![(expr.clone(), witness.clone())]),
2281 }
2282}
2283
2284fn certify_hypothesis(conclusion: &ProofExpr, ctx: &CertificationContext) -> KernelResult<Term> {
2286 if let Some(ih_term) = ctx.get_ih_term(conclusion) {
2288 return Ok(ih_term);
2289 }
2290
2291 if let Some(hyp) = ctx.get_local_hyp(conclusion) {
2294 return Ok(hyp);
2295 }
2296
2297 match conclusion {
2298 ProofExpr::Atom(name) => {
2299 if ctx.is_local(name) {
2301 return Ok(Term::Var(name.clone()));
2302 }
2303 if ctx.kernel_ctx.get_global(name).is_some() {
2305 Ok(Term::Global(name.clone()))
2306 } else {
2307 Err(KernelError::CertificationError(format!(
2308 "Unknown hypothesis: {}",
2309 name
2310 )))
2311 }
2312 }
2313 ProofExpr::Predicate { name, args, .. } => {
2315 let mut target_type = Term::Global(name.clone());
2319 for arg in args {
2320 let arg_term = proof_term_to_kernel_term_entity(arg)?;
2321 target_type = Term::App(Box::new(target_type), Box::new(arg_term));
2322 }
2323
2324 for (decl_name, decl_type) in ctx.kernel_ctx.iter_declarations() {
2326 if types_structurally_match(&target_type, decl_type) {
2327 return Ok(Term::Global(decl_name.to_string()));
2328 }
2329 }
2330
2331 Err(KernelError::CertificationError(format!(
2332 "Cannot find hypothesis with type: {:?}",
2333 conclusion
2334 )))
2335 }
2336 _ => {
2340 let target_type = proof_expr_to_type_ctx(conclusion, ctx.kernel_ctx).map_err(|_| {
2343 KernelError::CertificationError(format!(
2344 "Cannot certify hypothesis: {:?}",
2345 conclusion
2346 ))
2347 })?;
2348
2349 for (name, decl_type) in ctx.kernel_ctx.iter_declarations() {
2350 if types_structurally_match(&target_type, decl_type) {
2351 return Ok(Term::Global(name.to_string()));
2352 }
2353 }
2354
2355 Err(KernelError::CertificationError(format!(
2356 "Cannot find hypothesis with type matching: {:?}",
2357 conclusion
2358 )))
2359 }
2360 }
2361}
2362
2363fn types_structurally_match(a: &Term, b: &Term) -> bool {
2366 types_alpha_equiv(a, b, &mut Vec::new())
2368}
2369
2370fn types_alpha_equiv(a: &Term, b: &Term, bindings: &mut Vec<(String, String)>) -> bool {
2373 match (a, b) {
2374 (Term::Sort(u1), Term::Sort(u2)) => u1 == u2,
2375 (Term::Var(v1), Term::Var(v2)) => {
2376 for (bound_a, bound_b) in bindings.iter().rev() {
2378 if v1 == bound_a {
2379 return v2 == bound_b;
2380 }
2381 if v2 == bound_b {
2382 return false; }
2384 }
2385 v1 == v2
2387 }
2388 (Term::Global(g1), Term::Global(g2)) => g1 == g2,
2389 (Term::Lit(l1), Term::Lit(l2)) => l1 == l2,
2390 (Term::App(f1, a1), Term::App(f2, a2)) => {
2391 types_alpha_equiv(f1, f2, bindings) && types_alpha_equiv(a1, a2, bindings)
2392 }
2393 (
2394 Term::Pi {
2395 param: p1,
2396 param_type: pt1,
2397 body_type: bt1,
2398 },
2399 Term::Pi {
2400 param: p2,
2401 param_type: pt2,
2402 body_type: bt2,
2403 },
2404 ) => {
2405 if !types_alpha_equiv(pt1, pt2, bindings) {
2407 return false;
2408 }
2409 bindings.push((p1.clone(), p2.clone()));
2411 let result = types_alpha_equiv(bt1, bt2, bindings);
2412 bindings.pop();
2413 result
2414 }
2415 (
2416 Term::Lambda {
2417 param: p1,
2418 param_type: pt1,
2419 body: b1,
2420 },
2421 Term::Lambda {
2422 param: p2,
2423 param_type: pt2,
2424 body: b2,
2425 },
2426 ) => {
2427 if !types_alpha_equiv(pt1, pt2, bindings) {
2429 return false;
2430 }
2431 bindings.push((p1.clone(), p2.clone()));
2433 let result = types_alpha_equiv(b1, b2, bindings);
2434 bindings.pop();
2435 result
2436 }
2437 _ => false,
2438 }
2439}
2440
2441fn extract_and_types(conclusion: &ProofExpr) -> KernelResult<(Term, Term)> {
2443 match conclusion {
2444 ProofExpr::And(p, q) => {
2445 let p_term = proof_expr_to_type(p)?;
2446 let q_term = proof_expr_to_type(q)?;
2447 Ok((p_term, q_term))
2448 }
2449 _ => Err(KernelError::CertificationError(format!(
2450 "Expected And, got {:?}",
2451 conclusion
2452 ))),
2453 }
2454}
2455
2456fn param_domain(ctx: &Context, name: &str, pos: usize) -> Option<String> {
2461 let mut ty = ctx.get_global(kernel_arith_name(name))?;
2465 let mut i = 0;
2466 while let Term::Pi {
2467 param_type,
2468 body_type,
2469 ..
2470 } = ty
2471 {
2472 if i == pos {
2473 return match param_type.as_ref() {
2474 Term::Global(g) => Some(g.clone()),
2475 _ => None,
2476 };
2477 }
2478 ty = body_type;
2479 i += 1;
2480 }
2481 None
2482}
2483
2484fn collect_var_domains_term(t: &ProofTerm, variable: &str, ctx: &Context, out: &mut Vec<String>) {
2489 match t {
2490 ProofTerm::Function(name, args) => {
2491 for (j, a) in args.iter().enumerate() {
2492 if matches!(a, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == variable)
2493 {
2494 if let Some(g) = param_domain(ctx, name, j) {
2495 out.push(g);
2496 }
2497 }
2498 collect_var_domains_term(a, variable, ctx, out);
2499 }
2500 }
2501 ProofTerm::Group(args) => {
2502 for a in args {
2503 collect_var_domains_term(a, variable, ctx, out);
2504 }
2505 }
2506 _ => {}
2507 }
2508}
2509
2510fn collect_var_domains_expr(e: &ProofExpr, variable: &str, ctx: &Context, out: &mut Vec<String>) {
2514 match e {
2515 ProofExpr::Predicate { name, args, .. } => {
2516 for (j, a) in args.iter().enumerate() {
2517 if matches!(a, ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) if v == variable)
2518 {
2519 if let Some(g) = param_domain(ctx, name, j) {
2520 out.push(g);
2521 }
2522 }
2523 collect_var_domains_term(a, variable, ctx, out);
2524 }
2525 }
2526 ProofExpr::Identity(l, r) => {
2527 collect_var_domains_term(l, variable, ctx, out);
2528 collect_var_domains_term(r, variable, ctx, out);
2529 }
2530 ProofExpr::And(l, r)
2531 | ProofExpr::Or(l, r)
2532 | ProofExpr::Implies(l, r)
2533 | ProofExpr::Iff(l, r) => {
2534 collect_var_domains_expr(l, variable, ctx, out);
2535 collect_var_domains_expr(r, variable, ctx, out);
2536 }
2537 ProofExpr::Not(p)
2538 | ProofExpr::ForAll { body: p, .. }
2539 | ProofExpr::Exists { body: p, .. } => collect_var_domains_expr(p, variable, ctx, out),
2540 _ => {}
2541 }
2542}
2543
2544fn binder_domain(variable: &str, body: &ProofExpr, ctx: &Context) -> String {
2551 let mut domains = Vec::new();
2552 collect_var_domains_expr(body, variable, ctx, &mut domains);
2553 domains
2554 .into_iter()
2555 .find(|d| d != "Entity")
2556 .unwrap_or_else(|| "Entity".to_string())
2557}
2558
2559pub(crate) fn proof_expr_to_type_ctx(expr: &ProofExpr, ctx: &Context) -> KernelResult<Term> {
2564 if let ProofExpr::ForAll { variable, body } = expr {
2565 let dom = binder_domain(variable, body, ctx);
2566 let body_type = proof_expr_to_type_ctx(body, ctx)?;
2567 return Ok(Term::Pi {
2568 param: variable.clone(),
2569 param_type: Box::new(Term::Global(dom)),
2570 body_type: Box::new(body_type),
2571 });
2572 }
2573 if let ProofExpr::Identity(l, r) = expr {
2577 let l_term = proof_term_to_kernel_term(l)?;
2578 let r_term = proof_term_to_kernel_term(r)?;
2579 let domain = Term::Global(resolved_identity_domain(l, r, ctx));
2580 return Ok(Term::App(
2581 Box::new(Term::App(
2582 Box::new(Term::App(
2583 Box::new(Term::Global("Eq".to_string())),
2584 Box::new(domain),
2585 )),
2586 Box::new(l_term),
2587 )),
2588 Box::new(r_term),
2589 ));
2590 }
2591 proof_expr_to_type(expr)
2592}
2593
2594pub(crate) fn proof_expr_to_type(expr: &ProofExpr) -> KernelResult<Term> {
2595 match expr {
2596 ProofExpr::Atom(name) if name == "⊥" || name == "False" || name == "false" => {
2599 Ok(Term::Global("False".to_string()))
2600 }
2601 ProofExpr::Atom(name) => Ok(Term::Global(name.clone())),
2602 ProofExpr::Not(p) => Ok(Term::Pi {
2607 param: "_".to_string(),
2608 param_type: Box::new(proof_expr_to_type(p)?),
2609 body_type: Box::new(Term::Global("False".to_string())),
2610 }),
2611 ProofExpr::And(p, q) => Ok(Term::App(
2612 Box::new(Term::App(
2613 Box::new(Term::Global("And".to_string())),
2614 Box::new(proof_expr_to_type(p)?),
2615 )),
2616 Box::new(proof_expr_to_type(q)?),
2617 )),
2618 ProofExpr::Or(p, q) => Ok(Term::App(
2619 Box::new(Term::App(
2620 Box::new(Term::Global("Or".to_string())),
2621 Box::new(proof_expr_to_type(p)?),
2622 )),
2623 Box::new(proof_expr_to_type(q)?),
2624 )),
2625 ProofExpr::Implies(p, q) => Ok(Term::Pi {
2626 param: "_".to_string(),
2627 param_type: Box::new(proof_expr_to_type(p)?),
2628 body_type: Box::new(proof_expr_to_type(q)?),
2629 }),
2630 ProofExpr::Iff(p, q) => {
2633 let pt = proof_expr_to_type(p)?;
2634 let qt = proof_expr_to_type(q)?;
2635 let pq = Term::Pi {
2636 param: "_".to_string(),
2637 param_type: Box::new(pt.clone()),
2638 body_type: Box::new(qt.clone()),
2639 };
2640 let qp = Term::Pi {
2641 param: "_".to_string(),
2642 param_type: Box::new(qt),
2643 body_type: Box::new(pt),
2644 };
2645 Ok(Term::App(
2646 Box::new(Term::App(
2647 Box::new(Term::Global("And".to_string())),
2648 Box::new(pq),
2649 )),
2650 Box::new(qp),
2651 ))
2652 }
2653 ProofExpr::ForAll { variable, body } => {
2655 let body_type = proof_expr_to_type(body)?;
2656 Ok(Term::Pi {
2657 param: variable.clone(),
2658 param_type: Box::new(Term::Global("Entity".to_string())),
2659 body_type: Box::new(body_type),
2660 })
2661 }
2662 ProofExpr::Predicate { name, args, .. } => {
2666 let mut result = Term::Global(name.clone());
2667 for arg in args {
2668 let arg_term = proof_term_to_kernel_term_entity(arg)?;
2669 result = Term::App(Box::new(result), Box::new(arg_term));
2670 }
2671 Ok(result)
2672 }
2673 ProofExpr::Identity(l, r) => {
2678 let l_term = proof_term_to_kernel_term(l)?;
2679 let r_term = proof_term_to_kernel_term(r)?;
2680 let domain = Term::Global(identity_domain(l, r).to_string());
2681 Ok(Term::App(
2682 Box::new(Term::App(
2683 Box::new(Term::App(
2684 Box::new(Term::Global("Eq".to_string())),
2685 Box::new(domain),
2686 )),
2687 Box::new(l_term),
2688 )),
2689 Box::new(r_term),
2690 ))
2691 }
2692 ProofExpr::Exists { variable, body } => {
2696 let var_type = Term::Global(existential_domain(variable, body));
2697 let body_type = proof_expr_to_type(body)?;
2698
2699 let predicate = Term::Lambda {
2701 param: variable.clone(),
2702 param_type: Box::new(var_type.clone()),
2703 body: Box::new(body_type),
2704 };
2705
2706 Ok(Term::App(
2707 Box::new(Term::App(
2708 Box::new(Term::Global("Ex".to_string())),
2709 Box::new(var_type),
2710 )),
2711 Box::new(predicate),
2712 ))
2713 }
2714 ProofExpr::Temporal { operator, body } => Ok(Term::App(
2720 Box::new(Term::Global(operator.clone())),
2721 Box::new(proof_expr_to_type(body)?),
2722 )),
2723 _ => Err(KernelError::CertificationError(format!(
2724 "Cannot convert {:?} to kernel type",
2725 expr
2726 ))),
2727 }
2728}
2729
2730fn kernel_arith_name(name: &str) -> &str {
2740 match name {
2741 "Add" => "add",
2742 "Sub" => "sub",
2743 "Mul" => "mul",
2744 "Div" => "div",
2745 other => other,
2746 }
2747}
2748
2749fn is_arith_builtin(name: &str) -> bool {
2754 matches!(
2755 name,
2756 "le" | "lt"
2757 | "ge"
2758 | "gt"
2759 | "add"
2760 | "sub"
2761 | "mul"
2762 | "div"
2763 | "mod"
2764 | "Add"
2765 | "Sub"
2766 | "Mul"
2767 | "Div"
2768 )
2769}
2770
2771fn proof_term_to_kernel_term_entity(term: &ProofTerm) -> KernelResult<Term> {
2782 match term {
2783 ProofTerm::Constant(name) => Ok(Term::Global(name.clone())),
2784 ProofTerm::Variable(name) | ProofTerm::BoundVarRef(name) => Ok(Term::Var(name.clone())),
2785 ProofTerm::Function(name, args) => {
2786 let arith = is_arith_builtin(name);
2787 let mut result = Term::Global(kernel_arith_name(name).to_string());
2788 for arg in args {
2789 let arg_term = if arith {
2790 proof_term_to_kernel_term(arg)?
2791 } else {
2792 proof_term_to_kernel_term_entity(arg)?
2793 };
2794 result = Term::App(Box::new(result), Box::new(arg_term));
2795 }
2796 Ok(result)
2797 }
2798 ProofTerm::Group(_) => Err(KernelError::CertificationError(
2799 "Cannot convert Group to kernel term".to_string(),
2800 )),
2801 }
2802}
2803
2804pub(crate) fn proof_term_to_kernel_term(term: &ProofTerm) -> KernelResult<Term> {
2805 match term {
2806 ProofTerm::Constant(name) => match crate::numeral::literal_of_constant(name) {
2810 Some(lit) => Ok(Term::Lit(lit)),
2811 None => Ok(Term::Global(name.clone())),
2812 },
2813 ProofTerm::Variable(name) => Ok(Term::Var(name.clone())),
2814 ProofTerm::BoundVarRef(name) => Ok(Term::Var(name.clone())),
2815 ProofTerm::Function(name, args) => {
2816 let mut result = Term::Global(kernel_arith_name(name).to_string());
2819 for arg in args {
2820 let arg_term = proof_term_to_kernel_term(arg)?;
2821 result = Term::App(Box::new(result), Box::new(arg_term));
2822 }
2823 Ok(result)
2824 }
2825 ProofTerm::Group(_) => Err(KernelError::CertificationError(
2826 "Cannot convert Group to kernel term".to_string(),
2827 )),
2828 }
2829}
2830
2831fn decidable_instance_for(prop: &Term, kctx: &Context) -> Option<Term> {
2855 let mut candidates: Vec<(String, Term)> = Vec::new();
2856 let types = kctx
2857 .iter_definitions()
2858 .map(|(n, ty, _)| (n, ty))
2859 .chain(kctx.iter_declarations());
2860 for (name, ty) in types {
2861 let mut binders: Vec<String> = Vec::new();
2862 let mut cur = ty;
2863 while let Term::Pi {
2864 param, body_type, ..
2865 } = cur
2866 {
2867 binders.push(param.clone());
2868 cur = body_type;
2869 }
2870 let Term::App(head, pattern) = cur else {
2871 continue;
2872 };
2873 if !matches!(head.as_ref(), Term::Global(g) if g == "Decidable") {
2874 continue;
2875 }
2876 if let Term::Var(subject) = pattern.as_ref() {
2878 if binders.iter().any(|b| b == subject) {
2879 continue;
2880 }
2881 }
2882 let mut bound: std::collections::HashMap<String, Term> = std::collections::HashMap::new();
2883 if !match_instance_pattern(pattern, prop, &binders, &mut bound) {
2884 continue;
2885 }
2886 let mut applied = Term::Global(name.to_string());
2887 let mut complete = true;
2888 for b in &binders {
2889 match bound.get(b) {
2890 Some(t) => applied = Term::App(Box::new(applied), Box::new(t.clone())),
2891 None => {
2892 complete = false;
2893 break;
2894 }
2895 }
2896 }
2897 if complete {
2898 candidates.push((name.to_string(), applied));
2899 }
2900 }
2901 candidates.sort_by(|a, b| a.0.cmp(&b.0));
2902 candidates.into_iter().next().map(|(_, t)| t)
2903}
2904
2905fn match_instance_pattern(
2908 pattern: &Term,
2909 target: &Term,
2910 metas: &[String],
2911 bound: &mut std::collections::HashMap<String, Term>,
2912) -> bool {
2913 if let Term::Var(name) = pattern {
2914 if metas.iter().any(|m| m == name) {
2915 return match bound.get(name) {
2916 Some(seen) => seen == target,
2917 None => {
2918 bound.insert(name.clone(), target.clone());
2919 true
2920 }
2921 };
2922 }
2923 }
2924 match (pattern, target) {
2925 (Term::App(pf, pa), Term::App(tf, ta)) => {
2926 match_instance_pattern(pf, tf, metas, bound)
2927 && match_instance_pattern(pa, ta, metas, bound)
2928 }
2929 (p, t) => p == t,
2930 }
2931}
2932
2933fn identity_domain(l: &ProofTerm, r: &ProofTerm) -> &'static str {
2938 match (term_domain(l), term_domain(r)) {
2939 ("Bool", _) | (_, "Bool") => "Bool",
2940 ("Int", _) | (_, "Int") => "Int",
2941 _ => "Entity",
2942 }
2943}
2944
2945fn term_domain(t: &ProofTerm) -> &'static str {
2948 match t {
2949 ProofTerm::Function(n, _) if matches!(n.as_str(), "le" | "lt" | "ge" | "gt") => "Bool",
2950 ProofTerm::Function(n, _)
2951 if matches!(
2952 n.as_str(),
2953 "add" | "sub" | "mul" | "div" | "mod" | "Add" | "Sub" | "Mul" | "Div"
2954 ) =>
2955 {
2956 "Int"
2957 }
2958 ProofTerm::Constant(s) if s == "true" || s == "false" => "Bool",
2959 ProofTerm::Constant(s) if crate::numeral::is_numeral(s) => "Int",
2960 _ => "Entity",
2961 }
2962}
2963
2964fn resolved_domain(t: &ProofTerm, kctx: &Context) -> String {
2971 let syntactic = term_domain(t);
2972 if syntactic != "Entity" {
2973 return syntactic.to_string();
2974 }
2975 match t {
2976 ProofTerm::Function(name, _) => {
2977 if let Some(ty) = kctx.get_global(name) {
2978 let mut cur = ty;
2979 while let Term::Pi { body_type, .. } = cur {
2980 cur = body_type;
2981 }
2982 if let Term::Global(g) = cur {
2983 return g.clone();
2984 }
2985 }
2986 }
2987 ProofTerm::Constant(name) | ProofTerm::Variable(name) | ProofTerm::BoundVarRef(name) => {
2996 if let Some(Term::Global(g)) = kctx.get_global(name).or_else(|| kctx.get(name)) {
2997 return g.clone();
2998 }
2999 }
3000 _ => {}
3001 }
3002 syntactic.to_string()
3003}
3004
3005fn resolved_identity_domain(l: &ProofTerm, r: &ProofTerm, kctx: &Context) -> String {
3010 let (dl, dr) = (resolved_domain(l, kctx), resolved_domain(r, kctx));
3011 if dl == "Bool" || dr == "Bool" {
3012 "Bool".to_string()
3013 } else if dl == "Int" || dr == "Int" {
3014 "Int".to_string()
3015 } else if dl != "Entity" {
3016 dl
3017 } else {
3018 dr
3019 }
3020}
3021
3022fn lt_terms(expr: &ProofExpr) -> KernelResult<(ProofTerm, ProofTerm)> {
3024 if let ProofExpr::Identity(lhs, rhs) = expr {
3025 if let (ProofTerm::Function(name, args), ProofTerm::Constant(t)) = (lhs, rhs) {
3026 if name == "lt" && args.len() == 2 && t == "true" {
3027 return Ok((args[0].clone(), args[1].clone()));
3028 }
3029 }
3030 }
3031 Err(KernelError::CertificationError(format!(
3032 "expected a strict inequality `lt(a, b) = true`, got {expr:?}"
3033 )))
3034}
3035
3036fn le_terms(expr: &ProofExpr) -> KernelResult<(ProofTerm, ProofTerm)> {
3039 if let ProofExpr::Identity(lhs, _) = expr {
3040 if let ProofTerm::Function(name, args) = lhs {
3041 if name == "le" && args.len() == 2 {
3042 return Ok((args[0].clone(), args[1].clone()));
3043 }
3044 }
3045 }
3046 Err(KernelError::CertificationError(format!(
3047 "expected an `le(a, b) = true` inequality, got {:?}",
3048 expr
3049 )))
3050}
3051
3052fn add_terms(t: &ProofTerm) -> KernelResult<(ProofTerm, ProofTerm)> {
3054 binop_terms("add", t)
3055}
3056
3057fn binop_terms(op: &str, t: &ProofTerm) -> KernelResult<(ProofTerm, ProofTerm)> {
3059 if let ProofTerm::Function(name, args) = t {
3060 if name == op && args.len() == 2 {
3061 return Ok((args[0].clone(), args[1].clone()));
3062 }
3063 }
3064 Err(KernelError::CertificationError(format!(
3065 "expected `{}(x, y)`, got {:?}",
3066 op, t
3067 )))
3068}
3069
3070fn build_bool_discriminator(h: Term) -> Term {
3075 let g = |s: &str| Term::Global(s.to_string());
3076 let motive = Term::Lambda {
3078 param: "b".to_string(),
3079 param_type: Box::new(g("Bool")),
3080 body: Box::new(Term::Match {
3081 discriminant: Box::new(Term::Var("b".to_string())),
3082 motive: Box::new(Term::Lambda {
3083 param: "_".to_string(),
3084 param_type: Box::new(g("Bool")),
3085 body: Box::new(Term::Sort(logicaffeine_kernel::Universe::Prop)),
3086 }),
3087 cases: vec![g("False"), g("True")],
3088 }),
3089 };
3090 [g("Bool"), g("false"), motive, g("I"), g("true"), h]
3091 .into_iter()
3092 .fold(g("Eq_rec"), |acc, arg| {
3093 Term::App(Box::new(acc), Box::new(arg))
3094 })
3095}
3096
3097fn extract_motive_body(
3104 conclusion: &ProofExpr,
3105 var_name: &str,
3106 kctx: &Context,
3107) -> KernelResult<Term> {
3108 match conclusion {
3109 ProofExpr::ForAll { variable, body } if variable == var_name => {
3110 proof_expr_to_type_ctx(body, kctx)
3114 }
3115 _ => Err(KernelError::CertificationError(format!(
3116 "StructuralInduction conclusion must be ForAll over {}, got {:?}",
3117 var_name, conclusion
3118 ))),
3119 }
3120}
3121
3122fn compute_ih_conclusion(
3125 conclusion: &ProofExpr,
3126 orig_var: &str,
3127 step_var: &str,
3128) -> KernelResult<ProofExpr> {
3129 match conclusion {
3130 ProofExpr::ForAll { body, .. } => Ok(substitute_var_in_expr(body, orig_var, step_var)),
3131 _ => Err(KernelError::CertificationError(
3132 "Expected ForAll for IH computation".to_string(),
3133 )),
3134 }
3135}
3136
3137fn constructor_arg_types(ctx: &Context, constructor: &str) -> KernelResult<Vec<Term>> {
3143 let mut ty = ctx
3144 .get_global(constructor)
3145 .ok_or_else(|| {
3146 KernelError::CertificationError(format!("unknown constructor {}", constructor))
3147 })?
3148 .clone();
3149 let mut args = Vec::new();
3150 while let Term::Pi {
3151 param_type,
3152 body_type,
3153 ..
3154 } = ty
3155 {
3156 args.push(*param_type);
3157 ty = *body_type;
3158 }
3159 Ok(args)
3160}
3161
3162fn build_motive(ind_type: &str, result_type: &Term, motive_param: &str) -> Term {
3166 Term::Lambda {
3167 param: motive_param.to_string(),
3168 param_type: Box::new(Term::Global(ind_type.to_string())),
3169 body: Box::new(result_type.clone()),
3170 }
3171}
3172
3173fn substitute_var_in_expr(expr: &ProofExpr, from: &str, to: &str) -> ProofExpr {
3175 match expr {
3176 ProofExpr::Atom(s) if s == from => ProofExpr::Atom(to.to_string()),
3177 ProofExpr::Atom(s) => ProofExpr::Atom(s.clone()),
3178
3179 ProofExpr::TypedVar { name, typename } => ProofExpr::TypedVar {
3180 name: if name == from {
3181 to.to_string()
3182 } else {
3183 name.clone()
3184 },
3185 typename: typename.clone(),
3186 },
3187
3188 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
3189 name: name.clone(),
3190 args: args
3191 .iter()
3192 .map(|a| substitute_var_in_term(a, from, to))
3193 .collect(),
3194 world: world.clone(),
3195 },
3196
3197 ProofExpr::Identity(l, r) => ProofExpr::Identity(
3198 substitute_var_in_term(l, from, to),
3199 substitute_var_in_term(r, from, to),
3200 ),
3201
3202 ProofExpr::And(l, r) => ProofExpr::And(
3203 Box::new(substitute_var_in_expr(l, from, to)),
3204 Box::new(substitute_var_in_expr(r, from, to)),
3205 ),
3206
3207 ProofExpr::Or(l, r) => ProofExpr::Or(
3208 Box::new(substitute_var_in_expr(l, from, to)),
3209 Box::new(substitute_var_in_expr(r, from, to)),
3210 ),
3211
3212 ProofExpr::Implies(l, r) => ProofExpr::Implies(
3213 Box::new(substitute_var_in_expr(l, from, to)),
3214 Box::new(substitute_var_in_expr(r, from, to)),
3215 ),
3216
3217 ProofExpr::Iff(l, r) => ProofExpr::Iff(
3218 Box::new(substitute_var_in_expr(l, from, to)),
3219 Box::new(substitute_var_in_expr(r, from, to)),
3220 ),
3221
3222 ProofExpr::Not(inner) => ProofExpr::Not(Box::new(substitute_var_in_expr(inner, from, to))),
3223
3224 ProofExpr::ForAll { variable, body } if variable != from => ProofExpr::ForAll {
3226 variable: variable.clone(),
3227 body: Box::new(substitute_var_in_expr(body, from, to)),
3228 },
3229
3230 ProofExpr::Exists { variable, body } if variable != from => ProofExpr::Exists {
3231 variable: variable.clone(),
3232 body: Box::new(substitute_var_in_expr(body, from, to)),
3233 },
3234
3235 ProofExpr::Lambda { variable, body } if variable != from => ProofExpr::Lambda {
3236 variable: variable.clone(),
3237 body: Box::new(substitute_var_in_expr(body, from, to)),
3238 },
3239
3240 ProofExpr::App(f, a) => ProofExpr::App(
3241 Box::new(substitute_var_in_expr(f, from, to)),
3242 Box::new(substitute_var_in_expr(a, from, to)),
3243 ),
3244
3245 ProofExpr::Term(t) => ProofExpr::Term(substitute_var_in_term(t, from, to)),
3246
3247 ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
3248 name: name.clone(),
3249 args: args
3250 .iter()
3251 .map(|a| substitute_var_in_expr(a, from, to))
3252 .collect(),
3253 },
3254
3255 other => other.clone(),
3257 }
3258}
3259
3260fn substitute_var_in_term(term: &ProofTerm, from: &str, to: &str) -> ProofTerm {
3262 match term {
3263 ProofTerm::Variable(s) if s == from => ProofTerm::Variable(to.to_string()),
3264 ProofTerm::Variable(s) => ProofTerm::Variable(s.clone()),
3265 ProofTerm::Constant(s) => ProofTerm::Constant(s.clone()),
3266 ProofTerm::BoundVarRef(s) if s == from => ProofTerm::BoundVarRef(to.to_string()),
3267 ProofTerm::BoundVarRef(s) => ProofTerm::BoundVarRef(s.clone()),
3268 ProofTerm::Function(name, args) => ProofTerm::Function(
3269 name.clone(),
3270 args.iter()
3271 .map(|a| substitute_var_in_term(a, from, to))
3272 .collect(),
3273 ),
3274 ProofTerm::Group(terms) => ProofTerm::Group(
3275 terms
3276 .iter()
3277 .map(|t| substitute_var_in_term(t, from, to))
3278 .collect(),
3279 ),
3280 }
3281}
3282
3283#[cfg(test)]
3284#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/certifier/canonical_arith_boundary_tests.rs"]
3285mod canonical_arith_boundary_tests;
3286
3287#[cfg(test)]
3288#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/certifier/connective_lowering_tests.rs"]
3289mod connective_lowering_tests;