theory Test

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

begin

atom_decl name

ML {* val _ = recursive := false *}

nominal_datatype lm =

  Vr "name"

| Ap "lm" "lm"

| Lm x::"name" l::"lm"  bind x in l

lemmas supp_fn' = lm.fv[simplified lm.supp]

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>atom name \<sharp> c; \<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))")

    defer

    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)

    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 del: lm.perm)

    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)

    apply(rule a3)

    apply(simp add: fresh_Pair)

    apply(drule_tac x="((p \<bullet> name) \<leftrightarrow> new) + p" in meta_spec)

    apply(simp)

    done

  then have "P c (0 \<bullet> lm)" by blast

  then show "P c lm" by simp

qed

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>atom name \<sharp> c; \<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)

    thm at_set_avoiding

    apply(subgoal_tac "\<exists>q. (q \<bullet> {p \<bullet> atom name}) \<sharp>* c \<and> supp (p \<bullet> Lm name lm) \<sharp>* q")

    apply(erule exE)

    apply(rule_tac t="p \<bullet> Lm name lm" and 

                   s="q \<bullet> p \<bullet> Lm name lm" in subst)

    defer

    apply(simp add: lm.perm)

    apply(rule a3)

    apply(simp add: eqvts fresh_star_def)

    apply(drule_tac x="q + p" in meta_spec)

    apply(simp)

    sorry

  then have "P c (0 \<bullet> lm)" by blast

  then show "P c lm" by simp

qed

text {* example 1, equivalent to example 2 from Terms *}

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.supp

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

thm lam_bp.fv[simplified lam_bp.supp]

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

thm lam'_bp'.fv[simplified lam'_bp'.supp]

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

thm trm'_pat'.fv[simplified trm'_pat'.supp]

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

thm trm0_pat0.fv[simplified trm0_pat0.supp,no_vars]

text {* example type schemes *}

nominal_datatype t =

  VarTS "name"

| FunTS "t" "t"

and  tyS =

  All xs::"name fset" 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

thm t_tyS.fv[simplified t_tyS.supp]

ML {* Sign.of_sort @{theory} (@{typ t}, @{sort fs}) *}

ML {* Sign.of_sort @{theory} (@{typ tyS}, @{sort fs}) *}

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

thm trm1_bp1.fv[simplified trm1_bp1.supp]

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

thm trm3_rassigns3.fv[simplified trm3_rassigns3.supp]

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

thm trm5_lts.fv[simplified trm5_lts.supp]

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

thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.supp

thm mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.fv[simplified mexp_body_defn_sexp_sbody_spec_tyty_path_trmtrm.supp]

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

thm phd.fv[simplified phd.supp]

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

thm exp_pat3.fv[simplified exp_pat3.supp]

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