(* Title: ZF/ex/comb.ML
ID: $Id$
Author: Lawrence C Paulson
Copyright 1993 University of Cambridge
Combinatory Logic example: the Church-Rosser Theorem
Curiously, combinators do not include free variables.
Example taken from
J. Camilleri and T. F. Melham.
Reasoning with Inductively Defined Relations in the HOL Theorem Prover.
Report 265, University of Cambridge Computer Laboratory, 1992.
HOL system proofs may be found in
/usr/groups/theory/hvg-aftp/contrib/rule-induction/cl.ml
*)
open Comb;
(*** Transitive closure preserves the Church-Rosser property ***)
goalw Comb.thy [diamond_def]
"!!x y r. [| diamond(r); <x,y>:r^+ |] ==> \
\ ALL y'. <x,y'>:r --> (EX z. <y',z>: r^+ & <y,z>: r)";
by (etac trancl_induct 1);
by (blast_tac (claset() addIs [r_into_trancl]) 1);
by (slow_best_tac (claset() addSDs [spec RS mp]
addIs [r_into_trancl, trans_trancl RS transD]) 1);
val diamond_strip_lemmaE = result() RS spec RS mp RS exE;
val [major] = goal Comb.thy "diamond(r) ==> diamond(r^+)";
by (rewtac diamond_def); (*unfold only in goal, not in premise!*)
by (rtac (impI RS allI RS allI) 1);
by (etac trancl_induct 1);
by (ALLGOALS (*Seems to be a brittle, undirected search*)
(slow_best_tac (claset() addIs [r_into_trancl, trans_trancl RS transD]
addEs [major RS diamond_strip_lemmaE])));
qed "diamond_trancl";
val [_,_,comb_Ap] = comb.intrs;
val Ap_E = comb.mk_cases comb.con_defs "p#q : comb";
AddSIs comb.intrs;
AddSEs comb.free_SEs;
(*** Results about Contraction ***)
(*For type checking: replaces a-1->b by a,b:comb *)
val contract_combE2 = contract.dom_subset RS subsetD RS SigmaE2;
val contract_combD1 = contract.dom_subset RS subsetD RS SigmaD1;
val contract_combD2 = contract.dom_subset RS subsetD RS SigmaD2;
goal Comb.thy "field(contract) = comb";
by (blast_tac (claset() addIs [contract.K] addSEs [contract_combE2]) 1);
qed "field_contract_eq";
bind_thm ("reduction_refl",
(field_contract_eq RS equalityD2 RS subsetD RS rtrancl_refl));
bind_thm ("rtrancl_into_rtrancl2",
(r_into_rtrancl RS (trans_rtrancl RS transD)));
AddSIs [reduction_refl, contract.K, contract.S];
val reduction_rls = [contract.K RS rtrancl_into_rtrancl2,
contract.S RS rtrancl_into_rtrancl2,
contract.Ap1 RS rtrancl_into_rtrancl2,
contract.Ap2 RS rtrancl_into_rtrancl2];
(*Example only: not used*)
goalw Comb.thy [I_def] "!!p. p:comb ==> I#p ---> p";
by (blast_tac (claset() addIs reduction_rls) 1);
qed "reduce_I";
goalw Comb.thy [I_def] "I: comb";
by (Blast_tac 1);
qed "comb_I";
(** Non-contraction results **)
(*Derive a case for each combinator constructor*)
val K_contractE = contract.mk_cases comb.con_defs "K -1-> r";
val S_contractE = contract.mk_cases comb.con_defs "S -1-> r";
val Ap_contractE = contract.mk_cases comb.con_defs "p#q -1-> r";
AddIs [contract.Ap1, contract.Ap2];
AddSEs [K_contractE, S_contractE, Ap_contractE];
goalw Comb.thy [I_def] "!!r. I -1-> r ==> P";
by (Blast_tac 1);
qed "I_contract_E";
goal Comb.thy "!!p r. K#p -1-> r ==> (EX q. r = K#q & p -1-> q)";
by (Blast_tac 1);
qed "K1_contractD";
goal Comb.thy "!!p r. [| p ---> q; r: comb |] ==> p#r ---> q#r";
by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
by (etac rtrancl_induct 1);
by (blast_tac (claset() addIs reduction_rls) 1);
by (etac (trans_rtrancl RS transD) 1);
by (blast_tac (claset() addIs (contract_combD2::reduction_rls)) 1);
qed "Ap_reduce1";
goal Comb.thy "!!p r. [| p ---> q; r: comb |] ==> r#p ---> r#q";
by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
by (etac rtrancl_induct 1);
by (blast_tac (claset() addIs reduction_rls) 1);
by (etac (trans_rtrancl RS transD) 1);
by (blast_tac (claset() addIs (contract_combD2::reduction_rls)) 1);
qed "Ap_reduce2";
(** Counterexample to the diamond property for -1-> **)
goal Comb.thy "K#I#(I#I) -1-> I";
by (REPEAT (ares_tac [contract.K, comb_I, comb_Ap] 1));
qed "KIII_contract1";
goalw Comb.thy [I_def] "K#I#(I#I) -1-> K#I#((K#I)#(K#I))";
by (DEPTH_SOLVE (resolve_tac (comb.intrs @ contract.intrs) 1));
qed "KIII_contract2";
goal Comb.thy "K#I#((K#I)#(K#I)) -1-> I";
by (REPEAT (ares_tac (comb.intrs @ [contract.K, comb_I]) 1));
qed "KIII_contract3";
goalw Comb.thy [diamond_def] "~ diamond(contract)";
by (blast_tac (claset() addIs [KIII_contract1,KIII_contract2,KIII_contract3]
addSEs [I_contract_E]) 1);
qed "not_diamond_contract";
(*** Results about Parallel Contraction ***)
(*For type checking: replaces a=1=>b by a,b:comb *)
val parcontract_combE2 = parcontract.dom_subset RS subsetD RS SigmaE2;
val parcontract_combD1 = parcontract.dom_subset RS subsetD RS SigmaD1;
val parcontract_combD2 = parcontract.dom_subset RS subsetD RS SigmaD2;
goal Comb.thy "field(parcontract) = comb";
by (blast_tac (claset() addIs [parcontract.K]
addSEs [parcontract_combE2]) 1);
qed "field_parcontract_eq";
(*Derive a case for each combinator constructor*)
val K_parcontractE = parcontract.mk_cases comb.con_defs "K =1=> r";
val S_parcontractE = parcontract.mk_cases comb.con_defs "S =1=> r";
val Ap_parcontractE = parcontract.mk_cases comb.con_defs "p#q =1=> r";
AddIs parcontract.intrs;
AddSEs [Ap_E, K_parcontractE, S_parcontractE, Ap_parcontractE];
(*** Basic properties of parallel contraction ***)
goal Comb.thy "!!p r. K#p =1=> r ==> (EX p'. r = K#p' & p =1=> p')";
by (Blast_tac 1);
qed "K1_parcontractD";
goal Comb.thy "!!p r. S#p =1=> r ==> (EX p'. r = S#p' & p =1=> p')";
by (Blast_tac 1);
qed "S1_parcontractD";
goal Comb.thy
"!!p q r. S#p#q =1=> r ==> (EX p' q'. r = S#p'#q' & p =1=> p' & q =1=> q')";
by (blast_tac (claset() addSDs [S1_parcontractD]) 1);
qed "S2_parcontractD";
(*Church-Rosser property for parallel contraction*)
goalw Comb.thy [diamond_def] "diamond(parcontract)";
by (rtac (impI RS allI RS allI) 1);
by (etac parcontract.induct 1);
by (ALLGOALS
(blast_tac (claset() addSDs [K1_parcontractD, S2_parcontractD]
addIs [parcontract_combD2])));
qed "diamond_parcontract";
(*** Equivalence of p--->q and p===>q ***)
goal Comb.thy "!!p q. p-1->q ==> p=1=>q";
by (etac contract.induct 1);
by (ALLGOALS Blast_tac);
qed "contract_imp_parcontract";
goal Comb.thy "!!p q. p--->q ==> p===>q";
by (forward_tac [rtrancl_type RS subsetD RS SigmaD1] 1);
by (dtac (field_contract_eq RS equalityD1 RS subsetD) 1);
by (etac rtrancl_induct 1);
by (blast_tac (claset() addIs [r_into_trancl]) 1);
by (blast_tac (claset() addIs [contract_imp_parcontract,
r_into_trancl, trans_trancl RS transD]) 1);
qed "reduce_imp_parreduce";
goal Comb.thy "!!p q. p=1=>q ==> p--->q";
by (etac parcontract.induct 1);
by (blast_tac (claset() addIs reduction_rls) 1);
by (blast_tac (claset() addIs reduction_rls) 1);
by (blast_tac (claset() addIs reduction_rls) 1);
by (blast_tac
(claset() addIs [trans_rtrancl RS transD,
Ap_reduce1, Ap_reduce2, parcontract_combD1,
parcontract_combD2]) 1);
qed "parcontract_imp_reduce";
goal Comb.thy "!!p q. p===>q ==> p--->q";
by (forward_tac [trancl_type RS subsetD RS SigmaD1] 1);
by (dtac (field_parcontract_eq RS equalityD1 RS subsetD) 1);
by (etac trancl_induct 1);
by (etac parcontract_imp_reduce 1);
by (etac (trans_rtrancl RS transD) 1);
by (etac parcontract_imp_reduce 1);
qed "parreduce_imp_reduce";
goal Comb.thy "p===>q <-> p--->q";
by (REPEAT (ares_tac [iffI, parreduce_imp_reduce, reduce_imp_parreduce] 1));
qed "parreduce_iff_reduce";
writeln"Reached end of file.";