Which proofs need a 'sorry'.
theory Test
imports "Parser" "../Attic/Prove"
begin
text {* example 1, equivalent to example 2 from Terms *}
atom_decl name
(* maybe should be added to Infinite.thy *)
lemma infinite_Un:
shows "infinite (S \<union> T) \<longleftrightarrow> infinite S \<or> infinite T"
by simp
ML {* val _ = cheat_alpha_eqvt := false *}
ML {* val _ = cheat_fv_eqvt := false *}
ML {* val _ = recursive := false *}
nominal_datatype lm =
Vr "name"
| Ap "lm" "lm"
| Lm x::"name" l::"lm" bind x in l
lemma finite_fv:
shows "finite (fv_lm t)"
apply(induct t rule: lm_induct)
apply(simp_all add: lm_fv)
done
lemma supp_fn:
shows "supp t = fv_lm t"
apply(induct t rule: lm_induct)
apply(simp_all add: lm_fv)
apply(simp only: supp_def)
apply(simp only: lm_perm)
apply(simp only: lm_eq_iff)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
apply(simp (no_asm) only: supp_def)
apply(simp only: lm_perm)
apply(simp only: lm_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
apply(simp only: supp_def[symmetric])
apply(rule_tac t="supp (Lm name lm)" and s="supp (Abs {atom name} lm)" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: lm_perm)
apply(simp only: permute_ABS)
apply(simp only: lm_eq_iff)
apply(simp only: Abs_eq_iff)
apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(simp only: supp_Abs)
done
lemmas supp_fn' = lm_fv[simplified supp_fn[symmetric]]
lemma
fixes c::"'a::fs"
assumes a1: "\<And>name c. P c (Vr name)"
and a2: "\<And>lm1 lm2 c. \<lbrakk>\<And>d. P d lm1; \<And>d. P d lm2\<rbrakk> \<Longrightarrow> P c (Ap lm1 lm2)"
and a3: "\<And>name lm c. \<lbrakk>\<And>d. P d lm\<rbrakk> \<Longrightarrow> P c (Lm name lm)"
shows "P c lm"
proof -
have "\<And>p. P c (p \<bullet> lm)"
apply(induct lm arbitrary: c rule: lm_induct)
apply(simp only: lm_perm)
apply(rule a1)
apply(simp only: lm_perm)
apply(rule a2)
apply(blast)[1]
apply(assumption)
apply(subgoal_tac "\<exists>new::name. (atom new) \<sharp> (c, Lm (p \<bullet> name) (p \<bullet> lm))")
apply(erule exE)
apply(rule_tac t="p \<bullet> Lm name lm" and
s="(((p \<bullet> name) \<leftrightarrow> new) + p) \<bullet> Lm name lm" in subst)
apply(simp)
apply(subst lm_perm)
apply(subst (2) lm_perm)
apply(rule flip_fresh_fresh)
apply(simp add: fresh_def)
apply(simp only: supp_fn')
apply(simp)
apply(simp add: fresh_Pair)
apply(simp add: lm_perm)
apply(rule a3)
apply(drule_tac x="((p \<bullet> name) \<leftrightarrow> new) + p" in meta_spec)
apply(simp)
apply(simp add: fresh_def)
apply(rule_tac X="supp (c, Lm (p \<bullet> name) (p \<bullet> lm))" in obtain_at_base)
apply(simp add: supp_Pair finite_supp)
apply(blast)
done
then have "P c (0 \<bullet> lm)" by blast
then show "P c lm" by simp
qed
nominal_datatype lam =
VAR "name"
| APP "lam" "lam"
| LAM x::"name" t::"lam" bind x in t
| LET bp::"bp" t::"lam" bind "bi bp" in t
and bp =
BP "name" "lam"
binder
bi::"bp \<Rightarrow> atom set"
where
"bi (BP x t) = {atom x}"
thm lam_bp_fv
thm lam_bp_eq_iff
thm lam_bp_bn
thm lam_bp_perm
thm lam_bp_induct
thm lam_bp_inducts
thm lam_bp_distinct
ML {* Sign.of_sort @{theory} (@{typ lam}, @{sort fs}) *}
term "supp (x :: lam)"
lemma bi_eqvt:
shows "(p \<bullet> (bi b)) = bi (p \<bullet> b)"
by (rule eqvts)
lemma supp_fv:
shows "supp t = fv_lam t"
and "supp bp = fv_bp bp \<and> fv_bi bp = {a. infinite {b. \<not>alpha_bi ((a \<rightleftharpoons> b) \<bullet> bp) bp}}"
apply(induct t and bp rule: lam_bp_inducts)
apply(simp_all add: lam_bp_fv)
(* VAR case *)
apply(simp only: supp_def)
apply(simp only: lam_bp_perm)
apply(simp only: lam_bp_eq_iff)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
(* APP case *)
apply(simp only: supp_def)
apply(simp only: lam_bp_perm)
apply(simp only: lam_bp_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
(* LAM case *)
apply(rule_tac t="supp (LAM name lam)" and s="supp (Abs {atom name} lam)" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: lam_bp_perm)
apply(simp only: permute_ABS)
apply(simp only: lam_bp_eq_iff)
apply(simp only: Abs_eq_iff)
apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(simp only: supp_Abs)
(* LET case *)
apply(rule_tac t="supp (LET bp lam)" and s="supp (Abs (bi bp) lam) \<union> fv_bi bp" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: lam_bp_perm)
apply(simp only: permute_ABS)
apply(simp only: lam_bp_eq_iff)
apply(simp only: eqvts)
apply(simp only: Abs_eq_iff)
apply(simp only: ex_simps)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(blast)
apply(simp add: supp_Abs)
apply(blast)
(* BP case *)
apply(simp only: supp_def)
apply(simp only: lam_bp_perm)
apply(simp only: lam_bp_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
apply(simp)
done
thm lam_bp_fv[simplified supp_fv(1)[symmetric] supp_fv(2)[THEN conjunct1, symmetric]]
ML {* val _ = recursive := true *}
nominal_datatype lam' =
VAR' "name"
| APP' "lam'" "lam'"
| LAM' x::"name" t::"lam'" bind x in t
| LET' bp::"bp'" t::"lam'" bind "bi' bp" in t
and bp' =
BP' "name" "lam'"
binder
bi'::"bp' \<Rightarrow> atom set"
where
"bi' (BP' x t) = {atom x}"
thm lam'_bp'_fv
thm lam'_bp'_eq_iff[no_vars]
thm lam'_bp'_bn
thm lam'_bp'_perm
thm lam'_bp'_induct
thm lam'_bp'_inducts
thm lam'_bp'_distinct
ML {* Sign.of_sort @{theory} (@{typ lam'}, @{sort fs}) *}
lemma supp_fv':
shows "supp t = fv_lam' t"
and "supp bp = fv_bp' bp"
apply(induct t and bp rule: lam'_bp'_inducts)
apply(simp_all add: lam'_bp'_fv)
(* VAR case *)
apply(simp only: supp_def)
apply(simp only: lam'_bp'_perm)
apply(simp only: lam'_bp'_eq_iff)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
(* APP case *)
apply(simp only: supp_def)
apply(simp only: lam'_bp'_perm)
apply(simp only: lam'_bp'_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
(* LAM case *)
apply(rule_tac t="supp (LAM' name lam')" and s="supp (Abs {atom name} lam')" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: lam'_bp'_perm)
apply(simp only: permute_ABS)
apply(simp only: lam'_bp'_eq_iff)
apply(simp only: Abs_eq_iff)
apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(simp only: supp_Abs)
(* LET case *)
apply(rule_tac t="supp (LET' bp' lam')" and
s="supp (Abs (bi' bp') (bp', lam'))" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: lam'_bp'_perm)
apply(simp only: permute_ABS)
apply(simp only: lam'_bp'_eq_iff)
apply(simp only: Abs_eq_iff)
apply(simp only: alpha_gen)
apply(simp only: eqvts split_def fst_conv snd_conv)
apply(simp only: eqvts[symmetric] supp_Pair)
apply(simp only: eqvts Pair_eq)
apply(simp add: supp_Abs supp_Pair)
apply blast
apply(simp only: supp_def)
apply(simp only: lam'_bp'_perm)
apply(simp only: lam'_bp'_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base supp_atom)
apply simp
done
thm lam'_bp'_fv[simplified supp_fv'[symmetric]]
text {* example 2 *}
ML {* val _ = recursive := false *}
nominal_datatype trm' =
Var "name"
| App "trm'" "trm'"
| Lam x::"name" t::"trm'" bind x in t
| Let p::"pat'" "trm'" t::"trm'" bind "f p" in t
and pat' =
PN
| PS "name"
| PD "name" "name"
binder
f::"pat' \<Rightarrow> atom set"
where
"f PN = {}"
| "f (PD x y) = {atom x, atom y}"
| "f (PS x) = {atom x}"
thm trm'_pat'_fv
thm trm'_pat'_eq_iff
thm trm'_pat'_bn
thm trm'_pat'_perm
thm trm'_pat'_induct
thm trm'_pat'_distinct
lemma supp_fv_trm'_pat':
shows "supp t = fv_trm' t"
and "supp bp = fv_pat' bp \<and> {a. infinite {b. \<not>alpha_f ((a \<rightleftharpoons> b) \<bullet> bp) bp}} = fv_f bp"
apply(induct t and bp rule: trm'_pat'_inducts)
apply(simp_all add: trm'_pat'_fv)
(* VAR case *)
apply(simp only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: trm'_pat'_eq_iff)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
(* APP case *)
apply(simp only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: trm'_pat'_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
(* LAM case *)
apply(rule_tac t="supp (Lam name trm')" and s="supp (Abs {atom name} trm')" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: permute_ABS)
apply(simp only: trm'_pat'_eq_iff)
apply(simp only: Abs_eq_iff)
apply(simp only: insert_eqvt atom_eqvt empty_eqvt)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(simp only: supp_Abs)
(* LET case *)
apply(rule_tac t="supp (Let pat' trm'1 trm'2)"
and s="supp (Abs (f pat') trm'2) \<union> supp trm'1 \<union> fv_f pat'" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: permute_ABS)
apply(simp only: trm'_pat'_eq_iff)
apply(simp only: eqvts)
apply(simp only: Abs_eq_iff)
apply(simp only: ex_simps)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(blast)
apply(simp add: supp_Abs)
apply(blast)
(* PN case *)
apply(simp only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: trm'_pat'_eq_iff)
apply(simp)
(* PS case *)
apply(simp only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: trm'_pat'_eq_iff)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
apply(simp)
(* PD case *)
apply(simp only: supp_def)
apply(simp only: trm'_pat'_perm)
apply(simp only: trm'_pat'_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
apply(simp only: supp_def[symmetric])
apply(simp add: supp_at_base)
done
thm trm'_pat'_fv[simplified supp_fv_trm'_pat'(1)[symmetric] supp_fv_trm'_pat'(2)[THEN conjunct1, symmetric]]
nominal_datatype trm0 =
Var0 "name"
| App0 "trm0" "trm0"
| Lam0 x::"name" t::"trm0" bind x in t
| Let0 p::"pat0" "trm0" t::"trm0" bind "f0 p" in t
and pat0 =
PN0
| PS0 "name"
| PD0 "pat0" "pat0"
binder
f0::"pat0 \<Rightarrow> atom set"
where
"f0 PN0 = {}"
| "f0 (PS0 x) = {atom x}"
| "f0 (PD0 p1 p2) = (f0 p1) \<union> (f0 p2)"
thm trm0_pat0_fv
thm trm0_pat0_eq_iff
thm trm0_pat0_bn
thm trm0_pat0_perm
thm trm0_pat0_induct
thm trm0_pat0_distinct
text {* example type schemes *}
nominal_datatype t =
VarTS "name"
| FunTS "t" "t"
and tyS =
All xs::"name set" ty::"t" bind xs in ty
thm t_tyS_fv
thm t_tyS_eq_iff
thm t_tyS_bn
thm t_tyS_perm
thm t_tyS_induct
thm t_tyS_distinct
ML {* Sign.of_sort @{theory} (@{typ t}, @{sort fs}) *}
ML {* Sign.of_sort @{theory} (@{typ tyS}, @{sort fs}) *}
lemma supports_subset:
fixes S1 S2 :: "atom set"
assumes a: "S1 supports x"
and b: "S1 \<subseteq> S2"
shows "S2 supports x"
using a b
by (auto simp add: supports_def)
lemma finite_fv_t_tyS:
fixes T::"t"
and S::"tyS"
shows "finite (fv_t T)"
and "finite (fv_tyS S)"
apply(induct T and S rule: t_tyS_inducts)
apply(simp_all add: t_tyS_fv)
done
lemma supp_fv_t_tyS:
shows "supp T = fv_t T"
and "supp S = fv_tyS S"
apply(induct T and S rule: t_tyS_inducts)
apply(simp_all add: t_tyS_fv)
(* VarTS case *)
apply(simp only: supp_def)
apply(simp only: t_tyS_perm)
apply(simp only: t_tyS_eq_iff)
apply(simp only: supp_def[symmetric])
apply(simp only: supp_at_base)
(* FunTS case *)
apply(simp only: supp_def)
apply(simp only: t_tyS_perm)
apply(simp only: t_tyS_eq_iff)
apply(simp only: de_Morgan_conj)
apply(simp only: Collect_disj_eq)
apply(simp only: infinite_Un)
apply(simp only: Collect_disj_eq)
(* All case *)
apply(rule_tac t="supp (All fun t)" and s="supp (Abs (atom ` fun) t)" in subst)
apply(simp (no_asm) only: supp_def)
apply(simp only: t_tyS_perm)
apply(simp only: permute_ABS)
apply(simp only: t_tyS_eq_iff)
apply(simp only: Abs_eq_iff)
apply(simp only: insert_eqvt atom_eqvt empty_eqvt image_eqvt atom_eqvt_raw)
apply(simp only: alpha_gen)
apply(simp only: supp_eqvt[symmetric])
apply(simp only: eqvts)
apply(rule trans)
apply(rule finite_supp_Abs)
apply(simp add: finite_fv_t_tyS)
apply(simp)
done
(* example 1 from Terms.thy *)
nominal_datatype trm1 =
Vr1 "name"
| Ap1 "trm1" "trm1"
| Lm1 x::"name" t::"trm1" bind x in t
| Lt1 p::"bp1" "trm1" t::"trm1" bind "bv1 p" in t
and bp1 =
BUnit1
| BV1 "name"
| BP1 "bp1" "bp1"
binder
bv1
where
"bv1 (BUnit1) = {}"
| "bv1 (BP1 bp1 bp2) = (bv1 bp1) \<union> (bv1 bp2)"
| "bv1 (BV1 x) = {atom x}"
thm trm1_bp1_fv
thm trm1_bp1_eq_iff
thm trm1_bp1_bn
thm trm1_bp1_perm
thm trm1_bp1_induct
thm trm1_bp1_distinct
text {* example 3 from Terms.thy *}
nominal_datatype trm3 =
Vr3 "name"
| Ap3 "trm3" "trm3"
| Lm3 x::"name" t::"trm3" bind x in t
| Lt3 r::"rassigns3" t::"trm3" bind "bv3 r" in t
and rassigns3 =
ANil
| ACons "name" "trm3" "rassigns3"
binder
bv3
where
"bv3 ANil = {}"
| "bv3 (ACons x t as) = {atom x} \<union> (bv3 as)"
thm trm3_rassigns3_fv
thm trm3_rassigns3_eq_iff
thm trm3_rassigns3_bn
thm trm3_rassigns3_perm
thm trm3_rassigns3_induct
thm trm3_rassigns3_distinct
(* compat should be
compat (ANil) pi (PNil) \<equiv> TRue
compat (ACons x t ts) pi (ACons x' t' ts') \<equiv> pi o x = x' \<and> alpha t t' \<and> compat ts pi ts'
*)
(* example 5 from Terms.thy *)
nominal_datatype trm5 =
Vr5 "name"
| Ap5 "trm5" "trm5"
| Lt5 l::"lts" t::"trm5" bind "bv5 l" in t
and lts =
Lnil
| Lcons "name" "trm5" "lts"
binder
bv5
where
"bv5 Lnil = {}"
| "bv5 (Lcons n t ltl) = {atom n} \<union> (bv5 ltl)"
thm trm5_lts_fv
thm trm5_lts_eq_iff
thm trm5_lts_bn
thm trm5_lts_perm
thm trm5_lts_induct
thm trm5_lts_distinct
(* example from my PHD *)
atom_decl coname
nominal_datatype phd =
Ax "name" "coname"
| Cut n::"coname" t1::"phd" c::"coname" t2::"phd" bind n in t1, bind c in t2
| AndR c1::"coname" t1::"phd" c2::"coname" t2::"phd" "coname" bind c1 in t1, bind c2 in t2
| AndL1 n::"name" t::"phd" "name" bind n in t
| AndL2 n::"name" t::"phd" "name" bind n in t
| ImpL c::"coname" t1::"phd" n::"name" t2::"phd" "name" bind c in t1, bind n in t2
| ImpR c::"coname" n::"name" t::"phd" "coname" bind n in t, bind c in t
thm phd_fv
thm phd_eq_iff
thm phd_bn
thm phd_perm
thm phd_induct
thm phd_distinct
(* example form Leroy 96 about modules; OTT *)
nominal_datatype mexp =
Acc "path"
| Stru "body"
| Funct x::"name" "sexp" m::"mexp" bind x in m
| FApp "mexp" "path"
| Ascr "mexp" "sexp"
and body =
Empty
| Seq c::defn d::"body" bind "cbinders c" in d
and defn =
Type "name" "tyty"
| Dty "name"
| DStru "name" "mexp"
| Val "name" "trmtrm"
and sexp =
Sig sbody
| SFunc "name" "sexp" "sexp"
and sbody =
SEmpty
| SSeq C::spec D::sbody bind "Cbinders C" in D
and spec =
Type1 "name"
| Type2 "name" "tyty"
| SStru "name" "sexp"
| SVal "name" "tyty"
and tyty =
Tyref1 "name"
| Tyref2 "path" "tyty"
| Fun "tyty" "tyty"
and path =
Sref1 "name"
| Sref2 "path" "name"
and trmtrm =
Tref1 "name"
| Tref2 "path" "name"
| Lam' v::"name" "tyty" M::"trmtrm" bind v in M
| App' "trmtrm" "trmtrm"
| Let' "body" "trmtrm"
binder
cbinders :: "defn \<Rightarrow> atom set"
and Cbinders :: "spec \<Rightarrow> atom set"
where
"cbinders (Type t T) = {atom t}"
| "cbinders (Dty t) = {atom t}"
| "cbinders (DStru x s) = {atom x}"
| "cbinders (Val v M) = {atom v}"
| "Cbinders (Type1 t) = {atom t}"
| "Cbinders (Type2 t T) = {atom t}"
| "Cbinders (SStru x S) = {atom x}"
| "Cbinders (SVal v T) = {atom v}"
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_fv
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_eq_iff
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_bn
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_perm
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_induct
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_inducts
thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm_distinct
(* example 3 from Peter Sewell's bestiary *)
nominal_datatype exp =
VarP "name"
| AppP "exp" "exp"
| LamP x::"name" e::"exp" bind x in e
| LetP x::"name" p::"pat3" e1::"exp" e2::"exp" bind x in e2, bind "bp'' p" in e1
and pat3 =
PVar "name"
| PUnit
| PPair "pat3" "pat3"
binder
bp'' :: "pat3 \<Rightarrow> atom set"
where
"bp'' (PVar x) = {atom x}"
| "bp'' (PUnit) = {}"
| "bp'' (PPair p1 p2) = bp'' p1 \<union> bp'' p2"
thm exp_pat3_fv
thm exp_pat3_eq_iff
thm exp_pat3_bn
thm exp_pat3_perm
thm exp_pat3_induct
thm exp_pat3_distinct
(* example 6 from Peter Sewell's bestiary *)
nominal_datatype exp6 =
EVar name
| EPair exp6 exp6
| ELetRec x::name p::pat6 e1::exp6 e2::exp6 bind x in e1, bind x in e2, bind "bp6 p" in e1
and pat6 =
PVar' name
| PUnit'
| PPair' pat6 pat6
binder
bp6 :: "pat6 \<Rightarrow> atom set"
where
"bp6 (PVar' x) = {atom x}"
| "bp6 (PUnit') = {}"
| "bp6 (PPair' p1 p2) = bp6 p1 \<union> bp6 p2"
thm exp6_pat6_fv
thm exp6_pat6_eq_iff
thm exp6_pat6_bn
thm exp6_pat6_perm
thm exp6_pat6_induct
thm exp6_pat6_distinct
(* THE REST ARE NOT SUPPOSED TO WORK YET *)
(* example 7 from Peter Sewell's bestiary *)
(* dest_Const raised
nominal_datatype exp7 =
EVar' name
| EUnit'
| EPair' exp7 exp7
| ELetRec' l::lrbs e::exp7 bind "b7s l" in e, bind "b7s l" in l
and lrb =
Assign' name exp7
and lrbs =
Single' lrb
| More' lrb lrbs
binder
b7 :: "lrb \<Rightarrow> atom set" and
b7s :: "lrbs \<Rightarrow> atom set"
where
"b7 (Assign x e) = {atom x}"
| "b7s (Single a) = b7 a"
| "b7s (More a as) = (b7 a) \<union> (b7s as)"
thm alpha_exp7_raw_alpha_lrb_raw_alpha_lrbs_raw.intros
*)
(* example 8 from Peter Sewell's bestiary *)
(*
*** fv_bn: recursive argument, but wrong datatype.
*** At command "nominal_datatype".
nominal_datatype exp8 =
EVar' name
| EUnit'
| EPair' exp8 exp8
| ELetRec' l::lrbs8 e::exp8 bind "b_lrbs8 l" in e, bind "b_lrbs8 l" in l
and fnclause =
K' x::name p::pat8 e::exp8 bind "b_pat p" in e
and fnclauses =
S' fnclause
| ORs' fnclause fnclauses
and lrb8 =
Clause' fnclauses
and lrbs8 =
Single' lrb8
| More' lrb8 lrbs8
and pat8 =
PVar'' name
| PUnit''
| PPair'' pat8 pat8
binder
b_lrbs8 :: "lrbs8 \<Rightarrow> atom set" and
b_pat :: "pat8 \<Rightarrow> atom set" and
b_fnclauses :: "fnclauses \<Rightarrow> atom set" and
b_fnclause :: "fnclause \<Rightarrow> atom set" and
b_lrb8 :: "lrb8 \<Rightarrow> atom set"
where
"b_lrbs8 (Single' l) = b_lrb8 l"
| "b_lrbs8 (More' l ls) = b_lrb8 l \<union> b_lrbs8 ls"
| "b_pat (PVar'' x) = {atom x}"
| "b_pat (PUnit'') = {}"
| "b_pat (PPair'' p1 p2) = b_pat p1 \<union> b_pat p2"
| "b_fnclauses (S' fc) = (b_fnclause fc)"
| "b_fnclauses (ORs' fc fcs) = (b_fnclause fc) \<union> (b_fnclauses fcs)"
| "b_lrb8 (Clause' fcs) = (b_fnclauses fcs)"
| "b_fnclause (K' x pat exp8) = {atom x}"
thm alpha_exp8_raw_alpha_fnclause_raw_alpha_fnclauses_raw_alpha_lrb8_raw_alpha_lrbs8_raw_alpha_pat8_raw.intros
*)
(* example 4 from Terms.thy *)
(* fv_eqvt does not work, we need to repaire defined permute functions
defined fv and defined alpha... *)
(* lists-datastructure does not work yet
nominal_datatype trm4 =
Vr4 "name"
| Ap4 "trm4" "trm4 list"
| Lm4 x::"name" t::"trm4" bind x in t
thm alpha_trm4_raw_alpha_trm4_raw_list.intros[no_vars]
thm fv_trm4_raw_fv_trm4_raw_list.simps[no_vars]
*)
(* core haskell *)
atom_decl var
atom_decl tvar
(* there are types, coercion types and regular types *)
(* list-data-structure
nominal_datatype tkind =
KStar
| KFun "tkind" "tkind"
and ckind =
CKEq "ty" "ty"
and ty =
TVar "tvar"
| TC "string"
| TApp "ty" "ty"
| TFun "string" "ty list"
| TAll tv::"tvar" "tkind" T::"ty" bind tv in T
| TEq "ty" "ty" "ty"
and co =
CC "string"
| CApp "co" "co"
| CFun "string" "co list"
| CAll tv::"tvar" "ckind" C::"co" bind tv in C
| CEq "co" "co" "co"
| CSym "co"
| CCir "co" "co"
| CLeft "co"
| CRight "co"
| CSim "co"
| CRightc "co"
| CLeftc "co"
| CCoe "co" "co"
abbreviation
"atoms A \<equiv> atom ` A"
nominal_datatype trm =
Var "var"
| C "string"
| LAM tv::"tvar" "kind" t::"trm" bind tv in t
| APP "trm" "ty"
| Lam v::"var" "ty" t::"trm" bind v in t
| App "trm" "trm"
| Let x::"var" "ty" "trm" t::"trm" bind x in t
| Case "trm" "assoc list"
| Cast "trm" "ty" --"ty is supposed to be a coercion type only"
and assoc =
A p::"pat" t::"trm" bind "bv p" in t
and pat =
K "string" "(tvar \<times> kind) list" "(var \<times> ty) list"
binder
bv :: "pat \<Rightarrow> atom set"
where
"bv (K s ts vs) = (atoms (set (map fst ts))) \<union> (atoms (set (map fst vs)))"
*)
text {* weirdo example from Peter Sewell's bestiary *}
nominal_datatype weird =
WBind x::"name" y::"name" p1::"weird" p2::"weird" p3::"weird"
bind x in p1, bind x in p2, bind y in p2, bind y in p3
| WV "name"
| WP "weird" "weird"
thm permute_weird_raw.simps[no_vars]
thm alpha_weird_raw.intros[no_vars]
thm fv_weird_raw.simps[no_vars]
(* example 6 from Terms.thy *)
(* BV is not respectful, needs to fail*)
(*
nominal_datatype trm6 =
Vr6 "name"
| Lm6 x::"name" t::"trm6" bind x in t
| Lt6 left::"trm6" right::"trm6" bind "bv6 left" in right
binder
bv6
where
"bv6 (Vr6 n) = {}"
| "bv6 (Lm6 n t) = {atom n} \<union> bv6 t"
| "bv6 (Lt6 l r) = bv6 l \<union> bv6 r"
*)
(* example 7 from Terms.thy *)
(* BV is not respectful, needs to fail*)
(*
nominal_datatype trm7 =
Vr7 "name"
| Lm7 l::"name" r::"trm7" bind l in r
| Lt7 l::"trm7" r::"trm7" bind "bv7 l" in r
binder
bv7
where
"bv7 (Vr7 n) = {atom n}"
| "bv7 (Lm7 n t) = bv7 t - {atom n}"
| "bv7 (Lt7 l r) = bv7 l \<union> bv7 r"
*)
(* example 8 from Terms.thy *)
(* Binding in a term under a bn, needs to fail *)
(*
nominal_datatype foo8 =
Foo0 "name"
| Foo1 b::"bar8" f::"foo8" bind "bv8 b" in f --"check fo error if this is called foo"
and bar8 =
Bar0 "name"
| Bar1 "name" s::"name" b::"bar8" bind s in b
binder
bv8
where
"bv8 (Bar0 x) = {}"
| "bv8 (Bar1 v x b) = {atom v}"
*)
(* example 9 from Terms.thy *)
(* BV is not respectful, needs to fail*)
(*
nominal_datatype lam9 =
Var9 "name"
| Lam9 n::"name" l::"lam9" bind n in l
and bla9 =
Bla9 f::"lam9" s::"lam9" bind "bv9 f" in s
binder
bv9
where
"bv9 (Var9 x) = {}"
| "bv9 (Lam9 x b) = {atom x}"
*)
(* Type schemes with separate datatypes *)
nominal_datatype T =
TVar "name"
| TFun "T" "T"
(* PROBLEM:
*** exception Datatype raised
*** (line 218 of "/usr/local/src/Isabelle_16-Mar-2010/src/HOL/Tools/Datatype/datatype_aux.ML")
*** At command "nominal_datatype".
nominal_datatype TyS =
TAll xs::"name list" ty::"T" bind xs in ty
*)
(* example 9 from Peter Sewell's bestiary *)
(* run out of steam at the moment *)
end