--- a/Nominal/Ex/PaperTest.thy	Tue Feb 19 05:38:46 2013 +0000
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,303 +0,0 @@
-theory PaperTest
-imports "../Nominal2"
-begin
-
-atom_decl name 
-
-datatype trm = 
-  Const "string"
-| Var "name"
-| App "trm" "trm"
-| Lam "name" "trm"  ("Lam [_]. _" [100, 100] 100)
-
-fun
-  subst :: "trm \<Rightarrow> name \<Rightarrow> name \<Rightarrow> trm"  ("_[_::=_]" [100,100,100] 100)
-where
-  "(Var x)[y::=p] = (if x=y then (App (App (Const ''unpermute'') (Var p)) (Var x)) else (Var x))"
-| "(App t\<^isub>1 t\<^isub>2)[y::=p] = App (t\<^isub>1[y::=p]) (t\<^isub>2[y::=p])"
-| "(Lam [x].t)[y::=p] = (if x=y then (Lam [x].t) else Lam [x].(t[y::=p]))"
-| "(Const n)[y::=p] = Const n"
-
-datatype utrm = 
-  UConst "string"
-| UnPermute "name" "name"
-| UVar "name"
-| UApp "utrm" "utrm"
-| ULam "name" "utrm"  ("ULam [_]. _" [100, 100] 100)
-
-fun
-  usubst :: "utrm \<Rightarrow> name \<Rightarrow> name \<Rightarrow> utrm"  ("_[_:::=_]" [100,100,100] 100)
-where
-  "(UVar x)[y:::=p] = (if x=y then UnPermute p x else (UVar x))"
-| "(UApp t\<^isub>1 t\<^isub>2)[y:::=p] = UApp (t\<^isub>1[y:::=p]) (t\<^isub>2[y:::=p])"
-| "(ULam [x].t)[y:::=p] = (if x=y then (ULam [x].t) else ULam [x].(t[y:::=p]))"
-| "(UConst n)[y:::=p] = UConst n"
-| "(UnPermute x q)[y:::=p] = UnPermute x q"
-
-function
-  ss :: "trm \<Rightarrow> nat"
-where
-  "ss (Var x) = 1"
-| "ss (Const s) = 1"
-| "ss (Lam [x].t) = 1 + ss t"
-| "ss (App (App (Const ''unpermute'') (Var p)) (Var x)) = 1"
-| "\<not>(\<exists>p x. t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x)) \<Longrightarrow> ss (App t1 t2) = 1 + ss t1 + ss t2"
-defer
-apply(simp_all)
-apply(auto)[1]
-apply(case_tac x)
-apply(simp_all)
-apply(auto)
-apply(blast)
-done
-
-termination
-  apply(relation "measure (\<lambda>t. size t)")
-  apply(simp_all)
-  done
-
-fun
-  uss :: "utrm \<Rightarrow> nat"
-where
-  "uss (UVar x) = 1"
-| "uss (UConst s) = 1"
-| "uss (ULam [x].t) = 1 + uss t"
-| "uss (UnPermute x y) = 1"
-| "uss (UApp t1 t2) = 1 + uss t1 + uss t2"
-
-lemma trm_uss:
-  shows "uss (t[x:::=p]) = uss t"
-apply(induct rule: uss.induct)
-apply(simp_all)
-done
-
-inductive
-  ufree :: "utrm \<Rightarrow> bool"
-where
-  "ufree (UVar x)"
-| "s \<noteq> ''unpermute'' \<Longrightarrow> ufree (UConst s)"
-| "ufree t \<Longrightarrow> ufree (ULam [x].t)"
-| "ufree (UnPermute x y)"
-| "\<lbrakk>ufree t1; ufree t2\<rbrakk> \<Longrightarrow> ufree (UApp t1 t2)"
-
-fun
-  trans :: "utrm \<Rightarrow> trm" ("\<parallel>_\<parallel>" [100] 100)
-where
-  "\<parallel>(UVar x)\<parallel> = Var x"
-| "\<parallel>(UConst x)\<parallel> = Const x"
-| "\<parallel>(UnPermute p x)\<parallel> = (App (App (Const ''unpermute'') (Var p)) (Var x))"
-| "\<parallel>(ULam [x].t)\<parallel> = Lam [x].(\<parallel>t\<parallel>)"
-| "\<parallel>(UApp t1 t2)\<parallel> = App (\<parallel>t1\<parallel>) (\<parallel>t2\<parallel>)"
-
-function
-  utrans :: "trm \<Rightarrow> utrm" ("\<lparr>_\<rparr>" [90] 100)
-where
-  "\<lparr>Var x\<rparr> = UVar x"
-| "\<lparr>Const x\<rparr> = UConst x"
-| "\<lparr>Lam [x].t\<rparr> = ULam [x].\<lparr>t\<rparr>"
-| "\<lparr>App (App (Const ''unpermute'') (Var p)) (Var x)\<rparr> = UnPermute p x"
-| "\<not>(\<exists>p x. t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x)) \<Longrightarrow> \<lparr>App t1 t2\<rparr> = UApp (\<lparr>t1\<rparr>) (\<lparr>t2\<rparr>)"
-defer
-apply(simp_all)
-apply(auto)[1]
-apply(case_tac x)
-apply(simp_all)
-apply(auto)
-apply(blast)
-done
-
-termination
-  apply(relation "measure (\<lambda>t. size t)")
-  apply(simp_all)
-  done
-
-
-lemma elim1:
-  "ufree t \<Longrightarrow> \<parallel>t\<parallel> \<noteq>(Const ''unpermute'')"
-apply(erule ufree.induct)
-apply(auto)
-done
-
-lemma elim2:
-  "ufree t \<Longrightarrow> \<not>(\<exists>p. \<parallel>t\<parallel> = App (Const ''unpermute'') (Var p))"
-apply(erule ufree.induct)
-apply(auto dest: elim1)
-done
-
-lemma ss1:
-  "ufree t \<Longrightarrow> uss t = ss (\<parallel>t\<parallel>)"
-apply(erule ufree.induct)
-apply(simp_all)
-apply(subst ss.simps)
-apply(auto)
-apply(drule elim2)
-apply(auto)
-done
-
-lemma trans1:
-  shows "\<parallel>\<lparr>t\<rparr>\<parallel> = t"
-apply(induct t)
-apply(simp)
-apply(simp)
-prefer 2
-apply(simp)
-apply(case_tac "(\<exists>p x. t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x))")
-apply(erule exE)+
-apply(simp)
-apply(simp)
-done
-
-lemma trans_subst:
-  shows "\<lparr>t[x ::= p]\<rparr> = \<lparr>t\<rparr>[x :::= p]"
-apply(induct rule: subst.induct)
-apply(simp)
-defer
-apply(simp)
-apply(simp)
-apply(simp)
-apply(case_tac "(t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x))")
-apply(erule exE)+
-apply(simp only:)
-apply(subst utrans.simps)
-apply(subst usubst.simps)
-apply(case_tac "xa = x")
-apply(subst (asm) subst.simps)
-apply(simp only:)
-apply(subst (asm) utrans.simps)
-apply(simp only: usubst.simps)
-apply(simp)
-apply(auto)[1]
-apply(case_tac "pa = x")
-apply(simp)
-prefer 2
-apply(simp)
-apply(simp)
-done
-
-lemma 
-  "ss (t[x ::= p]) = ss t"
-apply(subst (2) trans1[symmetric])
-apply(subst ss1[symmetric])
-
-
-fun
-  fr :: "trm \<Rightarrow> name set"
-where
-  "fr (Var x) = {x}"
-| "fr (Const s) = {}"
-| "fr (Lam [x].t) = fr t - {x}"
-| "fr (App t1 t2) = fr t1 \<union> fr t2"
-
-function
-  sfr :: "trm \<Rightarrow> name set"
-where
-  "sfr (Var x) = {}"
-| "sfr (Const s) = {}"
-| "sfr (Lam [x].t) = sfr t - {x}"
-| "sfr (App (App (Const ''unpermute'') (Var p)) (Var x)) = {p, x}"
-| "\<not>(\<exists>p x. t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x)) \<Longrightarrow> sfr (App t1 t2) = sfr t1 \<union> sfr t2"
-defer
-apply(simp_all)
-apply(auto)[1]
-apply(case_tac x)
-apply(simp_all)
-apply(auto)
-apply(blast)
-done
-
-termination
-  apply(relation "measure (\<lambda>t. size t)")
-  apply(simp_all)
-  done
-
-function
-  ss :: "trm \<Rightarrow> nat"
-where
-  "ss (Var x) = 1"
-| "ss (Const s) = 1"
-| "ss (Lam [x].t) = 1 + ss t"
-| "ss (App (App (Const ''unpermute'') (Var p)) (Var x)) = 1"
-| "\<not>(\<exists>p x. t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x)) \<Longrightarrow> ss (App t1 t2) = 1 + ss t1 + ss t2"
-defer
-apply(simp_all)
-apply(auto)[1]
-apply(case_tac x)
-apply(simp_all)
-apply(auto)
-apply(blast)
-done 
-
-termination
-  apply(relation "measure (\<lambda>t. size t)")
-  apply(simp_all)
-  done
-
-inductive
-  improper :: "trm \<Rightarrow> bool"
-where
-  "improper (App (App (Const ''unpermute'') (Var p)) (Var x))"
-| "improper p x t \<Longrightarrow> improper p x (Lam [y].t)"
-| "\<lbrakk>improper p x t1; improper p x t2\<rbrakk> \<Longrightarrow> improper p x (App t1 t2)"
-
-lemma trm_ss:
-  shows "\<not>improper p x t \<Longrightarrow> ss (t[x::= p]) = ss t"
-apply(induct rule: ss.induct)
-apply(simp)
-apply(simp)
-apply(simp)
-apply(auto)[1]
-apply(case_tac "improper p x t")
-apply(drule improper.intros(2))
-apply(blast)
-apply(simp)
-using improper.intros(1)
-apply(blast)
-apply(erule contrapos_pn)
-thm contrapos_np
-apply(simp)
-apply(auto)[1]
-apply(simp)
-apply(erule disjE)
-apply(erule conjE)+
-apply(subst ss.simps)
-apply(simp)
-apply(rule disjI1)
-apply(rule allI)
-apply(rule notI)
-
-apply(simp del: ss.simps)
-apply(erule disjE)
-apply(subst ss.simps)
-apply(simp)
-apply(simp only: subst.simps)
-apply(subst ss.simps)
-apply(simp del: ss.simps)
-apply(rule conjI)
-apply(rule impI)
-apply(erule conjE)
-apply(erule exE)+
-apply(subst ss.simps)
-apply(simp)
-apply(auto)[1]
-apply(simp add: if_splits)
-apply()
-
-function
-  simp :: "name \<Rightarrow> trm \<Rightarrow> trm"
-where
-  "simp p (Const c) = (Const c)"
-| "simp p (Var x) = App (App (Const ''permute'') (Var p)) (Var x)"
-| "simp p (App t1 t2) = (if ((\<exists>x. t1 = App (Const ''unpermute'') (Var p) \<and> t2 = (Var x))) 
-                         then t2
-                         else App (simp p t1) (simp p t2))"
-| "simp p (Lam [x].t) = Lam [x]. (simp p (t[x ::= p]))"
-apply(pat_completeness)
-apply(simp_all)
-apply(auto)
-done
-
-termination
-apply(relation "measure (\<lambda>(_, t). size t)")
-apply(simp_all)
-
-end
\ No newline at end of file