theory Lambda
imports "../Nominal2" 
begin

lemma Abs_lst_fcb2:
  fixes as bs :: "atom list"
    and x y :: "'b :: fs"
    and c::"'c::fs"
  assumes eq: "[as]lst. x = [bs]lst. y"
  and fcb1: "(set as) \<sharp>* f as x c"
  and fresh1: "set as \<sharp>* c"
  and fresh2: "set bs \<sharp>* c"
  and perm1: "\<And>p. supp p \<sharp>* c \<Longrightarrow> p \<bullet> (f as x c) = f (p \<bullet> as) (p \<bullet> x) c"
  and perm2: "\<And>p. supp p \<sharp>* c \<Longrightarrow> p \<bullet> (f bs y c) = f (p \<bullet> bs) (p \<bullet> y) c"
  shows "f as x c = f bs y c"
proof -
  have "supp (as, x, c) supports (f as x c)"
    unfolding  supports_def fresh_def[symmetric]
    by (simp add: fresh_Pair perm1 fresh_star_def supp_swap swap_fresh_fresh)
  then have fin1: "finite (supp (f as x c))"
    by (auto intro: supports_finite simp add: finite_supp)
  have "supp (bs, y, c) supports (f bs y c)"
    unfolding  supports_def fresh_def[symmetric]
    by (simp add: fresh_Pair perm2 fresh_star_def supp_swap swap_fresh_fresh)
  then have fin2: "finite (supp (f bs y c))"
    by (auto intro: supports_finite simp add: finite_supp)
  obtain q::"perm" where 
    fr1: "(q \<bullet> (set as)) \<sharp>* (x, c, f as x c, f bs y c)" and 
    fr2: "supp q \<sharp>* Abs_lst as x" and 
    inc: "supp q \<subseteq> (set as) \<union> q \<bullet> (set as)"
    using at_set_avoiding3[where xs="set as" and c="(x, c, f as x c, f bs y c)" and x="[as]lst. x"]  
      fin1 fin2
    by (auto simp add: supp_Pair finite_supp Abs_fresh_star dest: fresh_star_supp_conv)
  have "Abs_lst (q \<bullet> as) (q \<bullet> x) = q \<bullet> Abs_lst as x" by simp
  also have "\<dots> = Abs_lst as x"
    by (simp only: fr2 perm_supp_eq)
  finally have "Abs_lst (q \<bullet> as) (q \<bullet> x) = Abs_lst bs y" using eq by simp
  then obtain r::perm where 
    qq1: "q \<bullet> x = r \<bullet> y" and 
    qq2: "q \<bullet> as = r \<bullet> bs" and 
    qq3: "supp r \<subseteq> (q \<bullet> (set as)) \<union> set bs"
    apply(drule_tac sym)
    apply(simp only: Abs_eq_iff2 alphas)
    apply(erule exE)
    apply(erule conjE)+
    apply(drule_tac x="p" in meta_spec)
    apply(simp add: set_eqvt)
    apply(blast)
    done
  have "(set as) \<sharp>* f as x c" by (rule fcb1)
  then have "q \<bullet> ((set as) \<sharp>* f as x c)"
    by (simp add: permute_bool_def)
  then have "set (q \<bullet> as) \<sharp>* f (q \<bullet> as) (q \<bullet> x) c"
    apply(simp add: fresh_star_eqvt set_eqvt)
    apply(subst (asm) perm1)
    using inc fresh1 fr1
    apply(auto simp add: fresh_star_def fresh_Pair)
    done
  then have "set (r \<bullet> bs) \<sharp>* f (r \<bullet> bs) (r \<bullet> y) c" using qq1 qq2 by simp
  then have "r \<bullet> ((set bs) \<sharp>* f bs y c)"
    apply(simp add: fresh_star_eqvt set_eqvt)
    apply(subst (asm) perm2[symmetric])
    using qq3 fresh2 fr1
    apply(auto simp add: set_eqvt fresh_star_def fresh_Pair)
    done
  then have fcb2: "(set bs) \<sharp>* f bs y c" by (simp add: permute_bool_def)
  have "f as x c = q \<bullet> (f as x c)"
    apply(rule perm_supp_eq[symmetric])
    using inc fcb1 fr1 by (auto simp add: fresh_star_def)
  also have "\<dots> = f (q \<bullet> as) (q \<bullet> x) c" 
    apply(rule perm1)
    using inc fresh1 fr1 by (auto simp add: fresh_star_def)
  also have "\<dots> = f (r \<bullet> bs) (r \<bullet> y) c" using qq1 qq2 by simp
  also have "\<dots> = r \<bullet> (f bs y c)"
    apply(rule perm2[symmetric])
    using qq3 fresh2 fr1 by (auto simp add: fresh_star_def)
  also have "... = f bs y c"
    apply(rule perm_supp_eq)
    using qq3 fr1 fcb2 by (auto simp add: fresh_star_def)
  finally show ?thesis by simp
qed

lemma Abs_lst1_fcb2:
  fixes a b :: "atom"
    and x y :: "'b :: fs"
    and c::"'c :: fs"
  assumes e: "(Abs_lst [a] x) = (Abs_lst [b] y)"
  and fcb1: "a \<sharp> f a x c"
  and fresh: "{a, b} \<sharp>* c"
  and perm1: "\<And>p. supp p \<sharp>* c \<Longrightarrow> p \<bullet> (f a x c) = f (p \<bullet> a) (p \<bullet> x) c"
  and perm2: "\<And>p. supp p \<sharp>* c \<Longrightarrow> p \<bullet> (f b y c) = f (p \<bullet> b) (p \<bullet> y) c"
  shows "f a x c = f b y c"
using e
apply(drule_tac Abs_lst_fcb2[where c="c" and f="\<lambda>(as::atom list) . f (hd as)"])
apply(simp_all)
using fcb1 fresh perm1 perm2
apply(simp_all add: fresh_star_def)
done

lemma Abs_lst1_fcb2':
  fixes a b :: "'a::at"
    and x y :: "'b :: fs"
    and c::"'c :: fs"
  assumes e: "(Abs_lst [atom a] x) = (Abs_lst [atom b] y)"
  and fcb1: "atom a \<sharp> f a x c"
  and fresh: "{atom a, atom b} \<sharp>* c"
  and perm1: "\<And>p. supp p \<sharp>* c \<Longrightarrow> p \<bullet> (f a x c) = f (p \<bullet> a) (p \<bullet> x) c"
  and perm2: "\<And>p. supp p \<sharp>* c \<Longrightarrow> p \<bullet> (f b y c) = f (p \<bullet> b) (p \<bullet> y) c"
  shows "f a x c = f b y c"
using e
apply(drule_tac Abs_lst1_fcb2[where c="c" and f="\<lambda>a . f ((inv atom) a)"])
using  fcb1 fresh perm1 perm2
apply(simp_all add: fresh_star_def inv_f_f inj_on_def atom_eqvt)
done


atom_decl name

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

ML {* Method.SIMPLE_METHOD' *}
ML {* Sign.intern_const *}

ML {*
val test:((Proof.context -> Method.method) context_parser) =
Scan.succeed (fn ctxt =>
 let
   val _ = Inductive.the_inductive ctxt "local.frees_lst_graph"
 in 
   Method.SIMPLE_METHOD' (K all_tac)
 end)
*}

method_setup test = {* test *} {* test *}

section {* free name function *}

text {* first returns an atom list *}

ML Thm.implies_intr

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)"
  unfolding eqvt_def
  unfolding frees_lst_graph_def
  apply (rule, perm_simp, rule)
apply(rule TrueI)
apply(rule_tac y="x" in lam.exhaust)
apply(auto)
apply (erule_tac c="()" in Abs_lst1_fcb2)
apply(simp add: supp_removeAll fresh_def)
apply(simp add: fresh_star_def fresh_Unit)
apply(simp add: eqvt_at_def removeAll_eqvt atom_eqvt)
apply(simp add: eqvt_at_def removeAll_eqvt atom_eqvt)
done

termination
  by lexicographic_order

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

text {* second returns an atom set - therefore needs an invariant *}

nominal_primrec (invariant "\<lambda>x (y::atom set). finite y")
  frees_set :: "lam \<Rightarrow> atom set"
where
  "frees_set (Var x) = {atom x}"
| "frees_set (App t1 t2) = frees_set t1 \<union> frees_set t2"
| "frees_set (Lam [x]. t) = (frees_set t) - {atom x}"
  apply(simp add: eqvt_def frees_set_graph_def)
  apply(rule, perm_simp, rule)
  apply(erule frees_set_graph.induct)
  apply(auto)[9]
  apply(rule_tac y="x" in lam.exhaust)
  apply(auto)[3]
  apply(simp)
  apply(erule_tac c="()" in Abs_lst1_fcb2)
  apply(simp add: fresh_minus_atom_set)
  apply(simp add: fresh_star_def fresh_Unit)
  apply(simp add: Diff_eqvt eqvt_at_def, perm_simp, rule refl)
  apply(simp add: Diff_eqvt eqvt_at_def, perm_simp, rule refl)
  done

termination 
  by lexicographic_order

lemma "frees_set t = supp t"
  by (induct rule: frees_set.induct) (simp_all add: lam.supp supp_at_base)

lemma fresh_fun_eqvt_app3:
  assumes a: "eqvt f"
  and b: "a \<sharp> x" "a \<sharp> y" "a \<sharp> z"
  shows "a \<sharp> f x y z"
  using fresh_fun_eqvt_app[OF a b(1)] a b
  by (metis fresh_fun_app)


section {* 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"
  apply(simp add: eqvt_def height_graph_def)
  apply (rule, perm_simp, rule)
  apply(rule TrueI)
  apply(rule_tac y="x" in lam.exhaust)
  apply(auto)
  apply (erule_tac c="()" in Abs_lst1_fcb2)
  apply(simp_all add: fresh_def pure_supp eqvt_at_def fresh_star_def)
  done

termination
  by lexicographic_order
  
thm height.simps

  
section {* 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])"
  unfolding eqvt_def subst_graph_def
  apply (rule, perm_simp, rule)
  apply(rule TrueI)
  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_all add: fresh_star_def fresh_Pair_elim)
  apply (erule_tac c="(ya,sa)" in Abs_lst1_fcb2)
  apply(simp_all add: Abs_fresh_iff)
  apply(simp add: fresh_star_def fresh_Pair)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
done

termination
  by lexicographic_order

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"
  by (nominal_induct t avoiding: x s rule: lam.strong_induct)
     (auto simp add: lam.fresh fresh_at_base)

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

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
  by (nominal_induct t avoiding: z y s rule: lam.strong_induct)
      (auto simp add: lam.fresh fresh_at_base)

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

lemma height_ge_one:
  shows "1 \<le> (height e)"
by (induct e rule: lam.induct) (simp_all)

theorem height_subst:
  shows "height (e[x::=e']) \<le> ((height e) - 1) + (height e')"
proof (nominal_induct e avoiding: x e' rule: lam.strong_induct)
  case (Var y)
  have "1 \<le> height e'" by (rule height_ge_one)
  then show "height (Var y[x::=e']) \<le> height (Var y) - 1 + height e'" by simp
next
  case (Lam y e1)
  hence ih: "height (e1[x::=e']) \<le> ((height e1) - 1) + (height e')" by simp
  moreover
  have vc: "atom y\<sharp>x" "atom y\<sharp>e'" by fact+ (* usual variable convention *)
  ultimately show "height ((Lam [y]. e1)[x::=e']) \<le> height (Lam [y]. e1) - 1 + height e'" by simp
next
  case (App e1 e2)
  hence ih1: "height (e1[x::=e']) \<le> ((height e1) - 1) + (height e')"
    and ih2: "height (e2[x::=e']) \<le> ((height e2) - 1) + (height e')" by simp_all
  then show "height ((App e1 e2)[x::=e']) \<le> height (App e1 e2) - 1 + height e'"  by simp
qed

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 supp_lookup:
  shows "supp (lookup xs n x) \<subseteq> {atom x}"
  apply(induct arbitrary: n rule: lookup.induct)
  apply(simp add: ln.supp supp_at_base)
  apply(simp add: ln.supp pure_supp)
  done

lemma supp_lookup_in:
  shows "x \<in> set xs \<Longrightarrow> supp (lookup xs n x) = {}"
  by (induct arbitrary: n rule: lookup.induct)(auto simp add: ln.supp pure_supp)

lemma supp_lookup_notin:
  shows "x \<notin> set xs \<Longrightarrow> supp (lookup xs n x) = {atom x}"
  by (induct arbitrary: n rule: lookup.induct) (auto simp add: ln.supp pure_supp supp_at_base)

lemma supp_lookup_fresh:
  shows "atom ` set xs \<sharp>* lookup xs n x"
  by (case_tac "x \<in> set xs") (auto simp add: fresh_star_def fresh_def supp_lookup_in supp_lookup_notin)

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

text {* Function that translates lambda-terms into locally nameless terms *}

nominal_primrec (invariant "\<lambda>(_, xs) y. atom ` set xs \<sharp>* y")
  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))"
  apply (simp add: eqvt_def trans_graph_def)
  apply (rule, perm_simp, rule)
  apply (erule trans_graph.induct)
  apply (auto simp add: ln.fresh)[3]
  apply (simp add: supp_lookup_fresh)
  apply (simp add: fresh_star_def ln.fresh)
  apply (simp add: ln.fresh fresh_star_def)
  apply(auto)[1]
  apply (rule_tac y="a" and c="b" in lam.strong_exhaust)
  apply (auto simp add: fresh_star_def)[3]
  apply(simp_all)
  apply(erule conjE)+
  apply (erule_tac Abs_lst1_fcb2')
  apply (simp add: fresh_star_def)
  apply (simp add: fresh_star_def)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  done

termination
  by lexicographic_order

text {* count the bound-variable occurences in a lambda-term *}

nominal_primrec
  cbvs :: "lam \<Rightarrow> name list \<Rightarrow> nat"
where
  "cbvs (Var x) xs = (if x \<in> set xs then 1 else 0)"
| "cbvs (App t1 t2) xs = (cbvs t1 xs) + (cbvs t2 xs)"
| "atom x \<sharp> xs \<Longrightarrow> cbvs (Lam [x]. t) xs = cbvs t (x # xs)"
  apply(simp add: eqvt_def cbvs_graph_def)
  apply(rule, perm_simp, rule)
  apply(simp_all)
  apply(case_tac x)
  apply(rule_tac y="a" and c="b" in lam.strong_exhaust)
  apply(auto simp add: fresh_star_def)[3]
  apply(erule conjE)
  apply(erule Abs_lst1_fcb2')
  apply(simp add: pure_fresh fresh_star_def)
  apply(simp add: pure_fresh fresh_star_def)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  done

termination
  by lexicographic_order

section {* De Bruijn Terms *}

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

fun dbapp_in where
  "dbapp_in None _ = None"
| "dbapp_in (Some _ ) None = None"
| "dbapp_in (Some x) (Some y) = Some (DBApp x y)"

fun dblam_in where
  "dblam_in None = None"
| "dblam_in (Some x) = Some (DBLam x)"

lemma db_in_eqvt[eqvt]:
  "p \<bullet> (dbapp_in x y) = dbapp_in (p \<bullet> x) (p \<bullet> y)"
  "p \<bullet> (dblam_in x) = dblam_in (p \<bullet> x)"
  apply (case_tac [!] x)
  apply (simp_all add: eqvts)
  apply (case_tac y)
  apply (simp_all add: eqvts)
  done

instance db :: pure
  apply default
  apply (induct_tac x rule: db.induct)
  apply (simp_all add: permute_pure)
  done

lemma fresh_at_list: "atom x \<sharp> xs \<longleftrightarrow> x \<notin> set xs"
  unfolding fresh_def supp_set[symmetric]
  by (induct xs) (auto simp add: supp_of_finite_insert supp_at_base supp_set_empty)

fun
  vindex :: "name list \<Rightarrow> name \<Rightarrow> nat \<Rightarrow> db option" 
where
  "vindex [] v n = None"
| "vindex (h # t) v n = (if v = h then (Some (DBVar n)) else (vindex t v (Suc n)))"

lemma vindex_eqvt[eqvt]:
  "(p \<bullet> vindex l v n) = vindex (p \<bullet> l) (p \<bullet> v) (p \<bullet> n)"
  by (induct l arbitrary: n) (simp_all add: permute_pure)

nominal_primrec
  transdb :: "lam \<Rightarrow> name list \<Rightarrow> db option"
where
  "transdb (Var x) l = vindex l x 0"
| "transdb (App t1 t2) xs = dbapp_in (transdb t1 xs) (transdb t2 xs)"
| "x \<notin> set xs \<Longrightarrow> transdb (Lam [x].t) xs = dblam_in (transdb t (x # xs))"
  unfolding eqvt_def transdb_graph_def
  apply (rule, perm_simp, rule)
  apply(rule TrueI)
  apply (case_tac x)
  apply (rule_tac y="a" and c="b" in lam.strong_exhaust)
  apply (auto simp add: fresh_star_def fresh_at_list)[3]
  apply(simp_all)
  apply(erule conjE)
  apply (erule_tac c="xsa" in Abs_lst1_fcb2')
  apply (simp add: pure_fresh)
  apply(simp add: fresh_star_def fresh_at_list)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq db_in_eqvt)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq db_in_eqvt)
  done

termination
  by lexicographic_order

lemma transdb_eqvt[eqvt]:
  "p \<bullet> transdb t l = transdb (p \<bullet>t) (p \<bullet>l)"
  apply (nominal_induct t avoiding: l p rule: lam.strong_induct)
  apply (simp add: vindex_eqvt)
  apply (simp_all add: permute_pure)
  apply (simp add: fresh_at_list)
  apply (subst transdb.simps)
  apply (simp add: fresh_at_list[symmetric])
  apply (drule_tac x="name # l" in meta_spec)
  apply auto
  done

lemma db_trans_test:
  assumes a: "y \<noteq> x"
  shows "transdb (Lam [x]. Lam [y]. App (Var x) (Var y)) [] = 
  Some (DBLam (DBLam (DBApp (DBVar 1) (DBVar 0))))"
  using a by simp

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

lemma supp_subst:
  "supp (t[x ::= s]) \<subseteq> supp t \<union> supp s"
  by (induct t x s rule: subst.induct) (auto simp add: lam.supp)

lemma var_fresh_subst:
  "atom x \<sharp> s \<Longrightarrow> atom x \<sharp> (t[x ::= s])"
  by (induct t x s rule: subst.induct) (auto simp add: lam.supp lam.fresh fresh_at_base)

(* function that evaluates a lambda term *)
nominal_primrec
   eval :: "lam \<Rightarrow> lam" and
   apply_subst :: "lam \<Rightarrow> lam \<Rightarrow> lam"
where
  "eval (Var x) = Var x"
| "eval (Lam [x].t) = Lam [x].(eval t)"
| "eval (App t1 t2) = apply_subst (eval t1) (eval t2)"
| "apply_subst (Var x) t2 = App (Var x) t2"
| "apply_subst (App t0 t1) t2 = App (App t0 t1) t2"
| "atom x \<sharp> t2 \<Longrightarrow> apply_subst (Lam [x].t1) t2 = eval (t1[x::= t2])"
  apply(simp add: eval_apply_subst_graph_def eqvt_def)
  apply(rule, perm_simp, rule)
  apply(rule TrueI)
  apply (case_tac x)
  apply (case_tac a rule: lam.exhaust)
  apply simp_all[3]
  apply blast
  apply (case_tac b)
  apply (rule_tac y="a" and c="ba" in lam.strong_exhaust)
  apply simp_all[3]
  apply blast
  apply blast
  apply (simp add: Abs1_eq_iff fresh_star_def)
  apply(simp_all)
  apply(erule_tac c="()" in Abs_lst1_fcb2)
  apply (simp add: Abs_fresh_iff)
  apply(simp add: fresh_star_def fresh_Unit)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq)
  apply(erule conjE)
  apply(erule_tac c="t2a" in Abs_lst1_fcb2')
  apply (erule fresh_eqvt_at)
  apply (simp add: finite_supp)
  apply (simp add: fresh_Inl var_fresh_subst)
  apply(simp add: fresh_star_def)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq subst_eqvt)
  apply(simp add: eqvt_at_def atom_eqvt fresh_star_Pair perm_supp_eq subst_eqvt)
done


(* a small test
termination sorry

lemma 
  assumes "x \<noteq> y"
  shows "eval (App (Lam [x].App (Var x) (Var x)) (Var y)) = App (Var y) (Var y)"
using assms
apply(simp add: lam.supp fresh_def supp_at_base)
done
*)


text {* TODO: eqvt_at for the other side *}
nominal_primrec q where
  "atom c \<sharp> (x, M) \<Longrightarrow> q (Lam [x]. M) (N :: lam) = Lam [x]. (Lam [c]. (App M (q (Var c) N)))"
| "q (Var x) N = Var x"
| "q (App l r) N = App l r"
unfolding eqvt_def q_graph_def
apply (rule, perm_simp, rule)
apply (rule TrueI)
apply (case_tac x)
apply (rule_tac y="a" in lam.exhaust)
apply simp_all
apply blast
apply blast
apply (rule_tac x="(name, lam)" and ?'a="name" in obtain_fresh)
apply blast
apply clarify
apply (rule_tac x="(x, xa, M, Ma, c, ca, Na)" and ?'a="name" in obtain_fresh)
apply (subgoal_tac "eqvt_at q_sumC (Var ca, Na)") --"Could come from nominal_function?"
apply (subgoal_tac "Lam [c]. App M (q_sumC (Var c, Na)) = Lam [a]. App M (q_sumC (Var a, Na))")
apply (subgoal_tac "Lam [ca]. App Ma (q_sumC (Var ca, Na)) = Lam [a]. App Ma (q_sumC (Var a, Na))")
apply (simp only:)
apply (erule Abs_lst1_fcb)
oops

text {* Working Examples *}

nominal_primrec
  map_term :: "(lam \<Rightarrow> lam) \<Rightarrow> lam \<Rightarrow> lam"
where
  "eqvt f \<Longrightarrow> map_term f (Var x) = f (Var x)"
| "eqvt f \<Longrightarrow> map_term f (App t1 t2) = App (f t1) (f t2)"
| "eqvt f \<Longrightarrow> map_term f (Lam [x].t) = Lam [x].(f t)"
| "\<not>eqvt f \<Longrightarrow> map_term f t = t"
  apply (simp add: eqvt_def map_term_graph_def)
  apply (rule, perm_simp, rule)
  apply(rule TrueI)
  apply (case_tac x, case_tac "eqvt a", case_tac b rule: lam.exhaust)
  apply auto
  apply (erule Abs_lst1_fcb)
  apply (simp_all add: Abs_fresh_iff fresh_fun_eqvt_app)
  apply (simp add: eqvt_def permute_fun_app_eq)
  done

termination
  by lexicographic_order

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

nominal_primrec
  CPS :: "lam \<Rightarrow> (lam \<Rightarrow> lam) \<Rightarrow> lam"
where
  "CPS (Var x) k = Var x"
| "CPS (App M N) k = CPS M (\<lambda>m. CPS N (\<lambda>n. n))"
oops

consts b :: name
nominal_primrec
  Z :: "lam \<Rightarrow> (lam \<Rightarrow> lam) \<Rightarrow> lam"
where
  "Z (App M N) k = Z M (%m. (Z N (%n.(App m n))))"
| "Z (App M N) k = Z M (%m. (Z N (%n.(App (App m n) (Abs b (k (Var b)))))))"
unfolding eqvt_def Z_graph_def
apply (rule, perm_simp, rule)
oops

text {* tests of functions containing if and case *}

consts P :: "lam \<Rightarrow> bool"

nominal_primrec  
  A :: "lam => lam"
where  
  "A (App M N) = (if (True \<or> P M) then (A M) else (A N))"
| "A (Var x) = (Var x)" 
| "A (App M N) = (if True then M else A N)"
oops

nominal_primrec  
  C :: "lam => lam"
where  
  "C (App M N) = (case (True \<or> P M) of True \<Rightarrow> (A M) | False \<Rightarrow> (A N))"
| "C (Var x) = (Var x)" 
| "C (App M N) = (if True then M else C N)"
oops

nominal_primrec  
  A :: "lam => lam"
where  
  "A (Lam [x].M) = (Lam [x].M)"
| "A (Var x) = (Var x)"
| "A (App M N) = (if True then M else A N)"
oops

nominal_primrec  
  B :: "lam => lam"
where  
  "B (Lam [x].M) = (Lam [x].M)"
| "B (Var x) = (Var x)"
| "B (App M N) = (if True then M else (B N))"
unfolding eqvt_def
unfolding B_graph_def
apply(perm_simp)
apply(rule allI)
apply(rule refl)
oops


lemma test:
  assumes "t = s"
  and "supp p \<sharp>* t" "supp p \<sharp>* x"
  and "(p \<bullet> t) = s \<Longrightarrow> (p \<bullet> x) = y"
  shows "x = y"
using assms by (simp add: perm_supp_eq)

lemma test2:
  assumes "cs \<subseteq> as \<union> bs"
  and "as \<sharp>* x" "bs \<sharp>* x"
  shows "cs \<sharp>* x"
using assms
by (auto simp add: fresh_star_def) 

lemma test3:
  assumes "cs \<subseteq> as"
  and "as \<sharp>* x"
  shows "cs \<sharp>* x"
using assms
by (auto simp add: fresh_star_def) 



nominal_primrec  (invariant "\<lambda>(_, _, xs) y. atom ` fst ` set xs \<sharp>* y \<and> atom ` snd ` set xs \<sharp>* y")
  aux :: "lam \<Rightarrow> lam \<Rightarrow> (name \<times> name) list \<Rightarrow> bool"
where
  "aux (Var x) (Var y) xs = ((x, y) \<in> set xs)"
| "aux (App t1 t2) (App s1 s2) xs = (aux t1 s1 xs \<and> aux t2 s2 xs)"
| "aux (Var x) (App t1 t2) xs = False"
| "aux (Var x) (Lam [y].t) xs = False"
| "aux (App t1 t2) (Var x) xs = False"
| "aux (App t1 t2) (Lam [x].t) xs = False"
| "aux (Lam [x].t) (Var y) xs = False"
| "aux (Lam [x].t) (App t1 t2) xs = False"
| "\<lbrakk>{atom x} \<sharp>* (s, xs); {atom y} \<sharp>* (t, xs); x \<noteq> y\<rbrakk> \<Longrightarrow> 
       aux (Lam [x].t) (Lam [y].s) xs = aux t s ((x, y) # xs)"
  apply (simp add: eqvt_def aux_graph_def)
  apply (rule, perm_simp, rule)
  apply(erule aux_graph.induct)
  apply(simp_all add: fresh_star_def pure_fresh)[9]
  apply(case_tac x)
  apply(simp)
  apply(rule_tac y="a" and c="(b, c)" in lam.strong_exhaust)
  apply(simp)
  apply(rule_tac y="b" and c="c" in lam.strong_exhaust)
  apply(metis)+
  apply(simp)
  apply(rule_tac y="b" and c="c" in lam.strong_exhaust)
  apply(metis)+
  apply(simp)
  apply(rule_tac y="b" and c="(lam, c, name)" in lam.strong_exhaust)
  apply(metis)+
  apply(simp)
  apply(drule_tac x="name" in meta_spec)
  apply(drule_tac x="lama" in meta_spec)
  apply(drule_tac x="c" in meta_spec)
  apply(drule_tac x="namea" in meta_spec)
  apply(drule_tac x="lam" in meta_spec)
  apply(simp add: fresh_star_Pair)
  apply(simp add: fresh_star_def fresh_at_base lam.fresh)
  apply(auto)[1]
  apply(simp_all)[44]
  apply(simp del: Product_Type.prod.inject)  
  sorry

termination by lexicographic_order

end