1use logicaffeine_kernel::{
19 int_lit, lit_bigint, normalize, normalize_at, normalize_checked, BigInt, Context, Literal,
20 Term, Transparency,
21};
22
23fn global(name: &str) -> Term {
24 Term::Global(name.to_string())
25}
26fn app(f: Term, x: Term) -> Term {
27 Term::App(Box::new(f), Box::new(x))
28}
29fn app2(f: Term, x: Term, y: Term) -> Term {
30 app(app(f, x), y)
31}
32fn app3(f: Term, x: Term, y: Term, z: Term) -> Term {
33 app(app2(f, x, y), z)
34}
35fn int() -> Term {
36 global("Int")
37}
38
39fn refl(t: Term) -> Term {
41 app2(global("refl"), int(), t)
42}
43
44fn eq_sym(x: Term, y: Term, proof: Term) -> Term {
46 app(app(app(app(global("Eq_sym"), int()), x), y), proof)
47}
48
49fn match_bin(t: &Term, op: &str) -> Option<(Term, Term)> {
51 if let Term::App(f, b) = t {
52 if let Term::App(g, a) = f.as_ref() {
53 if let Term::Global(name) = g.as_ref() {
54 if name == op {
55 return Some(((**a).clone(), (**b).clone()));
56 }
57 }
58 }
59 }
60 None
61}
62
63fn conv(ctx: &Context, a: &Term, b: &Term) -> bool {
65 normalize(ctx, a) == normalize(ctx, b)
66}
67
68pub fn prove_int_eq(ctx: &Context, lhs: &Term, rhs: &Term) -> Option<Term> {
73 if !logicaffeine_kernel::int_inductive::supports_integer_polynomial_operations(ctx) {
74 return None;
75 }
76 let lhs = polynomial_view(ctx, lhs);
80 let rhs = polynomial_view(ctx, rhs);
81 let (lhs, rhs) = (&lhs, &rhs);
82
83 if ground_integer_expression(lhs) && ground_integer_expression(rhs) {
87 let left_value = normalize_checked(ctx, lhs).ok()?;
88 let right_value = normalize_checked(ctx, rhs).ok()?;
89 return match (&left_value, &right_value) {
90 (
91 Term::Lit(Literal::Int(_) | Literal::BigInt(_)),
92 Term::Lit(Literal::Int(_) | Literal::BigInt(_)),
93 ) if left_value == right_value => Some(refl(left_value)),
94 _ => None,
95 };
96 }
97
98 let mut polys = Polynomials { atoms: Vec::new() };
102 let pl = to_poly(&mut polys, ctx, lhs);
103 let pr = to_poly(&mut polys, ctx, rhs);
104 if pl != pr {
105 return None;
106 }
107
108 if let Some(p) = prove_eq(ctx, lhs, rhs, MAX_REWRITE_DEPTH) {
110 return Some(p);
111 }
112 prove_by_normalization(ctx, lhs, rhs)
116}
117
118struct Polynomials {
126 atoms: Vec<Term>,
127}
128impl Polynomials {
129 fn atom_id(&mut self, t: &Term) -> usize {
130 if let Some(i) = self.atoms.iter().position(|a| a == t) {
131 i
132 } else {
133 self.atoms.push(t.clone());
134 self.atoms.len() - 1
135 }
136 }
137}
138
139type Mono = Vec<usize>;
141type Poly = Vec<(Mono, BigInt)>;
143
144fn poly_canon(mut terms: Poly) -> Poly {
145 for (m, _) in terms.iter_mut() {
146 m.sort_unstable();
147 }
148 terms.sort_by(|a, b| a.0.cmp(&b.0));
149 let mut out: Poly = Vec::new();
150 for (m, c) in terms {
151 if c.is_zero() {
152 continue;
153 }
154 if let Some(last) = out.last_mut() {
155 if last.0 == m {
156 last.1 = last.1.add(&c);
157 if last.1.is_zero() {
158 out.pop();
159 }
160 continue;
161 }
162 }
163 out.push((m, c));
164 }
165 out
166}
167
168fn poly_add(a: &Poly, b: &Poly) -> Poly {
169 let mut t = a.clone();
170 t.extend(b.iter().cloned());
171 poly_canon(t)
172}
173fn poly_mul(a: &Poly, b: &Poly) -> Poly {
174 let mut t = Vec::new();
175 for (m1, c1) in a {
176 for (m2, c2) in b {
177 let mut m = m1.clone();
178 m.extend(m2.iter().cloned());
179 t.push((m, c1.mul(c2)));
180 }
181 }
182 poly_canon(t)
183}
184fn poly_scale(k: i64, a: &Poly) -> Poly {
185 let k = BigInt::from_i64(k);
186 poly_canon(a.iter().map(|(m, c)| (m.clone(), c.mul(&k))).collect())
187}
188
189fn ground_integer_expression(term: &Term) -> bool {
192 let mut pending = vec![term];
193 while let Some(term) = pending.pop() {
194 match term {
195 Term::Lit(Literal::Int(_) | Literal::BigInt(_)) => {}
196 Term::App(function, right) => {
197 let Term::App(head, left) = function.as_ref() else {
198 return false;
199 };
200 let Term::Global(name) = head.as_ref() else {
201 return false;
202 };
203 if !matches!(name.as_str(), "add" | "mul" | "sub") {
204 return false;
205 }
206 pending.push(left);
207 pending.push(right);
208 }
209 _ => return false,
210 }
211 }
212 true
213}
214
215fn polynomial_view(ctx: &Context, term: &Term) -> Term {
218 normalize_at(
219 ctx,
220 term,
221 Transparency::Excluding(&|name| matches!(name, "add" | "mul" | "sub")),
222 )
223}
224
225fn to_poly(p: &mut Polynomials, ctx: &Context, t: &Term) -> Poly {
227 let t = polynomial_view(ctx, t);
228 if let Term::Lit(literal) = &t {
229 if let Some(n) = lit_bigint(literal) {
230 return if n.is_zero() {
231 vec![]
232 } else {
233 vec![(vec![], n)]
234 };
235 }
236 }
237 if let Some((a, b)) = match_bin(&t, "add") {
238 return poly_add(&to_poly(p, ctx, &a), &to_poly(p, ctx, &b));
239 }
240 if let Some((a, b)) = match_bin(&t, "mul") {
241 return poly_mul(&to_poly(p, ctx, &a), &to_poly(p, ctx, &b));
242 }
243 if let Some((a, b)) = match_bin(&t, "sub") {
244 return poly_add(&to_poly(p, ctx, &a), &poly_scale(-1, &to_poly(p, ctx, &b)));
245 }
246 let id = p.atom_id(&t);
247 vec![(vec![id], BigInt::from_i64(1))]
248}
249
250fn lit_t(n: i64) -> Term {
261 Term::Lit(Literal::Int(n))
262}
263
264fn coefficient_term(n: &BigInt) -> Term {
266 Term::Lit(int_lit(n.clone()))
267}
268fn ax1(name: &str, a: Term) -> Term {
269 app(global(name), a)
270}
271fn ax2(name: &str, a: Term, b: Term) -> Term {
272 app2(global(name), a, b)
273}
274fn ax3(name: &str, a: Term, b: Term, c: Term) -> Term {
275 app3(global(name), a, b, c)
276}
277
278fn mono_to_term(mono: &[usize], atoms: &[Term]) -> Option<Term> {
280 let mut iter = mono.iter();
281 let first = *iter.next()?;
282 let mut t = atoms[first].clone();
283 for &id in iter {
284 t = ax2("mul", t, atoms[id].clone());
285 }
286 Some(t)
287}
288fn scaled_term(mono: &[usize], coeff: &BigInt, atoms: &[Term]) -> Term {
290 match mono_to_term(mono, atoms) {
291 None => coefficient_term(coeff),
292 Some(m) if coeff.to_i64() == Some(1) => m,
293 Some(m) => ax2("mul", coefficient_term(coeff), m),
294 }
295}
296fn reify(poly: &[(Mono, BigInt)], atoms: &[Term]) -> Term {
298 let mut iter = poly.iter().filter(|(_, c)| !c.is_zero());
302 let Some((m0, c0)) = iter.next() else {
303 return lit_t(0);
304 };
305 let mut t = scaled_term(m0, c0, atoms);
306 for (m, c) in iter {
307 t = ax2("add", t, scaled_term(m, c, atoms));
308 }
309 t
310}
311
312fn as_scaled_mul(c: &BigInt, m_term: &Term) -> Term {
315 if c.to_i64() == Some(1) {
316 let mul1m = ax2("mul", lit_t(1), m_term.clone());
318 let chain = eq_trans(
319 mul1m.clone(),
320 ax2("mul", m_term.clone(), lit_t(1)),
321 m_term.clone(),
322 ax2("mul_comm", lit_t(1), m_term.clone()),
323 ax1("mul_one", m_term.clone()),
324 );
325 eq_sym(mul1m, m_term.clone(), chain)
326 } else {
327 refl(ax2("mul", coefficient_term(c), m_term.clone()))
328 }
329}
330
331fn rev_distrib(c1: &BigInt, c2: &BigInt, m_term: &Term) -> Term {
333 let big_c = ax2("add", coefficient_term(c1), coefficient_term(c2));
334 let mul_c1 = ax2("mul", coefficient_term(c1), m_term.clone());
335 let mul_c2 = ax2("mul", coefficient_term(c2), m_term.clone());
336 let s1 = ax2("mul_comm", big_c.clone(), m_term.clone());
338 let s2 = ax3(
340 "mul_distrib_add",
341 m_term.clone(),
342 coefficient_term(c1),
343 coefficient_term(c2),
344 );
345 let s3 = cong2(
347 "add",
348 &ax2("mul", m_term.clone(), coefficient_term(c1)),
349 &mul_c1,
350 &ax2("mul", m_term.clone(), coefficient_term(c2)),
351 &mul_c2,
352 ax2("mul_comm", m_term.clone(), coefficient_term(c1)),
353 ax2("mul_comm", m_term.clone(), coefficient_term(c2)),
354 );
355 let forward = eq_trans(
357 ax2("mul", big_c.clone(), m_term.clone()),
358 ax2("mul", m_term.clone(), big_c.clone()),
359 ax2("add", mul_c1.clone(), mul_c2.clone()),
360 s1,
361 eq_trans(
362 ax2("mul", m_term.clone(), big_c.clone()),
363 ax2(
364 "add",
365 ax2("mul", m_term.clone(), coefficient_term(c1)),
366 ax2("mul", m_term.clone(), coefficient_term(c2)),
367 ),
368 ax2("add", mul_c1.clone(), mul_c2.clone()),
369 s2,
370 s3,
371 ),
372 );
373 eq_sym(
374 ax2("mul", big_c, m_term.clone()),
375 ax2("add", mul_c1, mul_c2),
376 forward,
377 )
378}
379
380fn combine_coeff(m: &[usize], c1: &BigInt, c2: &BigInt, atoms: &[Term]) -> Option<Term> {
382 let t1 = scaled_term(m, c1, atoms);
383 let t2 = scaled_term(m, c2, atoms);
384 let sum = c1.add(c2);
385 let result = scaled_term(m, &sum, atoms);
386 let _ = (&t1, &t2, &result);
387 match mono_to_term(m, atoms) {
388 None => Some(refl(coefficient_term(&sum))),
390 Some(m_term) => {
391 let coerce = cong2(
393 "add",
394 &t1,
395 &ax2("mul", coefficient_term(c1), m_term.clone()),
396 &t2,
397 &ax2("mul", coefficient_term(c2), m_term.clone()),
398 as_scaled_mul(c1, &m_term),
399 as_scaled_mul(c2, &m_term),
400 );
401 let rd = rev_distrib(c1, c2, &m_term);
402 let coerced = ax2(
403 "add",
404 ax2("mul", coefficient_term(c1), m_term.clone()),
405 ax2("mul", coefficient_term(c2), m_term.clone()),
406 );
407 if sum.to_i64() != Some(1) {
408 Some(eq_trans(ax2("add", t1, t2), coerced, result, coerce, rd))
409 } else {
410 let mul1m = ax2("mul", lit_t(1), m_term.clone());
414 let to_bare = eq_trans(
415 mul1m.clone(),
416 ax2("mul", m_term.clone(), lit_t(1)),
417 m_term.clone(),
418 ax2("mul_comm", lit_t(1), m_term.clone()),
419 ax1("mul_one", m_term.clone()),
420 );
421 let inner = eq_trans(coerced.clone(), mul1m, result.clone(), rd, to_bare);
422 Some(eq_trans(ax2("add", t1, t2), coerced, result, coerce, inner))
423 }
424 }
425 }
426}
427
428fn swap_top(x: Term, y: Term, z: Term) -> Term {
430 let s1 = ax3("add_assoc", x.clone(), y.clone(), z.clone());
432 let s2 = cong2(
433 "add",
434 &x,
435 &x,
436 &ax2("add", y.clone(), z.clone()),
437 &ax2("add", z.clone(), y.clone()),
438 refl(x.clone()),
439 ax2("add_comm", y.clone(), z.clone()),
440 );
441 let s3 = eq_sym(
442 ax2("add", ax2("add", x.clone(), z.clone()), y.clone()),
443 ax2("add", x.clone(), ax2("add", z.clone(), y.clone())),
444 ax3("add_assoc", x.clone(), z.clone(), y.clone()),
445 );
446 eq_trans(
447 ax2("add", ax2("add", x.clone(), y.clone()), z.clone()),
448 ax2("add", x.clone(), ax2("add", y.clone(), z.clone())),
449 ax2("add", ax2("add", x.clone(), z.clone()), y.clone()),
450 s1,
451 eq_trans(
452 ax2("add", x.clone(), ax2("add", y.clone(), z.clone())),
453 ax2("add", x.clone(), ax2("add", z.clone(), y.clone())),
454 ax2("add", ax2("add", x.clone(), z.clone()), y),
455 s2,
456 s3,
457 ),
458 )
459}
460
461fn merge_term(
464 atoms: &[Term],
465 p: &[(Mono, BigInt)],
466 m: &[usize],
467 c: &BigInt,
468) -> Option<(Poly, Term)> {
469 let st = scaled_term(m, c, atoms);
470 if p.is_empty() {
471 let proof = eq_trans(
473 ax2("add", lit_t(0), st.clone()),
474 ax2("add", st.clone(), lit_t(0)),
475 st.clone(),
476 ax2("add_comm", lit_t(0), st.clone()),
477 ax1("add_zero", st.clone()),
478 );
479 return Some((vec![(m.to_vec(), c.clone())], proof));
480 }
481 let (ml, cl) = p.last().unwrap().clone();
482 let init = &p[..p.len() - 1];
483 let last_t = scaled_term(&ml, &cl, atoms);
484 let reify_p = reify(p, atoms);
485
486 use std::cmp::Ordering;
487 match m.to_vec().cmp(&ml) {
488 Ordering::Greater => {
489 let mut res = p.to_vec();
491 res.push((m.to_vec(), c.clone()));
492 Some((res, refl(ax2("add", reify_p, st))))
493 }
494 Ordering::Equal => {
495 if cl.add(c).is_zero() {
496 let cc = combine_coeff(&ml, &cl, c, atoms)?;
500 let cancel = match mono_to_term(&ml, atoms) {
501 None => cc, Some(m_term) => eq_trans(
503 ax2("add", last_t.clone(), st.clone()),
504 ax2("mul", lit_t(0), m_term.clone()),
505 lit_t(0),
506 cc,
507 eq_trans(
508 ax2("mul", lit_t(0), m_term.clone()),
509 ax2("mul", m_term.clone(), lit_t(0)),
510 lit_t(0),
511 ax2("mul_comm", lit_t(0), m_term.clone()),
512 ax1("mul_zero", m_term),
513 ),
514 ),
515 };
516 if init.is_empty() {
518 return Some((vec![], cancel));
519 }
520 let ri = reify(init, atoms);
521 let assoc = ax3("add_assoc", ri.clone(), last_t.clone(), st.clone());
522 let cong = cong2(
523 "add",
524 &ri,
525 &ri,
526 &ax2("add", last_t.clone(), st.clone()),
527 &lit_t(0),
528 refl(ri.clone()),
529 cancel,
530 );
531 let azero = ax1("add_zero", ri.clone());
532 let proof = eq_trans(
533 ax2("add", ax2("add", ri.clone(), last_t.clone()), st.clone()),
534 ax2("add", ri.clone(), ax2("add", last_t.clone(), st.clone())),
535 ri.clone(),
536 assoc,
537 eq_trans(
538 ax2("add", ri.clone(), ax2("add", last_t.clone(), st.clone())),
539 ax2("add", ri.clone(), lit_t(0)),
540 ri.clone(),
541 cong,
542 azero,
543 ),
544 );
545 return Some((init.to_vec(), proof));
546 }
547 let cc = combine_coeff(&ml, &cl, c, atoms)?; let combined = scaled_term(&ml, &cl.add(c), atoms);
549 if init.is_empty() {
550 Some((vec![(ml, cl.add(c))], cc))
551 } else {
552 let ri = reify(init, atoms);
553 let assoc = ax3("add_assoc", ri.clone(), last_t.clone(), st.clone());
554 let cong = cong2(
555 "add",
556 &ri,
557 &ri,
558 &ax2("add", last_t.clone(), st.clone()),
559 &combined,
560 refl(ri.clone()),
561 cc,
562 );
563 let proof = eq_trans(
564 ax2("add", ax2("add", ri.clone(), last_t), st),
565 ax2(
566 "add",
567 ri.clone(),
568 ax2(
569 "add",
570 scaled_term(&ml, &cl, atoms),
571 scaled_term(m, c, atoms),
572 ),
573 ),
574 ax2("add", ri.clone(), combined),
575 assoc,
576 cong,
577 );
578 let mut res = init.to_vec();
579 res.push((ml, cl.add(c)));
580 Some((res, proof))
581 }
582 }
583 Ordering::Less => {
584 if init.is_empty() {
585 let mut res = vec![(m.to_vec(), c.clone())];
587 res.push((ml, cl));
588 Some((res, ax2("add_comm", last_t, st)))
589 } else {
590 let ri = reify(init, atoms);
591 let swap = swap_top(ri.clone(), last_t.clone(), st.clone());
592 let (init2, inner) = merge_term(atoms, init, m, c)?; let ri2 = reify(&init2, atoms);
594 let cong = cong2(
595 "add",
596 &ax2("add", ri.clone(), st.clone()),
597 &ri2,
598 &last_t,
599 &last_t,
600 inner,
601 refl(last_t.clone()),
602 );
603 let proof = eq_trans(
604 ax2("add", ax2("add", ri.clone(), last_t.clone()), st.clone()),
605 ax2("add", ax2("add", ri, st.clone()), last_t.clone()),
606 ax2("add", ri2.clone(), last_t.clone()),
607 swap,
608 cong,
609 );
610 let proof = if init2.is_empty() {
614 let zfix = eq_trans(
615 ax2("add", lit_t(0), last_t.clone()),
616 ax2("add", last_t.clone(), lit_t(0)),
617 last_t.clone(),
618 ax2("add_comm", lit_t(0), last_t.clone()),
619 ax1("add_zero", last_t.clone()),
620 );
621 eq_trans(
622 ax2(
623 "add",
624 ax2("add", reify(init, atoms), last_t.clone()),
625 st.clone(),
626 ),
627 ax2("add", ri2, last_t.clone()),
628 last_t.clone(),
629 proof,
630 zfix,
631 )
632 } else {
633 proof
634 };
635 let mut res = init2;
636 res.push((ml, cl));
637 Some((res, proof))
638 }
639 }
640 }
641}
642
643fn merge_canonical(
646 atoms: &[Term],
647 pa: &[(Mono, BigInt)],
648 pb: &[(Mono, BigInt)],
649) -> Option<(Poly, Term)> {
650 let ra = reify(pa, atoms);
651 if pb.is_empty() {
652 return Some((pa.to_vec(), ax1("add_zero", ra)));
654 }
655 if pb.len() == 1 {
656 let (m, c) = &pb[0];
657 return merge_term(atoms, pa, m, c);
658 }
659 let (ml, cl) = pb.last().unwrap().clone();
660 let pb_init = &pb[..pb.len() - 1];
661 let rbi = reify(pb_init, atoms);
662 let slast = scaled_term(&ml, &cl, atoms);
663 let assoc_sym = eq_sym(
665 ax2("add", ax2("add", ra.clone(), rbi.clone()), slast.clone()),
666 ax2("add", ra.clone(), ax2("add", rbi.clone(), slast.clone())),
667 ax3("add_assoc", ra.clone(), rbi.clone(), slast.clone()),
668 );
669 let (m1, p1) = merge_canonical(atoms, pa, pb_init)?; let rm1 = reify(&m1, atoms);
671 let cong = cong2(
672 "add",
673 &ax2("add", ra.clone(), rbi.clone()),
674 &rm1,
675 &slast,
676 &slast,
677 p1,
678 refl(slast.clone()),
679 );
680 let (m2, p2) = merge_term(atoms, &m1, &ml, &cl)?; let rm2 = reify(&m2, atoms);
682 let proof = eq_trans(
683 ax2("add", ra.clone(), ax2("add", rbi.clone(), slast.clone())),
684 ax2("add", ax2("add", ra, rbi), slast.clone()),
685 rm2,
686 assoc_sym,
687 eq_trans(
688 ax2(
689 "add",
690 ax2("add", reify(pa, atoms), reify(pb_init, atoms)),
691 slast.clone(),
692 ),
693 ax2("add", rm1, slast),
694 reify(&m2, atoms),
695 cong,
696 p2,
697 ),
698 );
699 Some((m2, proof))
700}
701
702fn atom_index(polys: &Polynomials, t: &Term) -> Option<usize> {
705 polys.atoms.iter().position(|a| a == t)
706}
707
708fn swap_last(a: &Term, b: &Term, x: &Term) -> Term {
711 let m_ab_x = ax2("mul", ax2("mul", a.clone(), b.clone()), x.clone());
712 let m_a_bx = ax2("mul", a.clone(), ax2("mul", b.clone(), x.clone()));
713 let m_a_xb = ax2("mul", a.clone(), ax2("mul", x.clone(), b.clone()));
714 let m_ax_b = ax2("mul", ax2("mul", a.clone(), x.clone()), b.clone());
715 let s1 = ax3("mul_assoc", a.clone(), b.clone(), x.clone());
717 let s2 = cong2(
719 "mul",
720 a,
721 a,
722 &ax2("mul", b.clone(), x.clone()),
723 &ax2("mul", x.clone(), b.clone()),
724 refl(a.clone()),
725 ax2("mul_comm", b.clone(), x.clone()),
726 );
727 let s3 = eq_sym(
729 m_ax_b.clone(),
730 m_a_xb.clone(),
731 ax3("mul_assoc", a.clone(), x.clone(), b.clone()),
732 );
733 let inner = eq_trans(m_a_bx.clone(), m_a_xb, m_ax_b.clone(), s2, s3); eq_trans(m_ab_x, m_a_bx, m_ax_b, s1, inner)
735}
736
737fn insert_atom(polys: &Polynomials, p: &Term, x: &Term) -> Option<(Term, Term)> {
740 let xid = atom_index(polys, x)?;
741 let prod = ax2("mul", p.clone(), x.clone());
742 match match_bin(p, "mul") {
743 None => {
744 let pid = atom_index(polys, p)?;
745 if pid <= xid {
746 Some((prod.clone(), refl(prod)))
747 } else {
748 Some((
749 ax2("mul", x.clone(), p.clone()),
750 ax2("mul_comm", p.clone(), x.clone()),
751 ))
752 }
753 }
754 Some((pinit, plast)) => {
755 let lastid = atom_index(polys, &plast)?;
756 if lastid <= xid {
757 Some((prod.clone(), refl(prod)))
758 } else {
759 let swap = swap_last(&pinit, &plast, x); let (inner, pin) = insert_atom(polys, &pinit, x)?; let cong = cong2(
763 "mul",
764 &ax2("mul", pinit.clone(), x.clone()),
765 &inner,
766 &plast,
767 &plast,
768 pin,
769 refl(plast.clone()),
770 );
771 let result = ax2("mul", inner, plast.clone());
772 let proof = eq_trans(
773 prod,
774 ax2("mul", ax2("mul", pinit.clone(), x.clone()), plast.clone()),
775 result.clone(),
776 swap,
777 cong,
778 );
779 Some((result, proof))
780 }
781 }
782 }
783}
784
785fn merge_sorted(polys: &Polynomials, ca: &Term, cb: &Term) -> Option<(Term, Term)> {
788 match match_bin(cb, "mul") {
789 None => insert_atom(polys, ca, cb),
790 Some((cbinit, cblast)) => {
791 let assoc_rev = eq_sym(
793 ax2(
794 "mul",
795 ax2("mul", ca.clone(), cbinit.clone()),
796 cblast.clone(),
797 ),
798 ax2(
799 "mul",
800 ca.clone(),
801 ax2("mul", cbinit.clone(), cblast.clone()),
802 ),
803 ax3("mul_assoc", ca.clone(), cbinit.clone(), cblast.clone()),
804 );
805 let (merged1, p1) = merge_sorted(polys, ca, &cbinit)?; let cong = cong2(
807 "mul",
808 &ax2("mul", ca.clone(), cbinit.clone()),
809 &merged1,
810 &cblast,
811 &cblast,
812 p1,
813 refl(cblast.clone()),
814 );
815 let (merged2, p2) = insert_atom(polys, &merged1, &cblast)?; let start = ax2("mul", ca.clone(), cb.clone());
817 let mid = ax2(
818 "mul",
819 ax2("mul", ca.clone(), cbinit.clone()),
820 cblast.clone(),
821 );
822 let proof = eq_trans(
823 start,
824 mid.clone(),
825 merged2.clone(),
826 assoc_rev,
827 eq_trans(
828 mid,
829 ax2("mul", merged1.clone(), cblast.clone()),
830 merged2.clone(),
831 cong,
832 p2,
833 ),
834 );
835 Some((merged2, proof))
836 }
837 }
838}
839
840fn split_coeff(t: &Term) -> (BigInt, Option<Term>) {
844 if let Term::Lit(literal) = t {
845 if let Some(n) = lit_bigint(literal) {
846 return (n, None);
847 }
848 }
849 if let Some((a, b)) = match_bin(t, "mul") {
850 if let Term::Lit(literal) = a {
851 if let Some(n) = lit_bigint(&literal) {
852 return (n, Some(b));
853 }
854 }
855 }
856 (BigInt::from_i64(1), Some(t.clone()))
857}
858
859fn swap_middle(p: &Term, q: &Term, r: &Term, s: &Term) -> Term {
863 let rs = ax2("mul", r.clone(), s.clone());
864 let qs = ax2("mul", q.clone(), s.clone());
865 let qr = ax2("mul", q.clone(), r.clone());
866 let rq = ax2("mul", r.clone(), q.clone());
867 let w0 = ax2("mul", ax2("mul", p.clone(), q.clone()), rs.clone());
868 let w1 = ax2("mul", p.clone(), ax2("mul", q.clone(), rs.clone()));
869 let w2 = ax2("mul", p.clone(), ax2("mul", qr.clone(), s.clone()));
870 let w3 = ax2("mul", p.clone(), ax2("mul", rq.clone(), s.clone()));
871 let w4 = ax2("mul", p.clone(), ax2("mul", r.clone(), qs.clone()));
872 let w5 = ax2("mul", ax2("mul", p.clone(), r.clone()), qs.clone());
873 let p01 = ax3("mul_assoc", p.clone(), q.clone(), rs.clone());
875 let p12 = cong2(
877 "mul",
878 p,
879 p,
880 &ax2("mul", q.clone(), rs.clone()),
881 &ax2("mul", qr.clone(), s.clone()),
882 refl(p.clone()),
883 eq_sym(
884 ax2("mul", qr.clone(), s.clone()),
885 ax2("mul", q.clone(), rs.clone()),
886 ax3("mul_assoc", q.clone(), r.clone(), s.clone()),
887 ),
888 );
889 let p23 = cong2(
891 "mul",
892 p,
893 p,
894 &ax2("mul", qr.clone(), s.clone()),
895 &ax2("mul", rq.clone(), s.clone()),
896 refl(p.clone()),
897 cong2(
898 "mul",
899 &qr,
900 &rq,
901 s,
902 s,
903 ax2("mul_comm", q.clone(), r.clone()),
904 refl(s.clone()),
905 ),
906 );
907 let p34 = cong2(
909 "mul",
910 p,
911 p,
912 &ax2("mul", rq.clone(), s.clone()),
913 &ax2("mul", r.clone(), qs.clone()),
914 refl(p.clone()),
915 ax3("mul_assoc", r.clone(), q.clone(), s.clone()),
916 );
917 let p45 = eq_sym(
919 w5.clone(),
920 w4.clone(),
921 ax3("mul_assoc", p.clone(), r.clone(), qs.clone()),
922 );
923 eq_trans(
924 w0,
925 w1.clone(),
926 w5.clone(),
927 p01,
928 eq_trans(
929 w1,
930 w2.clone(),
931 w5.clone(),
932 p12,
933 eq_trans(
934 w2,
935 w3.clone(),
936 w5.clone(),
937 p23,
938 eq_trans(w3, w4, w5, p34, p45),
939 ),
940 ),
941 )
942}
943
944fn merge_scaled(polys: &Polynomials, ca: &Term, cb: &Term) -> Option<(Term, Term)> {
951 let (c1, oa) = split_coeff(ca);
952 let (c2, ob) = split_coeff(cb);
953 let a = oa?;
954 let b = ob?;
955 let coeff = c1.mul(&c2);
956 let (merged, p_atoms) = merge_sorted(polys, &a, &b)?; let (lc1, lc2, lcoeff) = (
958 coefficient_term(&c1),
959 coefficient_term(&c2),
960 coefficient_term(&coeff),
961 );
962 let ca_u = ax2("mul", lc1.clone(), a.clone());
963 let cb_u = ax2("mul", lc2.clone(), b.clone());
964 let cvt_a = if c1.to_i64() == Some(1) {
965 as_scaled_mul(&c1, &a)
966 } else {
967 refl(ca_u.clone())
968 };
969 let cvt_b = if c2.to_i64() == Some(1) {
970 as_scaled_mul(&c2, &b)
971 } else {
972 refl(cb_u.clone())
973 };
974 let step_cvt = cong2("mul", ca, &ca_u, cb, &cb_u, cvt_a, cvt_b); let step_swap = swap_middle(&lc1, &a, &lc2, &b); let ab = ax2("mul", a.clone(), b.clone());
977 let coeff_redex = ax2("mul", lc1.clone(), lc2.clone());
978 let step_fold = cong2(
980 "mul",
981 &coeff_redex,
982 &lcoeff,
983 &ab,
984 &merged,
985 refl(lcoeff.clone()),
986 p_atoms,
987 ); let prod = ax2("mul", ca.clone(), cb.clone());
989 let mid1 = ax2("mul", ca_u, cb_u);
990 let mid2 = ax2("mul", coeff_redex, ab);
991 let scaled_lit = ax2("mul", lcoeff, merged.clone());
992 let up_to_lit = eq_trans(
993 prod.clone(),
994 mid1.clone(),
995 scaled_lit.clone(),
996 step_cvt,
997 eq_trans(mid1, mid2, scaled_lit.clone(), step_swap, step_fold),
998 ); if coeff.to_i64() == Some(1) {
1000 let elim = eq_sym(
1002 merged.clone(),
1003 scaled_lit.clone(),
1004 as_scaled_mul(&coeff, &merged),
1005 );
1006 Some((
1007 merged.clone(),
1008 eq_trans(prod, scaled_lit, merged, up_to_lit, elim),
1009 ))
1010 } else {
1011 Some((scaled_lit, up_to_lit))
1012 }
1013}
1014
1015fn is_lit(t: &Term, v: i64) -> bool {
1017 matches!(t, Term::Lit(logicaffeine_kernel::Literal::Int(n)) if *n == v)
1018}
1019
1020fn dist_mul(ctx: &Context, polys: &mut Polynomials, ca: &Term, cb: &Term) -> Option<(Poly, Term)> {
1023 if is_lit(cb, 0) {
1028 return Some((vec![], ax1("mul_zero", ca.clone()))); }
1030 if is_lit(ca, 0) {
1031 let prod = ax2("mul", ca.clone(), cb.clone());
1032 let flip = ax2("mul_comm", ca.clone(), cb.clone()); let zero = ax1("mul_zero", cb.clone()); return Some((
1035 vec![],
1036 eq_trans(
1037 prod,
1038 ax2("mul", cb.clone(), ca.clone()),
1039 lit_t(0),
1040 flip,
1041 zero,
1042 ),
1043 ));
1044 }
1045 if is_lit(cb, 1) {
1046 let pca = to_poly(polys, ctx, ca); return Some((pca, ax1("mul_one", ca.clone()))); }
1049 if is_lit(ca, 1) {
1050 let pcb = to_poly(polys, ctx, cb);
1051 let prod = ax2("mul", ca.clone(), cb.clone());
1052 let flip = ax2("mul_comm", ca.clone(), cb.clone()); let one = ax1("mul_one", cb.clone()); return Some((
1055 pcb,
1056 eq_trans(
1057 prod,
1058 ax2("mul", cb.clone(), ca.clone()),
1059 cb.clone(),
1060 flip,
1061 one,
1062 ),
1063 ));
1064 }
1065 if let Some((cb1, cb2)) = match_bin(cb, "add") {
1066 let distrib = ax3("mul_distrib_add", ca.clone(), cb1.clone(), cb2.clone());
1068 let (pp1, d1) = dist_mul(ctx, polys, ca, &cb1)?;
1069 let (pp2, d2) = dist_mul(ctx, polys, ca, &cb2)?;
1070 let rp1 = reify(&pp1, &polys.atoms);
1071 let rp2 = reify(&pp2, &polys.atoms);
1072 let cong = cong2(
1073 "add",
1074 &ax2("mul", ca.clone(), cb1.clone()),
1075 &rp1,
1076 &ax2("mul", ca.clone(), cb2.clone()),
1077 &rp2,
1078 d1,
1079 d2,
1080 );
1081 let (pm, mproof) = merge_canonical(&polys.atoms, &pp1, &pp2)?;
1082 let rpm = reify(&pm, &polys.atoms);
1083 let proof = eq_trans(
1084 ax2("mul", ca.clone(), cb.clone()),
1085 ax2(
1086 "add",
1087 ax2("mul", ca.clone(), cb1.clone()),
1088 ax2("mul", ca.clone(), cb2.clone()),
1089 ),
1090 rpm,
1091 distrib,
1092 eq_trans(
1093 ax2(
1094 "add",
1095 ax2("mul", ca.clone(), cb1),
1096 ax2("mul", ca.clone(), cb2),
1097 ),
1098 ax2("add", rp1, rp2),
1099 reify(&pm, &polys.atoms),
1100 cong,
1101 mproof,
1102 ),
1103 );
1104 return Some((pm, proof));
1105 }
1106 if let Some((_ca1, _ca2)) = match_bin(ca, "add") {
1107 let comm = ax2("mul_comm", ca.clone(), cb.clone());
1109 let (pm, inner) = dist_mul(ctx, polys, cb, ca)?; let rpm = reify(&pm, &polys.atoms);
1111 return Some((
1112 pm,
1113 eq_trans(
1114 ax2("mul", ca.clone(), cb.clone()),
1115 ax2("mul", cb.clone(), ca.clone()),
1116 rpm,
1117 comm,
1118 inner,
1119 ),
1120 ));
1121 }
1122 let prod = ax2("mul", ca.clone(), cb.clone());
1127 let pp = to_poly(polys, ctx, &prod);
1128 let c = reify(&pp, &polys.atoms);
1129 let proof = merge_sorted(polys, ca, cb)
1134 .filter(|(result, _)| *result == c)
1135 .or_else(|| merge_scaled(polys, ca, cb).filter(|(result, _)| *result == c))
1136 .map(|(_, pf)| pf)
1137 .or_else(|| prove_eq(ctx, &prod, &c, MONO_FALLBACK_DEPTH))?;
1138 Some((pp, proof))
1139}
1140
1141fn norm(ctx: &Context, polys: &mut Polynomials, t: &Term) -> Option<(Term, Term)> {
1143 if let Some((a, b)) = match_bin(t, "add") {
1144 let (ca, pa) = norm(ctx, polys, &a)?;
1145 let (cb, pb) = norm(ctx, polys, &b)?;
1146 let pa_poly = to_poly(polys, ctx, &a);
1147 let pb_poly = to_poly(polys, ctx, &b);
1148 let cong = cong2("add", &a, &ca, &b, &cb, pa, pb); let (merged, merge) = merge_canonical(&polys.atoms, &pa_poly, &pb_poly)?;
1150 let c = reify(&merged, &polys.atoms);
1151 return Some((
1152 c.clone(),
1153 eq_trans(t.clone(), ax2("add", ca, cb), c, cong, merge),
1154 ));
1155 }
1156 if let Some((a, b)) = match_bin(t, "mul") {
1157 let (ca, pa) = norm(ctx, polys, &a)?;
1158 let (cb, pb) = norm(ctx, polys, &b)?;
1159 let cong = cong2("mul", &a, &ca, &b, &cb, pa, pb); let (pm, dproof) = dist_mul(ctx, polys, &ca, &cb)?;
1161 let c = reify(&pm, &polys.atoms);
1162 return Some((
1163 c.clone(),
1164 eq_trans(t.clone(), ax2("mul", ca, cb), c, cong, dproof),
1165 ));
1166 }
1167 if let Some((a, b)) = match_bin(t, "sub") {
1168 let elimmed = ax2("add", a.clone(), ax2("mul", lit_t(-1), b.clone()));
1172 let elim = ax2("sub_elim", a, b);
1173 let (c, p) = norm(ctx, polys, &elimmed)?;
1174 return Some((c.clone(), eq_trans(t.clone(), elimmed, c, elim, p)));
1175 }
1176 let c = reify(&to_poly(polys, ctx, t), &polys.atoms);
1179 let proof = prove_eq(ctx, t, &c, MAX_REWRITE_DEPTH)?;
1180 Some((c, proof))
1181}
1182
1183fn prove_by_normalization(ctx: &Context, lhs: &Term, rhs: &Term) -> Option<Term> {
1185 let mut polys = Polynomials { atoms: Vec::new() };
1186 let (cl, pl) = norm(ctx, &mut polys, lhs)?; let (cr, pr) = norm(ctx, &mut polys, rhs)?; if cl != cr {
1190 return None;
1191 }
1192 Some(eq_trans(
1194 lhs.clone(),
1195 cl,
1196 rhs.clone(),
1197 pl,
1198 eq_sym(rhs.clone(), cr, pr),
1199 ))
1200}
1201
1202const MAX_REWRITE_DEPTH: u32 = 6;
1206
1207const MONO_FALLBACK_DEPTH: u32 = 6;
1212
1213fn prove_eq(ctx: &Context, lhs: &Term, rhs: &Term, depth: u32) -> Option<Term> {
1214 let nlhs = normalize(ctx, lhs);
1217 let nrhs = normalize(ctx, rhs);
1218 if nlhs == nrhs {
1219 return Some(refl(nlhs));
1220 }
1221
1222 if let Some(p) = match_axiom(ctx, lhs, rhs) {
1224 return Some(p);
1225 }
1226 if let Some(p) = match_axiom(ctx, rhs, lhs) {
1227 return Some(eq_sym(rhs.clone(), lhs.clone(), p));
1229 }
1230
1231 for op in ["add", "mul", "sub"] {
1234 if let (Some((la, lb)), Some((ra, rb))) = (match_bin(lhs, op), match_bin(rhs, op)) {
1235 if let (Some(pa), Some(pb)) = (
1236 prove_eq(ctx, &la, &ra, depth),
1237 prove_eq(ctx, &lb, &rb, depth),
1238 ) {
1239 return Some(cong2(op, &la, &ra, &lb, &rb, pa, pb));
1240 }
1241 }
1242 }
1243
1244 if depth > 0 {
1248 for (mid, p_lhs_mid) in forward_rewrites(lhs) {
1249 if let Some(p_mid_rhs) = prove_eq(ctx, &mid, rhs, depth - 1) {
1250 return Some(eq_trans(
1251 lhs.clone(),
1252 mid,
1253 rhs.clone(),
1254 p_lhs_mid,
1255 p_mid_rhs,
1256 ));
1257 }
1258 }
1259 }
1260
1261 None
1262}
1263
1264fn eq_trans(x: Term, y: Term, z: Term, p1: Term, p2: Term) -> Term {
1266 app(
1267 app(app(app(app(app(global("Eq_trans"), int()), x), y), z), p1),
1268 p2,
1269 )
1270}
1271
1272fn forward_rewrites(l: &Term) -> Vec<(Term, Term)> {
1275 let g = global;
1276 let mut out = Vec::new();
1277 if let Some((a, b)) = match_bin(l, "add") {
1279 out.push((
1280 app2(g("add"), b.clone(), a.clone()),
1281 app2(g("add_comm"), a.clone(), b.clone()),
1282 ));
1283 if let Some((a2, b2)) = match_bin(&a, "add") {
1285 let c = b.clone();
1286 out.push((
1287 app2(g("add"), a2.clone(), app2(g("add"), b2.clone(), c.clone())),
1288 app3(g("add_assoc"), a2.clone(), b2.clone(), c.clone()),
1289 ));
1290 }
1291 if let Some((b2, c2)) = match_bin(&b, "add") {
1293 let lhs_a = app2(g("add"), app2(g("add"), a.clone(), b2.clone()), c2.clone());
1294 let rhs_a = app2(g("add"), a.clone(), app2(g("add"), b2.clone(), c2.clone()));
1295 out.push((
1296 lhs_a.clone(),
1297 eq_sym(
1298 lhs_a,
1299 rhs_a,
1300 app3(g("add_assoc"), a.clone(), b2.clone(), c2.clone()),
1301 ),
1302 ));
1303 }
1304 }
1305 if let Some((a, b)) = match_bin(l, "mul") {
1307 out.push((
1308 app2(g("mul"), b.clone(), a.clone()),
1309 app2(g("mul_comm"), a.clone(), b.clone()),
1310 ));
1311 if let Some((a2, b2)) = match_bin(&a, "mul") {
1313 let c = b.clone();
1314 out.push((
1315 app2(g("mul"), a2.clone(), app2(g("mul"), b2.clone(), c.clone())),
1316 app3(g("mul_assoc"), a2.clone(), b2.clone(), c.clone()),
1317 ));
1318 }
1319 if let Some((b2, c2)) = match_bin(&b, "add") {
1321 out.push((
1322 app2(
1323 g("add"),
1324 app2(g("mul"), a.clone(), b2.clone()),
1325 app2(g("mul"), a.clone(), c2.clone()),
1326 ),
1327 app3(g("mul_distrib_add"), a.clone(), b2.clone(), c2.clone()),
1328 ));
1329 }
1330 }
1331 out
1332}
1333
1334fn eq_int_term(l: Term, r: Term) -> Term {
1336 app(app(app(global("Eq"), int()), l), r)
1337}
1338
1339fn eq_rec(x: Term, motive: Term, base: Term, y: Term, eqp: Term) -> Term {
1341 app(
1342 app(
1343 app(app(app(app(global("Eq_rec"), int()), x), motive), base),
1344 y,
1345 ),
1346 eqp,
1347 )
1348}
1349
1350fn lam_int(body: Term) -> Term {
1352 Term::Lambda {
1353 param: "__w".to_string(),
1354 param_type: Box::new(int()),
1355 body: Box::new(body),
1356 }
1357}
1358
1359fn cong2(op: &str, a: &Term, a2: &Term, b: &Term, b2: &Term, pa: Term, pb: Term) -> Term {
1362 let opab = app2(global(op), a.clone(), b.clone());
1363 let w = Term::Var("__w".to_string());
1364
1365 let p1 = lam_int(eq_int_term(
1368 opab.clone(),
1369 app2(global(op), w.clone(), b.clone()),
1370 ));
1371 let step1 = eq_rec(a.clone(), p1, refl(opab.clone()), a2.clone(), pa);
1372
1373 let p2 = lam_int(eq_int_term(opab.clone(), app2(global(op), a2.clone(), w)));
1376 eq_rec(b.clone(), p2, step1, b2.clone(), pb)
1377}
1378
1379fn match_axiom(ctx: &Context, l: &Term, r: &Term) -> Option<Term> {
1381 if let (Some((la, lb)), Some((ra, rb))) = (match_bin(l, "add"), match_bin(r, "add")) {
1383 if conv(ctx, &la, &rb) && conv(ctx, &lb, &ra) {
1384 return Some(app2(global("add_comm"), la, lb));
1385 }
1386 }
1387 if let (Some((la, lb)), Some((ra, rb))) = (match_bin(l, "mul"), match_bin(r, "mul")) {
1389 if conv(ctx, &la, &rb) && conv(ctx, &lb, &ra) {
1390 return Some(app2(global("mul_comm"), la, lb));
1391 }
1392 }
1393 if let Some((lab, lc)) = match_bin(l, "add") {
1395 if let Some((la, lb)) = match_bin(&lab, "add") {
1396 if let Some((ra, rbc)) = match_bin(r, "add") {
1397 if let Some((rb, rc)) = match_bin(&rbc, "add") {
1398 if conv(ctx, &la, &ra) && conv(ctx, &lb, &rb) && conv(ctx, &lc, &rc) {
1399 return Some(app3(global("add_assoc"), la, lb, lc));
1400 }
1401 }
1402 }
1403 }
1404 }
1405 if let Some((lab, lc)) = match_bin(l, "mul") {
1407 if let Some((la, lb)) = match_bin(&lab, "mul") {
1408 if let Some((ra, rbc)) = match_bin(r, "mul") {
1409 if let Some((rb, rc)) = match_bin(&rbc, "mul") {
1410 if conv(ctx, &la, &ra) && conv(ctx, &lb, &rb) && conv(ctx, &lc, &rc) {
1411 return Some(app3(global("mul_assoc"), la, lb, lc));
1412 }
1413 }
1414 }
1415 }
1416 }
1417 if let Some((la, lb)) = match_bin(l, "add") {
1419 if conv(ctx, &lb, &Term::Lit(logicaffeine_kernel::Literal::Int(0))) && conv(ctx, &la, r) {
1420 return Some(app(global("add_zero"), la));
1421 }
1422 }
1423 if let Some((la, lb)) = match_bin(l, "mul") {
1425 if conv(ctx, &lb, &Term::Lit(logicaffeine_kernel::Literal::Int(1))) && conv(ctx, &la, r) {
1426 return Some(app(global("mul_one"), la));
1427 }
1428 }
1429 if let Some((a, bc)) = match_bin(l, "mul") {
1431 if let Some((b, c)) = match_bin(&bc, "add") {
1432 if let Some((rab, rac)) = match_bin(r, "add") {
1433 if let (Some((ra1, rb1)), Some((ra2, rc1))) =
1434 (match_bin(&rab, "mul"), match_bin(&rac, "mul"))
1435 {
1436 if conv(ctx, &a, &ra1)
1437 && conv(ctx, &a, &ra2)
1438 && conv(ctx, &b, &rb1)
1439 && conv(ctx, &c, &rc1)
1440 {
1441 return Some(app3(global("mul_distrib_add"), a, b, c));
1442 }
1443 }
1444 }
1445 }
1446 }
1447 None
1448}
1449
1450#[cfg(test)]
1451#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/arith/tests.rs"]
1452mod tests;