10 atom_decl name |
10 atom_decl name |
11 |
11 |
12 nominal_datatype lam = |
12 nominal_datatype lam = |
13 Var "name" |
13 Var "name" |
14 | App "lam" "lam" |
14 | App "lam" "lam" |
15 | Lam "\<guillemotleft>name\<guillemotright>lam" ("Lam [_]._" [100,100] 100) |
15 | Lam "\<guillemotleft>name\<guillemotright>lam" (\<open>Lam [_]._\<close> [100,100] 100) |
16 |
16 |
17 text \<open>The depth of a lambda-term.\<close> |
17 text \<open>The depth of a lambda-term.\<close> |
18 |
18 |
19 nominal_primrec |
19 nominal_primrec |
20 depth :: "lam \<Rightarrow> nat" |
20 depth :: "lam \<Rightarrow> nat" |
66 and X::"name" |
66 and X::"name" |
67 shows "pi\<bullet>(lookup \<theta> X) = lookup (pi\<bullet>\<theta>) (pi\<bullet>X)" |
67 shows "pi\<bullet>(lookup \<theta> X) = lookup (pi\<bullet>\<theta>) (pi\<bullet>X)" |
68 by (induct \<theta>) (auto simp add: eqvts) |
68 by (induct \<theta>) (auto simp add: eqvts) |
69 |
69 |
70 nominal_primrec |
70 nominal_primrec |
71 psubst :: "(name\<times>lam) list \<Rightarrow> lam \<Rightarrow> lam" ("_<_>" [95,95] 105) |
71 psubst :: "(name\<times>lam) list \<Rightarrow> lam \<Rightarrow> lam" (\<open>_<_>\<close> [95,95] 105) |
72 where |
72 where |
73 "\<theta><(Var x)> = (lookup \<theta> x)" |
73 "\<theta><(Var x)> = (lookup \<theta> x)" |
74 | "\<theta><(App e\<^sub>1 e\<^sub>2)> = App (\<theta><e\<^sub>1>) (\<theta><e\<^sub>2>)" |
74 | "\<theta><(App e\<^sub>1 e\<^sub>2)> = App (\<theta><e\<^sub>1>) (\<theta><e\<^sub>2>)" |
75 | "x\<sharp>\<theta> \<Longrightarrow> \<theta><(Lam [x].e)> = Lam [x].(\<theta><e>)" |
75 | "x\<sharp>\<theta> \<Longrightarrow> \<theta><(Lam [x].e)> = Lam [x].(\<theta><e>)" |
76 by (finite_guess | simp add: abs_fresh | fresh_guess)+ |
76 by (finite_guess | simp add: abs_fresh | fresh_guess)+ |
81 shows "pi\<bullet>(\<theta><t>) = (pi\<bullet>\<theta>)<(pi\<bullet>t)>" |
81 shows "pi\<bullet>(\<theta><t>) = (pi\<bullet>\<theta>)<(pi\<bullet>t)>" |
82 by (nominal_induct t avoiding: \<theta> rule: lam.strong_induct) |
82 by (nominal_induct t avoiding: \<theta> rule: lam.strong_induct) |
83 (simp_all add: eqvts fresh_bij) |
83 (simp_all add: eqvts fresh_bij) |
84 |
84 |
85 abbreviation |
85 abbreviation |
86 subst :: "lam \<Rightarrow> name \<Rightarrow> lam \<Rightarrow> lam" ("_[_::=_]" [100,100,100] 100) |
86 subst :: "lam \<Rightarrow> name \<Rightarrow> lam \<Rightarrow> lam" (\<open>_[_::=_]\<close> [100,100,100] 100) |
87 where |
87 where |
88 "t[x::=t'] \<equiv> ([(x,t')])<t>" |
88 "t[x::=t'] \<equiv> ([(x,t')])<t>" |
89 |
89 |
90 lemma subst[simp]: |
90 lemma subst[simp]: |
91 shows "(Var x)[y::=t'] = (if x=y then t' else (Var x))" |
91 shows "(Var x)[y::=t'] = (if x=y then t' else (Var x))" |
113 Contexts - lambda-terms with a single hole. |
113 Contexts - lambda-terms with a single hole. |
114 Note that the lambda case in contexts does not bind a |
114 Note that the lambda case in contexts does not bind a |
115 name, even if we introduce the notation [_]._ for CLam. |
115 name, even if we introduce the notation [_]._ for CLam. |
116 \<close> |
116 \<close> |
117 nominal_datatype clam = |
117 nominal_datatype clam = |
118 Hole ("\<box>" 1000) |
118 Hole (\<open>\<box>\<close> 1000) |
119 | CAppL "clam" "lam" |
119 | CAppL "clam" "lam" |
120 | CAppR "lam" "clam" |
120 | CAppR "lam" "clam" |
121 | CLam "name" "clam" ("CLam [_]._" [100,100] 100) |
121 | CLam "name" "clam" (\<open>CLam [_]._\<close> [100,100] 100) |
122 |
122 |
123 text \<open>Filling a lambda-term into a context.\<close> |
123 text \<open>Filling a lambda-term into a context.\<close> |
124 |
124 |
125 nominal_primrec |
125 nominal_primrec |
126 filling :: "clam \<Rightarrow> lam \<Rightarrow> lam" ("_\<lbrakk>_\<rbrakk>" [100,100] 100) |
126 filling :: "clam \<Rightarrow> lam \<Rightarrow> lam" (\<open>_\<lbrakk>_\<rbrakk>\<close> [100,100] 100) |
127 where |
127 where |
128 "\<box>\<lbrakk>t\<rbrakk> = t" |
128 "\<box>\<lbrakk>t\<rbrakk> = t" |
129 | "(CAppL E t')\<lbrakk>t\<rbrakk> = App (E\<lbrakk>t\<rbrakk>) t'" |
129 | "(CAppL E t')\<lbrakk>t\<rbrakk> = App (E\<lbrakk>t\<rbrakk>) t'" |
130 | "(CAppR t' E)\<lbrakk>t\<rbrakk> = App t' (E\<lbrakk>t\<rbrakk>)" |
130 | "(CAppR t' E)\<lbrakk>t\<rbrakk> = App t' (E\<lbrakk>t\<rbrakk>)" |
131 | "(CLam [x].E)\<lbrakk>t\<rbrakk> = Lam [x].(E\<lbrakk>t\<rbrakk>)" |
131 | "(CLam [x].E)\<lbrakk>t\<rbrakk> = Lam [x].(E\<lbrakk>t\<rbrakk>)" |
132 by (rule TrueI)+ |
132 by (rule TrueI)+ |
133 |
133 |
134 text \<open>Composition od two contexts\<close> |
134 text \<open>Composition od two contexts\<close> |
135 |
135 |
136 nominal_primrec |
136 nominal_primrec |
137 clam_compose :: "clam \<Rightarrow> clam \<Rightarrow> clam" ("_ \<circ> _" [100,100] 100) |
137 clam_compose :: "clam \<Rightarrow> clam \<Rightarrow> clam" (\<open>_ \<circ> _\<close> [100,100] 100) |
138 where |
138 where |
139 "\<box> \<circ> E' = E'" |
139 "\<box> \<circ> E' = E'" |
140 | "(CAppL E t') \<circ> E' = CAppL (E \<circ> E') t'" |
140 | "(CAppL E t') \<circ> E' = CAppL (E \<circ> E') t'" |
141 | "(CAppR t' E) \<circ> E' = CAppR t' (E \<circ> E')" |
141 | "(CAppR t' E) \<circ> E' = CAppR t' (E \<circ> E')" |
142 | "(CLam [x].E) \<circ> E' = CLam [x].(E \<circ> E')" |
142 | "(CLam [x].E) \<circ> E' = CLam [x].(E \<circ> E')" |