theory Test
imports "Parser"
begin
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]
(* Potential problem: Is it correct that in the fv-function
the first two terms are created? Should be ommitted. Also
something wrong with the permutations. *)
primrec
fv_weird
where
"fv_weird (WBind_raw x y p1 p2 p3) =
(fv_weird p1 - {atom x}) \<union> (fv_weird p2 - ({atom x} \<union> {atom y})) \<union> (fv_weird p3 - {atom y})"
| "fv_weird (WV_raw x) = {atom x}"
| "fv_weird (WP_raw p1 p2) = (fv_weird p1 \<union> fv_weird p2)"
inductive
alpha_weird
where
"\<exists>p1 p2.
({atom y}, w3) \<approx>gen alpha_weird fv_weird p2 ({atom ya}, w3a) \<and>
({atom x} \<union> {atom y}, w2) \<approx>gen alpha_weird fv_weird (p1 + p2) ({atom xa} \<union> {atom ya}, w2a) \<and>
({atom x}, w1) \<approx>gen alpha_weird fv_weird p1 ({atom xa}, w1a) \<and>
supp p1 \<inter> supp p2 = {} \<Longrightarrow>
alpha_weird (WBind_raw x y w1 w2 w3) (WBind_raw xa ya w1a w2a w3a)"
| "x = xa \<Longrightarrow> alpha_weird (WV_raw x) (WV_raw xa)"
| "alpha_weird w2 w2a \<and> alpha_weird w1 w1a \<Longrightarrow> alpha_weird (WP_raw w1 w2) (WP_raw w1a w2a)"
(*
abbreviation "WBind \<equiv> WBind_raw"
abbreviation "WP \<equiv> WP_raw"
abbreviation "WV \<equiv> WV_raw"
lemma test:
assumes a: "distinct [x, y, z]"
shows "alpha_weird (WBind x y (WP (WV x) (WV z)) (WP (WV x) (WV y)) (WP (WV z) (WV y)))
(WBind y x (WP (WV y) (WV z)) (WP (WV y) (WV x)) (WP (WV z) (WV x)))"
apply(rule_tac alpha_weird.intros)
unfolding alpha_gen
using a
apply(simp)
apply(rule_tac x="(x \<leftrightarrow> y)" in exI)
apply(rule_tac x="(x \<leftrightarrow> y)" in exI)
apply(simp add: fresh_star_def)
apply(simp add: flip_def)
apply(auto)
prefer 2
apply(rule alpha_weird.intros)
apply(simp add: alpha_weird.intros(2))
prefer 2
apply(rule alpha_weird.intros)
apply(simp add: alpha_weird.intros(2))
apply(simp)
apply(rule alpha_weird.intros)
apply(simp)
apply(simp add: alpha_gen)
using a
apply(simp)
*)
text {* example 1 *}
(* ML {* set show_hyps *} *)
nominal_datatype lam =
VAR "name"
| APP "lam" "lam"
| 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}"
typ lam_raw
term VAR_raw
term APP_raw
term LET_raw
term Test.BP_raw
thm bi_raw.simps
thm permute_lam_raw_permute_bp_raw.simps
thm alpha_lam_raw_alpha_bp_raw.intros[no_vars]
thm fv_lam_raw_fv_bp_raw.simps[no_vars]
thm eqvts
print_theorems
text {* example 2 *}
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 (PS x) = {atom x}"
| "f (PD x y) = {atom x, atom y}"
thm alpha_trm'_raw_alpha_pat'_raw.intros[no_vars]
thm fv_trm'_raw_fv_pat'_raw.simps[no_vars]
thm f_raw.simps
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 f0_raw.simps
text {* example type schemes *}
(* does not work yet
nominal_datatype t =
Var "name"
| Fun "t" "t"
nominal_datatype tyS =
All xs::"name list" ty::"t_raw" bind xs in ty
*)
(* alpha_eqvt fails...
nominal_datatype t =
Var "name"
| Fun "t" "t"
and tyS =
All xs::"name set" ty::"t" bind xs in ty *)
(* 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 (BV1 x) = {atom x}"
| "bv1 (BP1 bp1 bp2) = (bv1 bp1) \<union> (bv1 bp2)"
thm bv1_raw.simps
(* example 2 from Terms.thy *)
nominal_datatype trm2 =
Vr2 "name"
| Ap2 "trm2" "trm2"
| Lm2 x::"name" t::"trm2" bind x in t
| Lt2 r::"rassign" t::"trm2" bind "bv2 r" in t
and rassign =
As "name" "trm2"
binder
bv2
where
"bv2 (As x t) = {atom x}"
(* 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)"
(* example 4 from Terms.thy *)
(* fv_eqvt does not work, we need to repaire defined permute functions...
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]
(* 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)"
(* example 6 from Terms.thy *)
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 *)
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 *)
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 *)
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}"
(* 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
(* PROBLEM?: why does it create for the Cut AndR ImpL cases
two permutations, but only one is used *)
thm alpha_phd_raw.intros[no_vars]
thm fv_phd_raw.simps[no_vars]
(* 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}"
(* core haskell *)
atom_decl var
atom_decl tvar
atom_decl co
datatype sort =
TY tvar
| CO co
nominal_datatype kind =
KStar
| KFun kind kind
| KEq kind kind
(* there are types, coercion types and regular types *)
(*
nominal_datatype ty =
TVar tvar
| TFun string "ty list"
| TAll tvar kind_raw ty --"some binding"
| TSym ty
| TCir ty ty
| TApp ty ty
| TLeft ty
| TRight ty
| TEq ty
| TRightc ty
| TLeftc ty
| TCoe ty ty
*)
typedecl ty --"hack since ty is not yet defined"
abbreviation
"atoms A \<equiv> atom ` A"
(* does not work yet
nominal_datatype trm =
Var var
| LAM tv::tvar kind_raw 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_raw) 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)))"
*)
(*thm bv_raw.simps*)
(* example 3 from Peter Sewell's bestiary *)
nominal_datatype exp =
Var "name"
| App "exp" "exp"
| Lam x::"name" e::"exp" bind x in e
| Let x::"name" p::"pat" e1::"exp" e2::"exp" bind x in e2, bind "bp p" in e1
and pat =
PVar "name"
| PUnit
| PPair "pat" "pat"
binder
bp :: "pat \<Rightarrow> atom set"
where
"bp (PVar x) = {atom x}"
| "bp (PUnit) = {}"
| "bp (PPair p1 p2) = bp p1 \<union> bp p2"
(* 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"
(* example 7 from Peter Sewell's bestiary *)
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)"
(* example 8 from Peter Sewell's bestiary *)
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}"
(* example 9 from Peter Sewell's bestiary *)
(* run out of steam at the moment *)
end