258 |> (fn thm => thm RS sym) (* "Gsi, Gsj, lhsi = lhsj |-- rhsj = rhsi" *) |
258 |> (fn thm => thm RS sym) (* "Gsi, Gsj, lhsi = lhsj |-- rhsj = rhsi" *) |
259 end |
259 end |
260 end |
260 end |
261 |
261 |
262 (* Generates the replacement lemma in fully quantified form. *) |
262 (* Generates the replacement lemma in fully quantified form. *) |
263 fun mk_replacement_lemma thy h ih_elim clause = |
263 fun mk_replacement_lemma ctxt h ih_elim clause = |
264 let |
264 let |
|
265 val thy = Proof_Context.theory_of ctxt |
265 val ClauseInfo {cdata=ClauseContext {qs, lhs, cqs, ags, case_hyp, ...}, |
266 val ClauseInfo {cdata=ClauseContext {qs, lhs, cqs, ags, case_hyp, ...}, |
266 RCs, tree, ...} = clause |
267 RCs, tree, ...} = clause |
267 local open Conv in |
268 local open Conv in |
268 val ih_conv = arg1_conv o arg_conv o arg_conv |
269 val ih_conv = arg1_conv o arg_conv o arg_conv |
269 end |
270 end |
274 val Ris = map (fn RCInfo {llRI, ...} => llRI) RCs |
275 val Ris = map (fn RCInfo {llRI, ...} => llRI) RCs |
275 val h_assums = map (fn RCInfo {h_assum, ...} => |
276 val h_assums = map (fn RCInfo {h_assum, ...} => |
276 Thm.assume (cterm_of thy (subst_bounds (rev qs, h_assum)))) RCs |
277 Thm.assume (cterm_of thy (subst_bounds (rev qs, h_assum)))) RCs |
277 |
278 |
278 val (eql, _) = |
279 val (eql, _) = |
279 Function_Ctx_Tree.rewrite_by_tree thy h ih_elim_case (Ris ~~ h_assums) tree |
280 Function_Ctx_Tree.rewrite_by_tree ctxt h ih_elim_case (Ris ~~ h_assums) tree |
280 |
281 |
281 val replace_lemma = (eql RS meta_eq_to_obj_eq) |
282 val replace_lemma = (eql RS meta_eq_to_obj_eq) |
282 |> Thm.implies_intr (cprop_of case_hyp) |
283 |> Thm.implies_intr (cprop_of case_hyp) |
283 |> fold_rev (Thm.implies_intr o cprop_of) h_assums |
284 |> fold_rev (Thm.implies_intr o cprop_of) h_assums |
284 |> fold_rev (Thm.implies_intr o cprop_of) ags |
285 |> fold_rev (Thm.implies_intr o cprop_of) ags |
326 |> fold_rev Thm.forall_intr (cterm_of thy h :: cqsj') |
327 |> fold_rev Thm.forall_intr (cterm_of thy h :: cqsj') |
327 end |
328 end |
328 |
329 |
329 |
330 |
330 |
331 |
331 fun mk_uniqueness_case thy globals G f ihyp ih_intro G_cases compat_store clauses rep_lemmas clausei = |
332 fun mk_uniqueness_case ctxt globals G f ihyp ih_intro G_cases compat_store clauses rep_lemmas clausei = |
332 let |
333 let |
|
334 val thy = Proof_Context.theory_of ctxt |
333 val Globals {x, y, ranT, fvar, ...} = globals |
335 val Globals {x, y, ranT, fvar, ...} = globals |
334 val ClauseInfo {cdata = ClauseContext {lhs, rhs, cqs, ags, case_hyp, ...}, lGI, RCs, ...} = clausei |
336 val ClauseInfo {cdata = ClauseContext {lhs, rhs, cqs, ags, case_hyp, ...}, lGI, RCs, ...} = clausei |
335 val rhsC = Pattern.rewrite_term thy [(fvar, f)] [] rhs |
337 val rhsC = Pattern.rewrite_term thy [(fvar, f)] [] rhs |
336 |
338 |
337 val ih_intro_case = full_simplify (HOL_basic_ss addsimps [case_hyp]) ih_intro |
339 val ih_intro_case = full_simplify (put_simpset HOL_basic_ss ctxt addsimps [case_hyp]) ih_intro |
338 |
340 |
339 fun prep_RC (RCInfo {llRI, RIvs, CCas, ...}) = (llRI RS ih_intro_case) |
341 fun prep_RC (RCInfo {llRI, RIvs, CCas, ...}) = (llRI RS ih_intro_case) |
340 |> fold_rev (Thm.implies_intr o cprop_of) CCas |
342 |> fold_rev (Thm.implies_intr o cprop_of) CCas |
341 |> fold_rev (Thm.forall_intr o cterm_of thy o Free) RIvs |
343 |> fold_rev (Thm.forall_intr o cterm_of thy o Free) RIvs |
342 |
344 |
364 |
366 |
365 val exactly_one = |
367 val exactly_one = |
366 ex1I |> instantiate' [SOME (ctyp_of thy ranT)] [SOME P2, SOME (cterm_of thy rhsC)] |
368 ex1I |> instantiate' [SOME (ctyp_of thy ranT)] [SOME P2, SOME (cterm_of thy rhsC)] |
367 |> curry (op COMP) existence |
369 |> curry (op COMP) existence |
368 |> curry (op COMP) uniqueness |
370 |> curry (op COMP) uniqueness |
369 |> simplify (HOL_basic_ss addsimps [case_hyp RS sym]) |
371 |> simplify (put_simpset HOL_basic_ss ctxt addsimps [case_hyp RS sym]) |
370 |> Thm.implies_intr (cprop_of case_hyp) |
372 |> Thm.implies_intr (cprop_of case_hyp) |
371 |> fold_rev (Thm.implies_intr o cprop_of) ags |
373 |> fold_rev (Thm.implies_intr o cprop_of) ags |
372 |> fold_rev Thm.forall_intr cqs |
374 |> fold_rev Thm.forall_intr cqs |
373 |
375 |
374 val function_value = |
376 val function_value = |
399 val ih_intro = ihyp_thm RS (f_def RS ex1_implies_ex) |
401 val ih_intro = ihyp_thm RS (f_def RS ex1_implies_ex) |
400 val ih_elim = ihyp_thm RS (f_def RS ex1_implies_un) |
402 val ih_elim = ihyp_thm RS (f_def RS ex1_implies_un) |
401 |> instantiate' [] [NONE, SOME (cterm_of thy h)] |
403 |> instantiate' [] [NONE, SOME (cterm_of thy h)] |
402 |
404 |
403 val _ = trace_msg (K "Proving Replacement lemmas...") |
405 val _ = trace_msg (K "Proving Replacement lemmas...") |
404 val repLemmas = map (mk_replacement_lemma thy h ih_elim) clauses |
406 val repLemmas = map (mk_replacement_lemma ctxt h ih_elim) clauses |
405 |
407 |
406 val _ = trace_msg (K "Proving cases for unique existence...") |
408 val _ = trace_msg (K "Proving cases for unique existence...") |
407 val (ex1s, values) = |
409 val (ex1s, values) = |
408 split_list (map (mk_uniqueness_case thy globals G f ihyp ih_intro G_elim compat_store clauses repLemmas) clauses) |
410 split_list |
|
411 (map |
|
412 (mk_uniqueness_case ctxt globals G f ihyp ih_intro G_elim compat_store clauses repLemmas) |
|
413 clauses) |
409 |
414 |
410 val _ = trace_msg (K "Proving: Graph is a function") |
415 val _ = trace_msg (K "Proving: Graph is a function") |
411 val graph_is_function = complete |
416 val graph_is_function = complete |
412 |> Thm.forall_elim_vars 0 |
417 |> Thm.forall_elim_vars 0 |
413 |> fold (curry op COMP) ex1s |
418 |> fold (curry op COMP) ex1s |
549 |
554 |
550 (********************************************************** |
555 (********************************************************** |
551 * PROVING THE RULES |
556 * PROVING THE RULES |
552 **********************************************************) |
557 **********************************************************) |
553 |
558 |
554 fun mk_psimps thy globals R clauses valthms f_iff graph_is_function = |
559 fun mk_psimps ctxt globals R clauses valthms f_iff graph_is_function = |
555 let |
560 let |
|
561 val thy = Proof_Context.theory_of ctxt |
556 val Globals {domT, z, ...} = globals |
562 val Globals {domT, z, ...} = globals |
557 |
563 |
558 fun mk_psimp (ClauseInfo {qglr = (oqs, _, _, _), cdata = ClauseContext {cqs, lhs, ags, ...}, ...}) valthm = |
564 fun mk_psimp (ClauseInfo {qglr = (oqs, _, _, _), cdata = ClauseContext {cqs, lhs, ags, ...}, ...}) valthm = |
559 let |
565 let |
560 val lhs_acc = cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ lhs)) (* "acc R lhs" *) |
566 val lhs_acc = cterm_of thy (HOLogic.mk_Trueprop (mk_acc domT R $ lhs)) (* "acc R lhs" *) |
564 |> (fn it => it COMP graph_is_function) |
570 |> (fn it => it COMP graph_is_function) |
565 |> Thm.implies_intr z_smaller |
571 |> Thm.implies_intr z_smaller |
566 |> Thm.forall_intr (cterm_of thy z) |
572 |> Thm.forall_intr (cterm_of thy z) |
567 |> (fn it => it COMP valthm) |
573 |> (fn it => it COMP valthm) |
568 |> Thm.implies_intr lhs_acc |
574 |> Thm.implies_intr lhs_acc |
569 |> asm_simplify (HOL_basic_ss addsimps [f_iff]) |
575 |> asm_simplify (put_simpset HOL_basic_ss ctxt addsimps [f_iff]) |
570 |> fold_rev (Thm.implies_intr o cprop_of) ags |
576 |> fold_rev (Thm.implies_intr o cprop_of) ags |
571 |> fold_rev forall_intr_rename (map fst oqs ~~ cqs) |
577 |> fold_rev forall_intr_rename (map fst oqs ~~ cqs) |
572 end |
578 end |
573 in |
579 in |
574 map2 mk_psimp clauses valthms |
580 map2 mk_psimp clauses valthms |
712 |
718 |
713 val wf_induct_rule = @{thm Wellfounded.wfP_induct_rule} |
719 val wf_induct_rule = @{thm Wellfounded.wfP_induct_rule} |
714 val wf_in_rel = @{thm FunDef.wf_in_rel} |
720 val wf_in_rel = @{thm FunDef.wf_in_rel} |
715 val in_rel_def = @{thm FunDef.in_rel_def} |
721 val in_rel_def = @{thm FunDef.in_rel_def} |
716 |
722 |
717 fun mk_nest_term_case thy globals R' ihyp clause = |
723 fun mk_nest_term_case ctxt globals R' ihyp clause = |
718 let |
724 let |
|
725 val thy = Proof_Context.theory_of ctxt |
719 val Globals {z, ...} = globals |
726 val Globals {z, ...} = globals |
720 val ClauseInfo {cdata = ClauseContext {qs, cqs, ags, lhs, case_hyp, ...}, tree, |
727 val ClauseInfo {cdata = ClauseContext {qs, cqs, ags, lhs, case_hyp, ...}, tree, |
721 qglr=(oqs, _, _, _), ...} = clause |
728 qglr=(oqs, _, _, _), ...} = clause |
722 |
729 |
723 val ih_case = full_simplify (HOL_basic_ss addsimps [case_hyp]) ihyp |
730 val ih_case = full_simplify (put_simpset HOL_basic_ss ctxt addsimps [case_hyp]) ihyp |
724 |
731 |
725 fun step (fixes, assumes) (_ $ arg) u (sub,(hyps,thms)) = |
732 fun step (fixes, assumes) (_ $ arg) u (sub,(hyps,thms)) = |
726 let |
733 let |
727 val used = (u @ sub) |
734 val used = (u @ sub) |
728 |> map (fn (ctxt, thm) => Function_Ctx_Tree.export_thm thy ctxt thm) |
735 |> map (fn (ctxt, thm) => Function_Ctx_Tree.export_thm thy ctxt thm) |
761 in |
768 in |
762 Function_Ctx_Tree.traverse_tree step tree |
769 Function_Ctx_Tree.traverse_tree step tree |
763 end |
770 end |
764 |
771 |
765 |
772 |
766 fun mk_nest_term_rule thy globals R R_cases clauses = |
773 fun mk_nest_term_rule ctxt globals R R_cases clauses = |
767 let |
774 let |
|
775 val thy = Proof_Context.theory_of ctxt |
768 val Globals { domT, x, z, ... } = globals |
776 val Globals { domT, x, z, ... } = globals |
769 val acc_R = mk_acc domT R |
777 val acc_R = mk_acc domT R |
770 |
778 |
771 val R' = Free ("R", fastype_of R) |
779 val R' = Free ("R", fastype_of R) |
772 |
780 |
786 |
794 |
787 val ihyp_a = Thm.assume ihyp |> Thm.forall_elim_vars 0 |
795 val ihyp_a = Thm.assume ihyp |> Thm.forall_elim_vars 0 |
788 |
796 |
789 val R_z_x = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ x)) |
797 val R_z_x = cterm_of thy (HOLogic.mk_Trueprop (R $ z $ x)) |
790 |
798 |
791 val (hyps, cases) = fold (mk_nest_term_case thy globals R' ihyp_a) clauses ([], []) |
799 val (hyps, cases) = fold (mk_nest_term_case ctxt globals R' ihyp_a) clauses ([], []) |
792 in |
800 in |
793 R_cases |
801 R_cases |
794 |> Thm.forall_elim (cterm_of thy z) |
802 |> Thm.forall_elim (cterm_of thy z) |
795 |> Thm.forall_elim (cterm_of thy x) |
803 |> Thm.forall_elim (cterm_of thy x) |
796 |> Thm.forall_elim (cterm_of thy (acc_R $ z)) |
804 |> Thm.forall_elim (cterm_of thy (acc_R $ z)) |
808 |> fold Thm.implies_intr hyps |
816 |> fold Thm.implies_intr hyps |
809 |> Thm.implies_intr wfR' |
817 |> Thm.implies_intr wfR' |
810 |> Thm.forall_intr (cterm_of thy R') |
818 |> Thm.forall_intr (cterm_of thy R') |
811 |> Thm.forall_elim (cterm_of thy (inrel_R)) |
819 |> Thm.forall_elim (cterm_of thy (inrel_R)) |
812 |> curry op RS wf_in_rel |
820 |> curry op RS wf_in_rel |
813 |> full_simplify (HOL_basic_ss addsimps [in_rel_def]) |
821 |> full_simplify (put_simpset HOL_basic_ss ctxt addsimps [in_rel_def]) |
814 |> Thm.forall_intr (cterm_of thy Rrel) |
822 |> Thm.forall_intr (cterm_of thy Rrel) |
815 end |
823 end |
816 |
824 |
817 |
825 |
818 |
826 |
880 compat_store G_elim) f_defthm |
888 compat_store G_elim) f_defthm |
881 |
889 |
882 fun mk_partial_rules provedgoal = |
890 fun mk_partial_rules provedgoal = |
883 let |
891 let |
884 val newthy = theory_of_thm provedgoal (*FIXME*) |
892 val newthy = theory_of_thm provedgoal (*FIXME*) |
|
893 val newctxt = Proof_Context.init_global newthy (*FIXME*) |
885 |
894 |
886 val (graph_is_function, complete_thm) = |
895 val (graph_is_function, complete_thm) = |
887 provedgoal |
896 provedgoal |
888 |> Conjunction.elim |
897 |> Conjunction.elim |
889 |> apfst (Thm.forall_elim_vars 0) |
898 |> apfst (Thm.forall_elim_vars 0) |
890 |
899 |
891 val f_iff = graph_is_function RS (f_defthm RS ex1_implies_iff) |
900 val f_iff = graph_is_function RS (f_defthm RS ex1_implies_iff) |
892 |
901 |
893 val psimps = PROFILE "Proving simplification rules" |
902 val psimps = PROFILE "Proving simplification rules" |
894 (mk_psimps newthy globals R xclauses values f_iff) graph_is_function |
903 (mk_psimps newctxt globals R xclauses values f_iff) graph_is_function |
895 |
904 |
896 val simple_pinduct = PROFILE "Proving partial induction rule" |
905 val simple_pinduct = PROFILE "Proving partial induction rule" |
897 (mk_partial_induct_rule newthy globals R complete_thm) xclauses |
906 (mk_partial_induct_rule newthy globals R complete_thm) xclauses |
898 |
907 |
899 val total_intro = PROFILE "Proving nested termination rule" |
908 val total_intro = PROFILE "Proving nested termination rule" |
900 (mk_nest_term_rule newthy globals R R_elim) xclauses |
909 (mk_nest_term_rule newctxt globals R R_elim) xclauses |
901 |
910 |
902 val dom_intros = |
911 val dom_intros = |
903 if domintros then SOME (PROFILE "Proving domain introduction rules" |
912 if domintros then SOME (PROFILE "Proving domain introduction rules" |
904 (map (mk_domain_intro lthy globals R R_elim)) xclauses) |
913 (map (mk_domain_intro lthy globals R R_elim)) xclauses) |
905 else NONE |
914 else NONE |