src/HOL/Tools/Function/function_core.ML
changeset 51717 9e7d1c139569
parent 49170 03bee3a6a1b7
child 52223 5bb6ae8acb87
equal deleted inserted replaced
51709:19b47bfac6ef 51717:9e7d1c139569
   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