Nominal/nominal_inductive.ML
branchNominal2-Isabelle2016
changeset 3243 c4f31f1564b7
parent 3239 67370521c09c
child 3245 017e33849f4d
equal deleted inserted replaced
3242:4af8a92396ce 3243:c4f31f1564b7
    22   Thm.apply (Thm.apply @{cterm "plus :: perm => perm => perm"} p) q
    22   Thm.apply (Thm.apply @{cterm "plus :: perm => perm => perm"} p) q
    23 
    23 
    24 fun mk_cminus p =
    24 fun mk_cminus p =
    25   Thm.apply @{cterm "uminus :: perm => perm"} p
    25   Thm.apply @{cterm "uminus :: perm => perm"} p
    26 
    26 
    27 fun minus_permute_intro_tac p =
    27 fun minus_permute_intro_tac ctxt p =
    28   rtac (Drule.instantiate' [] [SOME (mk_cminus p)] @{thm permute_boolE})
    28   resolve_tac ctxt [Thm.instantiate' [] [SOME (mk_cminus p)] @{thm permute_boolE}]
    29 
    29 
    30 fun minus_permute_elim p thm =
    30 fun minus_permute_elim p thm =
    31   thm RS (Drule.instantiate' [] [NONE, SOME (mk_cminus p)] @{thm permute_boolI})
    31   thm RS (Thm.instantiate' [] [NONE, SOME (mk_cminus p)] @{thm permute_boolI})
    32 
    32 
    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
   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 (Thm.ctyp_of_cterm ct)] [NONE, SOME ct] @{thm spec}
   159       Thm.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 =
   165   Subgoal.SUBPROOF (fn {context, prems, ...} =>
   165   Subgoal.SUBPROOF (fn {context = ctxt', prems, ...} =>
   166     let
   166     let
   167       val prems' = prems
   167       val prems' = prems
   168         |> map (minus_permute_elim p)
   168         |> map (minus_permute_elim p)
   169         |> map (eqvt_srule context)
   169         |> map (eqvt_srule 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 ctxt')
   174     in
   174     in
   175       asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps (prm' :: @{thms HOL.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 = ctxt', params, prems, ...} =>
   179   Subgoal.SUBPROOF (fn {context = ctxt', params, prems, ...} =>
   180     let
   180     let
   181       val (prms, p, _) = split_last2 (map snd params)
   181       val (prms, p, _) = split_last2 (map snd params)
   182       val prm_tys = map (fastype_of o Thm.term_of) prms
   182       val prm_tys = map (fastype_of o Thm.term_of) prms
   183       val cperms = map (Thm.cterm_of ctxt' o perm_const) prm_tys
   183       val cperms = map (Thm.cterm_of ctxt' o perm_const) prm_tys
   184       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 
   185       val prem' = prem
   185       val prem' = prem
   186         |> cterm_instantiate (intr_cvars ~~ p_prms) 
   186         |> infer_instantiate ctxt' (map (#1 o dest_Var o Thm.term_of) intr_cvars ~~ p_prms) 
   187         |> eqvt_srule ctxt
   187         |> eqvt_srule ctxt'
   188 
   188 
   189       (* for inductive-premises*)
   189       (* for inductive-premises*)
   190       fun tac1 prm = helper_tac true prm p ctxt'
   190       fun tac1 prm = helper_tac true prm p ctxt'
   191 
   191 
   192       (* for non-inductive premises *)   
   192       (* for non-inductive premises *)   
   193       fun tac2 prm =  
   193       fun tac2 prm =  
   194         EVERY' [ minus_permute_intro_tac p, 
   194         EVERY' [ minus_permute_intro_tac ctxt' p, 
   195                  eqvt_stac ctxt', 
   195                  eqvt_stac ctxt', 
   196                  helper_tac false prm p ctxt' ]
   196                  helper_tac false prm p ctxt' ]
   197 
   197 
   198       fun select prm (t, i) =
   198       fun select prm (t, i) =
   199         (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
   200     in
   200     in
   201       EVERY1 [ eqvt_stac ctxt', 
   201       EVERY1 [ eqvt_stac ctxt', 
   202                rtac prem', 
   202                resolve_tac ctxt' [prem'], 
   203                RANGE (map (SUBGOAL o select) prems) ]
   203                RANGE (map (SUBGOAL o select) prems) ]
   204     end) ctxt
   204     end) ctxt
   205 
   205 
   206 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 =
   207   let
   207   let
   215     val ss = @{thms finite_supp supp_Pair finite_Un permute_finite} @ 
   215     val ss = @{thms finite_supp supp_Pair finite_Un permute_finite} @ 
   216              @{thms fresh_star_Pair fresh_star_permute_iff}
   216              @{thms fresh_star_Pair fresh_star_permute_iff}
   217     val simp = asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps ss)
   217     val simp = asm_full_simp_tac (put_simpset HOL_ss ctxt addsimps ss)
   218   in 
   218   in 
   219     Goal.prove ctxt [] [] fresh_goal
   219     Goal.prove ctxt [] [] fresh_goal
   220       (K (HEADGOAL (rtac @{thm at_set_avoiding2} 
   220       (K (HEADGOAL (resolve_tac ctxt @{thms at_set_avoiding2}
   221           THEN_ALL_NEW EVERY' [cut_facts_tac user_thm, REPEAT o etac @{thm conjE}, simp])))
   221           THEN_ALL_NEW EVERY' [cut_facts_tac user_thm, REPEAT o
       
   222             eresolve_tac ctxt @{thms conjE}, simp])))
   222   end
   223   end
   223 
   224 
   224 val supp_perm_eq' = @{lemma "fresh_star (supp (permute p x)) q ==> permute p x == permute (q + p) x" 
   225 val supp_perm_eq' = @{lemma "fresh_star (supp (permute p x)) q ==> permute p x == permute (q + p) x" 
   225   by (simp add: supp_perm_eq)}
   226   by (simp add: supp_perm_eq)}
   226 
   227 
   236       val prm_tys = map fastype_of prm_trms
   237       val prm_tys = map fastype_of prm_trms
   237 
   238 
   238       val avoid_trm' = subst_free (param_trms ~~ prm_trms) avoid_trm 
   239       val avoid_trm' = subst_free (param_trms ~~ prm_trms) avoid_trm 
   239       val concl_args' = map (subst_free (param_trms ~~ prm_trms)) concl_args 
   240       val concl_args' = map (subst_free (param_trms ~~ prm_trms)) concl_args 
   240       
   241       
   241       val user_thm' = map (cterm_instantiate (intr_cvars ~~ prms)) user_thm
   242       val user_thm' = map (infer_instantiate ctxt (map (#1 o dest_Var o Thm.term_of) intr_cvars ~~ prms)) user_thm
   242         |> map (full_simplify (put_simpset HOL_ss ctxt addsimps (@{thm fresh_star_Pair}::prems)))
   243         |> map (full_simplify (put_simpset HOL_ss ctxt addsimps (@{thm fresh_star_Pair}::prems)))
   243       
   244       
   244       val fthm = fresh_thm ctxt user_thm' (Thm.term_of p) (Thm.term_of c) concl_args' avoid_trm'
   245       val fthm = fresh_thm ctxt user_thm' (Thm.term_of p) (Thm.term_of c) concl_args' avoid_trm'
   245 
   246 
   246       val (([(_, q)], fprop :: fresh_eqs), ctxt') = Obtain.result
   247       val (([(_, q)], fprop :: fresh_eqs), ctxt') = Obtain.result
   247               (K (EVERY1 [etac @{thm exE}, 
   248               (K (EVERY1 [eresolve_tac ctxt @{thms exE}, 
   248                           full_simp_tac (put_simpset HOL_basic_ss ctxt
   249                           full_simp_tac (put_simpset HOL_basic_ss ctxt
   249                             addsimps @{thms supp_Pair fresh_star_Un}),
   250                             addsimps @{thms supp_Pair fresh_star_Un}),
   250                           REPEAT o etac @{thm conjE},
   251                           REPEAT o eresolve_tac ctxt @{thms conjE},
   251                           dtac fresh_star_plus,
   252                           dresolve_tac ctxt [fresh_star_plus],
   252                           REPEAT o dtac supp_perm_eq'])) [fthm] ctxt 
   253                           REPEAT o dresolve_tac ctxt [supp_perm_eq']])) [fthm] ctxt 
   253 
   254 
   254       val expand_conv = Conv.try_conv (Conv.rewrs_conv fresh_eqs)
   255       val expand_conv = Conv.try_conv (Conv.rewrs_conv fresh_eqs)
   255       fun expand_conv_bot ctxt = Conv.bottom_conv (K expand_conv) ctxt
   256       fun expand_conv_bot ctxt = Conv.bottom_conv (K expand_conv) ctxt
   256 
   257 
   257       val cperms = map (Thm.cterm_of ctxt o perm_const) prm_tys
   258       val cperms = map (Thm.cterm_of ctxt' o perm_const) prm_tys
   258       val qp_prms = map2 (fn ct1 => fn ct2 => Thm.mk_binop ct1 (mk_cplus q p) ct2) cperms prms 
   259       val qp_prms = map2 (fn ct1 => fn ct2 => Thm.mk_binop ct1 (mk_cplus q p) ct2) cperms prms 
   259       val prem' = prem
   260       val prem' = prem
   260         |> cterm_instantiate (intr_cvars ~~ qp_prms)
   261         |> infer_instantiate ctxt' (map (#1 o dest_Var o Thm.term_of) intr_cvars ~~ qp_prms)
   261         |> eqvt_srule ctxt
   262         |> eqvt_srule ctxt'
   262 
   263 
   263       val fprop' = eqvt_srule ctxt' fprop 
   264       val fprop' = eqvt_srule ctxt' fprop 
   264       val tac_fresh = simp_tac (put_simpset HOL_basic_ss ctxt' addsimps [fprop'])
   265       val tac_fresh = simp_tac (put_simpset HOL_basic_ss ctxt' addsimps [fprop'])
   265 
   266 
   266       (* for inductive-premises*)
   267       (* for inductive-premises*)
   267       fun tac1 prm = helper_tac true prm (mk_cplus q p) ctxt' 
   268       fun tac1 prm = helper_tac true prm (mk_cplus q p) ctxt' 
   268 
   269 
   269       (* for non-inductive premises *)   
   270       (* for non-inductive premises *)   
   270       fun tac2 prm =  
   271       fun tac2 prm =  
   271         EVERY' [ minus_permute_intro_tac (mk_cplus q p), 
   272         EVERY' [ minus_permute_intro_tac ctxt' (mk_cplus q p), 
   272                  eqvt_stac ctxt, 
   273                  eqvt_stac ctxt', 
   273                  helper_tac false prm (mk_cplus q p) ctxt' ]
   274                  helper_tac false prm (mk_cplus q p) ctxt' ]
   274 
   275 
   275       fun select prm (t, i) =
   276       fun select prm (t, i) =
   276         (if member same_name Ps (real_head_of t) then tac1 prm else tac2 prm) i
   277         (if member same_name Ps (real_head_of t) then tac1 prm else tac2 prm) i
   277 
   278 
   278       val side_thm = Goal.prove ctxt' [] [] (Thm.term_of concl)
   279       val side_thm = Goal.prove ctxt' [] [] (Thm.term_of concl)
   279         (fn {context = ctxt'', ...} => 
   280         (fn {context = ctxt'', ...} => 
   280            EVERY1 [ CONVERSION (expand_conv_bot ctxt''),
   281            EVERY1 [ CONVERSION (expand_conv_bot ctxt''),
   281                     eqvt_stac ctxt'',
   282                     eqvt_stac ctxt'',
   282                     rtac prem',
   283                     resolve_tac ctxt'' [prem'],
   283                     RANGE (tac_fresh :: map (SUBGOAL o select) prems) ])
   284                     RANGE (tac_fresh :: map (SUBGOAL o select) prems) ])
   284         |> singleton (Proof_Context.export ctxt' ctxt)
   285         |> singleton (Proof_Context.export ctxt' ctxt)
   285     in
   286     in
   286       rtac side_thm 1
   287       resolve_tac ctxt [side_thm] 1
   287     end) ctxt
   288     end) ctxt
   288 
   289 
   289 fun case_tac ctxt Ps avoid avoid_trm intr_cvars param_trms prem user_thm concl_args =
   290 fun case_tac ctxt Ps avoid avoid_trm intr_cvars param_trms prem user_thm concl_args =
   290   let
   291   let
   291     val tac1 = non_binder_tac prem intr_cvars Ps ctxt
   292     val tac1 = non_binder_tac prem intr_cvars Ps ctxt
   292     val tac2 = binder_tac prem intr_cvars param_trms Ps user_thm avoid_trm concl_args ctxt
   293     val tac2 = binder_tac prem intr_cvars param_trms Ps user_thm avoid_trm concl_args ctxt
   293   in 
   294   in 
   294     EVERY' [ rtac @{thm allI}, rtac @{thm allI}, 
   295     EVERY' [ resolve_tac ctxt @{thms allI}, resolve_tac ctxt @{thms allI}, 
   295              if null avoid then tac1 else tac2 ]
   296              if null avoid then tac1 else tac2 ]
   296   end
   297   end
   297 
   298 
   298 fun prove_sinduct_tac raw_induct user_thms Ps avoids avoid_trms intr_cvars param_trms concl_args 
   299 fun prove_sinduct_tac raw_induct user_thms Ps avoids avoid_trms intr_cvars param_trms concl_args 
   299   {prems, context} =
   300   {prems, context = ctxt} =
   300   let
   301   let
   301     val cases_tac = 
   302     val cases_tac = 
   302       map7 (case_tac context Ps) avoids avoid_trms intr_cvars param_trms prems user_thms concl_args
   303       map7 (case_tac ctxt Ps) avoids avoid_trms intr_cvars param_trms prems user_thms concl_args
   303   in 
   304   in 
   304     EVERY1 [ DETERM o rtac raw_induct, RANGE cases_tac ]
   305     EVERY1 [ DETERM o resolve_tac ctxt [raw_induct], RANGE cases_tac ]
   305   end
   306   end
   306 
   307 
   307 val normalise = @{lemma "(Q --> (!p c. P p c)) ==> (!!c. Q ==> P (0::perm) c)" by simp}
   308 val normalise = @{lemma "(Q --> (!p c. P p c)) ==> (!!c. Q ==> P (0::perm) c)" by simp}
   308 
   309 
   309 fun prove_strong_inductive pred_names rule_names avoids raw_induct intrs ctxt =
   310 fun prove_strong_inductive pred_names rule_names avoids raw_induct intrs ctxt =