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