src/HOL/UNITY/Extend.ML
changeset 7537 875754b599df
parent 7499 23e090051cb8
child 7538 357873391561
equal deleted inserted replaced
7536:5c094aec523d 7537:875754b599df
     7   function f (forget)    maps the extended state to the original state
     7   function f (forget)    maps the extended state to the original state
     8   function g (forgotten) maps the extended state to the "extending part"
     8   function g (forgotten) maps the extended state to the "extending part"
     9 *)
     9 *)
    10 
    10 
    11 (** These we prove OUTSIDE the locale. **)
    11 (** These we prove OUTSIDE the locale. **)
       
    12 
       
    13 
       
    14 (****************UNITY.ML****************)
       
    15 Goalw [stable_def, constrains_def] "stable UNIV = UNIV";
       
    16 by Auto_tac;
       
    17 qed "stable_UNIV";
       
    18 Addsimps [stable_UNIV];
       
    19 
    12 
    20 
    13 (*Possibly easier than reasoning about "inv h"*)
    21 (*Possibly easier than reasoning about "inv h"*)
    14 val [surj_h,prem] = 
    22 val [surj_h,prem] = 
    15 Goalw [good_map_def]
    23 Goalw [good_map_def]
    16      "[| surj h; !! x x' y y'. h(x,y) = h(x',y') ==> x=x' |] ==> good_map h";
    24      "[| surj h; !! x x' y y'. h(x,y) = h(x',y') ==> x=x' |] ==> good_map h";
    74 
    82 
    75 Goal "{s. P (f s)} = extend_set h {s. P s}";
    83 Goal "{s. P (f s)} = extend_set h {s. P s}";
    76 by Auto_tac;
    84 by Auto_tac;
    77 qed "Collect_eq_extend_set";
    85 qed "Collect_eq_extend_set";
    78 
    86 
    79 Goalw [extend_set_def, project_set_def] "project_set h (extend_set h F) = F";
    87 Goalw [extend_set_def, project_set_def]
       
    88      "project_set h (extend_set h F) = F";
    80 by Auto_tac;
    89 by Auto_tac;
    81 qed "extend_set_inverse";
    90 qed "extend_set_inverse";
    82 Addsimps [extend_set_inverse];
    91 Addsimps [extend_set_inverse];
    83 
    92 
    84 Goal "inj (extend_set h)";
    93 Goal "inj (extend_set h)";
   151 Goalw [extend_act_def]
   160 Goalw [extend_act_def]
   152      "(z, z') : extend_act h act ==> (f z, f z') : act";
   161      "(z, z') : extend_act h act ==> (f z, f z') : act";
   153 by Auto_tac;
   162 by Auto_tac;
   154 qed "extend_act_D";
   163 qed "extend_act_D";
   155 
   164 
   156 Goalw [extend_act_def, project_act_def]
   165 (*Premise is still undesirably strong, since Domain act can include
   157      "project_act h (extend_act h act) = act";
   166   non-reachable states, but it seems necessary for this result.*)
   158 by Auto_tac;
   167 Goalw [extend_act_def,project_set_def, project_act_def]
   159 by (Blast_tac 1);
   168  "Domain act <= project_set h C ==> project_act C h (extend_act h act) = act";
       
   169 by (Force_tac 1);
   160 qed "extend_act_inverse";
   170 qed "extend_act_inverse";
   161 Addsimps [extend_act_inverse];
   171 Addsimps [extend_act_inverse];
   162 
   172 
   163 Goal "inj (extend_act h)";
   173 Goal "inj (extend_act h)";
   164 by (rtac inj_on_inverseI 1);
   174 by (rtac inj_on_inverseI 1);
   165 by (rtac extend_act_inverse 1);
   175 by (rtac extend_act_inverse 1);
       
   176 by (force_tac (claset(), simpset() addsimps [project_set_def]) 1);
   166 qed "inj_extend_act";
   177 qed "inj_extend_act";
   167 
   178 
   168 Goalw [extend_set_def, extend_act_def]
   179 Goalw [extend_set_def, extend_act_def]
   169      "extend_act h act ^^ (extend_set h A) = extend_set h (act ^^ A)";
   180      "extend_act h act ^^ (extend_set h A) = extend_set h (act ^^ A)";
   170 by (Force_tac 1);
   181 by (Force_tac 1);
   186     "extend_act h Id = Id";
   197     "extend_act h Id = Id";
   187 by (force_tac (claset() addIs  [h_f_g_eq RS sym], simpset()) 1);
   198 by (force_tac (claset() addIs  [h_f_g_eq RS sym], simpset()) 1);
   188 qed "extend_act_Id";
   199 qed "extend_act_Id";
   189 
   200 
   190 Goalw [project_act_def]
   201 Goalw [project_act_def]
   191      "(z, z') : act ==> (f z, f z') : project_act h act";
   202      "[| (z, z') : act;  f z = f z' | z: C |] \
       
   203 \     ==> (f z, f z') : project_act C h act";
   192 by (auto_tac (claset() addSIs [exI] addIs [h_f_g_eq RS ssubst], 
   204 by (auto_tac (claset() addSIs [exI] addIs [h_f_g_eq RS ssubst], 
   193 	      simpset()));
   205 	      simpset()));
   194 qed "project_act_I";
   206 qed "project_act_I";
   195 
   207 
   196 Goalw [project_set_def, project_act_def]
   208 Goalw [project_set_def, project_act_def]
   197     "project_act h Id = Id";
   209     "project_act C h Id = Id";
   198 by (Force_tac 1);
   210 by (Force_tac 1);
   199 qed "project_act_Id";
   211 qed "project_act_Id";
   200 
   212 
       
   213 (*premise can be weakened*)
   201 Goalw [project_set_def, project_act_def]
   214 Goalw [project_set_def, project_act_def]
   202     "Domain (project_act h act) = project_set h (Domain act)";
   215     "Domain act <= C \
       
   216 \    ==> Domain (project_act C h act) = project_set h (Domain act)";
   203 by Auto_tac;
   217 by Auto_tac;
   204 by (res_inst_tac [("y1", "ya")] (surj_h RS surjD RS exE) 1);
   218 by (res_inst_tac [("y1", "ya")] (surj_h RS surjD RS exE) 1);
   205 by Auto_tac;
   219 by Auto_tac;
   206 qed "Domain_project_act";
   220 qed "Domain_project_act";
   207 
   221 
   219 
   233 
   220 Goalw [extend_def] "Init (extend h F) = extend_set h (Init F)";
   234 Goalw [extend_def] "Init (extend h F) = extend_set h (Init F)";
   221 by Auto_tac;
   235 by Auto_tac;
   222 qed "Init_extend";
   236 qed "Init_extend";
   223 
   237 
   224 Goalw [project_def] "Init (project h F) = project_set h (Init F)";
   238 Goalw [project_def] "Init (project C h F) = project_set h (Init F)";
   225 by Auto_tac;
   239 by Auto_tac;
   226 qed "Init_project";
   240 qed "Init_project";
   227 
   241 
   228 Goal "Acts (extend h F) = (extend_act h `` Acts F)";
   242 Goal "Acts (extend h F) = (extend_act h `` Acts F)";
   229 by (auto_tac (claset() addSIs [extend_act_Id RS sym], 
   243 by (auto_tac (claset() addSIs [extend_act_Id RS sym], 
   230 	      simpset() addsimps [extend_def, image_iff]));
   244 	      simpset() addsimps [extend_def, image_iff]));
   231 qed "Acts_extend";
   245 qed "Acts_extend";
   232 
   246 
   233 Goal "Acts (project h F) = (project_act h `` Acts F)";
   247 Goal "Acts (project C h F) = (project_act C h `` Acts F)";
   234 by (auto_tac (claset() addSIs [project_act_Id RS sym], 
   248 by (auto_tac (claset() addSIs [project_act_Id RS sym], 
   235 	      simpset() addsimps [project_def, image_iff]));
   249 	      simpset() addsimps [project_def, image_iff]));
   236 qed "Acts_project";
   250 qed "Acts_project";
   237 
   251 
   238 Addsimps [Init_extend, Init_project, Acts_extend, Acts_project];
   252 Addsimps [Init_extend, Init_project, Acts_extend, Acts_project];
   240 Goalw [SKIP_def] "extend h SKIP = SKIP";
   254 Goalw [SKIP_def] "extend h SKIP = SKIP";
   241 by (rtac program_equalityI 1);
   255 by (rtac program_equalityI 1);
   242 by Auto_tac;
   256 by Auto_tac;
   243 qed "extend_SKIP";
   257 qed "extend_SKIP";
   244 
   258 
   245 Goalw [SKIP_def] "project h SKIP = SKIP";
   259 Goalw [SKIP_def] "project C h SKIP = SKIP";
   246 by (rtac program_equalityI 1);
   260 by (rtac program_equalityI 1);
   247 by (auto_tac (claset() addIs  [h_f_g_eq RS sym], 
   261 by (auto_tac (claset() addIs  [h_f_g_eq RS sym], 
   248 	      simpset() addsimps [project_set_def]));
   262 	      simpset() addsimps [project_set_def]));
   249 qed "project_SKIP";
   263 qed "project_SKIP";
   250 
   264 
   251 Goal "project h (extend h F) = F";
   265 Goalw [project_set_def] "UNIV <= project_set h UNIV";
       
   266 by Auto_tac;
       
   267 qed "project_set_UNIV";
       
   268 
       
   269 (*ALL act: Acts F. Domain act is MUCH TOO STRONG since Domain Id = UNIV!*)
       
   270 Goal "UNIV <= project_set h C \
       
   271 \     ==> project C h (extend h F) = F";
   252 by (simp_tac (simpset() addsimps [extend_def, project_def]) 1);
   272 by (simp_tac (simpset() addsimps [extend_def, project_def]) 1);
   253 by (rtac program_equalityI 1);
   273 by (rtac program_equalityI 1);
   254 by (simp_tac (simpset() addsimps [image_compose RS sym, o_def]) 2);
   274 by (asm_simp_tac (simpset() addsimps [image_image_eq_UN,
       
   275                    subset_UNIV RS subset_trans RS extend_act_inverse]) 2);
   255 by (Simp_tac 1);
   276 by (Simp_tac 1);
   256 qed "extend_inverse";
   277 qed "extend_inverse";
   257 Addsimps [extend_inverse];
   278 Addsimps [extend_inverse];
   258 
   279 
   259 Goal "inj (extend h)";
   280 Goal "inj (extend h)";
   260 by (rtac inj_on_inverseI 1);
   281 by (rtac inj_on_inverseI 1);
   261 by (rtac extend_inverse 1);
   282 by (rtac extend_inverse 1);
       
   283 by (force_tac (claset(), simpset() addsimps [project_set_def]) 1);
   262 qed "inj_extend";
   284 qed "inj_extend";
   263 
   285 
   264 Goal "extend h (F Join G) = extend h F Join extend h G";
   286 Goal "extend h (F Join G) = extend h F Join extend h G";
   265 by (rtac program_equalityI 1);
   287 by (rtac program_equalityI 1);
   266 by (simp_tac (simpset() addsimps [image_Un, Acts_Join]) 2);
   288 by (simp_tac (simpset() addsimps [image_Un]) 2);
   267 by (simp_tac (simpset() addsimps [extend_set_Int_distrib]) 1);
   289 by (simp_tac (simpset() addsimps [extend_set_Int_distrib]) 1);
   268 qed "extend_Join";
   290 qed "extend_Join";
   269 Addsimps [extend_Join];
   291 Addsimps [extend_Join];
   270 
   292 
   271 Goal "extend h (JOIN I F) = (JN i:I. extend h (F i))";
   293 Goal "extend h (JOIN I F) = (JN i:I. extend h (F i))";
   272 by (rtac program_equalityI 1);
   294 by (rtac program_equalityI 1);
   273 by (simp_tac (simpset() addsimps [image_UN, Acts_JN]) 2);
   295 by (simp_tac (simpset() addsimps [image_UN]) 2);
   274 by (simp_tac (simpset() addsimps [extend_set_INT_distrib]) 1);
   296 by (simp_tac (simpset() addsimps [extend_set_INT_distrib]) 1);
   275 qed "extend_JN";
   297 qed "extend_JN";
   276 Addsimps [extend_JN];
   298 Addsimps [extend_JN];
   277 
   299 
   278 Goal "project h ((extend h F) Join G) = F Join (project h G)";
   300 Goal "UNIV <= project_set h C \
       
   301 \     ==> project C h ((extend h F) Join G) = F Join (project C h G)";
   279 by (rtac program_equalityI 1);
   302 by (rtac program_equalityI 1);
   280 by (simp_tac (simpset() addsimps [Acts_Join, image_Un,
   303 by (asm_simp_tac (simpset() addsimps [image_Un, image_image_eq_UN,
   281 				  image_compose RS sym, o_def]) 2);
   304                    subset_UNIV RS subset_trans RS extend_act_inverse]) 2);
   282 by (simp_tac (simpset() addsimps [project_set_extend_set_Int]) 1);
   305 by (simp_tac (simpset() addsimps [project_set_extend_set_Int]) 1);
   283 qed "project_extend_Join";
   306 qed "project_extend_Join";
   284 
   307 
   285 Goal "(extend h F) Join G = extend h H ==> H = F Join (project h G)";
   308 Goal "UNIV <= project_set h C \
   286 by (dres_inst_tac [("f", "project h")] arg_cong 1);
   309 \     ==> (extend h F) Join G = extend h H ==> H = F Join (project C h G)";
   287 by (full_simp_tac (simpset() addsimps [project_extend_Join]) 1);
   310 by (dres_inst_tac [("f", "project C h")] arg_cong 1);
   288 by (etac sym 1);
   311 by (asm_full_simp_tac (simpset() addsimps [project_extend_Join]) 1);
   289 qed "extend_Join_eq_extend_D";
   312 qed "extend_Join_eq_extend_D";
   290 
   313 
   291 
   314 
   292 (*** Safety: co, stable ***)
   315 (*** Safety: co, stable ***)
   293 
   316 
   305 qed "extend_invariant";
   328 qed "extend_invariant";
   306 
   329 
   307 (** Safety and project **)
   330 (** Safety and project **)
   308 
   331 
   309 Goalw [constrains_def]
   332 Goalw [constrains_def]
   310      "(project h F : A co B)  =  (F : (extend_set h A) co (extend_set h B))";
   333      "(project C h F : A co B)  =  \
   311 by Auto_tac;
   334 \     (F : (C Int extend_set h A) co (extend_set h B) & A <= B)";
   312 by (force_tac (claset(), simpset() addsimps [project_act_def]) 2);
       
   313 by (auto_tac (claset() addSIs [project_act_I], simpset()));
   335 by (auto_tac (claset() addSIs [project_act_I], simpset()));
       
   336 by (rewtac project_act_def);
       
   337 by (force_tac (claset() addSDs [Id_in_Acts RSN (2,bspec)], simpset()) 1);
       
   338 (*the <== direction*)
       
   339 by (force_tac (claset() addSDs [subsetD], simpset()) 1);
   314 qed "project_constrains";
   340 qed "project_constrains";
   315 
   341 
   316 Goal "(project h F : stable A)  =  (F : stable (extend_set h A))";
   342 (*The condition is required to prove the left-to-right direction;
   317 by (simp_tac (simpset() addsimps [stable_def, project_constrains]) 1);
   343   could weaken it to F : (C Int extend_set h A) co C*)
       
   344 Goalw [stable_def]
       
   345      "F : stable C \
       
   346 \     ==> (project C h F : stable A)  =  (F : stable (C Int extend_set h A))";
       
   347 by (simp_tac (simpset() addsimps [project_constrains]) 1);
       
   348 by (blast_tac (claset() addIs [constrains_weaken] addDs [constrains_Int]) 1);
   318 qed "project_stable";
   349 qed "project_stable";
   319 
   350 
   320 Goal "(project h F : increasing func)  =  (F : increasing (func o f))";
   351 Goal "(project UNIV h F : increasing func)  =  \
   321 by (simp_tac (simpset() addsimps [increasing_def, project_stable,
   352 \     (F : increasing (func o f))";
   322 				  Collect_eq_extend_set RS sym]) 1);
   353 by (asm_simp_tac (simpset() addsimps [increasing_def, project_stable,
       
   354 				      Collect_eq_extend_set RS sym]) 1);
   323 qed "project_increasing";
   355 qed "project_increasing";
   324 
   356 
   325 
   357 
   326 (*** Diff, needed for localTo ***)
   358 (*** Diff, needed for localTo ***)
   327 
   359 
   328 (** project versions **)
   360 (** project versions **)
   329 
   361 
   330 (*Opposite direction fails because Diff in the extended state may remove
   362 (*Opposite direction fails because Diff in the extended state may remove
   331   fewer actions, i.e. those that affect other state variables.*)
   363   fewer actions, i.e. those that affect other state variables.*)
   332 Goal "Diff (project h G) acts <= project h (Diff G (extend_act h `` acts))";
   364 Goal "(UN act:acts. Domain act) <= project_set h C \
   333 by (force_tac (claset(), 
   365 \     ==> Diff (project C h G) acts <= \
   334 	       simpset() addsimps [component_eq_subset, Diff_def]) 1);
   366 \         project C h (Diff G (extend_act h `` acts))";
       
   367 by (asm_full_simp_tac (simpset() addsimps [component_eq_subset, Diff_def,
       
   368 					   UN_subset_iff]) 1);
       
   369 by (force_tac (claset() addSIs [image_diff_subset RS subsetD], 
       
   370 	       simpset() addsimps [image_image_eq_UN]) 1);
   335 qed "Diff_project_component_project_Diff";
   371 qed "Diff_project_component_project_Diff";
   336 
   372 
   337 Goal "Diff G (extend_act h `` acts) : (extend_set h A) co (extend_set h B)  \
   373 Goal
   338 \     ==> Diff (project h G) acts : A co B";
   374    "[| (UN act:acts. Domain act) <= project_set h C; \
   339 by (rtac (Diff_project_component_project_Diff RS component_constrains) 1);
   375 \      Diff G (extend_act h `` acts) : (extend_set h A) co (extend_set h B) |]\
   340 by (etac (project_constrains RS iffD2) 1);
   376 \   ==> Diff (project C h G) acts : A co B";
       
   377 by (etac (Diff_project_component_project_Diff RS component_constrains) 1);
       
   378 by (rtac (project_constrains RS iffD2) 1);
       
   379 by (ftac constrains_imp_subset 1);
       
   380 by (Asm_full_simp_tac 1);
       
   381 by (blast_tac (claset() addIs [constrains_weaken]) 1);
   341 qed "Diff_project_co";
   382 qed "Diff_project_co";
   342 
   383 
   343 Goalw [stable_def]
   384 Goalw [stable_def]
   344      "Diff G (extend_act h `` acts) : stable (extend_set h A)  \
   385      "[| (UN act:acts. Domain act) <= project_set h C; \
   345 \     ==> Diff (project h G) acts : stable A";
   386 \        Diff G (extend_act h `` acts) : stable (extend_set h A) |] \
       
   387 \     ==> Diff (project C h G) acts : stable A";
   346 by (etac Diff_project_co 1);
   388 by (etac Diff_project_co 1);
       
   389 by (assume_tac 1);
   347 qed "Diff_project_stable";
   390 qed "Diff_project_stable";
   348 
   391 
   349 (** extend versions **)
   392 (** extend versions **)
   350 
   393 
   351 Goal "(Diff (extend h G) (extend_act h `` acts)) = extend h (Diff G acts)";
   394 Goal "(Diff (extend h G) (extend_act h `` acts)) = extend h (Diff G acts)";
   352 by (auto_tac (claset() addSIs [program_equalityI],
   395 by (auto_tac (claset() addSIs [program_equalityI],
   353 	      simpset() addsimps [Diff_def,
   396 	      simpset() addsimps [Diff_def,
   354 				  inj_extend_act RS image_set_diff RS sym,
   397 				  inj_extend_act RS image_set_diff RS sym]));
   355 				  image_compose RS sym, o_def]));
       
   356 qed "Diff_extend_eq";
   398 qed "Diff_extend_eq";
   357 
   399 
   358 Goal "(Diff (extend h G) (extend_act h `` acts) \
   400 Goal "(Diff (extend h G) (extend_act h `` acts) \
   359 \         : (extend_set h A) co (extend_set h B)) \
   401 \         : (extend_set h A) co (extend_set h B)) \
   360 \     = (Diff G acts : A co B)";
   402 \     = (Diff G acts : A co B)";
   365 \     = (Diff G acts : stable A)";
   407 \     = (Diff G acts : stable A)";
   366 by (simp_tac (simpset() addsimps [Diff_extend_co, stable_def]) 1);
   408 by (simp_tac (simpset() addsimps [Diff_extend_co, stable_def]) 1);
   367 qed "Diff_extend_stable";
   409 qed "Diff_extend_stable";
   368 
   410 
   369 (*Converse appears to fail*)
   411 (*Converse appears to fail*)
   370 Goal "(H : (func o f) localTo extend h G) ==> (project h H : func localTo G)";
   412 Goal "[| UNIV <= project_set h C;  (H : (func o f) localTo extend h G) |] \
       
   413 \     ==> (project C h H : func localTo G)";
   371 by (asm_full_simp_tac 
   414 by (asm_full_simp_tac 
   372     (simpset() addsimps [localTo_def, 
   415     (simpset() addsimps [localTo_def, 
   373 			 project_extend_Join RS sym,
   416 			 project_extend_Join RS sym,
   374 			 Diff_project_stable,
   417 			 subset_UNIV RS subset_trans RS Diff_project_stable,
   375 			 Collect_eq_extend_set RS sym]) 1);
   418 			 Collect_eq_extend_set RS sym]) 1);
   376 qed "project_localTo_I";
   419 qed "project_localTo_I";
   377 
   420 
   378 
   421 
   379 (*** Weak safety primitives: Co, Stable ***)
   422 (*** Weak safety primitives: Co, Stable ***)
   417 qed "extend_Always";
   460 qed "extend_Always";
   418 
   461 
   419 
   462 
   420 (** Reachability and project **)
   463 (** Reachability and project **)
   421 
   464 
   422 Goal "z : reachable F ==> f z : reachable (project h F)";
   465 Goal "[| reachable F <= C;  z : reachable F |] \
       
   466 \     ==> f z : reachable (project C h F)";
   423 by (etac reachable.induct 1);
   467 by (etac reachable.induct 1);
   424 by (force_tac (claset() addIs [reachable.Acts, project_act_I],
   468 by (force_tac (claset() addIs [reachable.Acts, project_act_I],
   425 	       simpset()) 2);
   469 	       simpset()) 2);
   426 by (force_tac (claset() addIs [reachable.Init, project_set_I],
   470 by (force_tac (claset() addIs [reachable.Init, project_set_I],
   427 	       simpset()) 1);
   471 	       simpset()) 1);
   428 qed "reachable_imp_reachable_project";
   472 qed "reachable_imp_reachable_project";
   429 
   473 
   430 (*Converse fails (?) *)
       
   431 Goalw [Constrains_def]
   474 Goalw [Constrains_def]
   432      "project h F : A Co B ==> F : (extend_set h A) Co (extend_set h B)";
   475      "[| reachable F <= C;  project C h F : A Co B |] \
       
   476 \     ==> F : (extend_set h A) Co (extend_set h B)";
   433 by (full_simp_tac (simpset() addsimps [project_constrains]) 1);
   477 by (full_simp_tac (simpset() addsimps [project_constrains]) 1);
       
   478 by (Clarify_tac 1);
   434 by (etac constrains_weaken_L 1);
   479 by (etac constrains_weaken_L 1);
   435 by (auto_tac (claset() addDs [reachable_imp_reachable_project], simpset()));
   480 by (auto_tac (claset() addDs [reachable_imp_reachable_project], simpset()));
   436 qed "project_Constrains_D";
   481 qed "project_Constrains_D";
   437 
   482 
   438 Goalw [Stable_def] "project h F : Stable A ==> F : Stable (extend_set h A)";
   483 Goalw [Stable_def]
       
   484      "[| reachable F <= C;  project C h F : Stable A |] \
       
   485 \     ==> F : Stable (extend_set h A)";
   439 by (asm_simp_tac (simpset() addsimps [project_Constrains_D]) 1);
   486 by (asm_simp_tac (simpset() addsimps [project_Constrains_D]) 1);
   440 qed "project_Stable_D";
   487 qed "project_Stable_D";
   441 
   488 
   442 Goalw [Always_def] "project h F : Always A ==> F : Always (extend_set h A)";
   489 Goalw [Always_def]
       
   490      "[| reachable F <= C;  project C h F : Always A |] \
       
   491 \     ==> F : Always (extend_set h A)";
   443 by (force_tac (claset() addIs [reachable.Init, project_set_I],
   492 by (force_tac (claset() addIs [reachable.Init, project_set_I],
   444 	       simpset() addsimps [project_Stable_D]) 1);
   493 	       simpset() addsimps [project_Stable_D]) 1);
   445 qed "project_Always_D";
   494 qed "project_Always_D";
   446 
   495 
   447 Goalw [Increasing_def]
   496 Goalw [Increasing_def]
   448      "project h F : Increasing func ==> F : Increasing (func o f)";
   497      "[| reachable F <= C;  project C h F : Increasing func |] \
       
   498 \     ==> F : Increasing (func o f)";
   449 by Auto_tac;
   499 by Auto_tac;
   450 by (stac Collect_eq_extend_set 1);
   500 by (stac Collect_eq_extend_set 1);
   451 by (asm_simp_tac (simpset() addsimps [project_Stable_D]) 1); 
   501 by (asm_simp_tac (simpset() addsimps [project_Stable_D]) 1); 
   452 qed "project_Increasing_D";
   502 qed "project_Increasing_D";
   453 
   503 
   454 (*NOT useful in its own right, but a guarantees rule likes premises
   504 
   455   in this form*)
   505 (** Converse results for weak safety: benefits of the argument C *)
   456 Goal "F Join project h G : A Co B    \
   506 
   457 \     ==> extend h F Join G : (extend_set h A) Co (extend_set h B)";
   507 Goal "[| C <= reachable F; x : reachable (project C h F) |] \
   458 by (asm_simp_tac
   508 \     ==> EX y. h(x,y) : reachable F";
   459     (simpset() addsimps [project_extend_Join, project_Constrains_D]) 1);
   509 by (etac reachable.induct 1);
   460 qed "extend_Join_Constrains";
   510 by (ALLGOALS 
   461 
   511     (asm_full_simp_tac
       
   512      (simpset() addsimps [project_set_def, project_act_def])));
       
   513 by (force_tac (claset() addIs [reachable.Acts],
       
   514 	       simpset() addsimps [project_act_def]) 2);
       
   515 by (force_tac (claset() addIs [reachable.Init],
       
   516 	       simpset() addsimps [project_set_def]) 1);
       
   517 qed "reachable_project_imp_reachable";
       
   518 
       
   519 Goalw [Constrains_def]
       
   520      "[| C <= reachable F;  F : (extend_set h A) Co (extend_set h B) |] \
       
   521 \     ==> project C h F : A Co B";
       
   522 by (full_simp_tac (simpset() addsimps [project_constrains, 
       
   523 				       extend_set_Int_distrib]) 1);
       
   524 by (rtac conjI 1);
       
   525 by (force_tac (claset() addSDs [constrains_imp_subset, 
       
   526 				reachable_project_imp_reachable], 
       
   527 	       simpset()) 2);
       
   528 by (etac constrains_weaken 1);
       
   529 by Auto_tac;
       
   530 qed "project_Constrains_I";
       
   531 
       
   532 Goalw [Stable_def]
       
   533      "[| C <= reachable F;  F : Stable (extend_set h A) |] \
       
   534 \     ==> project C h F : Stable A";
       
   535 by (asm_simp_tac (simpset() addsimps [project_Constrains_I]) 1);
       
   536 qed "project_Stable_I";
       
   537 
       
   538 Goalw [Increasing_def]
       
   539      "[| C <= reachable F;  F : Increasing (func o f) |] \
       
   540 \     ==> project C h F : Increasing func";
       
   541 by Auto_tac;
       
   542 by (asm_simp_tac (simpset() addsimps [Collect_eq_extend_set RS sym,
       
   543 				      project_Stable_I]) 1); 
       
   544 qed "project_Increasing_I";
       
   545 
       
   546 Goal "(project (reachable F) h F : A Co B)  =  \
       
   547 \     (F : (extend_set h A) Co (extend_set h B))";
       
   548 by (blast_tac (claset() addIs [project_Constrains_I, project_Constrains_D]) 1);
       
   549 qed "project_Constrains";
       
   550 
       
   551 Goalw [Stable_def]
       
   552      "(project (reachable F) h F : Stable A)  =  \
       
   553 \     (F : Stable (extend_set h A))";
       
   554 by (rtac project_Constrains 1);
       
   555 qed "project_Stable";
       
   556 
       
   557 Goal "(project (reachable F) h F : Increasing func)  =  \
       
   558 \     (F : Increasing (func o f))";
       
   559 by (asm_simp_tac (simpset() addsimps [Increasing_def, project_Stable,
       
   560 				      Collect_eq_extend_set RS sym]) 1);
       
   561 qed "project_Increasing";
       
   562 
       
   563 (**
       
   564     (*NOT useful in its own right, but a guarantees rule likes premises
       
   565       in this form*)
       
   566     Goal "F Join project C h G : A Co B    \
       
   567     \     ==> extend h F Join G : (extend_set h A) Co (extend_set h B)";
       
   568     by (asm_simp_tac
       
   569 	(simpset() addsimps [project_extend_Join, project_Constrains_D]) 1);
       
   570     qed "extend_Join_Constrains";
       
   571 **)
   462 
   572 
   463 (*** Progress: transient, ensures ***)
   573 (*** Progress: transient, ensures ***)
   464 
   574 
   465 Goal "(extend h F : transient (extend_set h A)) = (F : transient A)";
   575 Goal "(extend h F : transient (extend_set h A)) = (F : transient A)";
   466 by (auto_tac (claset(),
   576 by (auto_tac (claset(),
   555     (simpset() addsimps [LeadsTo_def, reachable_extend_eq, 
   665     (simpset() addsimps [LeadsTo_def, reachable_extend_eq, 
   556 			 extend_leadsto, extend_set_Int_distrib RS sym]) 1);
   666 			 extend_leadsto, extend_set_Int_distrib RS sym]) 1);
   557 qed "extend_LeadsTo";
   667 qed "extend_LeadsTo";
   558 
   668 
   559 
   669 
   560 (*** progress for (project h F) ***)
       
   561 
       
   562 Goal "F : transient (extend_set h A) ==> project h F : transient A";
       
   563 by (auto_tac (claset(),
       
   564 	      simpset() addsimps [transient_def, Domain_project_act]));
       
   565 by (rtac bexI 1);
       
   566 by (assume_tac 2);
       
   567 by (full_simp_tac (simpset() addsimps [extend_set_def, project_set_def, 
       
   568 				       project_act_def]) 1);
       
   569 by (Blast_tac 1);
       
   570 qed "transient_extend_set_imp_project_transient";
       
   571 
       
   572 (*Converse of the above...it requires a strong assumption about actions
       
   573   being enabled for all possible values of the new variables.*)
       
   574 Goal "[| project h F : transient A;  \
       
   575 \        ALL act: Acts F. extend_set h (project_set h (Domain act)) <= \
       
   576 \                         Domain act |]  \
       
   577 \     ==> F : transient (extend_set h A)";
       
   578 by (auto_tac (claset(),
       
   579 	      simpset() addsimps [transient_def, 				  Domain_project_act]));
       
   580 by (rtac bexI 1);
       
   581 by (assume_tac 2);
       
   582 by Auto_tac;
       
   583 by (res_inst_tac [("y1", "x")] (surj_h RS surjD RS exE) 1);
       
   584 by (res_inst_tac [("y1", "xa")] (surj_h RS surjD RS exE) 1);
       
   585 by (thin_tac "ALL act:?AA. ?P (act)" 1);
       
   586 by (force_tac (claset() addDs [project_act_I], simpset()) 1);
       
   587 qed "project_transient_imp_transient_extend_set";
       
   588 
       
   589 
       
   590 Goal "F : (extend_set h A) ensures (extend_set h B) \
       
   591 \     ==> project h F : A ensures B";
       
   592 by (asm_full_simp_tac
       
   593     (simpset() addsimps [ensures_def, project_constrains, 
       
   594 			 transient_extend_set_imp_project_transient,
       
   595 			 extend_set_Un_distrib RS sym, 
       
   596 			 extend_set_Diff_distrib RS sym]) 1);
       
   597 qed "ensures_extend_set_imp_project_ensures";
       
   598 
       
   599 
       
   600 (** Strong precondition and postcondition; doesn't seem very useful. **)
   670 (** Strong precondition and postcondition; doesn't seem very useful. **)
   601 
   671 
   602 Goal "F : X guarantees Y ==> \
   672 Goal "F : X guarantees Y ==> \
   603 \     extend h F : (extend h `` X) guarantees (extend h `` Y)";
   673 \     extend h F : (extend h `` X) guarantees (extend h `` Y)";
   604 by (rtac guaranteesI 1);
   674 by (rtac guaranteesI 1);
   605 by Auto_tac;
   675 by Auto_tac;
   606 by (blast_tac (claset() addDs [extend_Join_eq_extend_D, guaranteesD]) 1);
   676 by (blast_tac (claset() addDs [project_set_UNIV RS extend_Join_eq_extend_D, 
       
   677 			       guaranteesD]) 1);
   607 qed "guarantees_imp_extend_guarantees";
   678 qed "guarantees_imp_extend_guarantees";
   608 
   679 
   609 Goal "extend h F : (extend h `` X) guarantees (extend h `` Y) \
   680 Goal "extend h F : (extend h `` X) guarantees (extend h `` Y) \
   610 \    ==> F : X guarantees Y";
   681 \    ==> F : X guarantees Y";
   611 by (rtac guaranteesI 1);
   682 by (rtac guaranteesI 1);
   622 by (blast_tac (claset() addIs [guarantees_imp_extend_guarantees,
   693 by (blast_tac (claset() addIs [guarantees_imp_extend_guarantees,
   623 			       extend_guarantees_imp_guarantees]) 1);
   694 			       extend_guarantees_imp_guarantees]) 1);
   624 qed "extend_guarantees_eq";
   695 qed "extend_guarantees_eq";
   625 
   696 
   626 (*Weak precondition and postcondition; this is the good one!
   697 (*Weak precondition and postcondition; this is the good one!
   627   Not clear that it has a converse [or that we want one!] *)
   698   Not clear that it has a converse [or that we want one!] 
       
   699   Can generalize project (C G) to the function variable "proj"*)
   628 val [xguary,project,extend] =
   700 val [xguary,project,extend] =
   629 Goal "[| F : X guarantees Y;  \
   701 Goal "[| F : X guarantees Y;  \
   630 \        !!G. extend h F Join G : X' ==> F Join project h G : X;  \
   702 \        !!G. extend h F Join G : X' ==> F Join project (C G) h G : X;  \
   631 \        !!G. F Join project h G : Y ==> extend h F Join G : Y' |] \
   703 \        !!G. F Join project (C G) h G : Y ==> extend h F Join G : Y' |] \
   632 \     ==> extend h F : X' guarantees Y'";
   704 \     ==> extend h F : X' guarantees Y'";
   633 by (rtac (xguary RS guaranteesD RS extend RS guaranteesI) 1);
   705 by (rtac (xguary RS guaranteesD RS extend RS guaranteesI) 1);
   634 by (etac project 1);
   706 by (etac project 1);
   635 qed "project_guarantees";
   707 qed "project_guarantees";
   636 
   708 
   640 (*** guarantees corollaries ***)
   712 (*** guarantees corollaries ***)
   641 
   713 
   642 Goal "F : UNIV guarantees increasing func \
   714 Goal "F : UNIV guarantees increasing func \
   643 \     ==> extend h F : UNIV guarantees increasing (func o f)";
   715 \     ==> extend h F : UNIV guarantees increasing (func o f)";
   644 by (etac project_guarantees 1);
   716 by (etac project_guarantees 1);
   645 by (asm_simp_tac
   717 by (asm_simp_tac (simpset() addsimps [project_increasing RS sym]) 2);
   646     (simpset() addsimps [project_extend_Join, project_increasing RS sym]) 2);
   718 by (stac (project_set_UNIV RS project_extend_Join) 2);
   647 by Auto_tac;
   719 by Auto_tac;
   648 qed "extend_guar_increasing";
   720 qed "extend_guar_increasing";
   649 
   721 
   650 Goal "F : UNIV guarantees Increasing func \
   722 Goal "F : UNIV guarantees Increasing func \
   651 \     ==> extend h F : UNIV guarantees Increasing (func o f)";
   723 \     ==> extend h F : UNIV guarantees Increasing (func o f)";
   652 by (etac project_guarantees 1);
   724 by (etac project_guarantees 1);
   653 by (asm_simp_tac
   725 by (rtac (subset_UNIV RS project_Increasing_D) 2);
   654     (simpset() addsimps [project_extend_Join, project_Increasing_D]) 2);
   726 by (stac (project_set_UNIV RS project_extend_Join) 2);
   655 by Auto_tac;
   727 by Auto_tac;
   656 qed "extend_guar_Increasing";
   728 qed "extend_guar_Increasing";
   657 
   729 
   658 Goal "F : (func localTo G) guarantees increasing func  \
   730 Goal "F : (func localTo G) guarantees increasing func  \
   659 \     ==> extend h F : (func o f) localTo (extend h G)  \
   731 \     ==> extend h F : (func o f) localTo (extend h G)  \
   660 \                      guarantees increasing (func o f)";
   732 \                      guarantees increasing (func o f)";
   661 by (etac project_guarantees 1);
   733 by (etac project_guarantees 1);
   662 (*the "increasing" guarantee*)
   734 (*the "increasing" guarantee*)
   663 by (asm_simp_tac
   735 by (asm_simp_tac
   664     (simpset() addsimps [project_extend_Join, project_increasing RS sym]) 2);
   736     (simpset() addsimps [project_increasing RS sym]) 2);
       
   737 by (stac (project_set_UNIV RS project_extend_Join) 2);
       
   738 by (assume_tac 2);
   665 (*the "localTo" requirement*)
   739 (*the "localTo" requirement*)
       
   740 by (stac (project_set_UNIV RS project_extend_Join RS sym) 1);
   666 by (asm_simp_tac 
   741 by (asm_simp_tac 
   667     (simpset() addsimps [project_localTo_I, project_extend_Join RS sym]) 1);
   742     (simpset() addsimps [project_set_UNIV RS project_localTo_I]) 1);
   668 qed "extend_localTo_guar_increasing";
   743 qed "extend_localTo_guar_increasing";
   669 
   744 
   670 Goal "F : (func localTo G) guarantees Increasing func  \
   745 Goal "F : (func localTo G) guarantees Increasing func  \
   671 \     ==> extend h F : (func o f) localTo (extend h G)  \
   746 \     ==> extend h F : (func o f) localTo (extend h G)  \
   672 \                      guarantees Increasing (func o f)";
   747 \                      guarantees Increasing (func o f)";
   673 by (etac project_guarantees 1);
   748 by (etac project_guarantees 1);
   674 (*the "Increasing" guarantee*)
   749 (*the "Increasing" guarantee*)
   675 by (asm_simp_tac
   750 by (rtac (subset_UNIV RS project_Increasing_D) 2);
   676     (simpset() addsimps [project_extend_Join, project_Increasing_D]) 2);
   751 by (stac (project_set_UNIV RS project_extend_Join) 2);
       
   752 by (assume_tac 2);
   677 (*the "localTo" requirement*)
   753 (*the "localTo" requirement*)
       
   754 by (stac (project_set_UNIV RS project_extend_Join RS sym) 1);
   678 by (asm_simp_tac 
   755 by (asm_simp_tac 
   679     (simpset() addsimps [project_localTo_I, project_extend_Join RS sym]) 1);
   756     (simpset() addsimps [project_set_UNIV RS project_localTo_I]) 1);
   680 qed "extend_localTo_guar_Increasing";
   757 qed "extend_localTo_guar_Increasing";
   681 
   758 
   682 Close_locale "Extend";
   759 Close_locale "Extend";
   683 
   760 
   684 (*Close_locale should do this!
   761 (*Close_locale should do this!