src/CCL/CCL.ML
changeset 642 0db578095e6a
parent 611 11098f505bfe
child 757 2ca12511676d
equal deleted inserted replaced
641:49fc43cd6a35 642:0db578095e6a
    42 val caseBs = [caseBtrue,caseBfalse,caseBpair,caseBlam,caseBbot];
    42 val caseBs = [caseBtrue,caseBfalse,caseBpair,caseBlam,caseBbot];
    43 
    43 
    44 (*** Termination and Divergence ***)
    44 (*** Termination and Divergence ***)
    45 
    45 
    46 goalw CCL.thy [Trm_def,Dvg_def] "Trm(t) <-> ~ t = bot";
    46 goalw CCL.thy [Trm_def,Dvg_def] "Trm(t) <-> ~ t = bot";
    47 br iff_refl 1;
    47 by (rtac iff_refl 1);
    48 val Trm_iff = result();
    48 val Trm_iff = result();
    49 
    49 
    50 goalw CCL.thy [Trm_def,Dvg_def] "Dvg(t) <-> t = bot";
    50 goalw CCL.thy [Trm_def,Dvg_def] "Dvg(t) <-> t = bot";
    51 br iff_refl 1;
    51 by (rtac iff_refl 1);
    52 val Dvg_iff = result();
    52 val Dvg_iff = result();
    53 
    53 
    54 (*** Constructors are injective ***)
    54 (*** Constructors are injective ***)
    55 
    55 
    56 val prems = goal CCL.thy
    56 val prems = goal CCL.thy
   136                     addSDs (XH_to_Ds ccl_injs);
   136                     addSDs (XH_to_Ds ccl_injs);
   137 
   137 
   138 (****** Facts from gfp Definition of [= and = ******)
   138 (****** Facts from gfp Definition of [= and = ******)
   139 
   139 
   140 val major::prems = goal Set.thy "[| A=B;  a:B <-> P |] ==> a:A <-> P";
   140 val major::prems = goal Set.thy "[| A=B;  a:B <-> P |] ==> a:A <-> P";
   141 brs (prems RL [major RS ssubst]) 1;
   141 by (resolve_tac (prems RL [major RS ssubst]) 1);
   142 val XHlemma1 = result();
   142 val XHlemma1 = result();
   143 
   143 
   144 goal CCL.thy "(P(t,t') <-> Q) --> (<t,t'> : {p.EX t t'.p=<t,t'> &  P(t,t')} <-> Q)";
   144 goal CCL.thy "(P(t,t') <-> Q) --> (<t,t'> : {p.EX t t'.p=<t,t'> &  P(t,t')} <-> Q)";
   145 by (fast_tac ccl_cs 1);
   145 by (fast_tac ccl_cs 1);
   146 val XHlemma2 = result() RS mp;
   146 val XHlemma2 = result() RS mp;
   147 
   147 
   148 (*** Pre-Order ***)
   148 (*** Pre-Order ***)
   149 
   149 
   150 goalw CCL.thy [POgen_def,SIM_def]  "mono(%X.POgen(X))";
   150 goalw CCL.thy [POgen_def,SIM_def]  "mono(%X.POgen(X))";
   151 br monoI 1;
   151 by (rtac monoI 1);
   152 by (safe_tac ccl_cs);
   152 by (safe_tac ccl_cs);
   153 by (REPEAT_SOME (resolve_tac [exI,conjI,refl]));
   153 by (REPEAT_SOME (resolve_tac [exI,conjI,refl]));
   154 by (ALLGOALS (simp_tac ccl_ss));
   154 by (ALLGOALS (simp_tac ccl_ss));
   155 by (ALLGOALS (fast_tac set_cs));
   155 by (ALLGOALS (fast_tac set_cs));
   156 val POgen_mono = result();
   156 val POgen_mono = result();
   157 
   157 
   158 goalw CCL.thy [POgen_def,SIM_def]
   158 goalw CCL.thy [POgen_def,SIM_def]
   159   "<t,t'> : POgen(R) <-> t= bot | (t=true & t'=true)  | (t=false & t'=false) | \
   159   "<t,t'> : POgen(R) <-> t= bot | (t=true & t'=true)  | (t=false & t'=false) | \
   160 \                    (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & <a,a'> : R & <b,b'> : R) | \
   160 \                    (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & <a,a'> : R & <b,b'> : R) | \
   161 \                    (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))";
   161 \                    (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))";
   162 br (iff_refl RS XHlemma2) 1;
   162 by (rtac (iff_refl RS XHlemma2) 1);
   163 val POgenXH = result();
   163 val POgenXH = result();
   164 
   164 
   165 goal CCL.thy
   165 goal CCL.thy
   166   "t [= t' <-> t=bot | (t=true & t'=true) | (t=false & t'=false) | \
   166   "t [= t' <-> t=bot | (t=true & t'=true) | (t=false & t'=false) | \
   167 \                    (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & a [= a' & b [= b') | \
   167 \                    (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & a [= a' & b [= b') | \
   168 \                    (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.f(x) [= f'(x)))";
   168 \                    (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.f(x) [= f'(x)))";
   169 by (simp_tac (ccl_ss addsimps [PO_iff]) 1);
   169 by (simp_tac (ccl_ss addsimps [PO_iff]) 1);
   170 br (rewrite_rule [POgen_def,SIM_def] 
   170 br (rewrite_rule [POgen_def,SIM_def] 
   171                  (POgen_mono RS (PO_def RS def_gfp_Tarski) RS XHlemma1)) 1;
   171                  (POgen_mono RS (PO_def RS def_gfp_Tarski) RS XHlemma1)) 1;
   172 br (iff_refl RS XHlemma2) 1;
   172 by (rtac (iff_refl RS XHlemma2) 1);
   173 val poXH = result();
   173 val poXH = result();
   174 
   174 
   175 goal CCL.thy "bot [= b";
   175 goal CCL.thy "bot [= b";
   176 br (poXH RS iffD2) 1;
   176 by (rtac (poXH RS iffD2) 1);
   177 by (simp_tac ccl_ss 1);
   177 by (simp_tac ccl_ss 1);
   178 val po_bot = result();
   178 val po_bot = result();
   179 
   179 
   180 goal CCL.thy "a [= bot --> a=bot";
   180 goal CCL.thy "a [= bot --> a=bot";
   181 br impI 1;
   181 by (rtac impI 1);
   182 bd (poXH RS iffD1) 1;
   182 by (dtac (poXH RS iffD1) 1);
   183 be rev_mp 1;
   183 by (etac rev_mp 1);
   184 by (simp_tac ccl_ss 1);
   184 by (simp_tac ccl_ss 1);
   185 val bot_poleast = result() RS mp;
   185 val bot_poleast = result() RS mp;
   186 
   186 
   187 goal CCL.thy "<a,b> [= <a',b'> <->  a [= a' & b [= b'";
   187 goal CCL.thy "<a,b> [= <a',b'> <->  a [= a' & b [= b'";
   188 br (poXH RS iff_trans) 1;
   188 by (rtac (poXH RS iff_trans) 1);
   189 by (simp_tac ccl_ss 1);
   189 by (simp_tac ccl_ss 1);
   190 by (fast_tac ccl_cs 1);
   190 by (fast_tac ccl_cs 1);
   191 val po_pair = result();
   191 val po_pair = result();
   192 
   192 
   193 goal CCL.thy "lam x.f(x) [= lam x.f'(x) <-> (ALL x. f(x) [= f'(x))";
   193 goal CCL.thy "lam x.f(x) [= lam x.f'(x) <-> (ALL x. f(x) [= f'(x))";
   194 br (poXH RS iff_trans) 1;
   194 by (rtac (poXH RS iff_trans) 1);
   195 by (simp_tac ccl_ss 1);
   195 by (simp_tac ccl_ss 1);
   196 by (REPEAT (ares_tac [iffI,allI] 1 ORELSE eresolve_tac [exE,conjE] 1));
   196 by (REPEAT (ares_tac [iffI,allI] 1 ORELSE eresolve_tac [exE,conjE] 1));
   197 by (asm_simp_tac ccl_ss 1);
   197 by (asm_simp_tac ccl_ss 1);
   198 by (fast_tac ccl_cs 1);
   198 by (fast_tac ccl_cs 1);
   199 val po_lam = result();
   199 val po_lam = result();
   201 val ccl_porews = [po_bot,po_pair,po_lam];
   201 val ccl_porews = [po_bot,po_pair,po_lam];
   202 
   202 
   203 val [p1,p2,p3,p4,p5] = goal CCL.thy
   203 val [p1,p2,p3,p4,p5] = goal CCL.thy
   204     "[| t [= t';  a [= a';  b [= b';  !!x y.c(x,y) [= c'(x,y); \
   204     "[| t [= t';  a [= a';  b [= b';  !!x y.c(x,y) [= c'(x,y); \
   205 \       !!u.d(u) [= d'(u) |] ==> case(t,a,b,c,d) [= case(t',a',b',c',d')";
   205 \       !!u.d(u) [= d'(u) |] ==> case(t,a,b,c,d) [= case(t',a',b',c',d')";
   206 br (p1 RS po_cong RS po_trans) 1;
   206 by (rtac (p1 RS po_cong RS po_trans) 1);
   207 br (p2 RS po_cong RS po_trans) 1;
   207 by (rtac (p2 RS po_cong RS po_trans) 1);
   208 br (p3 RS po_cong RS po_trans) 1;
   208 by (rtac (p3 RS po_cong RS po_trans) 1);
   209 br (p4 RS po_abstractn RS po_abstractn RS po_cong RS po_trans) 1;
   209 by (rtac (p4 RS po_abstractn RS po_abstractn RS po_cong RS po_trans) 1);
   210 by (res_inst_tac [("f1","%d.case(t',a',b',c',d)")] 
   210 by (res_inst_tac [("f1","%d.case(t',a',b',c',d)")] 
   211                (p5 RS po_abstractn RS po_cong RS po_trans) 1);
   211                (p5 RS po_abstractn RS po_cong RS po_trans) 1);
   212 br po_refl 1;
   212 by (rtac po_refl 1);
   213 val case_pocong = result();
   213 val case_pocong = result();
   214 
   214 
   215 val [p1,p2] = goalw CCL.thy ccl_data_defs
   215 val [p1,p2] = goalw CCL.thy ccl_data_defs
   216     "[| f [= f';  a [= a' |] ==> f ` a [= f' ` a'";
   216     "[| f [= f';  a [= a' |] ==> f ` a [= f' ` a'";
   217 by (REPEAT (ares_tac [po_refl,case_pocong,p1,p2 RS po_cong] 1));
   217 by (REPEAT (ares_tac [po_refl,case_pocong,p1,p2 RS po_cong] 1));
   218 val apply_pocong = result();
   218 val apply_pocong = result();
   219 
   219 
   220 
   220 
   221 val prems = goal CCL.thy "~ lam x.b(x) [= bot";
   221 val prems = goal CCL.thy "~ lam x.b(x) [= bot";
   222 br notI 1;
   222 by (rtac notI 1);
   223 bd bot_poleast 1;
   223 by (dtac bot_poleast 1);
   224 be (distinctness RS notE) 1;
   224 by (etac (distinctness RS notE) 1);
   225 val npo_lam_bot = result();
   225 val npo_lam_bot = result();
   226 
   226 
   227 val eq1::eq2::prems = goal CCL.thy
   227 val eq1::eq2::prems = goal CCL.thy
   228     "[| x=a;  y=b;  x[=y |] ==> a[=b";
   228     "[| x=a;  y=b;  x[=y |] ==> a[=b";
   229 br (eq1 RS subst) 1;
   229 by (rtac (eq1 RS subst) 1);
   230 br (eq2 RS subst) 1;
   230 by (rtac (eq2 RS subst) 1);
   231 brs prems 1;
   231 by (resolve_tac prems 1);
   232 val po_lemma = result();
   232 val po_lemma = result();
   233 
   233 
   234 goal CCL.thy "~ <a,b> [= lam x.f(x)";
   234 goal CCL.thy "~ <a,b> [= lam x.f(x)";
   235 br notI 1;
   235 by (rtac notI 1);
   236 br (npo_lam_bot RS notE) 1;
   236 by (rtac (npo_lam_bot RS notE) 1);
   237 be (case_pocong RS (caseBlam RS (caseBpair RS po_lemma))) 1;
   237 by (etac (case_pocong RS (caseBlam RS (caseBpair RS po_lemma))) 1);
   238 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1));
   238 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1));
   239 val npo_pair_lam = result();
   239 val npo_pair_lam = result();
   240 
   240 
   241 goal CCL.thy "~ lam x.f(x) [= <a,b>";
   241 goal CCL.thy "~ lam x.f(x) [= <a,b>";
   242 br notI 1;
   242 by (rtac notI 1);
   243 br (npo_lam_bot RS notE) 1;
   243 by (rtac (npo_lam_bot RS notE) 1);
   244 be (case_pocong RS (caseBpair RS (caseBlam RS po_lemma))) 1;
   244 by (etac (case_pocong RS (caseBpair RS (caseBlam RS po_lemma))) 1);
   245 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1));
   245 by (REPEAT (resolve_tac [po_refl,npo_lam_bot] 1));
   246 val npo_lam_pair = result();
   246 val npo_lam_pair = result();
   247 
   247 
   248 fun mk_thm s = prove_goal CCL.thy s (fn _ => 
   248 fun mk_thm s = prove_goal CCL.thy s (fn _ => 
   249                           [rtac notI 1,dtac case_pocong 1,etac rev_mp 5,
   249                           [rtac notI 1,dtac case_pocong 1,etac rev_mp 5,
   258             "~ false [= lam x.f(x)","~ lam x.f(x) [= false"];
   258             "~ false [= lam x.f(x)","~ lam x.f(x) [= false"];
   259 
   259 
   260 (* Coinduction for [= *)
   260 (* Coinduction for [= *)
   261 
   261 
   262 val prems = goal CCL.thy "[|  <t,u> : R;  R <= POgen(R) |] ==> t [= u";
   262 val prems = goal CCL.thy "[|  <t,u> : R;  R <= POgen(R) |] ==> t [= u";
   263 br (PO_def RS def_coinduct RS (PO_iff RS iffD2)) 1;
   263 by (rtac (PO_def RS def_coinduct RS (PO_iff RS iffD2)) 1);
   264 by (REPEAT (ares_tac prems 1));
   264 by (REPEAT (ares_tac prems 1));
   265 val po_coinduct = result();
   265 val po_coinduct = result();
   266 
   266 
   267 fun po_coinduct_tac s i = res_inst_tac [("R",s)] po_coinduct i;
   267 fun po_coinduct_tac s i = res_inst_tac [("R",s)] po_coinduct i;
   268 
   268 
   269 (*************** EQUALITY *******************)
   269 (*************** EQUALITY *******************)
   270 
   270 
   271 goalw CCL.thy [EQgen_def,SIM_def]  "mono(%X.EQgen(X))";
   271 goalw CCL.thy [EQgen_def,SIM_def]  "mono(%X.EQgen(X))";
   272 br monoI 1;
   272 by (rtac monoI 1);
   273 by (safe_tac set_cs);
   273 by (safe_tac set_cs);
   274 by (REPEAT_SOME (resolve_tac [exI,conjI,refl]));
   274 by (REPEAT_SOME (resolve_tac [exI,conjI,refl]));
   275 by (ALLGOALS (simp_tac ccl_ss));
   275 by (ALLGOALS (simp_tac ccl_ss));
   276 by (ALLGOALS (fast_tac set_cs));
   276 by (ALLGOALS (fast_tac set_cs));
   277 val EQgen_mono = result();
   277 val EQgen_mono = result();
   279 goalw CCL.thy [EQgen_def,SIM_def]
   279 goalw CCL.thy [EQgen_def,SIM_def]
   280   "<t,t'> : EQgen(R) <-> (t=bot & t'=bot)  | (t=true & t'=true)  | \
   280   "<t,t'> : EQgen(R) <-> (t=bot & t'=bot)  | (t=true & t'=true)  | \
   281 \                                            (t=false & t'=false) | \
   281 \                                            (t=false & t'=false) | \
   282 \                (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & <a,a'> : R & <b,b'> : R) | \
   282 \                (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & <a,a'> : R & <b,b'> : R) | \
   283 \                (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))";
   283 \                (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : R))";
   284 br (iff_refl RS XHlemma2) 1;
   284 by (rtac (iff_refl RS XHlemma2) 1);
   285 val EQgenXH = result();
   285 val EQgenXH = result();
   286 
   286 
   287 goal CCL.thy
   287 goal CCL.thy
   288   "t=t' <-> (t=bot & t'=bot)  | (t=true & t'=true)  | (t=false & t'=false) | \
   288   "t=t' <-> (t=bot & t'=bot)  | (t=true & t'=true)  | (t=false & t'=false) | \
   289 \                    (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & a=a' & b=b') | \
   289 \                    (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & a=a' & b=b') | \
   290 \                    (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.f(x)=f'(x)))";
   290 \                    (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.f(x)=f'(x)))";
   291 by (subgoal_tac
   291 by (subgoal_tac
   292   "<t,t'> : EQ <-> (t=bot & t'=bot)  | (t=true & t'=true) | (t=false & t'=false) | \
   292   "<t,t'> : EQ <-> (t=bot & t'=bot)  | (t=true & t'=true) | (t=false & t'=false) | \
   293 \             (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & <a,a'> : EQ & <b,b'> : EQ) | \
   293 \             (EX a a' b b'.t=<a,b> &  t'=<a',b'>  & <a,a'> : EQ & <b,b'> : EQ) | \
   294 \             (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : EQ))" 1);
   294 \             (EX f f'.t=lam x.f(x) &  t'=lam x.f'(x) & (ALL x.<f(x),f'(x)> : EQ))" 1);
   295 be rev_mp 1;
   295 by (etac rev_mp 1);
   296 by (simp_tac (CCL_ss addsimps [EQ_iff RS iff_sym]) 1);
   296 by (simp_tac (CCL_ss addsimps [EQ_iff RS iff_sym]) 1);
   297 br (rewrite_rule [EQgen_def,SIM_def]
   297 br (rewrite_rule [EQgen_def,SIM_def]
   298                  (EQgen_mono RS (EQ_def RS def_gfp_Tarski) RS XHlemma1)) 1;
   298                  (EQgen_mono RS (EQ_def RS def_gfp_Tarski) RS XHlemma1)) 1;
   299 br (iff_refl RS XHlemma2) 1;
   299 by (rtac (iff_refl RS XHlemma2) 1);
   300 val eqXH = result();
   300 val eqXH = result();
   301 
   301 
   302 val prems = goal CCL.thy "[|  <t,u> : R;  R <= EQgen(R) |] ==> t = u";
   302 val prems = goal CCL.thy "[|  <t,u> : R;  R <= EQgen(R) |] ==> t = u";
   303 br (EQ_def RS def_coinduct RS (EQ_iff RS iffD2)) 1;
   303 by (rtac (EQ_def RS def_coinduct RS (EQ_iff RS iffD2)) 1);
   304 by (REPEAT (ares_tac prems 1));
   304 by (REPEAT (ares_tac prems 1));
   305 val eq_coinduct = result();
   305 val eq_coinduct = result();
   306 
   306 
   307 val prems = goal CCL.thy 
   307 val prems = goal CCL.thy 
   308     "[|  <t,u> : R;  R <= EQgen(lfp(%x.EQgen(x) Un R Un EQ)) |] ==> t = u";
   308     "[|  <t,u> : R;  R <= EQgen(lfp(%x.EQgen(x) Un R Un EQ)) |] ==> t = u";
   309 br (EQ_def RS def_coinduct3 RS (EQ_iff RS iffD2)) 1;
   309 by (rtac (EQ_def RS def_coinduct3 RS (EQ_iff RS iffD2)) 1);
   310 by (REPEAT (ares_tac (EQgen_mono::prems) 1));
   310 by (REPEAT (ares_tac (EQgen_mono::prems) 1));
   311 val eq_coinduct3 = result();
   311 val eq_coinduct3 = result();
   312 
   312 
   313 fun eq_coinduct_tac s i = res_inst_tac [("R",s)] eq_coinduct i;
   313 fun eq_coinduct_tac s i = res_inst_tac [("R",s)] eq_coinduct i;
   314 fun eq_coinduct3_tac s i = res_inst_tac [("R",s)] eq_coinduct3 i;
   314 fun eq_coinduct3_tac s i = res_inst_tac [("R",s)] eq_coinduct3 i;