diff --git a/src/HOL/Nominal/nominal_inductive.ML b/src/HOL/Nominal/nominal_inductive.ML --- a/src/HOL/Nominal/nominal_inductive.ML +++ b/src/HOL/Nominal/nominal_inductive.ML @@ -1,695 +1,695 @@ (* Title: HOL/Nominal/nominal_inductive.ML Author: Stefan Berghofer, TU Muenchen Infrastructure for proving equivariance and strong induction theorems for inductive predicates involving nominal datatypes. *) signature NOMINAL_INDUCTIVE = sig val prove_strong_ind: string -> (string * string list) list -> local_theory -> Proof.state val prove_eqvt: string -> string list -> local_theory -> local_theory end structure NominalInductive : NOMINAL_INDUCTIVE = struct val inductive_forall_def = @{thm HOL.induct_forall_def}; val inductive_atomize = @{thms induct_atomize}; val inductive_rulify = @{thms induct_rulify}; fun rulify_term thy = Raw_Simplifier.rewrite_term thy inductive_rulify []; fun atomize_conv ctxt = Raw_Simplifier.rewrite_cterm (true, false, false) (K (K NONE)) (put_simpset HOL_basic_ss ctxt addsimps inductive_atomize); fun atomize_intr ctxt = Conv.fconv_rule (Conv.prems_conv ~1 (atomize_conv ctxt)); fun atomize_induct ctxt = Conv.fconv_rule (Conv.prems_conv ~1 (Conv.params_conv ~1 (fn ctxt' => Conv.prems_conv ~1 (atomize_conv ctxt')) ctxt)); fun preds_of ps t = inter (op = o apsnd dest_Free) ps (Term.add_frees t []); val fresh_prod = @{thm fresh_prod}; val perm_bool = mk_meta_eq @{thm perm_bool_def}; val perm_boolI = @{thm perm_boolI}; val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb (Drule.strip_imp_concl (Thm.cprop_of perm_boolI)))); fun mk_perm_bool ctxt pi th = th RS infer_instantiate ctxt [(#1 (dest_Var (Thm.term_of perm_boolI_pi)), pi)] perm_boolI; fun mk_perm_bool_simproc names = Simplifier.make_simproc \<^context> "perm_bool" {lhss = [\<^term>\perm pi x\], proc = fn _ => fn _ => fn ct => (case Thm.term_of ct of Const (\<^const_name>\Nominal.perm\, _) $ _ $ t => if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t)) then SOME perm_bool else NONE | _ => NONE)}; fun transp ([] :: _) = [] | transp xs = map hd xs :: transp (map tl xs); fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of (Const (s, T), ts) => (case strip_type T of (Ts, Type (tname, _)) => (case NominalDatatype.get_nominal_datatype thy tname of NONE => fold (add_binders thy i) ts bs | SOME {descr, index, ...} => (case AList.lookup op = (#3 (the (AList.lookup op = descr index))) s of NONE => fold (add_binders thy i) ts bs | SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') => let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs' in (add_binders thy i u (fold (fn (u, T) => if exists (fn j => j < i) (loose_bnos u) then I else insert (op aconv o apply2 fst) (incr_boundvars (~i) u, T)) cargs1 bs'), cargs2) end) cargs (bs, ts ~~ Ts)))) | _ => fold (add_binders thy i) ts bs) | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs)) | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs | add_binders thy i _ bs = bs; fun split_conj f names (Const (\<^const_name>\HOL.conj\, _) $ p $ q) _ = (case head_of p of Const (name, _) => if member (op =) names name then SOME (f p q) else NONE | _ => NONE) | split_conj _ _ _ _ = NONE; fun strip_all [] t = t | strip_all (_ :: xs) (Const (\<^const_name>\All\, _) $ Abs (s, T, t)) = strip_all xs t; (*********************************************************************) (* maps R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t)) *) (* or ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t) *) (* to R ... & id (ALL z. P z (pi_1 o ... o pi_n o t)) *) (* or id (ALL z. P z (pi_1 o ... o pi_n o t)) *) (* *) (* where "id" protects the subformula from simplification *) (*********************************************************************) fun inst_conj_all names ps pis (Const (\<^const_name>\HOL.conj\, _) $ p $ q) _ = (case head_of p of Const (name, _) => if member (op =) names name then SOME (HOLogic.mk_conj (p, Const (\<^const_name>\Fun.id\, HOLogic.boolT --> HOLogic.boolT) $ (subst_bounds (pis, strip_all pis q)))) else NONE | _ => NONE) | inst_conj_all names ps pis t u = if member (op aconv) ps (head_of u) then SOME (Const (\<^const_name>\Fun.id\, HOLogic.boolT --> HOLogic.boolT) $ (subst_bounds (pis, strip_all pis t))) else NONE | inst_conj_all _ _ _ _ _ = NONE; fun inst_conj_all_tac ctxt k = EVERY [TRY (EVERY [eresolve_tac ctxt [conjE] 1, resolve_tac ctxt [conjI] 1, assume_tac ctxt 1]), REPEAT_DETERM_N k (eresolve_tac ctxt [allE] 1), simp_tac (put_simpset HOL_basic_ss ctxt addsimps [@{thm id_apply}]) 1]; fun map_term f t u = (case f t u of NONE => map_term' f t u | x => x) and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of (NONE, NONE) => NONE | (SOME t'', NONE) => SOME (t'' $ u) | (NONE, SOME u'') => SOME (t $ u'') | (SOME t'', SOME u'') => SOME (t'' $ u'')) | map_term' f (Abs (s, T, t)) (Abs (s', T', t')) = (case map_term f t t' of NONE => NONE | SOME t'' => SOME (Abs (s, T, t''))) | map_term' _ _ _ = NONE; (*********************************************************************) (* Prove F[f t] from F[t], where F is monotone *) (*********************************************************************) fun map_thm ctxt f tac monos opt th = let val prop = Thm.prop_of th; fun prove t = Goal.prove ctxt [] [] t (fn {context = goal_ctxt, ...} => EVERY [cut_facts_tac [th] 1, eresolve_tac goal_ctxt [rev_mp] 1, REPEAT_DETERM (FIRSTGOAL (resolve_tac goal_ctxt monos)), REPEAT_DETERM (resolve_tac goal_ctxt [impI] 1 THEN (assume_tac goal_ctxt 1 ORELSE tac))]) in Option.map prove (map_term f prop (the_default prop opt)) end; val eta_contract_cterm = Thm.dest_arg o Thm.cprop_of o Thm.eta_conversion; fun first_order_matchs pats objs = Thm.first_order_match (eta_contract_cterm (Conjunction.mk_conjunction_balanced pats), eta_contract_cterm (Conjunction.mk_conjunction_balanced objs)); fun first_order_mrs ths th = ths MRS Thm.instantiate (first_order_matchs (cprems_of th) (map Thm.cprop_of ths)) th; -fun prove_strong_ind s avoids ctxt = +fun prove_strong_ind s avoids lthy = let - val thy = Proof_Context.theory_of ctxt; + val thy = Proof_Context.theory_of lthy; val ({names, ...}, {raw_induct, intrs, elims, ...}) = - Inductive.the_inductive_global ctxt (Sign.intern_const thy s); + Inductive.the_inductive_global lthy (Sign.intern_const thy s); val ind_params = Inductive.params_of raw_induct; - val raw_induct = atomize_induct ctxt raw_induct; - val elims = map (atomize_induct ctxt) elims; - val monos = Inductive.get_monos ctxt; - val eqvt_thms = NominalThmDecls.get_eqvt_thms ctxt; + val raw_induct = atomize_induct lthy raw_induct; + val elims = map (atomize_induct lthy) elims; + val monos = Inductive.get_monos lthy; + val eqvt_thms = NominalThmDecls.get_eqvt_thms lthy; val _ = (case subtract (op =) (fold (Term.add_const_names o Thm.prop_of) eqvt_thms []) names of [] => () | xs => error ("Missing equivariance theorem for predicate(s): " ^ commas_quote xs)); val induct_cases = map (fst o fst) (fst (Rule_Cases.get (the - (Induct.lookup_inductP ctxt (hd names))))); - val (raw_induct', ctxt') = ctxt + (Induct.lookup_inductP lthy (hd names))))); + val (raw_induct', ctxt') = lthy |> yield_singleton (Variable.import_terms false) (Thm.prop_of raw_induct); val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |> HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb); val ps = map (fst o snd) concls; val _ = (case duplicates (op = o apply2 fst) avoids of [] => () | xs => error ("Duplicate case names: " ^ commas_quote (map fst xs))); val _ = avoids |> forall (fn (a, xs) => null (duplicates (op =) xs) orelse error ("Duplicate variable names for case " ^ quote a)); val _ = (case subtract (op =) induct_cases (map fst avoids) of [] => () | xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs)); val avoids' = if null induct_cases then replicate (length intrs) ("", []) else map (fn name => (name, the_default [] (AList.lookup op = avoids name))) induct_cases; fun mk_avoids params (name, ps) = let val k = length params - 1 in map (fn x => case find_index (equal x o fst) params of ~1 => error ("No such variable in case " ^ quote name ^ " of inductive definition: " ^ quote x) | i => (Bound (k - i), snd (nth params i))) ps end; val prems = map (fn (prem, avoid) => let val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem); val concl = incr_boundvars 1 (Logic.strip_assums_concl prem); val params = Logic.strip_params prem in (params, fold (add_binders thy 0) (prems @ [concl]) [] @ map (apfst (incr_boundvars 1)) (mk_avoids params avoid), prems, strip_comb (HOLogic.dest_Trueprop concl)) end) (Logic.strip_imp_prems raw_induct' ~~ avoids'); val atomTs = distinct op = (maps (map snd o #2) prems); val ind_sort = if null atomTs then \<^sort>\type\ else Sign.minimize_sort thy (Sign.certify_sort thy (map (fn T => Sign.intern_class thy ("fs_" ^ Long_Name.base_name (fst (dest_Type T)))) atomTs)); val (fs_ctxt_tyname, _) = Name.variant "'n" (Variable.names_of ctxt'); val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt'; val fsT = TFree (fs_ctxt_tyname, ind_sort); val inductive_forall_def' = Thm.instantiate' [SOME (Thm.global_ctyp_of thy fsT)] [] inductive_forall_def; fun lift_pred' t (Free (s, T)) ts = list_comb (Free (s, fsT --> T), t :: ts); val lift_pred = lift_pred' (Bound 0); fun lift_prem (t as (f $ u)) = let val (p, ts) = strip_comb t in if member (op =) ps p then HOLogic.mk_induct_forall fsT $ Abs ("z", fsT, lift_pred p (map (incr_boundvars 1) ts)) else lift_prem f $ lift_prem u end | lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t) | lift_prem t = t; fun mk_distinct [] = [] | mk_distinct ((x, T) :: xs) = map_filter (fn (y, U) => if T = U then SOME (HOLogic.mk_Trueprop (HOLogic.mk_not (HOLogic.eq_const T $ x $ y))) else NONE) xs @ mk_distinct xs; fun mk_fresh (x, T) = HOLogic.mk_Trueprop (NominalDatatype.fresh_const T fsT $ x $ Bound 0); val (prems', prems'') = split_list (map (fn (params, bvars, prems, (p, ts)) => let val params' = params @ [("y", fsT)]; val prem = Logic.list_implies (map mk_fresh bvars @ mk_distinct bvars @ map (fn prem => if null (preds_of ps prem) then prem else lift_prem prem) prems, HOLogic.mk_Trueprop (lift_pred p ts)); val vs = map (Var o apfst (rpair 0)) (Term.rename_wrt_term prem params') in (Logic.list_all (params', prem), (rev vs, subst_bounds (vs, prem))) end) prems); val ind_vars = (Old_Datatype_Prop.indexify_names (replicate (length atomTs) "pi") ~~ map NominalAtoms.mk_permT atomTs) @ [("z", fsT)]; val ind_Ts = rev (map snd ind_vars); val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem, HOLogic.list_all (ind_vars, lift_pred p (map (fold_rev (NominalDatatype.mk_perm ind_Ts) (map Bound (length atomTs downto 1))) ts)))) concls)); val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem, lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls)); val vc_compat = map (fn (params, bvars, prems, (p, ts)) => map (fn q => Logic.list_all (params, incr_boundvars ~1 (Logic.list_implies (map_filter (fn prem => if null (preds_of ps prem) then SOME prem else map_term (split_conj (K o I) names) prem prem) prems, q)))) (mk_distinct bvars @ maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop (NominalDatatype.fresh_const U T $ u $ t)) bvars) (ts ~~ binder_types (fastype_of p)))) prems; val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp"; val pt2_atoms = map (fn aT => Global_Theory.get_thm thy ("pt_" ^ Long_Name.base_name (fst (dest_Type aT)) ^ "2")) atomTs; val eqvt_ss = simpset_of (put_simpset HOL_basic_ss (Proof_Context.init_global thy) addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms) addsimprocs [mk_perm_bool_simproc [\<^const_name>\Fun.id\], NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]); val fresh_bij = Global_Theory.get_thms thy "fresh_bij"; val perm_bij = Global_Theory.get_thms thy "perm_bij"; val fs_atoms = map (fn aT => Global_Theory.get_thm thy ("fs_" ^ Long_Name.base_name (fst (dest_Type aT)) ^ "1")) atomTs; val exists_fresh' = Global_Theory.get_thms thy "exists_fresh'"; val fresh_atm = Global_Theory.get_thms thy "fresh_atm"; val swap_simps = Global_Theory.get_thms thy "swap_simps"; val perm_fresh_fresh = Global_Theory.get_thms thy "perm_fresh_fresh"; fun obtain_fresh_name ts T (freshs1, freshs2, ctxt) = let (** protect terms to avoid that fresh_prod interferes with **) (** pairs used in introduction rules of inductive predicate **) fun protect t = let val T = fastype_of t in Const (\<^const_name>\Fun.id\, T --> T) $ t end; val p = foldr1 HOLogic.mk_prod (map protect ts @ freshs1); val ex = Goal.prove ctxt [] [] (HOLogic.mk_Trueprop (HOLogic.exists_const T $ Abs ("x", T, NominalDatatype.fresh_const T (fastype_of p) $ Bound 0 $ p))) (fn _ => EVERY [resolve_tac ctxt exists_fresh' 1, resolve_tac ctxt fs_atoms 1]); val (([(_, cx)], ths), ctxt') = Obtain.result (fn ctxt' => EVERY [eresolve_tac ctxt' [exE] 1, full_simp_tac (put_simpset HOL_ss ctxt' addsimps (fresh_prod :: fresh_atm)) 1, full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps [@{thm id_apply}]) 1, REPEAT (eresolve_tac ctxt [conjE] 1)]) [ex] ctxt in (freshs1 @ [Thm.term_of cx], freshs2 @ ths, ctxt') end; fun mk_ind_proof ctxt' thss = Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} => let val th = Goal.prove ctxt [] [] concl (fn {context, ...} => resolve_tac context [raw_induct] 1 THEN EVERY (maps (fn ((((_, bvars, oprems, _), vc_compat_ths), ihyp), (vs, ihypt)) => [REPEAT (resolve_tac context [allI] 1), simp_tac (put_simpset eqvt_ss context) 1, SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} => let val (params', (pis, z)) = chop (length params - length atomTs - 1) (map (Thm.term_of o #2) params) ||> split_last; val bvars' = map (fn (Bound i, T) => (nth params' (length params' - i), T) | (t, T) => (t, T)) bvars; val pi_bvars = map (fn (t, _) => fold_rev (NominalDatatype.mk_perm []) pis t) bvars'; val (P, ts) = strip_comb (HOLogic.dest_Trueprop (Thm.term_of concl)); val (freshs1, freshs2, ctxt'') = fold (obtain_fresh_name (ts @ pi_bvars)) (map snd bvars') ([], [], ctxt'); val freshs2' = NominalDatatype.mk_not_sym freshs2; val pis' = map NominalDatatype.perm_of_pair (pi_bvars ~~ freshs1); fun concat_perm pi1 pi2 = let val T = fastype_of pi1 in if T = fastype_of pi2 then Const (\<^const_name>\append\, T --> T --> T) $ pi1 $ pi2 else pi2 end; val pis'' = fold (concat_perm #> map) pis' pis; val env = Pattern.first_order_match thy (ihypt, Thm.prop_of ihyp) (Vartab.empty, Vartab.empty); val ihyp' = Thm.instantiate (TVars.empty, Vars.make (map (fn (v, t) => (dest_Var v, Thm.global_cterm_of thy t)) (map (Envir.subst_term env) vs ~~ map (fold_rev (NominalDatatype.mk_perm []) (rev pis' @ pis)) params' @ [z]))) ihyp; fun mk_pi th = Simplifier.simplify (put_simpset HOL_basic_ss ctxt'' addsimps [@{thm id_apply}] addsimprocs [NominalDatatype.perm_simproc]) (Simplifier.simplify (put_simpset eqvt_ss ctxt'') (fold_rev (mk_perm_bool ctxt'' o Thm.cterm_of ctxt'') (rev pis' @ pis) th)); val (gprems1, gprems2) = split_list (map (fn (th, t) => if null (preds_of ps t) then (SOME th, mk_pi th) else (map_thm ctxt'' (split_conj (K o I) names) (eresolve_tac ctxt'' [conjunct1] 1) monos NONE th, mk_pi (the (map_thm ctxt'' (inst_conj_all names ps (rev pis'')) (inst_conj_all_tac ctxt'' (length pis'')) monos (SOME t) th)))) (gprems ~~ oprems)) |>> map_filter I; val vc_compat_ths' = map (fn th => let val th' = first_order_mrs gprems1 th; val (bop, lhs, rhs) = (case Thm.concl_of th' of _ $ (fresh $ lhs $ rhs) => (fn t => fn u => fresh $ t $ u, lhs, rhs) | _ $ (_ $ (_ $ lhs $ rhs)) => (curry (HOLogic.mk_not o HOLogic.mk_eq), lhs, rhs)); val th'' = Goal.prove ctxt'' [] [] (HOLogic.mk_Trueprop (bop (fold_rev (NominalDatatype.mk_perm []) pis lhs) (fold_rev (NominalDatatype.mk_perm []) pis rhs))) (fn _ => simp_tac (put_simpset HOL_basic_ss ctxt'' addsimps (fresh_bij @ perm_bij)) 1 THEN resolve_tac ctxt'' [th'] 1) in Simplifier.simplify (put_simpset eqvt_ss ctxt'' addsimps fresh_atm) th'' end) vc_compat_ths; val vc_compat_ths'' = NominalDatatype.mk_not_sym vc_compat_ths'; (** Since swap_simps simplifies (pi :: 'a prm) o (x :: 'b) to x **) (** we have to pre-simplify the rewrite rules **) val swap_simps_simpset = put_simpset HOL_ss ctxt'' addsimps swap_simps @ map (Simplifier.simplify (put_simpset HOL_ss ctxt'' addsimps swap_simps)) (vc_compat_ths'' @ freshs2'); val th = Goal.prove ctxt'' [] [] (HOLogic.mk_Trueprop (list_comb (P $ hd ts, map (fold (NominalDatatype.mk_perm []) pis') (tl ts)))) (fn _ => EVERY ([simp_tac (put_simpset eqvt_ss ctxt'') 1, resolve_tac ctxt'' [ihyp'] 1, REPEAT_DETERM_N (Thm.nprems_of ihyp - length gprems) (simp_tac swap_simps_simpset 1), REPEAT_DETERM_N (length gprems) (simp_tac (put_simpset HOL_basic_ss ctxt'' addsimps [inductive_forall_def'] addsimprocs [NominalDatatype.perm_simproc]) 1 THEN resolve_tac ctxt'' gprems2 1)])); val final = Goal.prove ctxt'' [] [] (Thm.term_of concl) (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (put_simpset HOL_ss ctxt'' addsimps vc_compat_ths'' @ freshs2' @ perm_fresh_fresh @ fresh_atm) 1); val final' = Proof_Context.export ctxt'' ctxt' [final]; in resolve_tac ctxt' final' 1 end) context 1]) (prems ~~ thss ~~ ihyps ~~ prems''))) in cut_facts_tac [th] 1 THEN REPEAT (eresolve_tac ctxt [conjE] 1) THEN REPEAT (REPEAT (resolve_tac ctxt [conjI, impI] 1) THEN eresolve_tac ctxt [impE] 1 THEN assume_tac ctxt 1 THEN REPEAT (eresolve_tac ctxt @{thms allE_Nil} 1) THEN asm_full_simp_tac ctxt 1) - end) |> singleton (Proof_Context.export ctxt' ctxt); + end) |> singleton (Proof_Context.export ctxt' lthy); (** strong case analysis rule **) val cases_prems = map (fn ((name, avoids), rule) => let - val ([rule'], ctxt') = Variable.import_terms false [Thm.prop_of rule] ctxt; + val ([rule'], ctxt') = Variable.import_terms false [Thm.prop_of rule] lthy; val prem :: prems = Logic.strip_imp_prems rule'; val concl = Logic.strip_imp_concl rule' in (prem, List.drop (snd (strip_comb (HOLogic.dest_Trueprop prem)), length ind_params), concl, fold_map (fn (prem, (_, avoid)) => fn ctxt => let val prems = Logic.strip_assums_hyp prem; val params = Logic.strip_params prem; val bnds = fold (add_binders thy 0) prems [] @ mk_avoids params avoid; fun mk_subst (p as (s, T)) (i, j, ctxt, ps, qs, is, ts) = if member (op = o apsnd fst) bnds (Bound i) then let val ([s'], ctxt') = Variable.variant_fixes [s] ctxt; val t = Free (s', T) in (i + 1, j, ctxt', ps, (t, T) :: qs, i :: is, t :: ts) end else (i + 1, j + 1, ctxt, p :: ps, qs, is, Bound j :: ts); val (_, _, ctxt', ps, qs, is, ts) = fold_rev mk_subst params (0, 0, ctxt, [], [], [], []) in ((ps, qs, is, map (curry subst_bounds (rev ts)) prems), ctxt') end) (prems ~~ avoids) ctxt') end) (Inductive.partition_rules' raw_induct (intrs ~~ avoids') ~~ elims); val cases_prems' = map (fn (prem, args, concl, (prems, _)) => let fun mk_prem (ps, [], _, prems) = Logic.list_all (ps, Logic.list_implies (prems, concl)) | mk_prem (ps, qs, _, prems) = Logic.list_all (ps, Logic.mk_implies (Logic.list_implies (mk_distinct qs @ maps (fn (t, T) => map (fn u => HOLogic.mk_Trueprop (NominalDatatype.fresh_const T (fastype_of u) $ t $ u)) args) qs, HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map HOLogic.dest_Trueprop prems))), concl)) in map mk_prem prems end) cases_prems; val cases_eqvt_simpset = put_simpset HOL_ss (Proof_Context.init_global thy) addsimps eqvt_thms @ swap_simps @ perm_pi_simp addsimprocs [NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]; val simp_fresh_atm = map (Simplifier.simplify (put_simpset HOL_basic_ss (Proof_Context.init_global thy) addsimps fresh_atm)); fun mk_cases_proof ((((name, thss), elim), (prem, args, concl, (prems, ctxt'))), prems') = (name, Goal.prove ctxt' [] (prem :: prems') concl (fn {prems = hyp :: hyps, context = ctxt1} => EVERY (resolve_tac ctxt1 [hyp RS elim] 1 :: map (fn (((_, vc_compat_ths), case_hyp), (_, qs, is, _)) => SUBPROOF (fn {prems = case_hyps, params, context = ctxt2, concl, ...} => if null qs then resolve_tac ctxt2 [first_order_mrs case_hyps case_hyp] 1 else let val params' = map (Thm.term_of o #2 o nth (rev params)) is; val tab = params' ~~ map fst qs; val (hyps1, hyps2) = chop (length args) case_hyps; (* turns a = t and [x1 # t, ..., xn # t] *) (* into [x1 # a, ..., xn # a] *) fun inst_fresh th' ths = let val (ths1, ths2) = chop (length qs) ths in (map (fn th => let val (cf, ct) = Thm.dest_comb (Thm.dest_arg (Thm.cprop_of th)); val arg_cong' = Thm.instantiate' [SOME (Thm.ctyp_of_cterm ct)] [NONE, SOME ct, SOME cf] (arg_cong RS iffD2); val inst = Thm.first_order_match (ct, Thm.dest_arg (Thm.dest_arg (Thm.cprop_of th'))) in [th', th] MRS Thm.instantiate inst arg_cong' end) ths1, ths2) end; val (vc_compat_ths1, vc_compat_ths2) = chop (length vc_compat_ths - length args * length qs) (map (first_order_mrs hyps2) vc_compat_ths); val vc_compat_ths' = NominalDatatype.mk_not_sym vc_compat_ths1 @ flat (fst (fold_map inst_fresh hyps1 vc_compat_ths2)); val (freshs1, freshs2, ctxt3) = fold (obtain_fresh_name (args @ map fst qs @ params')) (map snd qs) ([], [], ctxt2); val freshs2' = NominalDatatype.mk_not_sym freshs2; val pis = map (NominalDatatype.perm_of_pair) ((freshs1 ~~ map fst qs) @ (params' ~~ freshs1)); val mk_pis = fold_rev (mk_perm_bool ctxt3) (map (Thm.cterm_of ctxt3) pis); val obj = Thm.global_cterm_of thy (foldr1 HOLogic.mk_conj (map (map_aterms (fn x as Free _ => if member (op =) args x then x else (case AList.lookup op = tab x of SOME y => y | NONE => fold_rev (NominalDatatype.mk_perm []) pis x) | x => x) o HOLogic.dest_Trueprop o Thm.prop_of) case_hyps)); val inst = Thm.first_order_match (Thm.dest_arg (Drule.strip_imp_concl (hd (cprems_of case_hyp))), obj); val th = Goal.prove ctxt3 [] [] (Thm.term_of concl) (fn {context = ctxt4, ...} => resolve_tac ctxt4 [Thm.instantiate inst case_hyp] 1 THEN SUBPROOF (fn {context = ctxt5, prems = fresh_hyps, ...} => let val fresh_hyps' = NominalDatatype.mk_not_sym fresh_hyps; val case_simpset = cases_eqvt_simpset addsimps freshs2' @ simp_fresh_atm (vc_compat_ths' @ fresh_hyps'); val fresh_fresh_simpset = case_simpset addsimps perm_fresh_fresh; val hyps1' = map (mk_pis #> Simplifier.simplify fresh_fresh_simpset) hyps1; val hyps2' = map (mk_pis #> Simplifier.simplify case_simpset) hyps2; val case_hyps' = hyps1' @ hyps2' in simp_tac case_simpset 1 THEN REPEAT_DETERM (TRY (resolve_tac ctxt5 [conjI] 1) THEN resolve_tac ctxt5 case_hyps' 1) end) ctxt4 1) val final = Proof_Context.export ctxt3 ctxt2 [th] in resolve_tac ctxt2 final 1 end) ctxt1 1) (thss ~~ hyps ~~ prems))) |> - singleton (Proof_Context.export ctxt' ctxt)) + singleton (Proof_Context.export ctxt' lthy)) in ctxt'' |> - Proof.theorem NONE (fn thss => fn ctxt => (* FIXME ctxt/ctxt' should be called lthy/lthy' *) + Proof.theorem NONE (fn thss => fn lthy1 => let val rec_name = space_implode "_" (map Long_Name.base_name names); val rec_qualified = Binding.qualify false rec_name; val ind_case_names = Rule_Cases.case_names induct_cases; val induct_cases' = Inductive.partition_rules' raw_induct (intrs ~~ induct_cases); - val thss' = map (map (atomize_intr ctxt)) thss; + val thss' = map (map (atomize_intr lthy1)) thss; val thsss = Inductive.partition_rules' raw_induct (intrs ~~ thss'); val strong_raw_induct = - mk_ind_proof ctxt thss' |> Inductive.rulify ctxt; - val strong_cases = map (mk_cases_proof ##> Inductive.rulify ctxt) + mk_ind_proof lthy1 thss' |> Inductive.rulify lthy1; + val strong_cases = map (mk_cases_proof ##> Inductive.rulify lthy1) (thsss ~~ elims ~~ cases_prems ~~ cases_prems'); val strong_induct_atts = map (Attrib.internal o K) [ind_case_names, Rule_Cases.consumes (~ (Thm.nprems_of strong_raw_induct))]; val strong_induct = if length names > 1 then strong_raw_induct else strong_raw_induct RSN (2, rev_mp); - val ((_, [strong_induct']), ctxt') = ctxt |> Local_Theory.note + val ((_, [strong_induct']), lthy2) = lthy1 |> Local_Theory.note ((rec_qualified (Binding.name "strong_induct"), strong_induct_atts), [strong_induct]); val strong_inducts = - Project_Rule.projects ctxt (1 upto length names) strong_induct'; + Project_Rule.projects lthy1 (1 upto length names) strong_induct'; in - ctxt' |> + lthy2 |> Local_Theory.notes [((rec_qualified (Binding.name "strong_inducts"), []), strong_inducts |> map (fn th => ([th], [Attrib.internal (K ind_case_names), Attrib.internal (K (Rule_Cases.consumes (1 - Thm.nprems_of th)))])))] |> snd |> Local_Theory.notes (map (fn ((name, elim), (_, cases)) => ((Binding.qualified_name (Long_Name.qualify (Long_Name.base_name name) "strong_cases"), [Attrib.internal (K (Rule_Cases.case_names (map snd cases))), Attrib.internal (K (Rule_Cases.consumes (1 - Thm.nprems_of elim)))]), [([elim], [])])) (strong_cases ~~ induct_cases')) |> snd end) (map (map (rulify_term thy #> rpair [])) vc_compat) end; fun prove_eqvt s xatoms lthy = let val thy = Proof_Context.theory_of lthy; val ({names, ...}, {raw_induct, intrs, elims, ...}) = Inductive.the_inductive_global lthy (Sign.intern_const thy s); val raw_induct = atomize_induct lthy raw_induct; val elims = map (atomize_induct lthy) elims; val intrs = map (atomize_intr lthy) intrs; val monos = Inductive.get_monos lthy; val intrs' = Inductive.unpartition_rules intrs (map (fn (((s, ths), (_, k)), th) => (s, ths ~~ Inductive.infer_intro_vars thy th k ths)) (Inductive.partition_rules raw_induct intrs ~~ Inductive.arities_of raw_induct ~~ elims)); val k = length (Inductive.params_of raw_induct); val atoms' = NominalAtoms.atoms_of thy; val atoms = if null xatoms then atoms' else let val atoms = map (Sign.intern_type thy) xatoms in (case duplicates op = atoms of [] => () | xs => error ("Duplicate atoms: " ^ commas xs); case subtract (op =) atoms' atoms of [] => () | xs => error ("No such atoms: " ^ commas xs); atoms) end; val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp"; val (([t], [pi]), ctxt1) = lthy |> Variable.import_terms false [Thm.concl_of raw_induct] ||>> Variable.variant_fixes ["pi"]; fun eqvt_simpset ctxt = put_simpset HOL_basic_ss ctxt addsimps (NominalThmDecls.get_eqvt_thms ctxt @ perm_pi_simp) addsimprocs [mk_perm_bool_simproc names, NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]; val ps = map (fst o HOLogic.dest_imp) (HOLogic.dest_conj (HOLogic.dest_Trueprop t)); fun eqvt_tac ctxt pi (intr, vs) st = let fun eqvt_err s = let val ([t], ctxt') = Variable.import_terms true [Thm.prop_of intr] ctxt in error ("Could not prove equivariance for introduction rule\n" ^ Syntax.string_of_term ctxt' t ^ "\n" ^ s) end; val res = SUBPROOF (fn {context = ctxt'', prems, params, ...} => let val prems' = map (fn th => the_default th (map_thm ctxt'' (split_conj (K I) names) (eresolve_tac ctxt'' [conjunct2] 1) monos NONE th)) prems; val prems'' = map (fn th => Simplifier.simplify (eqvt_simpset ctxt'') (mk_perm_bool ctxt'' (Thm.cterm_of ctxt'' pi) th)) prems'; val intr' = infer_instantiate ctxt'' (map (#1 o dest_Var) vs ~~ map (Thm.cterm_of ctxt'' o NominalDatatype.mk_perm [] pi o Thm.term_of o #2) params) intr in (resolve_tac ctxt'' [intr'] THEN_ALL_NEW (TRY o resolve_tac ctxt'' prems'')) 1 end) ctxt 1 st in case (Seq.pull res handle THM (s, _, _) => eqvt_err s) of NONE => eqvt_err ("Rule does not match goal\n" ^ Syntax.string_of_term ctxt (hd (Thm.prems_of st))) | SOME (th, _) => Seq.single th end; val thss = map (fn atom => let val pi' = Free (pi, NominalAtoms.mk_permT (Type (atom, []))) in map (fn th => zero_var_indexes (th RS mp)) (Old_Datatype_Aux.split_conj_thm (Goal.prove ctxt1 [] [] (HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn p => let val (h, ts) = strip_comb p; val (ts1, ts2) = chop k ts in HOLogic.mk_imp (p, list_comb (h, ts1 @ map (NominalDatatype.mk_perm [] pi') ts2)) end) ps))) (fn {context = ctxt'', ...} => EVERY (resolve_tac ctxt'' [raw_induct] 1 :: map (fn intr_vs => full_simp_tac (eqvt_simpset ctxt'') 1 THEN eqvt_tac ctxt'' pi' intr_vs) intrs')) |> singleton (Proof_Context.export ctxt1 lthy))) end) atoms in lthy |> Local_Theory.notes (map (fn (name, ths) => ((Binding.qualified_name (Long_Name.qualify (Long_Name.base_name name) "eqvt"), [Attrib.internal (K NominalThmDecls.eqvt_add)]), [(ths, [])])) (names ~~ transp thss)) |> snd end; (* outer syntax *) val _ = Outer_Syntax.local_theory_to_proof \<^command_keyword>\nominal_inductive\ "prove equivariance and strong induction theorem for inductive predicate involving nominal datatypes" (Parse.name -- Scan.optional (\<^keyword>\avoids\ |-- Parse.and_list1 (Parse.name -- (\<^keyword>\:\ |-- Scan.repeat1 Parse.name))) [] >> (fn (name, avoids) => prove_strong_ind name avoids)); val _ = Outer_Syntax.local_theory \<^command_keyword>\equivariance\ "prove equivariance for inductive predicate involving nominal datatypes" (Parse.name -- Scan.optional (\<^keyword>\[\ |-- Parse.list1 Parse.name --| \<^keyword>\]\) [] >> (fn (name, atoms) => prove_eqvt name atoms)); end diff --git a/src/HOL/Nominal/nominal_inductive2.ML b/src/HOL/Nominal/nominal_inductive2.ML --- a/src/HOL/Nominal/nominal_inductive2.ML +++ b/src/HOL/Nominal/nominal_inductive2.ML @@ -1,500 +1,500 @@ (* Title: HOL/Nominal/nominal_inductive2.ML Author: Stefan Berghofer, TU Muenchen Infrastructure for proving equivariance and strong induction theorems for inductive predicates involving nominal datatypes. Experimental version that allows to avoid lists of atoms. *) signature NOMINAL_INDUCTIVE2 = sig val prove_strong_ind: string -> string option -> (string * string list) list -> local_theory -> Proof.state end structure NominalInductive2 : NOMINAL_INDUCTIVE2 = struct val inductive_forall_def = @{thm HOL.induct_forall_def}; val inductive_atomize = @{thms induct_atomize}; val inductive_rulify = @{thms induct_rulify}; fun rulify_term thy = Raw_Simplifier.rewrite_term thy inductive_rulify []; fun atomize_conv ctxt = Raw_Simplifier.rewrite_cterm (true, false, false) (K (K NONE)) (put_simpset HOL_basic_ss ctxt addsimps inductive_atomize); fun atomize_intr ctxt = Conv.fconv_rule (Conv.prems_conv ~1 (atomize_conv ctxt)); fun atomize_induct ctxt = Conv.fconv_rule (Conv.prems_conv ~1 (Conv.params_conv ~1 (K (Conv.prems_conv ~1 (atomize_conv ctxt))) ctxt)); fun fresh_postprocess ctxt = Simplifier.full_simplify (put_simpset HOL_basic_ss ctxt addsimps [@{thm fresh_star_set_eq}, @{thm fresh_star_Un_elim}, @{thm fresh_star_insert_elim}, @{thm fresh_star_empty_elim}]); fun preds_of ps t = inter (op = o apsnd dest_Free) ps (Term.add_frees t []); val perm_bool = mk_meta_eq @{thm perm_bool_def}; val perm_boolI = @{thm perm_boolI}; val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb (Drule.strip_imp_concl (Thm.cprop_of perm_boolI)))); fun mk_perm_bool ctxt pi th = th RS infer_instantiate ctxt [(#1 (dest_Var (Thm.term_of perm_boolI_pi)), pi)] perm_boolI; fun mk_perm_bool_simproc names = Simplifier.make_simproc \<^context> "perm_bool" {lhss = [\<^term>\perm pi x\], proc = fn _ => fn _ => fn ct => (case Thm.term_of ct of Const (\<^const_name>\Nominal.perm\, _) $ _ $ t => if member (op =) names (the_default "" (try (head_of #> dest_Const #> fst) t)) then SOME perm_bool else NONE | _ => NONE)}; fun transp ([] :: _) = [] | transp xs = map hd xs :: transp (map tl xs); fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of (Const (s, T), ts) => (case strip_type T of (Ts, Type (tname, _)) => (case NominalDatatype.get_nominal_datatype thy tname of NONE => fold (add_binders thy i) ts bs | SOME {descr, index, ...} => (case AList.lookup op = (#3 (the (AList.lookup op = descr index))) s of NONE => fold (add_binders thy i) ts bs | SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') => let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs' in (add_binders thy i u (fold (fn (u, T) => if exists (fn j => j < i) (loose_bnos u) then I else AList.map_default op = (T, []) (insert op aconv (incr_boundvars (~i) u))) cargs1 bs'), cargs2) end) cargs (bs, ts ~~ Ts)))) | _ => fold (add_binders thy i) ts bs) | (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs)) | add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs | add_binders thy i _ bs = bs; fun split_conj f names (Const (\<^const_name>\HOL.conj\, _) $ p $ q) _ = (case head_of p of Const (name, _) => if member (op =) names name then SOME (f p q) else NONE | _ => NONE) | split_conj _ _ _ _ = NONE; fun strip_all [] t = t | strip_all (_ :: xs) (Const (\<^const_name>\All\, _) $ Abs (s, T, t)) = strip_all xs t; (*********************************************************************) (* maps R ... & (ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t)) *) (* or ALL pi_1 ... pi_n z. P z (pi_1 o ... o pi_n o t) *) (* to R ... & id (ALL z. P z (pi_1 o ... o pi_n o t)) *) (* or id (ALL z. P z (pi_1 o ... o pi_n o t)) *) (* *) (* where "id" protects the subformula from simplification *) (*********************************************************************) fun inst_conj_all names ps pis (Const (\<^const_name>\HOL.conj\, _) $ p $ q) _ = (case head_of p of Const (name, _) => if member (op =) names name then SOME (HOLogic.mk_conj (p, Const (\<^const_name>\Fun.id\, HOLogic.boolT --> HOLogic.boolT) $ (subst_bounds (pis, strip_all pis q)))) else NONE | _ => NONE) | inst_conj_all names ps pis t u = if member (op aconv) ps (head_of u) then SOME (Const (\<^const_name>\Fun.id\, HOLogic.boolT --> HOLogic.boolT) $ (subst_bounds (pis, strip_all pis t))) else NONE | inst_conj_all _ _ _ _ _ = NONE; fun inst_conj_all_tac ctxt k = EVERY [TRY (EVERY [eresolve_tac ctxt [conjE] 1, resolve_tac ctxt [conjI] 1, assume_tac ctxt 1]), REPEAT_DETERM_N k (eresolve_tac ctxt [allE] 1), simp_tac (put_simpset HOL_basic_ss ctxt addsimps [@{thm id_apply}]) 1]; fun map_term f t u = (case f t u of NONE => map_term' f t u | x => x) and map_term' f (t $ u) (t' $ u') = (case (map_term f t t', map_term f u u') of (NONE, NONE) => NONE | (SOME t'', NONE) => SOME (t'' $ u) | (NONE, SOME u'') => SOME (t $ u'') | (SOME t'', SOME u'') => SOME (t'' $ u'')) | map_term' f (Abs (s, T, t)) (Abs (s', T', t')) = (case map_term f t t' of NONE => NONE | SOME t'' => SOME (Abs (s, T, t''))) | map_term' _ _ _ = NONE; (*********************************************************************) (* Prove F[f t] from F[t], where F is monotone *) (*********************************************************************) fun map_thm ctxt f tac monos opt th = let val prop = Thm.prop_of th; fun prove t = Goal.prove ctxt [] [] t (fn _ => EVERY [cut_facts_tac [th] 1, eresolve_tac ctxt [rev_mp] 1, REPEAT_DETERM (FIRSTGOAL (resolve_tac ctxt monos)), REPEAT_DETERM (resolve_tac ctxt [impI] 1 THEN (assume_tac ctxt 1 ORELSE tac))]) in Option.map prove (map_term f prop (the_default prop opt)) end; fun abs_params params t = let val vs = map (Var o apfst (rpair 0)) (Term.rename_wrt_term t params) in (Logic.list_all (params, t), (rev vs, subst_bounds (vs, t))) end; fun inst_params thy (vs, p) th cts = let val env = Pattern.first_order_match thy (p, Thm.prop_of th) (Vartab.empty, Vartab.empty) in Thm.instantiate (TVars.empty, Vars.make (map (dest_Var o Envir.subst_term env) vs ~~ cts)) th end; fun prove_strong_ind s alt_name avoids ctxt = let val thy = Proof_Context.theory_of ctxt; val ({names, ...}, {raw_induct, intrs, elims, ...}) = Inductive.the_inductive_global ctxt (Sign.intern_const thy s); val ind_params = Inductive.params_of raw_induct; val raw_induct = atomize_induct ctxt raw_induct; val elims = map (atomize_induct ctxt) elims; val monos = Inductive.get_monos ctxt; val eqvt_thms = NominalThmDecls.get_eqvt_thms ctxt; val _ = (case subtract (op =) (fold (Term.add_const_names o Thm.prop_of) eqvt_thms []) names of [] => () | xs => error ("Missing equivariance theorem for predicate(s): " ^ commas_quote xs)); val induct_cases = map (fst o fst) (fst (Rule_Cases.get (the (Induct.lookup_inductP ctxt (hd names))))); val induct_cases' = if null induct_cases then replicate (length intrs) "" else induct_cases; val (raw_induct', ctxt') = ctxt |> yield_singleton (Variable.import_terms false) (Thm.prop_of raw_induct); val concls = raw_induct' |> Logic.strip_imp_concl |> HOLogic.dest_Trueprop |> HOLogic.dest_conj |> map (HOLogic.dest_imp ##> strip_comb); val ps = map (fst o snd) concls; val _ = (case duplicates (op = o apply2 fst) avoids of [] => () | xs => error ("Duplicate case names: " ^ commas_quote (map fst xs))); val _ = (case subtract (op =) induct_cases (map fst avoids) of [] => () | xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs)); fun mk_avoids params name sets = let val (_, ctxt') = Proof_Context.add_fixes (map (fn (s, T) => (Binding.name s, SOME T, NoSyn)) params) ctxt; fun mk s = let val t = Syntax.read_term ctxt' s; val t' = fold_rev absfree params t |> funpow (length params) (fn Abs (_, _, t) => t) in (t', HOLogic.dest_setT (fastype_of t)) end handle TERM _ => error ("Expression " ^ quote s ^ " to be avoided in case " ^ quote name ^ " is not a set type"); fun add_set p [] = [p] | add_set (t, T) ((u, U) :: ps) = if T = U then let val S = HOLogic.mk_setT T in (Const (\<^const_name>\sup\, S --> S --> S) $ u $ t, T) :: ps end else (u, U) :: add_set (t, T) ps in fold (mk #> add_set) sets [] end; val prems = map (fn (prem, name) => let val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem); val concl = incr_boundvars 1 (Logic.strip_assums_concl prem); val params = Logic.strip_params prem in (params, if null avoids then map (fn (T, ts) => (HOLogic.mk_set T ts, T)) (fold (add_binders thy 0) (prems @ [concl]) []) else case AList.lookup op = avoids name of NONE => [] | SOME sets => map (apfst (incr_boundvars 1)) (mk_avoids params name sets), prems, strip_comb (HOLogic.dest_Trueprop concl)) end) (Logic.strip_imp_prems raw_induct' ~~ induct_cases'); val atomTs = distinct op = (maps (map snd o #2) prems); val atoms = map (fst o dest_Type) atomTs; val ind_sort = if null atomTs then \<^sort>\type\ else Sign.minimize_sort thy (Sign.certify_sort thy (map (fn a => Sign.intern_class thy ("fs_" ^ Long_Name.base_name a)) atoms)); val (fs_ctxt_tyname, _) = Name.variant "'n" (Variable.names_of ctxt'); val ([fs_ctxt_name], ctxt'') = Variable.variant_fixes ["z"] ctxt'; val fsT = TFree (fs_ctxt_tyname, ind_sort); val inductive_forall_def' = Thm.instantiate' [SOME (Thm.global_ctyp_of thy fsT)] [] inductive_forall_def; fun lift_pred' t (Free (s, T)) ts = list_comb (Free (s, fsT --> T), t :: ts); val lift_pred = lift_pred' (Bound 0); fun lift_prem (t as (f $ u)) = let val (p, ts) = strip_comb t in if member (op =) ps p then HOLogic.mk_induct_forall fsT $ Abs ("z", fsT, lift_pred p (map (incr_boundvars 1) ts)) else lift_prem f $ lift_prem u end | lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t) | lift_prem t = t; fun mk_fresh (x, T) = HOLogic.mk_Trueprop (NominalDatatype.fresh_star_const T fsT $ x $ Bound 0); val (prems', prems'') = split_list (map (fn (params, sets, prems, (p, ts)) => let val params' = params @ [("y", fsT)]; val prem = Logic.list_implies (map mk_fresh sets @ map (fn prem => if null (preds_of ps prem) then prem else lift_prem prem) prems, HOLogic.mk_Trueprop (lift_pred p ts)); in abs_params params' prem end) prems); val ind_vars = (Old_Datatype_Prop.indexify_names (replicate (length atomTs) "pi") ~~ map NominalAtoms.mk_permT atomTs) @ [("z", fsT)]; val ind_Ts = rev (map snd ind_vars); val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem, HOLogic.list_all (ind_vars, lift_pred p (map (fold_rev (NominalDatatype.mk_perm ind_Ts) (map Bound (length atomTs downto 1))) ts)))) concls)); val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem, lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls)); val (vc_compat, vc_compat') = map (fn (params, sets, prems, (p, ts)) => map (fn q => abs_params params (incr_boundvars ~1 (Logic.list_implies (map_filter (fn prem => if null (preds_of ps prem) then SOME prem else map_term (split_conj (K o I) names) prem prem) prems, q)))) (maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop (NominalDatatype.fresh_star_const U T $ u $ t)) sets) (ts ~~ binder_types (fastype_of p)) @ map (fn (u, U) => HOLogic.mk_Trueprop (Const (\<^const_name>\finite\, HOLogic.mk_setT U --> HOLogic.boolT) $ u)) sets) |> split_list) prems |> split_list; val perm_pi_simp = Global_Theory.get_thms thy "perm_pi_simp"; val pt2_atoms = map (fn a => Global_Theory.get_thm thy ("pt_" ^ Long_Name.base_name a ^ "2")) atoms; val eqvt_ss = simpset_of (put_simpset HOL_basic_ss (Proof_Context.init_global thy) addsimps (eqvt_thms @ perm_pi_simp @ pt2_atoms) addsimprocs [mk_perm_bool_simproc [\<^const_name>\Fun.id\], NominalPermeq.perm_simproc_app, NominalPermeq.perm_simproc_fun]); val fresh_star_bij = Global_Theory.get_thms thy "fresh_star_bij"; val pt_insts = map (NominalAtoms.pt_inst_of thy) atoms; val at_insts = map (NominalAtoms.at_inst_of thy) atoms; val dj_thms = maps (fn a => map (NominalAtoms.dj_thm_of thy a) (remove (op =) a atoms)) atoms; val finite_ineq = map2 (fn th => fn th' => th' RS (th RS @{thm pt_set_finite_ineq})) pt_insts at_insts; val perm_set_forget = map (fn th => th RS @{thm dj_perm_set_forget}) dj_thms; val perm_freshs_freshs = atomTs ~~ map2 (fn th => fn th' => th' RS (th RS @{thm pt_freshs_freshs})) pt_insts at_insts; fun obtain_fresh_name ts sets (T, fin) (freshs, ths1, ths2, ths3, ctxt) = let val thy = Proof_Context.theory_of ctxt; (** protect terms to avoid that fresh_star_prod_set interferes with **) (** pairs used in introduction rules of inductive predicate **) fun protect t = let val T = fastype_of t in Const (\<^const_name>\Fun.id\, T --> T) $ t end; val p = foldr1 HOLogic.mk_prod (map protect ts); val atom = fst (dest_Type T); val {at_inst, ...} = NominalAtoms.the_atom_info thy atom; val fs_atom = Global_Theory.get_thm thy ("fs_" ^ Long_Name.base_name atom ^ "1"); val avoid_th = Thm.instantiate' [SOME (Thm.global_ctyp_of thy (fastype_of p))] [SOME (Thm.global_cterm_of thy p)] ([at_inst, fin, fs_atom] MRS @{thm at_set_avoiding}); val (([(_, cx)], th1 :: th2 :: ths), ctxt') = Obtain.result (fn ctxt' => EVERY [resolve_tac ctxt' [avoid_th] 1, full_simp_tac (put_simpset HOL_ss ctxt' addsimps [@{thm fresh_star_prod_set}]) 1, full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps [@{thm id_apply}]) 1, rotate_tac 1 1, REPEAT (eresolve_tac ctxt' [conjE] 1)]) [] ctxt; val (Ts1, _ :: Ts2) = chop_prefix (not o equal T) (map snd sets); val pTs = map NominalAtoms.mk_permT (Ts1 @ Ts2); val (pis1, pis2) = chop (length Ts1) (map Bound (length pTs - 1 downto 0)); val _ $ (f $ (_ $ pi $ l) $ r) = Thm.prop_of th2 val th2' = Goal.prove ctxt' [] [] (Logic.list_all (map (pair "pi") pTs, HOLogic.mk_Trueprop (f $ fold_rev (NominalDatatype.mk_perm (rev pTs)) (pis1 @ pi :: pis2) l $ r))) (fn _ => cut_facts_tac [th2] 1 THEN full_simp_tac (put_simpset HOL_basic_ss ctxt' addsimps perm_set_forget) 1) |> Simplifier.simplify (put_simpset eqvt_ss ctxt') in (freshs @ [Thm.term_of cx], ths1 @ ths, ths2 @ [th1], ths3 @ [th2'], ctxt') end; fun mk_ind_proof ctxt' thss = Goal.prove ctxt' [] prems' concl' (fn {prems = ihyps, context = ctxt} => let val th = Goal.prove ctxt [] [] concl (fn {context, ...} => resolve_tac ctxt [raw_induct] 1 THEN EVERY (maps (fn (((((_, sets, oprems, _), vc_compat_ths), vc_compat_vs), ihyp), vs_ihypt) => [REPEAT (resolve_tac ctxt [allI] 1), simp_tac (put_simpset eqvt_ss context) 1, SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} => let val (cparams', (pis, z)) = chop (length params - length atomTs - 1) (map #2 params) ||> (map Thm.term_of #> split_last); val params' = map Thm.term_of cparams' val sets' = map (apfst (curry subst_bounds (rev params'))) sets; val pi_sets = map (fn (t, _) => fold_rev (NominalDatatype.mk_perm []) pis t) sets'; val (P, ts) = strip_comb (HOLogic.dest_Trueprop (Thm.term_of concl)); val gprems1 = map_filter (fn (th, t) => if null (preds_of ps t) then SOME th else map_thm ctxt' (split_conj (K o I) names) (eresolve_tac ctxt' [conjunct1] 1) monos NONE th) (gprems ~~ oprems); val vc_compat_ths' = map2 (fn th => fn p => let val th' = gprems1 MRS inst_params thy p th cparams'; val (h, ts) = strip_comb (HOLogic.dest_Trueprop (Thm.concl_of th')) in Goal.prove ctxt' [] [] (HOLogic.mk_Trueprop (list_comb (h, map (fold_rev (NominalDatatype.mk_perm []) pis) ts))) (fn _ => simp_tac (put_simpset HOL_basic_ss ctxt' addsimps (fresh_star_bij @ finite_ineq)) 1 THEN resolve_tac ctxt' [th'] 1) end) vc_compat_ths vc_compat_vs; val (vc_compat_ths1, vc_compat_ths2) = chop (length vc_compat_ths - length sets) vc_compat_ths'; val vc_compat_ths1' = map (Conv.fconv_rule (Conv.arg_conv (Conv.arg_conv (Simplifier.rewrite (put_simpset eqvt_ss ctxt'))))) vc_compat_ths1; val (pis', fresh_ths1, fresh_ths2, fresh_ths3, ctxt'') = fold (obtain_fresh_name ts sets) (map snd sets' ~~ vc_compat_ths2) ([], [], [], [], ctxt'); fun concat_perm pi1 pi2 = let val T = fastype_of pi1 in if T = fastype_of pi2 then Const (\<^const_name>\append\, T --> T --> T) $ pi1 $ pi2 else pi2 end; val pis'' = fold_rev (concat_perm #> map) pis' pis; val ihyp' = inst_params thy vs_ihypt ihyp (map (fold_rev (NominalDatatype.mk_perm []) (pis' @ pis) #> Thm.global_cterm_of thy) params' @ [Thm.global_cterm_of thy z]); fun mk_pi th = Simplifier.simplify (put_simpset HOL_basic_ss ctxt' addsimps [@{thm id_apply}] addsimprocs [NominalDatatype.perm_simproc]) (Simplifier.simplify (put_simpset eqvt_ss ctxt') (fold_rev (mk_perm_bool ctxt' o Thm.cterm_of ctxt') (pis' @ pis) th)); val gprems2 = map (fn (th, t) => if null (preds_of ps t) then mk_pi th else mk_pi (the (map_thm ctxt' (inst_conj_all names ps (rev pis'')) (inst_conj_all_tac ctxt' (length pis'')) monos (SOME t) th))) (gprems ~~ oprems); val perm_freshs_freshs' = map (fn (th, (_, T)) => th RS the (AList.lookup op = perm_freshs_freshs T)) (fresh_ths2 ~~ sets); val th = Goal.prove ctxt'' [] [] (HOLogic.mk_Trueprop (list_comb (P $ hd ts, map (fold_rev (NominalDatatype.mk_perm []) pis') (tl ts)))) (fn _ => EVERY ([simp_tac (put_simpset eqvt_ss ctxt'') 1, resolve_tac ctxt'' [ihyp'] 1] @ map (fn th => resolve_tac ctxt'' [th] 1) fresh_ths3 @ [REPEAT_DETERM_N (length gprems) (simp_tac (put_simpset HOL_basic_ss ctxt'' addsimps [inductive_forall_def'] addsimprocs [NominalDatatype.perm_simproc]) 1 THEN resolve_tac ctxt'' gprems2 1)])); val final = Goal.prove ctxt'' [] [] (Thm.term_of concl) (fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (put_simpset HOL_ss ctxt'' addsimps vc_compat_ths1' @ fresh_ths1 @ perm_freshs_freshs') 1); val final' = Proof_Context.export ctxt'' ctxt' [final]; in resolve_tac ctxt' final' 1 end) context 1]) (prems ~~ thss ~~ vc_compat' ~~ ihyps ~~ prems''))) in cut_facts_tac [th] 1 THEN REPEAT (eresolve_tac ctxt' [conjE] 1) THEN REPEAT (REPEAT (resolve_tac ctxt' [conjI, impI] 1) THEN eresolve_tac ctxt' [impE] 1 THEN assume_tac ctxt' 1 THEN REPEAT (eresolve_tac ctxt' @{thms allE_Nil} 1) THEN asm_full_simp_tac ctxt 1) end) |> fresh_postprocess ctxt' |> singleton (Proof_Context.export ctxt' ctxt); in ctxt'' |> - Proof.theorem NONE (fn thss => fn ctxt => (* FIXME ctxt/ctxt' should be called lthy/lthy' *) + Proof.theorem NONE (fn thss => fn lthy1 => let val rec_name = space_implode "_" (map Long_Name.base_name names); val rec_qualified = Binding.qualify false rec_name; val ind_case_names = Rule_Cases.case_names induct_cases; val induct_cases' = Inductive.partition_rules' raw_induct (intrs ~~ induct_cases); - val thss' = map (map (atomize_intr ctxt)) thss; + val thss' = map (map (atomize_intr lthy1)) thss; val thsss = Inductive.partition_rules' raw_induct (intrs ~~ thss'); val strong_raw_induct = - mk_ind_proof ctxt thss' |> Inductive.rulify ctxt; + mk_ind_proof lthy1 thss' |> Inductive.rulify lthy1; val strong_induct_atts = map (Attrib.internal o K) [ind_case_names, Rule_Cases.consumes (~ (Thm.nprems_of strong_raw_induct))]; val strong_induct = if length names > 1 then strong_raw_induct else strong_raw_induct RSN (2, rev_mp); val (induct_name, inducts_name) = case alt_name of NONE => (rec_qualified (Binding.name "strong_induct"), rec_qualified (Binding.name "strong_inducts")) | SOME s => (Binding.name s, Binding.name (s ^ "s")); - val ((_, [strong_induct']), ctxt') = ctxt |> Local_Theory.note + val ((_, [strong_induct']), lthy2) = lthy1 |> Local_Theory.note ((induct_name, strong_induct_atts), [strong_induct]); val strong_inducts = - Project_Rule.projects ctxt' (1 upto length names) strong_induct' + Project_Rule.projects lthy2 (1 upto length names) strong_induct' in - ctxt' |> + lthy2 |> Local_Theory.notes [((inducts_name, []), strong_inducts |> map (fn th => ([th], [Attrib.internal (K ind_case_names), Attrib.internal (K (Rule_Cases.consumes (1 - Thm.nprems_of th)))])))] |> snd end) (map (map (rulify_term thy #> rpair [])) vc_compat) end; (* outer syntax *) val _ = Outer_Syntax.local_theory_to_proof \<^command_keyword>\nominal_inductive2\ "prove strong induction theorem for inductive predicate involving nominal datatypes" (Parse.name -- Scan.option (\<^keyword>\(\ |-- Parse.!!! (Parse.name --| \<^keyword>\)\)) -- (Scan.optional (\<^keyword>\avoids\ |-- Parse.enum1 "|" (Parse.name -- (\<^keyword>\:\ |-- Parse.and_list1 Parse.term))) []) >> (fn ((name, rule_name), avoids) => prove_strong_ind name rule_name avoids)); end