src/HOL/Nominal/nominal_inductive2.ML
changeset 59582 0fbed69ff081
parent 59498 50b60f501b05
child 59621 291934bac95e
equal deleted inserted replaced
59580:cbc38731d42f 59582:0fbed69ff081
    36 fun preds_of ps t = inter (op = o apsnd dest_Free) ps (Term.add_frees t []);
    36 fun preds_of ps t = inter (op = o apsnd dest_Free) ps (Term.add_frees t []);
    37 
    37 
    38 val perm_bool = mk_meta_eq @{thm perm_bool_def};
    38 val perm_bool = mk_meta_eq @{thm perm_bool_def};
    39 val perm_boolI = @{thm perm_boolI};
    39 val perm_boolI = @{thm perm_boolI};
    40 val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb
    40 val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb
    41   (Drule.strip_imp_concl (cprop_of perm_boolI))));
    41   (Drule.strip_imp_concl (Thm.cprop_of perm_boolI))));
    42 
    42 
    43 fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    43 fun mk_perm_bool pi th = th RS Drule.cterm_instantiate
    44   [(perm_boolI_pi, pi)] perm_boolI;
    44   [(perm_boolI_pi, pi)] perm_boolI;
    45 
    45 
    46 fun mk_perm_bool_simproc names = Simplifier.simproc_global_i
    46 fun mk_perm_bool_simproc names = Simplifier.simproc_global_i
    47   (theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn ctxt =>
    47   (Thm.theory_of_thm perm_bool) "perm_bool" [@{term "perm pi x"}] (fn ctxt =>
    48     fn Const (@{const_name Nominal.perm}, _) $ _ $ t =>
    48     fn Const (@{const_name Nominal.perm}, _) $ _ $ t =>
    49          if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t))
    49          if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t))
    50          then SOME perm_bool else NONE
    50          then SOME perm_bool else NONE
    51      | _ => NONE);
    51      | _ => NONE);
    52 
    52 
   129 (*         Prove  F[f t]  from  F[t],  where F is monotone           *)
   129 (*         Prove  F[f t]  from  F[t],  where F is monotone           *)
   130 (*********************************************************************)
   130 (*********************************************************************)
   131 
   131 
   132 fun map_thm ctxt f tac monos opt th =
   132 fun map_thm ctxt f tac monos opt th =
   133   let
   133   let
   134     val prop = prop_of th;
   134     val prop = Thm.prop_of th;
   135     fun prove t =
   135     fun prove t =
   136       Goal.prove ctxt [] [] t (fn _ =>
   136       Goal.prove ctxt [] [] t (fn _ =>
   137         EVERY [cut_facts_tac [th] 1, etac rev_mp 1,
   137         EVERY [cut_facts_tac [th] 1, etac rev_mp 1,
   138           REPEAT_DETERM (FIRSTGOAL (resolve_tac ctxt monos)),
   138           REPEAT_DETERM (FIRSTGOAL (resolve_tac ctxt monos)),
   139           REPEAT_DETERM (rtac impI 1 THEN (atac 1 ORELSE tac))])
   139           REPEAT_DETERM (rtac impI 1 THEN (atac 1 ORELSE tac))])
   142 fun abs_params params t =
   142 fun abs_params params t =
   143   let val vs =  map (Var o apfst (rpair 0)) (Term.rename_wrt_term t params)
   143   let val vs =  map (Var o apfst (rpair 0)) (Term.rename_wrt_term t params)
   144   in (Logic.list_all (params, t), (rev vs, subst_bounds (vs, t))) end;
   144   in (Logic.list_all (params, t), (rev vs, subst_bounds (vs, t))) end;
   145 
   145 
   146 fun inst_params thy (vs, p) th cts =
   146 fun inst_params thy (vs, p) th cts =
   147   let val env = Pattern.first_order_match thy (p, prop_of th)
   147   let val env = Pattern.first_order_match thy (p, Thm.prop_of th)
   148     (Vartab.empty, Vartab.empty)
   148     (Vartab.empty, Vartab.empty)
   149   in Thm.instantiate ([],
   149   in Thm.instantiate ([],
   150     map (Envir.subst_term env #> cterm_of thy) vs ~~ cts) th
   150     map (Envir.subst_term env #> Thm.cterm_of thy) vs ~~ cts) th
   151   end;
   151   end;
   152 
   152 
   153 fun prove_strong_ind s alt_name avoids ctxt =
   153 fun prove_strong_ind s alt_name avoids ctxt =
   154   let
   154   let
   155     val thy = Proof_Context.theory_of ctxt;
   155     val thy = Proof_Context.theory_of ctxt;
   166           commas_quote xs));
   166           commas_quote xs));
   167     val induct_cases = map (fst o fst) (fst (Rule_Cases.get (the
   167     val induct_cases = map (fst o fst) (fst (Rule_Cases.get (the
   168       (Induct.lookup_inductP ctxt (hd names)))));
   168       (Induct.lookup_inductP ctxt (hd names)))));
   169     val induct_cases' = if null induct_cases then replicate (length intrs) ""
   169     val induct_cases' = if null induct_cases then replicate (length intrs) ""
   170       else induct_cases;
   170       else induct_cases;
   171     val ([raw_induct'], ctxt') = Variable.import_terms false [prop_of raw_induct] ctxt;
   171     val ([raw_induct'], ctxt') = Variable.import_terms false [Thm.prop_of raw_induct] ctxt;
   172     val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |>
   172     val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |>
   173       HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb);
   173       HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb);
   174     val ps = map (fst o snd) concls;
   174     val ps = map (fst o snd) concls;
   175 
   175 
   176     val _ = (case duplicates (op = o apply2 fst) avoids of
   176     val _ = (case duplicates (op = o apply2 fst) avoids of
   228     val (fs_ctxt_tyname, _) = Name.variant "'n" (Variable.names_of ctxt');
   228     val (fs_ctxt_tyname, _) = Name.variant "'n" (Variable.names_of ctxt');
   229     val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt';
   229     val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt';
   230     val fsT = TFree (fs_ctxt_tyname, ind_sort);
   230     val fsT = TFree (fs_ctxt_tyname, ind_sort);
   231 
   231 
   232     val inductive_forall_def' = Drule.instantiate'
   232     val inductive_forall_def' = Drule.instantiate'
   233       [SOME (ctyp_of thy fsT)] [] inductive_forall_def;
   233       [SOME (Thm.ctyp_of thy fsT)] [] inductive_forall_def;
   234 
   234 
   235     fun lift_pred' t (Free (s, T)) ts =
   235     fun lift_pred' t (Free (s, T)) ts =
   236       list_comb (Free (s, fsT --> T), t :: ts);
   236       list_comb (Free (s, fsT --> T), t :: ts);
   237     val lift_pred = lift_pred' (Bound 0);
   237     val lift_pred = lift_pred' (Bound 0);
   238 
   238 
   317         val atom = fst (dest_Type T);
   317         val atom = fst (dest_Type T);
   318         val {at_inst, ...} = NominalAtoms.the_atom_info thy atom;
   318         val {at_inst, ...} = NominalAtoms.the_atom_info thy atom;
   319         val fs_atom = Global_Theory.get_thm thy
   319         val fs_atom = Global_Theory.get_thm thy
   320           ("fs_" ^ Long_Name.base_name atom ^ "1");
   320           ("fs_" ^ Long_Name.base_name atom ^ "1");
   321         val avoid_th = Drule.instantiate'
   321         val avoid_th = Drule.instantiate'
   322           [SOME (ctyp_of thy (fastype_of p))] [SOME (cterm_of thy p)]
   322           [SOME (Thm.ctyp_of thy (fastype_of p))] [SOME (Thm.cterm_of thy p)]
   323           ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding});
   323           ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding});
   324         val (([(_, cx)], th1 :: th2 :: ths), ctxt') = Obtain.result
   324         val (([(_, cx)], th1 :: th2 :: ths), ctxt') = Obtain.result
   325           (fn ctxt' => EVERY
   325           (fn ctxt' => EVERY
   326             [rtac avoid_th 1,
   326             [rtac avoid_th 1,
   327              full_simp_tac (put_simpset HOL_ss ctxt' addsimps [@{thm fresh_star_prod_set}]) 1,
   327              full_simp_tac (put_simpset HOL_ss ctxt' addsimps [@{thm fresh_star_prod_set}]) 1,
   331           [] ctxt;
   331           [] ctxt;
   332         val (Ts1, _ :: Ts2) = take_prefix (not o equal T) (map snd sets);
   332         val (Ts1, _ :: Ts2) = take_prefix (not o equal T) (map snd sets);
   333         val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2);
   333         val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2);
   334         val (pis1, pis2) = chop (length Ts1)
   334         val (pis1, pis2) = chop (length Ts1)
   335           (map Bound (length pTs - 1 downto 0));
   335           (map Bound (length pTs - 1 downto 0));
   336         val _ $ (f $ (_ $ pi $ l) $ r) = prop_of th2
   336         val _ $ (f $ (_ $ pi $ l) $ r) = Thm.prop_of th2
   337         val th2' =
   337         val th2' =
   338           Goal.prove ctxt' [] []
   338           Goal.prove ctxt' [] []
   339             (Logic.list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop
   339             (Logic.list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop
   340                (f $ fold_rev (NominalDatatype.mk_perm (rev pTs))
   340                (f $ fold_rev (NominalDatatype.mk_perm (rev pTs))
   341                   (pis1 @ pi :: pis2) l $ r)))
   341                   (pis1 @ pi :: pis2) l $ r)))
   342             (fn _ => cut_facts_tac [th2] 1 THEN
   342             (fn _ => cut_facts_tac [th2] 1 THEN
   343                full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps perm_set_forget) 1) |>
   343                full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps perm_set_forget) 1) |>
   344           Simplifier.simplify (put_simpset eqvt_ss ctxt')
   344           Simplifier.simplify (put_simpset eqvt_ss ctxt')
   345       in
   345       in
   346         (freshs @ [term_of cx],
   346         (freshs @ [Thm.term_of cx],
   347          ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt')
   347          ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt')
   348       end;
   348       end;
   349 
   349 
   350     fun mk_ind_proof ctxt' thss =
   350     fun mk_ind_proof ctxt' thss =
   351       Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   351       Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} =>
   356             [REPEAT (rtac allI 1), simp_tac (put_simpset eqvt_ss context) 1,
   356             [REPEAT (rtac allI 1), simp_tac (put_simpset eqvt_ss context) 1,
   357              SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   357              SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} =>
   358                let
   358                let
   359                  val (cparams', (pis, z)) =
   359                  val (cparams', (pis, z)) =
   360                    chop (length params - length atomTs - 1) (map #2 params) ||>
   360                    chop (length params - length atomTs - 1) (map #2 params) ||>
   361                    (map term_of #> split_last);
   361                    (map Thm.term_of #> split_last);
   362                  val params' = map term_of cparams'
   362                  val params' = map Thm.term_of cparams'
   363                  val sets' = map (apfst (curry subst_bounds (rev params'))) sets;
   363                  val sets' = map (apfst (curry subst_bounds (rev params'))) sets;
   364                  val pi_sets = map (fn (t, _) =>
   364                  val pi_sets = map (fn (t, _) =>
   365                    fold_rev (NominalDatatype.mk_perm []) pis t) sets';
   365                    fold_rev (NominalDatatype.mk_perm []) pis t) sets';
   366                  val (P, ts) = strip_comb (HOLogic.dest_Trueprop (term_of concl));
   366                  val (P, ts) = strip_comb (HOLogic.dest_Trueprop (Thm.term_of concl));
   367                  val gprems1 = map_filter (fn (th, t) =>
   367                  val gprems1 = map_filter (fn (th, t) =>
   368                    if null (preds_of ps t) then SOME th
   368                    if null (preds_of ps t) then SOME th
   369                    else
   369                    else
   370                      map_thm ctxt' (split_conj (K o I) names)
   370                      map_thm ctxt' (split_conj (K o I) names)
   371                        (etac conjunct1 1) monos NONE th)
   371                        (etac conjunct1 1) monos NONE th)
   372                    (gprems ~~ oprems);
   372                    (gprems ~~ oprems);
   373                  val vc_compat_ths' = map2 (fn th => fn p =>
   373                  val vc_compat_ths' = map2 (fn th => fn p =>
   374                    let
   374                    let
   375                      val th' = gprems1 MRS inst_params thy p th cparams';
   375                      val th' = gprems1 MRS inst_params thy p th cparams';
   376                      val (h, ts) =
   376                      val (h, ts) =
   377                        strip_comb (HOLogic.dest_Trueprop (concl_of th'))
   377                        strip_comb (HOLogic.dest_Trueprop (Thm.concl_of th'))
   378                    in
   378                    in
   379                      Goal.prove ctxt' [] []
   379                      Goal.prove ctxt' [] []
   380                        (HOLogic.mk_Trueprop (list_comb (h,
   380                        (HOLogic.mk_Trueprop (list_comb (h,
   381                           map (fold_rev (NominalDatatype.mk_perm []) pis) ts)))
   381                           map (fold_rev (NominalDatatype.mk_perm []) pis) ts)))
   382                        (fn _ => simp_tac (put_simpset HOL_basic_ss ctxt' addsimps
   382                        (fn _ => simp_tac (put_simpset HOL_basic_ss ctxt' addsimps
   397                      else pi2
   397                      else pi2
   398                    end;
   398                    end;
   399                  val pis'' = fold_rev (concat_perm #> map) pis' pis;
   399                  val pis'' = fold_rev (concat_perm #> map) pis' pis;
   400                  val ihyp' = inst_params thy vs_ihypt ihyp
   400                  val ihyp' = inst_params thy vs_ihypt ihyp
   401                    (map (fold_rev (NominalDatatype.mk_perm [])
   401                    (map (fold_rev (NominalDatatype.mk_perm [])
   402                       (pis' @ pis) #> cterm_of thy) params' @ [cterm_of thy z]);
   402                       (pis' @ pis) #> Thm.cterm_of thy) params' @ [Thm.cterm_of thy z]);
   403                  fun mk_pi th =
   403                  fun mk_pi th =
   404                    Simplifier.simplify (put_simpset HOL_basic_ss ctxt' addsimps [@{thm id_apply}]
   404                    Simplifier.simplify (put_simpset HOL_basic_ss ctxt' addsimps [@{thm id_apply}]
   405                        addsimprocs [NominalDatatype.perm_simproc])
   405                        addsimprocs [NominalDatatype.perm_simproc])
   406                      (Simplifier.simplify (put_simpset eqvt_ss ctxt')
   406                      (Simplifier.simplify (put_simpset eqvt_ss ctxt')
   407                        (fold_rev (mk_perm_bool o cterm_of thy)
   407                        (fold_rev (mk_perm_bool o Thm.cterm_of thy)
   408                          (pis' @ pis) th));
   408                          (pis' @ pis) th));
   409                  val gprems2 = map (fn (th, t) =>
   409                  val gprems2 = map (fn (th, t) =>
   410                    if null (preds_of ps t) then mk_pi th
   410                    if null (preds_of ps t) then mk_pi th
   411                    else
   411                    else
   412                      mk_pi (the (map_thm ctxt' (inst_conj_all names ps (rev pis''))
   412                      mk_pi (the (map_thm ctxt' (inst_conj_all names ps (rev pis''))
   423                      [REPEAT_DETERM_N (length gprems)
   423                      [REPEAT_DETERM_N (length gprems)
   424                        (simp_tac (put_simpset HOL_basic_ss ctxt''
   424                        (simp_tac (put_simpset HOL_basic_ss ctxt''
   425                           addsimps [inductive_forall_def']
   425                           addsimps [inductive_forall_def']
   426                           addsimprocs [NominalDatatype.perm_simproc]) 1 THEN
   426                           addsimprocs [NominalDatatype.perm_simproc]) 1 THEN
   427                         resolve_tac ctxt'' gprems2 1)]));
   427                         resolve_tac ctxt'' gprems2 1)]));
   428                  val final = Goal.prove ctxt'' [] [] (term_of concl)
   428                  val final = Goal.prove ctxt'' [] [] (Thm.term_of concl)
   429                    (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (put_simpset HOL_ss ctxt''
   429                    (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (put_simpset HOL_ss ctxt''
   430                      addsimps vc_compat_ths1' @ fresh_ths1 @
   430                      addsimps vc_compat_ths1' @ fresh_ths1 @
   431                        perm_freshs_freshs') 1);
   431                        perm_freshs_freshs') 1);
   432                  val final' = Proof_Context.export ctxt'' ctxt' [final];
   432                  val final' = Proof_Context.export ctxt'' ctxt' [final];
   433                in resolve_tac ctxt' final' 1 end) context 1])
   433                in resolve_tac ctxt' final' 1 end) context 1])