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 = |
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 |