theory Lambda

imports 

  "../Nominal2"

  "~~/src/HOL/Library/Monad_Syntax"

begin

lemma perm_commute: 

  "a \<sharp> p \<Longrightarrow> a' \<sharp> p \<Longrightarrow> (a \<rightleftharpoons> a') + p = p + (a \<rightleftharpoons> a')"

apply(rule plus_perm_eq)

apply(simp add: supp_swap fresh_def)

done

atom_decl name

thm obtain_atom

ML {* trace := true *}

nominal_datatype lam =

  Var "name"

| App "lam" "lam"

| Lam x::"name" l::"lam"  binds x in l ("Lam [_]. _" [100, 100] 100)

nominal_datatype environment = 

   Ni

 | En name closure environment

and closure = 

   Clos "lam" "environment"

thm environment_closure.exhaust(1)

nominal_function 

  env_lookup :: "environment => name => closure"

where

  "env_lookup Ni x = Clos (Var x) Ni"

| "env_lookup (En v clos rest) x = (if (v = x) then clos else env_lookup rest x)"

   apply (auto)

   apply (simp add: env_lookup_graph_aux_def eqvt_def)

   by (metis environment_closure.strong_exhaust(1))

lemma 

  "Lam [x]. Var x = Lam [y]. Var y"

proof -

  obtain c::name where fresh: "atom c \<sharp> (Lam [x]. Var x, Lam [y]. Var y)"

    by (metis obtain_fresh)

  have "Lam [x]. Var x = (c \<leftrightarrow> x) \<bullet> Lam [x]. Var x"

    using fresh by (rule_tac flip_fresh_fresh[symmetric]) (simp_all add: fresh_Pair)

  also have "... = Lam [c].Var c" by simp

  also have "... = (c \<leftrightarrow> y) \<bullet> Lam [c]. Var c"

    using fresh by (rule_tac flip_fresh_fresh[symmetric]) (auto simp add: fresh_Pair)

  also have "... = Lam [y]. Var y" by simp

  finally show "Lam [x]. Var x = Lam [y]. Var y" .

qed

definition 

  Name :: "nat \<Rightarrow> name" 

where 

  "Name n = Abs_name (Atom (Sort ''name'' []) n)"

definition

   "Ident2 = Lam [Name 1].(Var (Name 1))"

definition 

   "Ident x = Lam [x].(Var x)"

lemma "Ident2 = Ident x"

unfolding Ident_def Ident2_def

by simp

lemma "Ident x = Ident y"

unfolding Ident_def

by simp

section {* Simple examples from Norrish 2004 *}

nominal_function 

  is_app :: "lam \<Rightarrow> bool"

where

  "is_app (Var x) = False"

| "is_app (App t1 t2) = True"

| "is_app (Lam [x]. t) = False"

thm is_app_graph_def is_app_graph_aux_def

apply(simp add: eqvt_def is_app_graph_aux_def)

apply(rule TrueI)

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

apply(auto)[3]

apply(all_trivials)

done

nominal_termination (eqvt) by lexicographic_order

thm is_app_def

thm is_app.eqvt

thm eqvts

nominal_function 

  rator :: "lam \<Rightarrow> lam option"

where

  "rator (Var x) = None"

| "rator (App t1 t2) = Some t1"

| "rator (Lam [x]. t) = None"

apply(simp add: eqvt_def rator_graph_aux_def)

apply(rule TrueI)

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

apply(auto)[3]

apply(simp_all)

done

nominal_termination (eqvt) by lexicographic_order

nominal_function 

  rand :: "lam \<Rightarrow> lam option"

where

  "rand (Var x) = None"

| "rand (App t1 t2) = Some t2"

| "rand (Lam [x]. t) = None"

apply(simp add: eqvt_def rand_graph_aux_def)

apply(rule TrueI)

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

apply(auto)[3]

apply(simp_all)

done

nominal_termination (eqvt) by lexicographic_order

nominal_function 

  is_eta_nf :: "lam \<Rightarrow> bool"

where

  "is_eta_nf (Var x) = True"

| "is_eta_nf (App t1 t2) = (is_eta_nf t1 \<and> is_eta_nf t2)"

| "is_eta_nf (Lam [x]. t) = (is_eta_nf t \<and> 

                             ((is_app t \<and> rand t = Some (Var x)) \<longrightarrow> atom x \<in> supp (rator t)))"

apply(simp add: eqvt_def is_eta_nf_graph_aux_def)

apply(rule TrueI)

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

apply(auto)[3]

using [[simproc del: alpha_lst]]

apply(simp_all)

apply(erule_tac c="()" in Abs_lst1_fcb2')

apply(simp_all add: pure_fresh fresh_star_def)[3]

apply(simp add: eqvt_at_def conj_eqvt)

apply(simp add: eqvt_at_def conj_eqvt)

done

nominal_termination (eqvt) by lexicographic_order

nominal_datatype path = Left | Right | In

section {* Paths to a free variables *} 

instance path :: pure

apply(induct_tac "x::path" rule: path.induct)

apply(simp_all)

done

nominal_function 

  var_pos :: "name \<Rightarrow> lam \<Rightarrow> (path list) set"

where

  "var_pos y (Var x) = (if y = x then {[]} else {})"

| "var_pos y (App t1 t2) = (Cons Left ` (var_pos y t1)) \<union> (Cons Right ` (var_pos y t2))"

| "atom x \<sharp> y \<Longrightarrow> var_pos y (Lam [x]. t) = (Cons In ` (var_pos y t))"

apply(simp add: eqvt_def var_pos_graph_aux_def)

apply(rule TrueI)

apply(case_tac x)

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

apply(auto simp add: fresh_star_def)[3]

using [[simproc del: alpha_lst]]

apply(simp_all)

apply(erule conjE)+

apply(erule_tac Abs_lst1_fcb2)

apply(simp add: pure_fresh)

apply(simp add: fresh_star_def)

apply(simp only: eqvt_at_def)

apply(perm_simp)

apply(simp)

apply(simp add: perm_supp_eq)

apply(simp only: eqvt_at_def)

apply(perm_simp)

apply(simp)

apply(simp add: perm_supp_eq)

done

nominal_termination (eqvt) by lexicographic_order

lemma var_pos1:

  assumes "atom y \<notin> supp t"

  shows "var_pos y t = {}"

using assms

apply(induct t rule: var_pos.induct)

apply(simp_all add: lam.supp supp_at_base fresh_at_base)

done

lemma var_pos2:

  shows "var_pos y (Lam [y].t) = {}"

apply(rule var_pos1)

apply(simp add: lam.supp)

done

text {* strange substitution operation *}

nominal_function

  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 ::== (App (Var y) s)])"

  apply(simp add: eqvt_def subst'_graph_aux_def)

  apply(rule TrueI)

  apply(case_tac x)

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

  apply(auto simp add: fresh_star_def)[3]

  using [[simproc del: alpha_lst]]

  apply(simp_all)

  apply(erule conjE)+

  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 only: eqvt_at_def)

  apply(perm_simp)

  apply(simp)

  apply(simp add: fresh_star_Pair perm_supp_eq)

  apply(simp only: eqvt_at_def)

  apply(perm_simp)

  apply(simp)

  apply(simp add: fresh_star_Pair perm_supp_eq)

done

nominal_termination (eqvt) by lexicographic_order

section {* free name function *}

lemma fresh_removeAll_name:

  fixes x::"name"

    and xs:: "name list"

  shows "atom x \<sharp> (removeAll y xs) \<longleftrightarrow> (atom x \<sharp> xs \<or> x = y)"

  apply (induct xs)

  apply(auto simp add: fresh_def supp_Nil supp_Cons supp_at_base)

  done

text {* first returns an atom list *}

nominal_function 

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

apply(simp add: eqvt_def frees_lst_graph_aux_def)

apply(rule TrueI)

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

using [[simproc del: alpha_lst]]

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

nominal_termination (eqvt) 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_function (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_aux_def)

  apply(erule frees_set_graph.induct)

  apply(auto)[9]

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

  apply(auto)[3]

  using [[simproc del: alpha_lst]]

  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)

  apply(simp add: Diff_eqvt eqvt_at_def)

  done

nominal_termination (eqvt) 

  by lexicographic_order

lemma "frees_set t = supp t"

  by (induct rule: frees_set.induct) (simp_all add: lam.supp supp_at_base)

section {* height function *}

nominal_function

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

  apply(rule TrueI)

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

  using [[simproc del: alpha_lst]]

  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

nominal_termination (eqvt)

  by lexicographic_order

thm height.simps

section {* capture-avoiding substitution *}

nominal_function

  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])"

  apply(simp add: eqvt_def subst_graph_aux_def)

  apply(rule TrueI)

  using [[simproc del: alpha_lst]]

  apply(auto)

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

  apply(blast)+

  using [[simproc del: alpha_lst]]

  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 only: eqvt_at_def)

  apply(perm_simp)

  apply(simp)

  apply(simp add: fresh_star_Pair perm_supp_eq)

  apply(simp only: eqvt_at_def)

  apply(perm_simp)

  apply(simp)

  apply(simp add: fresh_star_Pair perm_supp_eq)

done

nominal_termination (eqvt)

  by lexicographic_order

thm subst.eqvt

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: fresh_at_base)

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)

  using [[simproc del: alpha_lst]]

  apply(auto simp add:  flip_fresh_fresh fresh_Pair fresh_at_base)

  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

  by (nominal_induct t avoiding: z y s rule: lam.strong_induct)

      (auto simp add:  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:  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  fresh_fact)

thm beta.strong_induct

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  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: 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