src/HOL/IMP/Denotation.ML
changeset 1973 8c94c9a5be10
parent 1731 2ad693c6cb13
child 2031 03a843f0f447
equal deleted inserted replaced
1972:cc65911dceef 1973:8c94c9a5be10
     4     Copyright   1994 TUM
     4     Copyright   1994 TUM
     5 *)
     5 *)
     6 
     6 
     7 open Denotation;
     7 open Denotation;
     8 
     8 
     9 val denotation_cs =  comp_cs addss (!simpset addsimps evalc.intrs);
       
    10 
       
    11 
       
    12 (**** Rewrite Rules for C ****)
       
    13 
       
    14 val C_simps = map (fn t => t RS eq_reflection)
       
    15   [C_skip,C_assign,C_comp,C_if,C_while]; 
       
    16 
       
    17 
     9 
    18 (**** mono (Gamma(b,c)) ****)
    10 (**** mono (Gamma(b,c)) ****)
    19 
    11 
    20 qed_goalw "Gamma_mono" Denotation.thy [mono_def,Gamma_def]
    12 qed_goalw "Gamma_mono" Denotation.thy [mono_def,Gamma_def]
    21         "mono (Gamma b c)"
    13         "mono (Gamma b c)"
    22      (fn _ => [(best_tac comp_cs 1)]);
    14      (fn _ => [Fast_tac 1]);
    23 
    15 
    24 
    16 
    25 goal Denotation.thy "C(WHILE b DO c) = C(IF b THEN c;WHILE b DO c ELSE SKIP)";
    17 goal Denotation.thy "C(WHILE b DO c) = C(IF b THEN c;WHILE b DO c ELSE SKIP)";
    26 by(Simp_tac 1);
    18 by(Simp_tac 1);
    27 by(EVERY[stac (Gamma_mono RS lfp_Tarski) 1,
    19 by(EVERY[stac (Gamma_mono RS lfp_Tarski) 1,
    35 
    27 
    36 goal Denotation.thy "!!c s t. <c,s> -c-> t ==> (s,t) : C(c)";
    28 goal Denotation.thy "!!c s t. <c,s> -c-> t ==> (s,t) : C(c)";
    37 
    29 
    38 (* start with rule induction *)
    30 (* start with rule induction *)
    39 by (etac evalc.induct 1);
    31 by (etac evalc.induct 1);
    40 by (rewrite_tac (Gamma_def::C_simps));
    32 auto();
    41   (* simplification with HOL_ss too agressive *)
       
    42 (* skip *)
       
    43 by (fast_tac denotation_cs 1);
       
    44 (* assign *)
       
    45 by (fast_tac denotation_cs 1);
       
    46 (* comp *)
       
    47 by (fast_tac denotation_cs 1);
       
    48 (* if *)
       
    49 by (fast_tac denotation_cs 1);
       
    50 by (fast_tac denotation_cs 1);
       
    51 (* while *)
    33 (* while *)
       
    34 by(rewtac Gamma_def);
    52 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1);
    35 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1);
    53 by (fast_tac denotation_cs 1);
    36 by (Fast_tac 1);
    54 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1);
    37 by (rtac (rewrite_rule [Gamma_def] (Gamma_mono RS lfp_Tarski RS ssubst)) 1);
    55 by (fast_tac denotation_cs 1);
    38 by (Fast_tac 1);
    56 
    39 
    57 qed "com1";
    40 qed "com1";
    58 
       
    59 
    41 
    60 (* Denotational Semantics implies Operational Semantics *)
    42 (* Denotational Semantics implies Operational Semantics *)
    61 
    43 
    62 goal Denotation.thy "!s t. (s,t):C(c) --> <c,s> -c-> t";
    44 goal Denotation.thy "!s t. (s,t):C(c) --> <c,s> -c-> t";
    63 by (com.induct_tac "c" 1);
    45 by (com.induct_tac "c" 1);
    64 by (rewrite_tac C_simps);
    46 
    65 by (ALLGOALS (TRY o fast_tac denotation_cs));
    47 by(ALLGOALS Full_simp_tac);
       
    48 by(ALLGOALS (TRY o Fast_tac));
    66 
    49 
    67 (* while *)
    50 (* while *)
    68 by (strip_tac 1);
    51 by (strip_tac 1);
    69 by (etac (Gamma_mono RSN (2,induct)) 1);
    52 by (etac (Gamma_mono RSN (2,induct)) 1);
    70 by (rewtac Gamma_def);  
    53 by (rewtac Gamma_def);  
    71 by (fast_tac denotation_cs 1);
    54 by (Fast_tac 1);
    72 
    55 
    73 qed_spec_mp "com2";
    56 qed_spec_mp "com2";
    74 
    57 
    75 
    58 
    76 (**** Proof of Equivalence ****)
    59 (**** Proof of Equivalence ****)
    77 
    60 
    78 goal Denotation.thy "(s,t) : C(c)  =  (<c,s> -c-> t)";
    61 goal Denotation.thy "(s,t) : C(c)  =  (<c,s> -c-> t)";
    79 by (fast_tac (set_cs addEs [com2] addDs [com1]) 1);
    62 by (fast_tac (!claset addEs [com2] addDs [com1]) 1);
    80 qed "denotational_is_natural";
    63 qed "denotational_is_natural";