src/HOL/MicroJava/J/WellType.thy
author streckem
Mon May 26 18:36:15 2003 +0200 (2003-05-26)
changeset 14045 a34d89ce6097
parent 13672 b95d12325b51
child 14134 0fdf5708c7a8
permissions -rw-r--r--
Introduced distinction wf_prog vs. ws_prog
     1 (*  Title:      HOL/MicroJava/J/WellType.thy
     2     ID:         $Id$
     3     Author:     David von Oheimb
     4     Copyright   1999 Technische Universitaet Muenchen
     5 *)
     6 
     7 header {* \isaheader{Well-typedness Constraints} *}
     8 
     9 theory WellType = Term + WellForm:
    10 
    11 text {*
    12 the formulation of well-typedness of method calls given below (as well as
    13 the Java Specification 1.0) is a little too restrictive: Is does not allow
    14 methods of class Object to be called upon references of interface type.
    15 
    16 \begin{description}
    17 \item[simplifications:]\ \\
    18 \begin{itemize}
    19 \item the type rules include all static checks on expressions and statements, 
    20   e.g.\ definedness of names (of parameters, locals, fields, methods)
    21 \end{itemize}
    22 \end{description}
    23 *}
    24 
    25 text "local variables, including method parameters and This:"
    26 types 
    27   lenv   = "vname \<leadsto> ty"
    28   'c env = "'c prog \<times> lenv"
    29 
    30 syntax
    31   prg    :: "'c env => 'c prog"
    32   localT :: "'c env => (vname \<leadsto> ty)"
    33 
    34 translations  
    35   "prg"    => "fst"
    36   "localT" => "snd"
    37 
    38 consts
    39   more_spec :: "'c prog => (ty \<times> 'x) \<times> ty list =>
    40                 (ty \<times> 'x) \<times> ty list => bool"
    41   appl_methds :: "'c prog =>  cname => sig => ((ty \<times> ty) \<times> ty list) set"
    42   max_spec :: "'c prog =>  cname => sig => ((ty \<times> ty) \<times> ty list) set"
    43 
    44 defs
    45   more_spec_def: "more_spec G == \<lambda>((d,h),pTs). \<lambda>((d',h'),pTs'). G\<turnstile>d\<preceq>d' \<and>
    46                                 list_all2 (\<lambda>T T'. G\<turnstile>T\<preceq>T') pTs pTs'"
    47   
    48   -- "applicable methods, cf. 15.11.2.1"
    49   appl_methds_def: "appl_methds G C == \<lambda>(mn, pTs).
    50                      {((Class md,rT),pTs') |md rT mb pTs'.
    51                       method (G,C)  (mn, pTs') = Some (md,rT,mb) \<and>
    52                       list_all2 (\<lambda>T T'. G\<turnstile>T\<preceq>T') pTs pTs'}"
    53 
    54   -- "maximally specific methods, cf. 15.11.2.2"
    55   max_spec_def: "max_spec G C sig == {m. m \<in>appl_methds G C sig \<and> 
    56                                        (\<forall>m'\<in>appl_methds G C sig.
    57                                          more_spec G m' m --> m' = m)}"
    58 
    59 lemma max_spec2appl_meths: 
    60   "x \<in> max_spec G C sig ==> x \<in> appl_methds G C sig"
    61 apply (unfold max_spec_def)
    62 apply (fast)
    63 done
    64 
    65 lemma appl_methsD: 
    66 "((md,rT),pTs')\<in>appl_methds G C (mn, pTs) ==>  
    67   \<exists>D b. md = Class D \<and> method (G,C) (mn, pTs') = Some (D,rT,b)  
    68   \<and> list_all2 (\<lambda>T T'. G\<turnstile>T\<preceq>T') pTs pTs'"
    69 apply (unfold appl_methds_def)
    70 apply (fast)
    71 done
    72 
    73 lemmas max_spec2mheads = insertI1 [THEN [2] equalityD2 [THEN subsetD], 
    74                          THEN max_spec2appl_meths, THEN appl_methsD]
    75 
    76 
    77 consts
    78   typeof :: "(loc => ty option) => val => ty option"
    79 
    80 primrec
    81   "typeof dt  Unit    = Some (PrimT Void)"
    82   "typeof dt  Null    = Some NT"
    83   "typeof dt (Bool b) = Some (PrimT Boolean)"
    84   "typeof dt (Intg i) = Some (PrimT Integer)"
    85   "typeof dt (Addr a) = dt a"
    86 
    87 lemma is_type_typeof [rule_format (no_asm), simp]: 
    88   "(\<forall>a. v \<noteq> Addr a) --> (\<exists>T. typeof t v = Some T \<and> is_type G T)"
    89 apply (rule val.induct)
    90 apply     auto
    91 done
    92 
    93 lemma typeof_empty_is_type [rule_format (no_asm)]: 
    94   "typeof (\<lambda>a. None) v = Some T \<longrightarrow> is_type G T"
    95 apply (rule val.induct)
    96 apply     auto
    97 done
    98 
    99 lemma typeof_default_val: "\<exists>T. (typeof dt (default_val ty) = Some T) \<and> G\<turnstile> T \<preceq> ty"
   100 apply (case_tac ty)
   101 apply (case_tac prim_ty)
   102 apply auto
   103 done
   104 
   105 types
   106   java_mb = "vname list \<times> (vname \<times> ty) list \<times> stmt \<times> expr"
   107 -- "method body with parameter names, local variables, block, result expression."
   108 -- "local variables might include This, which is hidden anyway"
   109 
   110 consts
   111   ty_expr :: "('c env \<times> expr      \<times> ty     ) set"
   112   ty_exprs:: "('c env \<times> expr list \<times> ty list) set"
   113   wt_stmt :: "('c env \<times> stmt               ) set"
   114 
   115 syntax (xsymbols)
   116   ty_expr :: "'c env => [expr     , ty     ] => bool" ("_ \<turnstile> _ :: _"   [51,51,51]50)
   117   ty_exprs:: "'c env => [expr list, ty list] => bool" ("_ \<turnstile> _ [::] _" [51,51,51]50)
   118   wt_stmt :: "'c env =>  stmt                => bool" ("_ \<turnstile> _ \<surd>"      [51,51   ]50)
   119 
   120 syntax
   121   ty_expr :: "'c env => [expr     , ty     ] => bool" ("_ |- _ :: _"   [51,51,51]50)
   122   ty_exprs:: "'c env => [expr list, ty list] => bool" ("_ |- _ [::] _" [51,51,51]50)
   123   wt_stmt :: "'c env =>  stmt                => bool" ("_ |- _ [ok]"   [51,51   ]50)
   124 
   125 
   126 translations
   127   "E\<turnstile>e :: T" == "(E,e,T) \<in> ty_expr"
   128   "E\<turnstile>e[::]T" == "(E,e,T) \<in> ty_exprs"
   129   "E\<turnstile>c \<surd>"    == "(E,c)   \<in> wt_stmt"
   130   
   131 inductive "ty_expr" "ty_exprs" "wt_stmt" intros
   132   
   133   NewC: "[| is_class (prg E) C |] ==>
   134          E\<turnstile>NewC C::Class C"  -- "cf. 15.8"
   135 
   136   -- "cf. 15.15"
   137   Cast: "[| E\<turnstile>e::C; is_class (prg E) D;
   138             prg E\<turnstile>C\<preceq>? Class D |] ==>
   139          E\<turnstile>Cast D e:: Class D"
   140 
   141   -- "cf. 15.7.1"
   142   Lit:    "[| typeof (\<lambda>v. None) x = Some T |] ==>
   143          E\<turnstile>Lit x::T"
   144 
   145   
   146   -- "cf. 15.13.1"
   147   LAcc: "[| localT E v = Some T; is_type (prg E) T |] ==>
   148          E\<turnstile>LAcc v::T"
   149 
   150   BinOp:"[| E\<turnstile>e1::T;
   151             E\<turnstile>e2::T;
   152             if bop = Eq then T' = PrimT Boolean
   153                         else T' = T \<and> T = PrimT Integer|] ==>
   154             E\<turnstile>BinOp bop e1 e2::T'"
   155 
   156   -- "cf. 15.25, 15.25.1"
   157   LAss: "[| v ~= This;
   158             E\<turnstile>LAcc v::T;
   159             E\<turnstile>e::T';
   160             prg E\<turnstile>T'\<preceq>T |] ==>
   161          E\<turnstile>v::=e::T'"
   162 
   163   -- "cf. 15.10.1"
   164   FAcc: "[| E\<turnstile>a::Class C; 
   165             field (prg E,C) fn = Some (fd,fT) |] ==>
   166             E\<turnstile>{fd}a..fn::fT"
   167 
   168   -- "cf. 15.25, 15.25.1"
   169   FAss: "[| E\<turnstile>{fd}a..fn::T;
   170             E\<turnstile>v        ::T';
   171             prg E\<turnstile>T'\<preceq>T |] ==>
   172          E\<turnstile>{fd}a..fn:=v::T'"
   173 
   174 
   175   -- "cf. 15.11.1, 15.11.2, 15.11.3"
   176   Call: "[| E\<turnstile>a::Class C;
   177             E\<turnstile>ps[::]pTs;
   178             max_spec (prg E) C (mn, pTs) = {((md,rT),pTs')} |] ==>
   179          E\<turnstile>{C}a..mn({pTs'}ps)::rT"
   180 
   181 -- "well-typed expression lists"
   182 
   183   -- "cf. 15.11.???"
   184   Nil: "E\<turnstile>[][::][]"
   185 
   186   -- "cf. 15.11.???"
   187   Cons:"[| E\<turnstile>e::T;
   188            E\<turnstile>es[::]Ts |] ==>
   189         E\<turnstile>e#es[::]T#Ts"
   190 
   191 -- "well-typed statements"
   192 
   193   Skip:"E\<turnstile>Skip\<surd>"
   194 
   195   Expr:"[| E\<turnstile>e::T |] ==>
   196         E\<turnstile>Expr e\<surd>"
   197 
   198   Comp:"[| E\<turnstile>s1\<surd>; 
   199            E\<turnstile>s2\<surd> |] ==>
   200         E\<turnstile>s1;; s2\<surd>"
   201 
   202   -- "cf. 14.8"
   203   Cond:"[| E\<turnstile>e::PrimT Boolean;
   204            E\<turnstile>s1\<surd>;
   205            E\<turnstile>s2\<surd> |] ==>
   206          E\<turnstile>If(e) s1 Else s2\<surd>"
   207 
   208   -- "cf. 14.10"
   209   Loop:"[| E\<turnstile>e::PrimT Boolean;
   210            E\<turnstile>s\<surd> |] ==>
   211         E\<turnstile>While(e) s\<surd>"
   212 
   213 
   214 constdefs
   215 
   216  wf_java_mdecl :: "'c prog => cname => java_mb mdecl => bool"
   217 "wf_java_mdecl G C == \<lambda>((mn,pTs),rT,(pns,lvars,blk,res)).
   218   length pTs = length pns \<and>
   219   distinct pns \<and>
   220   unique lvars \<and>
   221         This \<notin> set pns \<and> This \<notin> set (map fst lvars) \<and> 
   222   (\<forall>pn\<in>set pns. map_of lvars pn = None) \<and>
   223   (\<forall>(vn,T)\<in>set lvars. is_type G T) &
   224   (let E = (G,map_of lvars(pns[\<mapsto>]pTs)(This\<mapsto>Class C)) in
   225    E\<turnstile>blk\<surd> \<and> (\<exists>T. E\<turnstile>res::T \<and> G\<turnstile>T\<preceq>rT))"
   226 
   227 syntax 
   228  wf_java_prog :: "'c prog => bool"
   229 translations
   230   "wf_java_prog" == "wf_prog wf_java_mdecl"
   231 
   232 lemma wf_java_prog_wf_java_mdecl: "\<lbrakk> 
   233   wf_java_prog G; (C, D, fds, mths) \<in> set G; jmdcl \<in> set mths \<rbrakk>
   234   \<Longrightarrow> wf_java_mdecl G C jmdcl"
   235 apply (simp only: wf_prog_def) 
   236 apply (erule conjE)+
   237 apply (drule bspec, assumption)
   238 apply (simp add: wf_cdecl_mdecl_def split_beta)
   239 done
   240 
   241 
   242 lemma wt_is_type: "(E\<turnstile>e::T \<longrightarrow> ws_prog (prg E) \<longrightarrow> is_type (prg E) T) \<and>  
   243        (E\<turnstile>es[::]Ts \<longrightarrow> ws_prog (prg E) \<longrightarrow> Ball (set Ts) (is_type (prg E))) \<and> 
   244        (E\<turnstile>c \<surd> \<longrightarrow> True)"
   245 apply (rule ty_expr_ty_exprs_wt_stmt.induct)
   246 apply auto
   247 apply (   erule typeof_empty_is_type)
   248 apply (  simp split add: split_if_asm)
   249 apply ( drule field_fields)
   250 apply ( drule (1) fields_is_type)
   251 apply (  simp (no_asm_simp))
   252 apply  (assumption)
   253 apply (auto dest!: max_spec2mheads method_wf_mhead is_type_rTI 
   254             simp add: wf_mdecl_def)
   255 done
   256 
   257 lemmas ty_expr_is_type = wt_is_type [THEN conjunct1,THEN mp, rule_format]
   258 
   259 lemma expr_class_is_class: "
   260   \<lbrakk>ws_prog (prg E); E \<turnstile> e :: Class C\<rbrakk> \<Longrightarrow> is_class (prg E) C"
   261   by (frule ty_expr_is_type, assumption, simp)
   262 
   263 
   264 end