src/HOL/Hoare/Examples.ML
changeset 6162 484adda70b65
parent 5983 79e301a6a51b
child 6802 655a16e16c01
equal deleted inserted replaced
6161:bc2a76ce1ea3 6162:484adda70b65
    12 \  {m=0 & s=0} \
    12 \  {m=0 & s=0} \
    13 \  WHILE m~=a \
    13 \  WHILE m~=a \
    14 \  INV {s=m*b} \  
    14 \  INV {s=m*b} \  
    15 \  DO s := s+b; m := m+1 OD \
    15 \  DO s := s+b; m := m+1 OD \
    16 \  {s = a*b}";
    16 \  {s = a*b}";
    17 by(hoare_tac (Asm_full_simp_tac) 1);
    17 by (hoare_tac (Asm_full_simp_tac) 1);
    18 qed "multiply_by_add";
    18 qed "multiply_by_add";
    19 
    19 
    20 (*** Euclid's algorithm for GCD ***)
    20 (*** Euclid's algorithm for GCD ***)
    21 
    21 
    22 Goal "|- VARS a b. \
    22 Goal "|- VARS a b. \
    47 \     INV {A^B = c * a^b} \
    47 \     INV {A^B = c * a^b} \
    48 \     DO  a := a*a; b := b div 2 OD; \
    48 \     DO  a := a*a; b := b div 2 OD; \
    49 \     c := c*a; b := b-1 \
    49 \     c := c*a; b := b-1 \
    50 \ OD \
    50 \ OD \
    51 \ {c = A^B}";
    51 \ {c = A^B}";
    52 by(hoare_tac (Asm_full_simp_tac) 1);
    52 by (hoare_tac (Asm_full_simp_tac) 1);
    53 by (exhaust_tac "b" 1);
    53 by (exhaust_tac "b" 1);
    54 by (hyp_subst_tac 1);
    54 by (hyp_subst_tac 1);
    55 by (asm_full_simp_tac (simpset() addsimps [mod_less]) 1);
    55 by (asm_full_simp_tac (simpset() addsimps [mod_less]) 1);
    56 by (asm_simp_tac (simpset() addsimps [mult_assoc]) 1);
    56 by (asm_simp_tac (simpset() addsimps [mult_assoc]) 1);
    57 qed "power_by_mult";
    57 qed "power_by_mult";
   114 \ INV {!j. j<i --> A!j ~= 0} \
   114 \ INV {!j. j<i --> A!j ~= 0} \
   115 \ DO i := i+1 OD \
   115 \ DO i := i+1 OD \
   116 \ {(i < length A --> A!i = 0) & \
   116 \ {(i < length A --> A!i = 0) & \
   117 \  (i = length A --> (!j. j < length A --> A!j ~= 0))}";
   117 \  (i = length A --> (!j. j < length A --> A!j ~= 0))}";
   118 by (hoare_tac Asm_full_simp_tac 1);
   118 by (hoare_tac Asm_full_simp_tac 1);
   119 by(blast_tac (claset() addSEs [less_SucE]) 1);
   119 by (blast_tac (claset() addSEs [less_SucE]) 1);
   120 qed "zero_search";
   120 qed "zero_search";
   121 
   121 
   122 (* 
   122 (* 
   123 The `partition' procedure for quicksort.
   123 The `partition' procedure for quicksort.
   124 `A' is the array to be sorted (modelled as a list).
   124 `A' is the array to be sorted (modelled as a list).
   144 \      DO u := u-1 OD; \
   144 \      DO u := u-1 OD; \
   145 \     IF l <= u THEN A := A[l := A!u, u := A!l] ELSE SKIP FI \
   145 \     IF l <= u THEN A := A[l := A!u, u := A!l] ELSE SKIP FI \
   146 \  OD \
   146 \  OD \
   147 \ {leq A u & (!k. u<k & k<l --> A!k = pivot) & geq A l}";
   147 \ {leq A u & (!k. u<k & k<l --> A!k = pivot) & geq A l}";
   148 (* expand and delete abbreviations first *)
   148 (* expand and delete abbreviations first *)
   149 by(asm_simp_tac HOL_basic_ss 1);
   149 by (asm_simp_tac HOL_basic_ss 1);
   150 by(REPEAT(etac thin_rl 1));
   150 by (REPEAT(etac thin_rl 1));
   151 by (hoare_tac Asm_full_simp_tac 1);
   151 by (hoare_tac Asm_full_simp_tac 1);
   152     by(asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1);
   152     by (asm_full_simp_tac (simpset() addsimps [neq_Nil_conv]) 1);
   153     by(Clarify_tac 1);
   153     by (Clarify_tac 1);
   154     by(asm_full_simp_tac (simpset() addsimps [nth_list_update]) 1);
   154     by (asm_full_simp_tac (simpset() addsimps [nth_list_update]) 1);
   155    by(blast_tac (claset() addSEs [less_SucE] addIs [Suc_leI]) 1);
   155    by (blast_tac (claset() addSEs [less_SucE] addIs [Suc_leI]) 1);
   156   br conjI 1;
   156   by (rtac conjI 1);
   157    by(Clarify_tac 1);
   157    by (Clarify_tac 1);
   158    bd (pred_less_imp_le RS le_imp_less_Suc) 1;
   158    by (dtac (pred_less_imp_le RS le_imp_less_Suc) 1);
   159    by(blast_tac (claset() addSEs [less_SucE]) 1);
   159    by (blast_tac (claset() addSEs [less_SucE]) 1);
   160   br less_imp_diff_less 1;
   160   by (rtac less_imp_diff_less 1);
   161   by(Blast_tac 1);
   161   by (Blast_tac 1);
   162  by(Clarify_tac 1);
   162  by (Clarify_tac 1);
   163  by(asm_simp_tac (simpset() addsimps [nth_list_update]) 1);
   163  by (asm_simp_tac (simpset() addsimps [nth_list_update]) 1);
   164  by(Clarify_tac 1);
   164  by (Clarify_tac 1);
   165  by(Simp_tac 1);
   165  by (Simp_tac 1);
   166 by(Clarify_tac 1);
   166 by (Clarify_tac 1);
   167 by(Asm_simp_tac 1);
   167 by (Asm_simp_tac 1);
   168 br conjI 1;
   168 by (rtac conjI 1);
   169  by(Clarify_tac 1);
   169  by (Clarify_tac 1);
   170  br order_antisym 1;
   170  by (rtac order_antisym 1);
   171   by(Asm_simp_tac 1);
   171   by (Asm_simp_tac 1);
   172  by(Asm_simp_tac 1);
   172  by (Asm_simp_tac 1);
   173 by(Clarify_tac 1);
   173 by (Clarify_tac 1);
   174 by(Asm_simp_tac 1);
   174 by (Asm_simp_tac 1);
   175 qed "Partition";
   175 qed "Partition";