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]) |