author  berghofe 
Wed, 28 Mar 2007 19:18:39 +0200  
changeset 22544  549615dcd4f2 
parent 22530  c192c5d1a6f2 
child 22730  8bcc8809ed3b 
permissions  rwrr 
22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

1 
(* Title: HOL/Nominal/nominal_inductive.ML 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

2 
ID: $Id$ 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

3 
Author: Stefan Berghofer, TU Muenchen 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

4 

22530  5 
Infrastructure for proving equivariance and strong induction theorems 
6 
for inductive predicates involving nominal datatypes. 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

7 
*) 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

8 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

9 
signature NOMINAL_INDUCTIVE = 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

10 
sig 
22530  11 
val nominal_inductive: string > (string * string list) list > theory > Proof.state 
12 
val equivariance: string > theory > theory 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

13 
end 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

14 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

15 
structure NominalInductive : NOMINAL_INDUCTIVE = 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

16 
struct 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

17 

22530  18 
val finite_Un = thm "finite_Un"; 
19 
val supp_prod = thm "supp_prod"; 

20 
val fresh_prod = thm "fresh_prod"; 

21 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

22 
val perm_boolI = thm "perm_boolI"; 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

23 
val (_, [perm_boolI_pi, _]) = Drule.strip_comb (snd (Thm.dest_comb 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

24 
(Drule.strip_imp_concl (cprop_of perm_boolI)))); 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

25 

22530  26 
val allE_Nil = read_instantiate_sg (the_context()) [("x", "[]")] allE; 
27 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

28 
fun transp ([] :: _) = [] 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

29 
 transp xs = map hd xs :: transp (map tl xs); 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

30 

22530  31 
fun add_binders thy i (t as (_ $ _)) bs = (case strip_comb t of 
32 
(Const (s, T), ts) => (case strip_type T of 

33 
(Ts, Type (tname, _)) => 

34 
(case NominalPackage.get_nominal_datatype thy tname of 

35 
NONE => fold (add_binders thy i) ts bs 

36 
 SOME {descr, index, ...} => (case AList.lookup op = 

37 
(#3 (the (AList.lookup op = descr index))) s of 

38 
NONE => fold (add_binders thy i) ts bs 

39 
 SOME cargs => fst (fold (fn (xs, x) => fn (bs', cargs') => 

40 
let val (cargs1, (u, _) :: cargs2) = chop (length xs) cargs' 

41 
in (add_binders thy i u 

42 
(fold (fn (u, T) => 

43 
if exists (fn j => j < i) (loose_bnos u) then I 

44 
else insert (op aconv o pairself fst) 

45 
(incr_boundvars (~i) u, T)) cargs1 bs'), cargs2) 

46 
end) cargs (bs, ts ~~ Ts)))) 

47 
 _ => fold (add_binders thy i) ts bs) 

48 
 (u, ts) => add_binders thy i u (fold (add_binders thy i) ts bs)) 

49 
 add_binders thy i (Abs (_, _, t)) bs = add_binders thy (i + 1) t bs 

50 
 add_binders thy i _ bs = bs; 

51 

52 
fun prove_strong_ind raw_induct names avoids thy = 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

53 
let 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

54 
val ctxt = ProofContext.init thy; 
22530  55 
val induct_cases = map fst (fst (RuleCases.get (the 
56 
(InductAttrib.lookup_inductS ctxt (hd names))))); 

57 
val raw_induct' = Logic.unvarify (prop_of raw_induct); 

58 
val concls = raw_induct' > Logic.strip_imp_concl > HOLogic.dest_Trueprop > 

59 
HOLogic.dest_conj > map (HOLogic.dest_imp ##> strip_comb); 

60 
val ps = map (fst o snd) concls; 

61 

62 
val _ = (case duplicates (op = o pairself fst) avoids of 

63 
[] => () 

64 
 xs => error ("Duplicate case names: " ^ commas_quote (map fst xs))); 

65 
val _ = assert_all (null o duplicates op = o snd) avoids 

66 
(fn (a, _) => error ("Duplicate variable names for case " ^ quote a)); 

67 
val _ = (case map fst avoids \\ induct_cases of 

68 
[] => () 

69 
 xs => error ("No such case(s) in inductive definition: " ^ commas_quote xs)); 

70 
val avoids' = map (fn name => 

71 
(name, the_default [] (AList.lookup op = avoids name))) induct_cases; 

72 
fun mk_avoids params (name, ps) = 

73 
let val k = length params  1 

74 
in map (fn x => case find_index (equal x o fst) params of 

75 
~1 => error ("No such variable in case " ^ quote name ^ 

76 
" of inductive definition: " ^ quote x) 

77 
 i => (Bound (k  i), snd (nth params i))) ps 

78 
end; 

79 

80 
val prems = map (fn (prem, avoid) => 

81 
let 

82 
val prems = map (incr_boundvars 1) (Logic.strip_assums_hyp prem); 

83 
val concl = incr_boundvars 1 (Logic.strip_assums_concl prem); 

84 
val params = Logic.strip_params prem 

85 
in 

86 
(params, 

87 
fold (add_binders thy 0) (prems @ [concl]) [] @ 

88 
map (apfst (incr_boundvars 1)) (mk_avoids params avoid), 

89 
prems, strip_comb (HOLogic.dest_Trueprop concl)) 

90 
end) (Logic.strip_imp_prems raw_induct' ~~ avoids'); 

91 

92 
val atomTs = distinct op = (maps (map snd o #2) prems); 

93 
val ind_sort = if null atomTs then HOLogic.typeS 

94 
else Sign.certify_sort thy (map (fn T => Sign.intern_class thy 

95 
("fs_" ^ Sign.base_name (fst (dest_Type T)))) atomTs); 

96 
val fs_ctxt_tyname = Name.variant (map fst (term_tfrees raw_induct')) "'n"; 

97 
val fs_ctxt_name = Name.variant (add_term_names (raw_induct', [])) "z"; 

98 
val fsT = TFree (fs_ctxt_tyname, ind_sort); 

99 

100 
fun lift_pred' t (Free (s, T)) ts = 

101 
list_comb (Free (s, fsT > T), t :: ts); 

102 
val lift_pred = lift_pred' (Bound 0); 

103 

104 
fun lift_prem (Const ("Trueprop", _) $ t) = 

105 
let val (u, ts) = strip_comb t 

106 
in 

107 
if u mem ps then 

108 
all fsT $ Abs ("z", fsT, HOLogic.mk_Trueprop 

109 
(lift_pred u (map (incr_boundvars 1) ts))) 

110 
else HOLogic.mk_Trueprop (lift_prem t) 

111 
end 

112 
 lift_prem (t as (f $ u)) = 

113 
let val (p, ts) = strip_comb t 

114 
in 

115 
if p mem ps then 

116 
HOLogic.all_const fsT $ Abs ("z", fsT, 

117 
lift_pred p (map (incr_boundvars 1) ts)) 

118 
else lift_prem f $ lift_prem u 

119 
end 

120 
 lift_prem (Abs (s, T, t)) = Abs (s, T, lift_prem t) 

121 
 lift_prem t = t; 

122 

123 
fun mk_distinct [] = [] 

124 
 mk_distinct ((x, T) :: xs) = List.mapPartial (fn (y, U) => 

125 
if T = U then SOME (HOLogic.mk_Trueprop 

126 
(HOLogic.mk_not (HOLogic.eq_const T $ x $ y))) 

127 
else NONE) xs @ mk_distinct xs; 

128 

129 
fun mk_fresh (x, T) = HOLogic.mk_Trueprop 

130 
(Const ("Nominal.fresh", T > fsT > HOLogic.boolT) $ x $ Bound 0); 

131 

132 
val (prems', prems'') = split_list (map (fn (params, bvars, prems, (p, ts)) => 

133 
let 

134 
val params' = params @ [("y", fsT)]; 

135 
val prem = Logic.list_implies 

136 
(map mk_fresh bvars @ mk_distinct bvars @ 

137 
map (fn prem => 

138 
if null (term_frees prem inter ps) then prem 

139 
else lift_prem prem) prems, 

140 
HOLogic.mk_Trueprop (lift_pred p ts)); 

141 
val vs = map (Var o apfst (rpair 0)) (rename_wrt_term prem params') 

142 
in 

143 
(list_all (params', prem), (rev vs, subst_bounds (vs, prem))) 

144 
end) prems); 

145 

146 
val ind_vars = 

147 
(DatatypeProp.indexify_names (replicate (length atomTs) "pi") ~~ 

148 
map NominalAtoms.mk_permT atomTs) @ [("z", fsT)]; 

149 
val ind_Ts = rev (map snd ind_vars); 

150 

151 
val concl = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj 

152 
(map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem, 

153 
HOLogic.list_all (ind_vars, lift_pred p 

154 
(map (fold_rev (NominalPackage.mk_perm ind_Ts) 

155 
(map Bound (length atomTs downto 1))) ts)))) concls)); 

156 

157 
val concl' = HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj 

158 
(map (fn (prem, (p, ts)) => HOLogic.mk_imp (prem, 

159 
lift_pred' (Free (fs_ctxt_name, fsT)) p ts)) concls)); 

160 

161 
val vc_compat = map (fn (params, bvars, prems, (p, ts)) => 

162 
map (fn q => list_all (params, incr_boundvars ~1 (Logic.list_implies 

163 
(filter (fn prem => null (ps inter term_frees prem)) prems, q)))) 

164 
(mk_distinct bvars @ 

165 
maps (fn (t, T) => map (fn (u, U) => HOLogic.mk_Trueprop 

166 
(Const ("Nominal.fresh", U > T > HOLogic.boolT) $ u $ t)) bvars) 

167 
(ts ~~ binder_types (fastype_of p)))) prems; 

168 

169 
val eqvt_ss = HOL_basic_ss addsimps NominalThmDecls.get_eqvt_thms thy; 

170 
val fresh_bij = PureThy.get_thms thy (Name "fresh_bij"); 

171 
val perm_bij = PureThy.get_thms thy (Name "perm_bij"); 

172 
val fs_atoms = map (fn aT => PureThy.get_thm thy 

173 
(Name ("fs_" ^ Sign.base_name (fst (dest_Type aT)) ^ "1"))) atomTs; 

174 
val exists_fresh' = PureThy.get_thms thy (Name "exists_fresh'"); 

175 
val fresh_atm = PureThy.get_thms thy (Name "fresh_atm"); 

176 
val calc_atm = PureThy.get_thms thy (Name "calc_atm"); 

177 
val perm_fresh_fresh = PureThy.get_thms thy (Name "perm_fresh_fresh"); 

178 
val pt2_atoms = map (fn aT => PureThy.get_thm thy 

179 
(Name ("pt_" ^ Sign.base_name (fst (dest_Type aT)) ^ "2")) RS sym) atomTs; 

180 

181 
fun obtain_fresh_name ts T (freshs1, freshs2, ctxt) = 

182 
let 

183 
(** protect terms to avoid that supp_prod interferes with **) 

184 
(** pairs used in introduction rules of inductive predicate **) 

185 
fun protect t = 

186 
let val T = fastype_of t in Const ("Fun.id", T > T) $ t end; 

187 
val p = foldr1 HOLogic.mk_prod (map protect ts @ freshs1); 

188 
val ex = Goal.prove ctxt [] [] (HOLogic.mk_Trueprop 

189 
(HOLogic.exists_const T $ Abs ("x", T, 

190 
Const ("Nominal.fresh", T > fastype_of p > HOLogic.boolT) $ 

191 
Bound 0 $ p))) 

192 
(fn _ => EVERY 

193 
[resolve_tac exists_fresh' 1, 

194 
simp_tac (HOL_ss addsimps (supp_prod :: finite_Un :: fs_atoms)) 1]); 

195 
val (([cx], ths), ctxt') = Obtain.result 

196 
(fn _ => EVERY 

197 
[etac exE 1, 

198 
full_simp_tac (HOL_ss addsimps (fresh_prod :: fresh_atm)) 1, 

199 
full_simp_tac (HOL_basic_ss addsimps [id_apply]) 1, 

200 
REPEAT (etac conjE 1)]) 

201 
[ex] ctxt 

202 
in (freshs1 @ [term_of cx], freshs2 @ ths, ctxt') end; 

203 

204 
fun mk_proof thy thss = 

205 
let val ctxt = ProofContext.init thy 

206 
in Goal.prove_global thy [] prems' concl' (fn ihyps => 

207 
let val th = Goal.prove ctxt [] [] concl (fn {context, ...} => 

208 
rtac raw_induct 1 THEN 

209 
EVERY (maps (fn ((((_, bvars, oprems, _), vc_compat_ths), ihyp), (vs, ihypt)) => 

210 
[REPEAT (rtac allI 1), simp_tac eqvt_ss 1, 

211 
SUBPROOF (fn {prems = gprems, params, concl, context = ctxt', ...} => 

212 
let 

213 
val (params', (pis, z)) = 

214 
chop (length params  length atomTs  1) (map term_of params) > 

215 
split_last; 

216 
val bvars' = map 

217 
(fn (Bound i, T) => (nth params' (length params'  i), T) 

218 
 (t, T) => (t, T)) bvars; 

219 
val pi_bvars = map (fn (t, _) => 

220 
fold_rev (NominalPackage.mk_perm []) pis t) bvars'; 

221 
val (P, ts) = strip_comb (HOLogic.dest_Trueprop (term_of concl)); 

222 
val (freshs1, freshs2, ctxt'') = fold 

223 
(obtain_fresh_name (ts @ pi_bvars)) 

224 
(map snd bvars') ([], [], ctxt'); 

225 
val freshs2' = NominalPackage.mk_not_sym freshs2; 

226 
val pis' = map NominalPackage.perm_of_pair (pi_bvars ~~ freshs1); 

227 
val env = Pattern.first_order_match thy (ihypt, prop_of ihyp) 

228 
(Vartab.empty, Vartab.empty); 

229 
val ihyp' = Thm.instantiate ([], map (pairself (cterm_of thy)) 

230 
(map (Envir.subst_vars env) vs ~~ 

231 
map (fold_rev (NominalPackage.mk_perm []) 

232 
(rev pis' @ pis)) params' @ [z])) ihyp; 

233 
val (gprems1, gprems2) = pairself (map fst) (List.partition 

234 
(fn (th, t) => null (term_frees t inter ps)) (gprems ~~ oprems)); 

235 
val vc_compat_ths' = map (fn th => 

236 
let 

237 
val th' = gprems1 MRS 

238 
Thm.instantiate (Thm.cterm_first_order_match 

239 
(Conjunction.mk_conjunction_list (cprems_of th), 

240 
Conjunction.mk_conjunction_list (map cprop_of gprems1))) th; 

241 
val (bop, lhs, rhs) = (case concl_of th' of 

242 
_ $ (fresh $ lhs $ rhs) => 

243 
(fn t => fn u => fresh $ t $ u, lhs, rhs) 

244 
 _ $ (_ $ (_ $ lhs $ rhs)) => 

245 
(curry (HOLogic.mk_not o HOLogic.mk_eq), lhs, rhs)); 

246 
val th'' = Goal.prove ctxt'' [] [] (HOLogic.mk_Trueprop 

247 
(bop (fold_rev (NominalPackage.mk_perm []) pis lhs) 

248 
(fold_rev (NominalPackage.mk_perm []) pis rhs))) 

249 
(fn _ => simp_tac (HOL_basic_ss addsimps 

250 
(fresh_bij @ perm_bij)) 1 THEN rtac th' 1) 

251 
in Simplifier.simplify (eqvt_ss addsimps fresh_atm) th'' end) 

252 
vc_compat_ths; 

253 
val vc_compat_ths'' = NominalPackage.mk_not_sym vc_compat_ths'; 

254 
val gprems1' = map (fn th => fold_rev (fn pi => fn th' => 

255 
Simplifier.simplify eqvt_ss (th' RS Drule.cterm_instantiate 

256 
[(perm_boolI_pi, cterm_of thy pi)] perm_boolI)) 

257 
(rev pis' @ pis) th) gprems1; 

258 
val gprems2' = map (Simplifier.simplify eqvt_ss) gprems2; 

259 
(** Since calc_atm simplifies (pi :: 'a prm) o (x :: 'b) to x **) 

260 
(** we have to presimplify the rewrite rules **) 

261 
val calc_atm_ss = HOL_ss addsimps calc_atm @ 

262 
map (Simplifier.simplify (HOL_ss addsimps calc_atm)) 

263 
(vc_compat_ths'' @ freshs2'); 

264 
val th = Goal.prove ctxt'' [] [] 

265 
(HOLogic.mk_Trueprop (list_comb (P $ hd ts, 

266 
map (fold (NominalPackage.mk_perm []) pis') (tl ts)))) 

267 
(fn _ => EVERY ([simp_tac eqvt_ss 1, rtac ihyp' 1, 

268 
REPEAT_DETERM_N (nprems_of ihyp  length gprems) 

269 
(simp_tac calc_atm_ss 1), 

270 
REPEAT_DETERM_N (length gprems) 

271 
(resolve_tac gprems1' 1 ORELSE 

272 
simp_tac (HOL_basic_ss addsimps pt2_atoms @ gprems2' 

273 
addsimprocs [NominalPackage.perm_simproc]) 1)])); 

274 
val final = Goal.prove ctxt'' [] [] (term_of concl) 

275 
(fn _ => cut_facts_tac [th] 1 THEN full_simp_tac (HOL_ss 

276 
addsimps vc_compat_ths'' @ freshs2' @ 

277 
perm_fresh_fresh @ fresh_atm) 1); 

278 
val final' = ProofContext.export ctxt'' ctxt' [final]; 

279 
in resolve_tac final' 1 end) context 1]) 

280 
(prems ~~ thss ~~ ihyps ~~ prems''))) 

281 
in 

282 
cut_facts_tac [th] 1 THEN REPEAT (etac conjE 1) THEN 

283 
REPEAT (REPEAT (resolve_tac [conjI, impI] 1) THEN 

284 
etac impE 1 THEN atac 1 THEN REPEAT (etac allE_Nil 1) THEN 

285 
asm_full_simp_tac (simpset_of thy) 1) 

286 
end) 

287 
end; 

288 

289 
in 

290 
thy > 

291 
ProofContext.init > 

292 
Proof.theorem_i NONE (fn thss => ProofContext.theory (fn thy => 

293 
let 

294 
val ctxt = ProofContext.init thy; 

295 
val rec_name = space_implode "_" (map Sign.base_name names); 

296 
val ind_case_names = RuleCases.case_names induct_cases; 

297 
val strong_raw_induct = mk_proof thy thss; 

298 
val strong_induct = 

299 
if length names > 1 then 

300 
(strong_raw_induct, [ind_case_names, RuleCases.consumes 0]) 

301 
else (strong_raw_induct RSN (2, rev_mp), 

302 
[ind_case_names, RuleCases.consumes 1]); 

303 
val ([strong_induct'], thy') = thy > 

304 
Theory.add_path rec_name > 

305 
PureThy.add_thms [(("strong_induct", #1 strong_induct), #2 strong_induct)]; 

306 
val strong_inducts = 

307 
ProjectRule.projects ctxt (1 upto length names) strong_induct' 

308 
in 

309 
thy' > 

310 
PureThy.add_thmss [(("strong_inducts", strong_inducts), 

311 
[ind_case_names, RuleCases.consumes 1])] > snd > 

312 
Theory.parent_path 

313 
end)) 

314 
(map (map (rpair [])) vc_compat) 

315 
end; 

316 

317 
fun prove_eqvt names raw_induct intrs thy = 

318 
let 

319 
val ctxt = ProofContext.init thy; 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

320 
val atoms = NominalAtoms.atoms_of thy; 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

321 
val eqvt_ss = HOL_basic_ss addsimps NominalThmDecls.get_eqvt_thms thy; 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

322 
val t = Logic.unvarify (concl_of raw_induct); 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

323 
val pi = Name.variant (add_term_names (t, [])) "pi"; 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

324 
val ps = map (fst o HOLogic.dest_imp) 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

325 
(HOLogic.dest_conj (HOLogic.dest_Trueprop t)); 
22544  326 
fun eqvt_tac th intr st = 
327 
let 

328 
fun eqvt_err s = error 

329 
("Could not prove equivariance for introduction rule\n" ^ 

330 
Sign.string_of_term (theory_of_thm intr) 

331 
(Logic.unvarify (prop_of intr)) ^ "\n" ^ s); 

332 
val res = SUBPROOF (fn {prems, ...} => 

333 
let val prems' = map (fn th' => 

334 
if null (names inter term_consts (prop_of th')) then th' RS th 

335 
else th') prems 

336 
in (rtac intr THEN_ALL_NEW 

337 
(resolve_tac prems ORELSE' 

338 
(cut_facts_tac prems' THEN' full_simp_tac eqvt_ss))) 1 

339 
end) ctxt 1 st 

340 
in 

341 
case (Seq.pull res handle THM (s, _, _) => eqvt_err s) of 

342 
NONE => eqvt_err ("Rule does not match goal\n" ^ 

343 
Sign.string_of_term (theory_of_thm st) (hd (prems_of st))) 

344 
 SOME (th, _) => Seq.single th 

345 
end; 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

346 
val thss = map (fn atom => 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

347 
let 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

348 
val pi' = Free (pi, NominalAtoms.mk_permT (Type (atom, []))); 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

349 
val perm_boolI' = Drule.cterm_instantiate 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

350 
[(perm_boolI_pi, cterm_of thy pi')] perm_boolI 
22530  351 
in map (fn th => zero_var_indexes (th RS mp)) 
22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

352 
(DatatypeAux.split_conj_thm (Goal.prove_global thy [] [] 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

353 
(HOLogic.mk_Trueprop (foldr1 HOLogic.mk_conj (map (fn p => 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

354 
HOLogic.mk_imp (p, list_comb 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

355 
(apsnd (map (NominalPackage.mk_perm [] pi')) (strip_comb p)))) ps))) 
22544  356 
(fn _ => EVERY (rtac raw_induct 1 :: map (fn intr => 
357 
full_simp_tac eqvt_ss 1 THEN eqvt_tac perm_boolI' intr) intrs)))) 

358 
end) atoms 

359 
in 

360 
fold (fn (name, ths) => 

361 
Theory.add_path (Sign.base_name name) #> 

362 
PureThy.add_thmss [(("eqvt", ths), [NominalThmDecls.eqvt_add])] #> snd #> 

363 
Theory.parent_path) (names ~~ transp thss) thy 

364 
end; 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

365 

22530  366 
fun gen_nominal_inductive f s avoids thy = 
367 
let 

368 
val ctxt = ProofContext.init thy; 

369 
val ({names, ...}, {raw_induct, intrs, ...}) = 

370 
InductivePackage.the_inductive ctxt (Sign.intern_const thy s); 

371 
in 

372 
thy > 

373 
prove_eqvt names raw_induct intrs > 

374 
f raw_induct names avoids 

375 
end; 

376 

377 
val nominal_inductive = gen_nominal_inductive prove_strong_ind; 

378 
fun equivariance s = gen_nominal_inductive (K (K (K I))) s []; 

379 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

380 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

381 
(* outer syntax *) 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

382 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

383 
local structure P = OuterParse and K = OuterKeyword in 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

384 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

385 
val nominal_inductiveP = 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

386 
OuterSyntax.command "nominal_inductive" 
22530  387 
"prove equivariance and strong induction theorem for inductive predicate involving nominal datatypes" K.thy_goal 
388 
(P.name  Scan.optional (P.$$$ "avoids"  P.and_list1 (P.name  

389 
(P.$$$ ":"  Scan.repeat1 P.name))) [] >> (fn (name, avoids) => 

390 
Toplevel.print o Toplevel.theory_to_proof (nominal_inductive name avoids))); 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

391 

22530  392 
val equivarianceP = 
393 
OuterSyntax.command "equivariance" 

394 
"prove equivariance for inductive predicate involving nominal datatypes" K.thy_decl 

395 
(P.name >> (Toplevel.theory o equivariance)); 

396 

397 
val _ = OuterSyntax.add_keywords ["avoids"]; 

398 
val _ = OuterSyntax.add_parsers [nominal_inductiveP, equivarianceP]; 

22313
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

399 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

400 
end; 
1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

401 

1a507b463f50
First steps towards strengthening of induction rules for
berghofe
parents:
diff
changeset

402 
end 