src/CCL/Fix.ML
changeset 8 c3d2c6dcf3f0
parent 0 a5a9c433f639
child 442 13ac1fd0a14d
equal deleted inserted replaced
7:268f93ab3bc4 8:c3d2c6dcf3f0
     6 For fix.thy.
     6 For fix.thy.
     7 *)
     7 *)
     8 
     8 
     9 open Fix;
     9 open Fix;
    10 
    10 
    11 val prems = goalw Fix.thy [INCL_def]
       
    12      "[| !!x.P(x) <-> Q(x) |] ==> INCL(%x.P(x)) <-> INCL(%x.Q(x))";
       
    13 by (REPEAT (ares_tac ([refl] @ FOL_congs @ set_congs @ prems) 1));
       
    14 val INCL_cong = result();
       
    15 
       
    16 val fix_congs = [INCL_cong] @ ccl_mk_congs Fix.thy ["napply"];
       
    17 
       
    18 (*** Fixed Point Induction ***)
    11 (*** Fixed Point Induction ***)
    19 
    12 
    20 val [base,step,incl] = goalw Fix.thy [INCL_def]
    13 val [base,step,incl] = goalw Fix.thy [INCL_def]
    21     "[| P(bot);  !!x.P(x) ==> P(f(x));  INCL(P) |] ==> P(fix(f))";
    14     "[| P(bot);  !!x.P(x) ==> P(f(x));  INCL(P) |] ==> P(fix(f))";
    22 br (incl RS spec RS mp) 1;
    15 br (incl RS spec RS mp) 1;
    23 by (rtac (Nat_ind RS ballI) 1 THEN atac 1);
    16 by (rtac (Nat_ind RS ballI) 1 THEN atac 1);
    24 by (ALLGOALS (SIMP_TAC term_ss));
    17 by (ALLGOALS (simp_tac term_ss));
    25 by (REPEAT (ares_tac [base,step] 1));
    18 by (REPEAT (ares_tac [base,step] 1));
    26 val fix_ind = result();
    19 val fix_ind = result();
    27 
    20 
    28 (*** Inclusive Predicates ***)
    21 (*** Inclusive Predicates ***)
    29 
    22 
    46 val incl::prems = goal Fix.thy
    39 val incl::prems = goal Fix.thy
    47      "[| INCL(P);  (ALL n:Nat.P(f^n`bot))-->P(fix(f)) ==> R |] ==> R";
    40      "[| INCL(P);  (ALL n:Nat.P(f^n`bot))-->P(fix(f)) ==> R |] ==> R";
    48 by (fast_tac (term_cs addIs ([incl RS inclD] @ prems)) 1);
    41 by (fast_tac (term_cs addIs ([incl RS inclD] @ prems)) 1);
    49 val inclE = result();
    42 val inclE = result();
    50 
    43 
    51 val fix_ss = term_ss addcongs fix_congs;
       
    52 
    44 
    53 (*** Lemmas for Inclusive Predicates ***)
    45 (*** Lemmas for Inclusive Predicates ***)
    54 
    46 
    55 goal Fix.thy "INCL(%x.~ a(x) [= t)";
    47 goal Fix.thy "INCL(%x.~ a(x) [= t)";
    56 br inclI 1;
    48 br inclI 1;
    74 val prems = goal Fix.thy "[| !!a.a:A ==> INCL(P(a)) |] ==> INCL(%x.ALL a:A.P(a,x))";
    66 val prems = goal Fix.thy "[| !!a.a:A ==> INCL(P(a)) |] ==> INCL(%x.ALL a:A.P(a,x))";
    75 by (fast_tac (set_cs addSIs ([inclI] @ (prems RL [inclD]))) 1);;
    67 by (fast_tac (set_cs addSIs ([inclI] @ (prems RL [inclD]))) 1);;
    76 val ball_INCL = result();
    68 val ball_INCL = result();
    77 
    69 
    78 goal Fix.thy "INCL(%x.a(x) = b(x)::'a::prog)";
    70 goal Fix.thy "INCL(%x.a(x) = b(x)::'a::prog)";
    79 by (SIMP_TAC (fix_ss addrews [eq_iff]) 1);
    71 by (simp_tac (term_ss addsimps [eq_iff]) 1);
    80 by (REPEAT (resolve_tac [conj_INCL,po_INCL] 1));
    72 by (REPEAT (resolve_tac [conj_INCL,po_INCL] 1));
    81 val eq_INCL = result();
    73 val eq_INCL = result();
    82 
    74 
    83 (*** Derivation of Reachability Condition ***)
    75 (*** Derivation of Reachability Condition ***)
    84 
    76 
    87 goal Fix.thy "idgen(fix(idgen)) = fix(idgen)";
    79 goal Fix.thy "idgen(fix(idgen)) = fix(idgen)";
    88 br (fixB RS sym) 1;
    80 br (fixB RS sym) 1;
    89 val fix_idgenfp = result();
    81 val fix_idgenfp = result();
    90 
    82 
    91 goalw Fix.thy [idgen_def] "idgen(lam x.x) = lam x.x";
    83 goalw Fix.thy [idgen_def] "idgen(lam x.x) = lam x.x";
    92 by (SIMP_TAC term_ss 1);
    84 by (simp_tac term_ss 1);
    93 br (term_case RS allI) 1;
    85 br (term_case RS allI) 1;
    94 by (ALLGOALS (SIMP_TAC term_ss));
    86 by (ALLGOALS (simp_tac term_ss));
    95 val id_idgenfp = result();
    87 val id_idgenfp = result();
    96 
    88 
    97 (* All fixed points are lam-expressions *)
    89 (* All fixed points are lam-expressions *)
    98 
    90 
    99 val [prem] = goal Fix.thy "idgen(d) = d ==> d = lam x.?f(x)";
    91 val [prem] = goal Fix.thy "idgen(d) = d ==> d = lam x.?f(x)";
   104 
    96 
   105 (* Lemmas for rewriting fixed points of idgen *)
    97 (* Lemmas for rewriting fixed points of idgen *)
   106 
    98 
   107 val prems = goalw Fix.thy [idgen_def] 
    99 val prems = goalw Fix.thy [idgen_def] 
   108     "[| a = b;  a ` t = u |] ==> b ` t = u";
   100     "[| a = b;  a ` t = u |] ==> b ` t = u";
   109 by (SIMP_TAC (term_ss addrews (prems RL [sym])) 1);
   101 by (simp_tac (term_ss addsimps (prems RL [sym])) 1);
   110 val l_lemma= result();
   102 val l_lemma= result();
   111 
   103 
   112 val idgen_lemmas =
   104 val idgen_lemmas =
   113     let fun mk_thm s = prove_goalw Fix.thy [idgen_def] s
   105     let fun mk_thm s = prove_goalw Fix.thy [idgen_def] s
   114            (fn [prem] => [rtac (prem RS l_lemma) 1,SIMP_TAC term_ss 1])
   106            (fn [prem] => [rtac (prem RS l_lemma) 1,simp_tac term_ss 1])
   115     in map mk_thm
   107     in map mk_thm
   116           [    "idgen(d) = d ==> d ` bot = bot",
   108           [    "idgen(d) = d ==> d ` bot = bot",
   117                "idgen(d) = d ==> d ` true = true",
   109                "idgen(d) = d ==> d ` true = true",
   118                "idgen(d) = d ==> d ` false = false",
   110                "idgen(d) = d ==> d ` false = false",
   119                "idgen(d) = d ==> d ` <a,b> = <d ` a,d ` b>",
   111                "idgen(d) = d ==> d ` <a,b> = <d ` a,d ` b>",
   139     "idgen(d) = d ==> \
   131     "idgen(d) = d ==> \
   140 \      {p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t & b = d ` t)} <=   \
   132 \      {p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t & b = d ` t)} <=   \
   141 \      POgen({p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t  & b = d ` t)})";
   133 \      POgen({p.EX a b.p=<a,b> & (EX t.a=fix(idgen) ` t  & b = d ` t)})";
   142 by (REPEAT (step_tac term_cs 1));
   134 by (REPEAT (step_tac term_cs 1));
   143 by (term_case_tac "t" 1);
   135 by (term_case_tac "t" 1);
   144 by (ALLGOALS (SIMP_TAC (term_ss addrews (POgenXH::([prem,fix_idgenfp] RL idgen_lemmas)))));
   136 by (ALLGOALS (simp_tac (term_ss addsimps (POgenXH::([prem,fix_idgenfp] RL idgen_lemmas)))));
   145 by (ALLGOALS (fast_tac set_cs));
   137 by (ALLGOALS (fast_tac set_cs));
   146 val lemma1 = result();
   138 val lemma1 = result();
   147 
   139 
   148 val [prem] = goal Fix.thy
   140 val [prem] = goal Fix.thy
   149     "idgen(d) = d ==> fix(idgen) [= d";
   141     "idgen(d) = d ==> fix(idgen) [= d";
   155 val [prem] = goal Fix.thy
   147 val [prem] = goal Fix.thy
   156     "idgen(d) = d ==> \
   148     "idgen(d) = d ==> \
   157 \      {p.EX a b.p=<a,b> & b = d ` a} <= POgen({p.EX a b.p=<a,b> & b = d ` a})";
   149 \      {p.EX a b.p=<a,b> & b = d ` a} <= POgen({p.EX a b.p=<a,b> & b = d ` a})";
   158 by (REPEAT (step_tac term_cs 1));
   150 by (REPEAT (step_tac term_cs 1));
   159 by (term_case_tac "a" 1);
   151 by (term_case_tac "a" 1);
   160 by (ALLGOALS (SIMP_TAC (term_ss addrews (POgenXH::([prem] RL idgen_lemmas)))));
   152 by (ALLGOALS (simp_tac (term_ss addsimps (POgenXH::([prem] RL idgen_lemmas)))));
   161 by (ALLGOALS (fast_tac set_cs));
   153 by (ALLGOALS (fast_tac set_cs));
   162 val lemma2 = result();
   154 val lemma2 = result();
   163 
   155 
   164 val [prem] = goal Fix.thy
   156 val [prem] = goal Fix.thy
   165     "idgen(d) = d ==> lam x.x [= d";
   157     "idgen(d) = d ==> lam x.x [= d";
   166 br (allI RS po_eta) 1;
   158 br (allI RS po_eta) 1;
   167 br (lemma2 RSN(2,po_coinduct)) 1;
   159 br (lemma2 RSN(2,po_coinduct)) 1;
   168 by (SIMP_TAC term_ss 1);
   160 by (simp_tac term_ss 1);
   169 by (ALLGOALS (fast_tac (term_cs addIs [prem,po_eta_lemma,fix_idgenfp])));
   161 by (ALLGOALS (fast_tac (term_cs addIs [prem,po_eta_lemma,fix_idgenfp])));
   170 val id_least_idgen = result();
   162 val id_least_idgen = result();
   171 
   163 
   172 goal Fix.thy  "fix(idgen) = lam x.x";
   164 goal Fix.thy  "fix(idgen) = lam x.x";
   173 by (fast_tac (term_cs addIs [eq_iff RS iffD2,
   165 by (fast_tac (term_cs addIs [eq_iff RS iffD2,
   194 by (REPEAT_SOME (ares_tac [allI]));
   186 by (REPEAT_SOME (ares_tac [allI]));
   195 br (applyBbot RS ssubst) 1;
   187 br (applyBbot RS ssubst) 1;
   196 brs prems 1;
   188 brs prems 1;
   197 br (applyB RS ssubst )1;
   189 br (applyB RS ssubst )1;
   198 by (res_inst_tac [("t","xa")] term_case 1);
   190 by (res_inst_tac [("t","xa")] term_case 1);
   199 by (ALLGOALS (SIMP_TAC term_ss));
   191 by (ALLGOALS (simp_tac term_ss));
   200 by (ALLGOALS (fast_tac (term_cs addIs ([all_INCL,INCL_subst] @ prems))));
   192 by (ALLGOALS (fast_tac (term_cs addIs ([all_INCL,INCL_subst] @ prems))));
   201 val term_ind = result();
   193 val term_ind = result();
   202 
   194