theory Lambda
imports "../Nominal2" 
begin


atom_decl name

nominal_datatype lam =
  Var "name"
| App "lam" "lam"
| Lam x::"name" l::"lam"  bind x in l ("Lam [_]. _" [100, 100] 100)

inductive 
  triv :: "lam \<Rightarrow> nat \<Rightarrow> bool"
where
  Var: "triv (Var x) n"

equivariance triv
nominal_inductive triv avoids Var : "{}::name set"
apply(auto simp add: fresh_star_def)
done 


text {* height function *}

nominal_primrec
  height :: "lam \<Rightarrow> int"
where
  "height (Var x) = 1"
| "height (App t1 t2) = max (height t1) (height t2) + 1"
| "height (Lam [x].t) = height t + 1"
defer
apply(rule_tac y="x" in lam.exhaust)
apply(auto simp add: lam.distinct lam.eq_iff)
apply(simp add: Abs_eq_iff alphas)
apply(clarify)
apply(subst (4) supp_perm_eq[where p="p", symmetric])
apply(simp add: pure_supp fresh_star_def)
apply(simp add: eqvt_at_def)
apply(subgoal_tac "\<And>p x r. height_graph x r \<Longrightarrow> height_graph (p \<bullet> x) (p \<bullet> r)") 
unfolding eqvt_def
apply(rule allI)
apply(simp add: permute_fun_def)
apply(rule ext)
apply(rule ext)
apply(simp add: permute_bool_def)
apply(rule iffI)
apply(drule_tac x="p" in meta_spec)
apply(drule_tac x="- p \<bullet> x" in meta_spec)
apply(drule_tac x="- p \<bullet> xa" in meta_spec)
apply(simp)
apply(drule_tac x="-p" in meta_spec)
apply(drule_tac x="x" in meta_spec)
apply(drule_tac x="xa" in meta_spec)
apply(simp)
apply(erule height_graph.induct)
apply(perm_simp)
apply(rule height_graph.intros)
apply(perm_simp)
apply(rule height_graph.intros)
apply(assumption)
apply(assumption)
apply(perm_simp)
apply(rule height_graph.intros)
apply(assumption)
done

termination
  by (relation "measure size") (simp_all add: lam.size)
  
thm height.simps

  
text {* free name function - returns atom lists *}

nominal_primrec 
  frees_lst :: "lam \<Rightarrow> atom list"
where
  "frees_lst (Var x) = [atom x]"
| "frees_lst (App t1 t2) = frees_lst t1 @ frees_lst t2"
| "frees_lst (Lam [x]. t) = removeAll (atom x) (frees_lst t)"
defer
apply(rule_tac y="x" in lam.exhaust)
apply(simp_all)[3]
apply(simp_all only: lam.distinct)
apply(simp add: lam.eq_iff)
apply(simp add: lam.eq_iff)
apply(simp add: lam.eq_iff)
apply(simp add: Abs_eq_iff)
apply(erule exE)
apply(simp add: alphas)
apply(simp add: atom_eqvt)
apply(clarify)
apply(rule trans)
apply(rule_tac p="p" in supp_perm_eq[symmetric])
apply(simp (no_asm) add: supp_removeAll)
apply(drule supp_eqvt_at)
apply(simp add: finite_supp)
apply(auto simp add: fresh_star_def)[1]
unfolding eqvt_at_def
apply(simp only: removeAll_eqvt atom_eqvt)
apply(subgoal_tac "\<And>p x r. frees_lst_graph x r \<Longrightarrow> frees_lst_graph (p \<bullet> x) (p \<bullet> r)") 
unfolding eqvt_def
apply(rule allI)
apply(simp add: permute_fun_def)
apply(rule ext)
apply(rule ext)
apply(simp add: permute_bool_def)
apply(rule iffI)
apply(drule_tac x="p" in meta_spec)
apply(drule_tac x="- p \<bullet> x" in meta_spec)
apply(drule_tac x="- p \<bullet> xa" in meta_spec)
apply(simp)
apply(drule_tac x="-p" in meta_spec)
apply(drule_tac x="x" in meta_spec)
apply(drule_tac x="xa" in meta_spec)
apply(simp)
apply(erule frees_lst_graph.induct)
apply(perm_simp)
apply(rule frees_lst_graph.intros)
apply(perm_simp)
apply(rule frees_lst_graph.intros)
apply(assumption)
apply(assumption)
apply(perm_simp)
apply(rule frees_lst_graph.intros)
apply(assumption)
done

termination
  apply(relation "measure size")
  apply(simp_all add: lam.size)
  done

text {* a small test lemma *}
lemma
  shows "supp t = set (frees_lst t)"
apply(induct t rule: frees_lst.induct)
apply(simp_all add: lam.supp supp_at_base)
done

text {* capture - avoiding substitution *}

nominal_primrec
  subst :: "lam \<Rightarrow> name \<Rightarrow> lam \<Rightarrow> lam"  ("_ [_ ::= _]" [90, 90, 90] 90)
where
  "(Var x)[y ::= s] = (if x = y then s else (Var x))"
| "(App t1 t2)[y ::= s] = App (t1[y ::= s]) (t2[y ::= s])"
| "atom x \<sharp> (y, s) \<Longrightarrow> (Lam [x]. t)[y ::= s] = Lam [x].(t[y ::= s])"
defer
apply(auto simp add: lam.distinct lam.eq_iff)
apply(rule_tac y="a" and c="(aa, b)" in lam.strong_exhaust)
apply(blast)+
apply(simp add: fresh_star_def)
apply(subgoal_tac "atom xa \<sharp> [[atom x]]lst. t")
apply(subst (asm) Abs_eq_iff2)
apply(simp add: alphas atom_eqvt)
apply(clarify)
apply(rule trans)
apply(rule_tac p="p" in supp_perm_eq[symmetric])
apply(rule fresh_star_supp_conv)
apply(drule fresh_star_perm_set_conv)
apply(simp add: finite_supp)
apply(subgoal_tac "{atom (p \<bullet> x), atom x} \<sharp>* ([[atom x]]lst. subst_sumC (t, ya, sa))")
apply(auto simp add: fresh_star_def)[1]
apply(simp (no_asm) add: fresh_star_def)
apply(rule conjI)
apply(simp (no_asm) add: Abs_fresh_iff)
apply(clarify)
apply(drule_tac a="atom (p \<bullet> x)" in fresh_eqvt_at)
apply(simp add: finite_supp)
apply(simp (no_asm_use) add: fresh_Pair)
apply(simp add: Abs_fresh_iff)
apply(simp)
apply(simp add: Abs_fresh_iff)
apply(subgoal_tac "p \<bullet> ya = ya")
apply(subgoal_tac "p \<bullet> sa = sa")
apply(simp add: atom_eqvt eqvt_at_def)
apply(rule perm_supp_eq)
apply(auto simp add: fresh_star_def fresh_Pair)[1]
apply(rule perm_supp_eq)
apply(auto simp add: fresh_star_def fresh_Pair)[1]
apply(simp add: Abs_fresh_iff)
apply(subgoal_tac "\<And>p x r. subst_graph x r \<Longrightarrow> subst_graph (p \<bullet> x) (p \<bullet> r)") 
unfolding eqvt_def
apply(rule allI)
apply(simp add: permute_fun_def)
apply(rule ext)
apply(rule ext)
apply(simp add: permute_bool_def)
apply(rule iffI)
apply(drule_tac x="p" in meta_spec)
apply(drule_tac x="- p \<bullet> x" in meta_spec)
apply(drule_tac x="- p \<bullet> xa" in meta_spec)
apply(simp)
apply(drule_tac x="-p" in meta_spec)
apply(drule_tac x="x" in meta_spec)
apply(drule_tac x="xa" in meta_spec)
apply(simp)
apply(erule subst_graph.induct)
apply(perm_simp)
apply(rule subst_graph.intros)
apply(perm_simp)
apply(rule subst_graph.intros)
apply(assumption)
apply(assumption)
apply(perm_simp)
apply(rule subst_graph.intros)
apply(simp add: fresh_Pair)
apply(assumption)
done

termination
  by (relation "measure (\<lambda>(t,_,_). size t)")
     (simp_all add: lam.size)

lemma subst_eqvt[eqvt]:
  shows "(p \<bullet> t[x ::= s]) = (p \<bullet> t)[(p \<bullet> x) ::= (p \<bullet> s)]"
by (induct t x s rule: subst.induct) (simp_all)

lemma forget:
  shows "atom x \<sharp> t \<Longrightarrow> t[x ::= s] = t"
apply(nominal_induct t avoiding: x s rule: lam.strong_induct)
apply(auto simp add: lam.fresh fresh_at_base)
done

text {* same lemma but with subst.induction *}
lemma forget2:
  shows "atom x \<sharp> t \<Longrightarrow> t[x ::= s] = t"
apply(induct t x s rule: subst.induct)
apply(auto simp add: lam.fresh fresh_at_base fresh_Pair)
done

lemma fresh_fact:
  fixes z::"name"
  assumes a: "atom z \<sharp> s"
  and b: "z = y \<or> atom z \<sharp> t"
  shows "atom z \<sharp> t[y ::= s]"
using a b
apply (nominal_induct t avoiding: z y s rule: lam.strong_induct)
apply (auto simp add: lam.fresh fresh_at_base)
done

lemma substitution_lemma:  
  assumes a: "x \<noteq> y" "atom x \<sharp> u"
  shows "t[x ::= s][y ::= u] = t[y ::= u][x ::= s[y ::= u]]"
using a 
by (nominal_induct t avoiding: x y s u rule: lam.strong_induct)
   (auto simp add: fresh_fact forget)

lemma subst_rename: 
  assumes a: "atom y \<sharp> t"
  shows "t[x ::= s] = ((y \<leftrightarrow> x) \<bullet>t)[y ::= s]"
using a 
apply (nominal_induct t avoiding: x y s rule: lam.strong_induct)
apply (auto simp add: lam.fresh fresh_at_base)
done


subsection {* single-step beta-reduction *}

inductive 
  beta :: "lam \<Rightarrow> lam \<Rightarrow> bool" (" _ \<longrightarrow>b _" [80,80] 80)
where
  b1[intro]: "t1 \<longrightarrow>b t2 \<Longrightarrow> App t1 s \<longrightarrow>b App t2 s"
| b2[intro]: "s1 \<longrightarrow>b s2 \<Longrightarrow> App t s1 \<longrightarrow>b App t s2"
| b3[intro]: "t1 \<longrightarrow>b t2 \<Longrightarrow> Lam [x]. t1 \<longrightarrow>b Lam [x]. t2"
| b4[intro]: "atom x \<sharp> s \<Longrightarrow> App (Lam [x]. t) s \<longrightarrow>b t[x ::= s]"

equivariance beta

nominal_inductive beta
  avoids b4: "x"
  by (simp_all add: fresh_star_def fresh_Pair lam.fresh fresh_fact)

text {* One-Reduction *}

inductive 
  One :: "lam \<Rightarrow> lam \<Rightarrow> bool" (" _ \<longrightarrow>1 _" [80,80] 80)
where
  o1[intro]: "Var x \<longrightarrow>1 Var x"
| o2[intro]: "\<lbrakk>t1 \<longrightarrow>1 t2; s1 \<longrightarrow>1 s2\<rbrakk> \<Longrightarrow> App t1 s1 \<longrightarrow>1 App t2 s2"
| o3[intro]: "t1 \<longrightarrow>1 t2 \<Longrightarrow> Lam [x].t1 \<longrightarrow>1 Lam [x].t2"
| 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]"

equivariance One

nominal_inductive One 
  avoids o3: "x"
      |  o4: "x"
  by (simp_all add: fresh_star_def fresh_Pair lam.fresh fresh_fact)

lemma One_refl:
  shows "t \<longrightarrow>1 t"
by (nominal_induct t rule: lam.strong_induct) (auto)

lemma One_subst: 
  assumes a: "t1 \<longrightarrow>1 t2" "s1 \<longrightarrow>1 s2"
  shows "t1[x ::= s1] \<longrightarrow>1 t2[x ::= s2]" 
using a 
apply(nominal_induct t1 t2 avoiding: s1 s2 x rule: One.strong_induct)
apply(auto simp add: substitution_lemma fresh_at_base fresh_fact fresh_Pair)
done

lemma better_o4_intro:
  assumes a: "t1 \<longrightarrow>1 t2" "s1 \<longrightarrow>1 s2"
  shows "App (Lam [x]. t1) s1 \<longrightarrow>1 t2[ x ::= s2]"
proof -
  obtain y::"name" where fs: "atom y \<sharp> (x, t1, s1, t2, s2)" by (rule obtain_fresh)
  have "App (Lam [x]. t1) s1 = App (Lam [y]. ((y \<leftrightarrow> x) \<bullet> t1)) s1" using fs
    by (auto simp add: lam.eq_iff Abs1_eq_iff' flip_def fresh_Pair fresh_at_base)
  also have "\<dots> \<longrightarrow>1 ((y \<leftrightarrow> x) \<bullet> t2)[y ::= s2]" using fs a by (auto simp add: One.eqvt)
  also have "\<dots> = t2[x ::= s2]" using fs by (simp add: subst_rename[symmetric])
  finally show "App (Lam [x].t1) s1 \<longrightarrow>1 t2[x ::= s2]" by simp
qed



section {* Locally Nameless Terms *}

nominal_datatype ln = 
  LNBnd nat
| LNVar name
| LNApp ln ln
| LNLam ln

fun
  lookup :: "name list \<Rightarrow> nat \<Rightarrow> name \<Rightarrow> ln" 
where
  "lookup [] n x = LNVar x"
| "lookup (y # ys) n x = (if x = y then LNBnd n else (lookup ys (n + 1) x))"

lemma [eqvt]:
  shows "(p \<bullet> lookup xs n x) = lookup (p \<bullet> xs) (p \<bullet> n) (p \<bullet> x)"
  apply(induct xs arbitrary: n)
  apply(simp_all add: permute_pure)
  done

nominal_primrec
  trans :: "lam \<Rightarrow> name list \<Rightarrow> ln"
where
  "trans (Var x) xs = lookup xs 0 x"
| "trans (App t1 t2) xs = LNApp (trans t1 xs) (trans t2 xs)"
| "atom x \<sharp> xs \<Longrightarrow> trans (Lam [x]. t) xs = LNLam (trans t (x # xs))"
defer
apply(case_tac x)
apply(simp)
apply(rule_tac y="a" and c="b" in lam.strong_exhaust)
apply(simp_all add: fresh_star_def)[3]
apply(blast)
apply(blast)
apply(simp_all add: lam.distinct)
apply(simp add: lam.eq_iff)
apply(simp add: lam.eq_iff)
apply(simp add: lam.eq_iff)
apply(erule conjE)
apply(subgoal_tac "atom xa \<sharp> [[atom x]]lst. t")
prefer 2
apply(simp add: Abs_fresh_iff)
apply(subst (asm) Abs_eq_iff2)
apply(auto)
apply(simp add: alphas)
apply(simp add: atom_eqvt)
apply(clarify)
apply(rule trans)
apply(rule_tac p="p" in supp_perm_eq[symmetric])
prefer 2
apply (subgoal_tac "p \<bullet> xsa = xsa")
apply (simp add: eqvt_at_def)
apply (rule supp_perm_eq)
apply (rule fresh_star_supp_conv)
apply (subgoal_tac "{atom (p \<bullet> x), atom x} \<sharp>* xsa")
apply (simp add: fresh_star_def fresh_def)
apply blast
apply (simp add: fresh_star_def fresh_def)
apply (simp add:  ln.supp)
apply(rule fresh_star_supp_conv)
apply (subst (asm) supp_perm_pair)
apply (elim disjE)
apply (simp add: fresh_star_def supp_zero_perm)
apply (simp add: flip_def[symmetric])
apply(subgoal_tac "supp (x \<leftrightarrow> p \<bullet> x) \<sharp>* trans_sumC (t, x # xsa)")
apply simp
apply (subst flip_def)
apply (simp add: supp_swap)
apply (simp add: fresh_star_def)
apply (rule)
apply rule
prefer 2
apply(drule_tac a="atom (p \<bullet> x)" in fresh_eqvt_at)
apply(simp add: finite_supp)
apply(simp (no_asm_use) add: fresh_Pair)
apply(simp add: Abs_fresh_iff fresh_Cons)[1]
apply (metis Rep_name_inverse atom_name_def fresh_at_base)
apply assumption
oops

(* lemma helpr: "atom x \<sharp> ta \<Longrightarrow> Lam [xa]. ta = Lam [x]. ((xa \<leftrightarrow> x) \<bullet> ta)"
  apply (case_tac "x = xa")
  apply simp
  apply (simp add: lam.eq_iff Abs1_eq_iff flip_def[symmetric])
  by (metis atom_eqvt flip_at_simps(2) fresh_permute_iff)

lemma supp_lookup: "supp (lookup l n name) = {atom name} - supp l"
  apply (induct l arbitrary: n)
  apply (simp_all add: ln.supp supp_at_base supp_Nil supp_Cons pure_supp)
  done

lemma trans_eqvt[eqvt]: "p \<bullet> (trans t l) = trans (p \<bullet> t) (p \<bullet> l)"
  apply (induct t l rule: trans.induct)
  apply simp_all
  apply (simp add: eqvts permute_pure)
  done

lemma diff_un: "a - (b \<union> c) = a - b - c"
  by blast

lemma supp_trans: "supp (trans t l) = supp t - supp l"
  apply (induct t arbitrary: l rule: lam.induct)
  apply (simp_all add: lam.supp supp_at_base supp_lookup ln.supp)
  apply blast
  apply (rule_tac x="(lam, l)" and ?'a="name" in obtain_fresh)
  apply (simp add: fresh_Pair)
  apply clarify
  apply (subgoal_tac "supp (Lambda.trans (Lam [a]. ((name \<leftrightarrow> a) \<bullet> lam)) l) =
    supp lam - {atom name} - supp l")
  using helpr
  apply simp
  apply (simp add: ln.supp)
  apply (subgoal_tac "supp ((name \<leftrightarrow> a) \<bullet> (Lambda.trans lam ((name \<leftrightarrow> a) \<bullet> (a # l)))) = supp lam - {atom name} - supp l")
  apply (simp add: trans_eqvt)
  apply (simp add: supp_eqvt[symmetric])
  apply (simp add: Diff_eqvt)
  apply (simp add: supp_eqvt supp_Cons  union_eqvt)
  apply (simp add: diff_un)
  apply (tactic {* Cong_Tac.cong_tac @{thm cong} 1*})
  apply (tactic {* Cong_Tac.cong_tac @{thm cong} 1*})
  apply rule
  prefer 2
  apply rule
  apply (simp add: supp_at_base)
  apply (subgoal_tac "(name \<leftrightarrow> a) \<bullet> (supp lam - {atom name}) = supp lam - {atom name}")
  apply (simp add: eqvts)
  unfolding flip_def
  apply (rule swap_fresh_fresh)
apply (metis fresh_at_base fresh_def fresh_minus_atom_set lam.fsupp supp_at_base)
by (metis fresh_def fresh_finite_atom_set fresh_minus_atom_set lam.fsupp)

lemma "atom x \<sharp> trans_sumC (t, x # xsa)"
  by (simp add: fresh_def meta_eq_to_obj_eq[OF trans_def, symmetric, unfolded fun_eq_iff] supp_trans supp_Cons supp_at_base)
*)

nominal_datatype db = 
  DBVar nat
| DBApp db db
| DBLam db

abbreviation
  mbind :: "'a option => ('a => 'b option) => 'b option"  ("_ \<guillemotright>= _" [65,65] 65) 
where  
  "c \<guillemotright>= f \<equiv> case c of None => None | (Some v) => f v"

lemma mbind_eqvt:
  fixes c::"'a::pt option"
  shows "(p \<bullet> (c \<guillemotright>= f)) = ((p \<bullet> c) \<guillemotright>= (p \<bullet> f))"
apply(cases c)
apply(simp_all)
apply(perm_simp)
apply(rule refl)
done

lemma mbind_eqvt_raw[eqvt_raw]:
  shows "(p \<bullet> option_case) \<equiv> option_case"
apply(rule eq_reflection)
apply(rule ext)+
apply(case_tac xb)
apply(simp_all)
apply(rule_tac p="-p" in permute_boolE)
apply(perm_simp add: permute_minus_cancel)
apply(simp)
apply(rule_tac p="-p" in permute_boolE)
apply(perm_simp add: permute_minus_cancel)
apply(simp)
done

fun
  index :: "atom list \<Rightarrow> nat \<Rightarrow> atom \<Rightarrow> nat option" 
where
  "index [] n x = None"
| "index (y # ys) n x = (if x = y then (Some n) else (index ys (n + 1) x))"

lemma [eqvt]:
  shows "(p \<bullet> index xs n x) = index (p \<bullet> xs) (p \<bullet> n) (p \<bullet> x)"
apply(induct xs arbitrary: n)
apply(simp_all add: permute_pure)
done

(*
nominal_primrec
  trans :: "lam \<Rightarrow> atom list \<Rightarrow> db option"
where
  "trans (Var x) xs = (index xs 0 (atom x) \<guillemotright>= (\<lambda>n. Some (DBVar n)))"
| "trans (App t1 t2) xs = ((trans t1 xs) \<guillemotright>= (\<lambda>db1. (trans t2 xs) \<guillemotright>= (\<lambda>db2. Some (DBApp db1 db2))))"
| "trans (Lam [x].t) xs = (trans t (atom x # xs) \<guillemotright>= (\<lambda>db. Some (DBLam db)))"
*)



end