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)
lemma cheat: "P" sorry
thm lam.strong_exhaust
lemma lam_strong_exhaust2:
"\<lbrakk>\<And>name. y = Var name \<Longrightarrow> P;
\<And>lam1 lam2. y = App lam1 lam2 \<Longrightarrow> P;
\<And>name lam. \<lbrakk>{atom name} \<sharp>* c; y = Lam [name]. lam\<rbrakk> \<Longrightarrow> P;
finite (supp c)\<rbrakk>
\<Longrightarrow> P"
sorry
abbreviation
"FCB f \<equiv> \<forall>x t r. atom x \<sharp> f x t r"
lemma Abs1_eq_fdest:
fixes x y :: "'a :: at_base"
and S T :: "'b :: fs"
assumes "(Abs_lst [atom x] T) = (Abs_lst [atom y] S)"
and "x \<noteq> y \<Longrightarrow> atom y \<sharp> T \<Longrightarrow> atom x \<sharp> f x T"
and "x \<noteq> y \<Longrightarrow> atom y \<sharp> T \<Longrightarrow> atom y \<sharp> f x T"
and "x \<noteq> y \<Longrightarrow> atom y \<sharp> T \<Longrightarrow> (atom x \<rightleftharpoons> atom y) \<bullet> T = S \<Longrightarrow> (atom x \<rightleftharpoons> atom y) \<bullet> (f x T) = f y S"
and "sort_of (atom x) = sort_of (atom y)"
shows "f x T = f y S"
using assms apply -
thm Abs1_eq_iff'
apply (subst (asm) Abs1_eq_iff')
apply simp_all
apply (elim conjE disjE)
apply simp
apply(rule trans)
apply (rule_tac p="(atom x \<rightleftharpoons> atom y)" in supp_perm_eq[symmetric])
apply(rule fresh_star_supp_conv)
apply(simp add: supp_swap fresh_star_def)
apply(simp add: swap_commute)
done
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(simp)
apply(simp)
apply(simp)
apply(rule_tac y="x" in lam.exhaust)
apply(auto)[6]
apply(simp)
apply(simp)
apply(simp)
apply (erule Abs1_eq_fdest)
apply(simp add: fresh_def)
apply(subst supp_of_finite_sets)
apply(simp)
apply(simp add: supp_atom)
apply(simp add: fresh_def)
apply(subst supp_of_finite_sets)
apply(simp)
apply(simp add: supp_atom)
apply(subst supp_finite_atom_set[symmetric])
apply(simp)
apply(simp add: fresh_def[symmetric])
apply(rule fresh_eqvt_at)
apply(assumption)
apply(simp add: finite_supp)
apply(simp)
apply(simp add: eqvt_at_def eqvts)
apply(simp)
done
termination
by (relation "measure size") (auto simp add: lam.size)
thm frees_set.simps
thm frees_set.induct
lemma "frees_set t = supp t"
apply(induct rule: frees_set.induct)
apply(simp_all add: lam.supp supp_at_base)
done
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)
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 Abs1_eq_fdest)
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 (relation "measure size") (auto simp add: lam.size)
thm f.simps
end
thm test.f.simps
thm test.f.simps[simplified test_def]
thm test_def
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
thm hei.f.simps
inductive
triv :: "lam \<Rightarrow> nat \<Rightarrow> bool"
where
Var: "triv (Var x) n"
| App: "\<lbrakk>triv t1 n; triv t2 n\<rbrakk> \<Longrightarrow> triv (App t1 t2) n"
lemma
"p \<bullet> (triv t x) = triv (p \<bullet> t) (p \<bullet> x)"
unfolding triv_def
apply(perm_simp)
apply(rule refl)
oops
(*apply(perm_simp)*)
ML {*
Inductive.the_inductive @{context} "Lambda.triv"
*}
thm triv_def
equivariance triv
nominal_inductive triv avoids Var: "{}::name set"
apply(auto simp add: fresh_star_def)
done
inductive
triv2 :: "lam \<Rightarrow> nat \<Rightarrow> bool"
where
Var1: "triv2 (Var x) 0"
| Var2: "triv2 (Var x) (n + n)"
| Var3: "triv2 (Var x) n"
equivariance triv2
nominal_inductive triv2 .
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"
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 Abs1_eq_fdest)
apply(simp_all add: fresh_def pure_supp eqvt_at_def)
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)"
unfolding eqvt_def frees_lst_graph_def
apply (rule, perm_simp, rule)
apply(rule TrueI)
apply(rule_tac y="x" in lam.exhaust)
apply(auto)
apply (erule Abs1_eq_fdest)
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 (relation "measure size") (simp_all add: lam.size)
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])"
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 Abs1_eq_fdest)
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(rule perm_supp_eq,simp add: fresh_star_def fresh_Pair supp_swap)+
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
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 [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)
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(simp)
apply (case_tac "xa \<in> set xs")
apply (simp add: fresh_star_def fresh_def supp_lookup_in)
apply (simp add: fresh_star_def fresh_def supp_lookup_notin)
apply blast
apply (simp add: fresh_star_def ln.fresh)
apply(simp)
apply (simp add: ln.fresh fresh_star_def)
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)
apply(elim conjE)
apply clarify
apply (erule Abs1_eq_fdest)
apply (simp_all add: ln.fresh)
prefer 2
apply(drule supp_eqvt_at)
apply (auto simp add: finite_supp supp_Pair fresh_def supp_Cons supp_at_base)[2]
prefer 2
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)
apply(simp add: fresh_star_def)
done
termination
by (relation "measure (size o fst)") (simp_all add: lam.size)
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 Abs1_eq_fdest)
apply(simp_all add: pure_fresh)
apply (simp add: eqvt_at_def swap_fresh_fresh)
done
termination
by (relation "measure (size o fst)") (simp_all add: lam.size)
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]
apply (induct xs)
apply (simp add: supp_set_empty)
apply simp
apply auto
apply (simp_all add: insert_absorb UnI2 finite_set supp_of_finite_insert supp_at_base)
done
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 Abs1_eq_fdest)
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 (relation "measure (\<lambda>(t,_). size t)") (simp_all add: lam.size)
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 "trans (Lam [x]. Lam [y]. App (Var x) (Var y)) [] 0 = 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
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
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 Abs1_eq_fdest)
apply (simp_all add: Abs_fresh_iff fresh_fun_eqvt_app)
apply (simp add: eqvt_def permute_fun_app_eq)
done
termination
by (relation "measure (\<lambda>(_,t). size t)") (simp_all add: lam.size)
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
text {* "HO" functions *}
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
(* Problem: nominal_primrec generates non-quantified free variable "x" *)
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
(* function tests *)
(* similar problem with function package *)
function
f :: "int list \<Rightarrow> int"
where
"f [] = 0"
| "f [e] = e"
| "f (l @ m) = f l + f m"
apply(simp_all)
oops
end