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)

section {* free name function *}

text {* first returns an atom list *}

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 Abs_lst1_fcb)

apply(simp add: supp_removeAll fresh_def)

apply(drule supp_eqvt_at)

apply(simp add: finite_supp)

apply(auto simp add: fresh_def supp_removeAll eqvts eqvt_at_def)

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 Abs_lst1_fcb)

  apply(simp_all add: fresh_minus_atom_set)

  apply(erule fresh_eqvt_at)

  apply(simp_all add: finite_supp eqvt_at_def eqvts)

  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 {* A test with a locale and an interpretation. *}

text {* conclusion: it is no necessary *}

locale test =

   fixes f1::"name \<Rightarrow> ('a::pt)"

     and f2::"lam \<Rightarrow> lam \<Rightarrow> 'a \<Rightarrow> 'a \<Rightarrow> ('a::pt)"

     and f3::"name \<Rightarrow> lam \<Rightarrow> 'a \<Rightarrow> ('a::pt)"

   assumes fs: "finite (supp (f1, f2, f3))"

       and eq: "eqvt f1" "eqvt f2" "eqvt f3"

       and fcb: "\<forall>x t r. atom x \<sharp> f3 x t r"

begin

nominal_primrec

  f :: "lam \<Rightarrow> ('a::pt)"

where

  "f (Var x) = f1 x"

| "f (App t1 t2) = f2 t1 t2 (f t1) (f t2)"

| "f (Lam [x].t) = f3 x t (f t)"

  apply (simp add: eqvt_def f_graph_def)

  apply (perm_simp)

  apply(simp add: eq[simplified eqvt_def])

  apply(rule TrueI)

  apply(rule_tac y="x" in lam.exhaust)

  apply(auto simp add: fresh_star_def)

  apply(erule Abs_lst1_fcb)

  apply simp_all

  apply(simp add: fcb)

  apply (rule fresh_fun_eqvt_app3[OF eq(3)])

  apply (simp add: fresh_at_base)

  apply assumption

  apply (erule fresh_eqvt_at)

  apply (simp add: finite_supp)

  apply assumption

  apply (subgoal_tac "\<And>p y r. p \<bullet> (f3 x y r) = f3 (p \<bullet> x) (p \<bullet> y) (p \<bullet> r)")

  apply (simp add: eqvt_at_def)

  apply (simp add: permute_fun_app_eq eq[unfolded eqvt_def])

  done

termination

  by lexicographic_order

end

interpretation hei: test

  "%n. (1 :: nat)"

  "%t1 t2 r1 r2. (r1 + r2)"

  "%n t r. r + 1"

  apply default

  apply (auto simp add: pure_fresh supp_Pair)

  apply (simp_all add: fresh_def supp_def permute_fun_def permute_pure)[3]

  apply (simp_all add: eqvt_def permute_fun_def permute_pure)

  done

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"

  unfolding eqvt_def height_graph_def

  apply (rule, perm_simp, rule)

apply(rule TrueI)

apply(rule_tac y="x" in lam.exhaust)

apply(auto simp add: lam.distinct lam.eq_iff)

apply (erule Abs_lst1_fcb)

apply(simp_all add: fresh_def pure_supp eqvt_at_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 Abs_lst1_fcb)

apply(simp_all add: Abs_fresh_iff)

apply(drule_tac a="atom (xa)" in fresh_eqvt_at)

apply(simp_all add: finite_supp fresh_Pair)

apply(subgoal_tac "(atom x \<rightleftharpoons> atom xa) \<bullet> sa = sa")

apply(subgoal_tac "(atom x \<rightleftharpoons> atom xa) \<bullet> ya = ya")

apply(simp add: eqvt_at_def)

apply(simp_all add: swap_fresh_fresh)

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)

  apply (simp add: supp_lookup_fresh)

  apply (simp add: fresh_star_def ln.fresh)

  apply (simp add: ln.fresh fresh_star_def)

  apply (rule_tac y="a" and c="b" in lam.strong_exhaust)

  apply (auto simp add: fresh_star_def)[3]

  apply (erule Abs_lst1_fcb)

  apply (simp_all add: fresh_star_def)

  apply (drule supp_eqvt_at)

  apply (rule finite_supp)

  apply (auto simp add: supp_Pair fresh_def supp_Cons supp_at_base)[1]

  apply (simp add: eqvt_at_def swap_fresh_fresh)

  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)

  apply(erule Abs_lst1_fcb)

  apply(simp_all add: pure_fresh)

  apply (simp add: eqvt_at_def swap_fresh_fresh)

  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)

  apply (rule_tac f="dblam_in" in arg_cong)

  apply (erule Abs_lst1_fcb)

  apply (simp_all add: pure_fresh)

  apply (subgoal_tac "(atom x \<rightleftharpoons> atom xa) \<bullet> xsa = xsa")

  apply (simp add: eqvt_at_def)

  apply (metis atom_name_def swap_fresh_fresh fresh_at_list)

  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