src/HOL/Induct/Exp.ML
changeset 5069 3ea049f7979d
parent 4477 b3e5857d8d99
child 5143 b94cd208f073
equal deleted inserted replaced
5068:fb28eaa07e01 5069:3ea049f7979d
    18    ];
    18    ];
    19 
    19 
    20 AddSEs eval_elim_cases;
    20 AddSEs eval_elim_cases;
    21 
    21 
    22 
    22 
    23 goal thy "(X x, s[n/x]) -|-> (n, s[n/x])";
    23 Goal "(X x, s[n/x]) -|-> (n, s[n/x])";
    24 by (rtac (assign_same RS subst) 1 THEN resolve_tac eval.intrs 1);
    24 by (rtac (assign_same RS subst) 1 THEN resolve_tac eval.intrs 1);
    25 qed "var_assign_eval";
    25 qed "var_assign_eval";
    26 
    26 
    27 AddSIs [var_assign_eval];
    27 AddSIs [var_assign_eval];
    28 
    28 
    29 
    29 
    30 (** Make the induction rule look nicer -- though eta_contract makes the new
    30 (** Make the induction rule look nicer -- though eta_contract makes the new
    31     version look worse than it is...**)
    31     version look worse than it is...**)
    32 
    32 
    33 goal thy "{((e,s),(n,s')). P e s n s'} = \
    33 Goal "{((e,s),(n,s')). P e s n s'} = \
    34 \         Collect (split (%v. split (split P v)))";
    34 \         Collect (split (%v. split (split P v)))";
    35 by (rtac Collect_cong 1);
    35 by (rtac Collect_cong 1);
    36 by (split_all_tac 1);
    36 by (split_all_tac 1);
    37 by (Simp_tac 1);
    37 by (Simp_tac 1);
    38 val split_lemma = result();
    38 val split_lemma = result();
    65   using eval restricted to its functional part.  Note that the execution
    65   using eval restricted to its functional part.  Note that the execution
    66   (c,s) -[eval]-> s2 can use unrestricted eval!  The reason is that 
    66   (c,s) -[eval]-> s2 can use unrestricted eval!  The reason is that 
    67   the execution (c,s) -[eval Int {...}]-> s1 assures us that execution is
    67   the execution (c,s) -[eval Int {...}]-> s1 assures us that execution is
    68   functional on the argument (c,s).
    68   functional on the argument (c,s).
    69 *)
    69 *)
    70 goal thy
    70 Goal
    71     "!!x. (c,s) -[eval Int {((e,s),(n,s')). Unique (e,s) (n,s') eval}]-> s1 \
    71     "!!x. (c,s) -[eval Int {((e,s),(n,s')). Unique (e,s) (n,s') eval}]-> s1 \
    72 \         ==> (ALL s2. (c,s) -[eval]-> s2 --> s2=s1)";
    72 \         ==> (ALL s2. (c,s) -[eval]-> s2 --> s2=s1)";
    73 by (etac exec.induct 1);
    73 by (etac exec.induct 1);
    74 by (ALLGOALS Full_simp_tac);
    74 by (ALLGOALS Full_simp_tac);
    75 by (Blast_tac 3);
    75 by (Blast_tac 3);
    85 by (ALLGOALS Fast_tac);         (*Blast_tac: proof fails*)
    85 by (ALLGOALS Fast_tac);         (*Blast_tac: proof fails*)
    86 qed "com_Unique";
    86 qed "com_Unique";
    87 
    87 
    88 
    88 
    89 (*Expression evaluation is functional, or deterministic*)
    89 (*Expression evaluation is functional, or deterministic*)
    90 goalw thy [Function_def] "Function eval";
    90 Goalw [Function_def] "Function eval";
    91 by (strip_tac 1);
    91 by (strip_tac 1);
    92 by (split_all_tac 1);
    92 by (split_all_tac 1);
    93 by (etac eval_induct 1);
    93 by (etac eval_induct 1);
    94 by (dtac com_Unique 4);
    94 by (dtac com_Unique 4);
    95 by (ALLGOALS (full_simp_tac (simpset() addsimps [Unique_def])));
    95 by (ALLGOALS (full_simp_tac (simpset() addsimps [Unique_def])));
    96 by (ALLGOALS Blast_tac);
    96 by (ALLGOALS Blast_tac);
    97 qed "Function_eval";
    97 qed "Function_eval";
    98 
    98 
    99 
    99 
   100 goal thy "!!x. (e,s) -|-> (v,s') ==> (e = N n) --> (v=n & s'=s)";
   100 Goal "!!x. (e,s) -|-> (v,s') ==> (e = N n) --> (v=n & s'=s)";
   101 by (etac eval_induct 1);
   101 by (etac eval_induct 1);
   102 by (ALLGOALS Asm_simp_tac);
   102 by (ALLGOALS Asm_simp_tac);
   103 val lemma = result();
   103 val lemma = result();
   104 bind_thm ("eval_N_E", refl RSN (2, lemma RS mp));
   104 bind_thm ("eval_N_E", refl RSN (2, lemma RS mp));
   105 
   105 
   106 AddSEs [eval_N_E];
   106 AddSEs [eval_N_E];
   107 
   107 
   108 
   108 
   109 (*This theorem says that "WHILE TRUE DO c" cannot terminate*)
   109 (*This theorem says that "WHILE TRUE DO c" cannot terminate*)
   110 goal thy "!!x. (c', s) -[eval]-> t ==> (c' = WHILE (N 0) DO c) --> False";
   110 Goal "!!x. (c', s) -[eval]-> t ==> (c' = WHILE (N 0) DO c) --> False";
   111 by (etac exec.induct 1);
   111 by (etac exec.induct 1);
   112 by Auto_tac;
   112 by Auto_tac;
   113 bind_thm ("while_true_E", refl RSN (2, result() RS mp));
   113 bind_thm ("while_true_E", refl RSN (2, result() RS mp));
   114 
   114 
   115 
   115 
   116 (** Equivalence of IF e THEN c;;(WHILE e DO c) ELSE SKIP  and  WHILE e DO c **)
   116 (** Equivalence of IF e THEN c;;(WHILE e DO c) ELSE SKIP  and  WHILE e DO c **)
   117 
   117 
   118 goal thy "!!x. (c',s) -[eval]-> t ==> \
   118 Goal "!!x. (c',s) -[eval]-> t ==> \
   119 \              (c' = WHILE e DO c) --> \
   119 \              (c' = WHILE e DO c) --> \
   120 \              (IF e THEN c;;c' ELSE SKIP, s) -[eval]-> t";
   120 \              (IF e THEN c;;c' ELSE SKIP, s) -[eval]-> t";
   121 by (etac exec.induct 1);
   121 by (etac exec.induct 1);
   122 by (ALLGOALS Asm_simp_tac);
   122 by (ALLGOALS Asm_simp_tac);
   123 by (ALLGOALS Blast_tac); 
   123 by (ALLGOALS Blast_tac); 
   124 bind_thm ("while_if1", refl RSN (2, result() RS mp));
   124 bind_thm ("while_if1", refl RSN (2, result() RS mp));
   125 
   125 
   126 
   126 
   127 goal thy "!!x. (c',s) -[eval]-> t ==> \
   127 Goal "!!x. (c',s) -[eval]-> t ==> \
   128 \              (c' = IF e THEN c;;(WHILE e DO c) ELSE SKIP) --> \
   128 \              (c' = IF e THEN c;;(WHILE e DO c) ELSE SKIP) --> \
   129 \              (WHILE e DO c, s) -[eval]-> t";
   129 \              (WHILE e DO c, s) -[eval]-> t";
   130 by (etac exec.induct 1);
   130 by (etac exec.induct 1);
   131 by (ALLGOALS Asm_simp_tac);
   131 by (ALLGOALS Asm_simp_tac);
   132 by (ALLGOALS Blast_tac); 
   132 by (ALLGOALS Blast_tac); 
   133 bind_thm ("while_if2", refl RSN (2, result() RS mp));
   133 bind_thm ("while_if2", refl RSN (2, result() RS mp));
   134 
   134 
   135 
   135 
   136 goal thy "((IF e THEN c;;(WHILE e DO c) ELSE SKIP, s) -[eval]-> t)  =  \
   136 Goal "((IF e THEN c;;(WHILE e DO c) ELSE SKIP, s) -[eval]-> t)  =  \
   137 \         ((WHILE e DO c, s) -[eval]-> t)";
   137 \         ((WHILE e DO c, s) -[eval]-> t)";
   138 by (blast_tac (claset() addIs [while_if1, while_if2]) 1);
   138 by (blast_tac (claset() addIs [while_if1, while_if2]) 1);
   139 qed "while_if";
   139 qed "while_if";
   140 
   140 
   141 
   141 
   142 
   142 
   143 (** Equivalence of  (IF e THEN c1 ELSE c2);;c
   143 (** Equivalence of  (IF e THEN c1 ELSE c2);;c
   144                and  IF e THEN (c1;;c) ELSE (c2;;c)   **)
   144                and  IF e THEN (c1;;c) ELSE (c2;;c)   **)
   145 
   145 
   146 goal thy "!!x. (c',s) -[eval]-> t ==> \
   146 Goal "!!x. (c',s) -[eval]-> t ==> \
   147 \              (c' = (IF e THEN c1 ELSE c2);;c) --> \
   147 \              (c' = (IF e THEN c1 ELSE c2);;c) --> \
   148 \              (IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t";
   148 \              (IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t";
   149 by (etac exec.induct 1);
   149 by (etac exec.induct 1);
   150 by (ALLGOALS Asm_simp_tac);
   150 by (ALLGOALS Asm_simp_tac);
   151 by (Blast_tac 1); 
   151 by (Blast_tac 1); 
   152 bind_thm ("if_semi1", refl RSN (2, result() RS mp));
   152 bind_thm ("if_semi1", refl RSN (2, result() RS mp));
   153 
   153 
   154 
   154 
   155 goal thy "!!x. (c',s) -[eval]-> t ==> \
   155 Goal "!!x. (c',s) -[eval]-> t ==> \
   156 \              (c' = IF e THEN (c1;;c) ELSE (c2;;c)) --> \
   156 \              (c' = IF e THEN (c1;;c) ELSE (c2;;c)) --> \
   157 \              ((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t";
   157 \              ((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t";
   158 by (etac exec.induct 1);
   158 by (etac exec.induct 1);
   159 by (ALLGOALS Asm_simp_tac);
   159 by (ALLGOALS Asm_simp_tac);
   160 by (ALLGOALS Blast_tac); 
   160 by (ALLGOALS Blast_tac); 
   161 bind_thm ("if_semi2", refl RSN (2, result() RS mp));
   161 bind_thm ("if_semi2", refl RSN (2, result() RS mp));
   162 
   162 
   163 
   163 
   164 goal thy "(((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t)  =  \
   164 Goal "(((IF e THEN c1 ELSE c2);;c, s) -[eval]-> t)  =  \
   165 \         ((IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t)";
   165 \         ((IF e THEN (c1;;c) ELSE (c2;;c), s) -[eval]-> t)";
   166 by (blast_tac (claset() addIs [if_semi1, if_semi2]) 1);
   166 by (blast_tac (claset() addIs [if_semi1, if_semi2]) 1);
   167 qed "if_semi";
   167 qed "if_semi";
   168 
   168 
   169 
   169 
   170 
   170 
   171 (** Equivalence of  VALOF c1 RESULTIS (VALOF c2 RESULTIS e)
   171 (** Equivalence of  VALOF c1 RESULTIS (VALOF c2 RESULTIS e)
   172                and  VALOF c1;;c2 RESULTIS e
   172                and  VALOF c1;;c2 RESULTIS e
   173  **)
   173  **)
   174 
   174 
   175 goal thy "!!x. (e',s) -|-> (v,s') ==> \
   175 Goal "!!x. (e',s) -|-> (v,s') ==> \
   176 \              (e' = VALOF c1 RESULTIS (VALOF c2 RESULTIS e)) --> \
   176 \              (e' = VALOF c1 RESULTIS (VALOF c2 RESULTIS e)) --> \
   177 \              (VALOF c1;;c2 RESULTIS e, s) -|-> (v,s')";
   177 \              (VALOF c1;;c2 RESULTIS e, s) -|-> (v,s')";
   178 by (etac eval_induct 1);
   178 by (etac eval_induct 1);
   179 by (ALLGOALS Asm_simp_tac);
   179 by (ALLGOALS Asm_simp_tac);
   180 by (Blast_tac 1); 
   180 by (Blast_tac 1); 
   181 bind_thm ("valof_valof1", refl RSN (2, result() RS mp));
   181 bind_thm ("valof_valof1", refl RSN (2, result() RS mp));
   182 
   182 
   183 
   183 
   184 goal thy "!!x. (e',s) -|-> (v,s') ==> \
   184 Goal "!!x. (e',s) -|-> (v,s') ==> \
   185 \              (e' = VALOF c1;;c2 RESULTIS e) --> \
   185 \              (e' = VALOF c1;;c2 RESULTIS e) --> \
   186 \              (VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s')";
   186 \              (VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s')";
   187 by (etac eval_induct 1);
   187 by (etac eval_induct 1);
   188 by (ALLGOALS Asm_simp_tac);
   188 by (ALLGOALS Asm_simp_tac);
   189 by (Blast_tac 1); 
   189 by (Blast_tac 1); 
   190 bind_thm ("valof_valof2", refl RSN (2, result() RS mp));
   190 bind_thm ("valof_valof2", refl RSN (2, result() RS mp));
   191 
   191 
   192 
   192 
   193 goal thy "((VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s'))  =  \
   193 Goal "((VALOF c1 RESULTIS (VALOF c2 RESULTIS e), s) -|-> (v,s'))  =  \
   194 \         ((VALOF c1;;c2 RESULTIS e, s) -|-> (v,s'))";
   194 \         ((VALOF c1;;c2 RESULTIS e, s) -|-> (v,s'))";
   195 by (blast_tac (claset() addIs [valof_valof1, valof_valof2]) 1);
   195 by (blast_tac (claset() addIs [valof_valof1, valof_valof2]) 1);
   196 qed "valof_valof";
   196 qed "valof_valof";
   197 
   197 
   198 
   198 
   199 (** Equivalence of  VALOF SKIP RESULTIS e  and  e **)
   199 (** Equivalence of  VALOF SKIP RESULTIS e  and  e **)
   200 
   200 
   201 goal thy "!!x. (e',s) -|-> (v,s') ==> \
   201 Goal "!!x. (e',s) -|-> (v,s') ==> \
   202 \              (e' = VALOF SKIP RESULTIS e) --> \
   202 \              (e' = VALOF SKIP RESULTIS e) --> \
   203 \              (e, s) -|-> (v,s')";
   203 \              (e, s) -|-> (v,s')";
   204 by (etac eval_induct 1);
   204 by (etac eval_induct 1);
   205 by (ALLGOALS Asm_simp_tac);
   205 by (ALLGOALS Asm_simp_tac);
   206 by (Blast_tac 1); 
   206 by (Blast_tac 1); 
   207 bind_thm ("valof_skip1", refl RSN (2, result() RS mp));
   207 bind_thm ("valof_skip1", refl RSN (2, result() RS mp));
   208 
   208 
   209 goal thy "!!x. (e,s) -|-> (v,s') ==> (VALOF SKIP RESULTIS e, s) -|-> (v,s')";
   209 Goal "!!x. (e,s) -|-> (v,s') ==> (VALOF SKIP RESULTIS e, s) -|-> (v,s')";
   210 by (Blast_tac 1);
   210 by (Blast_tac 1);
   211 qed "valof_skip2";
   211 qed "valof_skip2";
   212 
   212 
   213 goal thy "((VALOF SKIP RESULTIS e, s) -|-> (v,s'))  =  ((e, s) -|-> (v,s'))";
   213 Goal "((VALOF SKIP RESULTIS e, s) -|-> (v,s'))  =  ((e, s) -|-> (v,s'))";
   214 by (blast_tac (claset() addIs [valof_skip1, valof_skip2]) 1);
   214 by (blast_tac (claset() addIs [valof_skip1, valof_skip2]) 1);
   215 qed "valof_skip";
   215 qed "valof_skip";
   216 
   216 
   217 
   217 
   218 (** Equivalence of  VALOF x:=e RESULTIS x  and  e **)
   218 (** Equivalence of  VALOF x:=e RESULTIS x  and  e **)
   219 
   219 
   220 goal thy "!!x. (e',s) -|-> (v,s'') ==> \
   220 Goal "!!x. (e',s) -|-> (v,s'') ==> \
   221 \              (e' = VALOF x:=e RESULTIS X x) --> \
   221 \              (e' = VALOF x:=e RESULTIS X x) --> \
   222 \              (EX s'. (e, s) -|-> (v,s') & (s'' = s'[v/x]))";
   222 \              (EX s'. (e, s) -|-> (v,s') & (s'' = s'[v/x]))";
   223 by (etac eval_induct 1);
   223 by (etac eval_induct 1);
   224 by (ALLGOALS Asm_simp_tac);
   224 by (ALLGOALS Asm_simp_tac);
   225 by (thin_tac "?PP-->?QQ" 1);
   225 by (thin_tac "?PP-->?QQ" 1);
   227 by (Simp_tac 1);
   227 by (Simp_tac 1);
   228 by (Blast_tac 1); 
   228 by (Blast_tac 1); 
   229 bind_thm ("valof_assign1", refl RSN (2, result() RS mp));
   229 bind_thm ("valof_assign1", refl RSN (2, result() RS mp));
   230 
   230 
   231 
   231 
   232 goal thy "!!x. (e,s) -|-> (v,s') ==> \
   232 Goal "!!x. (e,s) -|-> (v,s') ==> \
   233 \              (VALOF x:=e RESULTIS X x, s) -|-> (v,s'[v/x])";
   233 \              (VALOF x:=e RESULTIS X x, s) -|-> (v,s'[v/x])";
   234 by (Blast_tac 1);
   234 by (Blast_tac 1);
   235 qed "valof_assign2";
   235 qed "valof_assign2";