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 thm fv_lam_raw_fv_bp_raw.simps[no_vars]

    24 

    25 abbreviation "VAR \<equiv> VAR_raw"

    26 abbreviation "APP \<equiv> APP_raw"

    27 abbreviation "LET \<equiv> LET_raw"

    28 abbreviation "BP \<equiv> BP_raw"

    29 abbreviation "bi \<equiv> bi_raw"

    30 

    31 (* non-recursive case *)

    32 primrec

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

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

    35 where

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

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

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

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

    40 

    41 primrec

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

    43 where

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

    45 

    46 

    47 inductive

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

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

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

    51 where

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

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

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

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

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

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

    58 

    59 lemma test1:

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

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

    62 apply(rule alpha_lam_alpha_bp_compat_bp.intros)

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

    64 apply(simp add: alpha_gen fresh_star_def)

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

    66 apply(rule alpha_lam_alpha_bp_compat_bp.intros)

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

    68 done

    69 

    70 lemma test2:

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

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

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

    74 using asm

    75 apply(clarify)

    76 apply(erule alpha_lam.cases)

    77 apply(simp_all)

    78 apply(erule exE)

    79 apply(clarify)

    80 apply(simp add: alpha_gen fresh_star_def)

    81 apply(erule alpha_lam.cases)

    82 apply(simp_all)

    83 apply(clarify)

    84 apply(erule compat_bp.cases)

    85 apply(simp_all)

    86 apply(clarify)

    87 apply(erule alpha_lam.cases)

    88 apply(simp_all)

    89 done

    90 

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

    92 

    93 inductive

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

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

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

    97 where

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

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

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

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

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

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

   104 

   105 lemma Test1:

   106   assumes "distinct [x, y]"

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

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

   109 apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)

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

   111 apply(simp add: alpha_gen fresh_star_def)

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

   113 apply(rule Alpha_lam_Alpha_bp_Compat_bp.intros)

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

   115 done

   116 

   117 lemma Test2:

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

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

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

   121 using asm

   122 apply(clarify)

   123 apply(erule Alpha_lam.cases)

   124 apply(simp_all)

   125 apply(erule exE)

   126 apply(clarify)

   127 apply(simp add: alpha_gen fresh_star_def)

   128 apply(erule Alpha_lam.cases)

   129 apply(simp_all)

   130 apply(clarify)

   131 apply(erule Compat_bp.cases)

   132 apply(simp_all)

   133 apply(clarify)

   134 apply(erule Alpha_lam.cases)

   135 apply(simp_all)

   136 done

   137 

   138 

   139 text {* example 2 *}

   140 

   141 nominal_datatype trm' =

   142   Var "name"

   143 | App "trm'" "trm'"

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

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

   146 and pat' =

   147   PN

   148 | PS "name"

   149 | PD "name" "name"

   150 binder

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

   152 where 

   153   "f PN = {}"

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

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

   156 

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

   158 

   159 abbreviation "Var \<equiv> Var_raw"

   160 abbreviation "App \<equiv> App_raw"

   161 abbreviation "Lam \<equiv> Lam_raw"

   162 abbreviation "Lett \<equiv> Let_raw"

   163 abbreviation "PN \<equiv> PN_raw"

   164 abbreviation "PS \<equiv> PS_raw"

   165 abbreviation "PD \<equiv> PD_raw"

   166 abbreviation "f \<equiv> f_raw"

   167 

   168 (* not_yet_done *)

   169 inductive 

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

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

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

   173 where

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

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

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

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

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

   179 | "alpha_pat' PN PN"

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

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

   182 | "compat_pat' PN pi PN"

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

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

   185 

   186 lemma

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

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

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

   190 using a

   191 apply -

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

   193 apply(auto simp add: alpha_gen)

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

   195 apply(auto simp add: fresh_star_def)

   196 defer

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

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

   199 defer

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

   201 apply(simp)

   202 (* they can be proved *)

   203 oops

   204 

   205 lemma

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

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

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

   209 using a

   210 apply(clarify)

   211 apply(erule alpha_trm'.cases)

   212 apply(simp_all)

   213 apply(auto simp add: alpha_gen)

   214 apply(erule alpha_trm'.cases)

   215 apply(simp_all)

   216 apply(clarify)

   217 apply(erule compat_pat'.cases)

   218 apply(simp_all)

   219 apply(clarify)

   220 apply(erule alpha_trm'.cases)

   221 apply(simp_all)

   222 done

   223 

   224 nominal_datatype trm0 =

   225   Var0 "name"

   226 | App0 "trm0" "trm0"

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

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

   229 and pat0 =

   230   PN0

   231 | PS0 "name"

   232 | PD0 "pat0" "pat0"

   233 binder

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

   235 where 

   236   "f0 PN0 = {}"

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

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

   239 

   240 thm f0_raw.simps

   241 (*thm trm0_pat0_induct

   242 thm trm0_pat0_perm

   243 thm trm0_pat0_fv

   244 thm trm0_pat0_bn*)

   245 

   246 text {* example type schemes *}

   247 

   248 (* does not work yet

   249 nominal_datatype t =

   250   Var "name"

   251 | Fun "t" "t"

   252 

   253 nominal_datatype tyS =

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

   255 *)

   256 

   257 

   258 nominal_datatype t = 

   259   Var "name" 

   260 | Fun "t" "t"

   261 and  tyS = 

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

   263 

   264 (* example 1 from Terms.thy *)

   265 

   266 nominal_datatype trm1 =

   267   Vr1 "name"

   268 | Ap1 "trm1" "trm1"

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

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

   271 and bp1 =

   272   BUnit1

   273 | BV1 "name"

   274 | BP1 "bp1" "bp1"

   275 binder

   276   bv1

   277 where

   278   "bv1 (BUnit1) = {}"

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

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

   281 

   282 thm bv1_raw.simps

   283 

   284 (* example 2 from Terms.thy *)

   285 

   286 nominal_datatype trm2 =

   287   Vr2 "name"

   288 | Ap2 "trm2" "trm2"

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

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

   291 and assign = 

   292   As "name" "trm2"

   293 binder

   294   bv2

   295 where

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

   297 

   298 (* compat should be

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

   300 *)

   301 

   302 

   303 thm fv_trm2_raw_fv_assign_raw.simps[no_vars]

   304 thm alpha_trm2_raw_alpha_assign_raw.intros[no_vars]

   305 

   306 

   307 

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

   309 

   310 nominal_datatype trm3 =

   311   Vr3 "name"

   312 | Ap3 "trm3" "trm3"

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

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

   315 and rassigns3 =

   316   ANil

   317 | ACons "name" "trm3" "rassigns3"

   318 binder

   319   bv3

   320 where

   321   "bv3 ANil = {}"

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

   323 

   324 

   325 (* compat should be

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

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

   328 *)

   329 

   330 (* example 4 from Terms.thy *)

   331 

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

   333    defined fv and defined alpha... *)

   334 nominal_datatype trm4 =

   335   Vr4 "name"

   336 | Ap4 "trm4" "trm4 list"

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

   338 

   339 thm alpha_trm4_raw_alpha_trm4_raw_list.intros[no_vars]

   340 thm fv_trm4_raw_fv_trm4_raw_list.simps[no_vars]

   341 

   342 (* example 5 from Terms.thy *)

   343 

   344 nominal_datatype trm5 =

   345   Vr5 "name"

   346 | Ap5 "trm5" "trm5"

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

   348 and lts =

   349   Lnil

   350 | Lcons "name" "trm5" "lts"

   351 binder

   352   bv5

   353 where

   354   "bv5 Lnil = {}"

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

   356 

   357 (* example 6 from Terms.thy *)

   358 

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

   360 nominal_datatype trm6 =

   361   Vr6 "name"

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

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

   364 binder

   365   bv6

   366 where

   367   "bv6 (Vr6 n) = {}"

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

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

   370 (* example 7 from Terms.thy *)

   371 

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

   373 nominal_datatype trm7 =

   374   Vr7 "name"

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

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

   377 binder 

   378   bv7 

   379 where

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

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

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

   383 

   384 (* example 8 from Terms.thy *)

   385 

   386 nominal_datatype foo8 =

   387   Foo0 "name"

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

   389 and bar8 =

   390   Bar0 "name"

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

   392 binder 

   393   bv8

   394 where

   395   "bv8 (Bar0 x) = {}"

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

   397 

   398 (* example 9 from Terms.thy *)

   399 

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

   401 nominal_datatype lam9 =

   402   Var9 "name"

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

   404 and bla9 =

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

   406 binder

   407   bv9

   408 where

   409   "bv9 (Var9 x) = {}"

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

   411 

   412 (* example from my PHD *)

   413 

   414 atom_decl coname

   415 

   416 nominal_datatype phd =

   417    Ax "name" "coname"

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

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

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

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

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

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

   424 

   425 thm alpha_phd_raw.intros[no_vars]

   426 thm fv_phd_raw.simps[no_vars]

   427 

   428 

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

   430 

   431 nominal_datatype mexp =

   432   Acc "path"

   433 | Stru "body"

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

   435 | FApp "mexp" "path"

   436 | Ascr "mexp" "sexp"

   437 and body =

   438   Empty

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

   440 and defn =  

   441   Type "name" "tyty"

   442 | Dty "name"

   443 | DStru "name" "mexp"

   444 | Val "name" "trmtrm"

   445 and sexp =

   446   Sig sbody

   447 | SFunc "name" "sexp" "sexp"

   448 and sbody = 

   449   SEmpty

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

   451 and spec =

   452   Type1 "name" 

   453 | Type2 "name" "tyty"

   454 | SStru "name" "sexp"

   455 | SVal "name" "tyty"

   456 and tyty =

   457   Tyref1 "name"

   458 | Tyref2 "path" "tyty"

   459 | Fun "tyty" "tyty"

   460 and path =

   461   Sref1 "name"

   462 | Sref2 "path" "name"

   463 and trmtrm =

   464   Tref1 "name"

   465 | Tref2 "path" "name"

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

   467 | App' "trmtrm" "trmtrm"

   468 | Let' "body" "trmtrm"

   469 binder

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

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

   472 where

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

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

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

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

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

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

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

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

   481 

   482 (* core haskell *)

   483 print_theorems

   484 

   485 atom_decl var

   486 atom_decl tvar

   487 

   488 

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

   490 nominal_datatype tkind = 

   491   KStar

   492 | KFun "tkind" "tkind"

   493 and ckind =

   494   CKEq "ty" "ty" 

   495 and ty =

   496   TVar "tvar"

   497 | TC "string"

   498 | TApp "ty" "ty"

   499 | TFun "string" "ty list"

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

   501 | TEq "ty" "ty" "ty"

   502 and co =

   503   CC "string"

   504 | CApp "co" "co"

   505 | CFun "string" "co list"

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

   507 | CEq "co" "co" "co"

   508 | CSym "co"

   509 | CCir "co" "co"

   510 | CLeft "co"

   511 | CRight "co"

   512 | CSim "co"

   513 | CRightc "co"

   514 | CLeftc "co"

   515 | CCoe "co" "co"

   516 

   517 

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

   519 

   520 abbreviation 

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

   522 

   523 nominal_datatype trm =

   524   Var "var"

   525 | C "string"

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

   527 | APP "trm" "ty"

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

   529 | App "trm" "trm"

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

   531 | Case "trm" "assoc list"

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

   533 and assoc = 

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

   535 and pat = 

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

   537 binder

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

   539 where

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

   541 

   542 (*

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

   544   s = s' & 

   545 

   546 *)

   547 

   548 

   549 (*thm bv_raw.simps*)

   550 

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

   552 nominal_datatype exp =

   553   VarP "name"

   554 | AppP "exp" "exp"

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

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

   557 and pat =

   558   PVar "name"

   559 | PUnit

   560 | PPair "pat" "pat"

   561 binder

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

   563 where

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

   565 | "bp (PUnit) = {}"

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

   567 thm alpha_exp_raw_alpha_pat_raw.intros

   568 

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

   570 nominal_datatype exp6 =

   571   EVar name

   572 | EPair exp6 exp6

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

   574 and pat6 =

   575   PVar' name

   576 | PUnit'

   577 | PPair' pat6 pat6

   578 binder

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

   580 where

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

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

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

   584 thm alpha_exp6_raw_alpha_pat6_raw.intros

   585 

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

   587 nominal_datatype exp7 =

   588   EVar name

   589 | EUnit

   590 | EPair exp7 exp7

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

   592 and lrb =

   593   Assign name exp7

   594 and lrbs =

   595   Single lrb

   596 | More lrb lrbs

   597 binder

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

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

   600 where

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

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

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

   604 thm alpha_exp7_raw_alpha_lrb_raw_alpha_lrbs_raw.intros

   605 

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

   607 nominal_datatype exp8 =

   608   EVar name

   609 | EUnit

   610 | EPair exp8 exp8

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

   612 and fnclause =

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

   614 and fnclauses =

   615   S fnclause

   616 | ORs fnclause fnclauses

   617 and lrb8 =

   618   Clause fnclauses

   619 and lrbs8 =

   620   Single lrb8

   621 | More lrb8 lrbs8

   622 and pat8 =

   623   PVar name

   624 | PUnit

   625 | PPair pat8 pat8

   626 binder

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

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

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

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

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

   632 where

   633   "b_lrbs8 (Single l) = b_lrb8 l"

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

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

   636 | "b_pat (PUnit) = {}"

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

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

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

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

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

   642 thm alpha_exp8_raw_alpha_fnclause_raw_alpha_fnclauses_raw_alpha_lrb8_raw_alpha_lrbs8_raw_alpha_pat8_raw.intros

   643 

   644 

   645 

   646 

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

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

   649 

   650 end

   651 

   652 

   653