Nominal/nominal_inductive.ML
changeset 3239 67370521c09c
parent 3231 188826f1ccdb
child 3243 c4f31f1564b7
equal deleted inserted replaced
3238:b2e1a7b83e05 3239:67370521c09c
    33 (* fixme: move to nominal_library *)
    33 (* fixme: move to nominal_library *)
    34 fun real_head_of (@{term Trueprop} $ t) = real_head_of t
    34 fun real_head_of (@{term Trueprop} $ t) = real_head_of t
    35   | real_head_of (Const (@{const_name Pure.imp}, _) $ _ $ t) = real_head_of t
    35   | real_head_of (Const (@{const_name Pure.imp}, _) $ _ $ t) = real_head_of t
    36   | real_head_of (Const (@{const_name Pure.all}, _) $ Abs (_, _, t)) = real_head_of t
    36   | real_head_of (Const (@{const_name Pure.all}, _) $ Abs (_, _, t)) = real_head_of t
    37   | real_head_of (Const (@{const_name All}, _) $ Abs (_, _, t)) = real_head_of t
    37   | real_head_of (Const (@{const_name All}, _) $ Abs (_, _, t)) = real_head_of t
    38   | real_head_of (Const ("HOL.induct_forall", _) $ Abs (_, _, t)) = real_head_of t
    38   | real_head_of (Const (@{const_name HOL.induct_forall}, _) $ Abs (_, _, t)) = real_head_of t
    39   | real_head_of t = head_of t
    39   | real_head_of t = head_of t
    40 
    40 
    41 
    41 
    42 fun mk_vc_compat (avoid, avoid_trm) prems concl_args params =
    42 fun mk_vc_compat (avoid, avoid_trm) prems concl_args params =
    43   if null avoid then
    43   if null avoid then
    79     |> (fn t => HOLogic.all_const c_ty $ lambda c t )
    79     |> (fn t => HOLogic.all_const c_ty $ lambda c t )
    80     |> (fn t => HOLogic.all_const @{typ perm} $  lambda p t)
    80     |> (fn t => HOLogic.all_const @{typ perm} $  lambda p t)
    81   end
    81   end
    82 
    82 
    83 fun induct_forall_const T =
    83 fun induct_forall_const T =
    84   Const ("HOL.induct_forall", (T --> @{typ bool}) --> @{typ bool})
    84   Const (@{const_name HOL.induct_forall}, (T --> @{typ bool}) --> @{typ bool})
    85 
    85 
    86 fun mk_induct_forall (a, T) t =
    86 fun mk_induct_forall (a, T) t =
    87   induct_forall_const T $ Abs (a, T, t)
    87   induct_forall_const T $ Abs (a, T, t)
    88 
    88 
    89 fun add_c_prop qnt Ps (c, c_name, c_ty) trm =
    89 fun add_c_prop qnt Ps (c, c_name, c_ty) trm =
   154 end
   154 end
   155 
   155 
   156 val all_elims = 
   156 val all_elims = 
   157   let
   157   let
   158     fun spec' ct =
   158     fun spec' ct =
   159       Drule.instantiate' [SOME (ctyp_of_term ct)] [NONE, SOME ct] @{thm spec}
   159       Drule.instantiate' [SOME (Thm.ctyp_of_cterm ct)] [NONE, SOME ct] @{thm spec}
   160   in
   160   in
   161     fold (fn ct => fn th => th RS spec' ct)
   161     fold (fn ct => fn th => th RS spec' ct)
   162   end
   162   end
   163 
   163 
   164 fun helper_tac flag prm p ctxt =
   164 fun helper_tac flag prm p ctxt =
   170 
   170 
   171       val prm' = (prems' MRS prm)
   171       val prm' = (prems' MRS prm)
   172         |> flag ? (all_elims [p])
   172         |> flag ? (all_elims [p])
   173         |> flag ? (eqvt_srule context)
   173         |> flag ? (eqvt_srule context)
   174     in
   174     in
   175       asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps (prm' :: @{thms induct_forall_def})) 1
   175       asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps (prm' :: @{thms HOL.induct_forall_def})) 1
   176     end) ctxt
   176     end) ctxt
   177 
   177 
   178 fun non_binder_tac prem intr_cvars Ps ctxt = 
   178 fun non_binder_tac prem intr_cvars Ps ctxt = 
   179   Subgoal.SUBPROOF (fn {context, params, prems, ...} =>
   179   Subgoal.SUBPROOF (fn {context = ctxt', params, prems, ...} =>
   180     let
   180     let
   181       val thy = Proof_Context.theory_of context
       
   182       val (prms, p, _) = split_last2 (map snd params)
   181       val (prms, p, _) = split_last2 (map snd params)
   183       val prm_tys = map (fastype_of o term_of) prms
   182       val prm_tys = map (fastype_of o Thm.term_of) prms
   184       val cperms = map (cterm_of thy o perm_const) prm_tys
   183       val cperms = map (Thm.cterm_of ctxt' o perm_const) prm_tys
   185       val p_prms = map2 (fn ct1 => fn ct2 => Thm.mk_binop ct1 p ct2) cperms prms 
   184       val p_prms = map2 (fn ct1 => fn ct2 => Thm.mk_binop ct1 p ct2) cperms prms 
   186       val prem' = prem
   185       val prem' = prem
   187         |> cterm_instantiate (intr_cvars ~~ p_prms) 
   186         |> cterm_instantiate (intr_cvars ~~ p_prms) 
   188         |> eqvt_srule ctxt
   187         |> eqvt_srule ctxt
   189 
   188 
   190       (* for inductive-premises*)
   189       (* for inductive-premises*)
   191       fun tac1 prm = helper_tac true prm p context 
   190       fun tac1 prm = helper_tac true prm p ctxt'
   192 
   191 
   193       (* for non-inductive premises *)   
   192       (* for non-inductive premises *)   
   194       fun tac2 prm =  
   193       fun tac2 prm =  
   195         EVERY' [ minus_permute_intro_tac p, 
   194         EVERY' [ minus_permute_intro_tac p, 
   196                  eqvt_stac context, 
   195                  eqvt_stac ctxt', 
   197                  helper_tac false prm p context ]
   196                  helper_tac false prm p ctxt' ]
   198 
   197 
   199       fun select prm (t, i) =
   198       fun select prm (t, i) =
   200         (if member same_name Ps (real_head_of t) then tac1 prm else tac2 prm) i
   199         (if member same_name Ps (real_head_of t) then tac1 prm else tac2 prm) i
   201     in
   200     in
   202       EVERY1 [ eqvt_stac context, 
   201       EVERY1 [ eqvt_stac ctxt', 
   203                rtac prem', 
   202                rtac prem', 
   204                RANGE (map (SUBGOAL o select) prems) ]
   203                RANGE (map (SUBGOAL o select) prems) ]
   205     end) ctxt
   204     end) ctxt
   206 
   205 
   207 fun fresh_thm ctxt user_thm p c concl_args avoid_trm =
   206 fun fresh_thm ctxt user_thm p c concl_args avoid_trm =
   230 
   229 
   231 
   230 
   232 fun binder_tac prem intr_cvars param_trms Ps user_thm avoid_trm concl_args ctxt = 
   231 fun binder_tac prem intr_cvars param_trms Ps user_thm avoid_trm concl_args ctxt = 
   233   Subgoal.FOCUS (fn {context = ctxt, params, prems, concl, ...} =>
   232   Subgoal.FOCUS (fn {context = ctxt, params, prems, concl, ...} =>
   234     let
   233     let
   235       val thy = Proof_Context.theory_of ctxt
       
   236       val (prms, p, c) = split_last2 (map snd params)
   234       val (prms, p, c) = split_last2 (map snd params)
   237       val prm_trms = map term_of prms
   235       val prm_trms = map Thm.term_of prms
   238       val prm_tys = map fastype_of prm_trms
   236       val prm_tys = map fastype_of prm_trms
   239 
   237 
   240       val avoid_trm' = subst_free (param_trms ~~ prm_trms) avoid_trm 
   238       val avoid_trm' = subst_free (param_trms ~~ prm_trms) avoid_trm 
   241       val concl_args' = map (subst_free (param_trms ~~ prm_trms)) concl_args 
   239       val concl_args' = map (subst_free (param_trms ~~ prm_trms)) concl_args 
   242       
   240       
   243       val user_thm' = map (cterm_instantiate (intr_cvars ~~ prms)) user_thm
   241       val user_thm' = map (cterm_instantiate (intr_cvars ~~ prms)) user_thm
   244         |> map (full_simplify (put_simpset HOL_ss ctxt addsimps (@{thm fresh_star_Pair}::prems)))
   242         |> map (full_simplify (put_simpset HOL_ss ctxt addsimps (@{thm fresh_star_Pair}::prems)))
   245       
   243       
   246       val fthm = fresh_thm ctxt user_thm' (term_of p) (term_of c) concl_args' avoid_trm'
   244       val fthm = fresh_thm ctxt user_thm' (Thm.term_of p) (Thm.term_of c) concl_args' avoid_trm'
   247 
   245 
   248       val (([(_, q)], fprop :: fresh_eqs), ctxt') = Obtain.result
   246       val (([(_, q)], fprop :: fresh_eqs), ctxt') = Obtain.result
   249               (K (EVERY1 [etac @{thm exE}, 
   247               (K (EVERY1 [etac @{thm exE}, 
   250                           full_simp_tac (put_simpset HOL_basic_ss ctxt
   248                           full_simp_tac (put_simpset HOL_basic_ss ctxt
   251                             addsimps @{thms supp_Pair fresh_star_Un}),
   249                             addsimps @{thms supp_Pair fresh_star_Un}),
   254                           REPEAT o dtac supp_perm_eq'])) [fthm] ctxt 
   252                           REPEAT o dtac supp_perm_eq'])) [fthm] ctxt 
   255 
   253 
   256       val expand_conv = Conv.try_conv (Conv.rewrs_conv fresh_eqs)
   254       val expand_conv = Conv.try_conv (Conv.rewrs_conv fresh_eqs)
   257       fun expand_conv_bot ctxt = Conv.bottom_conv (K expand_conv) ctxt
   255       fun expand_conv_bot ctxt = Conv.bottom_conv (K expand_conv) ctxt
   258 
   256 
   259       val cperms = map (cterm_of thy o perm_const) prm_tys
   257       val cperms = map (Thm.cterm_of ctxt o perm_const) prm_tys
   260       val qp_prms = map2 (fn ct1 => fn ct2 => Thm.mk_binop ct1 (mk_cplus q p) ct2) cperms prms 
   258       val qp_prms = map2 (fn ct1 => fn ct2 => Thm.mk_binop ct1 (mk_cplus q p) ct2) cperms prms 
   261       val prem' = prem
   259       val prem' = prem
   262         |> cterm_instantiate (intr_cvars ~~ qp_prms)
   260         |> cterm_instantiate (intr_cvars ~~ qp_prms)
   263         |> eqvt_srule ctxt
   261         |> eqvt_srule ctxt
   264 
   262 
   275                  helper_tac false prm (mk_cplus q p) ctxt' ]
   273                  helper_tac false prm (mk_cplus q p) ctxt' ]
   276 
   274 
   277       fun select prm (t, i) =
   275       fun select prm (t, i) =
   278         (if member same_name Ps (real_head_of t) then tac1 prm else tac2 prm) i
   276         (if member same_name Ps (real_head_of t) then tac1 prm else tac2 prm) i
   279 
   277 
   280       val side_thm = Goal.prove ctxt' [] [] (term_of concl)
   278       val side_thm = Goal.prove ctxt' [] [] (Thm.term_of concl)
   281         (fn {context, ...} => 
   279         (fn {context = ctxt'', ...} => 
   282            EVERY1 [ CONVERSION (expand_conv_bot context),
   280            EVERY1 [ CONVERSION (expand_conv_bot ctxt''),
   283                     eqvt_stac context,
   281                     eqvt_stac ctxt'',
   284                     rtac prem',
   282                     rtac prem',
   285                     RANGE (tac_fresh :: map (SUBGOAL o select) prems) ])
   283                     RANGE (tac_fresh :: map (SUBGOAL o select) prems) ])
   286         |> singleton (Proof_Context.export ctxt' ctxt)        
   284         |> singleton (Proof_Context.export ctxt' ctxt)
   287     in
   285     in
   288       rtac side_thm 1
   286       rtac side_thm 1
   289     end) ctxt
   287     end) ctxt
   290 
   288 
   291 fun case_tac ctxt Ps avoid avoid_trm intr_cvars param_trms prem user_thm concl_args =
   289 fun case_tac ctxt Ps avoid avoid_trm intr_cvars param_trms prem user_thm concl_args =
   308 
   306 
   309 val normalise = @{lemma "(Q --> (!p c. P p c)) ==> (!!c. Q ==> P (0::perm) c)" by simp}
   307 val normalise = @{lemma "(Q --> (!p c. P p c)) ==> (!!c. Q ==> P (0::perm) c)" by simp}
   310 
   308 
   311 fun prove_strong_inductive pred_names rule_names avoids raw_induct intrs ctxt =
   309 fun prove_strong_inductive pred_names rule_names avoids raw_induct intrs ctxt =
   312   let
   310   let
   313     val thy = Proof_Context.theory_of ctxt
       
   314     val ((_, [raw_induct']), ctxt') = Variable.import true [raw_induct] ctxt
   311     val ((_, [raw_induct']), ctxt') = Variable.import true [raw_induct] ctxt
   315 
   312 
   316     val (ind_prems, ind_concl) = raw_induct'
   313     val (ind_prems, ind_concl) = raw_induct'
   317       |> prop_of
   314       |> Thm.prop_of
   318       |> Logic.strip_horn
   315       |> Logic.strip_horn
   319       |>> map strip_full_horn
   316       |>> map strip_full_horn
   320     val params = map (fn (x, _, _) => x) ind_prems
   317     val params = map (fn (x, _, _) => x) ind_prems
   321     val param_trms = (map o map) Free params  
   318     val param_trms = (map o map) Free params  
   322 
   319 
   323     val intr_vars_tys = map (fn t => rev (Term.add_vars (prop_of t) [])) intrs
   320     val intr_vars_tys = map (fn t => rev (Term.add_vars (Thm.prop_of t) [])) intrs
   324     val intr_vars = (map o map) fst intr_vars_tys
   321     val intr_vars = (map o map) fst intr_vars_tys
   325     val intr_vars_substs = map2 (curry (op ~~)) intr_vars param_trms
   322     val intr_vars_substs = map2 (curry (op ~~)) intr_vars param_trms
   326     val intr_cvars = (map o map) (cterm_of thy o Var) intr_vars_tys      
   323     val intr_cvars = (map o map) (Thm.cterm_of ctxt o Var) intr_vars_tys
   327 
   324 
   328     val (intr_prems, intr_concls) = intrs
   325     val (intr_prems, intr_concls) = intrs
   329       |> map prop_of
   326       |> map Thm.prop_of
   330       |> map2 subst_Vars intr_vars_substs
   327       |> map2 subst_Vars intr_vars_substs
   331       |> map Logic.strip_horn
   328       |> map Logic.strip_horn
   332       |> split_list
   329       |> split_list
   333 
   330 
   334     val intr_concls_args =
   331     val intr_concls_args =
   367     fun after_qed ctxt_outside user_thms ctxt = 
   364     fun after_qed ctxt_outside user_thms ctxt = 
   368       let
   365       let
   369         val strong_ind_thms = Goal.prove ctxt [] ind_prems' ind_concl' 
   366         val strong_ind_thms = Goal.prove ctxt [] ind_prems' ind_concl' 
   370         (prove_sinduct_tac raw_induct user_thms Ps avoids avoid_trms intr_cvars param_trms intr_concls_args) 
   367         (prove_sinduct_tac raw_induct user_thms Ps avoids avoid_trms intr_cvars param_trms intr_concls_args) 
   371           |> singleton (Proof_Context.export ctxt ctxt_outside)
   368           |> singleton (Proof_Context.export ctxt ctxt_outside)
   372           |> Datatype_Aux.split_conj_thm
   369           |> Old_Datatype_Aux.split_conj_thm
   373           |> map (fn thm => thm RS normalise)
   370           |> map (fn thm => thm RS normalise)
   374           |> map (asm_full_simplify (put_simpset HOL_basic_ss ctxt
   371           |> map (asm_full_simplify (put_simpset HOL_basic_ss ctxt
   375               addsimps @{thms permute_zero induct_rulify})) 
   372               addsimps @{thms permute_zero induct_rulify})) 
   376           |> map (Drule.rotate_prems (length ind_prems'))
   373           |> map (Drule.rotate_prems (length ind_prems'))
   377           |> map zero_var_indexes
   374           |> map zero_var_indexes
   415 
   412 
   416     fun read_avoids avoid_trms intr =
   413     fun read_avoids avoid_trms intr =
   417       let
   414       let
   418         (* fixme hack *)
   415         (* fixme hack *)
   419         val (((_, ctrms), _), ctxt') = Variable.import true [intr] ctxt
   416         val (((_, ctrms), _), ctxt') = Variable.import true [intr] ctxt
   420         val trms = map (term_of o snd) ctrms
   417         val trms = map (Thm.term_of o snd) ctrms
   421         val ctxt'' = fold Variable.declare_term trms ctxt'
   418         val ctxt'' = fold Variable.declare_term trms ctxt'
   422       in
   419       in
   423         map (Syntax.read_term ctxt'') avoid_trms
   420         map (Syntax.read_term ctxt'') avoid_trms
   424       end
   421       end
   425 
   422 
   437     Scan.optional (@{keyword "avoids"} |-- Parse.enum1 "|" single_avoid_parser) []
   434     Scan.optional (@{keyword "avoids"} |-- Parse.enum1 "|" single_avoid_parser) []
   438 
   435 
   439   val main_parser = Parse.xname -- avoids_parser
   436   val main_parser = Parse.xname -- avoids_parser
   440 in
   437 in
   441   val _ =
   438   val _ =
   442     Outer_Syntax.local_theory_to_proof @{command_spec "nominal_inductive"}
   439     Outer_Syntax.local_theory_to_proof @{command_keyword nominal_inductive}
   443       "prove strong induction theorem for inductive predicate involving nominal datatypes"
   440       "prove strong induction theorem for inductive predicate involving nominal datatypes"
   444         (main_parser >> prove_strong_inductive_cmd)
   441         (main_parser >> prove_strong_inductive_cmd)
   445 end
   442 end
   446 
   443 
   447 end
   444 end