src/HOL/Induct/Comb.thy
author urbanc
Tue Jun 05 09:56:19 2007 +0200 (2007-06-05)
changeset 23243 a37d3e6e8323
parent 21404 eb85850d3eb7
child 23746 a455e69c31cc
permissions -rw-r--r--
included Class.thy in the compiling process for Nominal/Examples
paulson@13075
     1
(*  Title:      HOL/Induct/Comb.thy
paulson@3120
     2
    ID:         $Id$
paulson@3120
     3
    Author:     Lawrence C Paulson
paulson@3120
     4
    Copyright   1996  University of Cambridge
paulson@3120
     5
*)
paulson@3120
     6
paulson@13075
     7
header {* Combinatory Logic example: the Church-Rosser Theorem *}
paulson@3120
     8
haftmann@16417
     9
theory Comb imports Main begin
paulson@13075
    10
paulson@13075
    11
text {*
paulson@13075
    12
  Curiously, combinators do not include free variables.
paulson@13075
    13
paulson@13075
    14
  Example taken from \cite{camilleri-melham}.
paulson@3120
    15
paulson@13075
    16
HOL system proofs may be found in the HOL distribution at
paulson@13075
    17
   .../contrib/rule-induction/cl.ml
paulson@13075
    18
*}
paulson@13075
    19
paulson@13075
    20
subsection {* Definitions *}
paulson@13075
    21
paulson@13075
    22
text {* Datatype definition of combinators @{text S} and @{text K}. *}
paulson@13075
    23
paulson@3120
    24
datatype comb = K
paulson@3120
    25
              | S
wenzelm@19736
    26
              | Ap comb comb (infixl "##" 90)
wenzelm@19736
    27
wenzelm@21210
    28
notation (xsymbols)
wenzelm@19736
    29
  Ap  (infixl "\<bullet>" 90)
wenzelm@19736
    30
paulson@3120
    31
paulson@13075
    32
text {*
paulson@13075
    33
  Inductive definition of contractions, @{text "-1->"} and
paulson@13075
    34
  (multi-step) reductions, @{text "--->"}.
paulson@13075
    35
*}
paulson@13075
    36
paulson@3120
    37
consts
paulson@3120
    38
  contract  :: "(comb*comb) set"
paulson@3120
    39
wenzelm@19736
    40
abbreviation
wenzelm@21404
    41
  contract_rel1 :: "[comb,comb] => bool"   (infixl "-1->" 50) where
wenzelm@19736
    42
  "x -1-> y == (x,y) \<in> contract"
wenzelm@21404
    43
wenzelm@21404
    44
abbreviation
wenzelm@21404
    45
  contract_rel :: "[comb,comb] => bool"   (infixl "--->" 50) where
wenzelm@19736
    46
  "x ---> y == (x,y) \<in> contract^*"
paulson@15816
    47
paulson@3120
    48
inductive contract
paulson@13075
    49
  intros
paulson@13075
    50
    K:     "K##x##y -1-> x"
paulson@13075
    51
    S:     "S##x##y##z -1-> (x##z)##(y##z)"
paulson@13075
    52
    Ap1:   "x-1->y ==> x##z -1-> y##z"
paulson@13075
    53
    Ap2:   "x-1->y ==> z##x -1-> z##y"
paulson@3120
    54
paulson@13075
    55
text {*
paulson@13075
    56
  Inductive definition of parallel contractions, @{text "=1=>"} and
paulson@13075
    57
  (multi-step) parallel reductions, @{text "===>"}.
paulson@13075
    58
*}
paulson@3120
    59
paulson@3120
    60
consts
paulson@3120
    61
  parcontract :: "(comb*comb) set"
paulson@3120
    62
wenzelm@19736
    63
abbreviation
wenzelm@21404
    64
  parcontract_rel1 :: "[comb,comb] => bool"   (infixl "=1=>" 50) where
wenzelm@19736
    65
  "x =1=> y == (x,y) \<in> parcontract"
wenzelm@21404
    66
wenzelm@21404
    67
abbreviation
wenzelm@21404
    68
  parcontract_rel :: "[comb,comb] => bool"   (infixl "===>" 50) where
wenzelm@19736
    69
  "x ===> y == (x,y) \<in> parcontract^*"
paulson@3120
    70
paulson@3120
    71
inductive parcontract
paulson@13075
    72
  intros
paulson@13075
    73
    refl:  "x =1=> x"
paulson@13075
    74
    K:     "K##x##y =1=> x"
paulson@13075
    75
    S:     "S##x##y##z =1=> (x##z)##(y##z)"
paulson@13075
    76
    Ap:    "[| x=1=>y;  z=1=>w |] ==> x##z =1=> y##w"
paulson@3120
    77
paulson@13075
    78
text {*
paulson@13075
    79
  Misc definitions.
paulson@13075
    80
*}
paulson@3120
    81
wenzelm@19736
    82
definition
wenzelm@21404
    83
  I :: comb where
wenzelm@19736
    84
  "I = S##K##K"
paulson@3120
    85
wenzelm@21404
    86
definition
wenzelm@21404
    87
  diamond   :: "('a * 'a)set => bool" where
paulson@13075
    88
    --{*confluence; Lambda/Commutation treats this more abstractly*}
wenzelm@19736
    89
  "diamond(r) = (\<forall>x y. (x,y) \<in> r --> 
paulson@13075
    90
                  (\<forall>y'. (x,y') \<in> r --> 
wenzelm@19736
    91
                    (\<exists>z. (y,z) \<in> r & (y',z) \<in> r)))"
paulson@13075
    92
paulson@13075
    93
paulson@13075
    94
subsection {*Reflexive/Transitive closure preserves Church-Rosser property*}
paulson@13075
    95
paulson@13075
    96
text{*So does the Transitive closure, with a similar proof*}
paulson@13075
    97
paulson@13075
    98
text{*Strip lemma.  
paulson@13075
    99
   The induction hypothesis covers all but the last diamond of the strip.*}
paulson@13075
   100
lemma diamond_strip_lemmaE [rule_format]: 
paulson@13075
   101
    "[| diamond(r);  (x,y) \<in> r^* |] ==>   
paulson@13075
   102
          \<forall>y'. (x,y') \<in> r --> (\<exists>z. (y',z) \<in> r^* & (y,z) \<in> r)"
paulson@13075
   103
apply (unfold diamond_def)
paulson@16563
   104
apply (erule rtrancl_induct)
paulson@16563
   105
apply (meson rtrancl_refl)
paulson@16563
   106
apply (meson rtrancl_trans r_into_rtrancl)
paulson@13075
   107
done
paulson@13075
   108
paulson@13075
   109
lemma diamond_rtrancl: "diamond(r) ==> diamond(r^*)"
paulson@13075
   110
apply (simp (no_asm_simp) add: diamond_def)
paulson@13075
   111
apply (rule impI [THEN allI, THEN allI])
paulson@13075
   112
apply (erule rtrancl_induct, blast)
paulson@16588
   113
apply (meson rtrancl_trans r_into_rtrancl diamond_strip_lemmaE)
paulson@13075
   114
done
paulson@13075
   115
paulson@13075
   116
paulson@13075
   117
subsection {* Non-contraction results *}
paulson@13075
   118
paulson@13075
   119
text {* Derive a case for each combinator constructor. *}
paulson@13075
   120
paulson@13075
   121
inductive_cases
paulson@13075
   122
      K_contractE [elim!]: "K -1-> r"
paulson@13075
   123
  and S_contractE [elim!]: "S -1-> r"
paulson@13075
   124
  and Ap_contractE [elim!]: "p##q -1-> r"
paulson@13075
   125
paulson@13075
   126
declare contract.K [intro!] contract.S [intro!]
paulson@13075
   127
declare contract.Ap1 [intro] contract.Ap2 [intro]
paulson@13075
   128
paulson@13075
   129
lemma I_contract_E [elim!]: "I -1-> z ==> P"
paulson@13075
   130
by (unfold I_def, blast)
paulson@13075
   131
paulson@13075
   132
lemma K1_contractD [elim!]: "K##x -1-> z ==> (\<exists>x'. z = K##x' & x -1-> x')"
paulson@13075
   133
by blast
paulson@13075
   134
paulson@13075
   135
lemma Ap_reduce1 [intro]: "x ---> y ==> x##z ---> y##z"
paulson@13075
   136
apply (erule rtrancl_induct)
paulson@13075
   137
apply (blast intro: rtrancl_trans)+
paulson@13075
   138
done
paulson@13075
   139
paulson@13075
   140
lemma Ap_reduce2 [intro]: "x ---> y ==> z##x ---> z##y"
paulson@13075
   141
apply (erule rtrancl_induct)
paulson@13075
   142
apply (blast intro: rtrancl_trans)+
paulson@13075
   143
done
paulson@13075
   144
paulson@13075
   145
(** Counterexample to the diamond property for -1-> **)
paulson@13075
   146
paulson@13075
   147
lemma KIII_contract1: "K##I##(I##I) -1-> I"
paulson@13075
   148
by (rule contract.K)
paulson@13075
   149
paulson@13075
   150
lemma KIII_contract2: "K##I##(I##I) -1-> K##I##((K##I)##(K##I))"
paulson@13075
   151
by (unfold I_def, blast)
paulson@13075
   152
paulson@13075
   153
lemma KIII_contract3: "K##I##((K##I)##(K##I)) -1-> I"
paulson@13075
   154
by blast
paulson@13075
   155
paulson@13075
   156
lemma not_diamond_contract: "~ diamond(contract)"
paulson@13075
   157
apply (unfold diamond_def) 
paulson@13075
   158
apply (best intro: KIII_contract1 KIII_contract2 KIII_contract3)
paulson@13075
   159
done
paulson@13075
   160
paulson@13075
   161
paulson@13075
   162
subsection {* Results about Parallel Contraction *}
paulson@13075
   163
paulson@13075
   164
text {* Derive a case for each combinator constructor. *}
paulson@13075
   165
paulson@13075
   166
inductive_cases
paulson@13075
   167
      K_parcontractE [elim!]: "K =1=> r"
paulson@13075
   168
  and S_parcontractE [elim!]: "S =1=> r"
paulson@13075
   169
  and Ap_parcontractE [elim!]: "p##q =1=> r"
paulson@13075
   170
paulson@13075
   171
declare parcontract.intros [intro]
paulson@13075
   172
paulson@13075
   173
(*** Basic properties of parallel contraction ***)
paulson@13075
   174
paulson@13075
   175
subsection {* Basic properties of parallel contraction *}
paulson@13075
   176
paulson@13075
   177
lemma K1_parcontractD [dest!]: "K##x =1=> z ==> (\<exists>x'. z = K##x' & x =1=> x')"
paulson@13075
   178
by blast
paulson@13075
   179
paulson@13075
   180
lemma S1_parcontractD [dest!]: "S##x =1=> z ==> (\<exists>x'. z = S##x' & x =1=> x')"
paulson@13075
   181
by blast
paulson@13075
   182
paulson@13075
   183
lemma S2_parcontractD [dest!]:
paulson@13075
   184
     "S##x##y =1=> z ==> (\<exists>x' y'. z = S##x'##y' & x =1=> x' & y =1=> y')"
paulson@13075
   185
by blast
paulson@13075
   186
paulson@13075
   187
text{*The rules above are not essential but make proofs much faster*}
paulson@13075
   188
paulson@13075
   189
text{*Church-Rosser property for parallel contraction*}
paulson@13075
   190
lemma diamond_parcontract: "diamond parcontract"
paulson@13075
   191
apply (unfold diamond_def)
paulson@13075
   192
apply (rule impI [THEN allI, THEN allI])
paulson@13075
   193
apply (erule parcontract.induct, fast+)
paulson@13075
   194
done
paulson@13075
   195
paulson@13075
   196
text {*
paulson@13075
   197
  \medskip Equivalence of @{prop "p ---> q"} and @{prop "p ===> q"}.
paulson@13075
   198
*}
paulson@13075
   199
paulson@13075
   200
lemma contract_subset_parcontract: "contract <= parcontract"
paulson@13075
   201
apply (rule subsetI)
paulson@13075
   202
apply (simp only: split_tupled_all)
paulson@13075
   203
apply (erule contract.induct, blast+)
paulson@13075
   204
done
paulson@13075
   205
paulson@13075
   206
text{*Reductions: simply throw together reflexivity, transitivity and
paulson@13075
   207
  the one-step reductions*}
paulson@13075
   208
paulson@13075
   209
declare r_into_rtrancl [intro]  rtrancl_trans [intro]
paulson@13075
   210
paulson@13075
   211
(*Example only: not used*)
paulson@13075
   212
lemma reduce_I: "I##x ---> x"
paulson@13075
   213
by (unfold I_def, blast)
paulson@13075
   214
paulson@13075
   215
lemma parcontract_subset_reduce: "parcontract <= contract^*"
paulson@13075
   216
apply (rule subsetI)
paulson@13075
   217
apply (simp only: split_tupled_all)
paulson@16563
   218
apply (erule parcontract.induct, blast+)
paulson@13075
   219
done
paulson@13075
   220
paulson@13075
   221
lemma reduce_eq_parreduce: "contract^* = parcontract^*"
paulson@13075
   222
by (rule equalityI contract_subset_parcontract [THEN rtrancl_mono] 
paulson@13075
   223
         parcontract_subset_reduce [THEN rtrancl_subset_rtrancl])+
paulson@13075
   224
paulson@13075
   225
lemma diamond_reduce: "diamond(contract^*)"
paulson@13075
   226
by (simp add: reduce_eq_parreduce diamond_rtrancl diamond_parcontract)
paulson@3120
   227
paulson@3120
   228
end