theory Test_compat

imports "Parser" "../Attic/Prove"

begin

text {* 

  example 1 

  single let binding

*}

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

thm alpha_lam_raw_alpha_bp_raw.intros[no_vars]

thm fv_lam_raw_fv_bp_raw.simps[no_vars]

abbreviation "VAR \<equiv> VAR_raw"

abbreviation "APP \<equiv> APP_raw"

abbreviation "LET \<equiv> LET_raw"

abbreviation "BP \<equiv> BP_raw"

abbreviation "bi \<equiv> bi_raw"

(* non-recursive case *)

primrec

    fv_lam :: "lam_raw \<Rightarrow> atom set"

and fv_compat :: "bp_raw \<Rightarrow> atom set"

where

  "fv_lam (VAR name) = {atom name}"

| "fv_lam (APP lam1 lam2) = fv_lam lam1 \<union> fv_lam lam2"

| "fv_lam (LET bp lam) = (fv_compat bp) \<union> (fv_lam lam - bi bp)"

| "fv_compat (BP name lam) = fv_lam lam"

primrec

    fv_bp :: "bp_raw \<Rightarrow> atom set"

where

  "fv_bp (BP name lam) = {atom name} \<union> fv_lam lam"

inductive

  alpha_lam :: "lam_raw \<Rightarrow> lam_raw \<Rightarrow> bool" and

  alpha_bp  :: "bp_raw \<Rightarrow> bp_raw \<Rightarrow> bool" and

  compat_bp :: "bp_raw \<Rightarrow> perm \<Rightarrow> bp_raw \<Rightarrow> bool"

where

  "x = y \<Longrightarrow> alpha_lam (VAR x) (VAR y)"

| "alpha_lam l1 s1 \<and> alpha_lam l2 s2 \<Longrightarrow> alpha_lam (APP l1 l2) (APP s1 s2)"

| "\<exists>pi. (bi bp, lam) \<approx>gen alpha_lam fv_lam_raw pi (bi bp', lam') \<and> compat_bp bp pi bp' 

   \<Longrightarrow> alpha_lam (LET bp lam) (LET bp' lam')"

| "alpha_lam lam lam' \<and> name = name' \<Longrightarrow> alpha_bp (BP name lam) (BP name' lam')"

| "alpha_lam t t' \<and> pi \<bullet> x = x' \<Longrightarrow> compat_bp (BP x t) pi (BP x' t')" 

lemma test1:

  shows "alpha_lam (LET (BP x (VAR x)) (VAR x))

                   (LET (BP y (VAR x)) (VAR y))"

apply(rule alpha_lam_alpha_bp_compat_bp.intros)

apply(rule_tac x="(x \<leftrightarrow> y)" in exI)

apply(simp add: alpha_gen fresh_star_def)

apply(simp add: alpha_lam_alpha_bp_compat_bp.intros(1))

apply(rule alpha_lam_alpha_bp_compat_bp.intros)

apply(simp add: alpha_lam_alpha_bp_compat_bp.intros(1))

done

lemma test2:

  assumes asm: "distinct [x, y]"

  shows "\<not> alpha_lam (LET (BP x (VAR x)) (VAR x))

                     (LET (BP y (VAR y)) (VAR y))"

using asm

apply(clarify)

apply(erule alpha_lam.cases)

apply(simp_all)

apply(erule exE)

apply(clarify)

apply(simp add: alpha_gen fresh_star_def)

apply(erule alpha_lam.cases)

apply(simp_all)

apply(clarify)

apply(erule compat_bp.cases)

apply(simp_all)

apply(clarify)

apply(erule alpha_lam.cases)

apply(simp_all)

done

(* recursive case where we have also bind "bi bp" in bp *)

inductive

  Alpha_lam :: "lam_raw \<Rightarrow> lam_raw \<Rightarrow> bool" and

  Alpha_bp  :: "bp_raw \<Rightarrow> bp_raw \<Rightarrow> bool" and

  Compat_bp :: "bp_raw \<Rightarrow> perm \<Rightarrow> bp_raw \<Rightarrow> bool"

where

  "x = y \<Longrightarrow> Alpha_lam (VAR x) (VAR y)"

| "Alpha_lam l1 s1 \<and> Alpha_lam l2 s2 \<Longrightarrow> Alpha_lam (APP l1 l2) (APP s1 s2)"

| "\<exists>pi. (bi bp, lam) \<approx>gen Alpha_lam fv_lam_raw pi (bi bp', lam') \<and> Compat_bp bp pi bp' 

   \<Longrightarrow> Alpha_lam (LET bp lam) (LET bp' lam')"

| "Alpha_lam lam lam' \<and> name = name' \<Longrightarrow> Alpha_bp (BP name lam) (BP name' lam')"

| "Alpha_lam (pi \<bullet> t) t' \<and> pi \<bullet> x = x' \<Longrightarrow> Compat_bp (BP x t) pi (BP x' t')"

lemma Test1:

  assumes "distinct [x, y]"

  shows "Alpha_lam (LET (BP x (VAR x)) (VAR x))

                   (LET (BP y (VAR y)) (VAR y))"

apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)

apply(rule_tac x="(x \<leftrightarrow> y)" in exI)

apply(simp add: alpha_gen fresh_star_def)

apply(simp add: Alpha_lam_Alpha_bp_Compat_bp.intros(1))

apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)

apply(simp add: Alpha_lam_Alpha_bp_Compat_bp.intros(1))

done

lemma Test2:

  assumes asm: "distinct [x, y]"

  shows "\<not> Alpha_lam (LET (BP x (VAR x)) (VAR x))

                     (LET (BP y (VAR x)) (VAR y))"

using asm

apply(clarify)

apply(erule Alpha_lam.cases)

apply(simp_all)

apply(erule exE)

apply(clarify)

apply(simp add: alpha_gen fresh_star_def)

apply(erule Alpha_lam.cases)

apply(simp_all)

apply(clarify)

apply(erule Compat_bp.cases)

apply(simp_all)

apply(clarify)

apply(erule Alpha_lam.cases)

apply(simp_all)

done

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} \<union> {atom y}"

thm alpha_trm'_raw_alpha_pat'_raw.intros[no_vars]

abbreviation "Var \<equiv> Var_raw"

abbreviation "App \<equiv> App_raw"

abbreviation "Lam \<equiv> Lam_raw"

abbreviation "Lett \<equiv> Let_raw"

abbreviation "PN \<equiv> PN_raw"

abbreviation "PS \<equiv> PS_raw"

abbreviation "PD \<equiv> PD_raw"

abbreviation "f \<equiv> f_raw"

(* not_yet_done *)

inductive 

  alpha_trm' :: "trm'_raw \<Rightarrow> trm'_raw \<Rightarrow> bool" and

  alpha_pat'  :: "pat'_raw \<Rightarrow> pat'_raw \<Rightarrow> bool" and

  compat_pat' :: "pat'_raw \<Rightarrow> perm \<Rightarrow> pat'_raw \<Rightarrow> bool"

where

  "name = name' \<Longrightarrow> alpha_trm' (Var name) (Var name')"

| "alpha_trm' t2 t2' \<and> alpha_trm' t1 t1' \<Longrightarrow> alpha_trm' (App t1 t2) (App t1' t2')"

| "\<exists>pi. ({atom x}, t) \<approx>gen alpha_trm' fv_trm'_raw pi ({atom x'}, t') \<Longrightarrow> alpha_trm' (Lam x t) (Lam x' t')"

| "\<exists>pi. (f p, t) \<approx>gen alpha_trm' fv_trm'_raw pi (f p', t') \<and> alpha_trm' s s' \<and>

        compat_pat' p pi p' \<Longrightarrow> alpha_trm' (Lett p s t) (Lett p' s' t')"

| "alpha_pat' PN PN"

| "name = name' \<Longrightarrow> alpha_pat' (PS name) (PS name')"

| "name2 = name2' \<and> name1 = name1' \<Longrightarrow> alpha_pat' (PD name1 name2) (PD name1' name2')"

| "compat_pat' PN pi PN"

| "pi \<bullet> x = x' \<Longrightarrow> compat_pat' (PS x) pi (PS x')"

| "pi \<bullet> p1 = p1' \<and> pi \<bullet> p2 = p2' \<Longrightarrow> compat_pat' (PD p1 p2) pi (PD p1' p2')"

lemma

  assumes a: "distinct [x, y, z, u]"

  shows "alpha_trm' (Lett (PD x u) t (App (Var x) (Var y)))

                    (Lett (PD z u) t (App (Var z) (Var y)))"

using a

apply -

apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)

apply(auto simp add: alpha_gen)

apply(rule_tac x="(x \<leftrightarrow> z)" in exI)

apply(auto simp add: fresh_star_def)

defer

apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)

apply(simp add: alpha_trm'_alpha_pat'_compat_pat'.intros)

defer

apply(rule alpha_trm'_alpha_pat'_compat_pat'.intros)

apply(simp)

(* they can be proved *)

oops

lemma

  assumes a: "distinct [x, y, z, u]"

  shows "\<not> alpha_trm' (Lett (PD x u) t (App (Var x) (Var y)))

                      (Lett (PD z z) t (App (Var z) (Var y)))"

using a

apply(clarify)

apply(erule alpha_trm'.cases)

apply(simp_all)

apply(auto simp add: alpha_gen)

apply(erule alpha_trm'.cases)

apply(simp_all)

apply(clarify)

apply(erule compat_pat'.cases)

apply(simp_all)

apply(clarify)

apply(erule alpha_trm'.cases)

apply(simp_all)

done

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

(*thm trm0_pat0_induct

thm trm0_pat0_perm

thm trm0_pat0_fv

thm trm0_pat0_bn*)

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

*)

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::"assign" t::"trm2"    bind "bv2 r" in t

and assign = 

  As "name" "trm2"

binder

  bv2

where

  "bv2 (As x t) = {atom x}"

(* compat should be

compat (As x t) pi (As x' t') == pi o x = x' & alpha t t'

*)

thm fv_trm2_raw_fv_assign_raw.simps[no_vars]

thm alpha_trm2_raw_alpha_assign_raw.intros[no_vars]

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

(* 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 4 from Terms.thy *)

(* fv_eqvt does not work, we need to repaire defined permute functions

   defined fv and defined alpha... *)

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

(* 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 *)

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

(* 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 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 *)

print_theorems

atom_decl var

atom_decl tvar

(* there are types, coercion types and regular types *)

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"

typedecl ty --"hack since ty is not yet defined"

abbreviation 

  "atoms A \<equiv> atom ` A"

nominal_datatype trm =