wenzelm@10251: (*  Title:      HOL/Library/While.thy
wenzelm@10251:     ID:         $Id$
wenzelm@10251:     Author:     Tobias Nipkow
wenzelm@10251:     Copyright   2000 TU Muenchen
wenzelm@10251: *)
wenzelm@10251: 
wenzelm@10251: header {*
wenzelm@10251:  \title{A general ``while'' combinator}
wenzelm@10251:  \author{Tobias Nipkow}
wenzelm@10251: *}
wenzelm@10251: 
wenzelm@10251: theory While_Combinator = Main:
wenzelm@10251: 
wenzelm@10251: text {*
wenzelm@10251:  We define a while-combinator @{term while} and prove: (a) an
wenzelm@10251:  unrestricted unfolding law (even if while diverges!)  (I got this
wenzelm@10251:  idea from Wolfgang Goerigk), and (b) the invariant rule for reasoning
wenzelm@10251:  about @{term while}.
wenzelm@10251: *}
wenzelm@10251: 
wenzelm@10251: consts while_aux :: "('a => bool) \<times> ('a => 'a) \<times> 'a => 'a"
wenzelm@10251: recdef while_aux
wenzelm@10251:   "same_fst (\<lambda>b. True) (\<lambda>b. same_fst (\<lambda>c. True) (\<lambda>c.
wenzelm@10251:       {(t, s).  b s \<and> c s = t \<and>
wenzelm@10251:         \<not> (\<exists>f. f 0 = s \<and> (\<forall>i. b (f i) \<and> c (f i) = f (i + 1)))}))"
wenzelm@10251:   "while_aux (b, c, s) =
wenzelm@10251:     (if (\<exists>f. f 0 = s \<and> (\<forall>i. b (f i) \<and> c (f i) = f (i + 1)))
wenzelm@10251:       then arbitrary
wenzelm@10251:       else if b s then while_aux (b, c, c s)
wenzelm@10251:       else s)"
wenzelm@10251: 
wenzelm@10251: constdefs
wenzelm@10251:   while :: "('a => bool) => ('a => 'a) => 'a => 'a"
wenzelm@10251:   "while b c s == while_aux (b, c, s)"
wenzelm@10251: 
wenzelm@10251: ML_setup {*
wenzelm@10251:   goalw_cterm [] (cterm_of (sign_of (the_context ()))
wenzelm@10269:     (HOLogic.mk_Trueprop (hd (RecdefPackage.tcs_of (the_context ()) "while_aux"))));
nipkow@10653:   br wf_same_fst 1;
nipkow@10653:   br wf_same_fst 1;
wenzelm@10251:   by (asm_full_simp_tac (simpset() addsimps [wf_iff_no_infinite_down_chain]) 1);
wenzelm@10251:   by (Blast_tac 1);
wenzelm@10251:   qed "while_aux_tc";
wenzelm@10269: *} (* FIXME cannot access recdef tcs in Isar yet! *)
wenzelm@10251: 
wenzelm@10251: lemma while_aux_unfold:
wenzelm@10251:   "while_aux (b, c, s) =
wenzelm@10251:     (if \<exists>f. f 0 = s \<and> (\<forall>i. b (f i) \<and> c (f i) = f (i + 1))
wenzelm@10251:       then arbitrary
wenzelm@10251:       else if b s then while_aux (b, c, c s)
wenzelm@10251:       else s)"
wenzelm@10251:   apply (rule while_aux_tc [THEN while_aux.simps [THEN trans]])
wenzelm@10251:    apply (simp add: same_fst_def)
wenzelm@10251:   apply (rule refl)
wenzelm@10251:   done
wenzelm@10251: 
wenzelm@10251: text {*
wenzelm@10251:  The recursion equation for @{term while}: directly executable!
wenzelm@10251: *}
wenzelm@10251: 
wenzelm@10251: theorem while_unfold:
wenzelm@10251:     "while b c s = (if b s then while b c (c s) else s)"
wenzelm@10251:   apply (unfold while_def)
wenzelm@10251:   apply (rule while_aux_unfold [THEN trans])
wenzelm@10251:   apply auto
wenzelm@10251:   apply (subst while_aux_unfold)
wenzelm@10251:   apply simp
wenzelm@10251:   apply clarify
wenzelm@10251:   apply (erule_tac x = "\<lambda>i. f (Suc i)" in allE)
wenzelm@10251:   apply blast
wenzelm@10251:   done
wenzelm@10251: 
wenzelm@10251: text {*
wenzelm@10251:  The proof rule for @{term while}, where @{term P} is the invariant.
wenzelm@10251: *}
wenzelm@10251: 
nipkow@10653: theorem while_rule_lemma[rule_format]:
wenzelm@10251:   "(!!s. P s ==> b s ==> P (c s)) ==>
wenzelm@10251:     (!!s. P s ==> \<not> b s ==> Q s) ==>
wenzelm@10251:     wf {(t, s). P s \<and> b s \<and> t = c s} ==>
wenzelm@10251:     P s --> Q (while b c s)"
wenzelm@10251: proof -
wenzelm@10251:   case antecedent
wenzelm@10251:   assume wf: "wf {(t, s). P s \<and> b s \<and> t = c s}"
wenzelm@10251:   show ?thesis
wenzelm@10251:     apply (induct s rule: wf [THEN wf_induct])
wenzelm@10251:     apply simp
wenzelm@10251:     apply clarify
wenzelm@10251:     apply (subst while_unfold)
wenzelm@10251:     apply (simp add: antecedent)
wenzelm@10251:     done
wenzelm@10251: qed
wenzelm@10251: 
nipkow@10653: theorem while_rule:
wenzelm@10673:   "[| P s; !!s. [| P s; b s  |] ==> P (c s);
wenzelm@10673:     !!s. [| P s; \<not> b s  |] ==> Q s;
wenzelm@10673:     wf r;  !!s. [| P s; b s  |] ==> (c s, s) \<in> r |] ==>
nipkow@10653:     Q (while b c s)"
nipkow@10653: apply (rule while_rule_lemma)
nipkow@10653: prefer 4 apply assumption
nipkow@10653: apply blast
nipkow@10653: apply blast
nipkow@10653: apply(erule wf_subset)
nipkow@10653: apply blast
nipkow@10653: done
nipkow@10653: 
wenzelm@10251: hide const while_aux
wenzelm@10251: 
wenzelm@10251: end