helm/software/matita/contribs/ng_assembly/compiler/ast_type_lemmas.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 (* ********************************************************************** *)
  16 (*                          Progetto FreeScale                            *)
  17 (*                                                                        *)
  18 (*   Sviluppato da: Ing. Cosimo Oliboni, oliboni@cs.unibo.it              *)
  19 (*   Ultima modifica: 05/08/2009                                          *)
  20 (*                                                                        *)
  21 (* ********************************************************************** *)
  22
  23 include "compiler/ast_type.ma".
  24 include "common/list_utility_lemmas.ma".
  25
  26 (* ************************* *)
  27 (* dimensioni degli elementi *)
  28 (* ************************* *)
  29
  30 ndefinition astbasetype_destruct_aux ≝
  31 Πb1,b2:ast_base_type.ΠP:Prop.b1 = b2 →
  32  match eq_astbasetype b1 b2 with [ true ⇒ P → P | false ⇒ P ].
  33
  34 ndefinition astbasetype_destruct : astbasetype_destruct_aux.
  35  #b1; #b2; #P; #H;
  36  nrewrite < H;
  37  nelim b1;
  38  nnormalize;
  39  napply (λx.x).
  40 nqed.
  41
  42 nlemma eq_to_eqastbasetype : ∀n1,n2.n1 = n2 → eq_astbasetype n1 n2 = true.
  43  #n1; #n2; #H;
  44  nrewrite > H;
  45  nelim n2;
  46  nnormalize;
  47  napply refl_eq.
  48 nqed.
  49
  50 nlemma neqastbasetype_to_neq : ∀n1,n2.eq_astbasetype n1 n2 = false → n1 ≠ n2.
  51  #n1; #n2; #H;
  52  napply (not_to_not (n1 = n2) (eq_astbasetype n1 n2 = true) …);
  53  ##[ ##1: napply (eq_to_eqastbasetype n1 n2)
  54  ##| ##2: napply (eqfalse_to_neqtrue … H)
  55  ##]
  56 nqed.
  57
  58 nlemma eqastbasetype_to_eq : ∀b1,b2.eq_astbasetype b1 b2 = true → b1 = b2.
  59  #b1; #b2; ncases b1; ncases b2; nnormalize;
  60  ##[ ##1,5,9: #H; napply refl_eq
  61  ##| ##*: #H; napply (bool_destruct … H)
  62  ##]
  63 nqed.
  64
  65 nlemma neq_to_neqastbasetype : ∀n1,n2.n1 ≠ n2 → eq_astbasetype n1 n2 = false.
  66  #n1; #n2; #H;
  67  napply (neqtrue_to_eqfalse (eq_astbasetype n1 n2));
  68  napply (not_to_not (eq_astbasetype n1 n2 = true) (n1 = n2) ? H);
  69  napply (eqastbasetype_to_eq n1 n2).
  70 nqed.
  71
  72 nlemma decidable_astbasetype : ∀x,y:ast_base_type.decidable (x = y).
  73  #x; #y; nnormalize;
  74  napply (or2_elim (eq_astbasetype x y = true) (eq_astbasetype x y = false) ? (decidable_bexpr ?));
  75  ##[ ##1: #H; napply (or2_intro1 (x = y) (x ≠ y) (eqastbasetype_to_eq … H))
  76  ##| ##2: #H; napply (or2_intro2 (x = y) (x ≠ y) (neqastbasetype_to_neq … H))
  77  ##]
  78 nqed.
  79
  80 nlemma symmetric_eqastbasetype : symmetricT ast_base_type bool eq_astbasetype.
  81  #n1; #n2;
  82  napply (or2_elim (n1 = n2) (n1 ≠ n2) ? (decidable_astbasetype n1 n2));
  83  ##[ ##1: #H; nrewrite > H; napply refl_eq
  84  ##| ##2: #H; nrewrite > (neq_to_neqastbasetype n1 n2 H);
  85           napply (symmetric_eq ? (eq_astbasetype n2 n1) false);
  86           napply (neq_to_neqastbasetype n2 n1 (symmetric_neq ? n1 n2 H))
  87  ##]
  88 nqed.
  89
  90 nlemma asttype_destruct_base_base : ∀b1,b2.AST_TYPE_BASE b1 = AST_TYPE_BASE b2 → b1 = b2.
  91  #b1; #b2; #H;
  92  nchange with (match AST_TYPE_BASE b2 with [ AST_TYPE_BASE a ⇒ b1 = a | _ ⇒ False ]);
  93  nrewrite < H;
  94  nnormalize;
  95  napply refl_eq.
  96 nqed.
  97
  98 nlemma asttype_destruct_array_array_1 : ∀x1,x2,y1,y2.AST_TYPE_ARRAY x1 y1 = AST_TYPE_ARRAY x2 y2 → x1 = x2.
  99  #x1; #x2; #y1; #y2; #H;
 100  nchange with (match AST_TYPE_ARRAY x2 y2 with [ AST_TYPE_ARRAY a _ ⇒ x1 = a | _ ⇒ False ]);
 101  nrewrite < H;
 102  nnormalize;
 103  napply refl_eq.
 104 nqed.
 105
 106 nlemma asttype_destruct_array_array_2 : ∀x1,x2,y1,y2.AST_TYPE_ARRAY x1 y1 = AST_TYPE_ARRAY x2 y2 → y1 = y2.
 107  #x1; #x2; #y1; #y2; #H;
 108  nchange with (match AST_TYPE_ARRAY x2 y2 with [ AST_TYPE_ARRAY _ b ⇒ y1 = b | _ ⇒ False ]);
 109  nrewrite < H;
 110  nnormalize;
 111  napply refl_eq.
 112 nqed.
 113
 114 nlemma asttype_destruct_struct_struct : ∀b1,b2.AST_TYPE_STRUCT b1 = AST_TYPE_STRUCT b2 → b1 = b2.
 115  #b1; #b2; #H;
 116  nchange with (match AST_TYPE_STRUCT b2 with [ AST_TYPE_STRUCT a ⇒ b1 = a | _ ⇒ False ]);
 117  nrewrite < H;
 118  nnormalize;
 119  napply refl_eq.
 120 nqed.
 121
 122 ndefinition asttype_destruct_aux ≝
 123 Πb1,b2:ast_type.ΠP:Prop.b1 = b2 →
 124  match eq_asttype b1 b2 with [ true ⇒ P → P | false ⇒ P ].
 125
 126 ndefinition asttype_destruct : asttype_destruct_aux.
 127  #b1; #b2; #P; #H;
 128  nrewrite > H;
 129  napply (ast_type_index … b2);
 130  ##[ ##1: #e; nchange with (match eq_astbasetype e e with [ true ⇒ P → P | false ⇒ P ]);
 131           nrewrite > (eq_to_eqastbasetype e e (refl_eq …));
 132           nnormalize; napply (λx.x);
 133  ##| ##2: #e; #n; #H; nchange with (match (eq_asttype e e)⊗(eq_nat n n) with [ true ⇒ P → P | false ⇒ P]);
 134           nrewrite > (eq_to_eqnat n n (refl_eq …));
 135           nrewrite > (symmetric_andbool (eq_asttype e e) true);
 136           nchange with (match eq_asttype e e with [ true ⇒ P → P | false ⇒ P]);
 137           napply H;
 138  ##| ##3: #e; #H; nchange with (match eq_asttype e e with [ true ⇒ P → P | false ⇒ P]);
 139           napply H;
 140  ##| ##4: #hh; #tt; #H;
 141           nchange with (match bfold_right_neList2 ?? tt tt with [ true ⇒ P → P | false ⇒ P ] →
 142                         match (eq_asttype hh hh)⊗(bfold_right_neList2 ?? tt tt) with [ true ⇒ P → P | false ⇒ P ]);
 143           #H1;
 144           ncases (eq_asttype hh hh) in H:(%) ⊢ %; #H;
 145           ncases (bfold_right_neList2 ? (λx1,x2.eq_asttype x1 x2) tt tt) in H1:(%) ⊢ %; #H1;
 146           ##[ ##1: nnormalize; napply (λx.x);
 147           ##| ##3: nnormalize in H:(%) ⊢ %; napply H
 148           ##| ##*: nnormalize in H1:(%) ⊢ %; napply H1
 149           ##]
 150  ##]
 151 nqed.
 152
 153 nlemma eq_to_eqasttype_aux1
 154  : ∀nl1,nl2.
 155   ((eq_asttype (AST_TYPE_STRUCT nl1) (AST_TYPE_STRUCT nl2)) = true) →
 156   ((bfold_right_neList2 ? (λx,y.eq_asttype x y) nl1 nl2) = true).
 157  #nl1; #nl2; #H;
 158  napply H.
 159 nqed.
 160
 161 nlemma eq_to_eqasttype : ∀t1,t2.t1 = t2 → eq_asttype t1 t2 = true.
 162  #t1;
 163  napply (ast_type_index … t1);
 164  ##[ ##1: #b1; #t2; ncases t2;
 165           ##[ ##1: #b2; #H; nrewrite > (asttype_destruct_base_base … H);
 166                    nchange with ((eq_astbasetype b2 b2) = true);
 167                    nrewrite > (eq_to_eqastbasetype b2 b2 (refl_eq …));
 168                    napply refl_eq
 169           ##| ##2: #st2; #n2; #H; napply (asttype_destruct … H)
 170           ##| ##3: #nl2; #H; napply (asttype_destruct … H)
 171           ##]
 172  ##| ##2: #st1; #n1; #H; #t2; ncases t2;
 173           ##[ ##2: #st2; #n2; #H1;  nchange with (((eq_asttype st1 st2)⊗(eq_nat n1 n2)) = true);
 174                    nrewrite > (H st2 (asttype_destruct_array_array_1 … H1));
 175                    nrewrite > (eq_to_eqnat n1 n2 (asttype_destruct_array_array_2 … H1));
 176                    nnormalize;
 177                    napply refl_eq
 178           ##| ##1: #b2; #H1; napply (asttype_destruct … H1)
 179           ##| ##3: #nl2; #H1; napply (asttype_destruct … H1)
 180           ##]
 181  ##| ##3: #hh1; #H; #t2; ncases t2;
 182           ##[ ##3: #nl2; ncases nl2;
 183                    ##[ ##1: #hh2; #H1; nchange with ((eq_asttype hh1 hh2) = true);
 184                             nrewrite > (H hh2 (nelist_destruct_nil_nil ? hh1 hh2 (asttype_destruct_struct_struct … H1)));
 185                             napply refl_eq
 186                    ##| ##2: #hh2; #ll2; #H1; nelim (nelist_destruct_nil_cons ? hh1 hh2 ll2 (asttype_destruct_struct_struct … H1))
 187                    ##]
 188           ##| ##1: #b2; #H1; napply (asttype_destruct … H1)
 189           ##| ##2: #st2; #n2; #H1; napply (asttype_destruct … H1)
 190           ##]
 191  ##| ##4: #hh1; #ll1; #H; #H1; #t2; ncases t2;
 192           ##[ ##3: #nl2; ncases nl2;
 193                    ##[ ##1: #hh2; #H2; nelim (nelist_destruct_cons_nil ? hh1 hh2 ll1 (asttype_destruct_struct_struct … H2))
 194                    ##| ##2: #hh2; #ll2; #H2; nchange with (((eq_asttype hh1 hh2)⊗(bfold_right_neList2 ? (λx,y.eq_asttype x y) ll1 ll2)) = true);
 195                             nrewrite > (H hh2 (nelist_destruct_cons_cons_1 … (asttype_destruct_struct_struct … H2)));
 196                             nrewrite > (eq_to_eqasttype_aux1 ll1 ll2 (H1 (AST_TYPE_STRUCT ll2) ?));
 197                             ##[ ##1: nnormalize; napply refl_eq
 198                             ##| ##2: nrewrite > (nelist_destruct_cons_cons_2 … (asttype_destruct_struct_struct … H2));
 199                                      napply refl_eq
 200                             ##]
 201                    ##]
 202           ##| ##1: #b2; #H2; napply (asttype_destruct … H2)
 203           ##| ##2: #st2; #n2; #H2; napply (asttype_destruct … H2)
 204           ##]
 205  ##]
 206 nqed.
 207
 208 nlemma neqasttype_to_neq : ∀n1,n2.eq_asttype n1 n2 = false → n1 ≠ n2.
 209  #n1; #n2; #H;
 210  napply (not_to_not (n1 = n2) (eq_asttype n1 n2 = true) …);
 211  ##[ ##1: napply (eq_to_eqasttype n1 n2)
 212  ##| ##2: napply (eqfalse_to_neqtrue … H)
 213  ##]
 214 nqed.
 215
 216 nlemma eqasttype_to_eq : ∀t1,t2.eq_asttype t1 t2 = true → t1 = t2.
 217  #t1;
 218  napply (ast_type_index … t1);
 219  ##[ ##1: #b1; #t2; ncases t2;
 220           ##[ ##1: #b2; #H; nchange in H:(%) with ((eq_astbasetype b1 b2) = true);
 221                    nrewrite > (eqastbasetype_to_eq b1 b2 H);
 222                    napply refl_eq
 223           ##| ##2: #st2; #n2; nnormalize; #H; napply (bool_destruct … H)
 224           ##| ##3: #nl2; nnormalize; #H; napply (bool_destruct … H)
 225           ##]
 226  ##| ##2: #st1; #n1; #H; #t2; ncases t2;
 227           ##[ ##2: #st2; #n2; #H1; nchange in H1:(%) with (((eq_asttype st1 st2)⊗(eq_nat n1 n2)) = true);
 228                    nrewrite > (H st2 (andb_true_true_l … H1));
 229                    nrewrite > (eqnat_to_eq n1 n2 (andb_true_true_r … H1));
 230                    napply refl_eq
 231           ##| ##1: #b2; nnormalize; #H1; napply (bool_destruct … H1)
 232           ##| ##3: #nl2; nnormalize; #H1; napply (bool_destruct … H1)
 233           ##]
 234  ##| ##3: #hh1; #H; #t2; ncases t2;
 235           ##[ ##3: #nl2; ncases nl2;
 236                    ##[ ##1: #hh2; #H1; nchange in H1:(%) with ((eq_asttype hh1 hh2) = true);
 237                             nrewrite > (H hh2 H1);
 238                             napply refl_eq
 239                    ##| ##2: #hh2; #ll2; nnormalize; #H1; napply (bool_destruct … H1)
 240                    ##]
 241           ##| ##1: #b2; nnormalize; #H1; napply (bool_destruct … H1)
 242           ##| ##2: #st2; #n2; nnormalize; #H1; napply (bool_destruct … H1)
 243           ##]
 244  ##| ##4: #hh1; #ll1; #H; #H1; #t2; ncases t2;
 245           ##[ ##3: #nl2; ncases nl2;
 246                    ##[ ##1: #hh2; nnormalize; #H2; napply (bool_destruct … H2)
 247                    ##| ##2: #hh2; #ll2; #H2; nchange in H2:(%) with (((eq_asttype hh1 hh2)⊗(bfold_right_neList2 ? (λx,y.eq_asttype x y) ll1 ll2)) = true);
 248                             nrewrite > (H hh2 (andb_true_true_l … H2));
 249                             nrewrite > (asttype_destruct_struct_struct ll1 ll2 (H1 (AST_TYPE_STRUCT ll2) (andb_true_true_r … H2)));
 250                             napply refl_eq
 251                    ##]
 252           ##| ##1: #b2; nnormalize; #H2; napply (bool_destruct … H2)
 253           ##| ##2: #st2; #n2; nnormalize; #H2; napply (bool_destruct … H2)
 254           ##]
 255  ##]
 256 nqed.
 257
 258 nlemma neq_to_neqasttype : ∀n1,n2.n1 ≠ n2 → eq_asttype n1 n2 = false.
 259  #n1; #n2; #H;
 260  napply (neqtrue_to_eqfalse (eq_asttype n1 n2));
 261  napply (not_to_not (eq_asttype n1 n2 = true) (n1 = n2) ? H);
 262  napply (eqasttype_to_eq n1 n2).
 263 nqed.
 264
 265 nlemma decidable_asttype : ∀x,y:ast_type.decidable (x = y).
 266  #x; #y; nnormalize;
 267  napply (or2_elim (eq_asttype x y = true) (eq_asttype x y = false) ? (decidable_bexpr ?));
 268  ##[ ##1: #H; napply (or2_intro1 (x = y) (x ≠ y) (eqasttype_to_eq … H))
 269  ##| ##2: #H; napply (or2_intro2 (x = y) (x ≠ y) (neqasttype_to_neq … H))
 270  ##]
 271 nqed.
 272
 273 nlemma symmetric_eqasttype : symmetricT ast_type bool eq_asttype.
 274  #n1; #n2;
 275  napply (or2_elim (n1 = n2) (n1 ≠ n2) ? (decidable_asttype n1 n2));
 276  ##[ ##1: #H; nrewrite > H; napply refl_eq
 277  ##| ##2: #H; nrewrite > (neq_to_neqasttype n1 n2 H);
 278           napply (symmetric_eq ? (eq_asttype n2 n1) false);
 279           napply (neq_to_neqasttype n2 n1 (symmetric_neq ? n1 n2 H))
 280  ##]
 281 nqed.
 282
 283 nlemma isbastbasetype_to_isastbasetype : ∀ast.isb_ast_base_type ast = true → is_ast_base_type ast.
 284  #ast;
 285  ncases ast;
 286  nnormalize;
 287  ##[ ##1: #t; #H; napply I
 288  ##| ##2: #t; #n; #H; napply (bool_destruct … H)
 289  ##| ##3: #t; #H; napply (bool_destruct … H)
 290  ##]
 291 nqed.
 292
 293 nlemma isntbastbasetype_to_isntastbasetype : ∀ast.isntb_ast_base_type ast = true → isnt_ast_base_type ast.
 294  #ast;
 295  ncases ast;
 296  nnormalize;
 297  ##[ ##1: #t; #H; napply (bool_destruct … H)
 298  ##| ##2: #t; #n; #H; napply I
 299  ##| ##3: #l; #H; napply I
 300  ##]
 301 nqed.