26 (*Strip lemma. The induction hyp is all but the last diamond of the strip.*) |
26 (*Strip lemma. The induction hyp is all but the last diamond of the strip.*) |
27 goalw Comb.thy [diamond_def] |
27 goalw Comb.thy [diamond_def] |
28 "!!r. [| diamond(r); (x,y):r^* |] ==> \ |
28 "!!r. [| diamond(r); (x,y):r^* |] ==> \ |
29 \ ALL y'. (x,y'):r --> (EX z. (y',z): r^* & (y,z): r)"; |
29 \ ALL y'. (x,y'):r --> (EX z. (y',z): r^* & (y,z): r)"; |
30 by (etac rtrancl_induct 1); |
30 by (etac rtrancl_induct 1); |
31 by (Fast_tac 1); |
31 by (Blast_tac 1); |
32 by (slow_best_tac (!claset addIs [r_into_rtrancl RSN (2, rtrancl_trans)] |
32 by (slow_best_tac (set_cs addIs [r_into_rtrancl RSN (2, rtrancl_trans)] |
33 addSDs [spec_mp]) 1); |
33 addSDs [spec_mp]) 1); |
34 val diamond_strip_lemmaE = result() RS spec RS mp RS exE; |
34 val diamond_strip_lemmaE = result() RS spec RS mp RS exE; |
35 |
35 |
36 val [major] = goal Comb.thy "diamond(r) ==> diamond(r^*)"; |
36 val [major] = goal Comb.thy "diamond(r) ==> diamond(r^*)"; |
37 by (rewtac diamond_def); (*unfold only in goal, not in premise!*) |
37 by (rewtac diamond_def); (*unfold only in goal, not in premise!*) |
38 by (rtac (impI RS allI RS allI) 1); |
38 by (rtac (impI RS allI RS allI) 1); |
39 by (etac rtrancl_induct 1); |
39 by (etac rtrancl_induct 1); |
40 by (Fast_tac 1); |
40 by (Blast_tac 1); |
41 by (ALLGOALS (*Seems to be a brittle, undirected search*) |
41 by (slow_best_tac (*Seems to be a brittle, undirected search*) |
42 (slow_best_tac ((claset_of "Fun") addIs [r_into_rtrancl, rtrancl_trans] |
42 (set_cs addIs [r_into_rtrancl RSN (2, rtrancl_trans)] |
43 addEs [major RS diamond_strip_lemmaE]))); |
43 addEs [major RS diamond_strip_lemmaE]) 1); |
44 qed "diamond_rtrancl"; |
44 qed "diamond_rtrancl"; |
45 |
45 |
46 |
46 |
47 (*** Results about Contraction ***) |
47 (*** Results about Contraction ***) |
48 |
|
49 (** Non-contraction results **) |
|
50 |
48 |
51 (*Derive a case for each combinator constructor*) |
49 (*Derive a case for each combinator constructor*) |
52 val K_contractE = contract.mk_cases comb.simps "K -1-> z"; |
50 val K_contractE = contract.mk_cases comb.simps "K -1-> z"; |
53 val S_contractE = contract.mk_cases comb.simps "S -1-> z"; |
51 val S_contractE = contract.mk_cases comb.simps "S -1-> z"; |
54 val Ap_contractE = contract.mk_cases comb.simps "x#y -1-> z"; |
52 val Ap_contractE = contract.mk_cases comb.simps "x#y -1-> z"; |
55 |
53 |
56 AddIs contract.intrs; |
54 AddSIs [contract.K, contract.S]; |
|
55 AddIs [contract.Ap1, contract.Ap2]; |
57 AddSEs [K_contractE, S_contractE, Ap_contractE]; |
56 AddSEs [K_contractE, S_contractE, Ap_contractE]; |
58 Unsafe_Addss (!simpset); |
57 Unsafe_Addss (!simpset); |
59 |
58 |
60 goalw Comb.thy [I_def] "!!z. I -1-> z ==> P"; |
59 goalw Comb.thy [I_def] "!!z. I -1-> z ==> P"; |
61 by (Fast_tac 1); |
60 by (Blast_tac 1); |
62 qed "I_contract_E"; |
61 qed "I_contract_E"; |
63 AddSEs [I_contract_E]; |
62 AddSEs [I_contract_E]; |
64 |
63 |
65 goal Comb.thy "!!x z. K#x -1-> z ==> (EX x'. z = K#x' & x -1-> x')"; |
64 goal Comb.thy "!!x z. K#x -1-> z ==> (EX x'. z = K#x' & x -1-> x')"; |
66 by (Fast_tac 1); |
65 by (Blast_tac 1); |
67 qed "K1_contractD"; |
66 qed "K1_contractD"; |
68 AddSEs [K1_contractD]; |
67 AddSEs [K1_contractD]; |
69 |
68 |
70 goal Comb.thy "!!x z. x ---> y ==> x#z ---> y#z"; |
69 goal Comb.thy "!!x z. x ---> y ==> x#z ---> y#z"; |
71 by (etac rtrancl_induct 1); |
70 by (etac rtrancl_induct 1); |
72 by (ALLGOALS (best_tac (!claset addIs [r_into_rtrancl, rtrancl_trans]))); |
71 by (ALLGOALS (blast_tac (!claset addIs [r_into_rtrancl, rtrancl_trans]))); |
73 qed "Ap_reduce1"; |
72 qed "Ap_reduce1"; |
74 |
73 |
75 goal Comb.thy "!!x z. x ---> y ==> z#x ---> z#y"; |
74 goal Comb.thy "!!x z. x ---> y ==> z#x ---> z#y"; |
76 by (etac rtrancl_induct 1); |
75 by (etac rtrancl_induct 1); |
77 by (ALLGOALS (best_tac (!claset addIs [r_into_rtrancl, rtrancl_trans]))); |
76 by (ALLGOALS (blast_tac (!claset addIs [r_into_rtrancl, rtrancl_trans]))); |
78 qed "Ap_reduce2"; |
77 qed "Ap_reduce2"; |
79 |
78 |
80 (** Counterexample to the diamond property for -1-> **) |
79 (** Counterexample to the diamond property for -1-> **) |
81 |
80 |
82 goal Comb.thy "K#I#(I#I) -1-> I"; |
81 goal Comb.thy "K#I#(I#I) -1-> I"; |
83 by (rtac contract.K 1); |
82 by (rtac contract.K 1); |
84 qed "KIII_contract1"; |
83 qed "KIII_contract1"; |
85 |
84 |
86 goalw Comb.thy [I_def] "K#I#(I#I) -1-> K#I#((K#I)#(K#I))"; |
85 goalw Comb.thy [I_def] "K#I#(I#I) -1-> K#I#((K#I)#(K#I))"; |
87 by (Fast_tac 1); |
86 by (Blast_tac 1); |
88 qed "KIII_contract2"; |
87 qed "KIII_contract2"; |
89 |
88 |
90 goal Comb.thy "K#I#((K#I)#(K#I)) -1-> I"; |
89 goal Comb.thy "K#I#((K#I)#(K#I)) -1-> I"; |
91 by (Fast_tac 1); |
90 by (Blast_tac 1); |
92 qed "KIII_contract3"; |
91 qed "KIII_contract3"; |
93 |
92 |
94 goalw Comb.thy [diamond_def] "~ diamond(contract)"; |
93 goalw Comb.thy [diamond_def] "~ diamond(contract)"; |
95 by (fast_tac (!claset addIs [KIII_contract1,KIII_contract2,KIII_contract3]) 1); |
94 by (blast_tac (!claset addIs [KIII_contract1,KIII_contract2,KIII_contract3]) 1); |
96 qed "not_diamond_contract"; |
95 qed "not_diamond_contract"; |
97 |
96 |
98 |
97 |
99 |
98 |
100 (*** Results about Parallel Contraction ***) |
99 (*** Results about Parallel Contraction ***) |
109 Unsafe_Addss (!simpset); |
108 Unsafe_Addss (!simpset); |
110 |
109 |
111 (*** Basic properties of parallel contraction ***) |
110 (*** Basic properties of parallel contraction ***) |
112 |
111 |
113 goal Comb.thy "!!x z. K#x =1=> z ==> (EX x'. z = K#x' & x =1=> x')"; |
112 goal Comb.thy "!!x z. K#x =1=> z ==> (EX x'. z = K#x' & x =1=> x')"; |
114 by (Fast_tac 1); |
113 by (Blast_tac 1); |
115 qed "K1_parcontractD"; |
114 qed "K1_parcontractD"; |
116 AddSDs [K1_parcontractD]; |
115 AddSDs [K1_parcontractD]; |
117 |
116 |
118 goal Comb.thy "!!x z. S#x =1=> z ==> (EX x'. z = S#x' & x =1=> x')"; |
117 goal Comb.thy "!!x z. S#x =1=> z ==> (EX x'. z = S#x' & x =1=> x')"; |
119 by (Fast_tac 1); |
118 by (Blast_tac 1); |
120 qed "S1_parcontractD"; |
119 qed "S1_parcontractD"; |
121 AddSDs [S1_parcontractD]; |
120 AddSDs [S1_parcontractD]; |
122 |
121 |
123 goal Comb.thy |
122 goal Comb.thy |
124 "!!x y z. S#x#y =1=> z ==> (EX x' y'. z = S#x'#y' & x =1=> x' & y =1=> y')"; |
123 "!!x y z. S#x#y =1=> z ==> (EX x' y'. z = S#x'#y' & x =1=> x' & y =1=> y')"; |
125 by (Fast_tac 1); |
124 by (Blast_tac 1); |
126 qed "S2_parcontractD"; |
125 qed "S2_parcontractD"; |
127 AddSDs [S2_parcontractD]; |
126 AddSDs [S2_parcontractD]; |
128 |
127 |
129 (*The rules above are not essential but make proofs much faster*) |
128 (*The rules above are not essential but make proofs much faster*) |
130 |
129 |
131 |
130 |
132 (*Church-Rosser property for parallel contraction*) |
131 (*Church-Rosser property for parallel contraction*) |
133 goalw Comb.thy [diamond_def] "diamond parcontract"; |
132 goalw Comb.thy [diamond_def] "diamond parcontract"; |
134 by (rtac (impI RS allI RS allI) 1); |
133 by (rtac (impI RS allI RS allI) 1); |
135 by (etac parcontract.induct 1 THEN prune_params_tac); |
134 by (etac parcontract.induct 1 THEN prune_params_tac); |
136 by (ALLGOALS Fast_tac); |
135 by (Step_tac 1); |
|
136 by (ALLGOALS Blast_tac); |
137 qed "diamond_parcontract"; |
137 qed "diamond_parcontract"; |
138 |
138 |
139 |
139 |
140 (*** Equivalence of x--->y and x===>y ***) |
140 (*** Equivalence of x--->y and x===>y ***) |
141 |
141 |
142 goal Comb.thy "contract <= parcontract"; |
142 goal Comb.thy "contract <= parcontract"; |
143 by (rtac subsetI 1); |
143 by (rtac subsetI 1); |
144 by (split_all_tac 1); |
144 by (split_all_tac 1); |
145 by (etac contract.induct 1); |
145 by (etac contract.induct 1); |
146 by (ALLGOALS Fast_tac); |
146 by (ALLGOALS Blast_tac); |
147 qed "contract_subset_parcontract"; |
147 qed "contract_subset_parcontract"; |
148 |
148 |
149 (*Reductions: simply throw together reflexivity, transitivity and |
149 (*Reductions: simply throw together reflexivity, transitivity and |
150 the one-step reductions*) |
150 the one-step reductions*) |
151 |
151 |
152 AddSIs [contract.K, contract.S]; |
|
153 AddIs [Ap_reduce1, Ap_reduce2, r_into_rtrancl, rtrancl_trans]; |
152 AddIs [Ap_reduce1, Ap_reduce2, r_into_rtrancl, rtrancl_trans]; |
154 |
153 |
155 (*Example only: not used*) |
154 (*Example only: not used*) |
156 goalw Comb.thy [I_def] "I#x ---> x"; |
155 goalw Comb.thy [I_def] "I#x ---> x"; |
157 by (Deepen_tac 0 1); |
156 by (Blast_tac 1); |
158 qed "reduce_I"; |
157 qed "reduce_I"; |
159 |
158 |
160 goal Comb.thy "parcontract <= contract^*"; |
159 goal Comb.thy "parcontract <= contract^*"; |
161 by (rtac subsetI 1); |
160 by (rtac subsetI 1); |
162 by (split_all_tac 1); |
161 by (split_all_tac 1); |
163 by (etac parcontract.induct 1 THEN prune_params_tac); |
162 by (etac parcontract.induct 1 THEN prune_params_tac); |
164 by (ALLGOALS (Deepen_tac 0)); |
163 by (ALLGOALS Blast_tac); |
165 qed "parcontract_subset_reduce"; |
164 qed "parcontract_subset_reduce"; |
166 |
165 |
167 goal Comb.thy "contract^* = parcontract^*"; |
166 goal Comb.thy "contract^* = parcontract^*"; |
168 by (REPEAT |
167 by (REPEAT |
169 (resolve_tac [equalityI, |
168 (resolve_tac [equalityI, |