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