Impressum Comb.thy

(*  Title:      HOL/Induct/Comb.thy
  Author: Lawrence C Paulson
  Copyright 1996 University of Cambridge
*)

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

theory Comb
imports Main
begin

text ‹
  Combinator terms do not have free variables.
  Example taken from 🍋‹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 🍋‹x →🪙1 y›\›

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


subsection ‹Results about Parallel Contraction›

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 🍋‹p → q› and 🍋‹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