1797
fddb470720f1
renamed ExLam to Lambda and completed the proof of the strong ind principle; tuned paper
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 1
theory Lambda
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 2
imports
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 3
"../Nominal2"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 4
"~~/src/HOL/Library/Monad_Syntax"
1594
+ − 5
begin
+ − 6
2885
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 7
1594
+ − 8
atom_decl name
+ − 9
2436
+ − 10
nominal_datatype lam =
1800
78fdc6b36a1c
changed the eqvt-tac to move only outermost permutations inside; added tracing infrastructure for the eqvt-tac
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 11
Var "name"
2436
+ − 12
| App "lam" "lam"
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 13
| Lam x::"name" l::"lam" binds x in l ("Lam [_]. _" [100, 100] 100)
2431
331873ebc5cd
can now deal with type variables in nominal datatype definitions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 14
2885
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 15
ML {* Method.SIMPLE_METHOD' *}
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 16
ML {* Sign.intern_const *}
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 17
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 18
ML {*
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 19
val test:((Proof.context -> Method.method) context_parser) =
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 20
Scan.succeed (fn ctxt =>
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 21
let
2891
304dfe6cc83a
the simplifier can simplify "sort (atom a)" if a is a concrete atom type declared with atom_decl
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 22
val _ = Inductive.the_inductive ctxt "local.frees_lst_graph"
2885
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 23
in
2948
+ − 24
Method.SIMPLE_METHOD' (K (all_tac))
2885
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 25
end)
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 26
*}
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 27
1264f2a21ea9
some rudimentary infrastructure for storing data about nominal datatypes
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 28
method_setup test = {* test *} {* test *}
2868
+ − 29
2951
+ − 30
section {* Simple examples from Norrish 2004 *}
+ − 31
+ − 32
nominal_primrec
+ − 33
is_app :: "lam \<Rightarrow> bool"
+ − 34
where
+ − 35
"is_app (Var x) = False"
+ − 36
| "is_app (App t1 t2) = True"
+ − 37
| "is_app (Lam [x]. t) = False"
+ − 38
apply(simp add: eqvt_def is_app_graph_def)
+ − 39
apply (rule, perm_simp, rule)
+ − 40
apply(rule TrueI)
+ − 41
apply(rule_tac y="x" in lam.exhaust)
+ − 42
apply(auto)[3]
+ − 43
apply(all_trivials)
+ − 44
done
+ − 45
+ − 46
termination by lexicographic_order
+ − 47
+ − 48
lemma [eqvt]:
+ − 49
shows "(p \<bullet> (is_app t)) = is_app (p \<bullet> t)"
+ − 50
apply(induct t rule: lam.induct)
+ − 51
apply(simp_all add: permute_bool_def)
+ − 52
done
+ − 53
+ − 54
nominal_primrec
+ − 55
rator :: "lam \<Rightarrow> lam option"
+ − 56
where
+ − 57
"rator (Var x) = None"
+ − 58
| "rator (App t1 t2) = Some t1"
+ − 59
| "rator (Lam [x]. t) = None"
+ − 60
apply(simp add: eqvt_def rator_graph_def)
+ − 61
apply (rule, perm_simp, rule)
+ − 62
apply(rule TrueI)
+ − 63
apply(rule_tac y="x" in lam.exhaust)
+ − 64
apply(auto)[3]
+ − 65
apply(simp_all)
+ − 66
done
+ − 67
+ − 68
termination by lexicographic_order
+ − 69
+ − 70
lemma [eqvt]:
+ − 71
shows "(p \<bullet> (rator t)) = rator (p \<bullet> t)"
+ − 72
apply(induct t rule: lam.induct)
+ − 73
apply(simp_all)
+ − 74
done
+ − 75
+ − 76
nominal_primrec
+ − 77
rand :: "lam \<Rightarrow> lam option"
+ − 78
where
+ − 79
"rand (Var x) = None"
+ − 80
| "rand (App t1 t2) = Some t2"
+ − 81
| "rand (Lam [x]. t) = None"
+ − 82
apply(simp add: eqvt_def rand_graph_def)
+ − 83
apply (rule, perm_simp, rule)
+ − 84
apply(rule TrueI)
+ − 85
apply(rule_tac y="x" in lam.exhaust)
+ − 86
apply(auto)[3]
+ − 87
apply(simp_all)
+ − 88
done
+ − 89
+ − 90
termination by lexicographic_order
+ − 91
+ − 92
lemma [eqvt]:
+ − 93
shows "(p \<bullet> (rand t)) = rand (p \<bullet> t)"
+ − 94
apply(induct t rule: lam.induct)
+ − 95
apply(simp_all)
+ − 96
done
+ − 97
+ − 98
nominal_primrec
+ − 99
is_eta_nf :: "lam \<Rightarrow> bool"
+ − 100
where
+ − 101
"is_eta_nf (Var x) = True"
+ − 102
| "is_eta_nf (App t1 t2) = (is_eta_nf t1 \<and> is_eta_nf t2)"
+ − 103
| "is_eta_nf (Lam [x]. t) = (is_eta_nf t \<and>
+ − 104
((is_app t \<and> rand t = Some (Var x)) \<longrightarrow> atom x \<in> supp (rator t)))"
+ − 105
apply(simp add: eqvt_def is_eta_nf_graph_def)
+ − 106
apply (rule, perm_simp, rule)
+ − 107
apply(rule TrueI)
+ − 108
apply(rule_tac y="x" in lam.exhaust)
+ − 109
apply(auto)[3]
+ − 110
apply(simp_all)
+ − 111
apply(erule_tac c="()" in Abs_lst1_fcb2')
+ − 112
apply(simp_all add: pure_fresh fresh_star_def)[3]
+ − 113
apply(simp add: eqvt_at_def conj_eqvt)
+ − 114
apply(perm_simp)
+ − 115
apply(rule refl)
+ − 116
apply(simp add: eqvt_at_def conj_eqvt)
+ − 117
apply(perm_simp)
+ − 118
apply(rule refl)
+ − 119
done
+ − 120
+ − 121
termination by lexicographic_order
+ − 122
+ − 123
nominal_datatype path = Left | Right | In
+ − 124
+ − 125
section {* Paths to a free variables *}
+ − 126
+ − 127
instance path :: pure
+ − 128
apply(default)
+ − 129
apply(induct_tac "x::path" rule: path.induct)
+ − 130
apply(simp_all)
+ − 131
done
+ − 132
+ − 133
nominal_primrec
+ − 134
var_pos :: "name \<Rightarrow> lam \<Rightarrow> (path list) set"
+ − 135
where
+ − 136
"var_pos y (Var x) = (if y = x then {[]} else {})"
+ − 137
| "var_pos y (App t1 t2) = (Cons Left ` (var_pos y t1)) \<union> (Cons Right ` (var_pos y t2))"
+ − 138
| "atom x \<sharp> y \<Longrightarrow> var_pos y (Lam [x]. t) = (Cons In ` (var_pos y t))"
+ − 139
apply(simp add: eqvt_def var_pos_graph_def)
+ − 140
apply (rule, perm_simp, rule)
+ − 141
apply(rule TrueI)
+ − 142
apply(case_tac x)
+ − 143
apply(rule_tac y="b" and c="a" in lam.strong_exhaust)
+ − 144
apply(auto simp add: fresh_star_def)[3]
+ − 145
apply(simp_all)
+ − 146
apply(erule conjE)+
+ − 147
apply(erule_tac Abs_lst1_fcb2)
+ − 148
apply(simp add: pure_fresh)
+ − 149
apply(simp add: fresh_star_def)
+ − 150
apply(simp add: eqvt_at_def image_eqvt perm_supp_eq)
+ − 151
apply(perm_simp)
+ − 152
apply(rule refl)
+ − 153
apply(simp add: eqvt_at_def image_eqvt perm_supp_eq)
+ − 154
apply(perm_simp)
+ − 155
apply(rule refl)
+ − 156
done
+ − 157
+ − 158
termination by lexicographic_order
+ − 159
+ − 160
lemma var_pos1:
+ − 161
assumes "atom y \<notin> supp t"
+ − 162
shows "var_pos y t = {}"
+ − 163
using assms
+ − 164
apply(induct t rule: var_pos.induct)
+ − 165
apply(simp_all add: lam.supp supp_at_base fresh_at_base)
+ − 166
done
+ − 167
+ − 168
lemma var_pos2:
+ − 169
shows "var_pos y (Lam [y].t) = {}"
+ − 170
apply(rule var_pos1)
+ − 171
apply(simp add: lam.supp)
+ − 172
done
+ − 173
+ − 174
+ − 175
text {* strange substitution operation *}
+ − 176
+ − 177
nominal_primrec
+ − 178
subst' :: "lam \<Rightarrow> name \<Rightarrow> lam \<Rightarrow> lam" ("_ [_ ::== _]" [90, 90, 90] 90)
+ − 179
where
+ − 180
"(Var x)[y ::== s] = (if x = y then s else (Var x))"
+ − 181
| "(App t1 t2)[y ::== s] = App (t1[y ::== s]) (t2[y ::== s])"
+ − 182
| "atom x \<sharp> (y, s) \<Longrightarrow> (Lam [x]. t)[y ::== s] = Lam [x].(t[y ::== (App (Var y) s)])"
+ − 183
apply(simp add: eqvt_def subst'_graph_def)
+ − 184
apply (rule, perm_simp, rule)
+ − 185
apply(rule TrueI)
+ − 186
apply(case_tac x)
+ − 187
apply(rule_tac y="a" and c="(b, c)" in lam.strong_exhaust)
+ − 188
apply(auto simp add: fresh_star_def)[3]
+ − 189
apply(simp_all)
+ − 190
apply(erule conjE)+
+ − 191
apply (erule_tac c="(ya,sa)" in Abs_lst1_fcb2)
+ − 192
apply(simp_all add: Abs_fresh_iff)
+ − 193
apply(simp add: fresh_star_def fresh_Pair)
+ − 194
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
+ − 195
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
+ − 196
done
+ − 197
+ − 198
termination by lexicographic_order
+ − 199
+ − 200
2868
+ − 201
section {* free name function *}
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 202
2860
+ − 203
text {* first returns an atom list *}
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 204
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 205
nominal_primrec
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 206
frees_lst :: "lam \<Rightarrow> atom list"
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 207
where
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 208
"frees_lst (Var x) = [atom x]"
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 209
| "frees_lst (App t1 t2) = frees_lst t1 @ frees_lst t2"
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 210
| "frees_lst (Lam [x]. t) = removeAll (atom x) (frees_lst t)"
2868
+ − 211
unfolding eqvt_def
+ − 212
unfolding frees_lst_graph_def
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 213
apply (rule, perm_simp, rule)
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 214
apply(rule TrueI)
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 215
apply(rule_tac y="x" in lam.exhaust)
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 216
apply(auto)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 217
apply (erule_tac c="()" in Abs_lst1_fcb2)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 218
apply(simp add: supp_removeAll fresh_def)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 219
apply(simp add: fresh_star_def fresh_Unit)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 220
apply(simp add: eqvt_at_def removeAll_eqvt atom_eqvt)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 221
apply(simp add: eqvt_at_def removeAll_eqvt atom_eqvt)
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 222
done
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 223
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 224
termination
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 225
by lexicographic_order
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 226
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 227
text {* a small test lemma *}
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 228
lemma shows "supp t = set (frees_lst t)"
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 229
by (induct t rule: frees_lst.induct) (simp_all add: lam.supp supp_at_base)
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 230
2860
+ − 231
text {* second returns an atom set - therefore needs an invariant *}
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 232
2821
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 233
nominal_primrec (invariant "\<lambda>x (y::atom set). finite y")
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 234
frees_set :: "lam \<Rightarrow> atom set"
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 235
where
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 236
"frees_set (Var x) = {atom x}"
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 237
| "frees_set (App t1 t2) = frees_set t1 \<union> frees_set t2"
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 238
| "frees_set (Lam [x]. t) = (frees_set t) - {atom x}"
2845
+ − 239
apply(simp add: eqvt_def frees_set_graph_def)
+ − 240
apply(rule, perm_simp, rule)
+ − 241
apply(erule frees_set_graph.induct)
+ − 242
apply(auto)[9]
+ − 243
apply(rule_tac y="x" in lam.exhaust)
+ − 244
apply(auto)[3]
+ − 245
apply(simp)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 246
apply(erule_tac c="()" in Abs_lst1_fcb2)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 247
apply(simp add: fresh_minus_atom_set)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 248
apply(simp add: fresh_star_def fresh_Unit)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 249
apply(simp add: Diff_eqvt eqvt_at_def, perm_simp, rule refl)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 250
apply(simp add: Diff_eqvt eqvt_at_def, perm_simp, rule refl)
2845
+ − 251
done
2821
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 252
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 253
termination
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 254
by lexicographic_order
2821
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 255
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 256
lemma "frees_set t = supp t"
2845
+ − 257
by (induct rule: frees_set.induct) (simp_all add: lam.supp supp_at_base)
2821
c7d4bd9e89e0
fixed problem with earlier commit about nominal_function_common; added facility for specifying an invariant - added a definition of frees_set which need a finiteness invariant
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 258
2868
+ − 259
section {* height function *}
2431
331873ebc5cd
can now deal with type variables in nominal datatype definitions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 260
2666
+ − 261
nominal_primrec
2678
+ − 262
height :: "lam \<Rightarrow> int"
2666
+ − 263
where
2678
+ − 264
"height (Var x) = 1"
2683
+ − 265
| "height (App t1 t2) = max (height t1) (height t2) + 1"
+ − 266
| "height (Lam [x].t) = height t + 1"
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 267
apply(simp add: eqvt_def height_graph_def)
2791
+ − 268
apply (rule, perm_simp, rule)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 269
apply(rule TrueI)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 270
apply(rule_tac y="x" in lam.exhaust)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 271
apply(auto)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 272
apply (erule_tac c="()" in Abs_lst1_fcb2)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 273
apply(simp_all add: fresh_def pure_supp eqvt_at_def fresh_star_def)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 274
done
2666
+ − 275
+ − 276
termination
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 277
by lexicographic_order
2666
+ − 278
2707
+ − 279
thm height.simps
+ − 280
2683
+ − 281
2868
+ − 282
section {* capture-avoiding substitution *}
2683
+ − 283
2675
+ − 284
nominal_primrec
2683
+ − 285
subst :: "lam \<Rightarrow> name \<Rightarrow> lam \<Rightarrow> lam" ("_ [_ ::= _]" [90, 90, 90] 90)
2675
+ − 286
where
2683
+ − 287
"(Var x)[y ::= s] = (if x = y then s else (Var x))"
+ − 288
| "(App t1 t2)[y ::= s] = App (t1[y ::= s]) (t2[y ::= s])"
+ − 289
| "atom x \<sharp> (y, s) \<Longrightarrow> (Lam [x]. t)[y ::= s] = Lam [x].(t[y ::= s])"
2791
+ − 290
unfolding eqvt_def subst_graph_def
+ − 291
apply (rule, perm_simp, rule)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 292
apply(rule TrueI)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 293
apply(auto simp add: lam.distinct lam.eq_iff)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 294
apply(rule_tac y="a" and c="(aa, b)" in lam.strong_exhaust)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 295
apply(blast)+
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 296
apply(simp_all add: fresh_star_def fresh_Pair_elim)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 297
apply (erule_tac c="(ya,sa)" in Abs_lst1_fcb2)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 298
apply(simp_all add: Abs_fresh_iff)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 299
apply(simp add: fresh_star_def fresh_Pair)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 300
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 301
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
2675
+ − 302
done
+ − 303
2678
+ − 304
termination
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 305
by lexicographic_order
2683
+ − 306
+ − 307
lemma subst_eqvt[eqvt]:
+ − 308
shows "(p \<bullet> t[x ::= s]) = (p \<bullet> t)[(p \<bullet> x) ::= (p \<bullet> s)]"
+ − 309
by (induct t x s rule: subst.induct) (simp_all)
+ − 310
+ − 311
lemma forget:
+ − 312
shows "atom x \<sharp> t \<Longrightarrow> t[x ::= s] = t"
2845
+ − 313
by (nominal_induct t avoiding: x s rule: lam.strong_induct)
+ − 314
(auto simp add: lam.fresh fresh_at_base)
2683
+ − 315
+ − 316
text {* same lemma but with subst.induction *}
+ − 317
lemma forget2:
+ − 318
shows "atom x \<sharp> t \<Longrightarrow> t[x ::= s] = t"
2845
+ − 319
by (induct t x s rule: subst.induct)
+ − 320
(auto simp add: lam.fresh fresh_at_base fresh_Pair)
2683
+ − 321
+ − 322
lemma fresh_fact:
+ − 323
fixes z::"name"
+ − 324
assumes a: "atom z \<sharp> s"
2845
+ − 325
and b: "z = y \<or> atom z \<sharp> t"
2683
+ − 326
shows "atom z \<sharp> t[y ::= s]"
2845
+ − 327
using a b
+ − 328
by (nominal_induct t avoiding: z y s rule: lam.strong_induct)
+ − 329
(auto simp add: lam.fresh fresh_at_base)
2683
+ − 330
+ − 331
lemma substitution_lemma:
+ − 332
assumes a: "x \<noteq> y" "atom x \<sharp> u"
+ − 333
shows "t[x ::= s][y ::= u] = t[y ::= u][x ::= s[y ::= u]]"
+ − 334
using a
+ − 335
by (nominal_induct t avoiding: x y s u rule: lam.strong_induct)
+ − 336
(auto simp add: fresh_fact forget)
+ − 337
+ − 338
lemma subst_rename:
+ − 339
assumes a: "atom y \<sharp> t"
+ − 340
shows "t[x ::= s] = ((y \<leftrightarrow> x) \<bullet>t)[y ::= s]"
+ − 341
using a
+ − 342
apply (nominal_induct t avoiding: x y s rule: lam.strong_induct)
+ − 343
apply (auto simp add: lam.fresh fresh_at_base)
+ − 344
done
+ − 345
2767
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 346
lemma height_ge_one:
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 347
shows "1 \<le> (height e)"
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 348
by (induct e rule: lam.induct) (simp_all)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 349
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 350
theorem height_subst:
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 351
shows "height (e[x::=e']) \<le> ((height e) - 1) + (height e')"
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 352
proof (nominal_induct e avoiding: x e' rule: lam.strong_induct)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 353
case (Var y)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 354
have "1 \<le> height e'" by (rule height_ge_one)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 355
then show "height (Var y[x::=e']) \<le> height (Var y) - 1 + height e'" by simp
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 356
next
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 357
case (Lam y e1)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 358
hence ih: "height (e1[x::=e']) \<le> ((height e1) - 1) + (height e')" by simp
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 359
moreover
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 360
have vc: "atom y\<sharp>x" "atom y\<sharp>e'" by fact+ (* usual variable convention *)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 361
ultimately show "height ((Lam [y]. e1)[x::=e']) \<le> height (Lam [y]. e1) - 1 + height e'" by simp
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 362
next
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 363
case (App e1 e2)
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 364
hence ih1: "height (e1[x::=e']) \<le> ((height e1) - 1) + (height e')"
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 365
and ih2: "height (e2[x::=e']) \<le> ((height e2) - 1) + (height e')" by simp_all
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 366
then show "height ((App e1 e2)[x::=e']) \<le> height (App e1 e2) - 1 + height e'" by simp
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 367
qed
2683
+ − 368
+ − 369
subsection {* single-step beta-reduction *}
+ − 370
+ − 371
inductive
+ − 372
beta :: "lam \<Rightarrow> lam \<Rightarrow> bool" (" _ \<longrightarrow>b _" [80,80] 80)
+ − 373
where
+ − 374
b1[intro]: "t1 \<longrightarrow>b t2 \<Longrightarrow> App t1 s \<longrightarrow>b App t2 s"
+ − 375
| b2[intro]: "s1 \<longrightarrow>b s2 \<Longrightarrow> App t s1 \<longrightarrow>b App t s2"
+ − 376
| b3[intro]: "t1 \<longrightarrow>b t2 \<Longrightarrow> Lam [x]. t1 \<longrightarrow>b Lam [x]. t2"
+ − 377
| b4[intro]: "atom x \<sharp> s \<Longrightarrow> App (Lam [x]. t) s \<longrightarrow>b t[x ::= s]"
+ − 378
+ − 379
equivariance beta
+ − 380
+ − 381
nominal_inductive beta
+ − 382
avoids b4: "x"
+ − 383
by (simp_all add: fresh_star_def fresh_Pair lam.fresh fresh_fact)
+ − 384
+ − 385
text {* One-Reduction *}
+ − 386
+ − 387
inductive
+ − 388
One :: "lam \<Rightarrow> lam \<Rightarrow> bool" (" _ \<longrightarrow>1 _" [80,80] 80)
+ − 389
where
+ − 390
o1[intro]: "Var x \<longrightarrow>1 Var x"
+ − 391
| o2[intro]: "\<lbrakk>t1 \<longrightarrow>1 t2; s1 \<longrightarrow>1 s2\<rbrakk> \<Longrightarrow> App t1 s1 \<longrightarrow>1 App t2 s2"
+ − 392
| o3[intro]: "t1 \<longrightarrow>1 t2 \<Longrightarrow> Lam [x].t1 \<longrightarrow>1 Lam [x].t2"
+ − 393
| o4[intro]: "\<lbrakk>atom x \<sharp> (s1, s2); t1 \<longrightarrow>1 t2; s1 \<longrightarrow>1 s2\<rbrakk> \<Longrightarrow> App (Lam [x].t1) s1 \<longrightarrow>1 t2[x ::= s2]"
+ − 394
+ − 395
equivariance One
+ − 396
+ − 397
nominal_inductive One
+ − 398
avoids o3: "x"
+ − 399
| o4: "x"
+ − 400
by (simp_all add: fresh_star_def fresh_Pair lam.fresh fresh_fact)
+ − 401
+ − 402
lemma One_refl:
+ − 403
shows "t \<longrightarrow>1 t"
+ − 404
by (nominal_induct t rule: lam.strong_induct) (auto)
+ − 405
+ − 406
lemma One_subst:
+ − 407
assumes a: "t1 \<longrightarrow>1 t2" "s1 \<longrightarrow>1 s2"
+ − 408
shows "t1[x ::= s1] \<longrightarrow>1 t2[x ::= s2]"
+ − 409
using a
+ − 410
apply(nominal_induct t1 t2 avoiding: s1 s2 x rule: One.strong_induct)
+ − 411
apply(auto simp add: substitution_lemma fresh_at_base fresh_fact fresh_Pair)
+ − 412
done
+ − 413
+ − 414
lemma better_o4_intro:
+ − 415
assumes a: "t1 \<longrightarrow>1 t2" "s1 \<longrightarrow>1 s2"
+ − 416
shows "App (Lam [x]. t1) s1 \<longrightarrow>1 t2[ x ::= s2]"
+ − 417
proof -
2685
+ − 418
obtain y::"name" where fs: "atom y \<sharp> (x, t1, s1, t2, s2)" by (rule obtain_fresh)
2683
+ − 419
have "App (Lam [x]. t1) s1 = App (Lam [y]. ((y \<leftrightarrow> x) \<bullet> t1)) s1" using fs
+ − 420
by (auto simp add: lam.eq_iff Abs1_eq_iff' flip_def fresh_Pair fresh_at_base)
+ − 421
also have "\<dots> \<longrightarrow>1 ((y \<leftrightarrow> x) \<bullet> t2)[y ::= s2]" using fs a by (auto simp add: One.eqvt)
+ − 422
also have "\<dots> = t2[x ::= s2]" using fs by (simp add: subst_rename[symmetric])
+ − 423
finally show "App (Lam [x].t1) s1 \<longrightarrow>1 t2[x ::= s2]" by simp
+ − 424
qed
+ − 425
+ − 426
section {* Locally Nameless Terms *}
2678
+ − 427
2669
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 428
nominal_datatype ln =
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 429
LNBnd nat
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 430
| LNVar name
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 431
| LNApp ln ln
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 432
| LNLam ln
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 433
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 434
fun
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 435
lookup :: "name list \<Rightarrow> nat \<Rightarrow> name \<Rightarrow> ln"
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 436
where
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 437
"lookup [] n x = LNVar x"
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 438
| "lookup (y # ys) n x = (if x = y then LNBnd n else (lookup ys (n + 1) x))"
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 439
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 440
lemma supp_lookup:
2824
+ − 441
shows "supp (lookup xs n x) \<subseteq> {atom x}"
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 442
apply(induct arbitrary: n rule: lookup.induct)
2824
+ − 443
apply(simp add: ln.supp supp_at_base)
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 444
apply(simp add: ln.supp pure_supp)
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 445
done
2824
+ − 446
+ − 447
lemma supp_lookup_in:
+ − 448
shows "x \<in> set xs \<Longrightarrow> supp (lookup xs n x) = {}"
+ − 449
by (induct arbitrary: n rule: lookup.induct)(auto simp add: ln.supp pure_supp)
+ − 450
+ − 451
lemma supp_lookup_notin:
+ − 452
shows "x \<notin> set xs \<Longrightarrow> supp (lookup xs n x) = {atom x}"
+ − 453
by (induct arbitrary: n rule: lookup.induct) (auto simp add: ln.supp pure_supp supp_at_base)
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 454
2829
+ − 455
lemma supp_lookup_fresh:
+ − 456
shows "atom ` set xs \<sharp>* lookup xs n x"
+ − 457
by (case_tac "x \<in> set xs") (auto simp add: fresh_star_def fresh_def supp_lookup_in supp_lookup_notin)
+ − 458
+ − 459
lemma lookup_eqvt[eqvt]:
2669
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 460
shows "(p \<bullet> lookup xs n x) = lookup (p \<bullet> xs) (p \<bullet> n) (p \<bullet> x)"
2767
94f6f70e3067
New way of forward elimination of Abs1_eq and simplifications of the function obligation proofs.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 461
by (induct xs arbitrary: n) (simp_all add: permute_pure)
2669
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 462
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 463
text {* Function that translates lambda-terms into locally nameless terms *}
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 464
2826
+ − 465
nominal_primrec (invariant "\<lambda>(_, xs) y. atom ` set xs \<sharp>* y")
2669
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 466
trans :: "lam \<Rightarrow> name list \<Rightarrow> ln"
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 467
where
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 468
"trans (Var x) xs = lookup xs 0 x"
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 469
| "trans (App t1 t2) xs = LNApp (trans t1 xs) (trans t2 xs)"
2685
+ − 470
| "atom x \<sharp> xs \<Longrightarrow> trans (Lam [x]. t) xs = LNLam (trans t (x # xs))"
2829
+ − 471
apply (simp add: eqvt_def trans_graph_def)
+ − 472
apply (rule, perm_simp, rule)
2824
+ − 473
apply (erule trans_graph.induct)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 474
apply (auto simp add: ln.fresh)[3]
2829
+ − 475
apply (simp add: supp_lookup_fresh)
2824
+ − 476
apply (simp add: fresh_star_def ln.fresh)
+ − 477
apply (simp add: ln.fresh fresh_star_def)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 478
apply(auto)[1]
2829
+ − 479
apply (rule_tac y="a" and c="b" in lam.strong_exhaust)
+ − 480
apply (auto simp add: fresh_star_def)[3]
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 481
apply(simp_all)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 482
apply(erule conjE)+
2948
+ − 483
thm Abs_lst1_fcb2'
+ − 484
apply (erule_tac c="xsa" in Abs_lst1_fcb2')
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 485
apply (simp add: fresh_star_def)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 486
apply (simp add: fresh_star_def)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 487
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 488
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
2829
+ − 489
done
2669
1d1772a89026
the function translating lambda terms to locally nameless lambda terms; still needs a stronger abs_eq_iff lemma...at the moment only proved for restrictions
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 490
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 491
termination
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 492
by lexicographic_order
2827
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 493
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 494
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 495
text {* count the occurences of lambdas in a term *}
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 496
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 497
nominal_primrec
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 498
cntlams :: "lam \<Rightarrow> nat"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 499
where
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 500
"cntlams (Var x) = 0"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 501
| "cntlams (App t1 t2) = (cntlams t1) + (cntlams t2)"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 502
| "cntlams (Lam [x]. t) = Suc (cntlams t)"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 503
apply(simp add: eqvt_def cntlams_graph_def)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 504
apply(rule, perm_simp, rule)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 505
apply(rule TrueI)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 506
apply(rule_tac y="x" in lam.exhaust)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 507
apply(auto)[3]
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 508
apply(all_trivials)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 509
apply(simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 510
apply(simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 511
apply(erule_tac c="()" in Abs_lst1_fcb2')
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 512
apply(simp add: pure_fresh)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 513
apply(simp add: fresh_star_def pure_fresh)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 514
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 515
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 516
done
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 517
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 518
termination
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 519
by lexicographic_order
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 520
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 521
2860
+ − 522
text {* count the bound-variable occurences in a lambda-term *}
2827
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 523
2828
+ − 524
nominal_primrec
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 525
cntbvs :: "lam \<Rightarrow> name list \<Rightarrow> nat"
2827
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 526
where
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 527
"cntbvs (Var x) xs = (if x \<in> set xs then 1 else 0)"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 528
| "cntbvs (App t1 t2) xs = (cntbvs t1 xs) + (cntbvs t2 xs)"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 529
| "atom x \<sharp> xs \<Longrightarrow> cntbvs (Lam [x]. t) xs = cntbvs t (x # xs)"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 530
apply(simp add: eqvt_def cntbvs_graph_def)
2828
+ − 531
apply(rule, perm_simp, rule)
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 532
apply(rule TrueI)
2828
+ − 533
apply(case_tac x)
+ − 534
apply(rule_tac y="a" and c="b" in lam.strong_exhaust)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 535
apply(auto simp add: fresh_star_def)[3]
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 536
apply(all_trivials)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 537
apply(simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 538
apply(simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 539
apply(simp)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 540
apply(erule conjE)
2912
3c363a5070a5
copied all work to Lambda.thy; had to derive a special version of fcb1 for concrete atom
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 541
apply(erule Abs_lst1_fcb2')
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 542
apply(simp add: pure_fresh fresh_star_def)
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 543
apply(simp add: fresh_star_def)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 544
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 545
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
2828
+ − 546
done
2827
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 547
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 548
termination
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 549
by lexicographic_order
2827
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 550
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 551
section {* De Bruijn Terms *}
2827
394664816e24
defined the "count-bound-variables-occurences" function which has an accumulator like trans
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 552
2667
e3f8673085b1
added a translation function from lambda-terms to deBruijn terms (equivariance fails at the moment)
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 553
nominal_datatype db =
e3f8673085b1
added a translation function from lambda-terms to deBruijn terms (equivariance fails at the moment)
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 554
DBVar nat
e3f8673085b1
added a translation function from lambda-terms to deBruijn terms (equivariance fails at the moment)
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 555
| DBApp db db
e3f8673085b1
added a translation function from lambda-terms to deBruijn terms (equivariance fails at the moment)
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 556
| DBLam db
e3f8673085b1
added a translation function from lambda-terms to deBruijn terms (equivariance fails at the moment)
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 557
2942
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 558
lemma option_map_eqvt[eqvt]:
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 559
"p \<bullet> (Option.map f x) = Option.map (p \<bullet> f) (p \<bullet> x)"
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 560
by (cases x) (simp_all, simp add: permute_fun_app_eq)
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 561
2942
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 562
lemma option_bind_eqvt[eqvt]:
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 563
shows "(p \<bullet> (Option.map f c)) = (Option.map (p \<bullet> f) (p \<bullet> c))"
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 564
by (cases c) (simp_all, simp add: permute_fun_app_eq)
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 565
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 566
instance db :: pure
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 567
apply default
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 568
apply (induct_tac x rule: db.induct)
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 569
apply (simp_all add: permute_pure)
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 570
done
2795
+ − 571
+ − 572
lemma fresh_at_list: "atom x \<sharp> xs \<longleftrightarrow> x \<notin> set xs"
+ − 573
unfolding fresh_def supp_set[symmetric]
2845
+ − 574
by (induct xs) (auto simp add: supp_of_finite_insert supp_at_base supp_set_empty)
2795
+ − 575
2800
+ − 576
fun
+ − 577
vindex :: "name list \<Rightarrow> name \<Rightarrow> nat \<Rightarrow> db option"
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 578
where
2800
+ − 579
"vindex [] v n = None"
+ − 580
| "vindex (h # t) v n = (if v = h then (Some (DBVar n)) else (vindex t v (Suc n)))"
+ − 581
+ − 582
lemma vindex_eqvt[eqvt]:
+ − 583
"(p \<bullet> vindex l v n) = vindex (p \<bullet> l) (p \<bullet> v) (p \<bullet> n)"
+ − 584
by (induct l arbitrary: n) (simp_all add: permute_pure)
+ − 585
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 586
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 587
2800
+ − 588
nominal_primrec
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 589
transdb :: "lam \<Rightarrow> name list \<Rightarrow> db option"
2800
+ − 590
where
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 591
"transdb (Var x) l = vindex l x 0"
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 592
| "transdb (App t1 t2) xs =
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 593
Option.bind (transdb t1 xs) (\<lambda>d1. Option.bind (transdb t2 xs) (\<lambda>d2. Some (DBApp d1 d2)))"
2942
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 594
| "x \<notin> set xs \<Longrightarrow> transdb (Lam [x].t) xs = Option.map DBLam (transdb t (x # xs))"
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 595
unfolding eqvt_def transdb_graph_def
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 596
apply (rule, perm_simp, rule)
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 597
apply(rule TrueI)
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 598
apply (case_tac x)
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 599
apply (rule_tac y="a" and c="b" in lam.strong_exhaust)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 600
apply (auto simp add: fresh_star_def fresh_at_list)[3]
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 601
apply(simp_all)
2942
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 602
apply(elim conjE)
2912
3c363a5070a5
copied all work to Lambda.thy; had to derive a special version of fcb1 for concrete atom
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 603
apply (erule_tac c="xsa" in Abs_lst1_fcb2')
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 604
apply (simp add: pure_fresh)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 605
apply(simp add: fresh_star_def fresh_at_list)
2942
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 606
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq eqvts eqvts_raw)+
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 607
done
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 608
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 609
termination
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 610
by lexicographic_order
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 611
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 612
lemma transdb_eqvt[eqvt]:
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 613
"p \<bullet> transdb t l = transdb (p \<bullet>t) (p \<bullet>l)"
2942
fac8895b109a
Express trans_db with Option.map and Option.bind. Possibly mbind is a copy of bind?
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 614
apply (nominal_induct t avoiding: l rule: lam.strong_induct)
2800
+ − 615
apply (simp add: vindex_eqvt)
+ − 616
apply (simp_all add: permute_pure)
2797
+ − 617
apply (simp add: fresh_at_list)
2822
23befefc6e73
cleaned ups a bit the examples with the invariant framework; exported nominal_function_config datatype into separate structure and file
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 618
apply (subst transdb.simps)
2797
+ − 619
apply (simp add: fresh_at_list[symmetric])
2800
+ − 620
apply (drule_tac x="name # l" in meta_spec)
+ − 621
apply auto
2797
+ − 622
done
+ − 623
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 624
lemma db_trans_test:
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 625
assumes a: "y \<noteq> x"
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 626
shows "transdb (Lam [x]. Lam [y]. App (Var x) (Var y)) [] =
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 627
Some (DBLam (DBLam (DBApp (DBVar 1) (DBVar 0))))"
2795
+ − 628
using a by simp
2792
c4ed08a7454a
Defined translation from nominal to de-Bruijn; with a freshness condition for the lambda case.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 629
2841
+ − 630
lemma supp_subst:
+ − 631
"supp (t[x ::= s]) \<subseteq> supp t \<union> supp s"
+ − 632
by (induct t x s rule: subst.induct) (auto simp add: lam.supp)
+ − 633
+ − 634
lemma var_fresh_subst:
+ − 635
"atom x \<sharp> s \<Longrightarrow> atom x \<sharp> (t[x ::= s])"
+ − 636
by (induct t x s rule: subst.induct) (auto simp add: lam.supp lam.fresh fresh_at_base)
+ − 637
2834
+ − 638
(* function that evaluates a lambda term *)
+ − 639
nominal_primrec
+ − 640
eval :: "lam \<Rightarrow> lam" and
2860
+ − 641
apply_subst :: "lam \<Rightarrow> lam \<Rightarrow> lam"
2834
+ − 642
where
+ − 643
"eval (Var x) = Var x"
+ − 644
| "eval (Lam [x].t) = Lam [x].(eval t)"
2860
+ − 645
| "eval (App t1 t2) = apply_subst (eval t1) (eval t2)"
+ − 646
| "apply_subst (Var x) t2 = App (Var x) t2"
+ − 647
| "apply_subst (App t0 t1) t2 = App (App t0 t1) t2"
+ − 648
| "atom x \<sharp> t2 \<Longrightarrow> apply_subst (Lam [x].t1) t2 = eval (t1[x::= t2])"
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 649
apply(simp add: eval_apply_subst_graph_def eqvt_def)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 650
apply(rule, perm_simp, rule)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 651
apply(rule TrueI)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 652
apply (case_tac x)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 653
apply (case_tac a rule: lam.exhaust)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 654
apply simp_all[3]
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 655
apply blast
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 656
apply (case_tac b)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 657
apply (rule_tac y="a" and c="ba" in lam.strong_exhaust)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 658
apply simp_all[3]
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 659
apply blast
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 660
apply blast
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 661
apply (simp add: Abs1_eq_iff fresh_star_def)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 662
apply(simp_all)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 663
apply(erule_tac c="()" in Abs_lst1_fcb2)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 664
apply (simp add: Abs_fresh_iff)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 665
apply(simp add: fresh_star_def fresh_Unit)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 666
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 667
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 668
apply(erule conjE)
2912
3c363a5070a5
copied all work to Lambda.thy; had to derive a special version of fcb1 for concrete atom
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 669
apply(erule_tac c="t2a" in Abs_lst1_fcb2')
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 670
apply (erule fresh_eqvt_at)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 671
apply (simp add: finite_supp)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 672
apply (simp add: fresh_Inl var_fresh_subst)
2912
3c363a5070a5
copied all work to Lambda.thy; had to derive a special version of fcb1 for concrete atom
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 673
apply(simp add: fresh_star_def)
2902
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 674
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq subst_eqvt)
9c3f6a4d95d4
another change to the fcb2; this is needed in order to get all proofs through in Lambda.thy
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 675
apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq subst_eqvt)
2860
+ − 676
done
+ − 677
+ − 678
+ − 679
(* a small test
+ − 680
termination sorry
2845
+ − 681
2860
+ − 682
lemma
+ − 683
assumes "x \<noteq> y"
+ − 684
shows "eval (App (Lam [x].App (Var x) (Var x)) (Var y)) = App (Var y) (Var y)"
+ − 685
using assms
+ − 686
apply(simp add: lam.supp fresh_def supp_at_base)
+ − 687
done
+ − 688
*)
+ − 689
2852
+ − 690
+ − 691
text {* TODO: eqvt_at for the other side *}
+ − 692
nominal_primrec q where
+ − 693
"atom c \<sharp> (x, M) \<Longrightarrow> q (Lam [x]. M) (N :: lam) = Lam [x]. (Lam [c]. (App M (q (Var c) N)))"
+ − 694
| "q (Var x) N = Var x"
+ − 695
| "q (App l r) N = App l r"
+ − 696
unfolding eqvt_def q_graph_def
+ − 697
apply (rule, perm_simp, rule)
+ − 698
apply (rule TrueI)
+ − 699
apply (case_tac x)
+ − 700
apply (rule_tac y="a" in lam.exhaust)
+ − 701
apply simp_all
+ − 702
apply blast
+ − 703
apply blast
+ − 704
apply (rule_tac x="(name, lam)" and ?'a="name" in obtain_fresh)
+ − 705
apply blast
+ − 706
apply clarify
+ − 707
apply (rule_tac x="(x, xa, M, Ma, c, ca, Na)" and ?'a="name" in obtain_fresh)
+ − 708
apply (subgoal_tac "eqvt_at q_sumC (Var ca, Na)") --"Could come from nominal_function?"
+ − 709
apply (subgoal_tac "Lam [c]. App M (q_sumC (Var c, Na)) = Lam [a]. App M (q_sumC (Var a, Na))")
+ − 710
apply (subgoal_tac "Lam [ca]. App Ma (q_sumC (Var ca, Na)) = Lam [a]. App Ma (q_sumC (Var a, Na))")
+ − 711
apply (simp only:)
+ − 712
apply (erule Abs_lst1_fcb)
+ − 713
oops
+ − 714
2846
+ − 715
text {* Working Examples *}
+ − 716
+ − 717
nominal_primrec
+ − 718
map_term :: "(lam \<Rightarrow> lam) \<Rightarrow> lam \<Rightarrow> lam"
+ − 719
where
+ − 720
"eqvt f \<Longrightarrow> map_term f (Var x) = f (Var x)"
+ − 721
| "eqvt f \<Longrightarrow> map_term f (App t1 t2) = App (f t1) (f t2)"
+ − 722
| "eqvt f \<Longrightarrow> map_term f (Lam [x].t) = Lam [x].(f t)"
+ − 723
| "\<not>eqvt f \<Longrightarrow> map_term f t = t"
+ − 724
apply (simp add: eqvt_def map_term_graph_def)
+ − 725
apply (rule, perm_simp, rule)
+ − 726
apply(rule TrueI)
+ − 727
apply (case_tac x, case_tac "eqvt a", case_tac b rule: lam.exhaust)
+ − 728
apply auto
+ − 729
apply (erule Abs_lst1_fcb)
+ − 730
apply (simp_all add: Abs_fresh_iff fresh_fun_eqvt_app)
+ − 731
apply (simp add: eqvt_def permute_fun_app_eq)
+ − 732
done
+ − 733
+ − 734
termination
2858
de6b601c8d3d
added size-lemmas to simplifier; as a result termination can be proved by the standard lexicographic_order method
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 735
by lexicographic_order
2846
+ − 736
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 737
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 738
(*
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 739
abbreviation
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 740
mbind :: "'a option => ('a => 'b option) => 'b option" ("_ \<guillemotright>= _" [65,65] 65)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 741
where
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 742
"c \<guillemotright>= f \<equiv> case c of None => None | (Some v) => f v"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 743
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 744
lemma mbind_eqvt:
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 745
fixes c::"'a::pt option"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 746
shows "(p \<bullet> (c \<guillemotright>= f)) = ((p \<bullet> c) \<guillemotright>= (p \<bullet> f))"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 747
apply(cases c)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 748
apply(simp_all)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 749
apply(perm_simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 750
apply(rule refl)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 751
done
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 752
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 753
lemma mbind_eqvt_raw[eqvt_raw]:
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 754
shows "(p \<bullet> option_case) \<equiv> option_case"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 755
apply(rule eq_reflection)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 756
apply(rule ext)+
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 757
apply(case_tac xb)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 758
apply(simp_all)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 759
apply(rule_tac p="-p" in permute_boolE)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 760
apply(perm_simp add: permute_minus_cancel)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 761
apply(simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 762
apply(rule_tac p="-p" in permute_boolE)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 763
apply(perm_simp add: permute_minus_cancel)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 764
apply(simp)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 765
done
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 766
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 767
fun
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 768
index :: "atom list \<Rightarrow> nat \<Rightarrow> atom \<Rightarrow> nat option"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 769
where
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 770
"index [] n x = None"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 771
| "index (y # ys) n x = (if x = y then (Some n) else (index ys (n + 1) x))"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 772
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 773
lemma [eqvt]:
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 774
shows "(p \<bullet> index xs n x) = index (p \<bullet> xs) (p \<bullet> n) (p \<bullet> x)"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 775
apply(induct xs arbitrary: n)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 776
apply(simp_all add: permute_pure)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 777
done
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 778
*)
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 779
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 780
(*
2846
+ − 781
nominal_primrec
+ − 782
trans2 :: "lam \<Rightarrow> atom list \<Rightarrow> db option"
+ − 783
where
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 784
"trans2 (Var x) xs = (index xs 0 (atom x) \<guillemotright>= (\<lambda>n::nat. Some (DBVar n)))"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 785
| "trans2 (App t1 t2) xs =
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 786
((trans2 t1 xs) \<guillemotright>= (\<lambda>db1::db. (trans2 t2 xs) \<guillemotright>= (\<lambda>db2::db. Some (DBApp db1 db2))))"
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 787
| "trans2 (Lam [x].t) xs = (trans2 t (atom x # xs) \<guillemotright>= (\<lambda>db::db. Some (DBLam db)))"
2846
+ − 788
oops
2950
0911cb7bf696
changed bind to binds in specifications; bind will cause trouble with Monad_Syntax
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 789
*)
2846
+ − 790
+ − 791
nominal_primrec
+ − 792
CPS :: "lam \<Rightarrow> (lam \<Rightarrow> lam) \<Rightarrow> lam"
+ − 793
where
+ − 794
"CPS (Var x) k = Var x"
+ − 795
| "CPS (App M N) k = CPS M (\<lambda>m. CPS N (\<lambda>n. n))"
+ − 796
oops
+ − 797
+ − 798
consts b :: name
+ − 799
nominal_primrec
+ − 800
Z :: "lam \<Rightarrow> (lam \<Rightarrow> lam) \<Rightarrow> lam"
+ − 801
where
+ − 802
"Z (App M N) k = Z M (%m. (Z N (%n.(App m n))))"
+ − 803
| "Z (App M N) k = Z M (%m. (Z N (%n.(App (App m n) (Abs b (k (Var b)))))))"
+ − 804
unfolding eqvt_def Z_graph_def
+ − 805
apply (rule, perm_simp, rule)
+ − 806
oops
2789
32979078bfe9
functions involving if and case do not throw exceptions anymore; but eqvt_at assumption has now a precondition
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 807
2937
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 808
lemma test:
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 809
assumes "t = s"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 810
and "supp p \<sharp>* t" "supp p \<sharp>* x"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 811
and "(p \<bullet> t) = s \<Longrightarrow> (p \<bullet> x) = y"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 812
shows "x = y"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 813
using assms by (simp add: perm_supp_eq)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 814
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 815
lemma test2:
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 816
assumes "cs \<subseteq> as \<union> bs"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 817
and "as \<sharp>* x" "bs \<sharp>* x"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 818
shows "cs \<sharp>* x"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 819
using assms
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 820
by (auto simp add: fresh_star_def)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 821
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 822
lemma test3:
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 823
assumes "cs \<subseteq> as"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 824
and "as \<sharp>* x"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 825
shows "cs \<sharp>* x"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 826
using assms
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 827
by (auto simp add: fresh_star_def)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 828
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 829
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 830
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 831
nominal_primrec (invariant "\<lambda>(_, _, xs) y. atom ` fst ` set xs \<sharp>* y \<and> atom ` snd ` set xs \<sharp>* y")
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 832
aux :: "lam \<Rightarrow> lam \<Rightarrow> (name \<times> name) list \<Rightarrow> bool"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 833
where
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 834
"aux (Var x) (Var y) xs = ((x, y) \<in> set xs)"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 835
| "aux (App t1 t2) (App s1 s2) xs = (aux t1 s1 xs \<and> aux t2 s2 xs)"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 836
| "aux (Var x) (App t1 t2) xs = False"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 837
| "aux (Var x) (Lam [y].t) xs = False"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 838
| "aux (App t1 t2) (Var x) xs = False"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 839
| "aux (App t1 t2) (Lam [x].t) xs = False"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 840
| "aux (Lam [x].t) (Var y) xs = False"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 841
| "aux (Lam [x].t) (App t1 t2) xs = False"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 842
| "\<lbrakk>{atom x} \<sharp>* (s, xs); {atom y} \<sharp>* (t, xs); x \<noteq> y\<rbrakk> \<Longrightarrow>
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 843
aux (Lam [x].t) (Lam [y].s) xs = aux t s ((x, y) # xs)"
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 844
apply (simp add: eqvt_def aux_graph_def)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 845
apply (rule, perm_simp, rule)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 846
apply(erule aux_graph.induct)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 847
apply(simp_all add: fresh_star_def pure_fresh)[9]
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 848
apply(case_tac x)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 849
apply(simp)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 850
apply(rule_tac y="a" and c="(b, c)" in lam.strong_exhaust)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 851
apply(simp)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 852
apply(rule_tac y="b" and c="c" in lam.strong_exhaust)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 853
apply(metis)+
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 854
apply(simp)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 855
apply(rule_tac y="b" and c="c" in lam.strong_exhaust)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 856
apply(metis)+
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 857
apply(simp)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 858
apply(rule_tac y="b" and c="(lam, c, name)" in lam.strong_exhaust)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 859
apply(metis)+
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 860
apply(simp)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 861
apply(drule_tac x="name" in meta_spec)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 862
apply(drule_tac x="lama" in meta_spec)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 863
apply(drule_tac x="c" in meta_spec)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 864
apply(drule_tac x="namea" in meta_spec)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 865
apply(drule_tac x="lam" in meta_spec)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 866
apply(simp add: fresh_star_Pair)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 867
apply(simp add: fresh_star_def fresh_at_base lam.fresh)
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 868
apply(auto)[1]
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 869
apply(simp_all)[44]
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 870
apply(simp del: Product_Type.prod.inject)
2948
+ − 871
oops
2937
a56d422e17f6
added an example that recurses over two arguments; the interesting proof-obligation is not yet done
Christian Urban <urbanc@in.tum.de>
diff
changeset
+ − 872
2941
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 873
lemma abs_same_binder:
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 874
fixes t ta s sa :: "_ :: fs"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 875
assumes "sort_of (atom x) = sort_of (atom y)"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 876
shows "[[atom x]]lst. t = [[atom y]]lst. ta \<and> [[atom x]]lst. s = [[atom y]]lst. sa
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 877
\<longleftrightarrow> [[atom x]]lst. (t, s) = [[atom y]]lst. (ta, sa)"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 878
by (cases "atom x = atom y") (auto simp add: Abs1_eq_iff assms fresh_Pair)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 879
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 880
nominal_primrec
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 881
aux2 :: "lam \<Rightarrow> lam \<Rightarrow> bool"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 882
where
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 883
"aux2 (Var x) (Var y) = (x = y)"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 884
| "aux2 (App t1 t2) (App s1 s2) = (aux2 t1 s1 \<and> aux2 t2 s2)"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 885
| "aux2 (Var x) (App t1 t2) = False"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 886
| "aux2 (Var x) (Lam [y].t) = False"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 887
| "aux2 (App t1 t2) (Var x) = False"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 888
| "aux2 (App t1 t2) (Lam [x].t) = False"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 889
| "aux2 (Lam [x].t) (Var y) = False"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 890
| "aux2 (Lam [x].t) (App t1 t2) = False"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 891
| "x = y \<Longrightarrow> aux2 (Lam [x].t) (Lam [y].s) = aux2 t s"
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 892
apply(simp add: eqvt_def aux2_graph_def)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 893
apply(rule, perm_simp, rule, rule)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 894
apply(case_tac x)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 895
apply(rule_tac y="a" and c="b" in lam.strong_exhaust)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 896
apply(rule_tac y="b" in lam.exhaust)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 897
apply(auto)[3]
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 898
apply(rule_tac y="b" in lam.exhaust)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 899
apply(auto)[3]
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 900
apply(rule_tac y="b" and c="(name, lam)" in lam.strong_exhaust)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 901
apply(auto)[3]
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 902
apply(drule_tac x="name" in meta_spec)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 903
apply(drule_tac x="name" in meta_spec)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 904
apply(drule_tac x="lam" in meta_spec)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 905
apply(drule_tac x="(name \<leftrightarrow> namea) \<bullet> lama" in meta_spec)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 906
apply(simp add: Abs1_eq_iff fresh_star_def fresh_Pair_elim fresh_at_base lam.fresh flip_def)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 907
apply (metis Nominal2_Base.swap_commute fresh_permute_iff sort_of_atom_eq swap_atom_simps(2))
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 908
apply simp_all
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 909
apply (simp add: abs_same_binder)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 910
apply (erule_tac c="()" in Abs_lst1_fcb2)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 911
apply (simp_all add: pure_fresh fresh_star_def eqvt_at_def)
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 912
done
40991ebcda12
Define a version of aux only for same binders. Completeness is fine.
Cezary Kaliszyk <kaliszyk@in.tum.de>
diff
changeset
+ − 913
2940
+ − 914
text {* tests of functions containing if and case *}
+ − 915
+ − 916
consts P :: "lam \<Rightarrow> bool"
+ − 917
+ − 918
nominal_primrec
+ − 919
A :: "lam => lam"
+ − 920
where
+ − 921
"A (App M N) = (if (True \<or> P M) then (A M) else (A N))"
+ − 922
| "A (Var x) = (Var x)"
+ − 923
| "A (App M N) = (if True then M else A N)"
+ − 924
oops
+ − 925
+ − 926
nominal_primrec
+ − 927
C :: "lam => lam"
+ − 928
where
+ − 929
"C (App M N) = (case (True \<or> P M) of True \<Rightarrow> (A M) | False \<Rightarrow> (A N))"
+ − 930
| "C (Var x) = (Var x)"
+ − 931
| "C (App M N) = (if True then M else C N)"
+ − 932
oops
+ − 933
+ − 934
nominal_primrec
+ − 935
A :: "lam => lam"
+ − 936
where
+ − 937
"A (Lam [x].M) = (Lam [x].M)"
+ − 938
| "A (Var x) = (Var x)"
+ − 939
| "A (App M N) = (if True then M else A N)"
+ − 940
oops
+ − 941
+ − 942
nominal_primrec
+ − 943
B :: "lam => lam"
+ − 944
where
+ − 945
"B (Lam [x].M) = (Lam [x].M)"
+ − 946
| "B (Var x) = (Var x)"
+ − 947
| "B (App M N) = (if True then M else (B N))"
+ − 948
unfolding eqvt_def
+ − 949
unfolding B_graph_def
+ − 950
apply(perm_simp)
+ − 951
apply(rule allI)
+ − 952
apply(rule refl)
+ − 953
oops
+ − 954
1594
+ − 955
end
+ − 956
+ − 957
+ − 958