author | huffman |
Tue, 02 Mar 2010 16:07:48 -0800 | |
changeset 35522 | f9714c7c0837 |
parent 35521 | 47eec4da124a |
child 35525 | fa231b86cb1e |
permissions | -rw-r--r-- |
32126 | 1 |
(* Title: HOLCF/Tools/Domain/domain_library.ML |
23152 | 2 |
Author: David von Oheimb |
3 |
||
4 |
Library for domain command. |
|
5 |
*) |
|
6 |
||
7 |
||
31006 | 8 |
(* infix syntax *) |
9 |
||
10 |
infixr 5 -->; |
|
11 |
infixr 6 ->>; |
|
12 |
infixr 0 ===>; |
|
13 |
infixr 0 ==>; |
|
14 |
infix 0 ==; |
|
15 |
infix 1 ===; |
|
16 |
infix 1 ~=; |
|
17 |
||
18 |
infix 9 ` ; |
|
19 |
infix 9 `% ; |
|
20 |
infix 9 `%%; |
|
21 |
||
22 |
||
23152 | 23 |
(* ----- specific support for domain ---------------------------------------- *) |
24 |
||
31006 | 25 |
signature DOMAIN_LIBRARY = |
26 |
sig |
|
35465 | 27 |
val first : 'a * 'b * 'c -> 'a |
28 |
val second : 'a * 'b * 'c -> 'b |
|
29 |
val third : 'a * 'b * 'c -> 'c |
|
30 |
val upd_second : ('b -> 'd) -> 'a * 'b * 'c -> 'a * 'd * 'c |
|
31 |
val upd_third : ('c -> 'd) -> 'a * 'b * 'c -> 'a * 'b * 'd |
|
32 |
val mapn : (int -> 'a -> 'b) -> int -> 'a list -> 'b list |
|
33 |
val atomize : Proof.context -> thm -> thm list |
|
34 |
||
31006 | 35 |
val Imposs : string -> 'a; |
31162 | 36 |
val cpo_type : theory -> typ -> bool; |
31006 | 37 |
val pcpo_type : theory -> typ -> bool; |
38 |
val string_of_typ : theory -> typ -> string; |
|
39 |
||
40 |
(* Creating HOLCF types *) |
|
41 |
val ->> : typ * typ -> typ; |
|
42 |
val mk_ssumT : typ * typ -> typ; |
|
43 |
val mk_sprodT : typ * typ -> typ; |
|
44 |
val mk_uT : typ -> typ; |
|
45 |
val oneT : typ; |
|
46 |
val mk_maybeT : typ -> typ; |
|
47 |
val mk_ctupleT : typ list -> typ; |
|
48 |
val mk_TFree : string -> typ; |
|
49 |
val pcpoS : sort; |
|
50 |
||
51 |
(* Creating HOLCF terms *) |
|
52 |
val %: : string -> term; |
|
53 |
val %%: : string -> term; |
|
54 |
val ` : term * term -> term; |
|
55 |
val `% : term * string -> term; |
|
56 |
val /\ : string -> term -> term; |
|
57 |
val UU : term; |
|
31231 | 58 |
val ID : term; |
59 |
val oo : term * term -> term; |
|
31006 | 60 |
val mk_ctuple : term list -> term; |
61 |
val mk_fix : term -> term; |
|
62 |
val mk_iterate : term * term * term -> term; |
|
63 |
val mk_fail : term; |
|
64 |
val mk_return : term -> term; |
|
65 |
val list_ccomb : term * term list -> term; |
|
66 |
val con_app2 : string -> ('a -> term) -> 'a list -> term; |
|
35497 | 67 |
val prj : ('a -> 'b -> 'a) -> ('a -> 'b -> 'a) -> 'a -> 'b list -> int -> 'a |
31006 | 68 |
val proj : term -> 'a list -> int -> term; |
69 |
val mk_ctuple_pat : term list -> term; |
|
70 |
val mk_branch : term -> term; |
|
71 |
||
72 |
(* Creating propositions *) |
|
73 |
val mk_conj : term * term -> term; |
|
74 |
val mk_disj : term * term -> term; |
|
75 |
val mk_imp : term * term -> term; |
|
76 |
val mk_lam : string * term -> term; |
|
77 |
val mk_all : string * term -> term; |
|
78 |
val mk_ex : string * term -> term; |
|
79 |
val mk_constrainall : string * typ * term -> term; |
|
80 |
val === : term * term -> term; |
|
81 |
val strict : term -> term; |
|
82 |
val defined : term -> term; |
|
83 |
val mk_adm : term -> term; |
|
84 |
val lift : ('a -> term) -> 'a list * term -> term; |
|
85 |
val lift_defined : ('a -> term) -> 'a list * term -> term; |
|
86 |
||
87 |
(* Creating meta-propositions *) |
|
88 |
val mk_trp : term -> term; (* HOLogic.mk_Trueprop *) |
|
89 |
val == : term * term -> term; |
|
90 |
val ===> : term * term -> term; |
|
91 |
val ==> : term * term -> term; |
|
92 |
val mk_All : string * term -> term; |
|
93 |
||
31288 | 94 |
(* Domain specifications *) |
95 |
eqtype arg; |
|
35521 | 96 |
type cons = string * arg list; |
31006 | 97 |
type eq = (string * typ list) * cons list; |
35519 | 98 |
val mk_arg : (bool * Datatype.dtyp) * string -> arg; |
31006 | 99 |
val is_lazy : arg -> bool; |
100 |
val rec_of : arg -> int; |
|
31738
7b9b9ba532ca
discontinued ancient tradition to suffix certain ML module names with "_package"
haftmann
parents:
31288
diff
changeset
|
101 |
val dtyp_of : arg -> Datatype.dtyp; |
31006 | 102 |
val vname : arg -> string; |
103 |
val upd_vname : (string -> string) -> arg -> arg; |
|
104 |
val is_rec : arg -> bool; |
|
105 |
val is_nonlazy_rec : arg -> bool; |
|
106 |
val nonlazy : arg list -> string list; |
|
107 |
val nonlazy_rec : arg list -> string list; |
|
108 |
val %# : arg -> term; |
|
109 |
val /\# : arg * term -> term; |
|
110 |
val bound_arg : ''a list -> ''a -> term; (* ''a = arg or string *) |
|
111 |
val idx_name : 'a list -> string -> int -> string; |
|
112 |
val app_rec_arg : (int -> term) -> arg -> term; |
|
31228 | 113 |
val con_app : string -> arg list -> term; |
31738
7b9b9ba532ca
discontinued ancient tradition to suffix certain ML module names with "_package"
haftmann
parents:
31288
diff
changeset
|
114 |
val dtyp_of_eq : eq -> Datatype.dtyp; |
31228 | 115 |
|
31006 | 116 |
|
117 |
(* Name mangling *) |
|
118 |
val strip_esc : string -> string; |
|
119 |
val extern_name : string -> string; |
|
120 |
val dis_name : string -> string; |
|
121 |
val mat_name : string -> string; |
|
122 |
val pat_name : string -> string; |
|
123 |
end; |
|
124 |
||
31023 | 125 |
structure Domain_Library :> DOMAIN_LIBRARY = |
31006 | 126 |
struct |
23152 | 127 |
|
35465 | 128 |
fun first (x,_,_) = x; |
129 |
fun second (_,x,_) = x; |
|
130 |
fun third (_,_,x) = x; |
|
131 |
||
132 |
fun upd_first f (x,y,z) = (f x, y, z); |
|
133 |
fun upd_second f (x,y,z) = ( x, f y, z); |
|
134 |
fun upd_third f (x,y,z) = ( x, y, f z); |
|
135 |
||
136 |
fun mapn f n [] = [] |
|
137 |
| mapn f n (x::xs) = (f n x) :: mapn f (n+1) xs; |
|
138 |
||
139 |
fun foldr'' f (l,f2) = |
|
140 |
let fun itr [] = raise Fail "foldr''" |
|
141 |
| itr [a] = f2 a |
|
142 |
| itr (a::l) = f(a, itr l) |
|
143 |
in itr l end; |
|
144 |
||
145 |
fun atomize ctxt thm = |
|
146 |
let |
|
147 |
val r_inst = read_instantiate ctxt; |
|
148 |
fun at thm = |
|
149 |
case concl_of thm of |
|
150 |
_$(Const("op &",_)$_$_) => at(thm RS conjunct1)@at(thm RS conjunct2) |
|
151 |
| _$(Const("All" ,_)$Abs(s,_,_))=> at(thm RS (r_inst [(("x", 0), "?" ^ s)] spec)) |
|
152 |
| _ => [thm]; |
|
153 |
in map zero_var_indexes (at thm) end; |
|
154 |
||
23152 | 155 |
exception Impossible of string; |
156 |
fun Imposs msg = raise Impossible ("Domain:"^msg); |
|
157 |
||
158 |
(* ----- name handling ----- *) |
|
159 |
||
31288 | 160 |
val strip_esc = |
161 |
let fun strip ("'" :: c :: cs) = c :: strip cs |
|
162 |
| strip ["'"] = [] |
|
163 |
| strip (c :: cs) = c :: strip cs |
|
164 |
| strip [] = []; |
|
165 |
in implode o strip o Symbol.explode end; |
|
23152 | 166 |
|
31288 | 167 |
fun extern_name con = |
168 |
case Symbol.explode con of |
|
169 |
("o"::"p"::" "::rest) => implode rest |
|
170 |
| _ => con; |
|
23152 | 171 |
fun dis_name con = "is_"^ (extern_name con); |
172 |
fun dis_name_ con = "is_"^ (strip_esc con); |
|
173 |
fun mat_name con = "match_"^ (extern_name con); |
|
174 |
fun mat_name_ con = "match_"^ (strip_esc con); |
|
175 |
fun pat_name con = (extern_name con) ^ "_pat"; |
|
176 |
fun pat_name_ con = (strip_esc con) ^ "_pat"; |
|
177 |
||
31162 | 178 |
fun cpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, @{sort cpo}); |
30910 | 179 |
fun pcpo_type sg t = Sign.of_sort sg (Sign.certify_typ sg t, @{sort pcpo}); |
26939
1035c89b4c02
moved global pretty/string_of functions from Sign to Syntax;
wenzelm
parents:
26012
diff
changeset
|
180 |
fun string_of_typ sg = Syntax.string_of_typ_global sg o Sign.certify_typ sg; |
23152 | 181 |
|
182 |
(* ----- constructor list handling ----- *) |
|
183 |
||
31006 | 184 |
type arg = |
31738
7b9b9ba532ca
discontinued ancient tradition to suffix certain ML module names with "_package"
haftmann
parents:
31288
diff
changeset
|
185 |
(bool * Datatype.dtyp) * (* (lazy, recursive element) *) |
31288 | 186 |
string; (* argument name *) |
31006 | 187 |
|
188 |
type cons = |
|
31288 | 189 |
string * (* operator name of constr *) |
190 |
arg list; (* argument list *) |
|
31006 | 191 |
|
192 |
type eq = |
|
31288 | 193 |
(string * (* name of abstracted type *) |
194 |
typ list) * (* arguments of abstracted type *) |
|
195 |
cons list; (* represented type, as a constructor list *) |
|
23152 | 196 |
|
31228 | 197 |
val mk_arg = I; |
31229 | 198 |
|
35519 | 199 |
fun rec_of ((_,dtyp),_) = |
33971 | 200 |
case dtyp of Datatype_Aux.DtRec i => i | _ => ~1; |
31229 | 201 |
(* FIXME: what about indirect recursion? *) |
202 |
||
35519 | 203 |
fun is_lazy arg = fst (fst arg); |
204 |
fun dtyp_of arg = snd (fst arg); |
|
205 |
val vname = snd; |
|
206 |
val upd_vname = apsnd; |
|
23152 | 207 |
fun is_rec arg = rec_of arg >=0; |
208 |
fun is_nonlazy_rec arg = is_rec arg andalso not (is_lazy arg); |
|
33317 | 209 |
fun nonlazy args = map vname (filter_out is_lazy args); |
210 |
fun nonlazy_rec args = map vname (filter is_nonlazy_rec args); |
|
23152 | 211 |
|
31231 | 212 |
|
213 |
(* ----- combinators for making dtyps ----- *) |
|
214 |
||
33971 | 215 |
fun mk_uD T = Datatype_Aux.DtType(@{type_name "u"}, [T]); |
216 |
fun mk_sprodD (T, U) = Datatype_Aux.DtType(@{type_name "**"}, [T, U]); |
|
217 |
fun mk_ssumD (T, U) = Datatype_Aux.DtType(@{type_name "++"}, [T, U]); |
|
218 |
fun mk_liftD T = Datatype_Aux.DtType(@{type_name "lift"}, [T]); |
|
219 |
val unitD = Datatype_Aux.DtType(@{type_name "unit"}, []); |
|
220 |
val boolD = Datatype_Aux.DtType(@{type_name "bool"}, []); |
|
31231 | 221 |
val oneD = mk_liftD unitD; |
222 |
val trD = mk_liftD boolD; |
|
223 |
fun big_sprodD ds = case ds of [] => oneD | _ => foldr1 mk_sprodD ds; |
|
224 |
fun big_ssumD ds = case ds of [] => unitD | _ => foldr1 mk_ssumD ds; |
|
225 |
||
35519 | 226 |
fun dtyp_of_arg ((lazy, D), _) = if lazy then mk_uD D else D; |
35521 | 227 |
fun dtyp_of_cons (_, args) = big_sprodD (map dtyp_of_arg args); |
31231 | 228 |
fun dtyp_of_eq (_, cons) = big_ssumD (map dtyp_of_cons cons); |
229 |
||
230 |
||
23152 | 231 |
(* ----- support for type and mixfix expressions ----- *) |
232 |
||
30910 | 233 |
fun mk_uT T = Type(@{type_name "u"}, [T]); |
234 |
fun mk_cfunT (T, U) = Type(@{type_name "->"}, [T, U]); |
|
235 |
fun mk_sprodT (T, U) = Type(@{type_name "**"}, [T, U]); |
|
236 |
fun mk_ssumT (T, U) = Type(@{type_name "++"}, [T, U]); |
|
237 |
val oneT = @{typ one}; |
|
238 |
||
239 |
val op ->> = mk_cfunT; |
|
240 |
||
241 |
fun mk_TFree s = TFree ("'" ^ s, @{sort pcpo}); |
|
23152 | 242 |
|
243 |
(* ----- support for term expressions ----- *) |
|
244 |
||
245 |
fun %: s = Free(s,dummyT); |
|
246 |
fun %# arg = %:(vname arg); |
|
247 |
fun %%: s = Const(s,dummyT); |
|
248 |
||
249 |
local open HOLogic in |
|
250 |
val mk_trp = mk_Trueprop; |
|
251 |
fun mk_conj (S,T) = conj $ S $ T; |
|
252 |
fun mk_disj (S,T) = disj $ S $ T; |
|
253 |
fun mk_imp (S,T) = imp $ S $ T; |
|
254 |
fun mk_lam (x,T) = Abs(x,dummyT,T); |
|
255 |
fun mk_all (x,P) = HOLogic.mk_all (x,dummyT,P); |
|
256 |
fun mk_ex (x,P) = mk_exists (x,dummyT,P); |
|
24680 | 257 |
fun mk_constrainall (x,typ,P) = %%:"All" $ (TypeInfer.constrain (typ --> boolT) (mk_lam(x,P))); |
23152 | 258 |
end |
259 |
||
260 |
fun mk_All (x,P) = %%:"all" $ mk_lam(x,P); (* meta universal quantification *) |
|
261 |
||
262 |
infixr 0 ===>; fun S ===> T = %%:"==>" $ S $ T; |
|
263 |
infixr 0 ==>; fun S ==> T = mk_trp S ===> mk_trp T; |
|
264 |
infix 0 ==; fun S == T = %%:"==" $ S $ T; |
|
265 |
infix 1 ===; fun S === T = %%:"op =" $ S $ T; |
|
266 |
infix 1 ~=; fun S ~= T = HOLogic.mk_not (S === T); |
|
267 |
||
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
268 |
infix 9 ` ; fun f ` x = %%: @{const_name Rep_CFun} $ f $ x; |
23152 | 269 |
infix 9 `% ; fun f`% s = f` %: s; |
270 |
infix 9 `%%; fun f`%%s = f` %%:s; |
|
26012 | 271 |
|
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
272 |
fun mk_adm t = %%: @{const_name adm} $ t; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
273 |
val ID = %%: @{const_name ID}; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
274 |
fun mk_strictify t = %%: @{const_name strictify}`t; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
275 |
fun mk_ssplit t = %%: @{const_name ssplit}`t; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
276 |
fun mk_sscase (x, y) = %%: @{const_name sscase}`x`y; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
277 |
fun mk_fup (t,u) = %%: @{const_name fup} ` t ` u; |
26012 | 278 |
val ONE = @{term ONE}; |
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
279 |
fun mk_iterate (n,f,z) = %%: @{const_name iterate} $ n ` f ` z; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
280 |
fun mk_fix t = %%: @{const_name fix}`t; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
281 |
fun mk_return t = %%: @{const_name Fixrec.return}`t; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
282 |
val mk_fail = %%: @{const_name Fixrec.fail}; |
26012 | 283 |
|
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
284 |
fun mk_branch t = %%: @{const_name Fixrec.branch} $ t; |
26012 | 285 |
|
286 |
val pcpoS = @{sort pcpo}; |
|
287 |
||
23152 | 288 |
val list_ccomb = Library.foldl (op `); (* continuous version of list_comb *) |
289 |
fun con_app2 con f args = list_ccomb(%%:con,map f args); |
|
290 |
fun con_app con = con_app2 con %#; |
|
291 |
fun if_rec arg f y = if is_rec arg then f (rec_of arg) else y; |
|
292 |
fun app_rec_arg p arg = if_rec arg (fn n => fn x => (p n)`x) I (%# arg); |
|
293 |
fun prj _ _ x ( _::[]) _ = x |
|
31288 | 294 |
| prj f1 _ x (_::y::ys) 0 = f1 x y |
295 |
| prj f1 f2 x (y:: ys) j = prj f1 f2 (f2 x y) ys (j-1); |
|
23152 | 296 |
fun proj x = prj (fn S => K(%%:"fst" $S)) (fn S => K(%%:"snd" $S)) x; |
297 |
fun lift tfn = Library.foldr (fn (x,t)=> (mk_trp(tfn x) ===> t)); |
|
298 |
||
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
299 |
fun /\ v T = %%: @{const_name Abs_CFun} $ mk_lam(v,T); |
23152 | 300 |
fun /\# (arg,T) = /\ (vname arg) T; |
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
301 |
infixr 9 oo; fun S oo T = %%: @{const_name cfcomp}`S`T; |
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
302 |
val UU = %%: @{const_name UU}; |
23152 | 303 |
fun strict f = f`UU === UU; |
304 |
fun defined t = t ~= UU; |
|
33396 | 305 |
fun cpair (t,u) = %%: @{const_name Pair} $ t $ u; |
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
306 |
fun spair (t,u) = %%: @{const_name spair}`t`u; |
23152 | 307 |
fun mk_ctuple [] = HOLogic.unit (* used in match_defs *) |
31288 | 308 |
| mk_ctuple ts = foldr1 cpair ts; |
23152 | 309 |
fun mk_ctupleT [] = HOLogic.unitT (* used in match_defs *) |
31288 | 310 |
| mk_ctupleT Ts = foldr1 HOLogic.mk_prodT Ts; |
23152 | 311 |
fun mk_maybeT T = Type ("Fixrec.maybe",[T]); |
30595
c87a3350f5a9
proper spacing before ML antiquotations -- note that @ may be part of symbolic ML identifiers;
wenzelm
parents:
30190
diff
changeset
|
312 |
fun cpair_pat (p1,p2) = %%: @{const_name cpair_pat} $ p1 $ p2; |
26012 | 313 |
val mk_ctuple_pat = foldr1 cpair_pat; |
23152 | 314 |
fun lift_defined f = lift (fn x => defined (f x)); |
31986 | 315 |
fun bound_arg vns v = Bound (length vns - find_index (fn v' => v' = v) vns - 1); |
23152 | 316 |
|
317 |
fun cont_eta_contract (Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body)) = |
|
31288 | 318 |
(case cont_eta_contract body of |
319 |
body' as (Const("Cfun.Rep_CFun",Ta) $ f $ Bound 0) => |
|
320 |
if not (0 mem loose_bnos f) then incr_boundvars ~1 f |
|
321 |
else Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body') |
|
322 |
| body' => Const("Cfun.Abs_CFun",TT) $ Abs(a,T,body')) |
|
323 |
| cont_eta_contract(f$t) = cont_eta_contract f $ cont_eta_contract t |
|
324 |
| cont_eta_contract t = t; |
|
23152 | 325 |
|
326 |
fun idx_name dnames s n = s^(if length dnames = 1 then "" else string_of_int n); |
|
31288 | 327 |
|
23152 | 328 |
end; (* struct *) |