Theory Comb

```(*  Title:      HOL/Induct/Comb.thy
Author:     Lawrence C Paulson
*)

section ‹Combinatory Logic example: the Church-Rosser Theorem›

theory Comb
imports Main
begin

text ‹
Combinator terms do not have free variables.
Example taken from \<^cite>‹camilleri92›.
›

subsection ‹Definitions›

text ‹Datatype definition of combinators ‹S› and ‹K›.›

datatype comb = K
| S
| Ap comb comb (infixl "∙" 90)

text ‹
Inductive definition of contractions, ‹→⇧1› and
(multi-step) reductions, ‹→›.
›

inductive contract1 :: "[comb,comb] ⇒ bool"  (infixl "→⇧1" 50)
where
K:     "K∙x∙y →⇧1 x"
| S:     "S∙x∙y∙z →⇧1 (x∙z)∙(y∙z)"
| Ap1:   "x →⇧1 y ⟹ x∙z →⇧1 y∙z"
| Ap2:   "x →⇧1 y ⟹ z∙x →⇧1 z∙y"

abbreviation
contract :: "[comb,comb] ⇒ bool"   (infixl "→" 50) where
"contract ≡ contract1⇧*⇧*"

text ‹
Inductive definition of parallel contractions, ‹⇛⇧1› and
(multi-step) parallel reductions, ‹⇛›.
›

inductive parcontract1 :: "[comb,comb] ⇒ bool"  (infixl "⇛⇧1" 50)
where
refl:  "x ⇛⇧1 x"
| K:     "K∙x∙y ⇛⇧1 x"
| S:     "S∙x∙y∙z ⇛⇧1 (x∙z)∙(y∙z)"
| Ap:    "⟦x ⇛⇧1 y; z ⇛⇧1 w⟧ ⟹ x∙z ⇛⇧1 y∙w"

abbreviation
parcontract :: "[comb,comb] ⇒ bool"   (infixl "⇛" 50) where
"parcontract ≡ parcontract1⇧*⇧*"

text ‹
Misc definitions.
›

definition
I :: comb where
"I ≡ S∙K∙K"

definition
diamond   :: "([comb,comb] ⇒ bool) ⇒ bool" where
― ‹confluence; Lambda/Commutation treats this more abstractly›
"diamond r ≡ ∀x y. r x y ⟶
(∀y'. r x y' ⟶
(∃z. r y z ∧ r y' z))"

subsection ‹Reflexive/Transitive closure preserves Church-Rosser property›

text‹Remark: So does the Transitive closure, with a similar proof›

text‹Strip lemma.
The induction hypothesis covers all but the last diamond of the strip.›
lemma strip_lemma [rule_format]:
assumes "diamond r" and r: "r⇧*⇧* x y" "r x y'"
shows "∃z. r⇧*⇧* y' z ∧ r y z"
using r
proof (induction rule: rtranclp_induct)
case base
then show ?case
by blast
next
case (step y z)
then show ?case
using ‹diamond r› unfolding diamond_def
by (metis rtranclp.rtrancl_into_rtrancl)
qed

proposition diamond_rtrancl:
assumes "diamond r"
shows "diamond(r⇧*⇧*)"
unfolding diamond_def
proof (intro strip)
fix x y y'
assume "r⇧*⇧* x y" "r⇧*⇧* x y'"
then show "∃z. r⇧*⇧* y z ∧ r⇧*⇧* y' z"
proof (induction rule: rtranclp_induct)
case base
then show ?case
by blast
next
case (step y z)
then show ?case
by (meson assms strip_lemma rtranclp.rtrancl_into_rtrancl)
qed
qed

subsection ‹Non-contraction results›

text ‹Derive a case for each combinator constructor.›

inductive_cases
K_contractE [elim!]: "K →⇧1 r"
and S_contractE [elim!]: "S →⇧1 r"
and Ap_contractE [elim!]: "p∙q →⇧1 r"

declare contract1.K [intro!] contract1.S [intro!]
declare contract1.Ap1 [intro] contract1.Ap2 [intro]

lemma I_contract_E [iff]: "¬ I →⇧1 z"
unfolding I_def by blast

lemma K1_contractD [elim!]: "K∙x →⇧1 z ⟹ (∃x'. z = K∙x' ∧ x →⇧1 x')"
by blast

lemma Ap_reduce1 [intro]: "x → y ⟹ x∙z → y∙z"
by (induction rule: rtranclp_induct; blast intro: rtranclp_trans)

lemma Ap_reduce2 [intro]: "x → y ⟹ z∙x → z∙y"
by (induction rule: rtranclp_induct; blast intro: rtranclp_trans)

text ‹Counterexample to the diamond property for \<^term>‹x →⇧1 y››

lemma not_diamond_contract: "¬ diamond(contract1)"
unfolding diamond_def by (metis S_contractE contract1.K)

text ‹Derive a case for each combinator constructor.›

inductive_cases
K_parcontractE [elim!]: "K ⇛⇧1 r"
and S_parcontractE [elim!]: "S ⇛⇧1 r"
and Ap_parcontractE [elim!]: "p∙q ⇛⇧1 r"

declare parcontract1.intros [intro]

subsection ‹Basic properties of parallel contraction›
text‹The rules below are not essential but make proofs much faster›

lemma K1_parcontractD [dest!]: "K∙x ⇛⇧1 z ⟹ (∃x'. z = K∙x' ∧ x ⇛⇧1 x')"
by blast

lemma S1_parcontractD [dest!]: "S∙x ⇛⇧1 z ⟹ (∃x'. z = S∙x' ∧ x ⇛⇧1 x')"
by blast

lemma S2_parcontractD [dest!]: "S∙x∙y ⇛⇧1 z ⟹ (∃x' y'. z = S∙x'∙y' ∧ x ⇛⇧1 x' ∧ y ⇛⇧1 y')"
by blast

text‹Church-Rosser property for parallel contraction›
proposition diamond_parcontract: "diamond parcontract1"
proof -
have "(∃z. w ⇛⇧1 z ∧ y' ⇛⇧1 z)" if "y ⇛⇧1 w" "y ⇛⇧1 y'" for w y y'
using that by (induction arbitrary: y' rule: parcontract1.induct) fast+
then show ?thesis
by (auto simp: diamond_def)
qed

subsection ‹Equivalence of \<^prop>‹p → q› and \<^prop>‹p ⇛ q›.›

lemma contract_imp_parcontract: "x →⇧1 y ⟹ x ⇛⇧1 y"
by (induction rule: contract1.induct; blast)

text‹Reductions: simply throw together reflexivity, transitivity and
the one-step reductions›

proposition reduce_I: "I∙x → x"
unfolding I_def
by (meson contract1.K contract1.S r_into_rtranclp rtranclp.rtrancl_into_rtrancl)

lemma parcontract_imp_reduce: "x ⇛⇧1 y ⟹ x → y"
proof (induction rule: parcontract1.induct)
case (Ap x y z w)
then show ?case
by (meson Ap_reduce1 Ap_reduce2 rtranclp_trans)
qed auto

lemma reduce_eq_parreduce: "x → y  ⟷  x ⇛ y"
by (metis contract_imp_parcontract parcontract_imp_reduce predicate2I rtranclp_subset)

theorem diamond_reduce: "diamond(contract)"
using diamond_parcontract diamond_rtrancl reduce_eq_parreduce by presburger

end
```