1 theory Test_compat

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

     3 begin

     4 

     5 text {* 

     6   example 1 

     7   

     8   single let binding

     9 *}

    10 

    11 nominal_datatype lam =

    12   VAR "name"

    13 | APP "lam" "lam"

    14 | LET bp::"bp" t::"lam"   bind "bi bp" in t

    15 and bp = 

    16   BP "name" "lam" 

    17 binder

    18   bi::"bp \<Rightarrow> atom set"

    19 where

    20   "bi (BP x t) = {atom x}"

    21 

    22 thm alpha_lam_raw_alpha_bp_raw.intros[no_vars]

    23 

    24 abbreviation "VAR \<equiv> VAR_raw"

    25 abbreviation "APP \<equiv> APP_raw"

    26 abbreviation "LET \<equiv> LET_raw"

    27 abbreviation "BP \<equiv> BP_raw"

    28 abbreviation "bi \<equiv> bi_raw"

    29 

    30 (* non-recursive case *)

    31 

    32 fun

    33     fv_lam

    34 and fv_bi

    35 and fv_bp

    36 where

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

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

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

    40 | "fv_bi (BP name lam) = fv_lam lam"

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

    42 

    43 inductive

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

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

    46   alpha_bi  :: "bp_raw \<Rightarrow> perm \<Rightarrow> bp_raw \<Rightarrow> bool"

    47 where

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

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

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

    51    \<and> alpha_bi bp pi bp' 

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

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

    54 | "alpha_lam t t' \<Longrightarrow> alpha_bi (BP x t) pi (BP x' t')" 

    55 

    56 lemma test1:

    57   assumes "distinct [x, y]"

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

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

    60 apply(rule alpha_lam_alpha_bp_alpha_bi.intros)

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

    62 apply(simp add: alpha_gen fresh_star_def)

    63 apply(simp add: alpha_lam_alpha_bp_alpha_bi.intros(1))

    64 apply(rule conjI)

    65 defer

    66 apply(rule alpha_lam_alpha_bp_alpha_bi.intros)

    67 apply(simp add: alpha_lam_alpha_bp_alpha_bi.intros(1))

    68 apply(simp add: permute_set_eq atom_eqvt)

    69 done

    70 

    71 lemma test2:

    72   assumes asm: "distinct [x, y]"

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

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

    75 using asm

    76 apply(clarify)

    77 apply(erule alpha_lam.cases)

    78 apply(simp_all)

    79 apply(erule exE)

    80 apply(clarify)

    81 apply(simp add: alpha_gen fresh_star_def)

    82 apply(erule alpha_lam.cases)

    83 apply(simp_all)

    84 apply(clarify)

    85 apply(erule alpha_bi.cases)

    86 apply(simp_all)

    87 apply(clarify)

    88 apply(erule alpha_lam.cases)

    89 apply(simp_all)

    90 done

    91 

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

    93 

    94 inductive

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

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

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

    98 where

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

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

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

   102    \<and> (pi \<bullet> (bi bp)) = bi bp'

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

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

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

   106 local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding Alpha_inj}, []), (build_alpha_inj @{thms Alpha_lam_Alpha_bp_Compat_bp.intros} @{thms lam_raw.distinct lam_raw.inject bp_raw.distinct bp_raw.inject} @{thms Alpha_lam.cases Alpha_bp.cases Compat_bp.cases} ctxt)) ctxt)) *}

   107 local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding alpha_inj}, []), (build_alpha_inj @{thms alpha_lam_raw_alpha_bp_raw.intros} @{thms lam_raw.distinct lam_raw.inject bp_raw.distinct bp_raw.inject} @{thms alpha_lam_raw.cases alpha_bp_raw.cases} ctxt)) ctxt)) *}

   108 local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding alpha_dis}, []), (flat (map (distinct_rel ctxt @{thms alpha_lam_raw.cases}) ([(@{thms lam_raw.distinct},@{term alpha_lam_raw})])))) ctxt)) *}

   109 local_setup {* (fn ctxt => snd (Local_Theory.note ((@{binding Alpha_dis}, []), (flat (map (distinct_rel ctxt @{thms Alpha_lam.cases}) ([(@{thms lam_raw.distinct},@{term Alpha_lam})])))) ctxt)) *}

   110 lemma "Alpha_lam x y = alpha_lam_raw x y"

   111 apply rule

   112 apply(induct x y rule: Alpha_lam_Alpha_bp_Compat_bp.inducts(1))

   113 apply(simp_all only: alpha_lam_raw_alpha_bp_raw.intros)

   114 apply(simp_all add: alpha_inj)

   115 apply(erule exE) apply(rule_tac x="pi" in exI)

   116 apply(simp add: alpha_gen)

   117 apply clarify

   118 apply simp

   119 defer

   120 apply(induct x y rule: alpha_lam_raw_alpha_bp_raw.inducts(1))

   121 apply(simp_all only: Alpha_lam_Alpha_bp_Compat_bp.intros)

   122 apply(simp_all add: Alpha_inj)

   123 apply(erule exE) apply(rule_tac x="pi" in exI)

   124 apply(simp add: alpha_gen)

   125 apply clarify

   126 apply simp

   127 oops

   128 

   129 lemma Test1:

   130   assumes "distinct [x, y]"

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

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

   133 apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)

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

   135 apply(simp add: alpha_gen fresh_star_def)

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

   137 apply(rule conjI)

   138 apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)

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

   140 apply(simp add: permute_set_eq atom_eqvt)

   141 done

   142 

   143 lemma Test2:

   144   assumes asm: "distinct [x, y]"

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

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

   147 using asm

   148 apply(clarify)

   149 apply(erule Alpha_lam.cases)

   150 apply(simp_all)

   151 apply(erule exE)

   152 apply(clarify)

   153 apply(simp add: alpha_gen fresh_star_def)

   154 apply(erule Alpha_lam.cases)

   155 apply(simp_all)

   156 apply(clarify)

   157 apply(erule Compat_bp.cases)

   158 apply(simp_all)

   159 apply(clarify)

   160 apply(erule Alpha_lam.cases)

   161 apply(simp_all)

   162 done

   163 

   164 

   165 text {* example 2 *}

   166 

   167 nominal_datatype trm' =

   168   Var "name"

   169 | App "trm'" "trm'"

   170 | Lam x::"name" t::"trm'"          bind x in t 

   171 | Let p::"pat'" "trm'" t::"trm'"   bind "f p" in t

   172 and pat' =

   173   PN

   174 | PS "name"

   175 | PD "name" "name"

   176 binder

   177   f::"pat' \<Rightarrow> atom set"

   178 where 

   179   "f PN = {}"

   180 | "f (PS x) = {atom x}"

   181 | "f (PD x y) = {atom x} \<union> {atom y}"

   182 

   183 thm alpha_trm'_raw_alpha_pat'_raw.intros[no_vars]

   184 

   185 abbreviation "Var \<equiv> Var_raw"

   186 abbreviation "App \<equiv> App_raw"

   187 abbreviation "Lam \<equiv> Lam_raw"

   188 abbreviation "Lett \<equiv> Let_raw"

   189 abbreviation "PN \<equiv> PN_raw"

   190 abbreviation "PS \<equiv> PS_raw"

   191 abbreviation "PD \<equiv> PD_raw"

   192 abbreviation "f \<equiv> f_raw"

   193 

   194 (* not_yet_done *)

   195 inductive 

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

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

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

   199 where

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

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

   202 | "\<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')"

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

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

   205 | "alpha_pat' PN PN"

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

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

   208 | "compat_pat' PN pi PN"

   209 | "compat_pat' (PS x) pi (PS x')"

   210 | "compat_pat' (PD p1 p2) pi (PD p1' p2')"

   211 

   212 lemma

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

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

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

   216 using a

   217 apply -

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

   219 apply(auto simp add: alpha_gen)

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

   221 apply(auto simp add: fresh_star_def permute_set_eq atom_eqvt)

   222 defer

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

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

   225 prefer 4

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

   227 (* they can be proved *)

   228 oops

   229 

   230 lemma

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

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

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

   234 using a

   235 apply -

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

   237 apply(auto simp add: alpha_gen)

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

   239 apply(auto simp add: fresh_star_def permute_set_eq atom_eqvt)

   240 defer

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

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

   243 prefer 4

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

   245 (* they can be proved *)

   246 oops

   247 

   248 using a

   249 apply(clarify)

   250 apply(erule alpha_trm'.cases)

   251 apply(simp_all)

   252 apply(auto simp add: alpha_gen)

   253 apply(erule alpha_trm'.cases)

   254 apply(simp_all)

   255 apply(clarify)

   256 apply(erule compat_pat'.cases)

   257 apply(simp_all)

   258 apply(clarify)

   259 apply(erule alpha_trm'.cases)

   260 apply(simp_all)

   261 done

   262 

   263 nominal_datatype trm0 =

   264   Var0 "name"

   265 | App0 "trm0" "trm0"

   266 | Lam0 x::"name" t::"trm0"          bind x in t 

   267 | Let0 p::"pat0" "trm0" t::"trm0"   bind "f0 p" in t

   268 and pat0 =

   269   PN0

   270 | PS0 "name"

   271 | PD0 "pat0" "pat0"

   272 binder

   273   f0::"pat0 \<Rightarrow> atom set"

   274 where 

   275   "f0 PN0 = {}"

   276 | "f0 (PS0 x) = {atom x}"

   277 | "f0 (PD0 p1 p2) = (f0 p1) \<union> (f0 p2)"

   278 

   279 thm f0_raw.simps

   280 (*thm trm0_pat0_induct

   281 thm trm0_pat0_perm

   282 thm trm0_pat0_fv

   283 thm trm0_pat0_bn*)

   284 

   285 text {* example type schemes *}

   286 

   287 (* does not work yet

   288 nominal_datatype t =

   289   Var "name"

   290 | Fun "t" "t"

   291 

   292 nominal_datatype tyS =

   293   All xs::"name list" ty::"t_raw" bind xs in ty

   294 *)

   295 

   296 

   297 nominal_datatype t = 

   298   Var "name" 

   299 | Fun "t" "t"

   300 and  tyS = 

   301   All xs::"name set" ty::"t" bind xs in ty

   302 

   303 (* example 1 from Terms.thy *)

   304 

   305 nominal_datatype trm1 =

   306   Vr1 "name"

   307 | Ap1 "trm1" "trm1"

   308 | Lm1 x::"name" t::"trm1"       bind x in t 

   309 | Lt1 p::"bp1" "trm1" t::"trm1" bind "bv1 p" in t 

   310 and bp1 =

   311   BUnit1

   312 | BV1 "name"

   313 | BP1 "bp1" "bp1"

   314 binder

   315   bv1

   316 where

   317   "bv1 (BUnit1) = {}"

   318 | "bv1 (BV1 x) = {atom x}"

   319 | "bv1 (BP1 bp1 bp2) = (bv1 bp1) \<union> (bv1 bp2)"

   320 

   321 thm bv1_raw.simps

   322 

   323 (* example 2 from Terms.thy *)

   324 

   325 nominal_datatype trm2 =

   326   Vr2 "name"

   327 | Ap2 "trm2" "trm2"

   328 | Lm2 x::"name" t::"trm2"       bind x in t

   329 | Lt2 r::"assign" t::"trm2"    bind "bv2 r" in t

   330 and assign = 

   331   As "name" "trm2"

   332 binder

   333   bv2

   334 where

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

   336 

   337 (* compat should be

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

   339 *)

   340 

   341 

   342 thm fv_trm2_raw_fv_assign_raw.simps[no_vars]

   343 thm alpha_trm2_raw_alpha_assign_raw.intros[no_vars]

   344 

   345 

   346 

   347 text {* example 3 from Terms.thy *}

   348 

   349 nominal_datatype trm3 =

   350   Vr3 "name"

   351 | Ap3 "trm3" "trm3"

   352 | Lm3 x::"name" t::"trm3"        bind x in t

   353 | Lt3 r::"rassigns3" t::"trm3"   bind "bv3 r" in t

   354 and rassigns3 =

   355   ANil

   356 | ACons "name" "trm3" "rassigns3"

   357 binder

   358   bv3

   359 where

   360   "bv3 ANil = {}"

   361 | "bv3 (ACons x t as) = {atom x} \<union> (bv3 as)"

   362 

   363 

   364 (* compat should be

   365 compat (ANil) pi (PNil) \<equiv> TRue

   366 compat (ACons x t ts) pi (ACons x' t' ts') \<equiv> pi o x = x' \<and> alpha t t' \<and> compat ts pi ts'

   367 *)

   368 

   369 (* example 4 from Terms.thy *)

   370 

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

   372    defined fv and defined alpha... *)

   373 nominal_datatype trm4 =

   374   Vr4 "name"

   375 | Ap4 "trm4" "trm4 list"

   376 | Lm4 x::"name" t::"trm4"  bind x in t

   377 

   378 thm alpha_trm4_raw_alpha_trm4_raw_list.intros[no_vars]

   379 thm fv_trm4_raw_fv_trm4_raw_list.simps[no_vars]

   380 

   381 (* example 5 from Terms.thy *)

   382 

   383 nominal_datatype trm5 =

   384   Vr5 "name"

   385 | Ap5 "trm5" "trm5"

   386 | Lt5 l::"lts" t::"trm5"  bind "bv5 l" in t

   387 and lts =

   388   Lnil

   389 | Lcons "name" "trm5" "lts"

   390 binder

   391   bv5

   392 where

   393   "bv5 Lnil = {}"

   394 | "bv5 (Lcons n t ltl) = {atom n} \<union> (bv5 ltl)"

   395 

   396 (* example 6 from Terms.thy *)

   397 

   398 (* BV is not respectful, needs to fail*)

   399 nominal_datatype trm6 =

   400   Vr6 "name"

   401 | Lm6 x::"name" t::"trm6"         bind x in t

   402 | Lt6 left::"trm6" right::"trm6"  bind "bv6 left" in right

   403 binder

   404   bv6

   405 where

   406   "bv6 (Vr6 n) = {}"

   407 | "bv6 (Lm6 n t) = {atom n} \<union> bv6 t"

   408 | "bv6 (Lt6 l r) = bv6 l \<union> bv6 r"

   409 (* example 7 from Terms.thy *)

   410 

   411 (* BV is not respectful, needs to fail*)

   412 nominal_datatype trm7 =

   413   Vr7 "name"

   414 | Lm7 l::"name" r::"trm7"   bind l in r

   415 | Lt7 l::"trm7" r::"trm7"   bind "bv7 l" in r

   416 binder 

   417   bv7 

   418 where

   419   "bv7 (Vr7 n) = {atom n}"

   420 | "bv7 (Lm7 n t) = bv7 t - {atom n}"

   421 | "bv7 (Lt7 l r) = bv7 l \<union> bv7 r"

   422 

   423 (* example 8 from Terms.thy *)

   424 

   425 nominal_datatype foo8 =

   426   Foo0 "name"

   427 | Foo1 b::"bar8" f::"foo8" bind "bv8 b" in f --"check fo error if this is called foo"

   428 and bar8 =

   429   Bar0 "name"

   430 | Bar1 "name" s::"name" b::"bar8" bind s in b

   431 binder 

   432   bv8

   433 where

   434   "bv8 (Bar0 x) = {}"

   435 | "bv8 (Bar1 v x b) = {atom v}"

   436 

   437 (* example 9 from Terms.thy *)

   438 

   439 (* BV is not respectful, needs to fail*)

   440 nominal_datatype lam9 =

   441   Var9 "name"

   442 | Lam9 n::"name" l::"lam9" bind n in l

   443 and bla9 =

   444   Bla9 f::"lam9" s::"lam9" bind "bv9 f" in s

   445 binder

   446   bv9

   447 where

   448   "bv9 (Var9 x) = {}"

   449 | "bv9 (Lam9 x b) = {atom x}"

   450 

   451 (* example from my PHD *)

   452 

   453 atom_decl coname

   454 

   455 nominal_datatype phd =

   456    Ax "name" "coname"

   457 |  Cut n::"coname" t1::"phd" c::"coname" t2::"phd"              bind n in t1, bind c in t2

   458 |  AndR c1::"coname" t1::"phd" c2::"coname" t2::"phd" "coname"  bind c1 in t1, bind c2 in t2

   459 |  AndL1 n::"name" t::"phd" "name"                              bind n in t

   460 |  AndL2 n::"name" t::"phd" "name"                              bind n in t

   461 |  ImpL c::"coname" t1::"phd" n::"name" t2::"phd" "name"        bind c in t1, bind n in t2

   462 |  ImpR c::"coname" n::"name" t::"phd" "coname"                 bind n in t, bind c in t

   463 

   464 thm alpha_phd_raw.intros[no_vars]

   465 thm fv_phd_raw.simps[no_vars]

   466 

   467 

   468 (* example form Leroy 96 about modules; OTT *)

   469 

   470 nominal_datatype mexp =

   471   Acc "path"

   472 | Stru "body"

   473 | Funct x::"name" "sexp" m::"mexp"    bind x in m

   474 | FApp "mexp" "path"

   475 | Ascr "mexp" "sexp"

   476 and body =

   477   Empty

   478 | Seq c::defn d::"body"     bind "cbinders c" in d

   479 and defn =  

   480   Type "name" "tyty"

   481 | Dty "name"

   482 | DStru "name" "mexp"

   483 | Val "name" "trmtrm"

   484 and sexp =

   485   Sig sbody

   486 | SFunc "name" "sexp" "sexp"

   487 and sbody = 

   488   SEmpty

   489 | SSeq C::spec D::sbody    bind "Cbinders C" in D

   490 and spec =

   491   Type1 "name" 

   492 | Type2 "name" "tyty"

   493 | SStru "name" "sexp"

   494 | SVal "name" "tyty"

   495 and tyty =

   496   Tyref1 "name"

   497 | Tyref2 "path" "tyty"

   498 | Fun "tyty" "tyty"

   499 and path =

   500   Sref1 "name"

   501 | Sref2 "path" "name"

   502 and trmtrm =

   503   Tref1 "name"

   504 | Tref2 "path" "name"

   505 | Lam' v::"name" "tyty" M::"trmtrm"  bind v in M

   506 | App' "trmtrm" "trmtrm"

   507 | Let' "body" "trmtrm"

   508 binder

   509     cbinders :: "defn \<Rightarrow> atom set"

   510 and Cbinders :: "spec \<Rightarrow> atom set"

   511 where

   512   "cbinders (Type t T) = {atom t}"

   513 | "cbinders (Dty t) = {atom t}"

   514 | "cbinders (DStru x s) = {atom x}"

   515 | "cbinders (Val v M) = {atom v}"

   516 | "Cbinders (Type1 t) = {atom t}"

   517 | "Cbinders (Type2 t T) = {atom t}"

   518 | "Cbinders (SStru x S) = {atom x}"

   519 | "Cbinders (SVal v T) = {atom v}"  

   520 

   521 (* core haskell *)

   522 print_theorems

   523 

   524 atom_decl var

   525 atom_decl tvar

   526 

   527 

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

   529 nominal_datatype tkind = 

   530   KStar

   531 | KFun "tkind" "tkind"

   532 and ckind =

   533   CKEq "ty" "ty" 

   534 and ty =

   535   TVar "tvar"

   536 | TC "string"

   537 | TApp "ty" "ty"

   538 | TFun "string" "ty list"

   539 | TAll tv::"tvar" "tkind" T::"ty"  bind tv in T

   540 | TEq "ty" "ty" "ty"

   541 and co =

   542   CC "string"

   543 | CApp "co" "co"

   544 | CFun "string" "co list"

   545 | CAll tv::"tvar" "ckind" C::"co"  bind tv in C

   546 | CEq "co" "co" "co"

   547 | CSym "co"

   548 | CCir "co" "co"

   549 | CLeft "co"

   550 | CRight "co"

   551 | CSim "co"

   552 | CRightc "co"

   553 | CLeftc "co"

   554 | CCoe "co" "co"

   555 

   556 

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

   558 

   559 abbreviation 

   560   "atoms A \<equiv> atom ` A"

   561 

   562 nominal_datatype trm =

   563   Var "var"

   564 | C "string"

   565 | LAM tv::"tvar" "kind" t::"trm"   bind tv in t 

   566 | APP "trm" "ty"

   567 | Lam v::"var" "ty" t::"trm"       bind v in t

   568 | App "trm" "trm"

   569 | Let x::"var" "ty" "trm" t::"trm" bind x in t

   570 | Case "trm" "assoc list"

   571 | Cast "trm" "ty"                   --"ty is supposed to be a coercion type only"

   572 and assoc = 

   573   A p::"pat" t::"trm" bind "bv p" in t 

   574 and pat = 

   575   K "string" "(tvar \<times> kind) list" "(var \<times> ty) list"

   576 binder

   577  bv :: "pat \<Rightarrow> atom set"

   578 where

   579  "bv (K s ts vs) = (atoms (set (map fst ts))) \<union> (atoms (set (map fst vs)))"

   580 

   581 (*

   582 compat (K s ts vs) pi (K s' ts' vs') ==

   583   s = s' & 

   584 

   585 *)

   586 

   587 

   588 (*thm bv_raw.simps*)

   589 

   590 (* example 3 from Peter Sewell's bestiary *)

   591 nominal_datatype exp =

   592   VarP "name"

   593 | AppP "exp" "exp"

   594 | LamP x::"name" e::"exp" bind x in e

   595 | LetP x::"name" p::"pat" e1::"exp" e2::"exp" bind x in e2, bind "bp p" in e1

   596 and pat =

   597   PVar "name"

   598 | PUnit

   599 | PPair "pat" "pat"

   600 binder

   601   bp :: "pat \<Rightarrow> atom set"

   602 where

   603   "bp (PVar x) = {atom x}"

   604 | "bp (PUnit) = {}"

   605 | "bp (PPair p1 p2) = bp p1 \<union> bp p2"

   606 thm alpha_exp_raw_alpha_pat_raw.intros

   607 

   608 (* example 6 from Peter Sewell's bestiary *)

   609 nominal_datatype exp6 =

   610   EVar name

   611 | EPair exp6 exp6

   612 | ELetRec x::name p::pat6 e1::exp6 e2::exp6 bind x in e1, bind x in e2, bind "bp6 p" in e1

   613 and pat6 =

   614   PVar' name

   615 | PUnit'

   616 | PPair' pat6 pat6

   617 binder

   618   bp6 :: "pat6 \<Rightarrow> atom set"

   619 where

   620   "bp6 (PVar' x) = {atom x}"

   621 | "bp6 (PUnit') = {}"

   622 | "bp6 (PPair' p1 p2) = bp6 p1 \<union> bp6 p2"

   623 thm alpha_exp6_raw_alpha_pat6_raw.intros

   624 

   625 (* example 7 from Peter Sewell's bestiary *)

   626 nominal_datatype exp7 =

   627   EVar name

   628 | EUnit

   629 | EPair exp7 exp7

   630 | ELetRec l::lrbs e::exp7 bind "b7s l" in e, bind "b7s l" in l

   631 and lrb =

   632   Assign name exp7

   633 and lrbs =

   634   Single lrb

   635 | More lrb lrbs

   636 binder

   637   b7 :: "lrb \<Rightarrow> atom set" and

   638   b7s :: "lrbs \<Rightarrow> atom set"

   639 where

   640   "b7 (Assign x e) = {atom x}"

   641 | "b7s (Single a) = b7 a"

   642 | "b7s (More a as) = (b7 a) \<union> (b7s as)"

   643 thm alpha_exp7_raw_alpha_lrb_raw_alpha_lrbs_raw.intros

   644 

   645 (* example 8 from Peter Sewell's bestiary *)

   646 nominal_datatype exp8 =

   647   EVar name

   648 | EUnit

   649 | EPair exp8 exp8

   650 | ELetRec l::lrbs8 e::exp8 bind "b_lrbs8 l" in e, bind "b_lrbs8 l" in l

   651 and fnclause =

   652   K x::name p::pat8 e::exp8 bind "b_pat p" in e

   653 and fnclauses =

   654   S fnclause

   655 | ORs fnclause fnclauses

   656 and lrb8 =

   657   Clause fnclauses

   658 and lrbs8 =

   659   Single lrb8

   660 | More lrb8 lrbs8

   661 and pat8 =

   662   PVar name

   663 | PUnit

   664 | PPair pat8 pat8

   665 binder

   666   b_lrbs8 :: "lrbs8 \<Rightarrow> atom set" and

   667   b_pat :: "pat8 \<Rightarrow> atom set" and

   668   b_fnclauses :: "fnclauses \<Rightarrow> atom set" and

   669   b_fnclause :: "fnclause \<Rightarrow> atom set" and

   670   b_lrb8 :: "lrb8 \<Rightarrow> atom set"

   671 where

   672   "b_lrbs8 (Single l) = b_lrb8 l"

   673 | "b_lrbs8 (More l ls) = b_lrb8 l \<union> b_lrbs8 ls"

   674 | "b_pat (PVar x) = {atom x}"

   675 | "b_pat (PUnit) = {}"

   676 | "b_pat (PPair p1 p2) = b_pat p1 \<union> b_pat p2"

   677 | "b_fnclauses (S fc) = (b_fnclause fc)"

   678 | "b_fnclauses (ORs fc fcs) = (b_fnclause fc) \<union> (b_fnclauses fcs)"

   679 | "b_lrb8 (Clause fcs) = (b_fnclauses fcs)"

   680 | "b_fnclause (K x pat exp8) = {atom x}"

   681 thm alpha_exp8_raw_alpha_fnclause_raw_alpha_fnclauses_raw_alpha_lrb8_raw_alpha_lrbs8_raw_alpha_pat8_raw.intros

   682 

   683 

   684 

   685 

   686 (* example 9 from Peter Sewell's bestiary *)

   687 (* run out of steam at the moment *)

   688 

   689 end

   690 

   691 

   692