diff -r 3a8d722fd3ff -r 16c4ea954511 ex/LList.ML --- a/ex/LList.ML Fri Nov 11 10:35:03 1994 +0100 +++ b/ex/LList.ML Mon Nov 21 17:50:34 1994 +0100 @@ -23,7 +23,7 @@ goalw LList.thy llist.defs "!!A B. A<=B ==> llist(A) <= llist(B)"; by (rtac gfp_mono 1); by (REPEAT (ares_tac basic_monos 1)); -val llist_mono = result(); +qed "llist_mono"; goal LList.thy "llist(A) = {Numb(0)} <+> (A <*> llist(A))"; @@ -31,7 +31,7 @@ by (fast_tac (univ_cs addSIs (equalityI :: map rew llist.intrs) addEs [rew llist.elim]) 1) end; -val llist_unfold = result(); +qed "llist_unfold"; (*** Type checking by coinduction, using list_Fun @@ -43,44 +43,44 @@ be llist.coinduct 1; be (subsetD RS CollectD) 1; ba 1; -val llist_coinduct = result(); +qed "llist_coinduct"; goalw LList.thy [list_Fun_def, NIL_def] "NIL: list_Fun(A,X)"; by (fast_tac set_cs 1); -val list_Fun_NIL_I = result(); +qed "list_Fun_NIL_I"; goalw LList.thy [list_Fun_def,CONS_def] "!!M N. [| M: A; N: X |] ==> CONS(M,N) : list_Fun(A,X)"; by (fast_tac set_cs 1); -val list_Fun_CONS_I = result(); +qed "list_Fun_CONS_I"; (*Utilise the "strong" part, i.e. gfp(f)*) goalw LList.thy (llist.defs @ [list_Fun_def]) "!!M N. M: llist(A) ==> M : list_Fun(A, X Un llist(A))"; by (etac (llist.mono RS gfp_fun_UnI2) 1); -val list_Fun_llist_I = result(); +qed "list_Fun_llist_I"; (*** LList_corec satisfies the desired recurion equation ***) (*A continuity result?*) goalw LList.thy [CONS_def] "CONS(M, UN x.f(x)) = (UN x. CONS(M, f(x)))"; by (simp_tac (univ_ss addsimps [In1_UN1, Scons_UN1_y]) 1); -val CONS_UN1 = result(); +qed "CONS_UN1"; (*UNUSED; obsolete? goal Prod.thy "split(p, %x y.UN z.f(x,y,z)) = (UN z. split(p, %x y.f(x,y,z)))"; by (simp_tac (prod_ss setloop (split_tac [expand_split])) 1); -val split_UN1 = result(); +qed "split_UN1"; goal Sum.thy "sum_case(s,f,%y.UN z.g(y,z)) = (UN z.sum_case(s,f,%y. g(y,z)))"; by (simp_tac (sum_ss setloop (split_tac [expand_sum_case])) 1); -val sum_case2_UN1 = result(); +qed "sum_case2_UN1"; *) val prems = goalw LList.thy [CONS_def] "[| M<=M'; N<=N' |] ==> CONS(M,N) <= CONS(M',N')"; by (REPEAT (resolve_tac ([In1_mono,Scons_mono]@prems) 1)); -val CONS_mono = result(); +qed "CONS_mono"; val corec_fun_simps = [LList_corec_fun_def RS def_nat_rec_0, LList_corec_fun_def RS def_nat_rec_Suc]; @@ -95,7 +95,7 @@ by (res_inst_tac [("n","k")] natE 1); by (ALLGOALS (asm_simp_tac corec_fun_ss)); by (REPEAT (resolve_tac [allI, impI, subset_refl RS CONS_mono, UN1_upper] 1)); -val LList_corec_subset1 = result(); +qed "LList_corec_subset1"; goalw LList.thy [LList_corec_def] "sum_case(%u.NIL, split(%z w. CONS(z, LList_corec(w,f))), f(a)) <= \ @@ -104,7 +104,7 @@ by (safe_tac set_cs); by (ALLGOALS (res_inst_tac [("x","Suc(?k)")] UN1_I THEN' asm_simp_tac corec_fun_ss)); -val LList_corec_subset2 = result(); +qed "LList_corec_subset2"; (*the recursion equation for LList_corec -- NOT SUITABLE FOR REWRITING!*) goal LList.thy @@ -112,7 +112,7 @@ \ split(%z w. CONS(z, LList_corec(w,f))), f(a))"; by (REPEAT (resolve_tac [equalityI, LList_corec_subset1, LList_corec_subset2] 1)); -val LList_corec = result(); +qed "LList_corec"; (*definitional version of same*) val [rew] = goal LList.thy @@ -120,7 +120,7 @@ \ h(a) = sum_case(%u.NIL, split(%z w. CONS(z, h(w))), f(a))"; by (rewtac rew); by (rtac LList_corec 1); -val def_LList_corec = result(); +qed "def_LList_corec"; (*A typical use of co-induction to show membership in the gfp. Bisimulation is range(%x. LList_corec(x,f)) *) @@ -131,7 +131,7 @@ by (stac LList_corec 1); by (simp_tac (llist_ss addsimps [list_Fun_NIL_I, list_Fun_CONS_I, CollectI] |> add_eqI) 1); -val LList_corec_type = result(); +qed "LList_corec_type"; (*Lemma for the proof of llist_corec*) goal LList.thy @@ -143,7 +143,7 @@ by (stac LList_corec 1); by (asm_simp_tac (llist_ss addsimps [list_Fun_NIL_I]) 1); by (fast_tac (set_cs addSIs [list_Fun_CONS_I]) 1); -val LList_corec_type2 = result(); +qed "LList_corec_type2"; (**** llist equality as a gfp; the bisimulation principle ****) @@ -154,7 +154,7 @@ by (fast_tac (univ_cs addSIs (equalityI :: map rew LListD.intrs) addEs [rew LListD.elim]) 1) end; -val LListD_unfold = result(); +qed "LListD_unfold"; goal LList.thy "!M N. : LListD(diag(A)) --> ntrunc(k,M) = ntrunc(k,N)"; by (res_inst_tac [("n", "k")] less_induct 1); @@ -167,7 +167,7 @@ by (res_inst_tac [("n", "n'")] natE 1); by (asm_simp_tac (univ_ss addsimps [CONS_def, ntrunc_one_In1]) 1); by (asm_simp_tac (univ_ss addsimps [CONS_def, ntrunc_In1, ntrunc_Scons]) 1); -val LListD_implies_ntrunc_equality = result(); +qed "LListD_implies_ntrunc_equality"; (*The domain of the LListD relation*) goalw LList.thy (llist.defs @ [NIL_def, CONS_def]) @@ -177,7 +177,7 @@ by (res_inst_tac [("P", "%x. fst``x <= ?B")] (LListD_unfold RS ssubst) 1); by (simp_tac fst_image_ss 1); by (fast_tac univ_cs 1); -val fst_image_LListD = result(); +qed "fst_image_LListD"; (*This inclusion justifies the use of coinduction to show M=N*) goal LList.thy "LListD(diag(A)) <= diag(llist(A))"; @@ -189,7 +189,7 @@ ntrunc_equality) 1); by (assume_tac 1); by (etac (fst_imageI RS (fst_image_LListD RS subsetD)) 1); -val LListD_subset_diag = result(); +qed "LListD_subset_diag"; (** Coinduction, using LListD_Fun THE COINDUCTIVE DEFINITION PACKAGE COULD DO THIS! @@ -200,25 +200,25 @@ be LListD.coinduct 1; be (subsetD RS CollectD) 1; ba 1; -val LListD_coinduct = result(); +qed "LListD_coinduct"; goalw LList.thy [LListD_Fun_def,NIL_def] " : LListD_Fun(r,s)"; by (fast_tac set_cs 1); -val LListD_Fun_NIL_I = result(); +qed "LListD_Fun_NIL_I"; goalw LList.thy [LListD_Fun_def,CONS_def] "!!x. [| x:A; :s |] ==> : LListD_Fun(diag(A),s)"; by (fast_tac univ_cs 1); -val LListD_Fun_CONS_I = result(); +qed "LListD_Fun_CONS_I"; (*Utilise the "strong" part, i.e. gfp(f)*) goalw LList.thy (LListD.defs @ [LListD_Fun_def]) "!!M N. M: LListD(r) ==> M : LListD_Fun(r, X Un LListD(r))"; by (etac (LListD.mono RS gfp_fun_UnI2) 1); -val LListD_Fun_LListD_I = result(); +qed "LListD_Fun_LListD_I"; -(*This converse inclusion helps to strengthen llist_equalityI*) +(*This converse inclusion helps to strengthen LList_equalityI*) goal LList.thy "diag(llist(A)) <= LListD(diag(A))"; by (rtac subsetI 1); by (etac LListD_coinduct 1); @@ -229,19 +229,19 @@ by (ALLGOALS (asm_simp_tac (llist_ss addsimps [diagI, LListD_Fun_NIL_I, LListD_Fun_CONS_I]))); -val diag_subset_LListD = result(); +qed "diag_subset_LListD"; goal LList.thy "LListD(diag(A)) = diag(llist(A))"; by (REPEAT (resolve_tac [equalityI, LListD_subset_diag, diag_subset_LListD] 1)); -val LListD_eq_diag = result(); +qed "LListD_eq_diag"; goal LList.thy "!!M N. M: llist(A) ==> : LListD_Fun(diag(A), X Un diag(llist(A)))"; by (rtac (LListD_eq_diag RS subst) 1); br LListD_Fun_LListD_I 1; by (asm_simp_tac (HOL_ss addsimps [LListD_eq_diag, diagI]) 1); -val LListD_Fun_diag_I = result(); +qed "LListD_Fun_diag_I"; (** To show two LLists are equal, exhibit a bisimulation! @@ -254,7 +254,7 @@ by (etac LListD_coinduct 1); by (asm_simp_tac (HOL_ss addsimps [LListD_eq_diag]) 1); by (safe_tac prod_cs); -val llist_equalityI = result(); +qed "LList_equalityI"; (*** Finality of llist(A): Uniqueness of functions defined by corecursion ***) @@ -267,7 +267,7 @@ by (rtac ext 1); (*next step avoids an unknown (and flexflex pair) in simplification*) by (res_inst_tac [("A", "{u.True}"), - ("r", "range(%u. )")] llist_equalityI 1); + ("r", "range(%u. )")] LList_equalityI 1); by (rtac rangeI 1); by (safe_tac set_cs); by (stac prem1 1); @@ -275,25 +275,25 @@ by (simp_tac (llist_ss addsimps [LListD_Fun_NIL_I, CollectI RS LListD_Fun_CONS_I] |> add_eqI) 1); -val LList_corec_unique = result(); +qed "LList_corec_unique"; val [prem] = goal LList.thy "[| !!x. h(x) = sum_case(%u.NIL, split(%z w. CONS(z,h(w))), f(x)) |] \ \ ==> h = (%x.LList_corec(x,f))"; by (rtac (LList_corec RS (prem RS LList_corec_unique)) 1); -val equals_LList_corec = result(); +qed "equals_LList_corec"; (** Obsolete LList_corec_unique proof: complete induction, not coinduction **) goalw LList.thy [CONS_def] "ntrunc(Suc(0), CONS(M,N)) = {}"; by (rtac ntrunc_one_In1 1); -val ntrunc_one_CONS = result(); +qed "ntrunc_one_CONS"; goalw LList.thy [CONS_def] "ntrunc(Suc(Suc(k)), CONS(M,N)) = CONS (ntrunc(k,M), ntrunc(k,N))"; by (simp_tac (HOL_ss addsimps [ntrunc_Scons,ntrunc_In1]) 1); -val ntrunc_CONS = result(); +qed "ntrunc_CONS"; val [prem1,prem2] = goal LList.thy "[| !!x. h1(x) = sum_case(%u.NIL, split(%z w. CONS(z,h1(w))), f(x)); \ @@ -311,14 +311,14 @@ by (res_inst_tac [("n", "xc")] natE 2); by (ALLGOALS(asm_simp_tac(nat_ss addsimps [ntrunc_0,ntrunc_one_CONS,ntrunc_CONS]))); -val LList_corec_unique = result(); +result(); (*** Lconst -- defined directly using lfp, but equivalent to a LList_corec ***) goal LList.thy "mono(CONS(M))"; by (REPEAT (ares_tac [monoI, subset_refl, CONS_mono] 1)); -val Lconst_fun_mono = result(); +qed "Lconst_fun_mono"; (* Lconst(M) = CONS(M,Lconst(M)) *) val Lconst = standard (Lconst_fun_mono RS (Lconst_def RS def_lfp_Tarski)); @@ -330,20 +330,20 @@ by (safe_tac set_cs); by (res_inst_tac [("P", "%u. u: ?A")] (Lconst RS ssubst) 1); by (REPEAT (ares_tac [list_Fun_CONS_I, singletonI, UnI1] 1)); -val Lconst_type = result(); +qed "Lconst_type"; goal LList.thy "Lconst(M) = LList_corec(M, %x.Inr())"; by (rtac (equals_LList_corec RS fun_cong) 1); by (simp_tac sum_ss 1); by (rtac Lconst 1); -val Lconst_eq_LList_corec = result(); +qed "Lconst_eq_LList_corec"; (*Thus we could have used gfp in the definition of Lconst*) goal LList.thy "gfp(%N. CONS(M, N)) = LList_corec(M, %x.Inr())"; by (rtac (equals_LList_corec RS fun_cong) 1); by (simp_tac sum_ss 1); by (rtac (Lconst_fun_mono RS gfp_Tarski) 1); -val gfp_Lconst_eq_LList_corec = result(); +qed "gfp_Lconst_eq_LList_corec"; (*** Isomorphisms ***) @@ -351,19 +351,19 @@ goal LList.thy "inj(Rep_llist)"; by (rtac inj_inverseI 1); by (rtac Rep_llist_inverse 1); -val inj_Rep_llist = result(); +qed "inj_Rep_llist"; goal LList.thy "inj_onto(Abs_llist,llist(range(Leaf)))"; by (rtac inj_onto_inverseI 1); by (etac Abs_llist_inverse 1); -val inj_onto_Abs_llist = result(); +qed "inj_onto_Abs_llist"; (** Distinctness of constructors **) goalw LList.thy [LNil_def,LCons_def] "~ LCons(x,xs) = LNil"; by (rtac (CONS_not_NIL RS (inj_onto_Abs_llist RS inj_onto_contraD)) 1); by (REPEAT (resolve_tac (llist.intrs @ [rangeI, Rep_llist]) 1)); -val LCons_not_LNil = result(); +qed "LCons_not_LNil"; val LNil_not_LCons = standard (LCons_not_LNil RS not_sym); @@ -375,19 +375,19 @@ goalw LList.thy [LNil_def] "Rep_llist(LNil) = NIL"; by (rtac (llist.NIL_I RS Abs_llist_inverse) 1); -val Rep_llist_LNil = result(); +qed "Rep_llist_LNil"; goalw LList.thy [LCons_def] "Rep_llist(LCons(x,l)) = CONS(Leaf(x),Rep_llist(l))"; by (REPEAT (resolve_tac [llist.CONS_I RS Abs_llist_inverse, rangeI, Rep_llist] 1)); -val Rep_llist_LCons = result(); +qed "Rep_llist_LCons"; (** Injectiveness of CONS and LCons **) goalw LList.thy [CONS_def] "(CONS(M,N)=CONS(M',N')) = (M=M' & N=N')"; by (fast_tac (HOL_cs addSEs [Scons_inject, make_elim In1_inject]) 1); -val CONS_CONS_eq = result(); +qed "CONS_CONS_eq"; val CONS_inject = standard (CONS_CONS_eq RS iffD1 RS conjE); @@ -400,14 +400,14 @@ goalw LList.thy [LCons_def] "(LCons(x,xs)=LCons(y,ys)) = (x=y & xs=ys)"; by (fast_tac llist_cs 1); -val LCons_LCons_eq = result(); +qed "LCons_LCons_eq"; val LCons_inject = standard (LCons_LCons_eq RS iffD1 RS conjE); val [major] = goal LList.thy "CONS(M,N): llist(A) ==> M: A & N: llist(A)"; by (rtac (major RS llist.elim) 1); by (etac CONS_neq_NIL 1); by (fast_tac llist_cs 1); -val CONS_D = result(); +qed "CONS_D"; (****** Reasoning about llist(A) ******) @@ -424,7 +424,7 @@ \ LListD_Fun(diag(A), (%u.)``llist(A) Un \ \ diag(llist(A))) \ \ |] ==> f(M) = g(M)"; -by (rtac llist_equalityI 1); +by (rtac LList_equalityI 1); br (Mlist RS imageI) 1; by (rtac subsetI 1); by (etac imageE 1); @@ -435,7 +435,7 @@ br (gMlist RS LListD_Fun_diag_I) 1; by (etac ssubst 1); by (REPEAT (ares_tac [CONScase] 1)); -val llist_fun_equalityI = result(); +qed "LList_fun_equalityI"; (*** The functional "Lmap" ***) @@ -443,12 +443,12 @@ goal LList.thy "Lmap(f,NIL) = NIL"; by (rtac (Lmap_def RS def_LList_corec RS trans) 1); by (simp_tac List_case_ss 1); -val Lmap_NIL = result(); +qed "Lmap_NIL"; goal LList.thy "Lmap(f, CONS(M,N)) = CONS(f(M), Lmap(f,N))"; by (rtac (Lmap_def RS def_LList_corec RS trans) 1); by (simp_tac List_case_ss 1); -val Lmap_CONS = result(); +qed "Lmap_CONS"; (*Another type-checking proof by coinduction*) val [major,minor] = goal LList.thy @@ -459,34 +459,34 @@ by (ALLGOALS (asm_simp_tac (HOL_ss addsimps [Lmap_NIL,Lmap_CONS]))); by (REPEAT (ares_tac [list_Fun_NIL_I, list_Fun_CONS_I, minor, imageI, UnI1] 1)); -val Lmap_type = result(); +qed "Lmap_type"; (*This type checking rule synthesises a sufficiently large set for f*) val [major] = goal LList.thy "M: llist(A) ==> Lmap(f,M): llist(f``A)"; by (rtac (major RS Lmap_type) 1); by (etac imageI 1); -val Lmap_type2 = result(); +qed "Lmap_type2"; (** Two easy results about Lmap **) val [prem] = goalw LList.thy [o_def] "M: llist(A) ==> Lmap(f o g, M) = Lmap(f, Lmap(g, M))"; -by (rtac (prem RS imageI RS llist_equalityI) 1); +by (rtac (prem RS imageI RS LList_equalityI) 1); by (safe_tac set_cs); by (etac llist.elim 1); by (ALLGOALS (asm_simp_tac (HOL_ss addsimps [Lmap_NIL,Lmap_CONS]))); by (REPEAT (ares_tac [LListD_Fun_NIL_I, imageI, UnI1, rangeI RS LListD_Fun_CONS_I] 1)); -val Lmap_compose = result(); +qed "Lmap_compose"; val [prem] = goal LList.thy "M: llist(A) ==> Lmap(%x.x, M) = M"; -by (rtac (prem RS imageI RS llist_equalityI) 1); +by (rtac (prem RS imageI RS LList_equalityI) 1); by (safe_tac set_cs); by (etac llist.elim 1); by (ALLGOALS (asm_simp_tac (HOL_ss addsimps [Lmap_NIL,Lmap_CONS]))); by (REPEAT (ares_tac [LListD_Fun_NIL_I, imageI RS UnI1, rangeI RS LListD_Fun_CONS_I] 1)); -val Lmap_ident = result(); +qed "Lmap_ident"; (*** Lappend -- its two arguments cause some complications! ***) @@ -494,19 +494,19 @@ goalw LList.thy [Lappend_def] "Lappend(NIL,NIL) = NIL"; by (rtac (LList_corec RS trans) 1); by (simp_tac List_case_ss 1); -val Lappend_NIL_NIL = result(); +qed "Lappend_NIL_NIL"; goalw LList.thy [Lappend_def] "Lappend(NIL,CONS(N,N')) = CONS(N, Lappend(NIL,N'))"; by (rtac (LList_corec RS trans) 1); by (simp_tac List_case_ss 1); -val Lappend_NIL_CONS = result(); +qed "Lappend_NIL_CONS"; goalw LList.thy [Lappend_def] "Lappend(CONS(M,M'), N) = CONS(M, Lappend(M',N))"; by (rtac (LList_corec RS trans) 1); by (simp_tac List_case_ss 1); -val Lappend_CONS = result(); +qed "Lappend_CONS"; val Lappend_ss = List_case_ss addsimps [llist.NIL_I, Lappend_NIL_NIL, Lappend_NIL_CONS, @@ -514,14 +514,14 @@ |> add_eqI; goal LList.thy "!!M. M: llist(A) ==> Lappend(NIL,M) = M"; -by (etac llist_fun_equalityI 1); +by (etac LList_fun_equalityI 1); by (ALLGOALS (asm_simp_tac Lappend_ss)); -val Lappend_NIL = result(); +qed "Lappend_NIL"; goal LList.thy "!!M. M: llist(A) ==> Lappend(M,NIL) = M"; -by (etac llist_fun_equalityI 1); +by (etac LList_fun_equalityI 1); by (ALLGOALS (asm_simp_tac Lappend_ss)); -val Lappend_NIL2 = result(); +qed "Lappend_NIL2"; (** Alternative type-checking proofs for Lappend **) @@ -550,7 +550,7 @@ by (asm_simp_tac (Lappend_ss addsimps [Lappend_NIL, list_Fun_llist_I]) 1); by (asm_simp_tac Lappend_ss 1); by (fast_tac (set_cs addSIs [list_Fun_CONS_I]) 1); -val Lappend_type = result(); +qed "Lappend_type"; (**** Lazy lists as the type 'a llist -- strongly typed versions of above ****) @@ -565,12 +565,12 @@ goalw LList.thy [llist_case_def,LNil_def] "llist_case(c, d, LNil) = c"; by (simp_tac Rep_llist_ss 1); -val llist_case_LNil = result(); +qed "llist_case_LNil"; goalw LList.thy [llist_case_def,LCons_def] "llist_case(c, d, LCons(M,N)) = d(M,N)"; by (simp_tac Rep_llist_ss 1); -val llist_case_LCons = result(); +qed "llist_case_LCons"; (*Elimination is case analysis, not induction.*) val [prem1,prem2] = goalw LList.thy [NIL_def,CONS_def] @@ -585,7 +585,7 @@ by (asm_simp_tac (HOL_ss addsimps [Rep_llist_LCons]) 1); by (etac (Abs_llist_inverse RS ssubst) 1); by (rtac refl 1); -val llistE = result(); +qed "llistE"; (** llist_corec: corecursion for 'a llist **) @@ -599,7 +599,7 @@ by (asm_simp_tac (llist_ss addsimps [LList_corec_type2,Abs_llist_inverse]) 1); (*FIXME: correct case splits usd to be found automatically: by (ASM_SIMP_TAC(llist_ss addsimps [LList_corec_type2,Abs_llist_inverse]) 1);*) -val llist_corec = result(); +qed "llist_corec"; (*definitional version of same*) val [rew] = goal LList.thy @@ -607,7 +607,7 @@ \ h(a) = sum_case(%u.LNil, split(%z w. LCons(z, h(w))), f(a))"; by (rewtac rew); by (rtac llist_corec 1); -val def_llist_corec = result(); +qed "def_llist_corec"; (**** Proofs about type 'a llist functions ****) @@ -619,13 +619,13 @@ by (stac llist_unfold 1); by (simp_tac (HOL_ss addsimps [NIL_def, CONS_def]) 1); by (fast_tac univ_cs 1); -val LListD_Fun_subset_Sigma_llist = result(); +qed "LListD_Fun_subset_Sigma_llist"; goal LList.thy "prod_fun(Rep_llist,Rep_llist) `` r <= \ \ Sigma(llist(range(Leaf)), %x.llist(range(Leaf)))"; by (fast_tac (prod_cs addIs [Rep_llist]) 1); -val subset_Sigma_llist = result(); +qed "subset_Sigma_llist"; val [prem] = goal LList.thy "r <= Sigma(llist(range(Leaf)), %x.llist(range(Leaf))) ==> \ @@ -634,7 +634,7 @@ by (rtac (prem RS subsetD RS SigmaE2) 1); by (assume_tac 1); by (asm_simp_tac (HOL_ss addsimps [o_def,prod_fun,Abs_llist_inverse]) 1); -val prod_fun_lemma = result(); +qed "prod_fun_lemma"; goal LList.thy "prod_fun(Rep_llist, Rep_llist) `` range(%x. ) = \ @@ -642,7 +642,7 @@ br equalityI 1; by (fast_tac (univ_cs addIs [Rep_llist]) 1); by (fast_tac (univ_cs addSEs [Abs_llist_inverse RS subst]) 1); -val prod_fun_range_eq_diag = result(); +qed "prod_fun_range_eq_diag"; (** To show two llists are equal, exhibit a bisimulation! [also admits true equality] **) @@ -651,7 +651,7 @@ by (rtac (inj_Rep_llist RS injD) 1); by (res_inst_tac [("r", "prod_fun(Rep_llist,Rep_llist)``r"), ("A", "range(Leaf)")] - llist_equalityI 1); + LList_equalityI 1); by (rtac (prem1 RS prod_fun_imageI) 1); by (rtac (prem2 RS image_mono RS subset_trans) 1); by (rtac (image_compose RS subst) 1); @@ -661,18 +661,18 @@ by (rtac (LListD_Fun_subset_Sigma_llist RS prod_fun_lemma) 1); by (rtac (subset_Sigma_llist RS Un_least) 1); by (rtac diag_subset_Sigma 1); -val llist_equalityI = result(); +qed "llist_equalityI"; (** Rules to prove the 2nd premise of llist_equalityI **) goalw LList.thy [llistD_Fun_def,LNil_def] " : llistD_Fun(r)"; by (rtac (LListD_Fun_NIL_I RS prod_fun_imageI) 1); -val llistD_Fun_LNil_I = result(); +qed "llistD_Fun_LNil_I"; val [prem] = goalw LList.thy [llistD_Fun_def,LCons_def] ":r ==> : llistD_Fun(r)"; by (rtac (rangeI RS LListD_Fun_CONS_I RS prod_fun_imageI) 1); by (rtac (prem RS prod_fun_imageI) 1); -val llistD_Fun_LCons_I = result(); +qed "llistD_Fun_LCons_I"; (*Utilise the "strong" part, i.e. gfp(f)*) goalw LList.thy [llistD_Fun_def] @@ -682,7 +682,7 @@ by (rtac (image_Un RS ssubst) 1); by (stac prod_fun_range_eq_diag 1); br (Rep_llist RS LListD_Fun_diag_I) 1; -val llistD_Fun_range_I = result(); +qed "llistD_Fun_range_I"; (*A special case of list_equality for functions over lazy lists*) val [prem1,prem2] = goal LList.thy @@ -701,7 +701,7 @@ by (rtac llistD_Fun_range_I 1); by (etac ssubst 1); by (rtac prem2 1); -val llist_fun_equalityI = result(); +qed "llist_fun_equalityI"; (*simpset for llist bisimulations*) val llistD_simps = [llist_case_LNil, llist_case_LCons, @@ -715,12 +715,12 @@ goal LList.thy "lmap(f,LNil) = LNil"; by (rtac (lmap_def RS def_llist_corec RS trans) 1); by (simp_tac llistD_ss 1); -val lmap_LNil = result(); +qed "lmap_LNil"; goal LList.thy "lmap(f, LCons(M,N)) = LCons(f(M), lmap(f,N))"; by (rtac (lmap_def RS def_llist_corec RS trans) 1); by (simp_tac llistD_ss 1); -val lmap_LCons = result(); +qed "lmap_LCons"; (** Two easy results about lmap **) @@ -728,12 +728,12 @@ goal LList.thy "lmap(f o g, l) = lmap(f, lmap(g, l))"; by (res_inst_tac [("l","l")] llist_fun_equalityI 1); by (ALLGOALS (simp_tac (llistD_ss addsimps [lmap_LNil, lmap_LCons]))); -val lmap_compose = result(); +qed "lmap_compose"; goal LList.thy "lmap(%x.x, l) = l"; by (res_inst_tac [("l","l")] llist_fun_equalityI 1); by (ALLGOALS (simp_tac (llistD_ss addsimps [lmap_LNil, lmap_LCons]))); -val lmap_ident = result(); +qed "lmap_ident"; (*** iterates -- llist_fun_equalityI cannot be used! ***) @@ -741,7 +741,7 @@ goal LList.thy "iterates(f,x) = LCons(x, iterates(f,f(x)))"; by (rtac (iterates_def RS def_llist_corec RS trans) 1); by (simp_tac sum_ss 1); -val iterates = result(); +qed "iterates"; goal LList.thy "lmap(f, iterates(f,x)) = iterates(f,f(x))"; by (res_inst_tac [("r", "range(%u.)")] @@ -751,12 +751,12 @@ by (res_inst_tac [("x1", "f(u)")] (iterates RS ssubst) 1); by (res_inst_tac [("x1", "u")] (iterates RS ssubst) 1); by (simp_tac (llistD_ss addsimps [lmap_LCons]) 1); -val lmap_iterates = result(); +qed "lmap_iterates"; goal LList.thy "iterates(f,x) = LCons(x, lmap(f, iterates(f,x)))"; br (lmap_iterates RS ssubst) 1; br iterates 1; -val iterates_lmap = result(); +qed "iterates_lmap"; (*** A rather complex proof about iterates -- cf Andy Pitts ***) @@ -767,12 +767,12 @@ \ LCons(nat_rec(n, b, %m. f), nat_rec(n, l, %m. lmap(f)))"; by (nat_ind_tac "n" 1); by (ALLGOALS (asm_simp_tac (nat_ss addsimps [lmap_LCons]))); -val fun_power_lmap = result(); +qed "fun_power_lmap"; goal Nat.thy "nat_rec(n, g(x), %m. g) = nat_rec(Suc(n), x, %m. g)"; by (nat_ind_tac "n" 1); by (ALLGOALS (asm_simp_tac nat_ss)); -val fun_power_Suc = result(); +qed "fun_power_Suc"; val Pair_cong = read_instantiate_sg (sign_of Prod.thy) [("f","Pair")] (standard(refl RS cong RS cong)); @@ -798,7 +798,7 @@ by (stac fun_power_Suc 1); br (UN1_I RS UnI1) 1; br rangeI 1; -val iterates_equality = result(); +qed "iterates_equality"; (*** lappend -- its two arguments cause some complications! ***) @@ -806,31 +806,31 @@ goalw LList.thy [lappend_def] "lappend(LNil,LNil) = LNil"; by (rtac (llist_corec RS trans) 1); by (simp_tac llistD_ss 1); -val lappend_LNil_LNil = result(); +qed "lappend_LNil_LNil"; goalw LList.thy [lappend_def] "lappend(LNil,LCons(l,l')) = LCons(l, lappend(LNil,l'))"; by (rtac (llist_corec RS trans) 1); by (simp_tac llistD_ss 1); -val lappend_LNil_LCons = result(); +qed "lappend_LNil_LCons"; goalw LList.thy [lappend_def] "lappend(LCons(l,l'), N) = LCons(l, lappend(l',N))"; by (rtac (llist_corec RS trans) 1); by (simp_tac llistD_ss 1); -val lappend_LCons = result(); +qed "lappend_LCons"; goal LList.thy "lappend(LNil,l) = l"; by (res_inst_tac [("l","l")] llist_fun_equalityI 1); by (ALLGOALS (simp_tac (llistD_ss addsimps [lappend_LNil_LNil, lappend_LNil_LCons]))); -val lappend_LNil = result(); +qed "lappend_LNil"; goal LList.thy "lappend(l,LNil) = l"; by (res_inst_tac [("l","l")] llist_fun_equalityI 1); by (ALLGOALS (simp_tac (llistD_ss addsimps [lappend_LNil_LNil, lappend_LCons]))); -val lappend_LNil2 = result(); +qed "lappend_LNil2"; (*The infinite first argument blocks the second*) goal LList.thy "lappend(iterates(f,x), N) = iterates(f,x)"; @@ -840,7 +840,7 @@ by (safe_tac set_cs); by (stac iterates 1); by (simp_tac (llistD_ss addsimps [lappend_LCons]) 1); -val lappend_iterates = result(); +qed "lappend_iterates"; (** Two proofs that lmap distributes over lappend **) @@ -870,11 +870,11 @@ by (res_inst_tac [("l","l")] llist_fun_equalityI 1); by (simp_tac (llistD_ss addsimps [lappend_LNil, lmap_LNil])1); by (simp_tac (llistD_ss addsimps [lappend_LCons, lmap_LCons]) 1); -val lmap_lappend_distrib = result(); +qed "lmap_lappend_distrib"; (*Without strong coinduction, three case analyses might be needed*) goal LList.thy "lappend(lappend(l1,l2) ,l3) = lappend(l1, lappend(l2,l3))"; by (res_inst_tac [("l","l1")] llist_fun_equalityI 1); by (simp_tac (llistD_ss addsimps [lappend_LNil])1); by (simp_tac (llistD_ss addsimps [lappend_LCons]) 1); -val lappend_assoc = result(); +qed "lappend_assoc";