1use std::collections::HashMap;
34use std::sync::atomic::{AtomicUsize, Ordering};
35
36use crate::error::{ProofError, ProofResult};
37use crate::{MatchArm, ProofExpr, ProofTerm};
38
39pub type Substitution = HashMap<String, ProofTerm>;
58
59pub type ExprSubstitution = HashMap<String, ProofExpr>;
76
77static ALPHA_COUNTER: AtomicUsize = AtomicUsize::new(0);
83
84fn fresh_alpha_constant() -> ProofTerm {
87 let id = ALPHA_COUNTER.fetch_add(1, Ordering::SeqCst);
88 ProofTerm::Constant(format!("#α{}", id))
89}
90
91fn is_constructor_form(expr: &ProofExpr) -> bool {
98 matches!(expr, ProofExpr::Ctor { .. })
99}
100
101pub fn beta_reduce(expr: &ProofExpr) -> ProofExpr {
139 match expr {
140 ProofExpr::App(func, arg) => {
142 let func_reduced = beta_reduce(func);
144 let arg_reduced = beta_reduce(arg);
145
146 match func_reduced {
147 ProofExpr::Lambda { variable, body } => {
149 let result = substitute_expr_for_var(&body, &variable, &arg_reduced);
150 beta_reduce(&result)
152 }
153
154 ProofExpr::Fixpoint { ref name, ref body } if is_constructor_form(&arg_reduced) => {
157 let fix_expr = ProofExpr::Fixpoint {
159 name: name.clone(),
160 body: body.clone(),
161 };
162 let unfolded = substitute_expr_for_var(body, name, &fix_expr);
163 let applied = ProofExpr::App(Box::new(unfolded), Box::new(arg_reduced));
165 beta_reduce(&applied)
166 }
167
168 _ => {
169 ProofExpr::App(Box::new(func_reduced), Box::new(arg_reduced))
171 }
172 }
173 }
174
175 ProofExpr::And(l, r) => ProofExpr::And(Box::new(beta_reduce(l)), Box::new(beta_reduce(r))),
177 ProofExpr::Or(l, r) => ProofExpr::Or(Box::new(beta_reduce(l)), Box::new(beta_reduce(r))),
178 ProofExpr::Implies(l, r) => {
179 ProofExpr::Implies(Box::new(beta_reduce(l)), Box::new(beta_reduce(r)))
180 }
181 ProofExpr::Iff(l, r) => ProofExpr::Iff(Box::new(beta_reduce(l)), Box::new(beta_reduce(r))),
182 ProofExpr::Not(inner) => ProofExpr::Not(Box::new(beta_reduce(inner))),
183
184 ProofExpr::ForAll { variable, body } => ProofExpr::ForAll {
186 variable: variable.clone(),
187 body: Box::new(beta_reduce(body)),
188 },
189 ProofExpr::Exists { variable, body } => ProofExpr::Exists {
190 variable: variable.clone(),
191 body: Box::new(beta_reduce(body)),
192 },
193
194 ProofExpr::Lambda { variable, body } => ProofExpr::Lambda {
196 variable: variable.clone(),
197 body: Box::new(beta_reduce(body)),
198 },
199
200 ProofExpr::Modal {
202 domain,
203 force,
204 flavor,
205 body,
206 } => ProofExpr::Modal {
207 domain: domain.clone(),
208 force: *force,
209 flavor: flavor.clone(),
210 body: Box::new(beta_reduce(body)),
211 },
212 ProofExpr::Counterfactual {
213 antecedent,
214 consequent,
215 } => ProofExpr::Counterfactual {
216 antecedent: Box::new(beta_reduce(antecedent)),
217 consequent: Box::new(beta_reduce(consequent)),
218 },
219 ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
220 operator: operator.clone(),
221 body: Box::new(beta_reduce(body)),
222 },
223 ProofExpr::TemporalBinary {
224 operator,
225 left,
226 right,
227 } => ProofExpr::TemporalBinary {
228 operator: operator.clone(),
229 left: Box::new(beta_reduce(left)),
230 right: Box::new(beta_reduce(right)),
231 },
232
233 ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
235 name: name.clone(),
236 args: args.iter().map(beta_reduce).collect(),
237 },
238
239 ProofExpr::Match { scrutinee, arms } => {
241 let reduced_scrutinee = beta_reduce(scrutinee);
242
243 if let ProofExpr::Ctor {
245 name: ctor_name,
246 args: ctor_args,
247 } = &reduced_scrutinee
248 {
249 for arm in arms {
250 if &arm.ctor == ctor_name {
251 let mut result = arm.body.clone();
253 for (binding, arg) in arm.bindings.iter().zip(ctor_args.iter()) {
254 result = substitute_expr_for_var(&result, binding, arg);
255 }
256 return beta_reduce(&result);
258 }
259 }
260 }
261
262 ProofExpr::Match {
264 scrutinee: Box::new(reduced_scrutinee),
265 arms: arms
266 .iter()
267 .map(|arm| MatchArm {
268 ctor: arm.ctor.clone(),
269 bindings: arm.bindings.clone(),
270 body: beta_reduce(&arm.body),
271 })
272 .collect(),
273 }
274 }
275
276 ProofExpr::Fixpoint { name, body } => ProofExpr::Fixpoint {
278 name: name.clone(),
279 body: Box::new(beta_reduce(body)),
280 },
281
282 ProofExpr::Predicate { .. }
284 | ProofExpr::Identity(_, _)
285 | ProofExpr::Atom(_)
286 | ProofExpr::NeoEvent { .. }
287 | ProofExpr::TypedVar { .. }
288 | ProofExpr::Unsupported(_)
289 | ProofExpr::Hole(_)
290 | ProofExpr::Term(_) => expr.clone(),
291 }
292}
293
294fn free_vars_expr(
300 expr: &ProofExpr,
301 bound: &mut Vec<String>,
302 acc: &mut std::collections::HashSet<String>,
303) {
304 match expr {
305 ProofExpr::Atom(s) => {
306 if !bound.iter().any(|b| b == s) {
307 acc.insert(s.clone());
308 }
309 }
310 ProofExpr::Predicate { args, .. } => {
311 for a in args {
312 free_vars_term(a, bound, acc);
313 }
314 }
315 ProofExpr::Identity(l, r) => {
316 free_vars_term(l, bound, acc);
317 free_vars_term(r, bound, acc);
318 }
319 ProofExpr::And(l, r)
320 | ProofExpr::Or(l, r)
321 | ProofExpr::Implies(l, r)
322 | ProofExpr::Iff(l, r) => {
323 free_vars_expr(l, bound, acc);
324 free_vars_expr(r, bound, acc);
325 }
326 ProofExpr::Not(i) => free_vars_expr(i, bound, acc),
327 ProofExpr::ForAll { variable, body }
328 | ProofExpr::Exists { variable, body }
329 | ProofExpr::Lambda { variable, body } => {
330 bound.push(variable.clone());
331 free_vars_expr(body, bound, acc);
332 bound.pop();
333 }
334 ProofExpr::Modal { body, .. } => free_vars_expr(body, bound, acc),
335 ProofExpr::Counterfactual {
336 antecedent,
337 consequent,
338 } => {
339 free_vars_expr(antecedent, bound, acc);
340 free_vars_expr(consequent, bound, acc);
341 }
342 ProofExpr::Temporal { body, .. } => free_vars_expr(body, bound, acc),
343 ProofExpr::TemporalBinary { left, right, .. } => {
344 free_vars_expr(left, bound, acc);
345 free_vars_expr(right, bound, acc);
346 }
347 ProofExpr::App(f, a) => {
348 free_vars_expr(f, bound, acc);
349 free_vars_expr(a, bound, acc);
350 }
351 ProofExpr::NeoEvent {
352 event_var, roles, ..
353 } => {
354 bound.push(event_var.clone());
355 for (_, t) in roles {
356 free_vars_term(t, bound, acc);
357 }
358 bound.pop();
359 }
360 ProofExpr::Ctor { args, .. } => {
361 for a in args {
362 free_vars_expr(a, bound, acc);
363 }
364 }
365 ProofExpr::Match { scrutinee, arms } => {
366 free_vars_expr(scrutinee, bound, acc);
367 for arm in arms {
368 let depth = arm.bindings.len();
369 for b in &arm.bindings {
370 bound.push(b.clone());
371 }
372 free_vars_expr(&arm.body, bound, acc);
373 for _ in 0..depth {
374 bound.pop();
375 }
376 }
377 }
378 ProofExpr::Fixpoint { name, body } => {
379 bound.push(name.clone());
380 free_vars_expr(body, bound, acc);
381 bound.pop();
382 }
383 ProofExpr::TypedVar { name, .. } => {
384 if !bound.iter().any(|b| b == name) {
385 acc.insert(name.clone());
386 }
387 }
388 ProofExpr::Hole(_) | ProofExpr::Unsupported(_) => {}
389 ProofExpr::Term(t) => free_vars_term(t, bound, acc),
390 }
391}
392
393pub(crate) fn occurs_free(var: &str, expr: &ProofExpr) -> bool {
395 let mut free = std::collections::HashSet::new();
396 free_vars_expr(expr, &mut Vec::new(), &mut free);
397 free.contains(var)
398}
399
400fn free_vars_term(term: &ProofTerm, bound: &[String], acc: &mut std::collections::HashSet<String>) {
401 match term {
402 ProofTerm::Variable(s) | ProofTerm::BoundVarRef(s) => {
403 if !bound.iter().any(|b| b == s) {
404 acc.insert(s.clone());
405 }
406 }
407 ProofTerm::Constant(_) => {}
408 ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
409 for a in args {
410 free_vars_term(a, bound, acc);
411 }
412 }
413 }
414}
415
416fn all_names_expr(expr: &ProofExpr, acc: &mut std::collections::HashSet<String>) {
419 match expr {
420 ProofExpr::Atom(s) => {
421 acc.insert(s.clone());
422 }
423 ProofExpr::Predicate { args, .. } => {
424 for a in args {
425 all_names_term(a, acc);
426 }
427 }
428 ProofExpr::Identity(l, r) => {
429 all_names_term(l, acc);
430 all_names_term(r, acc);
431 }
432 ProofExpr::And(l, r)
433 | ProofExpr::Or(l, r)
434 | ProofExpr::Implies(l, r)
435 | ProofExpr::Iff(l, r) => {
436 all_names_expr(l, acc);
437 all_names_expr(r, acc);
438 }
439 ProofExpr::Not(i) => all_names_expr(i, acc),
440 ProofExpr::ForAll { variable, body }
441 | ProofExpr::Exists { variable, body }
442 | ProofExpr::Lambda { variable, body } => {
443 acc.insert(variable.clone());
444 all_names_expr(body, acc);
445 }
446 ProofExpr::Modal { body, .. } => all_names_expr(body, acc),
447 ProofExpr::Counterfactual {
448 antecedent,
449 consequent,
450 } => {
451 all_names_expr(antecedent, acc);
452 all_names_expr(consequent, acc);
453 }
454 ProofExpr::Temporal { body, .. } => all_names_expr(body, acc),
455 ProofExpr::TemporalBinary { left, right, .. } => {
456 all_names_expr(left, acc);
457 all_names_expr(right, acc);
458 }
459 ProofExpr::App(f, a) => {
460 all_names_expr(f, acc);
461 all_names_expr(a, acc);
462 }
463 ProofExpr::NeoEvent {
464 event_var, roles, ..
465 } => {
466 acc.insert(event_var.clone());
467 for (_, t) in roles {
468 all_names_term(t, acc);
469 }
470 }
471 ProofExpr::Ctor { args, .. } => {
472 for a in args {
473 all_names_expr(a, acc);
474 }
475 }
476 ProofExpr::Match { scrutinee, arms } => {
477 all_names_expr(scrutinee, acc);
478 for arm in arms {
479 for b in &arm.bindings {
480 acc.insert(b.clone());
481 }
482 all_names_expr(&arm.body, acc);
483 }
484 }
485 ProofExpr::Fixpoint { name, body } => {
486 acc.insert(name.clone());
487 all_names_expr(body, acc);
488 }
489 ProofExpr::TypedVar { name, .. } => {
490 acc.insert(name.clone());
491 }
492 ProofExpr::Hole(_) | ProofExpr::Unsupported(_) => {}
493 ProofExpr::Term(t) => all_names_term(t, acc),
494 }
495}
496
497fn all_names_term(term: &ProofTerm, acc: &mut std::collections::HashSet<String>) {
498 match term {
499 ProofTerm::Constant(s) | ProofTerm::Variable(s) | ProofTerm::BoundVarRef(s) => {
500 acc.insert(s.clone());
501 }
502 ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
503 for a in args {
504 all_names_term(a, acc);
505 }
506 }
507 }
508}
509
510fn fresh_proof_name(base: &str, avoid: &std::collections::HashSet<String>) -> String {
512 let mut candidate = format!("{}'", base);
513 let mut n: u32 = 0;
514 while avoid.contains(&candidate) {
515 n += 1;
516 candidate = format!("{}'{}", base, n);
517 }
518 candidate
519}
520
521fn alpha_rename_expr(expr: &ProofExpr, from: &str, to: &str) -> ProofExpr {
526 match expr {
527 ProofExpr::Atom(s) if s == from => ProofExpr::Atom(to.to_string()),
528 ProofExpr::Atom(s) => ProofExpr::Atom(s.clone()),
529 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
530 name: name.clone(),
531 args: args
532 .iter()
533 .map(|a| alpha_rename_term(a, from, to))
534 .collect(),
535 world: world.clone(),
536 },
537 ProofExpr::Identity(l, r) => ProofExpr::Identity(
538 alpha_rename_term(l, from, to),
539 alpha_rename_term(r, from, to),
540 ),
541 ProofExpr::And(l, r) => ProofExpr::And(
542 Box::new(alpha_rename_expr(l, from, to)),
543 Box::new(alpha_rename_expr(r, from, to)),
544 ),
545 ProofExpr::Or(l, r) => ProofExpr::Or(
546 Box::new(alpha_rename_expr(l, from, to)),
547 Box::new(alpha_rename_expr(r, from, to)),
548 ),
549 ProofExpr::Implies(l, r) => ProofExpr::Implies(
550 Box::new(alpha_rename_expr(l, from, to)),
551 Box::new(alpha_rename_expr(r, from, to)),
552 ),
553 ProofExpr::Iff(l, r) => ProofExpr::Iff(
554 Box::new(alpha_rename_expr(l, from, to)),
555 Box::new(alpha_rename_expr(r, from, to)),
556 ),
557 ProofExpr::Not(i) => ProofExpr::Not(Box::new(alpha_rename_expr(i, from, to))),
558 ProofExpr::ForAll { variable, body } => {
559 if variable == from {
560 expr.clone()
561 } else {
562 ProofExpr::ForAll {
563 variable: variable.clone(),
564 body: Box::new(alpha_rename_expr(body, from, to)),
565 }
566 }
567 }
568 ProofExpr::Exists { variable, body } => {
569 if variable == from {
570 expr.clone()
571 } else {
572 ProofExpr::Exists {
573 variable: variable.clone(),
574 body: Box::new(alpha_rename_expr(body, from, to)),
575 }
576 }
577 }
578 ProofExpr::Lambda { variable, body } => {
579 if variable == from {
580 expr.clone()
581 } else {
582 ProofExpr::Lambda {
583 variable: variable.clone(),
584 body: Box::new(alpha_rename_expr(body, from, to)),
585 }
586 }
587 }
588 ProofExpr::Modal {
589 domain,
590 force,
591 flavor,
592 body,
593 } => ProofExpr::Modal {
594 domain: domain.clone(),
595 force: *force,
596 flavor: flavor.clone(),
597 body: Box::new(alpha_rename_expr(body, from, to)),
598 },
599 ProofExpr::Counterfactual {
600 antecedent,
601 consequent,
602 } => ProofExpr::Counterfactual {
603 antecedent: Box::new(alpha_rename_expr(antecedent, from, to)),
604 consequent: Box::new(alpha_rename_expr(consequent, from, to)),
605 },
606 ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
607 operator: operator.clone(),
608 body: Box::new(alpha_rename_expr(body, from, to)),
609 },
610 ProofExpr::TemporalBinary {
611 operator,
612 left,
613 right,
614 } => ProofExpr::TemporalBinary {
615 operator: operator.clone(),
616 left: Box::new(alpha_rename_expr(left, from, to)),
617 right: Box::new(alpha_rename_expr(right, from, to)),
618 },
619 ProofExpr::App(f, a) => ProofExpr::App(
620 Box::new(alpha_rename_expr(f, from, to)),
621 Box::new(alpha_rename_expr(a, from, to)),
622 ),
623 ProofExpr::NeoEvent {
624 event_var,
625 verb,
626 roles,
627 } => {
628 if event_var == from {
629 expr.clone()
630 } else {
631 ProofExpr::NeoEvent {
632 event_var: event_var.clone(),
633 verb: verb.clone(),
634 roles: roles
635 .iter()
636 .map(|(r, t)| (r.clone(), alpha_rename_term(t, from, to)))
637 .collect(),
638 }
639 }
640 }
641 ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
642 name: name.clone(),
643 args: args
644 .iter()
645 .map(|a| alpha_rename_expr(a, from, to))
646 .collect(),
647 },
648 ProofExpr::Match { scrutinee, arms } => ProofExpr::Match {
649 scrutinee: Box::new(alpha_rename_expr(scrutinee, from, to)),
650 arms: arms
651 .iter()
652 .map(|arm| {
653 if arm.bindings.iter().any(|b| b == from) {
654 arm.clone()
655 } else {
656 MatchArm {
657 ctor: arm.ctor.clone(),
658 bindings: arm.bindings.clone(),
659 body: alpha_rename_expr(&arm.body, from, to),
660 }
661 }
662 })
663 .collect(),
664 },
665 ProofExpr::Fixpoint { name, body } => {
666 if name == from {
667 expr.clone()
668 } else {
669 ProofExpr::Fixpoint {
670 name: name.clone(),
671 body: Box::new(alpha_rename_expr(body, from, to)),
672 }
673 }
674 }
675 ProofExpr::TypedVar { name, typename } => {
676 if name == from {
677 ProofExpr::TypedVar {
678 name: to.to_string(),
679 typename: typename.clone(),
680 }
681 } else {
682 expr.clone()
683 }
684 }
685 ProofExpr::Hole(_) | ProofExpr::Unsupported(_) => expr.clone(),
686 ProofExpr::Term(t) => ProofExpr::Term(alpha_rename_term(t, from, to)),
687 }
688}
689
690fn alpha_rename_term(term: &ProofTerm, from: &str, to: &str) -> ProofTerm {
691 match term {
692 ProofTerm::Variable(s) if s == from => ProofTerm::Variable(to.to_string()),
693 ProofTerm::BoundVarRef(s) if s == from => ProofTerm::BoundVarRef(to.to_string()),
694 ProofTerm::Variable(s) => ProofTerm::Variable(s.clone()),
695 ProofTerm::BoundVarRef(s) => ProofTerm::BoundVarRef(s.clone()),
696 ProofTerm::Constant(s) => ProofTerm::Constant(s.clone()),
697 ProofTerm::Function(n, args) => ProofTerm::Function(
698 n.clone(),
699 args.iter()
700 .map(|a| alpha_rename_term(a, from, to))
701 .collect(),
702 ),
703 ProofTerm::Group(args) => ProofTerm::Group(
704 args.iter()
705 .map(|a| alpha_rename_term(a, from, to))
706 .collect(),
707 ),
708 }
709}
710
711fn rebind_for_subst(
715 variable: &str,
716 inner: &ProofExpr,
717 repl_fvs: &std::collections::HashSet<String>,
718) -> (String, ProofExpr) {
719 if repl_fvs.contains(variable) {
720 let mut avoid = repl_fvs.clone();
721 all_names_expr(inner, &mut avoid);
722 let fresh = fresh_proof_name(variable, &avoid);
723 let renamed = alpha_rename_expr(inner, variable, &fresh);
724 (fresh, renamed)
725 } else {
726 (variable.to_string(), inner.clone())
727 }
728}
729
730fn substitute_expr_for_var(body: &ProofExpr, var: &str, replacement: &ProofExpr) -> ProofExpr {
738 let mut repl_fvs = std::collections::HashSet::new();
739 free_vars_expr(replacement, &mut Vec::new(), &mut repl_fvs);
740 subst_expr_avoiding(
741 body,
742 var,
743 replacement,
744 &repl_fvs,
745 Occurrences::TermsAndAtoms,
746 )
747}
748
749pub fn instantiate_expr(body: &ProofExpr, var: &str, t: &ProofTerm) -> ProofExpr {
756 let mut repl_fvs = std::collections::HashSet::new();
757 free_vars_term(t, &[], &mut repl_fvs);
758 subst_expr_avoiding(
759 body,
760 var,
761 &ProofExpr::Term(t.clone()),
762 &repl_fvs,
763 Occurrences::Terms,
764 )
765}
766
767#[derive(Clone, Copy, PartialEq, Eq)]
769enum Occurrences {
770 Terms,
772 TermsAndAtoms,
775}
776
777fn subst_expr_avoiding(
778 body: &ProofExpr,
779 var: &str,
780 replacement: &ProofExpr,
781 repl_fvs: &std::collections::HashSet<String>,
782 at: Occurrences,
783) -> ProofExpr {
784 match body {
785 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
786 name: name.clone(),
787 args: args
788 .iter()
789 .map(|t| substitute_term_for_var(t, var, replacement))
790 .collect(),
791 world: world.clone(),
792 },
793
794 ProofExpr::Identity(l, r) => ProofExpr::Identity(
795 substitute_term_for_var(l, var, replacement),
796 substitute_term_for_var(r, var, replacement),
797 ),
798
799 ProofExpr::Atom(a) => {
800 if a == var && at == Occurrences::TermsAndAtoms {
802 replacement.clone()
803 } else {
804 ProofExpr::Atom(a.clone())
805 }
806 }
807
808 ProofExpr::And(l, r) => ProofExpr::And(
809 Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
810 Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
811 ),
812 ProofExpr::Or(l, r) => ProofExpr::Or(
813 Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
814 Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
815 ),
816 ProofExpr::Implies(l, r) => ProofExpr::Implies(
817 Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
818 Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
819 ),
820 ProofExpr::Iff(l, r) => ProofExpr::Iff(
821 Box::new(subst_expr_avoiding(l, var, replacement, repl_fvs, at)),
822 Box::new(subst_expr_avoiding(r, var, replacement, repl_fvs, at)),
823 ),
824 ProofExpr::Not(inner) => ProofExpr::Not(Box::new(subst_expr_avoiding(
825 inner,
826 var,
827 replacement,
828 repl_fvs,
829 at,
830 ))),
831
832 ProofExpr::ForAll {
835 variable,
836 body: inner,
837 } => {
838 if variable == var {
839 body.clone()
840 } else {
841 let (v, b) = rebind_for_subst(variable, inner, repl_fvs);
842 ProofExpr::ForAll {
843 variable: v,
844 body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
845 }
846 }
847 }
848 ProofExpr::Exists {
849 variable,
850 body: inner,
851 } => {
852 if variable == var {
853 body.clone()
854 } else {
855 let (v, b) = rebind_for_subst(variable, inner, repl_fvs);
856 ProofExpr::Exists {
857 variable: v,
858 body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
859 }
860 }
861 }
862
863 ProofExpr::Lambda {
864 variable,
865 body: inner,
866 } => {
867 if variable == var {
868 body.clone()
869 } else {
870 let (v, b) = rebind_for_subst(variable, inner, repl_fvs);
871 ProofExpr::Lambda {
872 variable: v,
873 body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
874 }
875 }
876 }
877
878 ProofExpr::App(f, a) => ProofExpr::App(
879 Box::new(subst_expr_avoiding(f, var, replacement, repl_fvs, at)),
880 Box::new(subst_expr_avoiding(a, var, replacement, repl_fvs, at)),
881 ),
882
883 ProofExpr::Modal {
884 domain,
885 force,
886 flavor,
887 body: inner,
888 } => ProofExpr::Modal {
889 domain: domain.clone(),
890 force: *force,
891 flavor: flavor.clone(),
892 body: Box::new(subst_expr_avoiding(inner, var, replacement, repl_fvs, at)),
893 },
894
895 ProofExpr::Counterfactual {
896 antecedent,
897 consequent,
898 } => ProofExpr::Counterfactual {
899 antecedent: Box::new(subst_expr_avoiding(
900 antecedent,
901 var,
902 replacement,
903 repl_fvs,
904 at,
905 )),
906 consequent: Box::new(subst_expr_avoiding(
907 consequent,
908 var,
909 replacement,
910 repl_fvs,
911 at,
912 )),
913 },
914
915 ProofExpr::Temporal {
916 operator,
917 body: inner,
918 } => ProofExpr::Temporal {
919 operator: operator.clone(),
920 body: Box::new(subst_expr_avoiding(inner, var, replacement, repl_fvs, at)),
921 },
922
923 ProofExpr::TemporalBinary {
924 operator,
925 left,
926 right,
927 } => ProofExpr::TemporalBinary {
928 operator: operator.clone(),
929 left: Box::new(subst_expr_avoiding(left, var, replacement, repl_fvs, at)),
930 right: Box::new(subst_expr_avoiding(right, var, replacement, repl_fvs, at)),
931 },
932
933 ProofExpr::NeoEvent {
934 event_var,
935 verb,
936 roles,
937 } => {
938 if event_var == var {
939 body.clone()
941 } else if repl_fvs.contains(event_var) {
942 let mut avoid = repl_fvs.clone();
944 for (_, t) in roles {
945 all_names_term(t, &mut avoid);
946 }
947 let fresh = fresh_proof_name(event_var, &avoid);
948 ProofExpr::NeoEvent {
949 event_var: fresh.clone(),
950 verb: verb.clone(),
951 roles: roles
952 .iter()
953 .map(|(r, t)| {
954 let renamed = alpha_rename_term(t, event_var, &fresh);
955 (
956 r.clone(),
957 substitute_term_for_var(&renamed, var, replacement),
958 )
959 })
960 .collect(),
961 }
962 } else {
963 ProofExpr::NeoEvent {
964 event_var: event_var.clone(),
965 verb: verb.clone(),
966 roles: roles
967 .iter()
968 .map(|(r, t)| (r.clone(), substitute_term_for_var(t, var, replacement)))
969 .collect(),
970 }
971 }
972 }
973
974 ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
975 name: name.clone(),
976 args: args
977 .iter()
978 .map(|a| subst_expr_avoiding(a, var, replacement, repl_fvs, at))
979 .collect(),
980 },
981
982 ProofExpr::Match { scrutinee, arms } => ProofExpr::Match {
983 scrutinee: Box::new(subst_expr_avoiding(
984 scrutinee,
985 var,
986 replacement,
987 repl_fvs,
988 at,
989 )),
990 arms: arms
991 .iter()
992 .map(|arm| {
993 if arm.bindings.iter().any(|b| b == var) {
995 arm.clone()
996 } else {
997 let mut arm_body = arm.body.clone();
1000 let mut new_bindings = arm.bindings.clone();
1001 let mut avoid = repl_fvs.clone();
1002 all_names_expr(&arm_body, &mut avoid);
1003 for b in &arm.bindings {
1004 avoid.insert(b.clone());
1005 }
1006 for binding in new_bindings.iter_mut() {
1007 if repl_fvs.contains(binding) {
1008 let fresh = fresh_proof_name(binding, &avoid);
1009 arm_body = alpha_rename_expr(&arm_body, binding, &fresh);
1010 avoid.insert(fresh.clone());
1011 *binding = fresh;
1012 }
1013 }
1014 MatchArm {
1015 ctor: arm.ctor.clone(),
1016 bindings: new_bindings,
1017 body: subst_expr_avoiding(&arm_body, var, replacement, repl_fvs, at),
1018 }
1019 }
1020 })
1021 .collect(),
1022 },
1023
1024 ProofExpr::Fixpoint { name, body: inner } => {
1025 if name == var {
1026 body.clone()
1027 } else {
1028 let (v, b) = rebind_for_subst(name, inner, repl_fvs);
1029 ProofExpr::Fixpoint {
1030 name: v,
1031 body: Box::new(subst_expr_avoiding(&b, var, replacement, repl_fvs, at)),
1032 }
1033 }
1034 }
1035
1036 ProofExpr::TypedVar { .. } | ProofExpr::Unsupported(_) => body.clone(),
1037
1038 ProofExpr::Hole(_) => body.clone(),
1040
1041 ProofExpr::Term(t) => ProofExpr::Term(substitute_term_for_var(t, var, replacement)),
1043 }
1044}
1045
1046fn substitute_term_for_var(term: &ProofTerm, var: &str, replacement: &ProofExpr) -> ProofTerm {
1050 match term {
1051 ProofTerm::Variable(v) if v == var => {
1052 expr_to_term(replacement)
1054 }
1055 ProofTerm::BoundVarRef(v) if v == var => expr_to_term(replacement),
1057 ProofTerm::Variable(_) | ProofTerm::Constant(_) | ProofTerm::BoundVarRef(_) => term.clone(),
1058 ProofTerm::Function(name, args) => ProofTerm::Function(
1059 name.clone(),
1060 args.iter()
1061 .map(|a| substitute_term_for_var(a, var, replacement))
1062 .collect(),
1063 ),
1064 ProofTerm::Group(terms) => ProofTerm::Group(
1065 terms
1066 .iter()
1067 .map(|t| substitute_term_for_var(t, var, replacement))
1068 .collect(),
1069 ),
1070 }
1071}
1072
1073fn expr_to_term(expr: &ProofExpr) -> ProofTerm {
1078 match expr {
1079 ProofExpr::Atom(s) => ProofTerm::Constant(s.clone()),
1081
1082 ProofExpr::Predicate { name, args, .. } if args.is_empty() => {
1084 ProofTerm::Constant(name.clone())
1085 }
1086
1087 ProofExpr::Predicate { name, args, .. } => ProofTerm::Function(name.clone(), args.clone()),
1089
1090 ProofExpr::Ctor { name, args } => {
1092 ProofTerm::Function(name.clone(), args.iter().map(expr_to_term).collect())
1093 }
1094
1095 ProofExpr::TypedVar { name, .. } => ProofTerm::Variable(name.clone()),
1097
1098 ProofExpr::Term(t) => t.clone(),
1100
1101 _ => ProofTerm::Constant(format!("{}", expr)),
1103 }
1104}
1105
1106pub fn unify_terms(t1: &ProofTerm, t2: &ProofTerm) -> ProofResult<Substitution> {
1153 let mut subst = Substitution::new();
1154 unify_terms_with_subst(t1, t2, &mut subst)?;
1155 Ok(subst)
1156}
1157
1158fn unify_terms_with_subst(
1160 t1: &ProofTerm,
1161 t2: &ProofTerm,
1162 subst: &mut Substitution,
1163) -> ProofResult<()> {
1164 let t1 = apply_subst_to_term(t1, subst);
1166 let t2 = apply_subst_to_term(t2, subst);
1167
1168 match (&t1, &t2) {
1169 (ProofTerm::Constant(c1), ProofTerm::Constant(c2)) if c1 == c2 => Ok(()),
1171
1172 (ProofTerm::Constant(c1), ProofTerm::Constant(c2)) => Err(ProofError::SymbolMismatch {
1174 left: c1.clone(),
1175 right: c2.clone(),
1176 }),
1177
1178 (ProofTerm::Variable(v), t) => {
1180 if let ProofTerm::Variable(v2) = t {
1182 if v == v2 {
1183 return Ok(());
1184 }
1185 }
1186 if occurs(v, t) {
1188 return Err(ProofError::OccursCheck {
1189 variable: v.clone(),
1190 term: t.clone(),
1191 });
1192 }
1193 subst.insert(v.clone(), t.clone());
1194 Ok(())
1195 }
1196
1197 (t, ProofTerm::Variable(v)) => {
1199 if occurs(v, t) {
1201 return Err(ProofError::OccursCheck {
1202 variable: v.clone(),
1203 term: t.clone(),
1204 });
1205 }
1206 subst.insert(v.clone(), t.clone());
1207 Ok(())
1208 }
1209
1210 (ProofTerm::BoundVarRef(v), t) => {
1213 if let ProofTerm::BoundVarRef(v2) = t {
1214 if v == v2 {
1215 return Ok(());
1216 }
1217 }
1218 if occurs(v, t) {
1219 return Err(ProofError::OccursCheck {
1220 variable: v.clone(),
1221 term: t.clone(),
1222 });
1223 }
1224 subst.insert(v.clone(), t.clone());
1225 Ok(())
1226 }
1227
1228 (t, ProofTerm::BoundVarRef(v)) => {
1230 if occurs(v, t) {
1231 return Err(ProofError::OccursCheck {
1232 variable: v.clone(),
1233 term: t.clone(),
1234 });
1235 }
1236 subst.insert(v.clone(), t.clone());
1237 Ok(())
1238 }
1239
1240 (ProofTerm::Function(f1, args1), ProofTerm::Function(f2, args2)) => {
1242 if f1 != f2 {
1243 return Err(ProofError::SymbolMismatch {
1244 left: f1.clone(),
1245 right: f2.clone(),
1246 });
1247 }
1248 if args1.len() != args2.len() {
1249 return Err(ProofError::ArityMismatch {
1250 expected: args1.len(),
1251 found: args2.len(),
1252 });
1253 }
1254 for (a1, a2) in args1.iter().zip(args2.iter()) {
1255 unify_terms_with_subst(a1, a2, subst)?;
1256 }
1257 Ok(())
1258 }
1259
1260 (ProofTerm::Group(g1), ProofTerm::Group(g2)) => {
1262 if g1.len() != g2.len() {
1263 return Err(ProofError::ArityMismatch {
1264 expected: g1.len(),
1265 found: g2.len(),
1266 });
1267 }
1268 for (t1, t2) in g1.iter().zip(g2.iter()) {
1269 unify_terms_with_subst(t1, t2, subst)?;
1270 }
1271 Ok(())
1272 }
1273
1274 _ => Err(ProofError::UnificationFailed {
1276 left: t1,
1277 right: t2,
1278 }),
1279 }
1280}
1281
1282fn occurs(var: &str, term: &ProofTerm) -> bool {
1285 match term {
1286 ProofTerm::Variable(v) => v == var,
1287 ProofTerm::BoundVarRef(v) => v == var, ProofTerm::Constant(_) => false,
1289 ProofTerm::Function(_, args) => args.iter().any(|a| occurs(var, a)),
1290 ProofTerm::Group(terms) => terms.iter().any(|t| occurs(var, t)),
1291 }
1292}
1293
1294pub fn apply_subst_to_term(term: &ProofTerm, subst: &Substitution) -> ProofTerm {
1332 resolve_term(term, subst, &mut Vec::new())
1333}
1334
1335fn resolve_term(term: &ProofTerm, subst: &Substitution, resolving: &mut Vec<String>) -> ProofTerm {
1338 match term {
1339 ProofTerm::Variable(v) | ProofTerm::BoundVarRef(v) => match subst.get(v) {
1341 Some(replacement) => {
1342 if resolving.iter().any(|r| r == v) {
1343 resolving.push(v.clone());
1344 panic!(
1345 "cyclic substitution {}: a triangular substitution resolves each replacement against the map, \
1346 and this one never resolves; a unifier's map is acyclic, and instantiating a binder \
1347 (`body[x := t]`) is `unify::instantiate_expr`",
1348 resolving.join(" ↦ ")
1349 );
1350 }
1351 resolving.push(v.clone());
1352 let resolved = resolve_term(replacement, subst, resolving);
1353 resolving.pop();
1354 resolved
1355 }
1356 None => term.clone(),
1357 },
1358 ProofTerm::Constant(_) => term.clone(),
1359 ProofTerm::Function(name, args) => {
1360 let new_args = args
1361 .iter()
1362 .map(|a| resolve_term(a, subst, resolving))
1363 .collect();
1364 ProofTerm::Function(name.clone(), new_args)
1365 }
1366 ProofTerm::Group(terms) => {
1367 let new_terms = terms
1368 .iter()
1369 .map(|t| resolve_term(t, subst, resolving))
1370 .collect();
1371 ProofTerm::Group(new_terms)
1372 }
1373 }
1374}
1375
1376pub fn unify_exprs(e1: &ProofExpr, e2: &ProofExpr) -> ProofResult<Substitution> {
1415 let mut subst = Substitution::new();
1416 unify_exprs_with_subst(e1, e2, &mut subst)?;
1417 Ok(subst)
1418}
1419
1420fn unify_exprs_with_subst(
1422 e1: &ProofExpr,
1423 e2: &ProofExpr,
1424 subst: &mut Substitution,
1425) -> ProofResult<()> {
1426 let e1 = beta_reduce(e1);
1429 let e2 = beta_reduce(e2);
1430
1431 match (&e1, &e2) {
1432 (ProofExpr::Atom(a1), ProofExpr::Atom(a2)) if a1 == a2 => Ok(()),
1434
1435 (
1437 ProofExpr::Predicate {
1438 name: n1,
1439 args: a1,
1440 world: w1,
1441 },
1442 ProofExpr::Predicate {
1443 name: n2,
1444 args: a2,
1445 world: w2,
1446 },
1447 ) => {
1448 if n1 != n2 {
1449 return Err(ProofError::SymbolMismatch {
1450 left: n1.clone(),
1451 right: n2.clone(),
1452 });
1453 }
1454 if a1.len() != a2.len() {
1455 return Err(ProofError::ArityMismatch {
1456 expected: a1.len(),
1457 found: a2.len(),
1458 });
1459 }
1460 match (w1, w2) {
1462 (Some(w1), Some(w2)) if w1 != w2 => {
1463 return Err(ProofError::SymbolMismatch {
1464 left: w1.clone(),
1465 right: w2.clone(),
1466 });
1467 }
1468 _ => {}
1469 }
1470 for (t1, t2) in a1.iter().zip(a2.iter()) {
1472 unify_terms_with_subst(t1, t2, subst)?;
1473 }
1474 Ok(())
1475 }
1476
1477 (ProofExpr::Identity(l1, r1), ProofExpr::Identity(l2, r2)) => {
1479 unify_terms_with_subst(l1, l2, subst)?;
1480 unify_terms_with_subst(r1, r2, subst)?;
1481 Ok(())
1482 }
1483
1484 (ProofExpr::And(l1, r1), ProofExpr::And(l2, r2))
1486 | (ProofExpr::Or(l1, r1), ProofExpr::Or(l2, r2))
1487 | (ProofExpr::Implies(l1, r1), ProofExpr::Implies(l2, r2))
1488 | (ProofExpr::Iff(l1, r1), ProofExpr::Iff(l2, r2)) => {
1489 unify_exprs_with_subst(l1, l2, subst)?;
1490 unify_exprs_with_subst(r1, r2, subst)?;
1491 Ok(())
1492 }
1493
1494 (ProofExpr::Not(inner1), ProofExpr::Not(inner2)) => {
1496 unify_exprs_with_subst(inner1, inner2, subst)
1497 }
1498
1499 (
1502 ProofExpr::ForAll {
1503 variable: v1,
1504 body: b1,
1505 },
1506 ProofExpr::ForAll {
1507 variable: v2,
1508 body: b2,
1509 },
1510 )
1511 | (
1512 ProofExpr::Exists {
1513 variable: v1,
1514 body: b1,
1515 },
1516 ProofExpr::Exists {
1517 variable: v2,
1518 body: b2,
1519 },
1520 ) => {
1521 let fresh = fresh_alpha_constant();
1524
1525 let subst1: Substitution = [(v1.clone(), fresh.clone())].into_iter().collect();
1527 let subst2: Substitution = [(v2.clone(), fresh)].into_iter().collect();
1528
1529 let body1_renamed = apply_subst_to_expr(b1, &subst1);
1531 let body2_renamed = apply_subst_to_expr(b2, &subst2);
1532
1533 unify_exprs_with_subst(&body1_renamed, &body2_renamed, subst)
1535 }
1536
1537 (
1539 ProofExpr::Lambda {
1540 variable: v1,
1541 body: b1,
1542 },
1543 ProofExpr::Lambda {
1544 variable: v2,
1545 body: b2,
1546 },
1547 ) => {
1548 let fresh = fresh_alpha_constant();
1550 let subst1: Substitution = [(v1.clone(), fresh.clone())].into_iter().collect();
1551 let subst2: Substitution = [(v2.clone(), fresh)].into_iter().collect();
1552 let body1_renamed = apply_subst_to_expr(b1, &subst1);
1553 let body2_renamed = apply_subst_to_expr(b2, &subst2);
1554 unify_exprs_with_subst(&body1_renamed, &body2_renamed, subst)
1555 }
1556
1557 (ProofExpr::App(f1, a1), ProofExpr::App(f2, a2)) => {
1559 unify_exprs_with_subst(f1, f2, subst)?;
1560 unify_exprs_with_subst(a1, a2, subst)?;
1561 Ok(())
1562 }
1563
1564 (
1567 ProofExpr::NeoEvent {
1568 event_var: e1,
1569 verb: v1,
1570 roles: r1,
1571 },
1572 ProofExpr::NeoEvent {
1573 event_var: e2,
1574 verb: v2,
1575 roles: r2,
1576 },
1577 ) => {
1578 if v1.to_lowercase() != v2.to_lowercase() {
1580 return Err(ProofError::SymbolMismatch {
1581 left: v1.clone(),
1582 right: v2.clone(),
1583 });
1584 }
1585
1586 if r1.len() != r2.len() {
1588 return Err(ProofError::ArityMismatch {
1589 expected: r1.len(),
1590 found: r2.len(),
1591 });
1592 }
1593
1594 let fresh = fresh_alpha_constant();
1596 let subst1: Substitution = [(e1.clone(), fresh.clone())].into_iter().collect();
1597 let subst2: Substitution = [(e2.clone(), fresh)].into_iter().collect();
1598
1599 for ((role1, term1), (role2, term2)) in r1.iter().zip(r2.iter()) {
1601 if role1 != role2 {
1603 return Err(ProofError::SymbolMismatch {
1604 left: role1.clone(),
1605 right: role2.clone(),
1606 });
1607 }
1608 let t1_renamed = apply_subst_to_term(term1, &subst1);
1610 let t2_renamed = apply_subst_to_term(term2, &subst2);
1611 unify_terms_with_subst(&t1_renamed, &t2_renamed, subst)?;
1612 }
1613 Ok(())
1614 }
1615
1616 (
1619 ProofExpr::Temporal {
1620 operator: op1,
1621 body: b1,
1622 },
1623 ProofExpr::Temporal {
1624 operator: op2,
1625 body: b2,
1626 },
1627 ) => {
1628 if op1 != op2 {
1629 return Err(ProofError::ExprUnificationFailed {
1630 left: e1.clone(),
1631 right: e2.clone(),
1632 });
1633 }
1634 unify_exprs_with_subst(b1, b2, subst)
1635 }
1636
1637 (
1640 ProofExpr::TemporalBinary {
1641 operator: op1,
1642 left: l1,
1643 right: r1,
1644 },
1645 ProofExpr::TemporalBinary {
1646 operator: op2,
1647 left: l2,
1648 right: r2,
1649 },
1650 ) => {
1651 if op1 != op2 {
1652 return Err(ProofError::ExprUnificationFailed {
1653 left: e1.clone(),
1654 right: e2.clone(),
1655 });
1656 }
1657 unify_exprs_with_subst(l1, l2, subst)?;
1658 unify_exprs_with_subst(r1, r2, subst)
1659 }
1660
1661 _ => Err(ProofError::ExprUnificationFailed {
1663 left: e1.clone(),
1664 right: e2.clone(),
1665 }),
1666 }
1667}
1668
1669pub fn apply_subst_to_expr(expr: &ProofExpr, subst: &Substitution) -> ProofExpr {
1693 match expr {
1694 ProofExpr::Predicate { name, args, world } => ProofExpr::Predicate {
1695 name: name.clone(),
1696 args: args.iter().map(|a| apply_subst_to_term(a, subst)).collect(),
1697 world: world.clone(),
1698 },
1699 ProofExpr::Identity(l, r) => {
1700 ProofExpr::Identity(apply_subst_to_term(l, subst), apply_subst_to_term(r, subst))
1701 }
1702 ProofExpr::Atom(a) => ProofExpr::Atom(a.clone()),
1703 ProofExpr::And(l, r) => ProofExpr::And(
1704 Box::new(apply_subst_to_expr(l, subst)),
1705 Box::new(apply_subst_to_expr(r, subst)),
1706 ),
1707 ProofExpr::Or(l, r) => ProofExpr::Or(
1708 Box::new(apply_subst_to_expr(l, subst)),
1709 Box::new(apply_subst_to_expr(r, subst)),
1710 ),
1711 ProofExpr::Implies(l, r) => ProofExpr::Implies(
1712 Box::new(apply_subst_to_expr(l, subst)),
1713 Box::new(apply_subst_to_expr(r, subst)),
1714 ),
1715 ProofExpr::Iff(l, r) => ProofExpr::Iff(
1716 Box::new(apply_subst_to_expr(l, subst)),
1717 Box::new(apply_subst_to_expr(r, subst)),
1718 ),
1719 ProofExpr::Not(inner) => ProofExpr::Not(Box::new(apply_subst_to_expr(inner, subst))),
1720 ProofExpr::ForAll { variable, body } => {
1721 let new_variable = match subst.get(variable) {
1723 Some(ProofTerm::Variable(new_name)) => new_name.clone(),
1724 _ => variable.clone(),
1725 };
1726 ProofExpr::ForAll {
1727 variable: new_variable,
1728 body: Box::new(apply_subst_to_expr(body, subst)),
1729 }
1730 }
1731 ProofExpr::Exists { variable, body } => {
1732 let new_variable = match subst.get(variable) {
1734 Some(ProofTerm::Variable(new_name)) => new_name.clone(),
1735 _ => variable.clone(),
1736 };
1737 ProofExpr::Exists {
1738 variable: new_variable,
1739 body: Box::new(apply_subst_to_expr(body, subst)),
1740 }
1741 }
1742 ProofExpr::Modal {
1743 domain,
1744 force,
1745 flavor,
1746 body,
1747 } => ProofExpr::Modal {
1748 domain: domain.clone(),
1749 force: *force,
1750 flavor: flavor.clone(),
1751 body: Box::new(apply_subst_to_expr(body, subst)),
1752 },
1753 ProofExpr::Counterfactual {
1754 antecedent,
1755 consequent,
1756 } => ProofExpr::Counterfactual {
1757 antecedent: Box::new(apply_subst_to_expr(antecedent, subst)),
1758 consequent: Box::new(apply_subst_to_expr(consequent, subst)),
1759 },
1760 ProofExpr::Temporal { operator, body } => ProofExpr::Temporal {
1761 operator: operator.clone(),
1762 body: Box::new(apply_subst_to_expr(body, subst)),
1763 },
1764 ProofExpr::TemporalBinary {
1765 operator,
1766 left,
1767 right,
1768 } => ProofExpr::TemporalBinary {
1769 operator: operator.clone(),
1770 left: Box::new(apply_subst_to_expr(left, subst)),
1771 right: Box::new(apply_subst_to_expr(right, subst)),
1772 },
1773 ProofExpr::Lambda { variable, body } => {
1774 let new_variable = match subst.get(variable) {
1776 Some(ProofTerm::Variable(new_name)) => new_name.clone(),
1777 _ => variable.clone(),
1778 };
1779 ProofExpr::Lambda {
1780 variable: new_variable,
1781 body: Box::new(apply_subst_to_expr(body, subst)),
1782 }
1783 }
1784 ProofExpr::App(f, a) => ProofExpr::App(
1785 Box::new(apply_subst_to_expr(f, subst)),
1786 Box::new(apply_subst_to_expr(a, subst)),
1787 ),
1788 ProofExpr::NeoEvent {
1789 event_var,
1790 verb,
1791 roles,
1792 } => ProofExpr::NeoEvent {
1793 event_var: event_var.clone(),
1794 verb: verb.clone(),
1795 roles: roles
1796 .iter()
1797 .map(|(r, t)| (r.clone(), apply_subst_to_term(t, subst)))
1798 .collect(),
1799 },
1800 ProofExpr::Ctor { name, args } => ProofExpr::Ctor {
1802 name: name.clone(),
1803 args: args.iter().map(|a| apply_subst_to_expr(a, subst)).collect(),
1804 },
1805 ProofExpr::Match { scrutinee, arms } => ProofExpr::Match {
1806 scrutinee: Box::new(apply_subst_to_expr(scrutinee, subst)),
1807 arms: arms
1808 .iter()
1809 .map(|arm| MatchArm {
1810 ctor: arm.ctor.clone(),
1811 bindings: arm.bindings.clone(),
1812 body: apply_subst_to_expr(&arm.body, subst),
1813 })
1814 .collect(),
1815 },
1816 ProofExpr::Fixpoint { name, body } => ProofExpr::Fixpoint {
1817 name: name.clone(),
1818 body: Box::new(apply_subst_to_expr(body, subst)),
1819 },
1820 ProofExpr::TypedVar { name, typename } => ProofExpr::TypedVar {
1821 name: name.clone(),
1822 typename: typename.clone(),
1823 },
1824 ProofExpr::Unsupported(s) => ProofExpr::Unsupported(s.clone()),
1825 ProofExpr::Hole(name) => ProofExpr::Hole(name.clone()),
1827 ProofExpr::Term(t) => ProofExpr::Term(apply_subst_to_term(t, subst)),
1829 }
1830}
1831
1832pub fn compose_substitutions(s1: Substitution, s2: Substitution) -> Substitution {
1865 let mut result: Substitution = s1
1866 .into_iter()
1867 .map(|(k, v)| (k, apply_subst_to_term(&v, &s2)))
1868 .collect();
1869
1870 for (k, v) in s2 {
1872 result.entry(k).or_insert(v);
1873 }
1874
1875 result
1876}
1877
1878pub fn unify_pattern(lhs: &ProofExpr, rhs: &ProofExpr) -> ProofResult<ExprSubstitution> {
1920 let mut solution = ExprSubstitution::new();
1921 unify_pattern_internal(lhs, rhs, &mut solution)?;
1922 Ok(solution)
1923}
1924
1925fn unify_pattern_internal(
1927 lhs: &ProofExpr,
1928 rhs: &ProofExpr,
1929 solution: &mut ExprSubstitution,
1930) -> ProofResult<()> {
1931 let lhs = beta_reduce(lhs);
1933 let rhs = beta_reduce(rhs);
1934
1935 match &lhs {
1936 ProofExpr::Hole(h) => {
1938 solution.insert(h.clone(), rhs.clone());
1939 Ok(())
1940 }
1941
1942 ProofExpr::App(_, _) => {
1944 let (head, args) = collect_app_args(&lhs);
1946
1947 if let ProofExpr::Hole(h) = head {
1948 let var_args = extract_distinct_vars(&args)?;
1950
1951 check_scope(&rhs, &var_args)?;
1953
1954 let renamed_rhs = rename_vars_to_bound(&rhs, &var_args);
1957 let lambda = build_lambda(var_args, renamed_rhs);
1958 solution.insert(h.clone(), lambda);
1959 Ok(())
1960 } else {
1961 if lhs == rhs {
1963 Ok(())
1964 } else {
1965 Err(ProofError::ExprUnificationFailed {
1966 left: lhs.clone(),
1967 right: rhs.clone(),
1968 })
1969 }
1970 }
1971 }
1972
1973 _ => {
1975 if lhs == rhs {
1976 Ok(())
1977 } else {
1978 Err(ProofError::ExprUnificationFailed {
1979 left: lhs.clone(),
1980 right: rhs.clone(),
1981 })
1982 }
1983 }
1984 }
1985}
1986
1987fn collect_app_args(expr: &ProofExpr) -> (ProofExpr, Vec<ProofExpr>) {
1989 let mut args = Vec::new();
1990 let mut current = expr.clone();
1991
1992 while let ProofExpr::App(func, arg) = current {
1993 args.push(*arg);
1994 current = *func;
1995 }
1996
1997 args.reverse();
1998 (current, args)
1999}
2000
2001fn extract_distinct_vars(args: &[ProofExpr]) -> ProofResult<Vec<String>> {
2004 let mut vars = Vec::new();
2005 for arg in args {
2006 match arg {
2007 ProofExpr::Term(ProofTerm::BoundVarRef(v)) => {
2008 if vars.contains(v) {
2009 return Err(ProofError::PatternNotDistinct(v.clone()));
2010 }
2011 vars.push(v.clone());
2012 }
2013 _ => return Err(ProofError::NotAPattern(arg.clone())),
2014 }
2015 }
2016 Ok(vars)
2017}
2018
2019fn check_scope(expr: &ProofExpr, allowed: &[String]) -> ProofResult<()> {
2021 let free_vars = collect_free_vars(expr);
2022 for var in free_vars {
2023 if !allowed.contains(&var) {
2024 return Err(ProofError::ScopeViolation {
2025 var,
2026 allowed: allowed.to_vec(),
2027 });
2028 }
2029 }
2030 Ok(())
2031}
2032
2033fn collect_free_vars(expr: &ProofExpr) -> Vec<String> {
2035 let mut vars = Vec::new();
2036 collect_free_vars_impl(expr, &mut vars, &mut Vec::new());
2037 vars
2038}
2039
2040fn collect_free_vars_impl(expr: &ProofExpr, vars: &mut Vec<String>, bound: &mut Vec<String>) {
2041 match expr {
2042 ProofExpr::Predicate { args, .. } => {
2043 for arg in args {
2044 collect_free_vars_term(arg, vars, bound);
2045 }
2046 }
2047 ProofExpr::Identity(l, r) => {
2048 collect_free_vars_term(l, vars, bound);
2049 collect_free_vars_term(r, vars, bound);
2050 }
2051 ProofExpr::Atom(s) => {
2052 if !bound.contains(s) && !vars.contains(s) {
2053 vars.push(s.clone());
2054 }
2055 }
2056 ProofExpr::And(l, r)
2057 | ProofExpr::Or(l, r)
2058 | ProofExpr::Implies(l, r)
2059 | ProofExpr::Iff(l, r) => {
2060 collect_free_vars_impl(l, vars, bound);
2061 collect_free_vars_impl(r, vars, bound);
2062 }
2063 ProofExpr::Not(inner) => collect_free_vars_impl(inner, vars, bound),
2064 ProofExpr::ForAll { variable, body }
2065 | ProofExpr::Exists { variable, body }
2066 | ProofExpr::Lambda { variable, body } => {
2067 bound.push(variable.clone());
2068 collect_free_vars_impl(body, vars, bound);
2069 bound.pop();
2070 }
2071 ProofExpr::App(f, a) => {
2072 collect_free_vars_impl(f, vars, bound);
2073 collect_free_vars_impl(a, vars, bound);
2074 }
2075 ProofExpr::Term(t) => collect_free_vars_term(t, vars, bound),
2076 ProofExpr::Hole(_) => {} _ => {} }
2079}
2080
2081fn collect_free_vars_term(term: &ProofTerm, vars: &mut Vec<String>, bound: &[String]) {
2082 match term {
2083 ProofTerm::Variable(v) => {
2084 if !bound.contains(v) && !vars.contains(v) {
2085 vars.push(v.clone());
2086 }
2087 }
2088 ProofTerm::Function(_, args) => {
2089 for arg in args {
2090 collect_free_vars_term(arg, vars, bound);
2091 }
2092 }
2093 ProofTerm::Group(terms) => {
2094 for t in terms {
2095 collect_free_vars_term(t, vars, bound);
2096 }
2097 }
2098 ProofTerm::Constant(_) | ProofTerm::BoundVarRef(_) => {}
2099 }
2100}
2101
2102fn rename_vars_to_bound(expr: &ProofExpr, bound_vars: &[String]) -> ProofExpr {
2105 expr.clone()
2109}
2110
2111fn build_lambda(vars: Vec<String>, body: ProofExpr) -> ProofExpr {
2113 vars.into_iter()
2114 .rev()
2115 .fold(body, |acc, var| ProofExpr::Lambda {
2116 variable: var,
2117 body: Box::new(acc),
2118 })
2119}
2120
2121pub fn match_term_pattern(pattern: &ProofTerm, target: &ProofTerm) -> Option<Substitution> {
2131 let mut subst = Substitution::new();
2132 let mut bound = Vec::new();
2133 if match_term_into(pattern, target, &mut subst, &mut bound) {
2134 Some(subst)
2135 } else {
2136 None
2137 }
2138}
2139
2140pub fn match_expr_pattern(pattern: &ProofExpr, target: &ProofExpr) -> Option<Substitution> {
2146 let mut subst = Substitution::new();
2147 let mut bound = Vec::new();
2148 if match_expr_into(pattern, target, &mut subst, &mut bound) {
2149 Some(subst)
2150 } else {
2151 None
2152 }
2153}
2154
2155fn match_bind(subst: &mut Substitution, bound: &[String], name: &str, value: &ProofTerm) -> bool {
2158 if let Some(existing) = subst.get(name) {
2159 return existing == value;
2160 }
2161 if term_mentions_any(value, bound) {
2162 return false;
2163 }
2164 subst.insert(name.to_string(), value.clone());
2165 true
2166}
2167
2168fn term_mentions_any(t: &ProofTerm, names: &[String]) -> bool {
2169 match t {
2170 ProofTerm::Variable(n) | ProofTerm::BoundVarRef(n) => names.iter().any(|b| b == n),
2171 ProofTerm::Constant(_) => false,
2172 ProofTerm::Function(_, args) | ProofTerm::Group(args) => {
2173 args.iter().any(|a| term_mentions_any(a, names))
2174 }
2175 }
2176}
2177
2178fn match_term_into(
2179 pattern: &ProofTerm,
2180 target: &ProofTerm,
2181 subst: &mut Substitution,
2182 bound: &mut Vec<String>,
2183) -> bool {
2184 match pattern {
2185 ProofTerm::Variable(name) => {
2186 if bound.contains(name) {
2189 return matches!(target, ProofTerm::Variable(n) if n == name);
2190 }
2191 match_bind(subst, bound, name, target)
2192 }
2193 ProofTerm::Constant(a) => matches!(target, ProofTerm::Constant(b) if a == b),
2194 ProofTerm::BoundVarRef(a) => matches!(target, ProofTerm::BoundVarRef(b) if a == b),
2195 ProofTerm::Function(name, args) => match target {
2196 ProofTerm::Function(tname, targs) if name == tname && args.len() == targs.len() => {
2197 for (a, b) in args.iter().zip(targs) {
2198 if !match_term_into(a, b, subst, bound) {
2199 return false;
2200 }
2201 }
2202 true
2203 }
2204 _ => false,
2205 },
2206 ProofTerm::Group(args) => match target {
2207 ProofTerm::Group(targs) if args.len() == targs.len() => {
2208 for (a, b) in args.iter().zip(targs) {
2209 if !match_term_into(a, b, subst, bound) {
2210 return false;
2211 }
2212 }
2213 true
2214 }
2215 _ => false,
2216 },
2217 }
2218}
2219
2220fn match_expr_into(
2221 pattern: &ProofExpr,
2222 target: &ProofExpr,
2223 subst: &mut Substitution,
2224 bound: &mut Vec<String>,
2225) -> bool {
2226 match (pattern, target) {
2227 (
2228 ProofExpr::Predicate {
2229 name: pn,
2230 args: pa,
2231 world: pw,
2232 },
2233 ProofExpr::Predicate {
2234 name: tn,
2235 args: ta,
2236 world: tw,
2237 },
2238 ) => {
2239 if pn != tn || pa.len() != ta.len() || pw != tw {
2240 return false;
2241 }
2242 for (a, b) in pa.iter().zip(ta) {
2243 if !match_term_into(a, b, subst, bound) {
2244 return false;
2245 }
2246 }
2247 true
2248 }
2249 (ProofExpr::Identity(pl, pr), ProofExpr::Identity(tl, tr)) => {
2250 match_term_into(pl, tl, subst, bound) && match_term_into(pr, tr, subst, bound)
2251 }
2252 (ProofExpr::Atom(a), ProofExpr::Atom(b)) => a == b,
2253 (ProofExpr::And(pl, pr), ProofExpr::And(tl, tr))
2254 | (ProofExpr::Or(pl, pr), ProofExpr::Or(tl, tr))
2255 | (ProofExpr::Implies(pl, pr), ProofExpr::Implies(tl, tr))
2256 | (ProofExpr::Iff(pl, pr), ProofExpr::Iff(tl, tr)) => {
2257 match_expr_into(pl, tl, subst, bound) && match_expr_into(pr, tr, subst, bound)
2258 }
2259 (ProofExpr::Not(p), ProofExpr::Not(t)) => match_expr_into(p, t, subst, bound),
2260 (
2261 ProofExpr::ForAll {
2262 variable: pv,
2263 body: pb,
2264 },
2265 ProofExpr::ForAll {
2266 variable: tv,
2267 body: tb,
2268 },
2269 )
2270 | (
2271 ProofExpr::Exists {
2272 variable: pv,
2273 body: pb,
2274 },
2275 ProofExpr::Exists {
2276 variable: tv,
2277 body: tb,
2278 },
2279 ) => {
2280 if pv != tv {
2281 return false;
2282 }
2283 bound.push(pv.clone());
2284 let ok = match_expr_into(pb, tb, subst, bound);
2285 bound.pop();
2286 ok
2287 }
2288 _ => pattern == target,
2291 }
2292}
2293
2294#[cfg(test)]
2295#[path = "../../logicaffeine_tests/unit/logicaffeine_proof/unify/tests.rs"]
2296mod tests;