src/HOL/Library/old_recdef.ML
changeset 60522 1409b4015671
parent 60521 52e956416fbf
child 60523 be2d9f5ddc76
equal deleted inserted replaced
60521:52e956416fbf 60522:1409b4015671
   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
  1310 
  1291 
  1311 fun simpl_conv ctxt thl ctm =
  1292 fun simpl_conv ctxt thl ctm =
  1312  rew_conv (ctxt addsimps thl) ctm RS meta_eq_to_obj_eq;
  1293  rew_conv (ctxt addsimps thl) ctm RS meta_eq_to_obj_eq;
  1313 
  1294 
  1314 
  1295 
  1315 fun RIGHT_ASSOC ctxt = rewrite_rule ctxt [Thms.disj_assoc];
  1296 fun RIGHT_ASSOC ctxt = rewrite_rule ctxt @{thms tfl_disj_assoc};
  1316 
  1297 
  1317 
  1298 
  1318 
  1299 
  1319 (*---------------------------------------------------------------------------
  1300 (*---------------------------------------------------------------------------
  1320  *                  TERMINATION CONDITION EXTRACTION
  1301  *                  TERMINATION CONDITION EXTRACTION
  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"
  2578       fun loop [] = ind
  2559       fun loop [] = ind
  2579         | loop (asm::rst) =
  2560         | loop (asm::rst) =
  2580           if (can (Thry.match_term thy asm) tc)
  2561           if (can (Thry.match_term thy asm) tc)
  2581           then Rules.UNDISCH
  2562           then Rules.UNDISCH
  2582                  (Rules.MATCH_MP
  2563                  (Rules.MATCH_MP
  2583                      (Rules.MATCH_MP Thms.simp_thm (Rules.DISCH (tych asm) ind))
  2564                      (Rules.MATCH_MP @{thm tfl_simp_thm} (Rules.DISCH (tych asm) ind))
  2584                      hth)
  2565                      hth)
  2585          else loop rst
  2566          else loop rst
  2586   in loop asl
  2567   in loop asl
  2587 end;
  2568 end;
  2588 
  2569 
  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