src/HOLCF/Tools/domain/domain_theorems.ML
changeset 26336 a0e2b706ce73
parent 26012 f6917792f8a4
child 26342 0f65fa163304
equal deleted inserted replaced
26335:961bbcc9d85b 26336:a0e2b706ce73
   124 val pg = pg' thy;
   124 val pg = pg' thy;
   125 
   125 
   126 (* ----- getting the axioms and definitions --------------------------------- *)
   126 (* ----- getting the axioms and definitions --------------------------------- *)
   127 
   127 
   128 local
   128 local
   129   fun ga s dn = get_thm thy (Name (dn ^ "." ^ s));
   129   fun ga s dn = PureThy.get_thm thy (Facts.Named (dn ^ "." ^ s, NONE));
   130 in
   130 in
   131   val ax_abs_iso  = ga "abs_iso"  dname;
   131   val ax_abs_iso  = ga "abs_iso"  dname;
   132   val ax_rep_iso  = ga "rep_iso"  dname;
   132   val ax_rep_iso  = ga "rep_iso"  dname;
   133   val ax_when_def = ga "when_def" dname;
   133   val ax_when_def = ga "when_def" dname;
   134   fun get_def mk_name (con,_) = ga (mk_name con^"_def") dname;
   134   fun get_def mk_name (con,_) = ga (mk_name con^"_def") dname;
   140     let
   140     let
   141       fun def_of_sel sel = ga (sel^"_def") dname;
   141       fun def_of_sel sel = ga (sel^"_def") dname;
   142       fun def_of_arg arg = Option.map def_of_sel (sel_of arg);
   142       fun def_of_arg arg = Option.map def_of_sel (sel_of arg);
   143       fun defs_of_con (_, args) = List.mapPartial def_of_arg args;
   143       fun defs_of_con (_, args) = List.mapPartial def_of_arg args;
   144     in
   144     in
   145       List.concat (map defs_of_con cons)
   145       maps defs_of_con cons
   146     end;
   146     end;
   147   val ax_copy_def = ga "copy_def" dname;
   147   val ax_copy_def = ga "copy_def" dname;
   148 end; (* local *)
   148 end; (* local *)
   149 
   149 
   150 (* ----- theorems concerning the isomorphism -------------------------------- *)
   150 (* ----- theorems concerning the isomorphism -------------------------------- *)
   279       val rhs = if con = c then TT else FF;
   279       val rhs = if con = c then TT else FF;
   280       val goal = lift_defined %: (nonlazy args, mk_trp (lhs === rhs));
   280       val goal = lift_defined %: (nonlazy args, mk_trp (lhs === rhs));
   281       val tacs = [asm_simp_tac (HOLCF_ss addsimps when_rews) 1];
   281       val tacs = [asm_simp_tac (HOLCF_ss addsimps when_rews) 1];
   282     in pg axs_dis_def goal tacs end;
   282     in pg axs_dis_def goal tacs end;
   283 
   283 
   284   val dis_apps = List.concat (map (fn (c,_) => map (dis_app c) cons) cons);
   284   val dis_apps = maps (fn (c,_) => map (dis_app c) cons) cons;
   285 
   285 
   286   fun dis_defin (con, args) =
   286   fun dis_defin (con, args) =
   287     let
   287     let
   288       val goal = defined (%:x_name) ==> defined (%%:(dis_name con) `% x_name);
   288       val goal = defined (%:x_name) ==> defined (%%:(dis_name con) `% x_name);
   289       val tacs =
   289       val tacs =
   318       val goal = lift_defined %: (nonlazy args, mk_trp (lhs === rhs));
   318       val goal = lift_defined %: (nonlazy args, mk_trp (lhs === rhs));
   319       val tacs = [asm_simp_tac (HOLCF_ss addsimps when_rews) 1];
   319       val tacs = [asm_simp_tac (HOLCF_ss addsimps when_rews) 1];
   320     in pg axs_mat_def goal tacs end;
   320     in pg axs_mat_def goal tacs end;
   321 
   321 
   322   val mat_apps =
   322   val mat_apps =
   323     List.concat (map (fn (c,_) => map (one_mat c) cons) cons);
   323     maps (fn (c,_) => map (one_mat c) cons) cons;
   324 in
   324 in
   325   val mat_rews = mat_stricts @ mat_apps;
   325   val mat_rews = mat_stricts @ mat_apps;
   326 end;
   326 end;
   327 
   327 
   328 local
   328 local
   350       val goal = lift_defined %: (nonlazy args, mk_trp (lhs === rhs));
   350       val goal = lift_defined %: (nonlazy args, mk_trp (lhs === rhs));
   351       val tacs = [asm_simp_tac (HOLCF_ss addsimps when_rews) 1];
   351       val tacs = [asm_simp_tac (HOLCF_ss addsimps when_rews) 1];
   352     in pg axs goal tacs end;
   352     in pg axs goal tacs end;
   353 
   353 
   354   val pat_stricts = map pat_strict cons;
   354   val pat_stricts = map pat_strict cons;
   355   val pat_apps = List.concat (map (fn c => map (pat_app c) cons) cons);
   355   val pat_apps = maps (fn c => map (pat_app c) cons) cons;
   356 in
   356 in
   357   val pat_rews = pat_stricts @ pat_apps;
   357   val pat_rews = pat_stricts @ pat_apps;
   358 end;
   358 end;
   359 
   359 
   360 local
   360 local
   377         rtac @{thm rev_contrapos} 1,
   377         rtac @{thm rev_contrapos} 1,
   378         eres_inst_tac [("f",dis_name con)] cfun_arg_cong 1,
   378         eres_inst_tac [("f",dis_name con)] cfun_arg_cong 1,
   379         asm_simp_tac (HOLCF_ss addsimps dis_rews) 1];
   379         asm_simp_tac (HOLCF_ss addsimps dis_rews) 1];
   380     in pg [] goal tacs end;
   380     in pg [] goal tacs end;
   381 in
   381 in
   382   val con_stricts = List.concat (map con_strict cons);
   382   val con_stricts = maps con_strict cons;
   383   val con_defins = map con_defin cons;
   383   val con_defins = map con_defin cons;
   384   val con_rews = con_stricts @ con_defins;
   384   val con_rews = con_stricts @ con_defins;
   385 end;
   385 end;
   386 
   386 
   387 local
   387 local
   405       [simp_tac (HOLCF_ss addsimps when_rews) 1];
   405       [simp_tac (HOLCF_ss addsimps when_rews) 1];
   406 
   406 
   407   fun sel_strict (_, args) =
   407   fun sel_strict (_, args) =
   408     List.mapPartial (Option.map one_sel o sel_of) args;
   408     List.mapPartial (Option.map one_sel o sel_of) args;
   409 in
   409 in
   410   val sel_stricts = List.concat (map sel_strict cons);
   410   val sel_stricts = maps sel_strict cons;
   411 end;
   411 end;
   412 
   412 
   413 local
   413 local
   414   fun sel_app_same c n sel (con, args) =
   414   fun sel_app_same c n sel (con, args) =
   415     let
   415     let
   440     else sel_app_diff c n sel (con, args);
   440     else sel_app_diff c n sel (con, args);
   441 
   441 
   442   fun one_sel c n sel = map (sel_app c n sel) cons;
   442   fun one_sel c n sel = map (sel_app c n sel) cons;
   443   fun one_sel' c n arg = Option.map (one_sel c n) (sel_of arg);
   443   fun one_sel' c n arg = Option.map (one_sel c n) (sel_of arg);
   444   fun one_con (c, args) =
   444   fun one_con (c, args) =
   445     List.concat (List.mapPartial I (mapn (one_sel' c) 0 args));
   445     flat (map_filter I (mapn (one_sel' c) 0 args));
   446 in
   446 in
   447   val sel_apps = List.concat (map one_con cons);
   447   val sel_apps = maps one_con cons;
   448 end;
   448 end;
   449 
   449 
   450 local
   450 local
   451   fun sel_defin sel =
   451   fun sel_defin sel =
   452     let
   452     let
   489               (args2, Name.variant_list (map vname args1) (map vname args2)));
   489               (args2, Name.variant_list (map vname args1) (map vname args2)));
   490         in [dist arg1 arg2, dist arg2 arg1] end;
   490         in [dist arg1 arg2, dist arg2 arg1] end;
   491     fun distincts []      = []
   491     fun distincts []      = []
   492       | distincts (c::cs) = (map (distinct c) cs) :: distincts cs;
   492       | distincts (c::cs) = (map (distinct c) cs) :: distincts cs;
   493   in distincts cons end;
   493   in distincts cons end;
   494 val dist_les = List.concat (List.concat distincts_le);
   494 val dist_les = flat (flat distincts_le);
   495 val dist_eqs =
   495 val dist_eqs =
   496   let
   496   let
   497     fun distinct (_,args1) ((_,args2), leqs) =
   497     fun distinct (_,args1) ((_,args2), leqs) =
   498       let
   498       let
   499         val (le1,le2) = (hd leqs, hd(tl leqs));
   499         val (le1,le2) = (hd leqs, hd(tl leqs));
   502         if nonlazy args1 = [] then [eq1, eq1 RS not_sym] else
   502         if nonlazy args1 = [] then [eq1, eq1 RS not_sym] else
   503         if nonlazy args2 = [] then [eq2, eq2 RS not_sym] else
   503         if nonlazy args2 = [] then [eq2, eq2 RS not_sym] else
   504           [eq1, eq2]
   504           [eq1, eq2]
   505       end;
   505       end;
   506     fun distincts []      = []
   506     fun distincts []      = []
   507       | distincts ((c,leqs)::cs) = List.concat
   507       | distincts ((c,leqs)::cs) = flat
   508 	            (ListPair.map (distinct c) ((map #1 cs),leqs)) @
   508 	            (ListPair.map (distinct c) ((map #1 cs),leqs)) @
   509 		    distincts cs;
   509 		    distincts cs;
   510   in map standard (distincts (cons ~~ distincts_le)) end;
   510   in map standard (distincts (cons ~~ distincts_le)) end;
   511 
   511 
   512 local 
   512 local 
   610 val pg = pg' thy;
   610 val pg = pg' thy;
   611 
   611 
   612 (* ----- getting the composite axiom and definitions ------------------------ *)
   612 (* ----- getting the composite axiom and definitions ------------------------ *)
   613 
   613 
   614 local
   614 local
   615   fun ga s dn = get_thm thy (Name (dn ^ "." ^ s));
   615   fun ga s dn = PureThy.get_thm thy (Facts.Named (dn ^ "." ^ s, NONE));
   616 in
   616 in
   617   val axs_reach      = map (ga "reach"     ) dnames;
   617   val axs_reach      = map (ga "reach"     ) dnames;
   618   val axs_take_def   = map (ga "take_def"  ) dnames;
   618   val axs_take_def   = map (ga "take_def"  ) dnames;
   619   val axs_finite_def = map (ga "finite_def") dnames;
   619   val axs_finite_def = map (ga "finite_def") dnames;
   620   val ax_copy2_def   =      ga "copy_def"  comp_dnam;
   620   val ax_copy2_def   =      ga "copy_def"  comp_dnam;
   621   val ax_bisim_def   =      ga "bisim_def" comp_dnam;
   621   val ax_bisim_def   =      ga "bisim_def" comp_dnam;
   622 end;
   622 end;
   623 
   623 
   624 local
   624 local
   625   fun gt  s dn = get_thm  thy (Name (dn ^ "." ^ s));
   625   fun gt  s dn = PureThy.get_thm  thy (Facts.Named (dn ^ "." ^ s, NONE));
   626   fun gts s dn = get_thms thy (Name (dn ^ "." ^ s));
   626   fun gts s dn = PureThy.get_thms thy (Facts.Named (dn ^ "." ^ s, NONE));
   627 in
   627 in
   628   val cases = map (gt  "casedist" ) dnames;
   628   val cases = map (gt  "casedist" ) dnames;
   629   val con_rews  = List.concat (map (gts "con_rews" ) dnames);
   629   val con_rews  = maps (gts "con_rews" ) dnames;
   630   val copy_rews = List.concat (map (gts "copy_rews") dnames);
   630   val copy_rews = maps (gts "copy_rews") dnames;
   631 end;
   631 end;
   632 
   632 
   633 fun dc_take dn = %%:(dn^"_take");
   633 fun dc_take dn = %%:(dn^"_take");
   634 val x_name = idx_name dnames "x"; 
   634 val x_name = idx_name dnames "x"; 
   635 val P_name = idx_name dnames "P";
   635 val P_name = idx_name dnames "P";
   666           fun mk_take n = dc_take (List.nth (dnames, n)) $ %:"n";
   666           fun mk_take n = dc_take (List.nth (dnames, n)) $ %:"n";
   667           val lhs = (dc_take dn $ (%%:"Suc" $ %:"n"))`(con_app con args);
   667           val lhs = (dc_take dn $ (%%:"Suc" $ %:"n"))`(con_app con args);
   668           val rhs = con_app2 con (app_rec_arg mk_take) args;
   668           val rhs = con_app2 con (app_rec_arg mk_take) args;
   669         in Library.foldr mk_all (map vname args, lhs === rhs) end;
   669         in Library.foldr mk_all (map vname args, lhs === rhs) end;
   670       fun mk_eqns ((dn, _), cons) = map (mk_eqn dn) cons;
   670       fun mk_eqns ((dn, _), cons) = map (mk_eqn dn) cons;
   671       val goal = mk_trp (foldr1 mk_conj (List.concat (map mk_eqns eqs)));
   671       val goal = mk_trp (foldr1 mk_conj (maps mk_eqns eqs));
   672       val simps = List.filter (has_fewer_prems 1) copy_rews;
   672       val simps = List.filter (has_fewer_prems 1) copy_rews;
   673       fun con_tac (con, args) =
   673       fun con_tac (con, args) =
   674         if nonlazy_rec args = []
   674         if nonlazy_rec args = []
   675         then all_tac
   675         then all_tac
   676         else EVERY (map c_UU_tac (nonlazy_rec args)) THEN
   676         else EVERY (map c_UU_tac (nonlazy_rec args)) THEN
   680         simp_tac iterate_Cprod_ss 1 ::
   680         simp_tac iterate_Cprod_ss 1 ::
   681         induct_tac "n" 1 ::
   681         induct_tac "n" 1 ::
   682         simp_tac (iterate_Cprod_ss addsimps copy_con_rews) 1 ::
   682         simp_tac (iterate_Cprod_ss addsimps copy_con_rews) 1 ::
   683         asm_full_simp_tac (HOLCF_ss addsimps simps) 1 ::
   683         asm_full_simp_tac (HOLCF_ss addsimps simps) 1 ::
   684         TRY (safe_tac HOL_cs) ::
   684         TRY (safe_tac HOL_cs) ::
   685         List.concat (map eq_tacs eqs);
   685         maps eq_tacs eqs;
   686     in pg copy_take_defs goal tacs end;
   686     in pg copy_take_defs goal tacs end;
   687 in
   687 in
   688   val take_rews = map standard
   688   val take_rews = map standard
   689     (atomize take_stricts @ take_0s @ atomize take_apps);
   689     (atomize take_stricts @ take_0s @ atomize take_apps);
   690 end; (* local *)
   690 end; (* local *)
   707   val take_ss = HOL_ss addsimps take_rews;
   707   val take_ss = HOL_ss addsimps take_rews;
   708   fun quant_tac i = EVERY
   708   fun quant_tac i = EVERY
   709     (mapn (fn n => fn _ => res_inst_tac [("x", x_name n)] spec i) 1 dnames);
   709     (mapn (fn n => fn _ => res_inst_tac [("x", x_name n)] spec i) 1 dnames);
   710 
   710 
   711   fun ind_prems_tac prems = EVERY
   711   fun ind_prems_tac prems = EVERY
   712     (List.concat (map (fn cons =>
   712     (maps (fn cons =>
   713       (resolve_tac prems 1 ::
   713       (resolve_tac prems 1 ::
   714         List.concat (map (fn (_,args) => 
   714         maps (fn (_,args) => 
   715           resolve_tac prems 1 ::
   715           resolve_tac prems 1 ::
   716           map (K(atac 1)) (nonlazy args) @
   716           map (K(atac 1)) (nonlazy args) @
   717           map (K(atac 1)) (List.filter is_rec args))
   717           map (K(atac 1)) (List.filter is_rec args))
   718         cons)))
   718         cons))
   719       conss));
   719       conss);
   720   local 
   720   local 
   721     (* check whether every/exists constructor of the n-th part of the equation:
   721     (* check whether every/exists constructor of the n-th part of the equation:
   722        it has a possibly indirectly recursive argument that isn't/is possibly 
   722        it has a possibly indirectly recursive argument that isn't/is possibly 
   723        indirectly lazy *)
   723        indirectly lazy *)
   724     fun rec_to quant nfn rfn ns lazy_rec (n,cons) = quant (exists (fn arg => 
   724     fun rec_to quant nfn rfn ns lazy_rec (n,cons) = quant (exists (fn arg => 
   763             map (K (atac 1))      (nonlazy args) @
   763             map (K (atac 1))      (nonlazy args) @
   764             map (K (etac spec 1)) (List.filter is_rec args);
   764             map (K (etac spec 1)) (List.filter is_rec args);
   765           fun cases_tacs (cons, cases) =
   765           fun cases_tacs (cons, cases) =
   766             res_inst_tac [("x","x")] cases 1 ::
   766             res_inst_tac [("x","x")] cases 1 ::
   767             asm_simp_tac (take_ss addsimps prems) 1 ::
   767             asm_simp_tac (take_ss addsimps prems) 1 ::
   768             List.concat (map con_tacs cons);
   768             maps con_tacs cons;
   769         in
   769         in
   770           tacs1 @ List.concat (map cases_tacs (conss ~~ cases))
   770           tacs1 @ maps cases_tacs (conss ~~ cases)
   771         end;
   771         end;
   772     in pg'' thy [] goal tacf end;
   772     in pg'' thy [] goal tacf end;
   773 
   773 
   774   val take_lemmas =
   774   val take_lemmas =
   775     let
   775     let
   834               etac disjE 1,
   834               etac disjE 1,
   835               asm_simp_tac (HOL_ss addsimps con_rews) 1,
   835               asm_simp_tac (HOL_ss addsimps con_rews) 1,
   836               asm_simp_tac take_ss 1];
   836               asm_simp_tac take_ss 1];
   837             fun con_tacs (con, args) =
   837             fun con_tacs (con, args) =
   838               asm_simp_tac take_ss 1 ::
   838               asm_simp_tac take_ss 1 ::
   839               List.concat (map arg_tacs (nonlazy_rec args));
   839               maps arg_tacs (nonlazy_rec args);
   840             fun foo_tacs n (cons, cases) =
   840             fun foo_tacs n (cons, cases) =
   841               simp_tac take_ss 1 ::
   841               simp_tac take_ss 1 ::
   842               rtac allI 1 ::
   842               rtac allI 1 ::
   843               res_inst_tac [("x",x_name n)] cases 1 ::
   843               res_inst_tac [("x",x_name n)] cases 1 ::
   844               asm_simp_tac take_ss 1 ::
   844               asm_simp_tac take_ss 1 ::
   845               List.concat (map con_tacs cons);
   845               maps con_tacs cons;
   846             val tacs =
   846             val tacs =
   847               rtac allI 1 ::
   847               rtac allI 1 ::
   848               induct_tac "n" 1 ::
   848               induct_tac "n" 1 ::
   849               simp_tac take_ss 1 ::
   849               simp_tac take_ss 1 ::
   850               TRY (safe_tac (empty_cs addSEs [conjE] addSIs [conjI])) ::
   850               TRY (safe_tac (empty_cs addSEs [conjE] addSIs [conjI])) ::
   851               List.concat (mapn foo_tacs 1 (conss ~~ cases));
   851               flat (mapn foo_tacs 1 (conss ~~ cases));
   852           in pg [] goal tacs end;
   852           in pg [] goal tacs end;
   853 
   853 
   854         fun one_finite (dn, l1b) =
   854         fun one_finite (dn, l1b) =
   855           let
   855           let
   856             val goal = mk_trp (%%:(dn^"_finite") $ %:"x");
   856             val goal = mk_trp (%%:(dn^"_finite") $ %:"x");
   874                   etac subst 1,
   874                   etac subst 1,
   875                   rtac fin_ind 1,
   875                   rtac fin_ind 1,
   876                   ind_prems_tac prems];
   876                   ind_prems_tac prems];
   877               in
   877               in
   878                 TRY (safe_tac HOL_cs) ::
   878                 TRY (safe_tac HOL_cs) ::
   879                 List.concat (map finite_tacs (finites ~~ atomize finite_ind))
   879                 maps finite_tacs (finites ~~ atomize finite_ind)
   880               end;
   880               end;
   881           in pg'' thy [] (ind_term concf) tacf end;
   881           in pg'' thy [] (ind_term concf) tacf end;
   882       in (finites, ind) end (* let *)
   882       in (finites, ind) end (* let *)
   883 
   883 
   884     else (* infinite case *)
   884     else (* infinite case *)
   939       val tacs = [
   939       val tacs = [
   940         rtac impI 1,
   940         rtac impI 1,
   941         induct_tac "n" 1,
   941         induct_tac "n" 1,
   942         simp_tac take_ss 1,
   942         simp_tac take_ss 1,
   943         safe_tac HOL_cs] @
   943         safe_tac HOL_cs] @
   944         List.concat (mapn x_tacs 0 xs);
   944         flat (mapn x_tacs 0 xs);
   945     in pg [ax_bisim_def] goal tacs end;
   945     in pg [ax_bisim_def] goal tacs end;
   946 in
   946 in
   947   val coind = 
   947   val coind = 
   948     let
   948     let
   949       fun mk_prj n x = mk_trp (proj (%:"R") eqs n $ %:x $ %:(x^"'"));
   949       fun mk_prj n x = mk_trp (proj (%:"R") eqs n $ %:x $ %:(x^"'"));
   952         mk_trp (%%:(comp_dname^"_bisim") $ %:"R") ===>
   952         mk_trp (%%:(comp_dname^"_bisim") $ %:"R") ===>
   953           Logic.list_implies (mapn mk_prj 0 xs,
   953           Logic.list_implies (mapn mk_prj 0 xs,
   954             mk_trp (foldr1 mk_conj (map mk_eqn xs)));
   954             mk_trp (foldr1 mk_conj (map mk_eqn xs)));
   955       val tacs =
   955       val tacs =
   956         TRY (safe_tac HOL_cs) ::
   956         TRY (safe_tac HOL_cs) ::
   957         List.concat (map (fn take_lemma => [
   957         maps (fn take_lemma => [
   958           rtac take_lemma 1,
   958           rtac take_lemma 1,
   959           cut_facts_tac [coind_lemma] 1,
   959           cut_facts_tac [coind_lemma] 1,
   960           fast_tac HOL_cs 1])
   960           fast_tac HOL_cs 1])
   961         take_lemmas);
   961         take_lemmas;
   962     in pg [] goal tacs end;
   962     in pg [] goal tacs end;
   963 end; (* local *)
   963 end; (* local *)
   964 
   964 
   965 in thy |> Sign.add_path comp_dnam
   965 in thy |> Sign.add_path comp_dnam
   966        |> (snd o (PureThy.add_thmss (map Thm.no_attributes [
   966        |> (snd o (PureThy.add_thmss (map Thm.no_attributes [