1371
|
1 |
theory Test_compat
|
|
2 |
imports "Parser" "../Attic/Prove"
|
|
3 |
begin
|
|
4 |
|
|
5 |
text {*
|
|
6 |
example 1
|
|
7 |
|
|
8 |
single let binding
|
|
9 |
*}
|
|
10 |
|
|
11 |
nominal_datatype lam =
|
|
12 |
VAR "name"
|
|
13 |
| APP "lam" "lam"
|
|
14 |
| LET bp::"bp" t::"lam" bind "bi bp" in t
|
|
15 |
and bp =
|
|
16 |
BP "name" "lam"
|
|
17 |
binder
|
|
18 |
bi::"bp \<Rightarrow> atom set"
|
|
19 |
where
|
|
20 |
"bi (BP x t) = {atom x}"
|
|
21 |
|
|
22 |
thm alpha_lam_raw_alpha_bp_raw.intros[no_vars]
|
|
23 |
|
|
24 |
abbreviation "VAR \<equiv> VAR_raw"
|
|
25 |
abbreviation "APP \<equiv> APP_raw"
|
|
26 |
abbreviation "LET \<equiv> LET_raw"
|
|
27 |
abbreviation "BP \<equiv> BP_raw"
|
|
28 |
abbreviation "bi \<equiv> bi_raw"
|
|
29 |
|
|
30 |
(* non-recursive case *)
|
|
31 |
|
1373
|
32 |
fun
|
|
33 |
fv_lam
|
|
34 |
and fv_bi
|
|
35 |
and fv_bp
|
|
36 |
where
|
|
37 |
"fv_lam (VAR name) = {atom name}"
|
|
38 |
| "fv_lam (APP lam1 lam2) = fv_lam lam1 \<union> fv_lam lam2"
|
|
39 |
| "fv_lam (LET bp lam) = (fv_bi bp) \<union> (fv_lam lam - bi bp)"
|
|
40 |
| "fv_bi (BP name lam) = fv_lam lam"
|
|
41 |
| "fv_bp (BP name lam) = {atom name} \<union> fv_lam lam"
|
|
42 |
|
1371
|
43 |
inductive
|
|
44 |
alpha_lam :: "lam_raw \<Rightarrow> lam_raw \<Rightarrow> bool" and
|
|
45 |
alpha_bp :: "bp_raw \<Rightarrow> bp_raw \<Rightarrow> bool" and
|
1373
|
46 |
alpha_bi :: "bp_raw \<Rightarrow> perm \<Rightarrow> bp_raw \<Rightarrow> bool"
|
1371
|
47 |
where
|
|
48 |
"x = y \<Longrightarrow> alpha_lam (VAR x) (VAR y)"
|
|
49 |
| "alpha_lam l1 s1 \<and> alpha_lam l2 s2 \<Longrightarrow> alpha_lam (APP l1 l2) (APP s1 s2)"
|
|
50 |
| "\<exists>pi. (bi bp, lam) \<approx>gen alpha_lam fv_lam_raw pi (bi bp', lam') \<and> (pi \<bullet> (bi bp)) = bi bp'
|
1373
|
51 |
\<and> alpha_bi bp pi bp'
|
1371
|
52 |
\<Longrightarrow> alpha_lam (LET bp lam) (LET bp' lam')"
|
|
53 |
| "alpha_lam lam lam' \<and> name = name' \<Longrightarrow> alpha_bp (BP name lam) (BP name' lam')"
|
1373
|
54 |
| "alpha_lam t t' \<Longrightarrow> alpha_bi (BP x t) pi (BP x' t')"
|
1371
|
55 |
|
|
56 |
lemma test1:
|
|
57 |
assumes "distinct [x, y]"
|
|
58 |
shows "alpha_lam (LET (BP x (VAR x)) (VAR x))
|
|
59 |
(LET (BP y (VAR x)) (VAR y))"
|
1373
|
60 |
apply(rule alpha_lam_alpha_bp_alpha_bi.intros)
|
1371
|
61 |
apply(rule_tac x="(x \<leftrightarrow> y)" in exI)
|
|
62 |
apply(simp add: alpha_gen fresh_star_def)
|
1373
|
63 |
apply(simp add: alpha_lam_alpha_bp_alpha_bi.intros(1))
|
1371
|
64 |
apply(rule conjI)
|
|
65 |
defer
|
1373
|
66 |
apply(rule alpha_lam_alpha_bp_alpha_bi.intros)
|
|
67 |
apply(simp add: alpha_lam_alpha_bp_alpha_bi.intros(1))
|
1371
|
68 |
apply(simp add: permute_set_eq atom_eqvt)
|
|
69 |
done
|
|
70 |
|
|
71 |
lemma test2:
|
|
72 |
assumes asm: "distinct [x, y]"
|
|
73 |
shows "\<not> alpha_lam (LET (BP x (VAR x)) (VAR x))
|
|
74 |
(LET (BP y (VAR y)) (VAR y))"
|
|
75 |
using asm
|
|
76 |
apply(clarify)
|
|
77 |
apply(erule alpha_lam.cases)
|
|
78 |
apply(simp_all)
|
|
79 |
apply(erule exE)
|
|
80 |
apply(clarify)
|
|
81 |
apply(simp add: alpha_gen fresh_star_def)
|
|
82 |
apply(erule alpha_lam.cases)
|
|
83 |
apply(simp_all)
|
|
84 |
apply(clarify)
|
1373
|
85 |
apply(erule alpha_bi.cases)
|
1371
|
86 |
apply(simp_all)
|
|
87 |
apply(clarify)
|
|
88 |
apply(erule alpha_lam.cases)
|
|
89 |
apply(simp_all)
|
|
90 |
done
|
|
91 |
|
|
92 |
(* recursive case where we have also bind "bi bp" in bp *)
|
|
93 |
|
|
94 |
inductive
|
|
95 |
Alpha_lam :: "lam_raw \<Rightarrow> lam_raw \<Rightarrow> bool" and
|
|
96 |
Alpha_bp :: "bp_raw \<Rightarrow> bp_raw \<Rightarrow> bool" and
|
|
97 |
Compat_bp :: "bp_raw \<Rightarrow> perm \<Rightarrow> bp_raw \<Rightarrow> bool"
|
|
98 |
where
|
|
99 |
"x = y \<Longrightarrow> Alpha_lam (VAR x) (VAR y)"
|
|
100 |
| "Alpha_lam l1 s1 \<and> Alpha_lam l2 s2 \<Longrightarrow> Alpha_lam (APP l1 l2) (APP s1 s2)"
|
|
101 |
| "\<exists>pi. (bi bp, lam) \<approx>gen Alpha_lam fv_lam_raw pi (bi bp', lam') \<and> Compat_bp bp pi bp'
|
|
102 |
\<and> (pi \<bullet> (bi bp)) = bi bp'
|
|
103 |
\<Longrightarrow> Alpha_lam (LET bp lam) (LET bp' lam')"
|
|
104 |
| "Alpha_lam lam lam' \<and> name = name' \<Longrightarrow> Alpha_bp (BP name lam) (BP name' lam')"
|
|
105 |
| "Alpha_lam (pi \<bullet> t) t' \<Longrightarrow> Compat_bp (BP x t) pi (BP x' t')"
|
1374
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
106 |
local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding Alpha_inj}, []), (build_alpha_inj @{thms Alpha_lam_Alpha_bp_Compat_bp.intros} @{thms lam_raw.distinct lam_raw.inject bp_raw.distinct bp_raw.inject} @{thms Alpha_lam.cases Alpha_bp.cases Compat_bp.cases} ctxt)) ctxt)) *}
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
107 |
local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding alpha_inj}, []), (build_alpha_inj @{thms alpha_lam_raw_alpha_bp_raw.intros} @{thms lam_raw.distinct lam_raw.inject bp_raw.distinct bp_raw.inject} @{thms alpha_lam_raw.cases alpha_bp_raw.cases} ctxt)) ctxt)) *}
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
108 |
local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding alpha_dis}, []), (flat (map (distinct_rel ctxt @{thms alpha_lam_raw.cases}) ([(@{thms lam_raw.distinct},@{term alpha_lam_raw})])))) ctxt)) *}
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
109 |
local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding Alpha_dis}, []), (flat (map (distinct_rel ctxt @{thms Alpha_lam.cases}) ([(@{thms lam_raw.distinct},@{term Alpha_lam})])))) ctxt)) *}
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
110 |
lemma "Alpha_lam x y = alpha_lam_raw x y"
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
111 |
apply rule
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
112 |
apply(induct x y rule: Alpha_lam_Alpha_bp_Compat_bp.inducts(1))
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
113 |
apply(simp_all only: alpha_lam_raw_alpha_bp_raw.intros)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
114 |
apply(simp_all add: alpha_inj)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
115 |
apply(erule exE) apply(rule_tac x="pi" in exI)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
116 |
apply(simp add: alpha_gen)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
117 |
apply clarify
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
118 |
apply simp
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
119 |
defer
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
120 |
apply(induct x y rule: alpha_lam_raw_alpha_bp_raw.inducts(1))
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
121 |
apply(simp_all only: Alpha_lam_Alpha_bp_Compat_bp.intros)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
122 |
apply(simp_all add: Alpha_inj)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
123 |
apply(erule exE) apply(rule_tac x="pi" in exI)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
124 |
apply(simp add: alpha_gen)
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
125 |
apply clarify
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
126 |
apply simp
|
d39ca37e526a
Trying to prove that old alpha is the same as new recursive one. Lets still to do.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
|
127 |
oops
|
1373
|
128 |
|
1371
|
129 |
lemma Test1:
|
|
130 |
assumes "distinct [x, y]"
|
|
131 |
shows "Alpha_lam (LET (BP x (VAR x)) (VAR x))
|
|
132 |
(LET (BP y (VAR y)) (VAR y))"
|
|
133 |
apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)
|
|
134 |
apply(rule_tac x="(x \<leftrightarrow> y)" in exI)
|
|
135 |
apply(simp add: alpha_gen fresh_star_def)
|
|
136 |
apply(simp add: Alpha_lam_Alpha_bp_Compat_bp.intros(1))
|
|
137 |
apply(rule conjI)
|
|
138 |
apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)
|
|
139 |
apply(simp add: Alpha_lam_Alpha_bp_Compat_bp.intros(1))
|
|
140 |
apply(simp add: permute_set_eq atom_eqvt)
|
|
141 |
done
|
|
142 |
|
|
143 |
lemma Test2:
|
|
144 |
assumes asm: "distinct [x, y]"
|
|
145 |
shows "\<not> Alpha_lam (LET (BP x (VAR x)) (VAR x))
|
|
146 |
(LET (BP y (VAR x)) (VAR y))"
|
|
147 |
using asm
|
|
148 |
apply(clarify)
|
|
149 |
apply(erule Alpha_lam.cases)
|
|
150 |
apply(simp_all)
|
|
151 |
apply(erule exE)
|
|
152 |
apply(clarify)
|
|
153 |
apply(simp add: alpha_gen fresh_star_def)
|
|
154 |
apply(erule Alpha_lam.cases)
|
|
155 |
apply(simp_all)
|
|
156 |
apply(clarify)
|
|
157 |
apply(erule Compat_bp.cases)
|
|
158 |
apply(simp_all)
|
|
159 |
apply(clarify)
|
|
160 |
apply(erule Alpha_lam.cases)
|
|
161 |
apply(simp_all)
|
|
162 |
done
|
|
163 |
|
|
164 |
|
|
165 |
text {* example 2 *}
|
|
166 |
|
|
167 |
nominal_datatype trm' =
|
|
168 |
Var "name"
|
|
169 |
| App "trm'" "trm'"
|
|
170 |
| Lam x::"name" t::"trm'" bind x in t
|
|
171 |
| Let p::"pat'" "trm'" t::"trm'" bind "f p" in t
|
|
172 |
and pat' =
|
|
173 |
PN
|
|
174 |
| PS "name"
|
|
175 |
| PD "name" "name"
|
|
176 |
binder
|
|
177 |
f::"pat' \<Rightarrow> atom set"
|
|
178 |
where
|
|
179 |
"f PN = {}"
|
|
180 |
| "f (PS x) = {atom x}"
|
|
181 |
| "f (PD x y) = {atom x} \<union> {atom y}"
|
|
182 |
|
|
183 |
thm alpha_trm'_raw_alpha_pat'_raw.intros[no_vars]
|
|
184 |
|
|
185 |
abbreviation "Var \<equiv> Var_raw"
|
|
186 |
abbreviation "App \<equiv> App_raw"
|
|
187 |
abbreviation "Lam \<equiv> Lam_raw"
|
|
188 |
abbreviation "Lett \<equiv> Let_raw"
|
|
189 |
abbreviation "PN \<equiv> PN_raw"
|
|
190 |
abbreviation "PS \<equiv> PS_raw"
|
|
191 |
abbreviation "PD \<equiv> PD_raw"
|
|
192 |
abbreviation "f \<equiv> f_raw"
|
|
193 |
|
|
194 |
(* not_yet_done *)
|
|
195 |
inductive
|
|
196 |
alpha_trm' :: "trm'_raw \<Rightarrow> trm'_raw \<Rightarrow> bool" and
|
|
197 |
alpha_pat' :: "pat'_raw \<Rightarrow> pat'_raw \<Rightarrow> bool" and
|
|
198 |
compat_pat' :: "pat'_raw \<Rightarrow> perm \<Rightarrow> pat'_raw \<Rightarrow> bool"
|
|
199 |
where
|
|
200 |
"name = name' \<Longrightarrow> alpha_trm' (Var name) (Var name')"
|
|
201 |
| "alpha_trm' t2 t2' \<and> alpha_trm' t1 t1' \<Longrightarrow> alpha_trm' (App t1 t2) (App t1' t2')"
|
|
202 |
| "\<exists>pi. ({atom x}, t) \<approx>gen alpha_trm' fv_trm'_raw pi ({atom x'}, t') \<Longrightarrow> alpha_trm' (Lam x t) (Lam x' t')"
|
|
203 |
| "\<exists>pi. (f p, t) \<approx>gen alpha_trm' fv_trm'_raw pi (f p', t') \<and> alpha_trm' s s' \<and> (pi \<bullet> f p) = f p' \<and>
|
|
204 |
compat_pat' p pi p' \<Longrightarrow> alpha_trm' (Lett p s t) (Lett p' s' t')"
|
|
205 |
| "alpha_pat' PN PN"
|
|
206 |
| "name = name' \<Longrightarrow> alpha_pat' (PS name) (PS name')"
|
|
207 |
| "name2 = name2' \<and> name1 = name1' \<Longrightarrow> alpha_pat' (PD name1 name2) (PD name1' name2')"
|
|
208 |
| "compat_pat' PN pi PN"
|
|
209 |
| "compat_pat' (PS x) pi (PS x')"
|
|
210 |
| "compat_pat' (PD p1 p2) pi (PD p1' p2')"
|
|
211 |
|
|
212 |
lemma
|
|
213 |
assumes a: "distinct [x, y, z, u]"
|
|
214 |
shows "alpha_trm' (Lett (PD x u) t (App (Var x) (Var y)))
|
|
215 |
(Lett (PD z u) t (App (Var z) (Var y)))"
|
|
216 |
using a
|
|
217 |
apply -
|
|
218 |
apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
219 |
apply(auto simp add: alpha_gen)
|
|
220 |
apply(rule_tac x="(x \<leftrightarrow> z)" in exI)
|
|
221 |
apply(auto simp add: fresh_star_def permute_set_eq atom_eqvt)
|
|
222 |
defer
|
|
223 |
apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
224 |
apply(simp add: alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
225 |
prefer 4
|
|
226 |
apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
227 |
(* they can be proved *)
|
|
228 |
oops
|
|
229 |
|
|
230 |
lemma
|
|
231 |
assumes a: "distinct [x, y, z, u]"
|
|
232 |
shows "alpha_trm' (Lett (PD x u) t (App (Var x) (Var y)))
|
|
233 |
(Lett (PD z z) t (App (Var z) (Var y)))"
|
|
234 |
using a
|
|
235 |
apply -
|
|
236 |
apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
237 |
apply(auto simp add: alpha_gen)
|
|
238 |
apply(rule_tac x="(x \<leftrightarrow> z)" in exI)
|
|
239 |
apply(auto simp add: fresh_star_def permute_set_eq atom_eqvt)
|
|
240 |
defer
|
|
241 |
apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
242 |
apply(simp add: alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
243 |
prefer 4
|
|
244 |
apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)
|
|
245 |
(* they can be proved *)
|
|
246 |
oops
|
|
247 |
|
|
248 |
using a
|
|
249 |
apply(clarify)
|
|
250 |
apply(erule alpha_trm'.cases)
|
|
251 |
apply(simp_all)
|
|
252 |
apply(auto simp add: alpha_gen)
|
|
253 |
apply(erule alpha_trm'.cases)
|
|
254 |
apply(simp_all)
|
|
255 |
apply(clarify)
|
|
256 |
apply(erule compat_pat'.cases)
|
|
257 |
apply(simp_all)
|
|
258 |
apply(clarify)
|
|
259 |
apply(erule alpha_trm'.cases)
|
|
260 |
apply(simp_all)
|
|
261 |
done
|
|
262 |
|
|
263 |
nominal_datatype trm0 =
|
|
264 |
Var0 "name"
|
|
265 |
| App0 "trm0" "trm0"
|
|
266 |
| Lam0 x::"name" t::"trm0" bind x in t
|
|
267 |
| Let0 p::"pat0" "trm0" t::"trm0" bind "f0 p" in t
|
|
268 |
and pat0 =
|
|
269 |
PN0
|
|
270 |
| PS0 "name"
|
|
271 |
| PD0 "pat0" "pat0"
|
|
272 |
binder
|
|
273 |
f0::"pat0 \<Rightarrow> atom set"
|
|
274 |
where
|
|
275 |
"f0 PN0 = {}"
|
|
276 |
| "f0 (PS0 x) = {atom x}"
|
|
277 |
| "f0 (PD0 p1 p2) = (f0 p1) \<union> (f0 p2)"
|
|
278 |
|
|
279 |
thm f0_raw.simps
|
|
280 |
(*thm trm0_pat0_induct
|
|
281 |
thm trm0_pat0_perm
|
|
282 |
thm trm0_pat0_fv
|
|
283 |
thm trm0_pat0_bn*)
|
|
284 |
|
|
285 |
text {* example type schemes *}
|
|
286 |
|
|
287 |
(* does not work yet
|
|
288 |
nominal_datatype t =
|
|
289 |
Var "name"
|
|
290 |
| Fun "t" "t"
|
|
291 |
|
|
292 |
nominal_datatype tyS =
|
|
293 |
All xs::"name list" ty::"t_raw" bind xs in ty
|
|
294 |
*)
|
|
295 |
|
|
296 |
|
|
297 |
nominal_datatype t =
|
|
298 |
Var "name"
|
|
299 |
| Fun "t" "t"
|
|
300 |
and tyS =
|
|
301 |
All xs::"name set" ty::"t" bind xs in ty
|
|
302 |
|
|
303 |
(* example 1 from Terms.thy *)
|
|
304 |
|
|
305 |
nominal_datatype trm1 =
|
|
306 |
Vr1 "name"
|
|
307 |
| Ap1 "trm1" "trm1"
|
|
308 |
| Lm1 x::"name" t::"trm1" bind x in t
|
|
309 |
| Lt1 p::"bp1" "trm1" t::"trm1" bind "bv1 p" in t
|
|
310 |
and bp1 =
|
|
311 |
BUnit1
|
|
312 |
| BV1 "name"
|
|
313 |
| BP1 "bp1" "bp1"
|
|
314 |
binder
|
|
315 |
bv1
|
|
316 |
where
|
|
317 |
"bv1 (BUnit1) = {}"
|
|
318 |
| "bv1 (BV1 x) = {atom x}"
|
|
319 |
| "bv1 (BP1 bp1 bp2) = (bv1 bp1) \<union> (bv1 bp2)"
|
|
320 |
|
|
321 |
thm bv1_raw.simps
|
|
322 |
|
|
323 |
(* example 2 from Terms.thy *)
|
|
324 |
|
|
325 |
nominal_datatype trm2 =
|
|
326 |
Vr2 "name"
|
|
327 |
| Ap2 "trm2" "trm2"
|
|
328 |
| Lm2 x::"name" t::"trm2" bind x in t
|
|
329 |
| Lt2 r::"assign" t::"trm2" bind "bv2 r" in t
|
|
330 |
and assign =
|
|
331 |
As "name" "trm2"
|
|
332 |
binder
|
|
333 |
bv2
|
|
334 |
where
|
|
335 |
"bv2 (As x t) = {atom x}"
|
|
336 |
|
|
337 |
(* compat should be
|
|
338 |
compat (As x t) pi (As x' t') == pi o x = x' & alpha t t'
|
|
339 |
*)
|
|
340 |
|
|
341 |
|
|
342 |
thm fv_trm2_raw_fv_assign_raw.simps[no_vars]
|
|
343 |
thm alpha_trm2_raw_alpha_assign_raw.intros[no_vars]
|
|
344 |
|
|
345 |
|
|
346 |
|
|
347 |
text {* example 3 from Terms.thy *}
|
|
348 |
|
|
349 |
nominal_datatype trm3 =
|
|
350 |
Vr3 "name"
|
|
351 |
| Ap3 "trm3" "trm3"
|
|
352 |
| Lm3 x::"name" t::"trm3" bind x in t
|
|
353 |
| Lt3 r::"rassigns3" t::"trm3" bind "bv3 r" in t
|
|
354 |
and rassigns3 =
|
|
355 |
ANil
|
|
356 |
| ACons "name" "trm3" "rassigns3"
|
|
357 |
binder
|
|
358 |
bv3
|
|
359 |
where
|
|
360 |
"bv3 ANil = {}"
|
|
361 |
| "bv3 (ACons x t as) = {atom x} \<union> (bv3 as)"
|
|
362 |
|
|
363 |
|
|
364 |
(* compat should be
|
|
365 |
compat (ANil) pi (PNil) \<equiv> TRue
|
|
366 |
compat (ACons x t ts) pi (ACons x' t' ts') \<equiv> pi o x = x' \<and> alpha t t' \<and> compat ts pi ts'
|
|
367 |
*)
|
|
368 |
|
|
369 |
(* example 4 from Terms.thy *)
|
|
370 |
|
|
371 |
(* fv_eqvt does not work, we need to repaire defined permute functions
|
|
372 |
defined fv and defined alpha... *)
|
|
373 |
nominal_datatype trm4 =
|
|
374 |
Vr4 "name"
|
|
375 |
| Ap4 "trm4" "trm4 list"
|
|
376 |
| Lm4 x::"name" t::"trm4" bind x in t
|
|
377 |
|
|
378 |
thm alpha_trm4_raw_alpha_trm4_raw_list.intros[no_vars]
|
|
379 |
thm fv_trm4_raw_fv_trm4_raw_list.simps[no_vars]
|
|
380 |
|
|
381 |
(* example 5 from Terms.thy *)
|
|
382 |
|
|
383 |
nominal_datatype trm5 =
|
|
384 |
Vr5 "name"
|
|
385 |
| Ap5 "trm5" "trm5"
|
|
386 |
| Lt5 l::"lts" t::"trm5" bind "bv5 l" in t
|
|
387 |
and lts =
|
|
388 |
Lnil
|
|
389 |
| Lcons "name" "trm5" "lts"
|
|
390 |
binder
|
|
391 |
bv5
|
|
392 |
where
|
|
393 |
"bv5 Lnil = {}"
|
|
394 |
| "bv5 (Lcons n t ltl) = {atom n} \<union> (bv5 ltl)"
|
|
395 |
|
|
396 |
(* example 6 from Terms.thy *)
|
|
397 |
|
|
398 |
(* BV is not respectful, needs to fail*)
|
|
399 |
nominal_datatype trm6 =
|
|
400 |
Vr6 "name"
|
|
401 |
| Lm6 x::"name" t::"trm6" bind x in t
|
|
402 |
| Lt6 left::"trm6" right::"trm6" bind "bv6 left" in right
|
|
403 |
binder
|
|
404 |
bv6
|
|
405 |
where
|
|
406 |
"bv6 (Vr6 n) = {}"
|
|
407 |
| "bv6 (Lm6 n t) = {atom n} \<union> bv6 t"
|
|
408 |
| "bv6 (Lt6 l r) = bv6 l \<union> bv6 r"
|
|
409 |
(* example 7 from Terms.thy *)
|
|
410 |
|
|
411 |
(* BV is not respectful, needs to fail*)
|
|
412 |
nominal_datatype trm7 =
|
|
413 |
Vr7 "name"
|
|
414 |
| Lm7 l::"name" r::"trm7" bind l in r
|
|
415 |
| Lt7 l::"trm7" r::"trm7" bind "bv7 l" in r
|
|
416 |
binder
|
|
417 |
bv7
|
|
418 |
where
|
|
419 |
"bv7 (Vr7 n) = {atom n}"
|
|
420 |
| "bv7 (Lm7 n t) = bv7 t - {atom n}"
|
|
421 |
| "bv7 (Lt7 l r) = bv7 l \<union> bv7 r"
|
|
422 |
|
|
423 |
(* example 8 from Terms.thy *)
|
|
424 |
|
|
425 |
nominal_datatype foo8 =
|
|
426 |
Foo0 "name"
|
|
427 |
| Foo1 b::"bar8" f::"foo8" bind "bv8 b" in f --"check fo error if this is called foo"
|
|
428 |
and bar8 =
|
|
429 |
Bar0 "name"
|
|
430 |
| Bar1 "name" s::"name" b::"bar8" bind s in b
|
|
431 |
binder
|
|
432 |
bv8
|
|
433 |
where
|
|
434 |
"bv8 (Bar0 x) = {}"
|
|
435 |
| "bv8 (Bar1 v x b) = {atom v}"
|
|
436 |
|
|
437 |
(* example 9 from Terms.thy *)
|
|
438 |
|
|
439 |
(* BV is not respectful, needs to fail*)
|
|
440 |
nominal_datatype lam9 =
|
|
441 |
Var9 "name"
|
|
442 |
| Lam9 n::"name" l::"lam9" bind n in l
|
|
443 |
and bla9 =
|
|
444 |
Bla9 f::"lam9" s::"lam9" bind "bv9 f" in s
|
|
445 |
binder
|
|
446 |
bv9
|
|
447 |
where
|
|
448 |
"bv9 (Var9 x) = {}"
|
|
449 |
| "bv9 (Lam9 x b) = {atom x}"
|
|
450 |
|
|
451 |
(* example from my PHD *)
|
|
452 |
|
|
453 |
atom_decl coname
|
|
454 |
|
|
455 |
nominal_datatype phd =
|
|
456 |
Ax "name" "coname"
|
|
457 |
| Cut n::"coname" t1::"phd" c::"coname" t2::"phd" bind n in t1, bind c in t2
|
|
458 |
| AndR c1::"coname" t1::"phd" c2::"coname" t2::"phd" "coname" bind c1 in t1, bind c2 in t2
|
|
459 |
| AndL1 n::"name" t::"phd" "name" bind n in t
|
|
460 |
| AndL2 n::"name" t::"phd" "name" bind n in t
|
|
461 |
| ImpL c::"coname" t1::"phd" n::"name" t2::"phd" "name" bind c in t1, bind n in t2
|
|
462 |
| ImpR c::"coname" n::"name" t::"phd" "coname" bind n in t, bind c in t
|
|
463 |
|
|
464 |
thm alpha_phd_raw.intros[no_vars]
|
|
465 |
thm fv_phd_raw.simps[no_vars]
|
|
466 |
|
|
467 |
|
|
468 |
(* example form Leroy 96 about modules; OTT *)
|
|
469 |
|
|
470 |
nominal_datatype mexp =
|
|
471 |
Acc "path"
|
|
472 |
| Stru "body"
|
|
473 |
| Funct x::"name" "sexp" m::"mexp" bind x in m
|
|
474 |
| FApp "mexp" "path"
|
|
475 |
| Ascr "mexp" "sexp"
|
|
476 |
and body =
|
|
477 |
Empty
|
|
478 |
| Seq c::defn d::"body" bind "cbinders c" in d
|
|
479 |
and defn =
|
|
480 |
Type "name" "tyty"
|
|
481 |
| Dty "name"
|
|
482 |
| DStru "name" "mexp"
|
|
483 |
| Val "name" "trmtrm"
|
|
484 |
and sexp =
|
|
485 |
Sig sbody
|
|
486 |
| SFunc "name" "sexp" "sexp"
|
|
487 |
and sbody =
|
|
488 |
SEmpty
|
|
489 |
| SSeq C::spec D::sbody bind "Cbinders C" in D
|
|
490 |
and spec =
|
|
491 |
Type1 "name"
|
|
492 |
| Type2 "name" "tyty"
|
|
493 |
| SStru "name" "sexp"
|
|
494 |
| SVal "name" "tyty"
|
|
495 |
and tyty =
|
|
496 |
Tyref1 "name"
|
|
497 |
| Tyref2 "path" "tyty"
|
|
498 |
| Fun "tyty" "tyty"
|
|
499 |
and path =
|
|
500 |
Sref1 "name"
|
|
501 |
| Sref2 "path" "name"
|
|
502 |
and trmtrm =
|
|
503 |
Tref1 "name"
|
|
504 |
| Tref2 "path" "name"
|
|
505 |
| Lam' v::"name" "tyty" M::"trmtrm" bind v in M
|
|
506 |
| App' "trmtrm" "trmtrm"
|
|
507 |
| Let' "body" "trmtrm"
|
|
508 |
binder
|
|
509 |
cbinders :: "defn \<Rightarrow> atom set"
|
|
510 |
and Cbinders :: "spec \<Rightarrow> atom set"
|
|
511 |
where
|
|
512 |
"cbinders (Type t T) = {atom t}"
|
|
513 |
| "cbinders (Dty t) = {atom t}"
|
|
514 |
| "cbinders (DStru x s) = {atom x}"
|
|
515 |
| "cbinders (Val v M) = {atom v}"
|
|
516 |
| "Cbinders (Type1 t) = {atom t}"
|
|
517 |
| "Cbinders (Type2 t T) = {atom t}"
|
|
518 |
| "Cbinders (SStru x S) = {atom x}"
|
|
519 |
| "Cbinders (SVal v T) = {atom v}"
|
|
520 |
|
|
521 |
(* core haskell *)
|
|
522 |
print_theorems
|
|
523 |
|
|
524 |
atom_decl var
|
|
525 |
atom_decl tvar
|
|
526 |
|
|
527 |
|
|
528 |
(* there are types, coercion types and regular types *)
|
|
529 |
nominal_datatype tkind =
|
|
530 |
KStar
|
|
531 |
| KFun "tkind" "tkind"
|
|
532 |
and ckind =
|
|
533 |
CKEq "ty" "ty"
|
|
534 |
and ty =
|
|
535 |
TVar "tvar"
|
|
536 |
| TC "string"
|
|
537 |
| TApp "ty" "ty"
|
|
538 |
| TFun "string" "ty list"
|
|
539 |
| TAll tv::"tvar" "tkind" T::"ty" bind tv in T
|
|
540 |
| TEq "ty" "ty" "ty"
|
|
541 |
and co =
|
|
542 |
CC "string"
|
|
543 |
| CApp "co" "co"
|
|
544 |
| CFun "string" "co list"
|
|
545 |
| CAll tv::"tvar" "ckind" C::"co" bind tv in C
|
|
546 |
| CEq "co" "co" "co"
|
|
547 |
| CSym "co"
|
|
548 |
| CCir "co" "co"
|
|
549 |
| CLeft "co"
|
|
550 |
| CRight "co"
|
|
551 |
| CSim "co"
|
|
552 |
| CRightc "co"
|
|
553 |
| CLeftc "co"
|
|
554 |
| CCoe "co" "co"
|
|
555 |
|
|
556 |
|
|
557 |
typedecl ty --"hack since ty is not yet defined"
|
|
558 |
|
|
559 |
abbreviation
|
|
560 |
"atoms A \<equiv> atom ` A"
|
|
561 |
|
|
562 |
nominal_datatype trm =
|
|
563 |
Var "var"
|
|
564 |
| C "string"
|
|
565 |
| LAM tv::"tvar" "kind" t::"trm" bind tv in t
|
|
566 |
| APP "trm" "ty"
|
|
567 |
| Lam v::"var" "ty" t::"trm" bind v in t
|
|
568 |
| App "trm" "trm"
|
|
569 |
| Let x::"var" "ty" "trm" t::"trm" bind x in t
|
|
570 |
| Case "trm" "assoc list"
|
|
571 |
| Cast "trm" "ty" --"ty is supposed to be a coercion type only"
|
|
572 |
and assoc =
|
|
573 |
A p::"pat" t::"trm" bind "bv p" in t
|
|
574 |
and pat =
|
|
575 |
K "string" "(tvar \<times> kind) list" "(var \<times> ty) list"
|
|
576 |
binder
|
|
577 |
bv :: "pat \<Rightarrow> atom set"
|
|
578 |
where
|
|
579 |
"bv (K s ts vs) = (atoms (set (map fst ts))) \<union> (atoms (set (map fst vs)))"
|
|
580 |
|
|
581 |
(*
|
|
582 |
compat (K s ts vs) pi (K s' ts' vs') ==
|
|
583 |
s = s' &
|
|
584 |
|
|
585 |
*)
|
|
586 |
|
|
587 |
|
|
588 |
(*thm bv_raw.simps*)
|
|
589 |
|
|
590 |
(* example 3 from Peter Sewell's bestiary *)
|
|
591 |
nominal_datatype exp =
|
|
592 |
VarP "name"
|
|
593 |
| AppP "exp" "exp"
|
|
594 |
| LamP x::"name" e::"exp" bind x in e
|
|
595 |
| LetP x::"name" p::"pat" e1::"exp" e2::"exp" bind x in e2, bind "bp p" in e1
|
|
596 |
and pat =
|
|
597 |
PVar "name"
|
|
598 |
| PUnit
|
|
599 |
| PPair "pat" "pat"
|
|
600 |
binder
|
|
601 |
bp :: "pat \<Rightarrow> atom set"
|
|
602 |
where
|
|
603 |
"bp (PVar x) = {atom x}"
|
|
604 |
| "bp (PUnit) = {}"
|
|
605 |
| "bp (PPair p1 p2) = bp p1 \<union> bp p2"
|
|
606 |
thm alpha_exp_raw_alpha_pat_raw.intros
|
|
607 |
|
|
608 |
(* example 6 from Peter Sewell's bestiary *)
|
|
609 |
nominal_datatype exp6 =
|
|
610 |
EVar name
|
|
611 |
| EPair exp6 exp6
|
|
612 |
| ELetRec x::name p::pat6 e1::exp6 e2::exp6 bind x in e1, bind x in e2, bind "bp6 p" in e1
|
|
613 |
and pat6 =
|
|
614 |
PVar' name
|
|
615 |
| PUnit'
|
|
616 |
| PPair' pat6 pat6
|
|
617 |
binder
|
|
618 |
bp6 :: "pat6 \<Rightarrow> atom set"
|
|
619 |
where
|
|
620 |
"bp6 (PVar' x) = {atom x}"
|
|
621 |
| "bp6 (PUnit') = {}"
|
|
622 |
| "bp6 (PPair' p1 p2) = bp6 p1 \<union> bp6 p2"
|
|
623 |
thm alpha_exp6_raw_alpha_pat6_raw.intros
|
|
624 |
|
|
625 |
(* example 7 from Peter Sewell's bestiary *)
|
|
626 |
nominal_datatype exp7 =
|
|
627 |
EVar name
|
|
628 |
| EUnit
|
|
629 |
| EPair exp7 exp7
|
|
630 |
| ELetRec l::lrbs e::exp7 bind "b7s l" in e, bind "b7s l" in l
|
|
631 |
and lrb =
|
|
632 |
Assign name exp7
|
|
633 |
and lrbs =
|
|
634 |
Single lrb
|
|
635 |
| More lrb lrbs
|
|
636 |
binder
|
|
637 |
b7 :: "lrb \<Rightarrow> atom set" and
|
|
638 |
b7s :: "lrbs \<Rightarrow> atom set"
|
|
639 |
where
|
|
640 |
"b7 (Assign x e) = {atom x}"
|
|
641 |
| "b7s (Single a) = b7 a"
|
|
642 |
| "b7s (More a as) = (b7 a) \<union> (b7s as)"
|
|
643 |
thm alpha_exp7_raw_alpha_lrb_raw_alpha_lrbs_raw.intros
|
|
644 |
|
|
645 |
(* example 8 from Peter Sewell's bestiary *)
|
|
646 |
nominal_datatype exp8 =
|
|
647 |
EVar name
|
|
648 |
| EUnit
|
|
649 |
| EPair exp8 exp8
|
|
650 |
| ELetRec l::lrbs8 e::exp8 bind "b_lrbs8 l" in e, bind "b_lrbs8 l" in l
|
|
651 |
and fnclause =
|
|
652 |
K x::name p::pat8 e::exp8 bind "b_pat p" in e
|
|
653 |
and fnclauses =
|
|
654 |
S fnclause
|
|
655 |
| ORs fnclause fnclauses
|
|
656 |
and lrb8 =
|
|
657 |
Clause fnclauses
|
|
658 |
and lrbs8 =
|
|
659 |
Single lrb8
|
|
660 |
| More lrb8 lrbs8
|
|
661 |
and pat8 =
|
|
662 |
PVar name
|
|
663 |
| PUnit
|
|
664 |
| PPair pat8 pat8
|
|
665 |
binder
|
|
666 |
b_lrbs8 :: "lrbs8 \<Rightarrow> atom set" and
|
|
667 |
b_pat :: "pat8 \<Rightarrow> atom set" and
|
|
668 |
b_fnclauses :: "fnclauses \<Rightarrow> atom set" and
|
|
669 |
b_fnclause :: "fnclause \<Rightarrow> atom set" and
|
|
670 |
b_lrb8 :: "lrb8 \<Rightarrow> atom set"
|
|
671 |
where
|
|
672 |
"b_lrbs8 (Single l) = b_lrb8 l"
|
|
673 |
| "b_lrbs8 (More l ls) = b_lrb8 l \<union> b_lrbs8 ls"
|
|
674 |
| "b_pat (PVar x) = {atom x}"
|
|
675 |
| "b_pat (PUnit) = {}"
|
|
676 |
| "b_pat (PPair p1 p2) = b_pat p1 \<union> b_pat p2"
|
|
677 |
| "b_fnclauses (S fc) = (b_fnclause fc)"
|
|
678 |
| "b_fnclauses (ORs fc fcs) = (b_fnclause fc) \<union> (b_fnclauses fcs)"
|
|
679 |
| "b_lrb8 (Clause fcs) = (b_fnclauses fcs)"
|
|
680 |
| "b_fnclause (K x pat exp8) = {atom x}"
|
|
681 |
thm alpha_exp8_raw_alpha_fnclause_raw_alpha_fnclauses_raw_alpha_lrb8_raw_alpha_lrbs8_raw_alpha_pat8_raw.intros
|
|
682 |
|
|
683 |
|
|
684 |
|
|
685 |
|
|
686 |
(* example 9 from Peter Sewell's bestiary *)
|
|
687 |
(* run out of steam at the moment *)
|
|
688 |
|
|
689 |
end
|
|
690 |
|
|
691 |
|
|
692 |
|