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
|
nipkow@8011
|
5 |
|
nipkow@8011
|
6 |
Well-typedness of Java programs
|
nipkow@8011
|
7 |
|
nipkow@8011
|
8 |
the formulation of well-typedness of method calls given below (as well as
|
nipkow@8011
|
9 |
the Java Specification 1.0) is a little too restrictive: Is does not allow
|
nipkow@8011
|
10 |
methods of class Object to be called upon references of interface type.
|
nipkow@8011
|
11 |
|
nipkow@8011
|
12 |
simplifications:
|
nipkow@8011
|
13 |
* the type rules include all static checks on expressions and statements, e.g.
|
nipkow@8011
|
14 |
definedness of names (of parameters, locals, fields, methods)
|
nipkow@8011
|
15 |
|
nipkow@8011
|
16 |
*)
|
nipkow@8011
|
17 |
|
nipkow@8011
|
18 |
WellType = Term + WellForm +
|
nipkow@8011
|
19 |
|
nipkow@8011
|
20 |
types lenv (* local variables, including method parameters and This *)
|
nipkow@8011
|
21 |
= "vname \\<leadsto> ty"
|
nipkow@8011
|
22 |
'c env
|
nipkow@8011
|
23 |
= "'c prog \\<times> lenv"
|
nipkow@8011
|
24 |
|
nipkow@8011
|
25 |
syntax
|
nipkow@8011
|
26 |
|
nipkow@8011
|
27 |
prg :: "'c env \\<Rightarrow> 'c prog"
|
nipkow@8011
|
28 |
localT :: "'c env \\<Rightarrow> (vname \\<leadsto> ty)"
|
nipkow@8011
|
29 |
|
nipkow@8011
|
30 |
translations
|
nipkow@8011
|
31 |
|
nipkow@8011
|
32 |
"prg" => "fst"
|
nipkow@8011
|
33 |
"localT" => "snd"
|
nipkow@8011
|
34 |
|
nipkow@8011
|
35 |
consts
|
nipkow@8011
|
36 |
|
nipkow@8011
|
37 |
more_spec :: "'c prog \\<Rightarrow> (ty \\<times> 'x) \\<times> ty list \\<Rightarrow>
|
nipkow@8011
|
38 |
(ty \\<times> 'x) \\<times> ty list \\<Rightarrow> bool"
|
nipkow@8011
|
39 |
m_head :: "'c prog \\<Rightarrow> ref_ty \\<Rightarrow> sig \\<Rightarrow> (ty \\<times> ty) option"
|
nipkow@8011
|
40 |
appl_methds :: "'c prog \\<Rightarrow> ref_ty \\<Rightarrow> sig \\<Rightarrow> ((ty \\<times> ty) \\<times> ty list) set"
|
nipkow@8011
|
41 |
max_spec :: "'c prog \\<Rightarrow> ref_ty \\<Rightarrow> sig \\<Rightarrow> ((ty \\<times> ty) \\<times> ty list) set"
|
nipkow@8011
|
42 |
|
nipkow@8011
|
43 |
defs
|
nipkow@8011
|
44 |
|
nipkow@8011
|
45 |
m_head_def "m_head G t sig \\<equiv> case t of NullT \\<Rightarrow> None | ClassT C \\<Rightarrow>
|
nipkow@8034
|
46 |
option_map (\\<lambda>(md,(rT,mb)). (Class md,rT)) (method (G,C) sig)"
|
nipkow@8011
|
47 |
|
nipkow@8011
|
48 |
more_spec_def "more_spec G \\<equiv> \\<lambda>((d,h),pTs). \\<lambda>((d',h'),pTs'). G\\<turnstile>d\\<preceq>d' \\<and>
|
nipkow@8011
|
49 |
list_all2 (\\<lambda>T T'. G\\<turnstile>T\\<preceq>T') pTs pTs'"
|
nipkow@8011
|
50 |
|
nipkow@8011
|
51 |
(* applicable methods, cf. 15.11.2.1 *)
|
nipkow@8011
|
52 |
appl_methds_def "appl_methds G T \\<equiv> \\<lambda>(mn, pTs). {(mh,pTs') |mh pTs'.
|
nipkow@8011
|
53 |
m_head G T (mn, pTs') = Some mh \\<and>
|
nipkow@8011
|
54 |
list_all2 (\\<lambda>T T'. G\\<turnstile>T\\<preceq>T') pTs pTs'}"
|
nipkow@8011
|
55 |
|
nipkow@8011
|
56 |
(* maximally specific methods, cf. 15.11.2.2 *)
|
nipkow@8011
|
57 |
max_spec_def "max_spec G rT sig \\<equiv> {m. m \\<in>appl_methds G rT sig \\<and>
|
nipkow@8011
|
58 |
(\\<forall>m'\\<in>appl_methds G rT sig.
|
nipkow@8011
|
59 |
more_spec G m' m \\<longrightarrow> m' = m)}"
|
nipkow@8011
|
60 |
consts
|
nipkow@8011
|
61 |
|
nipkow@8011
|
62 |
typeof :: "(loc \\<Rightarrow> ty option) \\<Rightarrow> val \\<Rightarrow> ty option"
|
nipkow@8011
|
63 |
|
nipkow@8011
|
64 |
primrec
|
nipkow@8011
|
65 |
"typeof dt Unit = Some (PrimT Void)"
|
nipkow@8011
|
66 |
"typeof dt Null = Some NT"
|
nipkow@8011
|
67 |
"typeof dt (Bool b) = Some (PrimT Boolean)"
|
nipkow@8011
|
68 |
"typeof dt (Intg i) = Some (PrimT Integer)"
|
nipkow@8011
|
69 |
"typeof dt (Addr a) = dt a"
|
nipkow@8011
|
70 |
|
nipkow@8011
|
71 |
types
|
nipkow@8011
|
72 |
javam = "vname list \\<times> (vname \\<times> ty) list \\<times> stmt \\<times> expr"
|
nipkow@8011
|
73 |
(* method body with parameter names, local variables, block, result expression *)
|
nipkow@8011
|
74 |
|
nipkow@8011
|
75 |
consts
|
nipkow@8011
|
76 |
|
nipkow@8011
|
77 |
ty_expr :: "javam env \\<Rightarrow> (expr \\<times> ty ) set"
|
nipkow@8011
|
78 |
ty_exprs:: "javam env \\<Rightarrow> (expr list \\<times> ty list) set"
|
nipkow@8011
|
79 |
wt_stmt :: "javam env \\<Rightarrow> stmt set"
|
nipkow@8011
|
80 |
|
nipkow@8011
|
81 |
syntax
|
nipkow@8011
|
82 |
|
nipkow@8011
|
83 |
ty_expr :: "javam env \\<Rightarrow> [expr , ty ] \\<Rightarrow> bool" ("_\\<turnstile>_\\<Colon>_" [51,51,51]50)
|
nipkow@8011
|
84 |
ty_exprs:: "javam env \\<Rightarrow> [expr list, ty list] \\<Rightarrow> bool" ("_\\<turnstile>_[\\<Colon>]_"[51,51,51]50)
|
nipkow@8011
|
85 |
wt_stmt :: "javam env \\<Rightarrow> stmt \\<Rightarrow> bool" ("_\\<turnstile>_ \\<surd>" [51,51 ]50)
|
nipkow@8011
|
86 |
|
nipkow@8011
|
87 |
translations
|
nipkow@8011
|
88 |
"E\\<turnstile>e \\<Colon> T" == "(e,T) \\<in> ty_expr E"
|
nipkow@8011
|
89 |
"E\\<turnstile>e[\\<Colon>]T" == "(e,T) \\<in> ty_exprs E"
|
nipkow@8011
|
90 |
"E\\<turnstile>c \\<surd>" == "c \\<in> wt_stmt E"
|
nipkow@8011
|
91 |
|
nipkow@8011
|
92 |
inductive "ty_expr E" "ty_exprs E" "wt_stmt E" intrs
|
nipkow@8011
|
93 |
|
nipkow@8011
|
94 |
(* well-typed expressions *)
|
nipkow@8011
|
95 |
|
nipkow@8011
|
96 |
(* cf. 15.8 *)
|
nipkow@8011
|
97 |
NewC "\\<lbrakk>is_class (prg E) C\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
98 |
E\\<turnstile>NewC C\\<Colon>Class C"
|
nipkow@8011
|
99 |
|
nipkow@8011
|
100 |
(* cf. 15.15 *)
|
nipkow@8011
|
101 |
Cast "\\<lbrakk>E\\<turnstile>e\\<Colon>T;
|
nipkow@8011
|
102 |
prg E\\<turnstile>T\\<Rightarrow>? T'\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
103 |
E\\<turnstile>Cast T' e\\<Colon>T'"
|
nipkow@8011
|
104 |
|
nipkow@8011
|
105 |
(* cf. 15.7.1 *)
|
nipkow@8011
|
106 |
Lit "\\<lbrakk>typeof (\\<lambda>v. None) x = Some T\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
107 |
E\\<turnstile>Lit x\\<Colon>T"
|
nipkow@8011
|
108 |
|
nipkow@8011
|
109 |
(* cf. 15.13.1 *)
|
nipkow@8011
|
110 |
LAcc "\\<lbrakk>localT E v = Some T; is_type (prg E) T\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
111 |
E\\<turnstile>LAcc v\\<Colon>T"
|
nipkow@8011
|
112 |
|
nipkow@8011
|
113 |
(* cf. 15.25, 15.25.1 *)
|
nipkow@8011
|
114 |
LAss "\\<lbrakk>E\\<turnstile>LAcc v\\<Colon>T;
|
nipkow@8011
|
115 |
E\\<turnstile>e\\<Colon>T';
|
nipkow@8011
|
116 |
prg E\\<turnstile>T'\\<preceq>T\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
117 |
E\\<turnstile>v\\<Colon>=e\\<Colon>T'"
|
nipkow@8011
|
118 |
|
nipkow@8011
|
119 |
(* cf. 15.10.1 *)
|
nipkow@8011
|
120 |
FAcc "\\<lbrakk>E\\<turnstile>a\\<Colon>Class C;
|
nipkow@8034
|
121 |
field (prg E,C) fn = Some (fd,fT)\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
122 |
E\\<turnstile>{fd}a..fn\\<Colon>fT"
|
nipkow@8011
|
123 |
|
nipkow@8011
|
124 |
(* cf. 15.25, 15.25.1 *)
|
nipkow@8011
|
125 |
FAss "\\<lbrakk>E\\<turnstile>{fd}a..fn\\<Colon>T;
|
nipkow@8011
|
126 |
E\\<turnstile>v \\<Colon>T';
|
nipkow@8011
|
127 |
prg E\\<turnstile>T'\\<preceq>T\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
128 |
E\\<turnstile>{fd}a..fn\\<in>=v\\<Colon>T'"
|
nipkow@8011
|
129 |
|
nipkow@8011
|
130 |
|
nipkow@8011
|
131 |
(* cf. 15.11.1, 15.11.2, 15.11.3 *)
|
nipkow@8011
|
132 |
Call "\\<lbrakk>E\\<turnstile>a\\<Colon>RefT t;
|
nipkow@8011
|
133 |
E\\<turnstile>ps[\\<Colon>]pTs;
|
nipkow@8011
|
134 |
max_spec (prg E) t (mn, pTs) = {((md,rT),pTs')}\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
135 |
E\\<turnstile>a..mn({pTs'}ps)\\<Colon>rT"
|
nipkow@8011
|
136 |
|
nipkow@8011
|
137 |
(* well-typed expression lists *)
|
nipkow@8011
|
138 |
|
nipkow@8011
|
139 |
(* cf. 15.11.??? *)
|
nipkow@8011
|
140 |
Nil "E\\<turnstile>[][\\<Colon>][]"
|
nipkow@8011
|
141 |
|
nipkow@8011
|
142 |
(* cf. 15.11.??? *)
|
nipkow@8011
|
143 |
Cons "\\<lbrakk>E\\<turnstile>e\\<Colon>T;
|
nipkow@8011
|
144 |
E\\<turnstile>es[\\<Colon>]Ts\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
145 |
E\\<turnstile>e#es[\\<Colon>]T#Ts"
|
nipkow@8011
|
146 |
|
nipkow@8011
|
147 |
(* well-typed statements *)
|
nipkow@8011
|
148 |
|
nipkow@8011
|
149 |
Skip "E\\<turnstile>Skip\\<surd>"
|
nipkow@8011
|
150 |
|
nipkow@8011
|
151 |
Expr "\\<lbrakk>E\\<turnstile>e\\<Colon>T\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
152 |
E\\<turnstile>Expr e\\<surd>"
|
nipkow@8011
|
153 |
|
nipkow@8011
|
154 |
Comp "\\<lbrakk>E\\<turnstile>s1\\<surd>;
|
nipkow@8011
|
155 |
E\\<turnstile>s2\\<surd>\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
156 |
E\\<turnstile>s1;; s2\\<surd>"
|
nipkow@8011
|
157 |
|
nipkow@8011
|
158 |
(* cf. 14.8 *)
|
nipkow@8011
|
159 |
Cond "\\<lbrakk>E\\<turnstile>e\\<Colon>PrimT Boolean;
|
nipkow@8011
|
160 |
E\\<turnstile>s1\\<surd>;
|
nipkow@8011
|
161 |
E\\<turnstile>s2\\<surd>\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
162 |
E\\<turnstile>If(e) s1 Else s2\\<surd>"
|
nipkow@8011
|
163 |
|
nipkow@8011
|
164 |
(* cf. 14.10 *)
|
nipkow@8011
|
165 |
Loop "\\<lbrakk>E\\<turnstile>e\\<Colon>PrimT Boolean;
|
nipkow@8011
|
166 |
E\\<turnstile>s\\<surd>\\<rbrakk> \\<Longrightarrow>
|
nipkow@8011
|
167 |
E\\<turnstile>While(e) s\\<surd>"
|
nipkow@8011
|
168 |
|
nipkow@8011
|
169 |
constdefs
|
nipkow@8011
|
170 |
|
nipkow@8011
|
171 |
wt_java_mdecl :: javam prog => cname => javam mdecl => bool
|
nipkow@8011
|
172 |
"wt_java_mdecl G C \\<equiv> \\<lambda>((mn,pTs),rT,(pns,lvars,blk,res)).
|
nipkow@8011
|
173 |
length pTs = length pns \\<and>
|
nipkow@8011
|
174 |
nodups pns \\<and>
|
nipkow@8011
|
175 |
unique lvars \\<and>
|
nipkow@8011
|
176 |
(\\<forall>pn\\<in>set pns. map_of lvars pn = None) \\<and>
|
nipkow@8011
|
177 |
(\\<forall>(vn,T)\\<in>set lvars. is_type G T) &
|
nipkow@8011
|
178 |
(let E = (G,map_of lvars(pns[\\<mapsto>]pTs)(This\\<mapsto>Class C)) in
|
nipkow@8011
|
179 |
E\\<turnstile>blk\\<surd> \\<and> (\\<exists>T. E\\<turnstile>res\\<Colon>T \\<and> G\\<turnstile>T\\<preceq>rT))"
|
nipkow@8011
|
180 |
|
nipkow@8011
|
181 |
wf_java_prog :: javam prog => bool
|
nipkow@8011
|
182 |
"wf_java_prog G \\<equiv> wf_prog wt_java_mdecl G"
|
nipkow@8011
|
183 |
|
nipkow@8011
|
184 |
end
|