928 |
928 |
929 end; |
929 end; |
930 |
930 |
931 |
931 |
932 |
932 |
933 (*** notable theorems ***) |
|
934 |
|
935 structure Thms = |
|
936 struct |
|
937 val WFREC_COROLLARY = @{thm tfl_wfrec}; |
|
938 val WF_INDUCTION_THM = @{thm tfl_wf_induct}; |
|
939 val CUT_DEF = @{thm tfl_cut_def}; |
|
940 val eqT = @{thm tfl_eq_True}; |
|
941 val rev_eq_mp = @{thm tfl_rev_eq_mp}; |
|
942 val simp_thm = @{thm tfl_simp_thm}; |
|
943 val P_imp_P_iff_True = @{thm tfl_P_imp_P_iff_True}; |
|
944 val imp_trans = @{thm tfl_imp_trans}; |
|
945 val disj_assoc = @{thm tfl_disj_assoc}; |
|
946 val tfl_disjE = @{thm tfl_disjE}; |
|
947 val choose_thm = @{thm tfl_exE}; |
|
948 end; |
|
949 |
|
950 |
|
951 |
|
952 (*** emulation of HOL inference rules for TFL ***) |
933 (*** emulation of HOL inference rules for TFL ***) |
953 |
934 |
954 structure Rules: RULES = |
935 structure Rules: RULES = |
955 struct |
936 struct |
956 |
937 |
1028 handle Utils.ERR _ => raise RULES_ERR "UNDISCH" "" |
1009 handle Utils.ERR _ => raise RULES_ERR "UNDISCH" "" |
1029 | THM _ => raise RULES_ERR "UNDISCH" ""; |
1010 | THM _ => raise RULES_ERR "UNDISCH" ""; |
1030 |
1011 |
1031 fun PROVE_HYP ath bth = MP (DISCH (cconcl ath) bth) ath; |
1012 fun PROVE_HYP ath bth = MP (DISCH (cconcl ath) bth) ath; |
1032 |
1013 |
1033 fun IMP_TRANS th1 th2 = th2 RS (th1 RS Thms.imp_trans) |
1014 fun IMP_TRANS th1 th2 = th2 RS (th1 RS @{thm tfl_imp_trans}) |
1034 handle THM (msg, _, _) => raise RULES_ERR "IMP_TRANS" msg; |
1015 handle THM (msg, _, _) => raise RULES_ERR "IMP_TRANS" msg; |
1035 |
1016 |
1036 |
1017 |
1037 (*---------------------------------------------------------------------------- |
1018 (*---------------------------------------------------------------------------- |
1038 * Conjunction |
1019 * Conjunction |
1107 val c = Dcterm.drop_prop (cconcl th1); |
1088 val c = Dcterm.drop_prop (cconcl th1); |
1108 val (disj1, disj2) = Dcterm.dest_disj c; |
1089 val (disj1, disj2) = Dcterm.dest_disj c; |
1109 val th2' = DISCH disj1 th2; |
1090 val th2' = DISCH disj1 th2; |
1110 val th3' = DISCH disj2 th3; |
1091 val th3' = DISCH disj2 th3; |
1111 in |
1092 in |
1112 th3' RS (th2' RS (th1 RS Thms.tfl_disjE)) |
1093 th3' RS (th2' RS (th1 RS @{thm tfl_disjE})) |
1113 handle THM (msg, _, _) => raise RULES_ERR "DISJ_CASES" msg |
1094 handle THM (msg, _, _) => raise RULES_ERR "DISJ_CASES" msg |
1114 end; |
1095 end; |
1115 |
1096 |
1116 |
1097 |
1117 (*----------------------------------------------------------------------------- |
1098 (*----------------------------------------------------------------------------- |
1235 val lam = #2 (Dcterm.dest_comb (Dcterm.drop_prop (cconcl exth))) |
1216 val lam = #2 (Dcterm.dest_comb (Dcterm.drop_prop (cconcl exth))) |
1236 val redex = Dcterm.capply lam fvar |
1217 val redex = Dcterm.capply lam fvar |
1237 val t$u = Thm.term_of redex |
1218 val t$u = Thm.term_of redex |
1238 val residue = Thm.cterm_of ctxt (Term.betapply (t, u)) |
1219 val residue = Thm.cterm_of ctxt (Term.betapply (t, u)) |
1239 in |
1220 in |
1240 GEN ctxt fvar (DISCH residue fact) RS (exth RS Thms.choose_thm) |
1221 GEN ctxt fvar (DISCH residue fact) RS (exth RS @{thm tfl_exE}) |
1241 handle THM (msg, _, _) => raise RULES_ERR "CHOOSE" msg |
1222 handle THM (msg, _, _) => raise RULES_ERR "CHOOSE" msg |
1242 end; |
1223 end; |
1243 |
1224 |
1244 local |
1225 local |
1245 val prop = Thm.prop_of exI |
1226 val prop = Thm.prop_of exI |
2085 | poly_tvars (TFree (a,sort)) = TVar (("?" ^ a, 0), sort) |
2066 | poly_tvars (TFree (a,sort)) = TVar (("?" ^ a, 0), sort) |
2086 | poly_tvars (TVar ((a,i),sort)) = TVar (("?" ^ a, i+1), sort); |
2067 | poly_tvars (TVar ((a,i),sort)) = TVar (("?" ^ a, i+1), sort); |
2087 |
2068 |
2088 local |
2069 local |
2089 val f_eq_wfrec_R_M = |
2070 val f_eq_wfrec_R_M = |
2090 #ant(USyntax.dest_imp(#2(USyntax.strip_forall (concl Thms.WFREC_COROLLARY)))) |
2071 #ant(USyntax.dest_imp(#2(USyntax.strip_forall (concl @{thm tfl_wfrec})))) |
2091 val {lhs=f, rhs} = USyntax.dest_eq f_eq_wfrec_R_M |
2072 val {lhs=f, rhs} = USyntax.dest_eq f_eq_wfrec_R_M |
2092 val _ = dest_Free f |
2073 val _ = dest_Free f |
2093 val (wfrec,_) = USyntax.strip_comb rhs |
2074 val (wfrec,_) = USyntax.strip_comb rhs |
2094 in |
2075 in |
2095 |
2076 |
2140 |
2121 |
2141 fun post_definition ctxt meta_tflCongs (def, pats) = |
2122 fun post_definition ctxt meta_tflCongs (def, pats) = |
2142 let val thy = Proof_Context.theory_of ctxt |
2123 let val thy = Proof_Context.theory_of ctxt |
2143 val tych = Thry.typecheck thy |
2124 val tych = Thry.typecheck thy |
2144 val f = #lhs(USyntax.dest_eq(concl def)) |
2125 val f = #lhs(USyntax.dest_eq(concl def)) |
2145 val corollary = Rules.MATCH_MP Thms.WFREC_COROLLARY def |
2126 val corollary = Rules.MATCH_MP @{thm tfl_wfrec} def |
2146 val pats' = filter given pats |
2127 val pats' = filter given pats |
2147 val given_pats = map pat_of pats' |
2128 val given_pats = map pat_of pats' |
2148 val rows = map row_of_pat pats' |
2129 val rows = map row_of_pat pats' |
2149 val WFR = #ant(USyntax.dest_imp(concl corollary)) |
2130 val WFR = #ant(USyntax.dest_imp(concl corollary)) |
2150 val R = #Rand(USyntax.dest_comb WFR) |
2131 val R = #Rand(USyntax.dest_comb WFR) |
2161 (Symtab.dest (BNF_LFP_Compat.get_all thy [BNF_LFP_Compat.Keep_Nesting])) |
2142 (Symtab.dest (BNF_LFP_Compat.get_all thy [BNF_LFP_Compat.Keep_Nesting])) |
2162 val corollaries' = map (Simplifier.simplify case_simpset) corollaries |
2143 val corollaries' = map (Simplifier.simplify case_simpset) corollaries |
2163 val extract = |
2144 val extract = |
2164 Rules.CONTEXT_REWRITE_RULE ctxt (f, [R], @{thm cut_apply}, meta_tflCongs @ context_congs) |
2145 Rules.CONTEXT_REWRITE_RULE ctxt (f, [R], @{thm cut_apply}, meta_tflCongs @ context_congs) |
2165 val (rules, TCs) = ListPair.unzip (map extract corollaries') |
2146 val (rules, TCs) = ListPair.unzip (map extract corollaries') |
2166 val rules0 = map (rewrite_rule ctxt [Thms.CUT_DEF]) rules |
2147 val rules0 = map (rewrite_rule ctxt @{thms tfl_cut_def}) rules |
2167 val mk_cond_rule = Rules.FILTER_DISCH_ALL(not o curry (op aconv) WFR) |
2148 val mk_cond_rule = Rules.FILTER_DISCH_ALL(not o curry (op aconv) WFR) |
2168 val rules1 = Rules.LIST_CONJ(map mk_cond_rule rules0) |
2149 val rules1 = Rules.LIST_CONJ(map mk_cond_rule rules0) |
2169 in |
2150 in |
2170 {rules = rules1, |
2151 {rules = rules1, |
2171 rows = rows, |
2152 rows = rows, |
2201 quote fid ^ " but found one of " ^ |
2182 quote fid ^ " but found one of " ^ |
2202 quote x) |
2183 quote x) |
2203 else () |
2184 else () |
2204 val (case_rewrites,context_congs) = extraction_thms thy |
2185 val (case_rewrites,context_congs) = extraction_thms thy |
2205 val tych = Thry.typecheck thy |
2186 val tych = Thry.typecheck thy |
2206 val WFREC_THM0 = Rules.ISPEC (tych functional) Thms.WFREC_COROLLARY |
2187 val WFREC_THM0 = Rules.ISPEC (tych functional) @{thm tfl_wfrec} |
2207 val Const(@{const_name All},_) $ Abs(Rname,Rtype,_) = concl WFREC_THM0 |
2188 val Const(@{const_name All},_) $ Abs(Rname,Rtype,_) = concl WFREC_THM0 |
2208 val R = Free (singleton (Name.variant_list (List.foldr Misc_Legacy.add_term_names [] eqns)) Rname, |
2189 val R = Free (singleton (Name.variant_list (List.foldr Misc_Legacy.add_term_names [] eqns)) Rname, |
2209 Rtype) |
2190 Rtype) |
2210 val WFREC_THM = Rules.ISPECL [tych R, tych g] WFREC_THM0 |
2191 val WFREC_THM = Rules.ISPECL [tych R, tych g] WFREC_THM0 |
2211 val ([proto_def, WFR],_) = USyntax.strip_imp(concl WFREC_THM) |
2192 val ([proto_def, WFR],_) = USyntax.strip_imp(concl WFREC_THM) |
2516 |
2497 |
2517 |
2498 |
2518 (*---------------------------------------------------------------------------- |
2499 (*---------------------------------------------------------------------------- |
2519 * Input : f, R, and [(pat1,TCs1),..., (patn,TCsn)] |
2500 * Input : f, R, and [(pat1,TCs1),..., (patn,TCsn)] |
2520 * |
2501 * |
2521 * Instantiates WF_INDUCTION_THM, getting Sinduct and then tries to prove |
2502 * Instantiates tfl_wf_induct, getting Sinduct and then tries to prove |
2522 * recursion induction (Rinduct) by proving the antecedent of Sinduct from |
2503 * recursion induction (Rinduct) by proving the antecedent of Sinduct from |
2523 * the antecedent of Rinduct. |
2504 * the antecedent of Rinduct. |
2524 *---------------------------------------------------------------------------*) |
2505 *---------------------------------------------------------------------------*) |
2525 fun mk_induction thy {fconst, R, SV, pat_TCs_list} = |
2506 fun mk_induction thy {fconst, R, SV, pat_TCs_list} = |
2526 let val ctxt = Proof_Context.init_global thy |
2507 let val ctxt = Proof_Context.init_global thy |
2527 val tych = Thry.typecheck thy |
2508 val tych = Thry.typecheck thy |
2528 val Sinduction = Rules.UNDISCH (Rules.ISPEC (tych R) Thms.WF_INDUCTION_THM) |
2509 val Sinduction = Rules.UNDISCH (Rules.ISPEC (tych R) @{thm tfl_wf_induct}) |
2529 val (pats,TCsl) = ListPair.unzip pat_TCs_list |
2510 val (pats,TCsl) = ListPair.unzip pat_TCs_list |
2530 val case_thm = complete_cases thy pats |
2511 val case_thm = complete_cases thy pats |
2531 val domain = (type_of o hd) pats |
2512 val domain = (type_of o hd) pats |
2532 val Pname = singleton (Name.variant_list (List.foldr (Library.foldr Misc_Legacy.add_term_names) |
2513 val Pname = singleton (Name.variant_list (List.foldr (Library.foldr Misc_Legacy.add_term_names) |
2533 [] (pats::TCsl))) "P" |
2514 [] (pats::TCsl))) "P" |
2621 |
2602 |
2622 (*---------------------------------------------------------------------- |
2603 (*---------------------------------------------------------------------- |
2623 * The termination condition (tc) is simplified to |- tc = tc' (there |
2604 * The termination condition (tc) is simplified to |- tc = tc' (there |
2624 * might not be a change!) and then 3 attempts are made: |
2605 * might not be a change!) and then 3 attempts are made: |
2625 * |
2606 * |
2626 * 1. if |- tc = T, then eliminate it with eqT; otherwise, |
2607 * 1. if |- tc = T, then eliminate it with tfl_eq_True; otherwise, |
2627 * 2. apply the terminator to tc'. If |- tc' = T then eliminate; else |
2608 * 2. apply the terminator to tc'. If |- tc' = T then eliminate; else |
2628 * 3. replace tc by tc' in both the rules and the induction theorem. |
2609 * 3. replace tc by tc' in both the rules and the induction theorem. |
2629 *---------------------------------------------------------------------*) |
2610 *---------------------------------------------------------------------*) |
2630 |
2611 |
2631 fun simplify_tc tc (r,ind) = |
2612 fun simplify_tc tc (r,ind) = |
2632 let val tc1 = tych tc |
2613 let val tc1 = tych tc |
2633 val _ = trace_cterm ctxt "TC before simplification: " tc1 |
2614 val _ = trace_cterm ctxt "TC before simplification: " tc1 |
2634 val tc_eq = simplifier tc1 |
2615 val tc_eq = simplifier tc1 |
2635 val _ = trace_thms ctxt "result: " [tc_eq] |
2616 val _ = trace_thms ctxt "result: " [tc_eq] |
2636 in |
2617 in |
2637 elim_tc (Rules.MATCH_MP Thms.eqT tc_eq) (r,ind) |
2618 elim_tc (Rules.MATCH_MP @{thm tfl_eq_True} tc_eq) (r,ind) |
2638 handle Utils.ERR _ => |
2619 handle Utils.ERR _ => |
2639 (elim_tc (Rules.MATCH_MP(Rules.MATCH_MP Thms.rev_eq_mp tc_eq) |
2620 (elim_tc (Rules.MATCH_MP(Rules.MATCH_MP @{thm tfl_rev_eq_mp} tc_eq) |
2640 (Rules.prove ctxt strict (HOLogic.mk_Trueprop(USyntax.rhs(concl tc_eq)), |
2621 (Rules.prove ctxt strict (HOLogic.mk_Trueprop(USyntax.rhs(concl tc_eq)), |
2641 terminator))) |
2622 terminator))) |
2642 (r,ind) |
2623 (r,ind) |
2643 handle Utils.ERR _ => |
2624 handle Utils.ERR _ => |
2644 (Rules.UNDISCH(Rules.MATCH_MP (Rules.MATCH_MP Thms.simp_thm r) tc_eq), |
2625 (Rules.UNDISCH(Rules.MATCH_MP (Rules.MATCH_MP @{thm tfl_simp_thm} r) tc_eq), |
2645 simplify_induction thy tc_eq ind)) |
2626 simplify_induction thy tc_eq ind)) |
2646 end |
2627 end |
2647 |
2628 |
2648 (*---------------------------------------------------------------------- |
2629 (*---------------------------------------------------------------------- |
2649 * Nested termination conditions are harder to get at, since they are |
2630 * Nested termination conditions are harder to get at, since they are |
2660 *---------------------------------------------------------------------*) |
2641 *---------------------------------------------------------------------*) |
2661 fun simplify_nested_tc tc = |
2642 fun simplify_nested_tc tc = |
2662 let val tc_eq = simplifier (tych (#2 (USyntax.strip_forall tc))) |
2643 let val tc_eq = simplifier (tych (#2 (USyntax.strip_forall tc))) |
2663 in |
2644 in |
2664 Rules.GEN_ALL ctxt |
2645 Rules.GEN_ALL ctxt |
2665 (Rules.MATCH_MP Thms.eqT tc_eq |
2646 (Rules.MATCH_MP @{thm tfl_eq_True} tc_eq |
2666 handle Utils.ERR _ => |
2647 handle Utils.ERR _ => |
2667 (Rules.MATCH_MP(Rules.MATCH_MP Thms.rev_eq_mp tc_eq) |
2648 (Rules.MATCH_MP(Rules.MATCH_MP @{thm tfl_rev_eq_mp} tc_eq) |
2668 (Rules.prove ctxt strict (HOLogic.mk_Trueprop (USyntax.rhs(concl tc_eq)), |
2649 (Rules.prove ctxt strict (HOLogic.mk_Trueprop (USyntax.rhs(concl tc_eq)), |
2669 terminator)) |
2650 terminator)) |
2670 handle Utils.ERR _ => tc_eq)) |
2651 handle Utils.ERR _ => tc_eq)) |
2671 end |
2652 end |
2672 |
2653 |