src/HOL/Nominal/Examples/Lam_Funs.thy
changeset 80914 d97fdabd9e2b
parent 80149 40a3fc07a587
equal deleted inserted replaced
80913:46f59511b7bb 80914:d97fdabd9e2b
    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')"